2018年北京市培养单位工程管理与信息技术学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)
【答案】算法如下:
待排序记录的个数
关键字由d 个分量组成
静态链域
记录的其他数据域
存放n 个记录
.
用队列表示桶，共m 个
进行基数排序，返回收集用的链头指针
将
进行d 趟排序
初始化桶
按关键字的第j 个分量进行分配
k 为桶的序号
将将
链到桶头
链到桶尾
链成一个静态链表
将初始链表的终端结点指针置空，P 指向链表的第一个结点
队列的头、尾指针
对
修改桶的尾指针
扫描下一个记录
找第一个非空的桶
为收集链表的头指针，t 为尾指针
连接非空桶
本趟收集完毕，将链表的终端结点指针置空
2． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。
(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。
(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。
【答案】(1)算法如下:
按关键字第一个字母在字母表中的顺序输出各关键字
哈希地址
1~26
设哈希表初始值为
null
取关键字第一字母在字母表中的序号
(2)算法如下:
求链地址解决冲突的哈希表査找不成功时平均査找长度
记査找不成功的总的次数
按我们约定，査找不成功指到空指针为止
3． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
-
满足下述性质
:
当且仅当存在某个顶点
且
22
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
4． 假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下:
//s和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作成功返回1，否则返回0表示失败
//检査参数及置换后的长度的合法性
//若S 串被替换的子串长度小于t 串长度，则S 串部分右移
//S串中被替换子串的长度小于t 串的长度
//将t 串复制到S 串的适当位置
//算法结束
//本算法是串的置换操作，将串S 中所有非空串t 相等且不重叠的子串用V 代替
//判断S 是否有和t 相等的子串
//串S 中包含和t 相等的子串
//creat操作是将串常量(此处为空串) 赋值给
temp
//求串t 和s 的长度
//用串v 替换t 形成部
分结果
//将串s 中串后的部分形成新的s 串
//求串s 的长度
相关内容
相关标签