数据结构选择题及答案

一、选择题

1、下列查找方法中，（）适用于查找有序单链表。
A．分块查找; B．哈希查找; C．顺序查找; D．二分查找;
2、在有n个结点的二叉树的二叉链表表示中，空指针数为( )。
A．不定; B．n+1; C．n; D．n-1;
3、在下列排序方法中，（）方法所有情况下时间复杂度均为O(nlogn)。
A．希尔排序; B．堆排序; C．快速排序; D．直接插入排序;
4、设有一个nn的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么对角元素A[i][i]存放于B中（）处。
A. (i+3)*i/2 B. (i+1)*i/2
C. (2n-i+1)*i/2 D. (2n-i-1)*i/2
5、已知一组待排序的记录关键字初始排列如下：45,34,87,25,67,43,11,66,27,78。快速排序法一趟排序的结果为（）。
A．34,45,25,67,43,11,66,27,78,87 B．87,45,11,25,34,78,27,66,67,43
C．27,34,11,25,43,45,67,66,87,78 D．34,11,27,25,43,78,45,67,66,87
6、若某二叉树有15个叶子结点，有15个结点仅有一个孩子，则该二叉树的总结点数是( )。
A. 42 B. 44 C. 45 D. 46
7、设n个元素进栈序列是x1，x2，x3，…，xn，其输出序列是1，2，3，…，n，若x3=3，则x1的值( )。
A. 可能是2 B. 不可能是1 C. 一定是2 D. 一定是1
8、在一个单链表中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。。
A. p=q; p->next=q; B. p->next=q; q->next=p;
C. p->next=q->next; p=q; D. q->next=p->next; p->next=q;
9、串"aababaabacab"的next数组为( )
A. 011212345123 B. 012112345123
C. 012121234512 D. 012341123412
10、对下图所示的无向图，从顶点1开始进行深度优先遍历；可得到顶点访问序列是（）
在这里插入图片描述

A.1 2 4 3 5 7 6 B.1 2 4 3 5 6 7
C.1 2 4 5 6 3 7 D.1 2 3 4 5 7 6

答案：
1 2 3 4 5 6 7 8 9 10
C B B A C B A D C A

二、算法设计题（请先简要说明算法思想，然后写出算法的C语言源代码实现）

1、设计一个算法deleteMinNode(LinkList &L)，在带头结点的单链表L中删除所有结点值最小的结点（可能有多个结点值最小的结点）。
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;

2、二叉树用二叉链表存储表示。
typedef struct BiTNode
{
TelemType data;
Struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
编写一个复制一棵二叉树的递归算法。
统一使用如下函数名：BiTree CopyTree(BiTree T)

1、参考答案：
用p从头至尾扫描单链表，pre指向p结点的前驱，用minp保存值最小的结点指针，minpre指向minp结点的前驱。一面扫描，一面比较，将最小值的结点放到minp中。算法如下：
void deleteMinNode (LinkList &L)
{
LinkList pre=L, p=pre->next, minp=p, minpre=pre;
ElemType mindata=p->data;
while (p!=NULL && p->data<mindata)
{ mindata=p->data;
p=p->next;
}
p=pre->next;
while (p!=NULL)
{
if (p->data==mindata)
{ pre->next=p->next;
free§;
}
pre=pre->next;
p=pre->next;
}
}
2、参考答案：
BiTree CopyTree(BiTree T) {
if (!T ) return NULL;
if (!(newT = (BiTNode)malloc(sizeof(BiTNode))))
exit(Overflow);
newT-> data = T-> data;
newT-> lchild = CopyTree(T-> lchild);
newT-> rchild = CopyTree(T-> rchild);
return newT;
}