数据结构算法 模拟练习及解答二 绍兴文理学院 计算机系计算机应用教研室

1、某二叉树的先序序列和后序序列正好相同，则该二叉树一定是 ( )的二叉树。 A.空或只有一个结点 B.高度等于其结点数 一、选择题（共15分，每题1.5分） 1、某二叉树的先序序列和后序序列正好相同，则该二叉树一定是 ( )的二叉树。 A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子 A 2、下列排序算法中，时间复杂度不受数据初始状态影响，恒为○(nlog2n)的是( )。 A.堆排序 B.冒泡排序 C.直接选择排序 D.快速排序 A 3、在有n个叶子结点的哈夫曼树中，其结点总数为( )。 A.不确定 B.2n C.2n-1 D.2n+1 C 4、一棵左、右子树均不空的二叉树在先序线索化后，其空指针域数( )。 A.0 B.1 C.2 D.不确定 B TKS 2 CX02

5、设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m的前的条件是( )。 A. n在m的右方 B. n是m的祖先 C. n是m的子孙 D. n在m的左方 D 6、任何一个无向连通图的最小生成树( )。 A. 只有一棵 B. 一定有多棵 C. 有一棵或多棵 D. 可能不存在 C 7、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中( )。 A. 第i行非∞的元素之和 B. 第i列非∞的元素之和 C. 第i行非∞且非0的元素个数 D. 第i列非∞且非0的元素个数 D 8、对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标依次为( )。 A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 D TKS 3 CX02

10、快速排序方法在( )情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 9、设哈希表长m=14，哈希函数H(key)=key mod 11。表中已有4个结点addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如果用二次探测再散列法处理冲突，则关键字49的结点的地址是( )。 A. 8 B. 3 C. 5 D. 9 D 10、快速排序方法在( )情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 C 二、判断题（共 9分，每题 1.5分）（正确的打√，错误的打×） 1、（ ）给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。 × 2、（ ）由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。 × TKS 4 CX02

3、（ ）在对链队列作出队操作时，不会改变front指针的值。 √ 4、（ ）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。 × 5、（ ）若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=n-i+1(i=1,2...,n)。 √ 6、（ ）图G的拓扑序列唯一，则其弧数必为n-1(其中n为G的顶点数) 。 × 三、填空题（第3题2分，其它每空1分，共15分） 1、设有一个链队列，结点结构为：队尾指针为Ls(!=NULL)，则执行入队操作时，s->next=Ls->next；_____________；________ 。结点结构为： 。 ls->next=s; ls=s; data next 2、在有n（n>0）个结点的二叉链表中，非空链域的个数为 ________。 n+1 TKS 5 CX02

3、一棵二叉排序树中若存在30个结点，其每个结点的查找成功的长度<6，则有_______个结点其每个结点的查找成功的长度=4。 8 4、有n个结点的二叉排序树，其树的高度的范围是 _____________。 [log2n]+1～n 5、字符串s=“i am a student”，t=“good”，则sub(s，8，7)= ___________； student concat(concat(sub(s,6,2),t),sub(s,7,8))=_________________。 a good student 6、在有n个结点的无向图中，其边数最多为 _____________。 n(n-1)/2 7、对矩阵采用压缩存储是为了 _____________。 节省空间 8、在双向链表中，在指针P所指结点前面插入一个结点S所指向结点的语句序列是：______________；______________________； _______________；______________________。 S->next=P; S->prior=P->prior; P->prior=S; S->prior->next=S； 9、对广义表A=(x,((a,b),c,d))的运算head (head (tail (A)))的结果是 _______ 。 (a) 10、判断线索二叉树中某结点指针P所指结点有左孩子的条件是 ______________ 。 P->ltag=1 TKS 6 CX02

1、已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，要求(8分) 四、应用题（共45分） 1、已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，要求(8分) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 data A B C D E F G H I J K L M N O parent (1)画出该树；(4分) (2)在(1)的基础上将这棵树转换成二叉树；(4分) (2) A B C D E F G H I J K L M N O (1) A B C D E F G H I J K L M N O TKS 7 CX02

