当前位置:问答库>考研试题

2017年山东财经大学计算机科学与技术学院809计算机专业基础综合之数据结构考研强化模拟题

  摘要

一、填空题

1. 应用prim 算法求解连通网络的最小生成树问题。

(1)针对如图所示的连通网络,试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

〔始顶点号,终顶点号,权值)

(2)下面是Prim 算法的实现,中间有5个地方缺失,请阅读程序后将它们补上。

的值在〈limits •h>中

//图的顶点数,应由用户定义

//用二维数组作为邻接矩阵表示

//生成树的边结点

//边的起点与终点

//边上的权值

//最小生成树定义

//从顶点rt 出发构造图G 的最小生成树T ,rt 成为树的根结点

//初始化最小生成树

T

//依次求MST 的候选边

//遍历当前候选边集合

//选具有最小权值的候选边

//图不连通,出错处理

//修改候选边集合

【答案】(1)(0,3,1); (3,5, 4); (5,2,2); (3,1, 5); (1,4,3) (2)①T[k]; tovex=i②min=Maxint③mispos=i④exit (O )⑤T[i]; fromvex=v

【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V,E}是连通图

,是N

上最小生成树边的集合。算法从属于

为止。

2. 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

3. 有五个数据依次入栈:1,2, 3, 4, 5。在各种出栈的序列中,以3, 4先出栈的序列有_____。(3在4之前出栈)

【答案】3个

【解析】以3, 4先出栈的序列有34521、34215、34251共3个。

4. 对于给定的元素,可以构造出的逻辑结构有_____,_____,_____,_____四种。

【答案】集合;线性结构;树形结构;图状结构(网状结构)

5. 假定有k 个关键字互为同义词,若用线性探测再哈希法把这k 个关键字存入哈希表中,至少要进行_____次探测。

【答案】的次数最小。总次数为

6. 线性表

【答案】(n -1)/2

【解析】删除第一个元素需要移动n -i 次,以此类推,删除最后一个元素需要移动0次。平 均次数为

7. 在有n 个顶点的有向图中,每个顶点的度最大可达。

【答案】2(n-l )

【解析】当有向图为完全连通图时每个顶点的度达到最大,出度入度均为n-1。

E T 开始,重复执行下述操作:在所有u 属于

加入集合

同时将

并入

v

直到

的边(u ,v )属于E

中找一条代价最小的边

用数组表示,假定删除表中任一元素的概率相同,则删除一个元素

【解析】当该关键字发生冲突时,用线性探测不会遇到别的关键字冲突,这个时候需要探测

平均需要移动元素的个数是_____。

8. 若用n 表示图中顶点数目,则有_____条边的无向图成为完全图。

【答案】n (n-l )/2

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边,即为n (n-l )。又因为每条边重复出现两次,所有无向完全图的边数为n (n-l )/2。

9. 己知有序表为(12,18,24,35,47,50,62,83,90,115,134)当用二分法查找90时,需_____次查找成功,查找47时_____成功,查找100时,需_____次才能确定不成功。

【答案】2;4;3

【解析】二分法查找元素次数列表

找100是找到115就停止了。

10.无用单元是指_____,例_____

【答案】用户不再使用而系统没有回收的结构和变量;

二、选择题

11.在任意一棵非空二叉排序树T1中,删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中,正确的是( )

I. 若v 是T1的叶结点,则T1与T3不同 II. 若v 是T1的叶结点,则T1与T3相同 III. 若v 不是T1的叶结点,则T1与T3不同 IV. 若v 不是T1的叶结点,则T1与T3相同 A. 仅 I 、III B .仅 I 、IV C. 仅 II 、III D. 仅 II 、IV 【答案】C

【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中,如果删除的结点是叶子结点那么在插入结点后,后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点,那么再插入这个结点后,后来的二叉树可能发生变化,不完全相同。

12.已知广义表用和数取出LS 中原子e 的运算是( )。

【答案】C