青岛XX大学数据结构复习题2期末试题及参考答案(DOC 6页).doc

1、教师试做时间出题教师 房斐斐取题时间审核教研室主任出题单位使用班级考试日期考试成绩期望值 印刷份数 规定完成时间 交教学部印刷日期 学号： 姓名： 班级： .密.封.线. 专业 年级 班 20 20 学年第 学期 数据结构 课试卷 试卷类型：复习题2卷题号一二三四五六七八九十总成绩得分 一、 填空题（每空1分，共10分）1. 数据结构被形式地定义为(D，R)，其中D是_的有限集合，R是D上的_有限集合。2. 栈中元素的进出原则是_。3. 假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则末尾元素A57的第一个字节地址为 ；若按行存

2、储时，元素A14的第一个字节地址为 。4. 一棵具有257个结点的完全二叉树，它的深度为 。5. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 。6. 线性有序表(a1, a2, a3, , a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。7. 设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是_。8. 在堆排序、快速排序和归并排序中，若只从最坏情况下最快并且要节省内存考虑，则应选取_方法。二、 选择题（每题2分，共30分）

3、（ ）1. 算法分析的两个主要方面是：（A）空间复杂性和时间复杂性 （B）正确性和简明性（C）可读性和文档性 （D）数据复杂性和程序复杂性（ ）2. 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：（A）访问第i个结点（1in）和求第i个结点的直接前驱（2in） （B）在第i个结点后插入一个新结点（1in）（C）删除第i个结点（1in）（D）将n个结点从小到大排序（ ）3双向循环链表的每个结点中包括两个指针next和previous，分别指向该结点的后继和前驱结点。现要删除指针p所指向的结点，下面的操作序列中哪一个是正确的？（A）p-next-previous = p -previo

4、us; p -previous-next = p -next；（B）p -next-previous = p -next; p -previous-next = p -previous；（C）p -previous-next = p -previous; p -next-previous = p -next；（D）p -previous-next-next = p -next; p -next-previous = p - previous；（ ）4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连

5、续都可以（ ）5. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（）i （）n=i （）n-i+1 （）不确定（ ）6. 数组Qn用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为（）rf （）（nfr）% n （）nrf （）（nrf）% n（ ）7. 判定一个栈ST（最多元素为m）为空的条件是（）ST-top0 （）ST-top=0 （）ST-topm （）ST-top=m青岛理工大学成教学院试卷纸 共 页 第 1 页试题要求：1、试题后标注本题得分；2、试卷应附有评

6、卷用标准答案，并有每题每步得分标准；3、试卷必须装订，拆散无效；4、试卷必须打印或用碳素笔楷书，以便誉印；5、考试前到指定地点领取试卷；6、各题之间应适当给学生留下答题的空间。学号； 姓名： 班级： .密.封.线. _学年第 学期 数据结构 课程试卷标准答案及评分标准 复习题2卷 注意：标题请用宋体4号，内容请用宋体5号。一、填空题(每空1分，共10分)1. 数据元素；关系2. 后进先出3. 1282；10724. 95. O(n+e)6. 87. H C Q P A M S R D F X Y8. 堆排序二、 单项选择题(每空2分，共30分，多选漏选均不得分)1. A 2. A 3. A 4

7、.D 5.C6. D 7. B 8. A 9.D 10.B11. C 12. D 13. A 14.A 15.D三、判断题(每题1分，共10分)1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 四、简答题(共18分，意思正确给分)1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？（共4分）解答： 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示

8、结点间关系的指针。优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（rchild; /应改为r=q；if(!r-rtag) while(!r-rtag)r=r-rchild; /应改为 while(!r-Ltag) r=r-Lchild;return r; /应改为return r-rchild；/ISucc答：这是找结点后继的程序。共有3处错误。当rtag0时说明内装右孩子指针，但孩子未必是后继，需要计算。中序遍历应当先左再根再右，所以应当找左子树直到叶子处。r=r-lchild; 直到LTag=1； 应改为：while(!r-Ltag)r=r-Lchild;六、算法设计题（两题共1

9、6分）1. （共8分）int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else m = Depth( T-lchild ); n= Depth( T-rchild ); depthval = 1 + (m n ? m : n); return depthval; 2. （共8分）int Search_Bin_Recursive(SSTable ST, int key, int low, int high) /折半查找的递归算法 if(lowhigh) return 0; /查找不到时返回0 mid=(low+high)/2; i

10、f(ST.elemmid.key= =key) return mid; else if(ST.elemmid.keykey) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); /Search_Bin_Recursive （ ）8. 判定一个队列QU（最多元素为m）为满队列的条件是（）QU-rear QU-front = = m （）QU-rear QU-front 1= = m（）QU-front = = QU-rear （）QU-f

11、ront = = QU-rear+1（ ）9. 设串s1=ABCDEFG，s2=PQRST，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的结果串是：（）BCDEF （）BCDEFG （）BCPQRST （）BCDEFEF（ ）10. 具有12个结点的完全二叉树有个度为2的结点。（）4 （）5 （）6 （）7（ ）11. 具有n(n0)个结点的完全二叉树的深度为 。（） log2(n) （） log2(n) （

12、） log2(n) +1 （） log2(n)+1（ ）12. 已知图的邻接矩阵如右图，根据算法，则从顶点0出发，按深度优先遍历的结点序列是：（）0 2 4 3 1 5 6 （）0 1 3 5 6 4 2 （）0 4 2 3 1 6 5 （）0 1 3 4 2 5 6（ ）13. 设哈希表长度为11，哈希函数为H（key）=key mod 11。表中已有4个元素H（15）=4；H（38）=5；H（61）=6；H（84）=7其余地址为空，若用二次探测再散列处理冲突，关键字为49的元素的地址是_。（）3 （）5 （）8 （）9（ ）14. 假设有60行70列的二维数组a160, 170以列序为主序

13、顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a32,58的存储地址为 。（无第0行第0列元素）（）16902 （）16904 （）14454 （）答案A, B, C均不对（ ）15. 广度优先遍历类似于二叉树的（）先序遍历 （B）中序遍历 （C）后序遍历 （D）层次遍历三、 判断题（每题1分，共10分）（ ）1. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（ ）2. 线性表在物理存储空间中也一定是连续的。（ ）3. 顺序存储方式只能用于存储线性结构。（ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队

14、列，也可以是线性表。 （ ）5. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。（ ）6. 二叉树中每个结点的两棵子树是有序的。 （ ）7. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（ ）8. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ ）9. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。( )10. 设有一稠密图G，则G采用邻接矩阵存储较省空间。四、 简答题（共18分）1. 试比较顺序存储结

15、构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？（4分）2. 把如图所示的树转化成二叉树,并写出其前序、中序、后序遍历序列。（6分）3. 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。（共8分）（1）试构造哈夫曼树（4分）（2）试为这8个字母设计不等长Huffman编码,（2分）（3）求其WPL值。（2分）青岛理工大学成教学院试卷纸 共 页 第 页 学号； 姓名： 班级： .密.封.线. 五、 算法理解题（共16分）1. 阅读算法，写出该算法的结果 (

16、5分)main() SqStackTp sq; int i; char ch; InitStack(&sq); For(ch=A;chrchild;if(!r-rtag)while(!r-rtag)r=r-rchild;return r;/ISucc return state;3. 阅读下列算法，若有错，改正之。（6分）六、 算法设计题（两题共16分）1. 请编写一个递归算法，求二叉树的深度。（8分）2. 已知11个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写出折半查找的算法程序，查找关键字为key的数据元素。（8分）青岛理工大学成教学院试卷纸 共 页 第 页