数据结构模拟试1.doc

数据结构模拟试题(一)一 单选题 1.线性表的表态存储结构与顺序存储结构相比优点是( ) A.所有的操作算法实现简单 B.便于随机存储 C.便于插入与删除 D.便于利用零散的存储空间 2.在双向链表存储结构中,删除P所指向的结点时须修改指针( ) A.P-next-prior=P-prior P-prior-next=P-next B.P-next=P-next-next P-next-prior=P C.P-prior-next=P P-prior=P-prior-prior D.P-prior=P-next-next P-next=P-prior-prior 3.以下序列不是堆的是( ) A.100,85,98,77,80,60,82,40,20,10,66B.100,98,85,82,80,77,66,60,40,20,10 C.10,20,40,60,66,77,80,82,85,98,100D.100,85,40,77,80,60,66,98,82,10,20 4.对任意7个关键字进行排序,至少要进行多少次关键字之间的比较. A. 13式 B. 1 C. 15 D. 16 5.对给出的一组关键字14,5,19,20,11,19若按关键字非递减排序,第一趟排序结果为14,5,19,20,11,19,问采用的排序方法是( ) A.简单选择排序B.快速排序 C.希尔排序 D.二路归并排序 6.有数据53,30,37,12,45,24,96,从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,则应选择下面的序列输入( ) A.45 ,24,53,12,37,96,30 B.37,24,12,30,53,45,96 C.12,24,30,37,45,53,96 D.30,24,12,37,45,96,53 7.设栈的输入序列是1,2,3,4n若输出序列的第一个元素是n,则第i个输出元素() A.不确定 B.n-i-1 C.i D.n-i 8.字符串ababaabab的nextval为( ) A.(0,1,0,1,0,4,1,0,1) B.(0,1,0,1,0,2,1,0,1) C.(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.25 10.如果T2是由有序树T转换而来的二叉树,那么T中的结点的后序就是T2中的结点的( ) A.先序 B.中序 C.后序 D.层次序列二 填空题 1. 8层完全二叉树至少有( )个结点,拥有100个结点的完全二叉树的最大层数为( ). 2. 用一维数组存放一棵完全二叉树ABCDEFGHIJKL,则后序遍历该二叉树的结点序列为（） 3. 哈夫曼树是带权路径( )的树,通常权值较大的结点离根( ). 4. 深度为K的完全二叉树,其前K-1层共有( )个结点. 5. 一个非连通无向图,共有28条边,则该图至少有( )个顶点. 6.克鲁斯卡尔算法的时间复杂度是( ),它对( )图较适用. 7.从源点到汇点长度最大的路径称为关键路径,该路径上的活动称为( ) 8.深度优先遍历类似于树的( )遍历.它所用的数据结构是( ) 9.对一个线性表分别进行遍历与逆置运算,其最好的时间复杂度分别为( )和( ). 10.一个循环队列存于AM中,队首和队尾指针分别为front和rear,队满的条件是( ).三 判断题 1.顺序文件是利用磁盘的特有的性质实现的,因此顺序文件只能存放在磁盘中.( ) 2.用希尔方法排序时,若关键字的初始排序杂乱无序,则排序效率就低.( ) 3.任一二叉树平均查找时间都小于顺序查找法查找同样的线性表的平均查找时间.( ) 4.若连通图上各边权值均不相同,则该图的最小生成树是唯一的.( ) 5.不使用递归也能实现二叉树的先序,中序和后序的遍历.( ) 6.任何一个非空的广义表,其表头可能是单元素或广义表,其表尾必定是广义表.( ) 7.稀疏矩阵压缩存储后,必会失去随机存取功能.( ) 8.KMP算法的最大特点是指示主串的指针不需回溯.( ) 9.栈的输入序列为1,2,3,4,n,输出序列为a1,a2,an,若ai=n(1=ia(i+1)an.( ) 10.在线性表顺序存储中,插入和删除元素时,移动元素的个数与该元素的位置有关.( )四 综合应用题1.给定(已生成)一个带头结点的单链表,设HEAD为头指针,结点的结构为(data,next),data主整数元素,next为指针,试定一算法,按递增次序输出单链表的数据元素,并释放结点所占的存储空间,(不允许使用数组作辅助空间).2.给定一组关键字29,18,25,47,58,12,51,10分别写出下列各种排序方法进行排序的变化过程.(1)归并排序,每归并一次书写一次序(2)快速排序,每划分一次书写一次序 (3)堆排序,先建一个堆,然后每从堆顶取下一个元素后,将堆调整一次.3.有一个二叉树中序序列为:ABCEFGHD 后序序列为: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,G,H,I,J E(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)ABDFGEHICJ数据结构模拟试题(一)参考答案一 单选题 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 increase(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,51,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 58 47 29 25 10 18 12 51 58 29 18 25 10 12 47 51 58 25 18 12 10 29 47 51 58 18 10 12 25 29 47 51 58 12 10 18 25 29 47 51 58 10 12 18 25 29 47 51 583.CBADEGHF4.(1)地址01234567