2018年河北师范大学信息技术学院833数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1. 请运用快速排序思想,设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
在后半部分继续进行划分
在前半部分继续进行划分
2. 编写算法,将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。
) 小元素。
图
【答案】算法如下:
//将自然数
,按" 蛇形M 填入n 阶方阵A 中
//i,j 是矩阵元素的下标,k 是要填入的自然数
//从右上向左下填数
//副对角线及以上部分的新i ,j 坐标
//副对角线以下的新的i ,j 坐标
//从左下向右上
//最外层
while
3. 已知非空双向链表由d 指出,结点结构为(llink,data ,rlink) ,请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。
【答案】算法如下:
//d是循环链表,本算法将链表中数据域值最大的结点移至链表的最前面
//设链表有头结点
//q指向待处理结点
//P记数据域值最大的结点
//将P 摘下
//插人P 结点
4. 已知无向图采用邻接表存储方式,试写出删除边(i, j) 的算法。
【答案】算法如下:
在用邻接表方式存储的无向图g 中,删除边(i,
j)
删顶点i 的边结点(i, j) , pre 是前驱指针
释放空间
沿链表继续査找
删顶点j 的边结点(j,
i)
释放空间
沿链表继续査找
5. 设给定关键字输入序列为(100,90,120,60,78,35,42,31,15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数;冲突时用链表法解决,写出哈希算法,并构造出哈希表,在等概率查找情况下查找成功的平均查找长度是多少?
【答案】算法如下:
关键字
链指针
用链地址法解决冲突,构造哈希表,哈希函数用
初始化
输入n(本例中n=9)
个关键字按题意x 互不相同
4等插入结点链入同义词表
构造的哈希表如图所示:
图构造的哈希表
查找成功时的平均查找长度
。
二、应用题
相关内容
相关标签