当前位置：问答库＞考研试题

一、算法设计题

1． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。

【答案】算法如下:

L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符

//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表

//建立三个链表的头结点

//置三个循环链表为空表

//分解原链表

//L指向待处理结点的后继

//处理字母字符

//处理数字字符

//处理其他符号

//结束while(L!＝

null) //算法结束

2． —个有向图G=(V，E) 的平方图

，使得表示。

【答案】算法如下:

第 2 页，共 34 页

满足下述性质

:

2

当且仅当存在某个顶点

2

且

。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表

3． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组

【答案】算法如下:

本句的有无不影响査找结果

4． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈，容量足够大

沿右子树向下

结束

5． 对给定关键字序号j(1

中找到关键字从小到大排在第j 位上的记

中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not

find ”信息。请编写出算法并简要说明算法思想。

录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。

例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下；

第 3 页，共 34 页

在后半部分继续进行划分

在前半部分继续进行划分

二、应用题

6． 一个ISAM 文件除了主索引外，还包括哪两级索引？

【答案】ISAM 文件有三级索引:磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引——主索引。故还包括的两级索引是盘组和磁道。

7． 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和, 给定一棵二叉树T , 采用二叉链表存储, 节点结构为:

其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针, 设计求T 的WPL 的算法。要求:

(1)给出算法的基本设计思想; (2)使用C 或

语言, 给出二叉树结点的数据类型定义;

语言描述算法, 关键之处给出注释。

(3)根据设计思想, 采用C 或

【答案】(1)算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度, 如果当前节点不是叶子节点, 那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和, 对于此函数要传入一个当前节点的树高的形参, 那么递归调用孩子节点时只需要将这个形参加一即可。

(2)typedef struct BiNode

(3)具体算法实现如下:

如果当前节点为空节点

第 4 页，共 34 页