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

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等插入结点链入同义词表

构造的哈希表如图所示:

图构造的哈希表

查找成功时的平均查找长度

二、应用题