数据结构自考2012年1月真题及答案解析

阅读下列算法，并回答下列问题：

(1)该算法采用的是何种排序方法?

(2)算法中的R[n+1]的作用是什么?

假设以单链表表示线性表，单链表的类型定义如下：

typedef struct node {

DataType data;

Struct node *next;

} LinkNode，* LinkList;

编写算法，在一个头指针为head且带头结点的单链表中，删除所有结点数据域值为x的结点。函数原型为：LinkList delnode (LinkList head，DataType x)

阅读下列算法，并回答下列问题：

(1)简述该算法的功能;

(2)写出分别输入字符串："abcba"和"abcbde"，调用算法函数的返回值。

阅读下列算法，并回答下列问题：

(1)简述该算法中标号s1所指示的循环语句的功能;

(2)简述该算法中标号s2所指示的循环语句的功能。

下列算法是利用二分查找方法在递减有序表R中插入元素x，并保持表R的有序性。请在空缺处填入适当的内容，使其成为一个完整的算法。

已知如图所示的带权无向图，请画出用普里姆算法从顶点1开始的最小生成树的构造过程。

已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，请画出此二叉树，并给出后序遍历序列。

对关键字序列(26，18，60，14，7，45，13，32)进行降序的堆排序，写出构建的初始堆(小根堆)及前两趟重建堆之后序列状态。

设散列函数为H (key)=key % 11，散列地址空间为0··10，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探查法解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。

一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为______。