5-8章习题答案-2013.doc

一、名词解释 1、二叉树： 2、哈夫曼树： 3、小根堆： 4、最小生成树 5、拓扑排序 6、二叉有哪些信誉好的足球投注网站树 7、出度： 8、权 二、填空 1、二叉树的度为： 2 ，当深度h=4时，其满二叉树的结点树为：15 。 2、在定义各种数据结构的存储实现时，为增强其数据类型的通用性，应将其定义为 通用数据（ElemType） 类型。如果是定义树的链接存储结构，除了定义数据类型，还应定义链接孩子结点的 左指针域(left) 和 右指针域(right) 。 3. 一棵二叉树的广义表表示是A（B（C,D）），则对其的中序遍历结果是 CBDA 。 4．对一棵完全二叉树的各结点从1开始编号，并按此编号把它顺序存储到一维数组a中，即将根结点编号为1并存储到a[1]中，其余类推，则a[i]元素的左孩子（如果有的话）元素为 a[2*i] ，右孩子（如果有的话）元素为 a[2*i+1] ，双亲元素（如果有的话）为 a[i/2] 。 5. 一个大根堆中，值最大的结点是 根 结点。 6、同一棵树中的数据元素必须是 同质（或同类型） 的。 7、一个广义表形式的二叉树A（B,C（，D）） 此二叉树的深度为 3 8、二叉有哪些信誉好的足球投注网站树是指树上所有 右 结点均大于 根结点 ，同时左右子树又各是一棵排序二叉树。 9、哈夫曼树是指此树的带权路径长度（WPL） 最小 。 10、图由非空顶点集和 边集 所组成。无向图某个顶点的度是 以该顶点为端点的边的数目。 11．一个有n个顶点的连通图的最小生成树的边数为 n-1 。 12、对有向图来说，出度是指某个顶点 出边的数目 。 13、在计算机中若采用索引查找，索引表中的每个索引项应至少包含索引值域 和 子表开始位置域 两个域。 14、在散列查找中，多个关键字求出的散列地址相同时，若散列地址已被占用，这种现象被称之为 冲突 。 15、在选择排序方法时，在最坏或平均情况下元素移动次数越多，则说明该方法的时间复杂性 越大（越差） 。 三、选择题 1、一棵三叉树的结点个数为10，则它的最小深度为 ？ ，最大深度为 ？ ，正确的是（ B ）。 A．5和8 B. 3和10 C. 1和10 D．2和7 2. 一棵深度为h的二叉树最多有（D ）个结点。 A．2h+1 B．2h-1 C．2h+1 D．2h-1 3. 一棵二叉树的第i层最多有（ D ）个结点。 A．2i+1 B．2i-1 C．2i+1 D．2i-1 4、在计算机领域，磁盘上的目录结构就是一棵树，对于这种数据结构，在查找时采用哪种方法较好？（ B ） A．顺序查找 B.二分查找 C. 索引查找 D. 散列查找 A．1 B.2 C. 3 D. 4 5、如果有一棵完全二叉树上的结点数是9，那么这棵二叉树的最大深度是（ C ） A．2 B．3 C．4 D．5 6、下列算法是二叉树的（ A ）。 void Preorder(struct BTreeNode* BT) { if(BT!=NULL){ printf(%c ,BT-data); Preorder(BT-left); Preorder(BT-right); } } A．前序遍历算法 B．中序遍历算法 C．后序遍历算法 D．按层遍历算法 7、 二叉有哪些信誉好的足球投注网站树的特点是（ B ）。 A．后序遍历有序 B．按层遍历有序 C．前序遍历有序 D．中序遍历有序 8、哈夫曼编码是（B ） A．等长编码 B．无前缀编码 C．有前缀编码 D．最短编码 9、根据大根堆排序，其排序结果为（B ）。 A．无序 B．升序 C．降序 D．逆序 10．一个图的边集形如：E(G)={(0,1), (0,2), (1,4),…},这是一个（A ）。 A．无向无权图 B．有向无权图 C．无向带权图 D．有向带权图 11．一个图的边集形如：E(G)={0,1, 0,2, 1,4,…},这是一个（B ）。 A．无向无权图 B．有向无权图 C．无向带权图 D．有向带权图 12．一个图的边集形如：E(G)={0,12, 0,23, 1,45,…},这是一个（ D