A是2iB不存在C是2i+1D是2i-1
13．有N个顶点的无向图的邻接矩阵是用（A）数组存储。
AN行N列B一维C任意行N列DN行任意列
14．连通分量是（A）的极大连通子图。
A无向图B有向图C树D图
15．最小生成树的构造可使用（A）算法。
Aprim算法B卡尔算法C迪杰斯特拉算法D哈夫曼算法
16．查找表是以（A）为逻辑结构。
A集合B图C文件D树
17．散列查找是由键值（A）确定散列表中的位置，进行存储或查找。
A的散列函数值B本身C平方D相反数
18．索引顺序表的特点是顺序表中的数据（D）。
A有序B无序C块间有序D散列
19．排序是根据（C）的大小重新安排各元素的顺序。
A数组B关键字C元素D结点
20．不稳定的排序方法是指在排序中，关键字值相等的不同记录间的前后相对位置（C）。
A保持不变B保持相反C不定D无关
二、填空题（每空2分，共20分）
1．已知带表头结点的单链表L，指针P指向L链表中的一个结点（非首结点、非尾结点），则删除P结点的直接后继结点的语句序列是P->next=P->next->next；删除尾结点的语句序列是while（p->next->next）p=p->next;p->next=NULL;。
2．栈S经过运算InitStack（s）;Push（s,a）;Pop（s,x）后，x的值是a。
3．队列Q经过运算InitQueue（q）;EnQueue（q,a）;OutQueue（Q,x）后，EmptyQueue（q）的值是TRUE。
4．根结点的层数为1。
5．在树与二叉树之间的转换方法中，树的根变为二叉树的根。
6．将下列按关键字的值从小到大的直接选择排序算法补充完整。
Select（listr,intn）
{
for（i=1;语句1i<=n;i++）
{
k=i;
for（j=i+1;语句2j<=n;j++）
if（r[k].key>r[j].key）语句3k=j;;
if（i!
=k）
swap（r[k],r[i]）;
}
}
7．两个不同的元素存入同一个散列表，当这两个元素的散列函数相同时，称为冲突。
三、应用题（每题6分，共30分）
1．二叉树的基本形态有几种，请画出所有形态。
的前序、中序和后
2．写出图1所示二叉树序遍历序列。
答：
前序：
ABDECF中序：
DBEACF后序：
DEBFCA
3．根据图2所示邻接表，写出该图从C点出发的深度和广度优先搜索序列。
答：
深度：
CDBAFE广度：
CDABFE
4．A、B、C三个元素进S栈的顺序是A、B、C，出栈的序列是C、B、A，请写出相应的操作序列。
答：
A入栈（Push（S,A）），B入栈（Push（S,B）），C入栈（Push（S,C）），C出栈（Pop（S）），B出栈（Pop（S）），A出栈（Pop（S））。
5．假设通信的电文由字符集a、b、c、d、e、f、g中的字母构成。
它们在电文中出现的频度分别为0.31、0.16、0.10、0.08、0.11、0.20、0.04，为这7个字母设计哈夫曼树。
答：
四、程序设计题10分
建一个单链表，将10个学生的成绩放入单链表（学生的成绩从键盘上输入），然后再将单链表中的学生成绩打印出来。
#include"stdafx.h"
#include/*malloc（）等*/
#include/*EOF（=^Z或F6）,NULL*/
#include
#include/*exit（）*/
/*函数结果状态代码*/
#defineTRUE1
#defineFALSE0
#defineOK1
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/
typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/
typedefintElemType;
structLNode
{
ElemTypedata;
structLNode*next;
};
typedefstructLNode*LinkList;/*另一种定义LinkList的方法*/
StatusInitList（LinkList*L）
{/*操作结果：
构造一个空的线性表L*/
*L=（LinkList）malloc（sizeof（structLNode））;/*产生头结点,并使L指向此头结点*/
if（!
*L）/*存储分配失败*/
exit（OVERFLOW）;
（*L）->next=NULL;/*指针域为空*/
returnOK;
}
StatusListInsert（LinkListL,ElemTypee）
{/*在带头结点的单链线性表L中第i个位置之前插入元素e*/
intj=0;
LinkListp=L,s;
while（p&&p->next）/*寻找第i-1个结点*/
{
p=p->next;
}
s=（LinkList）malloc（sizeof（structLNode））;/*生成新结点*/
s->data=e;/*插入L中*/
p->next=s;
s->next=NULL;
returnOK;
}
StatusListTraverse（LinkListL,void（*vi）（ElemType））
{/*操作结果:
依次对L的每个数据元素调用函数vi（）。
一旦vi（）失败,则操作失败*/
LinkListp=L->next;
while（p）
{
vi（p->data）;
p=p->next;
}
printf（"\n"）;
returnOK;
}
voidvisit（ElemTypec）/*与main2-1.c不同*/
{
printf（"%d",c）;
}
intmain（intargc,char*argv[]）
{
LinkListL;
inti,e;
i=InitList（&L）;
printf（"请输入10个学生的成绩：
\n"）;
for（i=1;i<=10;i++）
{
scanf（"%d",&e）;
ListInsert（L,e）;
}
printf（"在L的表尾依次插入10个学生的成绩后，输出链表结果：
L="）;
ListTraverse（L,visit）;
//*************************
return0;
}
答题卡
得分
评卷人
一、单选题：
（40分，每题2分）
题号
1
2
3
4
5
6
7
8
9
10
答案
题号
11
12
13
14
15
16
17
18
19
20
答案
得分
评卷人
二、填空题：
（20分，每空2分）
1．删除P结点的直接后继结点的语句序列是：
删除尾结点的语句序列是：
2．
3．
4．
5．
6．
语句1：
语句2：
语句3：
7．
得分
评卷人
三、应用题（30分，每题6分）
得分
评卷人
四、程序设计题，10分
升级会员 