寻一份《数据结构》试题及答案

《数据结构》试题一、选择题（每小题2分,共30分）1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素,则采用（ ）存储方式最节省时间.A、单链表 B、双链表 C、单向循环 D、顺序表2． 串是任意有限个（ ）A、符号构成的序列 B、符号构成的集合C、字符构成的序列 D、字符构成的集合3． 设矩阵A（aij ,l≤i,j≤ 10）的元素满足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (inext=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、简答题：（每小题4分,共20分）1. 对于一个有10000个结点的二叉树,树叶最多有多少个?最少有多少个?2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA,则该二叉树的前序序列是什么?3. 设有1000个无序的元素,需排出前10个最大（小）的元素,你认为采用哪种排序方法最快?为什么?4. 在KMP算法中,已知模式串为ADABCADADA ,请写出模式串的next[j]函数值.5. 中序遍历的递归算法平均空间复杂度为多少? 五、 算法设计题（每小题10分,共20分）1. 试编写一个算法,判断一给定的整型数组a[n]是不是一个堆.2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积.试写一高效算法,求二叉树的繁茂度.参考答案一、选择题1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C 13、B　　14、C　　15、D　　二、判断题 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空题1．U=L - > next2．4.　3．n-1、n(n-1)/2.4．p - > prior = NULL.5．连通6．回路或环7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I10．rear - > next = p、rear = p四、简答题：1. 答： 最多是完全二叉树的形态,即5000个叶子；最少是单支树的形态,即1个叶子.2.答：是：ABDEGCFH3. 答：用锦标赛排序或堆排序很合适,因为不必等全部元素排完就能得到所需结果,时间效率为O(nlog2n)； 即O（1000log21000）=O(10000) 锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089若用冒泡排序也较快,最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考虑递归时占用了栈空间,但递归次数最多不超过树的高度,所以空间复杂度为O(log2n) 五、 算法设计题1.提示：堆的定义是：kirchild, r.layer+1}); } //按层序入队时要随时标注结点所在层号 h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0], i=1; h; i++) if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多 return (h*maxn)} // Width