资源描述：
《信管数据结构期末试卷B-Answer》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构B卷参考答案一、单项选择题（每小题2分，共30分）1.LCJ2.[D]3.[D]4.[A]5.[D]6.1BJ7.[A]8JA]9.[D]10.[C]11.[C]12.[A]13JB114.[C]15.[C]二、填空题(每空2分，共20分)21.若n为主串长，m为子串长，则串的朴素匹配算法最坏的情况下需要比较字符的总次数为(n-m+l)*m。22.广义表((a),((b),j,((d))))的表头是0)o23.数据的逻辑结构分为两大类，它们是线性结构和非线性结构°24.已知循环队列用数组data[nl存储元素值，用front
2、,rear分别作为头尾指针，则当前元素个数为(rear-fronl+rQ%n。25.在一个长度为n的顺序表中的第i个元素(lWiWn)之前插入一个元素时，需向后移n・i+l个元素。26.己知二叉树有61个叶子节点，且仅有一个孩子的节点数为45,则总节点数为166o27.在单链表屮(假设结点指针域名称为next),删除指针P所指结点的后继结点的语句是D->next二p->next->next。28.n个顶点e条边的图采用邻接表存储，深度优先遍历算法的吋问复杂度为O(n+e)。29.对于n个关键字的集合进行冒泡排序，在最坏情况下的时间复
3、杂度为0(()O30.解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应是一个队列结构。三、简答题(每题10分，共50分)26.已知一棵树边的集合为{,,,,,,,,,vc,h>,va,c>},画出这棵树，并回答下列问题：(1)哪个是根结点？（2）哪些是叶子结点？（3）明1（些是结点g的祖先?（4）树的深度是多少？（5）树的度数是多少？参考答案：根结点是：a叶子结点是：difjk1g的祖先：ac树的深度：4树的度数：3（每对1小题
4、得2分）27.以下面数据作为叶子结点的权值构造一Huffman树，画出该树并计算出其帯权路径长度。2,4,5,8参考答案：带权路径长度：WPL二（2+4）*3+5*2+435（树画对得5分，带权路径长度对得5分）28.给定关键字集合（45,2&52,20,10,35,40,70,30,75,63,32）,（1）从一棵空的二叉搜索树开始，按表屮元素的次序构造一棵二叉搜索树。（2）画出从该二叉搜索树中删除关键码28和52后的结果。参考答案:（1）（评分标准：每个图5分）27.试画出下而带权无向图的一棵最小生成树。5参考答案：（对1根线得
5、2分，全对得10分）28.写出利用希尔排序对关键字序列（40,24,80,39,43,18,20,10,90,70）进行从小到大排序的每一趟结果。（假设gap取值分别为5、3、1）参考答案：Gap=5时18,20,10,39,43,40,24,80,90,70Gap=3时18,20,10,24,43,40,39,80,90,70Gap=l时10,18,20,24,39,40,43,70,80,90（每对1行得3分，全对10分）
