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

2018年五邑大学计算机学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题

  摘要

一、算法设计题

1. 已知某哈希表HT 的装填因子小于1,哈希函数H(key)为关键字的第一个字母在字母表中的序号。

(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。

(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意,此算法中规定不能用公式直接求解计算。

【答案】(1)算法如下:

按关键字第一个字母在字母表中的顺序输出各关键字

哈希地址

1~26

设哈希表初始值为

null

取关键字第一字母在字母表中的序号

(2)算法如下:

求链地址解决冲突的哈希表査找不成功时平均査找长度

记査找不成功的总的次数

按我们约定,査找不成功指到空指针为止

2. 已知两个线性表A , B 均以带头结点的单链表作存储结构,且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ,要求C 另开辟存储空间。,并同样以元素值的递增有序的单链表形式存储。

【答案】算法如下:

-

//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间

//pa、pb 是两链表的工作指针

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

3. 试设计一个C 语言算法(或C 语言程序) :用单链表做存储结构,以回车符为结束标志,输入一个任意长度的字符串,然后判断该字符串是否为“回文”(正向读和反向读时,串值相同的字符串称为“回文”) ,输出信息“Yes ”或“NO ”;最后删除字符串并释放全部空间。例如:

若输入“ABCD12321DCBA”是回文,则输出“Yes”; 若输入“ABCD123DCBA”,不是回文,则输出“NO”。

要求:定义相关数据类型,不得使用数组(顺序表) 做字符串的存储结构和辅助存储空间。假定字符串的长度为n ,试分析上述算法的时间复杂度。

【答案】算法如下:

//本算法判断数据域为字符且长为n 的单链表是否是”回文" ,返回1或0表示成功或失败

//字符栈,容量足够大

//设链表带头结点

//前一半字符入栈,链表指针后移

//若链表有奇数个结点,则跳过中间结点

//不是回文

4. 编写算法,将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。

【答案】算法如下:

//将自然数

,按" 蛇形M 填入n 阶方阵A 中

//i,j 是矩阵元素的下标,k 是要填入的自然数

//从右上向左下填数

//副对角线及以上部分的新i ,j 坐标

//副对角线以下的新的i ,j 坐标

//从左下向右上

//最外层

while

5. 有二叉排序树采用二叉链表方式存放,树中结点值各不相同,欲得到一个由大到小的结点值递减序列,简述处理方法思路,用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈,容量足够大

沿右子树向下

结束

二、应用题