2018年西安交通大学软件学院820计算机软件基础(含数据结构、程序设计)之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 己知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序(非降序) 并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。
例如:
第一个数组为:4，12，28 第二个数组为:1，7，9，29，45 输出结果为:
第一个数组
第二个数组
【答案】算法如下:
//A和B 是各有m 个和n 个整数的非降序数组，本算法将B 数组元素逐个插入到A 中 //使A 中各元素均不大于B 中各元素，且两数组仍保持非降序排列
.
" 交换A[m﹣1]和
B[0]
//寻找A[m﹣1]的插入位置
//寻找B[0]的插入位置
算法结束
2． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
【答案】算法如下:
第 2 页，共 39 页
在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，
将其
插入到二叉排序树中
f 指向当前结点的査找值为x 的结点，
双亲
无值为x 的结点，插入之
査询成功，值域为x 的结点的count 增
1
3． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。
(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。
(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。
【答案】(1)算法如下:
按关键字第一个字母在字母表中的顺序输出各关键字
哈希地址
1~26
设哈希表初始值为
null
取关键字第一字母在字母表中的序号
(2)算法如下:
求链地址解决冲突的哈希表査找不成功时平均査找长度
记査找不成功的总的次数
按我们约定，査找不成功指到空指针为止
第 3 页，共 39 页
-
4． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
) 区分在遍
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
向左
向右
访问根结点
找被访问结点的双亲
结束
5． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径
。
设有向图有n 个顶点
判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径
是队列，容量足够大，元素是顶点编号
人队
到顶点
不存在路径
第 4 页，共 39 页
【答案】算法如下: