2018年北京大学深圳研究生院907计算机专业基础之数据结构考研仿真模拟五套题
● 摘要
目录
2018年北京大学深圳研究生院907计算机专业基础之数据结构考研仿真模拟五套题（一） ... 2 2018年北京大学深圳研究生院907计算机专业基础之数据结构考研仿真模拟五套题（二） ... 9 2018年北京大学深圳研究生院907计算机专业基础之数据结构考研仿真模拟五套题（三） . 14 2018年北京大学深圳研究生院907计算机专业基础之数据结构考研仿真模拟五套题（四） . 19 2018年北京大学深圳研究生院907计算机专业基础之数据结构考研仿真模拟五套题（五） . 27
第 1 页，共 35 页
一、算法设计题
1． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。
【答案】算法如下:
//head是带头结点的单链表的头指针
//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间
//循环到仅剩头结点
//pre为元素最小值结点的前驱结点的指针
//P为工作指针
//记住当前最小值结点的前驱
//输出元素最小值结点的数据
//删除元素值最小的结点，释放结点
空间
//释放头结点
2． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
第 2 页，共 35 页
) 小元素。
在后半部分继续进行划分
在前半部分继续进行划分
3． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:
(1)如果单词重复出现，则只在链表上保留一个。
(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。
【答案】定义结点数据类型如下:
//频度域，记单词出现的次数
//maxsize是单词中可能含有的最多字母个数
(1)算法如下:
（ ）
//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//p是工作指针，pre 是前驱指针
//单词重复出现，频度增
1
//指针后移
//该单词没出现过，应插入
//将新结点插入到链表最后
//结束for 循环
//结束creat 算法 (2)算法如下:
（ ）
//建立有n 个单词的单向链表，重复单词只在链表中保留一个，最后输出频度最高的k 个单词
第 3 页，共 35 页
其中n 表示随后输入英语单
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//P是工作指针，pre 是前驱指针
//单词重复出现，频度增
1
//先将P 结点从链表上摘下，再按频度域值插入到合适位置
//将P 结点插入到合适位置
//指针后移
//该单词没出现过，应插入到链表最后
//if新结点插入
//结束for 循环建表
r
(输入要输出单词的个数
//输出频度最髙的k 个单词
(”第
//结束算法
4． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
第 4 页，共 35 页
) ；
个单词出现次\n”，++i，p ﹣＞data ，p ﹣＞freg) ；
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
相关内容
相关标签