当前位置:问答库>考研试题

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 页