《《数据结构》试题 (开卷)》由会员分享，可在线阅读，更多相关《《数据结构》试题 (开卷)（13页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构试题试题 ( (开卷开卷) )个人总结，仅供交流 个人总结 数据结构试题 （开卷）（电信系本科 2002 级 2003 年 12 月）题号一二三总分题分323830100得分一、回答下列问题 (每题 4 分，共 32 分)1. 对于一个有 10000 个结点的二叉树，树叶最多有多少个？最少有多少个？答： 最多是完全二叉树的形态，即 5000 个叶子；最少是单支树的形态，即 1 个叶子。2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF 和DGEBHFCA，则该二叉树的前序序列是什么？答：是：ABDEGCFH3. 设有 1000 个无序的元素，需排出前 10 个最
2、大（小）的元素，你认为采用哪种排序方法最快？为什么？答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为 O(nlog2n)； 即 O（1000log21000）=O(10000)锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+910=1089堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+910=1089若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+.n-10）=10n-55=10000-55=9945（次）4. 在 KMP 算法中，已知模式串为 ADABCADADA ，请写出模式
3、串的nextj函数值。答： 01121123435. 中序遍历的递归算法平均空间复杂度为多少？答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为 O(log2n)6. 欲将无序序列（24, 79, 13, 36, 70, 96, 12, 10, 36*, 49, 100, 27）中的关键码按升序重新排列，请写出快速排序第一趟排序的结果序列。另外请画出堆排序（小根堆）的初始堆。答：快速排序第一趟排序的结果序列为：10， 12， 13， 24， 70， 96, 36, 79, 36*, 49, 100, 27（注意要按振荡式逼近算法实现） 堆排序的初始堆如下，注意要从排
4、无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排成小根堆！ 初始堆序列为： 10，24，12，79，49，27，13，36，36*, 70, 100, 96无序堆 有序初始堆7. 已知一组关键字为（10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49） ，设哈希函数H（key）key MOD 13。请写出用线性探测法处理冲突构造所得的哈希表。答：012345678910111249401731323046471024638. 算法复杂度 O（1）的含义是什么？答：它表示与输入的元素规模无关，是一个常数（但不一定是 1） 。或：它表示该算法执行时耗费时
5、间的长短或占用辅助空间的多少与元素个数 n 无关，若能达到这样的时间效率或空间效率，将是最理想的算法。二、综合题（4 小题，共 38 分）1. 下图为某无向图的邻接表，按教材算法 7.5 和 7.6 分别写出深度优先搜索和广度优先搜索的结果，并画出逻辑结构图。 (10 分) A5B 37C267DE1F3G23H910I8J8答：深度优先搜索（DFS）结果为：AEBCFGDHIJ广度优先搜索（BFS）结果为：AEBCGFDHIJ这是有着 4 个连通分量的非连通图。A EB C FG H ID J2. 设 AH 8 个字符出现的概率为: ?=0.10, 0.16, 0.01, 0.02, 0.2
6、9, 0.10, 0.07, 0.25, 设计最优二进制码并计算平均码长。如果设计最优三进制编码（即可用 0,1,2 三种符号进行编码） ，画出最优三叉树并计算平均码长。 (10分) 答：最优二进制编码不惟一，但 WPL 惟一。对三进制编码，由于总共有 8 个字符，8%3=2,故第一次构建最优树只有 2 个结点，则最优三叉树为3. 给定一个由 n 个关键字不同的记录构成的序列，你能否用 2n-3次比较找出 n 个元素中的最大值和最小值？如果有，请描述你的方法。最快需多少次比较？（无需写算法） (8 分)答：可以实现。选用锦标赛算法。两两元素比较，淘汰较小的，形如一棵二叉树。树根为最大值（此时用
7、掉 n-1 次比较？） 。而最小者一定位于首次被淘汰之列。故只有? n/2?个。一共需 n-1+? n/2?次比较。4. 分析下面算法中 l 和 h 变量表示什么含义？初始调用时，l 和 h应取什么值？其中 p 为指向二叉树的根结点，如果去掉形参中的“ /设左右两个深度/层次计数器if(BT=NULL) return(0); /当前结点指针为空则立即返回else leftdep= BTreeDepth(BT-left); /遍历当前结点左子树rightdep=BTreeDepth(BT-right); /遍历当前结点右子树if( leftdeprightdep)return(leftdep+1
8、); /从叶子计数else return(rightdep+1); /BTreeDepth三、 算法设计题（每题 10 分，共 30 分）个人总结，仅供交流 1. 试用 C 或类 C 语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。个人总结 解： void SortA(sqlist if(L.length=0) return(0); /空表else for( i=1; i0) L.vi- zerosum= L.vi;else ? zerosum+;2. 试编写一个算法，判断一给定的整型数组 an是不是一个堆。解：提示：堆的定义是
9、：kia2*i| aia2*i+1)return(-1);return(minleap);else for( i=1; ilchild) 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=count0, i=1; h; i+) if(countimaxn) maxn=counti; /求出哪一层结点数最多return (h*maxn) / Width
10、附加题：（15 分）设 p、t 分别表示两棵没有度为 1 的结点的二叉树。设计一种算法，找出 p 和 t 中最大的同构子树并分析算法的时间复杂度（无需写出算法，描述思路即可） 。注：“同构“是指两个二叉树不仅结点数相同、并且它们的左右子树之间的关系也相同，但各结点的数据值可以不同。“最大的同构子树“即结点最多的同构子树。解： 我们把一棵二叉树用树描述符来表示，则问题会变得容易解决。所谓树描述符，即对每个结点按二叉树先序遍历并输出结点的度。例如左边二叉树的描述符为 202202000.在此描述符中，如果一个子串的字符数等于此子串中每个数字之和加 1，则此子串一定是一个子树。如上面的字符串中，2202000 是一个子树，因为他有 7 个字符，每个字符数字和为 2+2+2=6.同理，20200,200 也是子树。问题转化为两个字符串中寻找满足上述条件的最长公共子串。最长公共子串的算法已有（见习题） ，只需在此算法中加上判断此子串是否是一个子树的条件即可。判断一个子串是否为一个子树的复杂度为 O（n）,n 为字符串长度。由于求最长公共子串的复杂度为 O(mn)，m、n 分别为 p 和 t 的结点数，判子串是否为子树的过程可以和求最长公共子串相结合，即在求最长公共子串中完成。则求最大同构子树的复杂度为 O(mn)。1个人总结 个人总结，仅供交流
