数据结构试卷和答案

1《数据结构》试题参考答案（开卷）（电信系本科2001级2002年12月）一、回答下列问题(每题4分，共36分)1.某完全二叉树共有15381个结点，请问其树叶有多少个？答：n2=n/2=15381/2=7691(个)2.假设有二维数组A7×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|1kj且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情况对应模式串的next[j]＝演示程序亦验证了结果：next[j]=01121123434.已知一棵二叉树的前序序列和中序序列分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序序列是什么？答：法1：先画树而得后序序列；A(DBGE)(CHF)BC结论：DGEBHFCAD(GE)(HF)EFGH法2：直接推出后序序列step1:(DBGE)(CHF)Astep2:D(GE)B(HF)CAstep3:DGEBHFCA5.请证明：用二叉链表法（Lchild-Rchild）存储包含n个结点的二叉树，必有n+1个指针域为空。答：因为：用二叉链表存储包含n个结点的二叉树，结点共有2n个链域；又因为：二叉树中除根结点外，每一个结点有且仅有一个双亲，这就意味着只有n-1个结点的链域存放指向非空子女结点的指针（换句话说，有后继孩子链接的指针仅n-1个）；所以，空指针数目＝全部指针数2n－所有非空指针数(n-1)=所有空指针数＝n＋1，证毕。6.设二叉排序树中关键字互不相同，则其中最小元素必无左孩子，最大元素必无右孩子。此命题是否正确？最大元素和最小元素一定是叶子吗？一个新的结点总是插在二叉排序树的某叶子上吗？请解释姓名班级123456789100112112343ADABBADADAABCDEFGH2理由。答：①设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题正确。解释：假设最小元为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）。但具体是多少次，则不能按照公式1)1(log12nnnASL来计算（即24/23（log224）-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）＋1.000.590.340.250.410.150.190.120.130.210.200.090.060.100.110.060.040.030.013+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）中的关键码按升序重新排列，请写出快速排序第一趟排序的结果序列。另外请画出堆排序（小根堆）的初始堆。答：①快速排序第一趟排序的结果序列为：09，11，12，[23]，69，95,35,78,35*,48,99,26（注意要按振荡式逼近算法实现）②堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排成小根堆！初始堆序列为：09，23，11，78，48，26，12，35，35*,69,99,95无序堆有序初始堆3.已知一组关键字为（10，24，32，17，31，30，46，47，40，63，49），设哈希函数H（key）＝keyMOD7。请给出以下解答：（1）画出用链地址法处理冲突构造所得的哈希表；（2）若查找关键字17，需要依次与哪些关键字进行比较？（3）若查找关键字60，需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解：(1)哈希表如下：6349^^30^10241731^3246^4740^^(2)若查找关键字31，需要依次与哪些关键字进行比较？10、24、17和31（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/11≈1.824.某无向图G的邻接表如下图所示。要求：①请画出该图G的逻辑结构图；②根据邻接表写出其深度优先遍历序列和广度优先遍历序列(设访问起点为v3)；③根据遍历结果，画出图G的深度优先和广度优先生成树。v0431^v120^v2731^v320^v4650^01234567237812356995110935*489926092311784826123535*6999950123456v0v1v3v4v2v5v6v74v564^v654^v72解：①该无向图G的逻辑结构图如右图所示：②根据邻接表写出其深度优先遍历序列和广度优先遍历序列(设访问起点为v3)；深度优先遍历序列＝3-2-7-1-0-4-6-5广度优先遍历序列＝3-2-0-7-1-4-6-5③根据遍历结果，画出图G的深度优先和广度优先生成树如下(注意到访问起点为v3)。三、算法设计题（4小题，共36分）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】④。参考程序如下：typedefstruct{BTNodenode;intlayer;intlayer;}BTNRecord;//包含结点所在层次的记录类型intFanMao(BitreeT)//求一棵二叉树的繁茂度{intcountd;//count数组存放每一层的结点数v3v2v7v1v0v4v6V5v3v2v0v7v1v4v6V5法1的核心部分为：q=head;p=head-next;while(p!=q){r=p-next;p-next=head;head=p;p=r;}q-next=head;法2的核心部分为：q=head;p=head-next;while(p!=head){r=p-next;p-next=q;q=p;p=r;}p-next=q;head=q;5InitQueue(Q);//Q的元素为BTNRecord类型EnQueue(Q,{T,0});while(!QueueEmpty(Q)){DeQueue(Q,r);count[r.layer]++;if(r.node-lchild)EnQueue(Q,{r.node-lchild,r.layer+1});if(r.node-rchild)EnQueue(Q,{r.node-rchild,r.layer+1});}//利用层序遍历来统计各层的结点数h=r.layer;//最后一个队列元素所在层就是树的高度for(maxn=count[0],i=1;hcount[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稍难，用冒泡排序加标志会在有序的情况下很快；但用锦标赛排序会在一般情况下更有优势，快得多。冒泡是O（n2）,锦标赛是O（n+9log2n）解：用冒泡排序的核心算法：法1的核心部分为：for(i=1;i=10;i++){tag=1;while(tag==1){tag=