数据结构(I卷)

1、数据结构试卷（I卷）班级:学号:姓名:得分:题号三四五七八九十成绩复核得分 阅卷题目部分，（卷面共有45题,100分，各大题标有题量和总分）一、判断正误（11小题，共11分）1. 即使对不含相同元素的同意输入序列进行沥组不同的、合法的入栈和出栈组合操作，所得的输出序也一定相同。（）2. 栈和队列都是限制存取点的线性结构。（）3. 任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。（ ）4. 己知二义树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。（）5. 有n个数存放在伊维数组hl-n中，在进行顺序查找时.这n个数的排列有序或无序其平均査找

2、长度小同。（）6. 二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。7. 用希尔（Shell）方法排序时，若关键字的初始排序朵乱无序，则排序效率就低。（ ）8. 外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决丁内部排序的时间9. 完全二叉树就是满二叉树。（）10. 在散列法中，一个可用散列函数必须保证绝对不产生冲突。（）11 快速排序是对起泡排序的一种改进。（）二. 单项选择题（20小题，共42分）1. 在双向循环链表中，在P指针所指的结点后插入一个指针q所指向的新结点，其修改指针的操作是a、LBLB2. 双向链表中有两个指针域，llink和：

3、clink分别指向前趋及后继，设p指向链表中 的一个结点，现要求删去P所指结点，则正确的删除是（）（链中结点数大于2, p不是第一个结点）A 、 pill ink* rlink:=p1 link;p 11 ink* .rlink:二 p .rlink;dispose （p）;B 、 dispose（p）;pllink.rlink:二p*1link;P1link*, rlink:二p*rlink;C 、 pill ink ：rlink:=p* 1 link;dispose （p） ;1 link .rlink：二p* rlink;D、以上A, B, C都不对。3. 某堆栈的输入序列为乳b, c

4、, d,下面的四个序列中，不可能是它的输出序列的是A、a c, b, dB、 b, c, d, aC、 c, d, b,aD. d, c, a b4. 栈和队都是A、顺序存储的线性结构B、链式存储的非线性结构C、限制存取点的线性结构D、限制存取点的非线性结构5. 数组的基本操作主要包括。A、建立与删除B、索引与修改C、访问与修改D、访问与索引6. 下面说法不正确的是A、广义表的表头总是一个广义表B、广义表的表尾总是一个广义表C、广义表难以用顺序存储结构D、广义表可以是一个多层次的结构7. 设有一表示算术表达式的二义树（见下图），它所表示的算术表达式是A、A*B+C/(D*E) + (F-G)B

5、、(A*B+C)/(D*E)+(F-D、 A*B+C/D*E+F-GG) C、 (A*B+C)/(D*E+ (F-G)8深度为6 （根据的层次为1 ）的二叉树至多有（）个结点。A、64B、63C、31D、329. 下面不正确的说法是（1）在AOE网中.减小任一关键活动上的权值后，整个工期也就相应减小(2) A0E 一网工程工期为关键活动上的权之和；(3) 在关键活路径上的活动都是关键活动，而关键活动也必在关键路径上,A、(1)B、(2)C、(3)D、(2)10. 下列说法中不正确的是A、无向图中的极大连通子图称为连通分量B、连通图的广度优先搜索中一般要采用队列來暂存刚访问过的顶点C、图的深度优

6、先搜索中一般耍采用栈來暂存刚访问过的顶点D、有向图的遍历不可采用广度优先搜索方法11. 设有一个按各元素的值排好序的线性表II长度大于2,对给定的值K,分别用顺序查找法和二分法查找一个与K相等的元素，比较次数分别s和b：在查找不成功的情 况下，正确的s和b的数量关系是A、 总有s二bB、总有sbC、总有sb D、与K大小有关12. 设散列表的长m二14,散列函数为h(k)=k%ll,表中己有4个记录(如图所示)，如 果采用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是Ax 8B、3C、5D、9d13. 归并排序中，归并的趟数是A、0(n)B、0(logn)C、O(nlogn)D、

7、0(n*n)14. 下列排序算法中，在待排序数据己有序时，花费时间反而最多的是()排序。A、冒泡 B、希尔 C、快速 D、堆13.快速排序在最坏情况下时间复杂度是叵會比（）的性能差。A、堆排序B、起泡排序C、选择排序16. 若对一个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元 素所需要的时间复朵性为A、0（1）B、|因|C、| 因申D、闻17. 数据表示是指数据。A、书写在纸上B、从机外转为机内C、磁盘中的数据D、光盘中的数据18以下数据结构中，哪一个是线性结构阵D、串B、高度等于其结点数C.任一D、任一结点无右孩子A.空或只有一个结点结点无左孩子）的二叉树。19某二叉树的前

8、序和后序序列正好相反，则该二叉树一定是（20.在10阶B-树中根结点所包含的关键码个数最多为（），最少为A、 1B、2D、10三. 填空题（14小题，共47分）1. 在一个不带头结点单链表中，在表头插入或删除与在其他位置插入或删除其操作过程O2. 根据需要，用适当的语句填入下面算法的中：问题：设有n件物品，重量分别为wl,w2,w3,-,wn和一个能装载总重量为T的背包。 能否从n件物品中选择若干件恰好使它们的重量之和等于T。若能，则背包问题有解， 否则无解。解此问题的算法如下：FUNCTION kanp_stack(VAR stack, w:ARRAYl. . nZ OF real: VAR

9、 top:integer;T：real):boolean;wl： n存放n件物品的重量，依次从中取出物品放入背包中，检查背包 重量，若不超过T,则装入，否则弃之，取下一个物品试之。若有解则返回函数值 true,否则返回 false BEGINtop:=0;i：=l； i指示待选物品WHILE (1) AND (2)DOIF (3) OR (4) AND (i0)THEN i: = (7); 取出栈顶物品(8) : T:= (9) ;恢复 丁值i：=i+l准备挑选下一件物品；RETURN(10) 背包无解 END;3. 设有三对角矩阵如下图所示，将带状区域中的元素g (|i-j|=l)放在一维数

10、组B 中，则B的大小为。元素囲在B中的位置是下标从0开始计)a4. 二叉树结点的对称序序列为A, B, C, D, E, F, G,后序序列为B, D, C, A, F, G, E,则该二叉树结点的前序序列为，则该二叉树对应的树林包括棵树。5. 对于前序遍历和中序遍历结果相同的二义树为对于前序遍历和后序遍历结果相同的二叉树为.A、一般二义树B、只有根结点的二叉树C、根结点无左孩子的二叉树 D、根结点无右孩子的二叉树E、所有结点只有左子树的二叉树 F、所有结点只有右子树的二叉树6. 设有N个结点的完全二义树顺序存放在向量A1:N中，其下标值最大的分支结点为7. 具有n个结点的满二义树，其叶结点的个数是8. n个顶点的连通图用邻接矩阵表示时，该矩阵至少有个非零元崇。9. 对长度为n的査找表进行查找时.假定查找笫i个元素的概率为Pi.,查找长度（即在查找过程中依次同有关元素比较的总次数）为Ci,则在查找成功情况下的平均 查找长度的计算公式为。10. 对闭散列表來说，的方法就是处理冲突的方法。11. 在一棵有n个结点的非平衡二义树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为。12.