数据结构试卷和答案

《数据结构试卷和答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、＝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

3、1

4、和中序序列分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序序列是什么？答：法1：先画树而得后序序列；ABCDEFGHA(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个链域；又因为：二叉树中除根结点外，每一个结

5、点有且仅有一个双亲，这就意味着只有n-1个结点的链域存放指向非空子女结点的指针（换句话说，有后继孩子链接的指针仅n-1个）；所以，空指针数目＝全部指针数2n－所有非空指针数(n-1)=所有空指针数＝n＋1，证毕。6.设二叉排序树中关键字互不相同，则其中最小元素必无左孩子，最大元素必无右孩子。此命题是否正确？最大元素和最小元素一定是叶子吗？一个新的结点总是插在二叉排序树的某叶子上吗？7请解释理由。答：①设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题正确。解释：假设最小元为min，若最小元min有左

6、孩子min’，根据二叉排序树的定义应该有：min’

7、由此可反证出最小元必无左孩子；同理可反证出最大元必无右孩子。7.假设一有序表中有23个元素，现进行折半查找，则平均查找长度是多少？答：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不能按照公式来计算（即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种可能的序

8、列。(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)；无序的情况下最好选用快速排序、希尔排序、简单选择排序等，这些算法的共同特点是，

9、通过“振荡”让数值相差不大但位置差异很大的元素尽快到位。二、综合题（每题7分，共28分）1.设某一通信系统由0～9十种字符组成，其出现的概率为:w={0.20,0.11,0.06,0.03,0.12,0.06,0.19,0.01,0.13,0.09},现用Huffman方法进