数据结构A习题课资料.ppt

一、填空题 ;6、有n个叶子的哈夫曼树的结点总数为________。 7、树中结点A有2005个兄弟，结点B是A的双亲，则结点B的度是________。 8、已知一无向图G=(V,E)，其中V={a,b,c,d,e}，E={(a,b), (a,d), (a,c) (d,c), (b,e)}，现用某一种遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__________遍历方法。 9、设有一组记录的关键字为{19, 14, 1, 68,20,27, 55, 79}，用拉链法构造哈希表，哈希函数为h(key)=key%13，哈希地址为1的链中有________个记录。 10、已知有序表为(16, 18, 28, 35, 47, 52, 62, 88, 90, 118, 256)，当用二分法查找90时，需经过________次查找成功。 ;二、选择题 ;4、假设以行序为主序存储二维数组A[i][j]（1≤i≤100，1≤j≤100），设每个数据元素占2个存储单元，二维数组存储的起始地址为10，则Loc(A[5][5])= ( ) A) 808 B) 818 C) 1010 D) 1020 5、深度为6（根的层次为1）的二叉树至??有（ ）个结点。 A）64 B）32 C）31 D）63 6、设一个栈输入序列是1、2、3、4、5，则下列序列中不可能是栈的输出序列是（ ）。 A）32541 B）15432 C）14523 D）23145 7、二叉树的前序遍历为EFHIGJK，中序遍历序列为HFIEJKG。该二叉树根结点的右子树的根是（ ） A) E B) F C) G D) H;8、下面几个符号串编码集合中，不是前缀编码的是（ ） A) {0, 10, 110, 1111} B) {11, 10, 001, 101, 0001} C) {00, 010, 0110, 1000 D) {b, c, aa, ac, aba, abb, abc} 9、 m阶B-树中所有的非终端（除根外）结点中的关键字的个数必须大于或等于（ ）。 A） m B）m/2 C）m/2 +1 D）m/2 -1;三、简答题 ;2. 将图2所示的两棵树组成的森林转换为二叉树。;;4、已知结点权值：4，2，5，7，5。画出相应哈夫曼树并计算带权路径长度WPL。哈夫曼树中结点用结点的权值表示. ;6、对图3的3阶B-树，依次执行下列操作，画出各步操作的结果。 （1）插入90 ；（2）插入25；（3）插入45；（4）删除60；;7.已知下图所示的无向带权图： ;8、下图的邻接表表示一个给定的无向图。 ;算法填空 ;下面是二叉有哪些信誉好的足球投注网站树的有哪些信誉好的足球投注网站算法。 ;程序阅读题 ;问题： 1）以上程序实现了二叉树类的什么功能？ 2）如果有一棵二叉树对象如下图所示，则该对象调用H()输出的结果是什么？ 3）为什么要分别定义一个公有和一个私有的H函数共同实现该功能？;编程题 在类SingleList中增加一个成员函数,删除表中指定的元素x。函数原型如下： template class T bool SingleListT::Del(const T x)