资源描述：
《数据结构(c++)第二次作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构第二次作业答案学号：姓名：评分：.一.单项选择题(20分)()1.一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为_________。a、0b、1c、2d、不确定()2.下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是__________。a、堆排序b、起泡排序c、直接选择排序d、快速排序()3.设图的顶点数=n,边数=e，若用邻接表表示图，那么求最短路径的Dijkstra算法的时间复杂度为_________。a.O(n*e)b.O(n2)c.O(n+e)d.O(n3)()4.下面程序段的时间复杂度是_________。i=1;whi
2、le(i<=n)i=i*2;a.O(n)b.O(n2)c.O(2n)d.O(log2n)()5.在有n(>0)个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为___________。a.O(n)b.O(log2n)c.O(nlog2n)d.O(n2)()6.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为________个结点最佳。a.10b.25c.6d.625()7.已知数据表中的每个元素距其最终位置不远，则采用_______排序算法最省时间。a.堆排序b.插入排序c.快速排序d.直接选择排序(
3、)8.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是________的二叉树。a.空或只有一个结点b.高度等于其结点数（空树高度为0）c.任一结点无左孩子d.任一结点无右孩子()9.一棵左子树为空的二叉树在先序线索化后（不带头结点的线索化），其中的空链域的个数为_________。a.2b.1c.0d.不确定()10.假设图的顶点数=n,边数=e，那么当用邻接表表示图时，拓扑排序算法的时间复杂度为_________。a.O(n2)b.O(n+e)c.O(n*e)d.O(n3)二.填空作图简答题（共64分）：1.依次插入30，43，21，9，15，51并由空树构成一棵平衡二叉树，画出
4、该平衡二叉树形成过程及其中序线索二叉树。2.有一组关键码序列{40，20，60，15，50，45，95，10，75}，采用Shell排序方法从小到大进行排序，假设其间隔序列为5，3，1，请写出每趟的结果。3.对下面的3阶B树依次插入关键码60，14，6，画出插入三个关键码后并删除关键码20后的结果。420104012163050281.用Prim算法求下图的最小生成树,若从顶点0出发，请将算法中的两个辅助数组的变化过程填入下表。12340567647557685128辅助数组lowcost辅助数组nearvex0123456701234567所选边选出第1条边选出第2条边选出第3条边选出第
5、4条边选出第5条边选出第6条边选出第7条边42.求出下图中顶点A到其余个顶点的最短路径和最短路径长度。103ABCDHEFG207899198631273.已知报文为acedabdebdeebcdedebcde，试设计其赫夫曼编码并画出相应的赫夫曼树。41.设初始归并段为(10,15,31,∞),(9,20,∞),(22,34,37,∞),(6,15,42,∞),(12,37,∞),(84,95,∞),试利用败者树进行6路归并，画出选出最小的2个关键码的过程。2.已知哈希表地址空间为0~8，哈希函数为H(key)=key%7，采用线性探查法处理冲突。将数据（100，20，21，35，3，7
6、8，99，45）依次存入该散列表中，并计算等概率下查找不成功时的平均查找长度。012345678等概率下查找不成功时的平均查找长度：________。一.程序填空(16分)1.下面是仅给出了部分操作的二叉搜索树类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成将元素x插入到二叉树的操作。classBinNode{public:intdata;BinNode*leftchild,*rightchild;BinNode(){leftchild=rightchild=NULL;}};classBinTree{private:BinNode*root;voidclearhelp(Bi
7、nNode*rt){if(rt==NULL)return;clearhelp(rt->leftchild);clearhelp(rt->rightchild);deletert;}public:BinTree(){root=NULL;}~BinTree(){clearhelp(root);}voidinsert(constintx);//元素x插入到二叉树};voidBinTree::insert(constintx)/
