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
相关内容
相关标签