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

一、算法设计题

1． 结点类型和存储结构如下:

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

【答案】算法如下:

对存储在数组R 中的记录进行排序

初始化

设R[0]作监视哨，Max 是该类型最大元

素

初始假定第一个元素有序

前驱

第一个元素

査找第i 个元素的序号

将笫i 个元素链入静态链表

2． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。

【答案】算法如下:

//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间

//pa、pb 是两链表的工作指针

//监视哨

//pa指针后移

第 2 页，共 34 页

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

3． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。

【答案】算法如下:

//rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾

//申请结点空间

//将s 结点链入队尾

//rear指向新队尾

//rear是带头结点的循环链队列的尾指针

//本算法执行出队操作，成功输出队头元素；否则给出出错信息

//s指向队头元素

//队头元素出队

//空队列

4． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，

试写出判断表达式中括号

是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:

//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配

//s是一维数组，容量足够大，是用于存放括号的栈

//top用作栈顶指针

第 3 页，共 34 页

//'#先入栈，用于和表达式结束符号'#'匹配

//字符数组E 的工作指针

//逐字符处理字符表达式的数组

//读人其他字符，不进行处理

5． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。

(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。

【答案】(1)满足条件的二叉树如下:

(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:

全局变量

从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .

中序遍历右子树

叶结点

中序遍历左子树

二、应用题

6． 如果两个串含有相等的字符，能否说它们相等？

【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同(即两串串值相等) 。

7． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？

【答案】不一定相邻。哈希地址为同义词，都争夺哈希地址i 。

第 4 页，共 34 页

的关键字，和为解决冲突形成的探测序列f 的