2018年西南财经大学经济信息工程学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
2． 试设计一个C 语言算法(或C 语言程序) :用单链表做存储结构，以回车符为结束标志，输入一个任意长度的字符串，然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”) ，输出信息“Yes ”或“NO ”；最后删除字符串并释放全部空间。例如:
若输入“ABCD12321DCBA”是回文，则输出“Yes”； 若输入“ABCD123DCBA”，不是回文，则输出“NO”。
要求:定义相关数据类型，不得使用数组(顺序表) 做字符串的存储结构和辅助存储空间。假定字符串的长度为n ，试分析上述算法的时间复杂度。
【答案】算法如下:
//本算法判断数据域为字符且长为n 的单链表是否是”回文" ，返回1或0表示成功或失败
//字符栈，容量足够大
第 2 页，共 36 页
树中的所有叶结点链成带头结点的双链表
当前叶结点链入双链表
//设链表带头结点
//前一半字符入栈，链表指针后移
//若链表有奇数个结点，则跳过中间结点
//不是回文
3． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为
【答案】算法如下:
从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素
，其中，2为排序树中所含结点数，m 为输出的关键字个数。
4． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。
【答案】算法如下:
（ ）
//统计输入字符串中数字字符和字母字符的个数
//初始化
//’#’表示输入字符串结束
'//数字字符
//字母字符
//输出数字字符的个数
("数字％d 的个数＝
//求出字母字符的个数
("字母字符％c 的个数＝
//算法结束。
第 3 页，共 36 页
) ；
) ；
5． 对给定关键字序号j(1 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 二、应用题 6． 将关键字序列(7，8，30，11，18，9，14) 散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组. 散列函数是:H(key)＝(key×3)M0D7，处理冲突采用线性探测再散列法，要求装填(载）因子为 . (1)请画出所构造的散列表. (2)分别计算等概率情况下查找成功和查找不成功的平均查找长度. 【答案】(1) 要求装填因子为列函数值如下表: 采用线性探测法再散列法处理冲突，所构造的散列表为: (2)查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示: 故查找成功的平均查找长度为(1+1+1+1+3+3+2)/7＝12/7. 第 4 页，共 36 页 ，数组的长度应该为数组下标为0〜9. 各关键字的散
相关内容
相关标签