数据结构模拟试1.doc

1、数据结构模拟试题(一)一 单选题1.线性表的表态存储结构与顺序存储结构相比优点是( )A.所有的操作算法实现简单 B.便于随机存储C.便于插入与删除 D.便于利用零散的存储空间2.在双向链表存储结构中,删除 P 所指向的结点时须修改指针( )A.P-next-prior=P-prior P-prior-next=P-nextB.P-next=P-next-next P-next-prior=PC.P-prior-next=P P-prior=P-prior-priorD.P-prior=P-next-next P-next=P-prior-prior3.以下序列不是堆的是( )A.100,85

2、,98,77,80,60,82,40,20,10,66B.100,98,85,82,80,77,66,60,40,20,10C.10,20,40,60,66,77,80,82,85,98,100D.100,85,40,77,80,60,66,98,82,10,204.对任意 7 个关键字进行排序,至少要进行多少次关键字之间的比较.A. 13 式 B. 1 C. 15 D. 165.对给出的一组关键字14,5,19,20,11,19若按关键字非递减排序,第一趟排序结果为14,5,19,20,11,19,问采用的排序方法是( )A.简单选择排序 B.快速排序 C.希尔排序 D.二路归并排序6.有数

3、据53,30,37,12,45,24,96,从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,则应选择下面的序列输入( )A.45 ,24,53,12,37,96,30 B.37,24,12,30,53,45,96C.12,24,30,37,45,53,96 D.30,24,12,37,45,96,537.设栈的输入序列是 1,2,3,4n 若输出序列的第一个元素是 n,则第 i 个输出元素()A.不确定 B.n-i-1 C.i D.n-i8.字符串ababaabab的 nextval 为( )A.(0,1,0,1,0,4,1,0,1) B.(0,1,0,1,0,2,1,0,1) C

4、.(0,1,0,1,0,0,0,1,1)D.(0,1,0,1,0,1,0,1,1)9.设有 13 个值,用它们组成一棵哈夫曼树,则该哈无曼树的共有( )个结点.A.13 B.12 C.26 D.2510.如果 T2 是由有序树 T 转换而来的二叉树,那么 T 中的结点的后序就是 T2 中的结点的( )A.先序 B.中序 C.后序 D.层次序列二 填空题1. 8 层完全二叉树至少有( )个结点,拥有 100 个结点的完全二叉树的最大层数为( ).2. 用一维数组存放一棵完全二叉树 ABCDEFGHIJKL,则后序遍历该二叉树的结点序列为（）3. 哈夫曼树是带权路径( )的树,通常权值较大的结点离

5、根( ).4. 深度为 K 的完全二叉树,其前 K-1 层共有( )个结点.5. 一个非连通无向图,共有 28 条边,则该图至少有( )个顶点.6.克鲁斯卡尔算法的时间复杂度是( ),它对( )图较适用.7.从源点到汇点长度最大的路径称为关键路径,该路径上的活动称为( )8.深度优先遍历类似于树的( )遍历.它所用的数据结构是( )9.对一个线性表分别进行遍历与逆置运算,其最好的时间复杂度分别为( )和( ).10.一个循环队列存于 AM中,队首和队尾指针分别为 front 和 rear,队满的条件是( ).三 判断题1.顺序文件是利用磁盘的特有的性质实现的,因此顺序文件只能存放在磁盘中.(

6、)2.用希尔方法排序时,若关键字的初始排序杂乱无序,则排序效率就低.( )3.任一二叉树平均查找时间都小于顺序查找法查找同样的线性表的平均查找时间.( )4.若连通图上各边权值均不相同,则该图的最小生成树是唯一的.( )5.不使用递归也能实现二叉树的先序,中序和后序的遍历.( )6.任何一个非空的广义表,其表头可能是单元素或广义表,其表尾必定是广义表.( )7.稀疏矩阵压缩存储后,必会失去随机存取功能.( )8.KMP 算法的最大特点是指示主串的指针不需回溯.( )9.栈的输入序列为 1,2,3,4,n,输出序列为 a1,a2,an,若 ai=n(1a(i+1)an.( )10.在线性表顺序存

7、储中,插入和删除元素时,移动元素的个数与该元素的位置有关.( )四 综合应用题1.给定(已生成)一个带头结点的单链表,设 HEAD 为头指针,结点的结构为(data,next),data 主整数元素,next 为指针,试定一算法,按递增次序输出单链表的数据元素,并释放结点所占的存储空间,(不允许使用数组作辅助空间).2.给定一组关键字 29,18,25,47,58,12,51,10 分别写出下列各种排序方法进行排序的变化过程.(1)归并排序,每归并一次书写一次序(2)快速排序,每划分一次书写一次序(3)堆排序,先建一个堆,然后每从堆顶取下一个元素后,将堆调整一次.3.有一个二叉树中序序列为:A

8、BCEFGHD 后序序列为:ABFHGEDC,请画出此二叉树.4.使用哈希函数 hash(x)=x mod 11 把数据 1,13,12,34,38,33,27,22 插入到哈希表中.(1)用线性探测再散列法构造哈希表.(2)使用链地址法构造哈希表.(3)针对上面的情况,确定其装填因子,并计算线性探测再散列法与链地址法的查找成功所需的平均查找次数以及查找不成功所需的探查次数.哈希表的长度为 11, 地址空间为 0-105.用深度优先遍历如图的所示的无向图,试给出以 A 为开始结点的顶点的访问序列(同一个顶点的多个邻接点,按字母顺序访问),并给出一棵最小生成树.V(G)=A,B,C,D,E,F,

9、G,H,I,JE(G)=(A B 7)(A D 4)(A E 6)(A H 3)(B E 4)(B F 11)(B I 5)(C F 7)(C J 6)(C G 4)(D E 5)(D H 2)(E F 4 )(E H 1)(E I 6)(F I 5)(F G 8)(G J 5)(H I 4)数据结构模拟试题(一)参考答案A BD F GEH ICJ一 单选题 C A D C C B B A D B二 填空题1 ， 23最短，较近 4（） 5 6O(E*logE) ,边少 7关键活动8前序，栈 9（n） ，（n）10(rear+1)%M=front三 判断题 四 综合应用void increa

10、se(lklist *head)Lklist *p,*q,*r;Int min; P=head-next;While(p!=NULL) q=NULL;Min=p-data;R=p;While(r-next!=NULL)If(r-next-datanext-dataR=r-next;Printf(“%d”,min);If(q=NULL) P=p-next;Else q-next=q-next-next;2.(1)18,29,25,47,12,58,10,51 18,25,29,47,10,12,51,58 10,12,18,25,29,47,51,58(2)10,18,25,12,29,58,5

11、1,47 10,18,25,12,29,47,51,58 10 12 18 25 29 47 51 58(3)初堆： 58 47 51 29 18 12 25 10 51 47 25 29 18 12 10 5847 29 25 10 18 12 51 58 29 18 25 10 12 47 51 5825 18 12 10 29 47 51 58 18 10 12 25 29 47 51 5812 10 18 25 29 47 51 58 10 12 18 25 29 47 51 583.4.(1)地址 0 1 2 3 4 5 6 7 8 9 10数据 33 1 13 12 34 38 27 22(2)0CBADEGHF33 22 装填因子：线性探测法：成功：（）不成功：u*（1+1+1+9+8+7+6+5+4+3+2）=47/3链地址法：成功：（）不成功：u1/11*(3+4+2+1+1+3+1+1+1+1+1)=19/115.访问序列为：123 4 56 7 8 9 10 1 34 1213 27 38A BD F GEH ICJ