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

一、算法设计题

1． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。

【答案】算法如下:

在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置

否则返回-1表示失败

元素序号

结束

，查找失败的平均查找

期望值分析:在等概率情况下，则查找成功的平均查找长度为等，则查找成功时和关键字比较的个数的期望值约为

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

。

长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相

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

【答案】算法如下:

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

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

沿左分枝向下

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

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

的结点

根结点的值小于等于

x

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

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

q 记P 的双亲

结点的值小于等于

x

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

3． 设有一个数组中存放了一个无序的关键序列

【答案】算法如下:

4． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回

//在类C 中，一维数组下标从零开始

。现要求将K n 放在将元素排序后

的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。

//两串相等

//算法结束

5． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)

【答案】算法如下:

以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序

树

在调用时，

T=null

f 是P 的双亲

申请结点空间

根结点

左子女

右子树根结点的值大于等于根

结点的值

算法结束

中，试写出依次取A 中各值

构造一棵二叉排序

二、应用题

6． 简述广义表属于线性结构的理由。

【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性:在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。

7． 假定在一个8位字长的计算机中运行下列C 程序段:

若编译器编译时将8个8位寄存器R1〜R8分别分配给变量x 、y 、m 、n 、z1、Z2、k1和k2。请回答下列问题。(提示:带符号整数用补码表示)