模拟试题1一、选择题（共10题，每题1分，共10分）1．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链接存储，不必占用一片连续的存储单元D．线性表采用链接存储，便于插入和删除操作2．在一个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插入s所指结点，则执行的操作是（）。

A. s->next=p->next;p->next=s;B. q->next=s;s->next=p;C. p->next=s->next;s->next=p;D. p->next=s;s->next=q;3．设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是( )。

A．XYZ B. YZX C. ZXY D. ZYX4．若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则从队列中删除一个元素，再增加两个元素后，rear和front的值分别是( )。

A．1和5 B．2和4 C．4和2 D. 5和15．下列说法中正确的是（）。

A．二叉树就是度为2的树 B．二叉树中不存在度大于2的结点C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 6．在具有n个结点的二叉链表中，共有（）个空指针。

A. nB. n-1C. n+1D. 不确定7．根据二叉树与树的转换关系可知，深度为h的满二叉树对应的森林由（）棵树构成。

A．1 B．log2n C. h/2 D. h8．在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。

A．1/2 B．1 C. 2 D. 49．对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是（）。

A．8,17 Ｂ．5,10,12 C．9,16 D．9,1710．关于排序，下列说法中正确的是（）。

A. 稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高B. 在顺序表上实现的排序方法在链表上也可以实现C. 在链表上可以实现简单选择排序，但是难以实现堆排序D. 就平均性能而言，堆排序最佳二、填空题（共10空，每空2分，共20分）1．计算机执行下面的语句时，语句s的执行次数为 _______ 。

for(i=l；i<n-l；i++)for(j=n;j>=i;j--) s;2．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。

3．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是_______ 。

4． 一棵有124个叶子结点的完全二叉树，最多有个_______结点。

5． N 个顶点的无向连通图若要存在回路，则至少需要__________条边。

6． 对于一棵二叉排序树做_______遍历，可以得到一个有序的序列。

7． 进行折半查找的两个先决条件是查找表中数据有序和__________。

8． 按{12,24,36,90,52,30}的顺序构成的平衡二叉树，其根结点是__________。

9． 时间复杂度为O （nlg 2n ）且稳定的排序算法是__________排序。

10．快速排序在__________情况下会蜕变成为冒泡排序。

三、应用题（共5题，每题10分，共50分）1． 设一棵二叉树的先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C（1）画出这棵二叉树。

（2）将这棵二叉树转换成对应的树（或森林）。

2． 给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G 出现的频度，画出Huffman 树，并给出各字符的Huffman 编码。

3．根据Prim 算法或Kruskal 算法，求右图的最小生成树。

136542192116566111418334．某一工程作业的网络图如右图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。

箭头前后的圆圈表示事件的编号。

求出所有事件开始的最早时间和最晚时间，并给出关键路径。

19 3 760 25 10 8 4 113 2 2 7 245 3 1 63 34 4 755．设哈希函数H （k ）=3*K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按线性探测再散列的方法解决冲突，构造哈希表，并求出等概率下查找成功时的平均查找长度四、程序设计题（共2题，共20分）1． 设有两条带头结点单链表La 和Lb ，且表中的数据有序递增。

现要将两条单链表合并成为一条单链表Lc ，并使Lc 中的数据有序递减．．．．。

试写算法来实现，并说明算法的时间复杂度。

2． 写算法判断两棵二叉树是否相似。

相似的条件是：要么它们都为空或者都只有一个根结点，要么它们的左右子树均相似。

试题参考答案选择题1-5 BACBB 6-10 CDCAC填空题1 (n+3)(n-2)/2 2 FIFO3 11754 2485 N-16 中序遍历7 顺序存储 8 369 归并排序 10 数据基本有序操作题1、3、2、wpl=512 1635484题图AEDCBHGF223ADADF1 32GAFD1 323BG FDA1234 DFACGBE1234 DFACGB13 3ABMFD(2)CEM HG4、略5、散列地址0 1 2 3 4 5 6 7 8 9 10 关键字 4 12 49 38 13 24 32 21比较次数 1 1 1 2 1 2 1 2ASL succ =（1+1+1+2+1+2+1+2）/8=11/8算法设计1 void Merge（LinkedList la，Linklist lb）{ pa=La->next;pb=Lb->next;Lc =La;while(pa&&pb){if(pa->data<=pb->data){Lc->next=pa; Lc=pa;pa=pa->next;}else{Lc->next=pb; Lc=pb;pb=pb->next}}Lc->next=pa?pa:pb;free(Lb);}2 status sam(BiTree Ta, BiTree Tb) //判断相似{if(!Ta && !Tb) return OK;else{if ( Ta&&!Tb || !Ta&&Tb) return False;else { p=same(Ta->lchild,Tb->lchild);if(p) p= same(Ta->rchild,Tb->rchild);return p;}}//结束模拟试题2一、选择题（共10题，每题1分，共10分）1．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

2．在双向链表指针p的结点前插入一个指针q的结点操作是（）。

A. p->prior=q;q->next=p;p->prior->next=q;q->prior=q；B. p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;C. q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;D. q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;3．设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。

A．XYZ B. YZX C. ZXY D. ZYX4．递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。

A．队列 B．多维数组 C．栈 D. 线性表5．循环队列存储在数组A中，数组长度为m，则入队时的操作为（）。

A. rear=rear+1B. rear=(rear+1) % (m-1)C. rear=(rear+1) % mD. rear=(rear+1) % m6．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175B. 1180C. 1205D. 12107．有关二叉树下列说法正确的是（）。

A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为28．一棵非空的二叉树的先序遍历序列与中序遍历序列正好相同，则该二叉树一定满足（）。

A．所有的结点均无左孩子 B．所有的结点均无右孩子C．只有一个叶子结点 D．是任意一棵二叉树9．n个结点的完全有向图含有弧的数目（）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）10．对线性表进行二分查找时，要求线性表必须（）。

A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序二、填空题（共10空，每空2分，共20分）1．计算机执行下面的语句时，则其复杂时间度为O（_______）。

for(i=l；i<n-l；i++)for(j=n;j>=1;j--) s;2．栈的数据进出特点是_______。

3．在顺序表中做插入和删除操作，移动元素的个数大约等于表程长度的_________。

4．深度为5的完全二叉树,其结点至少有_______个，至多有_______个。

5．对一棵完全二叉树按照层次编号，编号为i（i>1）的结点的双亲结点的编号是_______。

6．对于一棵二叉排序树做_______遍历，可以得到一个有序的序列。

7．己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找时，第二次查找即查找成功的数据是 __________ 或 __________ 。

8．归并排序算法的时间复杂度为 __________。

三、操作题（共5题，每题10分，共50分）1．设一棵二叉树的先序、中序遍历序列分别为，先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C，画出这棵二叉树。