2022年《数据结构》期末试卷_A卷 .pdf

《2022年《数据结构》期末试卷_A卷 .pdf》由会员分享，可在线阅读，更多相关《2022年《数据结构》期末试卷_A卷 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 一、（本题 10分）（1）线性表和广义表的主要区别是什么？（2）已知广义表:C=(a,(b,(a,b),(a,b),(a,b),则 tail(head(tail(C)=？答案：（1）线性表和广义表都是元素a1,a2,an组成的序列，其主要区别点在于：在线性表中，ai是单个元素（原子）；在广义表中，ai 可以是单个元素（原子），也可以是广义表。（7 分）（2）tail(head(tail(C)=(a,b)（3 分）二、（本题 10 分）简述二叉树的两种存储结构（顺序存储和链式存储）的数据结构及主要优缺点。在哈夫曼树中，使用哪种存储结构，并说明理由。答案：顺序存储结构：typedef SqBi

2、TreeMax_Tree_Size;特点：使用数组存储二叉树上的结点元素，按照对应的完全二叉树的编号来存储二叉树。优点是适用于完全二叉树，访问方便。缺点是对于一般二叉树，较大地浪费了空间。（4分）链式存储结构：typedef strut BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;特点：使用结构体来表示结点元素，使用指针来指向结点的左右孩子。优点是插入与删除方便，节省空间，缺点是不能快速地随机访问结点元素。（4 分）在哈夫曼树中，使用静态三叉链表，这样可以方便地从根走到叶子，也可以从叶子走到根，而且可

3、以随机访问和节省空间。（2 分）三、（本题 10 分）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。先序序列：_B_F_ICEH_G；中序序列：D_KFIA_EJC_；后序序列：_K_FBHJ_G_A。答案：先序序列：A B D F K I C E H J G 中序序列：D B K F I A H E J C G后序序列：D K I F B H J E G C A (11分)画出树得 4 分。厦门大学数据结构课程期末试卷信息科学与技术学院计算机科学系 2009 年级专业主考教师：陈怡疆庄朝晖 试卷类型：（A 卷）名师资料总结-精品资料欢迎

4、下载-名师精心整理-第 1 页，共 5 页 -2 四、（本题 10 分）分别使用普里姆算法和克鲁斯卡尔算法求出图G1的最小生成树，仅需画出最小生成树的成长过程即可。答案：（1）普里姆算法求最小生成树的过程如下：5 分0 1 2 3 4 5 1 0 1 2 3 4 5 1 3 0 1 2 3 4 5 1 4 3 A B C D E H J F G K I 0 1 2 3 4 5 1 4 5 2 5 6 6 6 3 7 图 G1 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -3（2）克鲁斯卡尔算法如下：5 分五、（本题 10分）有向图 G2 如上所示，（1）请写出图 G2

5、 所有可能的拓扑序列：（2）请写出以顶点B 为起始点的深度优先遍历序列和广度优先遍历序列，并画出对应的生成树。遍历过程中当有多种选择时，编号小的结点优先。答案：（1）BACDE、BACED、BCADE、BCAED（5 分，少一个扣一分）（2）深度优先遍历序列：BADEC（3 分）0 1 2 3 4 5 1 4 5 2 3 0 1 2 3 4 5 1 4 2 3 0 1 2 3 4 5 1 2 3 0 1 2 3 4 5 1 2 0 1 2 3 4 5 1 0 1 2 3 4 5 1 4 5 3 0 1 2 3 4 5 1 4 5 2 3 A B C D E 图 G2 名师资料总结-精品资料欢迎

6、下载-名师精心整理-第 3 页，共 5 页 -4 广度优先遍历序列：BACDE（3 分）六、（本题 15分）已知键值序列为45,56,83,31,72,35,14,47,89,19 ，要求给出：（1）按键值排列次序构造一棵二叉排序树。（2）在等概率的情况下，求出该二叉排序树查找成功的平均查找长度。（3）针对上述 10 个键值，在不同的排列次序下所构造出的不同形态的二叉排序树中，在最坏和最好情况下，二叉排序树的高度各是多少？答案：（1）（2）在等概率情况下，该二叉排序树的平均检索长度是：ASL=(1+2*2+3*4+4*3)/10=29/10=2.9（3）对于上述 10 个键值，在最坏情况下，每

7、个结点（除了叶子结点）只有右孩子（或者只有左孩子），高度为 10。在最好情况下，高度为 log210+1=4。七、（本题 15分）设关键字序列为：49,38,66,80,70,15,22，欲对该序列进行从小到大排序。（1）用直接插入排序法进行排序，写出每趟的结果。（2）采用待排序列的第一个关键字作为枢轴，写出快速排序法的一趟和二趟排序之后的状态。（3）画出待排序列的初始化堆。答案：直接插入排序法原始关键字序列为：(49)38 66 80 70 15 22(38 49)66 80 70 15 22(38 49 66)80 70 15 22(38 49 66 80)70 15 22(38 49 6

8、6 70 80)15 22(38 49 66 70 80)15 22(15 38 49 66 70 80)22(15 22 38 49 66 70 80)快速排序法原始关键字序列为：49，38，66，80，70，15，22 4531 56 14 35 47 83 19 72 89 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -5 第一趟排序后22 38 15(49)70 80 66 第二趟排序后15(22)38 66(70)80 该堆是最大堆，具体如下：八、（本题 10分）假设一棵树的存储结构采用双亲表示法，双亲数组为int parentMaxSize，其中 MaxS

9、ize 为最大结点个数。树中各结点按先根遍历的次序存放，根结点存于parent0。试编写一个函数，计算下标p 所指结点和下标 q 所指结点的最近公共祖先结点。参考答案：int CommonAncestry(int parent,int MaxSize,int p,int q)int i,j;for(i=p;i!=-1;i=parenti)for(j=q;j!=-1;j=parentj)if(i=j)return I;九、（本题 10分）1，2，n 这 n 个数，无序地保存在数组c1.n中。请编写一个时间复杂度为 O(n)的排序算法，将数组c1.n按小到大排序。参考答案：void C_sort(int c,int n)int i,x;for(i=1;i=n;i+)while(ci!=i)x=ci;ci=cx;cx=x;交换 O(n)次。80 70 66 38 49 15 22 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -