6.5 已知一棵度为k的树中有1n个度为1的结点，2n个度为2的结点，…，kn个
度为k的结点，问该树中有多少个叶子结点？
解：由题意可知:
总结点数为: 1+n1+2*n2+3*n3+...+k*nk
而度为0的结点数就应为总结点数减去度不为0的结点数的总和，即
no=1+n1+2*n2+3*n3+...+k*nk-(n1+n2+n3+...+nk)
6.7 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？
解：能达到最大深度的树是单支树，其深度为n。满k叉树的深度最小，其
深度为:)1)1((logknk
6、26
HT储存的初始状态：
HT储存的终结状态：
根据题意构造的霍夫曼树为下图：
霍夫曼编码为：
6、27
AI
100
32 10 7 17 6 5 2 3 60 19 21 28
40
11
6、29
E
A B D F H
G I K J C
A
B
D
F
G
H C I
E
J
大工16秋《数据结构》在线作业21：若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（）。
A：gdbehfcaB：bdgaechfC：gdbecfhaD：gcefhabd正确答案：A2：具有3个结点的二叉树可能有（）种不同的形态。
A：3B：4C：5D：6正确答案：C3：若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（）。
A：cbedaB：decabC：deabcD：cedba正确答案：D4：（）方法可以判断出一个有向图中是否有环（回路）。
A：深度优先遍历B：拓扑排序C：求最短路径D：求关键路径正确答案：B5：深度为k的完全二叉树，其叶子结点必在第（）层上。
A：k-1B：1C：kD：k-1或k正确答案：D6：Huffman树的带权路径长度WPL等于（）。
A：除根结点之外的所有结点权值之和B：所有结点权值之和C：根结点的值D：各叶子结点的带权路径长度之和正确答案：D7：具有N个结点的完全二叉树的深度是（）。
A：log2NB：log2N +1C：log2(2N)D：log2N -1正确答案：B8：设有8个结点的无向图，该图至少应有（）条边才能确保是一个连通图。
A：5B：6C：7D：8正确答案：C9：任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（）。
A：发生改变B：不发生改变C：不能确定D：以上都不对正确答案：B10：一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。
A：250B：254C：501D：505正确答案：C11：在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
A：错误B：正确正确答案：A12：中缀表达式A+(B-C/D)*E的后缀形式是ABCD/-E*+。
A：错误B：正确正确答案：B13：度为2的有序树是二叉树。
A：错误B：正确正确答案：A14：若已知一棵二叉树的前序遍历序列和后序遍历序列，可以恢复该二叉树。
1. 假设用于通信的电文仅由8个字母（a, b, c, d, e, f, g, h ）组成，字母在电文中出现的频率分别是0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21和0.10。
为这8个字母设计一套哈夫曼编码，并计算其一个字母的平均编码长度（二进制位数）。
以上述8个字母为叶子结点构造的一棵最优二叉树如下：由其可得一套哈夫曼编码：a 0010b 10c 00000d 0001e 01f 00001g 11h 0011平均编码长度是 ∑P i ∙L i = 0.07×4 + 0.19×2 + 0.02×5 + 0.06×4 + 0.32×2 + 0.03×5 + 0.21×2 + 0.10×4 = 2.612. 无向网的5个顶点依序为a, b, c, d, e ，其邻接矩阵如下，画出该图及其最小生成树。
⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞713741143101338111083. 画出如下有向图的邻接表。
4. 编写运用栈实现图的深度优先搜索的非递归算法。
void dfs(graph G, int v0) // 一个连通分量上的深度优先搜索{ int v, w;visit(G,v0); // 访问出发顶点G.list[v0].visited=1;init_stack(S); // 初始化栈push(S,v0); // 出发顶点地址（下标）入栈while(!empty_stack(S)) // 当栈非空则执行以下循环{ v=gettop(S); // 取栈顶w=first_adj(G,v); // 求其第一个邻接点while(w && G.list[w].visited) // 寻找一个未被访问的邻接点 w=next_adj(G,v,w);if(w) // 若存在一个v的未被访问的邻接点w{ visit(G,w); // 访问wG.list[w].visited=1;push(S,w); // w入栈}else pop(S); // 否则，v的所有邻接点已访问或无邻接点则v出栈}}void depth_first_search(graph G) // 整个图的遍历{ for(int i=0; i<G.vexnum; i++) G.list[i].visited=0; // 被访标记复位 for(int i=0; i<G.vexnum; i++)if(G.list[i].visited==0) dfs(G,i);}。
《数据结构》2015年春学期在线作业（三）单选题1. 设在二叉排序树上要删除P指向的节点，且设f指向P的父结点，P为f的左孩子,P结点只有左子树,无右子树,那么应做的操作是什么？（）。
A. f->lchild=nullB. f->lchild=p->lchildC. f->lchild=p->rchildD. 都不是?正确答案：B2. 设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（）。
A. G’为G 的子图B. G’为G 的连通分量C. G’为G的极小连通子图且V’=VD. G’为G的一个无环子图?正确答案：B3. 希尔排序和快速排序分别属于（）。
A. 交换排序选择排序B. 插入排序选择排序C. 选择排序归并排序D. 交换排序选择排序?正确答案：B4. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（）次探测。
A. kB. k-1C. k(k-1)/2D. 1+k(k-1)/2?正确答案：C5. 图结构的广度优先搜索遍历算法中使用了（）。
A. 堆栈B. 队列C. 堆栈和队列D. 以上都不正确。
?正确答案：B6. 对于一组结点，从空树开始，把他们插入到二叉排序树中，就建立了一棵二叉排序树。
这时，整个二叉排序树的形状取决于（）。
A. 结点的输入顺序B. 结点的存储结构C. 结点的取值范围D. 计算机的硬件?正确答案：A7. 以下说法错误的是（）。
A. 散列法存储的基本思想是由关键码的值决定数据的存储地址。
B. 散列表的结点中只包含数据元素自身的信息，不包含任何指针。
C. 装填因子是散列法的一个重要参数，它反映散列表的装填程度。
D. 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。
?正确答案：B8. 二叉查找树的查找效率与二叉树的树型有关, 在（）时其查找效率最低。
