2018年北京市培养单位空间应用工程与技术中心862计算机学科综合(非专业)之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。
(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。
(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。
【答案】(1)算法如下:
按关键字第一个字母在字母表中的顺序输出各关键字
哈希地址
1~26
设哈希表初始值为
null
取关键字第一字母在字母表中的序号
(2)算法如下:
求链地址解决冲突的哈希表査找不成功时平均査找长度
记査找不成功的总的次数
按我们约定，査找不成功指到空指针为止
2． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
第 2 页，共 34 页
-
以后序遍历算法求以二叉树表示的算术表达式的
值
.
3． 输入一个字符串，内有数字和非数字字符，如:akl23x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a 中，例如123放入a[0]，456放入a[l]，...... 。编程统计其共有多少个整数，并输出这些数。
【答案】算法如下:
（ ）
//从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数
//整数存储到数组a ，i 记整数个数
//从左到右读入字符串
//'#'是字符串结束标记
//是数字字符
//数初始化
//拼数
//若拼数中输入了’#’，则不再输入
//输入非数字且非#时，继续输入字符
("共有
个整数，它们是:
)
求左子树表示的子表达式的值
求右子树表示的子表达式的值
//每10个数输出在一行上
//算法结束
第 3 页，共 34 页
4． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
5． 设记录
的关键字为
。
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
到:_
小数
设置T 中" 败者" 的初值
依次从
出发调整败者
为完全二叉树T 的叶结点，本算法建立败者树
是与题中要求的关键字类型相同的机器最
的双亲结点
二、应用题
6． 用单链表保存m 个整数, 节点的结构为(data, link) , 且余绝对值相等的节点。
例如若给定的单链表head 如下表
表
(n为正整数) 。现要求设计一个
时间复杂度尽可能高效地算法, 对于链表中绝对值相等的节点, 仅保留第一次出现的节点而删除其
第 4 页，共 34 页