大学《数据结构》试题及答案

《大学《数据结构》试题及答案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、大学《数据结构》试题及答案　　　　数据结构是计算机存储、组织数据的方式以下是由阳光网小编整理关于大学《数据结构》试题的内容希望大家喜欢　　　　1.属性与服务相同的对象构成类类中的每个对象称为该类的一——·　　　　2.在类的继承结构中位于上层的类叫做一——其下层的类则叫做类.　　　　3.若设串S=“documentHash.docO”则诙字符串S的长度为——·　　　　4.线性表的链接存储只能通过—————————顺序访问　　　　5.设链栈中结点的结构为(datalink)栈顶指针为top则向该链栈插入、—个新结点*p　　　　时应依次执行—————————————和一—

2、———操作　　　　6.广义表的深度定义为广义表中括号被嵌套的——一·　　　　7.在一棵高度为h的完全二又树中最少含有——个结点.假定树根结点的高度为O.　　　　8.从有序击(1210304356780295)中折半搜索56和98元素时其搜索长度分别为——和——·　　　　9n个(n>o)顶点的连通无向图中各顶点的度之和最少为————·　　　　10.设图的顶点数为n则求解最短路径的Dijkstra算法的时间复杂度为————·　　　　11.给定一组数据对象的关键码为{467956384084}则利用堆排序方法建立的初始最大堆的堆首和堆尾的关键码分别为——和——·L2.在索引

3、表中着一个索引项对应数据对象表中的一个表项0C称此索引为稠密索引　　　　若对应数据对象表中的若干表项则称此索引为——一索引.　　　　答案　　　　1.实例　　　　2.基类派生(或于类)　　　　3.16　　　　4.链接指针　　　　5.p一>Link=toptop=p　　　　6.重数　　　　7.2h　　　　8.32　　　　9.2(n1)　　　　10O(n2)　　　　11.8446　　　　12稀疏　　　　1、填空题(每小题2分本题满分20分)　　　　(1)C++语言中数组是按行优先顺序存储的假设定义了一个二维数组A[20][30]每个元素占两个字节其起始地址为2140则二维数

4、组A的最后一个数据元素的地址为2140+2*(30*201)=3338(3338,3339)　　　　(2)若AB是两个单链表链表长度分别为n和m其元素值递增有序将A和B归并成一个按元素值递增有序的单链表并要求辅助空间为O(1)则实现该功能的算法的时间复杂度为O(m+n)　　　　(3)快速排序的平均时间复杂度是　　　　(4)假设有一个包含9个元素的最小堆存放在数组A中则一定比A[3]大的元素有个;一定比A[3]小的元素有个(元素从第0个位置开始存放)　　　　(5)广义表(((A)),(B,C),D,((A),((E,F))))的长度是深度是　　　　(6)有10个元素的有

5、序表采用折半查找需要比较4次才可找到的元素个数为(7)当两个栈共享一存储区时栈利用一维数组A[n]表示两栈顶指针为top[0]与top[1]则栈满时的判断条件为top[0]+1=top[1]或者top[0]=top[1]+1(8)假设计算斐波那契数的函数Fib(longn)定义如下：　　　　longFib(longn){if(n<=1)returnn;　　　　elsereturnFib(n1)+Fib(n2)}　　　　计算Fib(5)时的递归调用树(即指明函数调用关系的树)的高度是4假设叶子结点所在的高度为0　　　　(9)完全二叉树按照层次次序自顶向下同层从左到右顺序

6、从0开始编号时编号为i的结点的左子结点的编号为2*i+1　　　　(10)假设用子女—兄弟链表方式表示森林对应的二叉树的根结点是p那么森林的第三棵树的根结点在二叉树中对应的结点是：p>rightchild>rightchild假　　　　2、选择题(每小题2分本题满分20分)　　　　(1)如果能够在只知道指针p指向链表中任一结点不知道头指针的情况下将结点*p从链　　　　表中删除则这个链表结构应该是：(B,C)(多选题)A.单链表B.循环链表C.双向链表D.带头结点的单链表(2)以下种矩阵压缩存储后会失去随机存取的功能?(A)　　　　A.稀疏矩阵B.对称矩阵C.对角矩阵D.

7、上三角矩阵　　　　(3)下面一方法可以判断出一个有向图是否有环(回路)：(B)(选AB也对)　　　　A.广度优先遍历B.拓扑排序C.求最短路径D.求关键路径(4)n个结点的线索二叉树(没有头结点)上含有的线索数为(B)　　　　A.2nB.nlC.n+lD.n　　　　(5)循环队列存储在数组A[0..m]中则入队时队尾指针rear的操作为(D)　　　　A.rear=rear+1B.rear=(rear+1)mod(m1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)　　　　(6)使用加权规则得到改进的Union操作