姓名 班级 数据结构试题参考答案 （开卷）（电信系本科2001级 2002年12月）一、回答下列问题 (每题4分，共36分)1. 某完全二叉树共有15381个结点，请问其树叶有多少个？答：n2=n/2=15381/2=7691(个)2. 假设有二维数组A79，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，末尾元素A68的第一个字节地址为多少？若按列存储时，元素A47的第一个字节地址为多少？答： 末尾元素A68的第一个字节地址1000（7行9列1）6B1000626=1372 按列存储时，元素A47的第一个字节地址1000（7列7行4）6B1000536=13183. 在KMP算法中，已知模式串为ADABBADADA ，请写出模式串的nextj函数值。答：根据 0 当j1时next j max k |1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情况1 2 3 4 5 6 7 8 9 100 1 1 2 1 1 2 3 4 3A D A B B A D A D A对应模式串的next j 演示程序亦验证了结果：nextj=01121123434. 已知一棵二叉树的前序序列和中序序列分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序序列是什么？ 答：法1：先画树而得后序序列； AB CD E F G H A(DBGE) (CHF) B C 结论：D G E B H F C AD (GE) (HF)E F G H法2：直接推出后序序列 step1: (DBGE) (CHF) Astep2: D(GE)B (HF) C Astep3: DGEB HF C A5. 请证明：用二叉链表法（Lchild-Rchild）存储包含n个结点的二叉树，必有n+1个指针域为空。答：因为：用二叉链表存储包含n个结点的二叉树，结点共有2n个链域；又因为：二叉树中除根结点外，每一个结点有且仅有一个双亲，这就意味着只有n-1个结点的链域存放指向非空子女结点的指针（换句话说，有后继孩子链接的指针仅n-1个）；所以，空指针数目全部指针数2n所有非空指针数(n-1)=所有空指针数n1，证毕。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（log2n）5次（25）。但具体是多少次，则不能按照公式来计算（即24/23（log224）-13.785次并不正确！）。因为这是在假设n2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为（122438485）89； ASL89/23=3.87 8. 已知输入序列的入栈次序为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.设某一通信系统由09十种字符组成，其出现的概率为: w=0.20, 0.11, 0.06, 0.03, 0.12, 0.06, 0.19, 0.01, 0.13, 0.09, 现用Huffman方法进行编码，请画出对应的Huffman树，并计算平均码长WPL。答： 可以先扩大100倍，以方便构造哈夫曼树。也可以直接构造。w=0.20, 0.11, 0.06, 0.03, 0.12, 0.06, 0.19, 0.01, 0.13, 0.09 1.00 0.59 0.34 0.25 0.41 0.15 0.19 0.12 0.13 0.21 0.20 0.09 0.06 0.10 0.11 0.06 0.040.03 0.01 平均码长是WPL（而不是ASL）WPL5（0.030.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.43.092. 欲将无序序列（23, 78, 12, 35, 69, 95, 11, 09, 35*, 48, 99, 26）中的关键码按升序重新排列，请写出快速排序第一趟排序的结果序列。另外请画出堆排序（小根堆）的初始堆。答：快速排序第一趟排序的结果序列为：09， 11， 12， 23， 69， 95, 35, 78, 35*, 48, 99, 26（注意要按振荡式逼近算法实现） 堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排成小根堆！ 初始堆序列为： 09，23，11，78，48，26，12，35，35*, 69, 99, 95无序堆 有序初始堆 0923 1178 48 26 12 35 35*69 99 95 2378 1235 69 95 11 09 35*48 99 263. 已知一组关键字为（10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49），设哈希函数H（key）key MOD 7。请给出以下解答：（1） 画出用链地址法处理冲突构造所得的哈希表；（2） 若查找关键字17，需要依次与哪些关键字进行比较？（3） 若查找关键字60，需要依次与哪些关键字比较？（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解：(1) 哈希表如下：01234566349301024173132464740 (2) 若查找关键字31，需要依次与哪些关键字进行比较？ 10、24、17和31（3） 若查找关键字60，需要依次与哪些关键字比较？ 先查4单元，与32、46比较，再查指针为空则返回。（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。11个元素中，有5个需比较1次，有4个需比较2次，有1个需比较3次，有1个需要比较4次，所以： ASL（5142+13+14）/11=20/111. 824. 某无向图G的邻接表如下图所示。要求： 请画出该图G的逻辑结构图； 根据邻接表写出其深度优先遍历序列和广度优先遍历序列(设访问起点为v3)； 根据遍历结果，画出图G的深度优先和广度优先生成树。01234567v0431v0 v1 v3 v4v2 v5 v6 v7 v1 20v2731v320v4650v564v654v72解：该无向图G的逻辑结构图如右图所示： 根据邻接表写出其深度优先遍历序列和广度优先遍历序列(设访问起点为v3)；深度优先遍历序列3-2-7-1-0-4-6-5 广度优先遍历序列3-2-0-7-1-4-6-5 根据遍历结果，画出图G的深度优先和广度优先生成树如下(注意到访问起点为v3)。v3 v2 v0