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

一、算法设计题

1． 设要求按

是一个记录构成的数组，

是一个整数数组，其值介于1〜100之间，现

的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]

中去。规定可使用的附加空间为O(1)。

【答案】算法如下:

//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序

//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整

//B[j]和B[k]交换

//r0是数组A 的元素类型，A[j]和A[k]

交换

//完成了一个小循环，第i 个已经安排好

//算法结束

2． 设排序二叉树中结点的结构为下述三个域构成:

Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。

【答案】算法如下:

非递归删除以r 为根的二叉排序树

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

沿左分枝向下

出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间

在二叉排序树T 中删除所有小于等于x

的结点

根结点的值小于等于

x

删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止

沿根结点左分支向下，査小干等于x 的结点

q 记P 的双亲

结点的值小于等于

x

再査原P 的右子树中小于等于x 的结点

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

试写出判断表达式中括号

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

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

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

//top用作栈顶指针

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

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

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

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

4． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)

【答案】算法如下:

//L是带头结点的单链表，本算法删除其最小值结点

//P为工作指针。指向恃处理的结点。假定链表非空

//pre指向最小值结点的前驱

//q指向最小值结点，初始假定第一元素结点是最小值结点

//查最小值结点

//指针后移

//从链表上刪除最小值结点

//释放最小值结点空间

//结束算法Delete

5． 写出一趟快速排序算法。

【答案】算法如下:

一趟快速排序算法，枢轴记录到位，并返回其所在位置

二、应用题

6． 一个循环队列的数据结构描述如下:

给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？

【答案】(1)队空:

//设s 是sequeuetp 类型变量