2018年北京市培养单位空间应用工程与技术中心864程序设计之数据结构考研核心题库
● 摘要
一、算法设计题
1. 设键盘输入n 个英语单词,输入格式为词个数,试编一程序,建立一个单向链表,实现:
(1)如果单词重复出现,则只在链表上保留一个。
(2)除满足(1)的要求外。链表结点还应有一个计数域,记录该单词重复出现的次数,然后输出出现次数最多的前k(k<=n) 个单词。
【答案】定义结点数据类型如下:
//频度域,记单词出现的次数
//maxsize是单词中可能含有的最多字母个数
(1)算法如下:
( )
//建立有n(n>0) 个单词的单向链表,若单词重复出现,则只在链表中保留一个
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//p是工作指针,pre 是前驱指针
//单词重复出现,频度增
1
//指针后移
//该单词没出现过,应插入
//将新结点插入到链表最后
//结束for 循环
//结束creat 算法
第 2 页,共 41 页
其中n 表示随后输入英语单
(2)算法如下:
( )
//建立有n 个单词的单向链表,重复单词只在链表中保留一个,最后输出频度最高的k 个单词
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//P是工作指针,pre 是前驱指针
//单词重复出现,频度增
1
//先将P 结点从链表上摘下,再按频度域值插入到合适位置
//将P 结点插入到合适位置
//指针后移
//该单词没出现过,应插入到链表最后
//if新结点插入
//结束for 循环建表
r
(输入要输出单词的个数
//输出频度最髙的k 个单词
(”第
//结束算法
2. 已知指针P 指向带表头的中根次序线索二叉树中的某结点,试写一算法FFA(P,q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG,LLINK ,INFO , RL1NK ,RTAG) ,且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下:
第 3 页,共 41 页
) ;
个单词出现次\n”,++i,p ﹣>data ,p ﹣>freg) ;
在中序线索树t 上,求结点p 的双亲结点q
暂存
找P 的中序最右下的结点
顺右线索找到q 的后继(P的袓先结点
)
若后继是头结点,则转到根结点
根结点无双亲
找最右结点的过程中回找到
P
结束FFA
3. 设有一个数组中存放了一个无序的关键序列
【答案】算法如下:
4. 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针,用它来指出结点排序后的逻辑顺序地址。设
用
表示辅助地址表。初始时
减序) 算法的语句序列。
【答案】算法如下:
一趟排序无交换发生,结束
表示n 个结点的值,用
,在排序中,凡需对结点交换就用它的地址
。现要求将K n 放在将元素排序后
准备到左子树中找
P
的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n(注:用程序实现) 。
来进行。例如当n=3时,对K(31,11,19) 则有T(2,3,1) 。试编写实现辅助地址表排序(按非递
第 4 页,共 41 页