2018年安徽农业大学信息与计算机学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)
【答案】算法如下:
//L是带头结点的单链表，本算法删除其最小值结点
//P为工作指针。指向恃处理的结点。假定链表非空
//pre指向最小值结点的前驱
//q指向最小值结点，初始假定第一元素结点是最小值结点
//查最小值结点
//指针后移
//从链表上刪除最小值结点
//释放最小值结点空间
//结束算法Delete
2． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。
【答案】算法如下:
利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成
树
数组存放生成树
数组存放顶点是否找到最短路径
初始化, 设顶点信息就是编号
从v0开始，求其最小生成树
是尚未到最小生成树的顶点的集合
循环n －1次
顶点u 已找到最短路径下，下面修改相关顶点的最短路径
算法结束
3． 二路插入排序是将待排关键字序列二路插入。编写实现2-路插入排序算法。
【答案】算法如下:
二路插入排序的算法
辅助存储
插人后部
折半査找插入位置
移动元素
插入有序位置
插入前部
移动元素
将序列复制回去
4． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
【答案】算法如下:
中关键字分二路分别按序插入到辅助向量
前半部和后半部(注.. 向量d 可视为循环表) ，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分
在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，
将其
插入到二叉排序树中
f 指向当前结点的査找值为x 的结点，
双亲
无值为x 的结点，插入之
査询成功，值域为x 的结点的count 增
1
5． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N
的二叉树的存储结构。
和
分别指示结点i 的左儿子和右儿子，
，使
) 表示i 的左(右) 儿子为空。试写一个
存放结点i 的父亲；然后再写一个判别结点u 是否
算法，由L 和R 建立一个一维数组为结点V 的后代的算法。
【答案】算法如下:
和
是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组
T 数组初始化
若结点i 的左子女是则结点L 的
双亲是结点
i
若结点i 的右子女是R , 则R 的
双亲是
i
判断U 是否是V 的后代
本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代
二、应用题