2017青岛科技大学自命题试题数据结构.doc
第 页(共 3 页)1青 岛 科 技 大 学二一七年硕士研究生入学考试试题考试科目:数据结构注意事项:1本试卷共 三 道大题(共计 22 个小题) ,满分 150 分;2本卷属试题卷,答题另有答题卷,答案一律写在答题卷上,写在该试题卷上或草纸上均无效。要注意试卷清洁,不要在试卷上涂划;3必须用蓝、黑钢笔或签字笔答题,其它均无效。 一 选择题(每题 2 分,共 30 分)1 数据结构通常是研究数据结构的( )以及它们的操作。A)理想与逻辑 B)存储和抽象 C)理想和抽象 D)逻辑结构和存储结构2指出下面程序段的时间复杂度( ) 。i=1;While(inext=P; P-next=S; B)S-next=P-next; P=S;C)S-next=P-next; P-next=S; D)P-next=S; S-next=P;7具有 n 个叶子结点的哈夫曼树,所有结点个数为() 。A)2n B) 2n+1 C) 2n-2 D) 2n-18一棵深度为 K 的完全二叉树至少有( )结点。A)2 k+1 B) 2 k-1 C) 2 k-1 -1 D) 2 k+19 平面上有五个点 A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图 G 的点,每两点之间的距离是图 G 中对应边的权值。以下哪条边不是图 G 的最小生成树中的() 。第 页(共 3 页)2A)EA B) AD C)DE D)BD10 二叉树 T 的层次遍历序列为 A B C D E F G H I,已知 A 是 C 的父结点,D 是 G 的父结点,F 是 I 的父结点,树中所有结点的最大深度为 3(根结点深度设为 0) ,可知 F 的父结点为() 。A) B B) E C) D D) C11设栈的初始状态为空,元素 a,b,c,d,e,f,g 依次进栈,以下出栈序列不可能出现的是() 。A)a,b,c,e,d,f,g B)g,e,f,d,c,b,a C)b,c,a,f,e,g,d D)d,c,f,e,b,a,g12一个 n 阶对称矩阵,如果以行或列为主序存入内存,则容量为() 。A) n*n B) n*n/2 C) n*(n+1)/2 D) (n+1)*(n+1)/213n 个顶点的强连通图至少有( )条边,其形状是() 。A)n*(n-1),树状 B)n+1,有回路 C) n-1,无回路 D)n,环状14若用冒泡法对序列(10,14,26,29,41,52)从大到小排序,则需要进行()次比较。A) 3 B) 15 C) 10 D)2515具有 12 个关键字的有序表,若查找每个元素的概率相同,进行二分查找的平均查找长度为( )。A)4 B)2.5 C)3.1 D)5二应用题(60 分) 1 (15 分)什么是最优树?假设用于通信的电文仅由 8 个字母组成,字母在电文中出现的频率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。 试为这 8 个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例,比较两种方案的优缺点。2.(15 分)什么是关键路径?什么是关键活动?试对下图所示的 AOE-网: 求这个工程最早可能在什么时间结束; 求每个活动的最早开始时间和最迟开始时间; 确定哪些活动是关键活动3 (15 分)假设线性表的关键字集合为 key=32,75,31,63,48,94,25,47,18,70,散列地址空间为HT11,若采用除留余数法构造散列函数和链地址法处理冲突,试求出每一元素的散列地址,画出最后得到的散列表,并求出等概率下查找成功的平均查找长度。4. (15 分)阅读以下算法: 该算法是什么样排序算法;该算法待排序记录的存储结构是什么?简述该排序算法的思想;设待排序的关键字序列为12,2,16,30,28,10 ,16*,20,6,18 ,试写出使用该排第 页(共 3 页)3序方法,每趟排序结束后关键字序列的状态;void Sort ( SqList i =high+1; - - j ) L.rj+1 = L.rj;L.rhigh+1 = L.r0; / Sort三算法设计题(60 分)1.(20 分)已知 head 是指向带头结点的单链表的头指针,试编写以下算法:统计单链表中结点个数的算法;删除单链表中值为 x 的算法;2 (20 分)设以二叉链表作为二叉树的存储结构,写出如下算法:用先序遍历的方法,统计二叉树中度为 1 的结点的个数;用层次遍历的方法,统计二叉树中度为 1 的结点的个数;3(20 分)写出如下算法:创建一个有向图邻接表的存储结构的算法;写出利用该存储结构实现对有向图进行拓扑排序的算法;