《数据结构》试题参考答案 （开卷）（电信系本科2001级 2002年12月）一、回答下列问题 (每题4分，共36分)1. 某完全二叉树共有15381个结点，请问其树叶有多少个？ 答：n2=⎡n/2⎤=⎡15381/2⎤=7691(个)2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。
已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=13183. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。
答：根据0 当j ＝1时next[ j ]＝ max { k |1<k<j 且‘T 1…T k-1’=‘T j-(k-1) …T j-1’ }1 其他情况对应模式串的next[ j ]演示程序亦验证了结果：next[j]=01121123434. 已知一棵二叉树的前序序列和中序序列分别为：ABDEGCFH 和DBGEACHF ，则该二叉树的后序序列是什么？答：法1：先画树而得后序序列；A(DBGE) (CHF)B C结论：DGEBHFCAD (GE) (HF)E F G H法2：直接推出后序序列 step1: (DBGE) (CHF)A step2: D(GE)B (HF) C A step3: DGE B HF C A5. 请证明：用二叉链表法（Lchild-Rchild ）存储包含n 个结点的二叉树，必有n+1个指针域为空。
答：因为：用二叉链表存储包含n 个结点的二叉树，结点共有2n 个链域；又因为：二叉树中除根结点外，每一个结点有且仅有一个双亲，这就意味着只有n-1个结点的链域存放指向非空子女结点的指针（换句话说，有后继孩子链接的指针仅n-1个）；所以，空指针数目＝全部指针数2n －所有非空指针数(n-1)=所有空指针数＝n ＋1，证毕。
6.设二叉排序树中关键字互不相同，则其中最小元素必无左孩子，最大元素必无右孩子。
此命题是否正确？最大元素和最小元素一定是叶子吗？一个新的结点总是插在二叉排序树的某叶子上吗？ 请解释理由。
答：① 设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。
此命题正确。
解释：假设最小元为min ，若最小元min 有左孩子min ’，根据二叉排序树的定义应该有：min ’< min,与min 是最小元矛盾，由此可反证出最小元必无左孩子；同理可反证出最大元必无右孩子。
② 最大元和最小元不一定是叶子；解释：虽然最小元必无左孩子，最大元必无右孩子，但最小元可有右孩子，最大元可有左孩子。
如下图A 和B 所示。
所以最大元和最小元不一定是叶子。
③ 一个新的结点不一定总是插在二叉排序树的某叶子上。
解释：例如给定关键字{A,B,C}，以B 、A 、C 的次序插入一空的二叉排序树中，过程如下图C 所示。
当再插入C 时，C 作为B 的右孩子，插入后如图D 所示，但此时B 已有左孩子A ，元矛盾，由此可反证出最小元必无左孩子；同理可反证出最大元必无右孩子。
7. 假设一有序表中有23个元素，现进行折半查找，则平均查找长度是多少？ 答：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不能按照公式1)1(log 12-++=n nn ASL 来计算（即24/23（log 224）-1≈3.785次并不正确！）。
因为这是在假设n ＝2m-1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋8×5）＝89； ASL ＝89/23=3.878. 已知输入序列的入栈次序为X 、Y 、Z ，请列出出栈的所有可能序列。
答： 共5种可能的序列。
(1) X 、Y 、Z 全入 Z 、Y 、X 出栈 (2) X 、Y 先入栈 Y 、X 、 Z 出栈 Y 、Z 、X 出栈(3) X 先入栈 X 、Y 、Z 出栈 X 、Z 、Y 出栈9. 若初始记录基本有序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？请解释理由（排序方法各列举两种即可）。
答：基本有序时可选用直接插入、简单选择、堆排序、锦标赛排序、冒泡排序、归并排序、(希尔排序)等方法，其中插入排序和冒泡应该是最快的。
因为只有比较动作，无需移动元素。
此时平均时间复杂度为O(n)；无序的情况下最好选用快速排序、希尔排序、简单选择排序等，这些算法的共同特点是，通过“振荡”让数值相差不大但位置差异很大的元素尽快到位。
二、综合题（每题7分，共28分）1.设某一通信系统由0～9十种字符组成，其出现的概率为:ω={0.20, 0.11,0.06, 0.03, 0.12, 0.06, 0.19,0.01, 0.13, 0.09}, 现用Huffman 方法进行编码，请画出对应的Huffman 树，并计算平均码长WPL 。
答：① 可以先扩大100倍，以方便构造哈夫曼树。
也可以直接构造。
ω={0.20,0.11,0.06,0.03,0.12, 0.06,0.19,0.01,0.13, 0.09}② 平均码长是WPL （而不是ASL ）WPL ＝5（0.03＋0.01）＋＋4（0.06+0.06+0.09）＋+3（0.11+0.12+0.13+0.19）++2（0.20）＝0.2+0.84+1.65+0.4 ＝3.092. 欲将无序序列（23, 78, 12, 35, 69, 95, 11, 09, 35*, 48, 99, 26）中的关键码按升序重新排列，请写出快速排序第一趟排序的结果序列。
另外请画出堆排序（小根堆）的初始堆。
（注意要按振荡式逼近算法实现）② 堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排成小根堆！无序堆 有序初始堆3. 已知一组关键字为（10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49），设哈希函数H （key ）＝key MOD 7。
请给出以下解答： （1） 画出用链地址法处理冲突构造所得的哈希表；（2） 若查找关键字17，需要依次与哪些关键字进行比较？ （3） 若查找关键字60，需要依次与哪些关键字比较？（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
解：(1)(2) 若查找关键字（3） 若查找关键字60，需要依次与哪些关键字比较？ 先查4单元，与32、46比较，再查指针为空则返回。
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
11个元素中，有5个需比较1次，有4个需比较2次，有1个需比较3次，有1个需要比较4次，所以： ASL ＝（5×1＋4×2+1×3+1×4）/11=20/114. 某无向图G 的邻接表如下图所示。
要求：①请画出该图G 的逻辑结构图；② 根据邻接表写出其深度优先遍历序列和广度优先遍历序列(设访问起点为v 3)； ③ 根据遍历结果，画出图G 的深度优先和广度优先生成树。
0 1 2 3 4 56②根据邻接表写出其深度优先遍历序列和广度优先遍历序列(设访问起点为v3)；深度优先遍历序列＝3-2-7-1-0-4-6-5 广度优先遍历序列＝3-2-0-7-1-4-6-5 ③根据遍历结果，画出图G36分）1. 试用C或类C语言编写一个算法，将一循环单链表就地逆置。
（9分）解：要想让an指向an-1,……a2指向a1，至少有两种算法：法1 ：用插入法，扫描a1……an, 将每个ai插入到链表首部即可(实际上是链栈的概念)；法2：用替换法：扫描a1……an, 将每个ai—1的指针域送入ai+1的指针域。
2. 定义二叉树的宽度为二叉树一层中结点个数的最大值，试编写一算法求二叉树的宽度。
（9分）解：要用层次遍历以及队列来处理，并一定要设立一个宽度计数器和一个temp，在统计完每一层的结点个数之后就要与计数器中前一层的值比较，保留大值。
可参见严题集【6.52】④。
参考程序如下：typedef struct{BTNode node;int layer;int layer;} BTNRecord; //包含结点所在层次的记录类型int FanMao(Bitree T) //求一棵二叉树的"繁茂度"{int count d; //count数组存放每一层的结点数InitQueue(Q); //Q的元素为BTNRecord类型EnQueue(Q,{T, 0});while(!QueueEmpty(Q)){DeQueue(Q,r);count[yer]++;if(r.node->lchild) EnQueue(Q,{r.node->lchild, yer+1});if(r.node->rchild) EnQueue(Q,{r.node->rchild, yer+1});} //利用层序遍历来统计各层的结点数h=yer; //最后一个队列元素所在层就是树的高度for(maxn=count[0], i=1;h count[i]; i++)if(count[i]>maxn) maxn=count[i]; //求层最大结点数return (h*maxn);} //FanMao分析: 如果不允许使用辅助数组，就必须在遍历的同时求出层最大结点数，形式上会复杂一些。
3. 试用C或类C语言编写一个算法：（A、B两题任选其一， 9分）A.统计二叉树的总结点数和叶子结点数。
B. 对于一个有10000个记录的线性表，希望用尽可能快的速度挑选出前10个最小的记录。
解：A容易，将遍历函数中Visit()细化即可，设立两个计数器，一个每次都＋＋，一个是遇见叶子才＋＋。
或者，可参考【严题集6.42③】编写递归算法（计算二叉树中叶子结点的数目）。
至于总结点数就更容易添加了。
思路：用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其用sum2计数。
至于总结点数，无论是否叶子都累计到sum中即可。
法一：核心部分为：初始化：sum=sum2=0;DLR(liuyu *root) //中序遍历的递归函数{if(root!=NULL){if((root->lchild==NULL)&&(root->rchild==NULL))sum2++; //统计叶子结点数sum++; //统计总结点数DLR(root->lchild);DLR(root->rchild); }return(0);}B稍难，用冒泡排序加标志会在有序的情况下很快；但用锦标赛排序会在一般情况下更有优势，快得多。