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

一、算法设计题

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

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

【答案】算法如下:

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

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

沿左分枝向下

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

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

的结点

根结点的值小于等于

x

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

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

q 记P 的双亲

结点的值小于等于

x

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

2． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。

【答案】算法如下:

//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反

//空链表

//奇数序号结点在L1中

//偶数序号

结点逆置插入到L2中

//置L1

表尾

3． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。

【答案】算法如下:

//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表 //本算法将元素x 插入到线性表中，并保持线性表的有序性

//题目要求下标从1开始

//对分査找元素x 的插入位置

//元素后移

//将元素x 插人

算法结束

设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。

时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。

4． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。

【答案】算法如下:

从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树

申请结点空间

结点赋值，其线

索初始化

查找结点的插入位置

f 是P 的双亲

根结点

左子女

修改线索

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

修改线索

读入下个数

算法结束

，

，那么left 域中存放的是该结点的按中

，那么right

域中存放的是该结点的右儿子结点的地址。

，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。