题号：908
大连海事大学2013年硕士研究生招生考试试题
考试科目：数据结构
适用专业：计算机技术（专业学位），软件工程（专业学位）
考生须知：1、所有答案必须写在答题纸上，写在试题纸上无效；
2、考生不得在答题纸上作与答题内容无关的标记，否则试卷作废。
一、判断下列叙述是否正确。(共20分,每小题1分)
请在答卷上写出题号并用“√”或“×”回答。
1.顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。
2.因为线性表L是一个有序表,所以可采用折半查找方法来查找表中的数据元素,以减少查找成功时的ASL。
3.由于给定的有向无环图(DAG)中只有一个出度为0的顶点,所以该DAG的拓扑排序序列一定是唯一的。
4.若(u,v)是连通网络的一条最小权值的边,则一定存在一棵最小生成树包含(u,v)。 5.在一个AOE网中,若某一活动的最早开始时间和最迟开始时间相同，则该活动为关键活动。
6.在线索二叉树中,根据线索可以找到树中任何一个结点在相应遍历序列中的直接后继。
7.只要能够进行均匀映射的哈希函数就一定受欢迎。 8.能完全拓扑排序的有向图至少存在一个入度为0的顶点。
1
9.在哈夫曼树中,分支总数一定是偶数。
10.给定一棵的先序遍历序列和后序遍历序列,可以唯一地确定这棵树的结构。 11.哈夫曼树是最优二叉树,所以根结点到权值最大的叶结点之间的路径长度最长。 12.采用孩子―兄弟表示法可以唯一地表示一棵非空二叉树。
13.采用二叉链表作为存储结构,将一棵非空树转换成二叉树后,根结点没有右子树。 14.对任何长度为n＞0的序列,任何基于关键字比较的排序算法的时间复杂度都不小于O(n╳log2n)。
15.提高外排序速度的核心工作是减少记录在内外存之间的I/O次数。 16.对任何序列进行排序,快速排序一定比简单插入排序快。
17.在一棵平衡二叉树插入新结点x,由于做了平衡旋转处理,所以,结点x一定不可能是叶子结点。
18.任何广义表都可以用树型结构加以表示。
19.算法的优劣与算法描述语言无关,也与所使用的计算机无关。
20.按照定义,在7阶的B树中,每个非终端结点中指向其子树的指针数至少为4。
二、选择填空。(共20分,每小题2分。答案必须写在答卷上!) 1.具有12个结点的完全二叉树有（ ）
A.1个度为1的结点 B.5个叶结点 C.5个度为1的结点 D.5个分支结点 E.没有度为1的结点
2
2.对27个记录的有序顺序表作折半查找,当查找失败时,至少需要与关键字比较（ ）次
A.3 B.5 C.4 D.6 E.7
3.假设二维数组A［1...60,1...70］以列序为主序顺序存储，其中A［20,31］的地址为10000,每个元素占1个存储单元,那么A[27,29]的存储地址为（ ）
A.10113 B.9887 C.9774 D.10226 E.A~D都不对
4.设循环队列顺序存放在一维数组sq.data[0...m]中,采用牺牲一个存储单元的方式区分队满与队空的条件,且假设 sq.front指向队头元素的位置,sq.rear指向队尾元素的下一个位置,则修改队头指针的操作可表示为（ ）
A. sq.front=(sq.rear+ 1)MOD m B. sq.front=(sq.rear+ 1)MOD m+ 1 C. sq.front=(sq.front+ 1) MOD m D. sq.front= sq. rear
E. sq.front=(sq.front+ 1)MOD m+1
25.若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有（ ）棵树
A. k B. n
3
相关推荐：
loading