数据结构(C++)第二次作业答案.doc

数据结构第二次作业答案一. 单项选择题(20分)( )1. 一棵左子树为空的二叉树在前序线索化后，其空指针域数为 C a、0 b、1 c、2 d、不确定( )2. 下列排序算法中，_D_算法可能会出现下面的情况：初始数据有序时，花费的时间反而更长。a、堆排序 b、起泡排序 c、直接选择排序 d、快速排序( )3. 在图采用邻接表存储时，求最小生成树的prim算法的时间复杂度是_B_。a.O(n*e) b. O(n+e) c. O(n2) d.O(n3)( )4. 下面程序段的时间复杂度是_A_。 i=1; while(i0)个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为_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. 排序算法的稳定性是指_A_。a.经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 b.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 c.算法的排序性能与被排序元素的数量关系不大 d.算法的排序性能与被排序元素的数量关系密切( )8. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_B_的二叉树。a. 空或只有一个结点 b. 高度等于其结点数（空树高度为0）c. 任一结点无左孩子 d. 任一结点无右孩子( )9. 已知有向图G=(V,E)其中V= V1 V2 V3 V4 V5 V6 V7,E=,为_A_。a. V1 V3 V4 V6 V2 V5 V7 b. V1 V3V2 V6 V4 V5 V7 c. V1 V2 V3 V4 V5 V6 V7 d. V1 V2 V5 V3 V4 V6 V7( )10. 下列关于AOE网的叙述中不正确的是_D_。a. 关键活动不按期完成会影响整个工程的完成时间 b. 所有的关键活动提前完成，那么整个工程将会提前完成 c. 某些关键活动若提前完成，那么整个工程将会提前完成 d. 任一关键活动提前完成，那么整个工程将会提前完成二. 填空作图简答题（共64分）：1. 将算术表达式(a+b)+c*(d+e)+f)*(g+h)转化为二叉树，并写出其前序序列。二叉树略前序序列：*+ab*c+def+gh2. 有一组关键码序列10，20，60，47，50，45，95，33，75，采用Shell排序方法从小到大进行排序，假设其间隔序列为5，3，1，请写出每趟的结果。请按照下面的图例完成此题：3. 对下面的3阶B树依次插入关键码80，26，6，画出插入三个关键码后并删除关键码40后的结果。20104012 1630502 84. 用Prim算法求下图的最小生成树, 若从顶点0出发，请将算法中的两个辅助数组的变化过程填入下表。12340567647557685128辅助数组lowcost辅助数组nearvex0123456701234567所选边选出第1条边06 57 -10000000(0,3,5)选出第2条边06 57 6-100-10003(0,1,6)选出第3条边06354 6-1-11-11003(1,2,3)选出第4条边06354126-1-1-1-11223(2,5,1)选出第5条边06354126-1-1-1-11-123(2,6,2)选出第6条边06354126-1-1-1-11-1-13(1,4,4)选出第7条边06354126-1-1-1-1-1-1-13(3,7,6)5. 求出下图中顶点A到其余个顶点的最短路径和最短路径长度。10 3ABCDHEFG20789919863127AE=10;AF=17;AB=19;AG=25;AC=26;AD=27;AH=286. 已知报文为afecdaceadabdefbedeebcdefdede，试设计其赫夫曼编码并画出相应的赫夫曼树。 a：2；b：4；c：3；d：6；e：7；acbdeacbde 7. 设初始归并段为(10,15,31,),(9,20, ),(22,34,37, ),(6,15,42, ),(12,37, ),(84,95, ),试利用败者树进行6路归并，画出选出最小的2个关键码的过程。 8. 已知哈希表地址空间为08，哈希函数为H(key)=key % 7，采用线性探查法处理冲突。将数据（100，20，21，35，3，78，99，45）依次存入该散列表中，并计算等概率下查找不成功时的平均查找长度。0123456782135100378992045等概率下查找不成功时的平均查找长度：_ (1+2+3+4+5+6+7+8+9)/7=45/7_三. 程序填空(16分)下面是仅给出了部分操作的二叉搜索树类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成将元素x 插入到二叉树的操作。class BinNode public: int data; BinNode* leftchild, * rightchild; BinNode() leftchild = rightchild = NULL; ;class BinTree private: BinNode* root; void clearhelp(BinNode* rt) if (rt = NULL) return; clearhelp(rt-leftchild); clearhelp(rt-rightchild); delete rt; public: BinTree() root = NULL; BinTree() clearhelp(root); void insert(const int x) ; /元素x 插入到二叉树;void BinTree : insert(const int x) /元素x 插入到二叉树 BinNode *i, *j, *k; i=new BinNode ; i-data = x; if ( root=Null ) root = i; else j = root; while ( j!=Null ) k = j;if ( xj-data 或