一、判断题（每题2分，共10分）。
1. 线性表的逻辑顺序与物理顺序总是一致的。 （×）
2. 堆排序是不稳定的排序方法。 （√ ）
3. 在非空二叉树中，任一结点均有两棵二叉树。 （ × ）
4. 一个无序的元素序列可以通过构造一棵二叉排序树而变成一个有序的元素序列。（√）
5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（√ ）
二、单项选择题（每题2分，共10分）
1. 表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素需要移动元素的平均次数为（ D ），删除一个元素需要移动元素的平均次数为（A ）。
A. (n-1)/2 B. n C. n-1 D. n/2
2. 对于一个头指针为L的带头结点的单链表，判定该表为空表的条件是（ B ）。
A. L=NULL; B. L->next=NULL; C. L->next==L; D. L!=NULL;
3. 以下数据结构中，（ A ）是非线性数据结构。
A. 树 B. 字符串 C. 数组 D. 栈
4. 对线性表进行折半查找时，要求线性表必须（C）。
A.以顺序方式存储。
B.以链式方式存储。
C.以顺序方式存储，且结点按关键字有序排序。
D.以链式方式存储，且结点按关键字有序排序。
5. 在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ D）。
A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序
三、填空题 （每小题2分，共10分）
1. 在内部排序中，平均比较次数最少的是 快速排序 ，要求附加的内存容量最大的是归并排序。
2. 由n个权值构成的哈夫曼树共有 2n-1 个结点。
3. 在单链表中，除首元结点外，任一结点的存储位置由其直接前趋结点的链域指示。
3. 栈结构允许进行删除操作的一端称为栈的栈顶 。
4. 设GetHead(p)为求广义表p的表头函数，GetTail(p)为求广义表p的表尾函数。其中( )是函数符号，运算GetTail(GetHead((a,b),(c,d)))的结果是 (b) 。
四、简答题 （每题7分，共42分）
1. 单链表的存储结构为
typedef struct LNode {
　ElemType data;
　struct LNode *next ; //结点后继指针
｝LNode, *LinkList;
已知L是带表头结点的非空单链表，且p结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列，以实现删除p结点的语句序列 (4)(7)(3)(1)(9) 。
(1) p->next=p->next->next; (2) p=p->next->next;
(3) while(p->next!=q) p=p->next; (4) q=p;
(5) while(p->next->next!=q) p=p->next;
(6) q=p->next; (7) p=L;
(8) L=L->next; (9) free (q);
2. 已知一个栈S的输入序列为abcd , 能否通过栈的Push和Pop操作输出序列cbda；如果能，请写出操作序列；如果不能，请说明原因。
答： 能。Push(S, a), Push(S, b), Push(S, c), Pop(S, c), Pop(S, b), Push(S, d), Pop(S, d), Pop(S, a)
3. 已知一棵二叉树的中序遍历序列为CDBAEGF, 先序遍历序列为ABCDEFG，试问能不能唯一确定一棵二叉树，若能，请画出该二叉树。
答：（1）由中序遍历序列和先序遍历或中序遍历和后序遍历序列可以唯一确定一棵二叉树。基本思想是前序（后序）定根，中序分左右。
对于给定的先序和中序序列，可确定根结点为A,以A为根的左子树结点为B,C,D,右子树结点为E,F,G。进一步确定所有子树的根结点，因而也就确定了整个二叉树。对应的二叉树如附图2 所示。

4. 已知一个有向图和该图的邻接表如图1所示，并依此邻接表进行从顶点a开始出发的深度优先遍历，画出由此得到的深度优先生成树。

答：DFS生成树如附图下图所示。

6. 已知序列(12,18,4,3,6,13,2,9,19,8)。请给出采用希尔排序对该序列作升序排序的第一趟结果（初始步长为5）。
答： (12,2,4,3,6,13,18,9,19,8)
五、算法设计题(第1，2题每题10分，第3题8分，共28分)
1. 下面是一个二叉树中序遍历的非递归算法，请在 处填上适当内容，使其成为一个完整算法。
Status Inorder (BiTree T,Status(*Visit)(TElemType e) )
　　InitStack (S); Push (S, T);
　　while ( (1) ) {
　　　while (GetTop (S, p) && p) Push (S, (2) );
　　　Pop (S, p);
　　　if (!StackEmpty (S)) {
　　　　Pop (S, p)； if(!visit(p->data)) return ERROR;
　　　　Push (S, (3) ) ;
　　　} //if
　　} //while
　　return OK;
}
注： typedef struct BiTNode {
　　　　TEelemType data;
　　　　struct BiTNode *lchild,*rchild;//左右孩子指针
　　} BiTNode, *BiTree ;


答：　 (1) !Stackempty(S)
　　　(2) p->lchild
　　　(3) p->rchild
2. 下面是一个快速排序的划分算法，请在 处填上适当内容，使其成为一个完整算法。
int Partition(SqList *L,int low,int high){
　　//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并
　　//返回其所在位置，此时在它之前（后）的记录均不大（小）于它。
　　L.r[0]=L.r[low];
　　pivotkey=L.r[low].key;
　　while(（1）){
　　　while(low<high && L.r[high].key>=pivotkey) （2）;
　　　L.r[low]=L.r[high];
　　　while(low<high && L.r[low].key<=pivotkey) ++low;
　　　L.r[high]=L.r[low];
　　}
　　L.r[low]=（3）;
　　return low;
}//Partition
答：（1） low< high
　　（2）- -high
　　（3） L.r[0]
3. 编写将栈S中所有值为e的数据元素删除的算法。
Status algo2 (Stack &S, int e) {
　　Stack &T; int d;
　　while (! StackEmpty(S)) {
　　　Pop(&S, &d);
　　　if (d!=e) Push(&T,d);
　　}
　　while(!StackEmpty(T)) {
　　　Pop(&T,&d);
　　Push(&S,d);　　
　　}
}