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

2017年上海市培养单位上海生命科学研究院864程序设计之数据结构考研强化模拟题

  摘要

一、填空题

1. 在一个具有n 个单元的顺序栈中,假定以地址高端(即下标为n 的单元)作为栈底,以top 作为栈顶指针,则当向栈中压入一个元素时,top 的变化是top=_____。

【答案】

【解析】由于栈底在地址高端,栈中压入一个元素时,栈顶向地址底端移动一个单位,

所以

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

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

3. 建立索引文件的目的是_____。

【答案】提高查找速度 4. 假定查找有序表

【答案】37/12

【解析】折半查找时每个的次数如表所示:

平均查找次数为

5. 在二叉树中,指针p 所指结点为叶结点的条件是_____。

【答案】

【解析】叶子节点的左右孩子都不存在。

6. 应用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

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

为止。

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

属于

加入集合

同时将

并入

v

直到

的边(u ,v )属于E

中找一条代价最小的边

7

求REPLACE (S ,V , m )=_____。

【答案】

表示,两栈顶指针为

8. 当两个栈共享一存储区时,栈利用一维数组当栈1空时

【答案】

为_____,栈2空时

为_____,栈满时为_____。

【解析】共享栈的栈底在共享存储区的两端,当栈满时栈顶相邻。

9. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接,请填空完善之。

【答案】(1)(2)

链表未到尾就一直进行

将当前结点作为头结点后的第一元素结点插入

10.如某二叉树有20个叶结点,有30个结点仅有一个孩子,则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。

11.设m 、n 均为自然数,m 可表示为一些不超过n 的自然数之和,f (m , n )为这种表示方式的 数目。例f (5, 3)=5,有5种表示方式:3+2, 3+1+1,2+2+1,2+1+1+1, 1+1+1+1+1。

①以下是该函数的程序段,请将未完成的部分填入,使之完整。

②执行程序,f (6,4)=_____。 【答案】①1; 1; f (m ,n -1); n ②9