2、某工程的AOE网络如右图所示,图中弧上的权值分别为a1～a10的t个活动的期限。完成下列各题：(13分) v5 v1 v2 v3 v4 v6 a9=3 a6=1 a4=2 a3=2 a2=4 a1=3 a5=5 a7=7 a10=8 a8=5 (1)求出不少于三个的拓扑序列。(3分) 123456； 123546； 132456； 132546 (2)求各事件的最早发生时间ve和最迟发生时间vl，以及各项活动的最早开始时间e和最迟开始时间l。填于下面表中。(8分) (3)完成该项工程最少需要几天(2分) 事件 1 2 3 4 5 6 Ve   Vl 3 4 9 5 14 完成该项工程最少需要14天。 6 4 9 16 14 (4)画出关键路径(2分) 活动 a1 a2 a3 a4 a5 a6 a7 a8 A9 a10 e   l v1→v3→v4→v6 3 4 4 4 9 5 3 3 7 9 4 10 7 9 11 6 TKS 8 CX02

(1) 构造平衡二叉搜索树的过程(6分) (2) ASLsucc= (1/9)*(1+2*2+3*4+4*2)=25/9 3、设有一个关键码的输入序列{55,31,11,37,46,73,63,02,07},要求(10分) (1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。(6分) (2) 计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度。(2分) (3) 计算该平衡二叉搜索树在等概率下的搜索不成功的平均搜索长度。(2分) (1) 构造平衡二叉搜索树的过程(6分) 46 31 55 37 63 73 11 55 31 11 31 11 55 37 46 31 11 46 37 73 55 右旋 左右旋 左旋 右左旋 46 31 55 37 63 73 11 02 07 46 31 55 37 63 73 07 02 11 (2) ASLsucc= (1/9)*(1+2*2+3*4+4*2)=25/9 左右旋 (3) ASLunsucc= (1/10)*(3*6+4*4)=17/5 TKS 9 CX02

4、将下列带状矩阵的非零元素压缩到数组B中去，按以行为主序，顺序的存储其非零元素，如图所示，按其压缩规律，给出Ａ中非零元素aij的下标(i,j)与Ｂ中的下标(从1开始存放)K的关系。(4分) 解：k=2*i+j-2 a11　a12　 0　 0　 0 a21　a22 a23　 0　 0 0 a32 a33　a34 0 0 0 a43　a44 a45 0　 0　 0　 a54 a55 A= TKS 10 CX02

(1)二路归并排序（5分） (2)希尔排序(增量为5,2,1)（5分) 5、设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。(10分) (1)二路归并排序（5分） (2)希尔排序(增量为5,2,1)（5分) (1)二路归并排序 12 2 16 30 28 10 20 6 18 2 12 16 30 10 28 16 20 6 18 2 12 16 30 10 16 20 28 2 10 12 16 16 20 28 30 2 6 10 12 16 16 18 20 28 30 (2)希尔排序 12 2 16 30 28 10 16 20 6 18 d1=5 10 2 16 6 18 12 16 20 30 28 d1=3 10 2 16 6 18 12 16 20 30 28 d1=1 2 6 10 12 16 16 18 20 28 30 TKS 11 CX02

五、算法设计题（16分） comstr(s1,s2)= 1、下列算法的功能是比较两个链串的大小，其返回值为： 请在空白处填入适当的内容。(8分) int comstr(LinkString s1,LinkString s2) //s1和s2为两个链串的头指针 { while(s1&&s2) {if(s1－>date<s2－>date) return -1； if(s1－>date>s2－>date) return 1； ① ； ② ； } if( ③ ) return -1； if( ④ ) return 1； ⑤ ； 解： ① s1=s1－>next ② s2=s2－>next ③ s2(或s2!=NULL或s2&&!s1) ④ s1(或s1!=NULL或s1&&!s2) ⑤ return 0 TKS 12 CX02

{ dl=depth(t->Lchild)； dr=depth(t->Rchild)； 2、计算二叉树的深度的算法（8分） 解： int dl=dr=0; int depth(tree *t) { if(!t) return 0； else { dl=depth(t->Lchild)； dr=depth(t->Rchild)； if(dl>dr) return 1+dl； else return 1+dr； } TKS 13 CX02