数据结构期末试卷A卷答案.docx

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

1、厦门高校数据构造课程期末试卷信息科学与技术学院计算机科学系2021年级专业主考老师：陈怡疆 庄朝晖 试卷类型：A卷一, 此题10分1线性表与广义表的主要区分是什么？2广义表: C=(a,(b, (a,b), (a,b), (a,b), 那么tail(head(tail(C) =？答案：1线性表与广义表都是元素a1,a2,an组成的序列，其主要区分点在于：在线性表中，ai是单个元素原子；在广义表中，ai可以是单个元素原子，也可以是广义表。7分2tail(head(tail(C) = (a,b)3分二, 此题10分简述二叉树的两种存储构造依次存储与链式存储的数据构造及主要优缺点。在哈夫曼树中，运用

2、哪种存储构造，并说明理由。答案：依次存储构造：typedef SqBiTreeMax_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分。ABCDEHJFGKI四, 此题10分 分别运用普里姆算法与克鲁斯卡尔算法求出图G1的最小生

4、成树，仅需画出最小生成树的成长过程即可。图G10123451452566637 答案：1普里姆算法求最小生成树的过程如下：5分0123451012345130123451430123451453012345145232克鲁斯卡尔算法如下：5分012345101234512012345123012345142301234514523五, 此题10分有向图G2如上所示，1请写出图G2全部可能的拓扑序列： 2请写出以顶点B为起始点的深度优先遍历序列与广度优先遍历序列，并画出对应的生成树。遍历过程中当有多种选择时，编号小的结点优先。图G2ABCDE答案：1BACDE, BACED, BCADE, BC

5、AED 5分，少一个扣一分 2深度优先遍历序列：BADEC 3分 广度优先遍历序列：BACDE 3分六, 此题15分键值序列为45,56,83,31,72,35,14,47,89,19，要求给出：1按键值排列次序构造一棵二叉排序树。2在等概率的状况下，求出该二叉排序树查找胜利的平均查找长度。3针对上述10个键值，在不同的排列次序下所构造出的不同形态的二叉排序树中，在最坏与最好状况下，二叉排序树的高度各是多少？答案： 14553156143547831972892在等概率状况下，该二叉排序树的平均检索长度是：3对于上述10个键值，在最坏状况下，每个结点除了叶子结点只有右孩子或者只有左孩子，高度为

6、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 66 70 80) 15 22 (38 49 66 70 8

7、0) 15 22 (15 38 49 66 70 80) 22 (15 22 38 49 66 70 80) 快速排序法原始关键字序列为：49，38，66，80，70，15，22第一趟排序后 22 38 15 (49) 70 80 66第二趟排序后 15 (22) 38 66 (70) 80 该堆是最大堆，详细如下：80706638491522八, 此题10分假设一棵树的存储构造采纳双亲表示法，双亲数组为int parentMaxSize，其中MaxSize为最大结点个数。树中各结点按先根遍历的次序存放，根结点存于parent0。试编写一个函数，计算下标p所指结点与下标q所指结点的最近公共祖先

8、结点。参考答案：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)次。第 4 页