数据结构第二次作业答案C语言版07

1、数据结构第二次作业答案学号： 姓名： 评分： .一. 单项选择题(20分)( )1. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_b_的二叉树。a. 空或只有一个结点 b. 高度等于其结点数（空树高度为0）c. 任一结点无左孩子 d. 任一结点无右孩子( )2. 设图的顶点数=n, 边数=e，若用邻接表表示图，那么求最短路径的Dijkstra算法的时间复杂度为_b_。a.O(n*e) b.O(n2) c.O(n+e) d.O(n3)( )3. 一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为_b_。a、0 b、1 c、2 d、不确定( )4. 下面程

2、序段的时间复杂度是_d_。 i=1; while(i<=n) i=i*2; a. O(n) b. O(n2) c. O(2n) d. O(log2n)( )5. 在有n(>0)个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为_b_。a. O(n) b. O(log2n) c. O(nlog2n) d. O(n2)( )6. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为_b_个结点最佳。 a. 10 b. 25 c. 6 d. 625( )7. 下列排序算法中时间复杂度不受数据初始状态影响

3、，恒为O(n2)的是_c_。a、堆排序 b、起泡排序 c、直接选择排序 d、快速排序( )8. 已知数据表中的每个元素距其最终位置不远，则采用_b_排序算法最省时间。a.堆排序 b.插入排序 c.快速排序 d.直接选择排序( )9. 假设图的顶点数=n, 边数=e，那么当用邻接表表示图时，拓扑排序算法的时间复杂度为_b_。a. O(n2) b. O(n+e) c. O(n*e) d. O(n3)( )10. 一棵左子树为空的二叉树在先序线索化后（不带头结点的线索化），其中的空链域的个数为_a_。a. 2 b. 1 c. 0 d. 不确定二. 填空作图简答题（共62分）：511530439211

4、530439211. 依次插入30，43，21，9，15，51并由空树构成一棵平衡二叉树， 画出该平衡二叉树形成过程及其中序线索二叉树。21304392130433043302. 有一组关键码序列40，20，60，15，50，45，95，10，75，采用Shell排序方法从小到大进行排序，假设其间隔序列为5，3，1，请写出每趟的结果。答案：第1趟： 40，20，10，15，50，45，95，60，75第2趟： 15，20，10，40，50，45，95，60，75第3趟： 10，15，20，40，45，50，60，75，953. 对下面的3阶B树依次插入关键码60，14，6，画出插入三个关键码后

5、并删除关键码20后的结果。20104012 1630502 84. 用Prim算法求下图的最小生成树, 若从顶点0出发，请将算法中的辅助数组closedge的变化过程填入下表。12340567647557685128辅助数组closedge01234567所选边选出第1条边adjvexlowcost选出第2条边adjvexlowcost选出第3条边adjvexlowcost选出第4条边adjvexlowcost选出第5条边adjvexlowcost选出第6条边adjvexlowcost选出第7条边adjvexlowcost5. 假设某森林的先根遍历序列为EBADCFHGIKJ和中根遍历序列为A

6、BCDEFGHIJK。请画出该森林的带双亲的孩子链表示。6. 已知9个结点的值分别为19，请将各结点的值填入下面二叉排序树中：5193246787. 用堆排序算法(“最大堆”排序算法)对关键字70，33，79，67，46，24，30，40进行排序，请先建“最大堆”，然后输出一个堆顶元素, 并调整成堆：初始状态 40 ， 33 ， 24 ， 67 ， 46 ， 79 ， 30 ，70 所建大顶堆 79，70，40，67，46，24，30，33或79，70，67，46，40，24，30，33输出一个堆顶元素后调整的结果70，67，40，33，46，24，30，79或70，46，67，33，40，2

7、4，30，798. 如下图已知哈希表为空，哈希函数为H（Key）= Key MOD 11, 冲突解决方法分别用线性探测再散列和二次探测再散列。填入在依次插入关键字14，37，25，16之后的情况，并求等概率情况下所要求的平均查找长度。（1）线性探测再散列 0 1 2 3 4 5 6 7 8 9 1014372516（2）二次探测再散列 0 1 2 3 4 5 6 7 8 9 1025143716线性探测再散列查找不成功时的平均查找长度=_21/11 _;二次探测再散列查找成功时的平均查找长度=_6/4=3/2=1.5_;9. 用快速排序对下列关键字进行排序（图示）, 基准元素取第一个元素。 7

8、0 33 79 67 46 24 30 40 写出两趟排序的结果。第一趟排序之后: 40，33，67，46，24，30 70 79 或 40，33，30，67，46，24 70 79;第二趟排序之后: 30，33，24 40 67，46 70，79 或 24，33，30 40 46，6770，79;若基准元素按“三者取中”的原则取，则两趟排序的结果是：第一趟排序之后:40，33，46，24，30 67 79，70 或 33，40，30，24，46 67，70，79;第二趟排序之后:30，33，24 40 46 67，70，79 或 24，30 33 40，46 67，70，79;10. 已知一

9、字符串bcbdebcecbdcabd，试设计其赫夫曼编码并画出相应的赫夫曼树。a：1；b：5；c：4；d：3；e：2；aedbcaedbc 11. 求出下图中顶点A到其余个顶点的最短路径和最短路径长度。10 3ABCDHEFG20789919863127AE=10; AF=17; AB=19; AG=25; AC=26; AD=27; AH=28三. 程序填空(18分)1. 下面是仅给出了部分操作的二叉树类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成计算度为1的结点个数的操作countNodes1( )。typedef struct BinNode int data; str

10、uct BinNode* leftchild, * rightchild;BinNode, *BinTree;void InitBinTree(BinTree &root) /初始化二叉树root root=Null;void DestroyBinTree(BinTree &root) /销毁二叉树rootif (root = NULL) return; DestroyBinTree(root->leftchild); DestroyBinTree (root->rightchild);free(root);int countNodes1(BinTree &

11、root) /计算二叉树root中度为1的结点数 if ( _ root!=NULL _ ) if(root-> leftchild!=NULL && root-> rightchild!=NULL) _return _ countNodes1(root-> leftchild ) + countNodes1(root-> rightchild)_; else if(root-> leftchild=NULL && _root-> rightchild!=NULL _ _)_ _ return _ 1 + countNodes

12、1(root-> rightchild)_;else if (root-> leftchild!=NULL && root-> rightchild=NULL_ ) _ return _ countNodes1(root-> leftchild ) + 1_; return 0;2. 下面是起泡排序算法的实现。试在程序的每一划线部分填入一条语句或表达式，以使该算法在发现数据有序时能及时停止。void BubbleSort(int datalist, int size) /要排序的数据存放在数组datalist中，元素个数=size int exchange,i,j,temp; i=1; excha