A、n-iB、n-i+1C、n-i-1D、i
4.插入和删除操作只能在一端进行的线性表，称为（C）。
A.队列B.线性表C.栈D.循环队列
5、队列是仅允许在（）进行插入，而在（）进行删除。
（A）
A.队尾，队首B.队尾，队尾C.队首，队尾D.队首，队首
6.链表适合于（A）查找。
A.顺序B.二分C.随机D.顺序或二分
7.数据的基本单位是（A）。
A.数据元素B.数据结构C.数据项D.数据对象
8.下列哪个不是算法的特性（B）。
A.有穷性B.可数性C.可行性D.确定性
9.在表长为n的顺序表中进行线性查找，它的平均查找长度为（B）。
A.ASL=nB.ASL=（n+1）/2C.ASL=
+1D.ASL=log2n
10.一个线性表第一个元素的存储地址是320，每个元素的长度为3，则第五个元素的地址是（C）。
A.311B.328C.332D.313
11.设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（D）。
A.P==LB.P->front==LC.P==NULLD.P->rear==L
12.已知P为单链表中的非首尾结点，删除P结点的后继结点Q的语句为（A）。
A.P->NEXT=Q->NEXT;FREE（Q）;B.Q->NEXT=P;FREE（Q）;
C.Q->NEXT=P->NEXT;FREE（Q）;D.P->NEXT=S;S->NEXT=P;
13.循环队列SQ队满的条件是（B）。
A.SQ->rear==SQ->frontB.（SQ->rear+1）%MAXLEN==SQ->front
C.SQ->rear==0D.SQ->front==0
14.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（B）。
A、79，46，56，38，40，80
B、84，79，56，38，40，46
C、84，79，56，46，40，38
D、84，56，79，40，46，38
15.排序趟数与序列原始状态（原始排列）有关的排序方法是（ACD）方法。
A、插入排序B、选择排序
C、冒泡排序 D、快速排序
16.下列排序方法中，（B）是稳定的排序方法。
A、直接选择排序B、二分法插入排序
C、希尔排序D、快速排序
17.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中（C）的两趟排序后的结果。
A、选择排序B、冒泡排序
C、插入排序D、堆排序
18.对序列（15，9，7，8，20，-1，4）进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C）排序。
A、选择B、快速
C、希尔D、冒泡
19.一组待排序记录的关键字为（46，79，56，38，40，84），则利用快速排序，以第一个记录为基准元素得到的一次划分结果为（C）。
A（38,40,46,56,79,84）B、（40,38,46,79,56,84）
C、（40,38,46,56,79,84）
D、（40,38,46,84,56,79）
20.用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是（C）。
A、94,32,40,90,80,46,21,69B、32,40,21,46,69,94,90,80
C21,32,46,40,80,69,90,94D、90,69,80,46,21,32,94,40
21.若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（B）。
A、10B、15C、21D、34
22.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（A）。
A、堆排序<快速排序<归并排序
B、堆排序<归并排序<快速排序
C、堆排序>归并排序>快速排序
D、堆排序>快速排序>归并排序
23.最小生成树的构造可使用（B）算法。
A.Dijkstra算法B.Prim算法C.Haffman算法D.Floyd算法
24.具有32个结点的完全二叉树的深度为（B）。
A.5B.6C.7D.8
25.在有n个叶子结点的哈夫曼树中，其结点总数为（D）。
A．不确定B．2nC．2n+1D．2n-1
26.下列陈述正确的是（B）。
A.二叉树是度为2的有序树B.二叉树中最多只有二棵树,且有左右子树之分
C.二叉树必有度为2的结点D.二叉树中结点只有一个孩子时无左右之分
27.先序为A，B，C的二叉树共有（A）种。
A.3B.4C.5D.6
28.在树结构中,若结点B有3个兄弟,A是B的父亲结点,则A的度为（B）。
A.3B.4C.5D.6
29.在一个图中，所有顶点的度数之和等于所有边数的（B）倍。
A、1B、2C、3D、4
30.n个顶点的强连通图至少有（A）边。
A、nB、n-1C、n+1D、n（n-1）
31.在一个无向图中，所有顶点的度数之和等于所有边数的（C）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。
A、1/2B、2C、1D、4
32.任何一个无向连通图的最小生成树（B）。
A、只有一棵B、一棵或多棵
C、一定有多棵D、可能不存在
33.在图的表示法中，表示形式唯一的是（A）
A、邻接矩阵表示法B、邻接表表示法
C、逆邻接矩阵表示法D、逆邻接表表示法
34.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。
A.nB.n+1C.n-1D.n+2
35.在一个图中，所有顶点的度数之和等于图的边数的（B）。
A．1/2B．2C．1D．4
36．有7个结点的有向完全图有（C）边。
A.30B.40C.42D.56
37.假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，则叶子结点数为（B）。
A、15B、16C、17D、47
38.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（C）。
A、n在m右方B、n是m祖先
C、n在m左方D、n是m子孙
39.某二叉树的后序遍历序列为：
DABEC，中序遍历序列为：
DEBAC，则前序遍历序列为（D）。
A、ACBEDB、DECAB
C、DEABCD、CEDBA
40.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子的编号为（90），右孩子的编号为（91）。
A、46B、47C、91D、91
41.某树中，若结点B有4个兄弟，A是B的父亲结点，则A的度为（C）。
A、3B、4C、5D、6
42.下列叙述正确的是（D）
A、二叉树是度为2的有序树
B、二叉树结点只有一个孩子时无左右之分
C、二叉树中必有度为2的结点
D、二叉树中最多只有两棵子树，且有左右之分
43.由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（D）。
A、23B、37
C、46D、44
44．在图的表示方法中，表示形式是唯一的是（C）。
A.邻接表B.逆邻接表C.邻接矩阵D.其他
44.下列关键字序列中，构成大根堆的是（D）
A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33
C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，3
45.对序列（15，9，7，8，20，-1，4）进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C）排序。
A.选择B.快速C.希尔D.冒泡
46.设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（C）。
A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙
二、填空题
1.树和图都属于非线性结构。
2.顺序表中逻辑上相邻的元素在物理位置上也相邻。
3.双向链表有两个指针域，一个指向前趋，另一个指向__后继__。
4.若进栈的次序是A,B,C,D,E,写出两种出栈顺序_ABCDE、EDCBA。
5.队列存取数据应遵循的原则是先进先出。
6.有20个结点的完全二叉树，编号为7的结点的父结点编号为3。
7.两个序列分别为：
L1={3，50，41，42，55，65，70，75}，L2={3，50，41，42，65，55，.
10，5}，用冒泡排序法对L1和L2进行排序，交换次数较少的是序列：
L1。
8.在排序方法中，从无序序列中选择关键字最小的记录，与无序区（初始为空）的第一个记录交换的排序方法，称为选择排序。
9.有向图的边也称为弧，用邻接矩阵存储有向图，其第i行的所有元素之和等于顶点i的出度。
10．树转换成的二叉树，其根结点的右子树一定为空。
11.二叉排序树是一种动态查找表。
12.对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7条记录60插入到有序表中时，为寻找插入位置需比较15次。
13.在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有1个前驱结点；叶子结点没有后继结点，其余结点的后继结点可以任意多个。
14.在具有n个结点的二叉树中，有n+1个空指针。
15.深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是n/2+1。
16.由a，b，c三个结点构成的二叉树，共有30种不同形态，若是构成树，共有9种形态。
17.树所对应的二叉树其根结点的右子树一定为空。
18.已知完全二叉树的第8层有8个结点，则其叶结点数是68
三、综合应用题。
2.已知完全二叉树的第8层有4个结点，请计算它的叶子结点数和总结点数。
（写出计算过程）。
（6分）
解：
由题意可知，
该完全二叉树有八层，其中
第一层结点数为：
1
第二层结点数为：
2
第三层结点数为：
4
第四层结点数为：
8
第五层结点数为：
16
第六层结点数为：
32
第七层结点数为：
64
第八层结点数为：
4
因为第八层结点数为4，且为完全二叉树，则第八层四个结点为叶子结点，第七层前两个结点有子结点，其余62个结点无子结点，则第七层的后62个结点为叶子结点，故叶子结点数有4+62=66
总结点数为1+2+4+8+16+32+64+4=131
3.已知数据序列{10,8,18,15,7,16}，写出采用直接插入算法排序时，每一趟排序的结果。
（6分）
解：
直接插入排序过程如下所示
初始列：
（10），8,18,15,7,16
第一趟：
（8,10）,18,15,7,16
第二趟：
（8,10,18），15,7,16
第三趟：
（8,10,15,18），7,16
第四趟：
（7,8,10,15,18），16
第五趟：
（7,8,10,15,16,18）
6.一棵具有6层的满二叉树中结点数为多少？
请写出计算公式。
解：
63
7.给定一个权集W={4,8,6,9,18}，画出相应的哈夫曼树，并计算WPL。
8.已知二叉树的先序遍历序列为:
ABDGHCEFI,中序遍历的序列为：
GDHBAECIF。
请完成以下各题：
（1）画出此二叉树。
（2）写出它的后序遍历序列。
（3）将此二叉树看作森林的二叉树表示，试将它还原为森林。
（1）
（2）其后序遍历的序列为：
GHDBEIFCA
（3）
8-1.对下面的带权无向图：
（1）画出邻接矩阵。
55
（2）画出它的一棵最小生成树。
1
1046
375
解：
（1）
055000
（2）最小生成树
5011000边为红色的
510046
0100030
004305
006050
9.有一组关键字{14,15,30,28,5,10},写出冒泡排序过程的
图示。
解：
第一趟排序结果：
14,15,28,5,10，（30）
第二趟排序结果：
14,15,5,10，（28,30）
第三趟排序结果：
14,5,10，（15,28,30）
第四趟排序结果：
5,10，（14,15,28,30）
第五趟排序结果：
5，（10,14,15,28,30）
第六趟排序结果：
（5,10,14,15,28,30）
10.给定一个权集W={4，5，7，8，6，12，18}，试画出相应的哈夫曼树，并计算其带权径长度WPL。
WPL=（12+18）*2+（6+7+8）*3+（4+5）*4=159
11.假设用于通信的电文仅由A、B、C、D、E、F、G、H等8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10。
试为这8个字母设计哈夫曼编码。
11-1对于下面所示的图，求出：
（1）画出邻接矩阵和邻接表
（2）求出各顶点的入度和出度
解：
（1）邻接矩阵
12345
邻接表
1
2
3
5
∧
2
4
∧
3
5
∧
4
1
∧
5
4
∧
（2）ID
（1）=1,OD
（1）=3;ID
（2）=1,OD
（2）=1;ID（3）=1,OD（3）=1;ID（4）=2,OD（4）=1;ID（5）=2,OD（5）=1;
12.已知一个无向图的顶点集为{a,b,c,d,e}，其邻接矩阵如下，画出草图，写出从顶点a出发按深度优先搜索进行遍历的结点序列。
01001
10010
00011
01101
10110
解：
（1）
（2）深度优先搜索：
abdce（答案不唯一）
广度优先搜索：
abedc（答案不唯一）
13.网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。
0810110
803013
103040
110407
013070
解：
最小生成树：
811
108
34
13734
7
16.写出图的一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出惟一一种拓扑序列。
17.对图中所示图分别写出深度优先遍历和广度优先遍历的项点序列
18.对图7-21中所示图分别用克鲁斯卡尔算法和普里姆算法（从顶点2开始）求出其最小生成树。
：
19.根据下图，实现下列功能：
（1）建立图的邻接表；
（2）输出图的拓扑序列。
四、算法设计题
1、单向链表中，在p指针所指向的结点前插入一个元素x,写出相关算法,并画出图形进行描述。
解：
#include
#include
typedefintDataType;
typedefstructnode
{
DataTypedata;
structnode*next;
}Listnode;
intInsert（Listnode*head,DataTypea,intb）//这个是插入算法
{
Listnode*p,*h,*s;
intk=1;
p=head;
h=head->next;
while（h!
=NULL&&k<=b-1）
{
k++;
p=h;
h=h->next;
}
if（p==NULL）
{
printf（"插入失败"）;
return0;
}
s=（Listnode*）malloc（sizeof（Listnode））;
s->data=a;
s->next=h;
p->next=s;
return1;
}
voidmain（）
{
Listnode*H,*p;
intx,y;
H=（Listnode*）malloc（sizeof（Listnode））;
H->next=NULL;
printf（"请输入将被存入链表中的数（0为结束）：
"）;
scanf（"%d",&x）;
while（x!
=0）
{
p=（Listnode*）malloc（sizeof（Listnode））;
p->data=x;
p->next=H->next;
H->next=p;
scanf（"%d",&x）;
}
printf（"请输入将被插入的数:
\n"）;
scanf（"%d",&x）;
printf（"请输入将被插入的数的位置：
\n"）;
scanf（"%d",&y）;
p=H->next;
printf（"插入前，链表：
"）;
while（p!
=NULL）
{
printf（"%d",p->data）;
p=p->next;
}
if（Insert（H,x,y））//这里是调用插入算法
{
p=H->next;
printf（"插入后处理后的链表：
\n"）;
while（p!
=NULL）
{
printf（"%d",p->data）;
p=p->next;
}
printf（"\n"）;
}
}
2、在单链表中删除第i个结点,若删除成功返回1,否则返回0,并要求画出图形进行描述。
解：
#include
#include
template
classSeqList
{
public:
TDelete（inti）;
Tdata[5];
intlength;
};
template
TSeqList:
:
Delete（inti）
{
intj;
Tx;
if（length==0）throw"下溢";
if（i<1||i>length）throw"位置异常";
x=data[i-1];
for（j=i;jdata[j-1]=data[j];
length--;
returnx;
}
intDelElem（LinkList*L,inti,datatype*x）
{LinkList*p;
p=GetList（L,i-1）;/*调用按序号查找第i-1个元素地址p函数*/
if（p!
=NULL&&p->next!
=NULL）
{Del_Elem（p,x）;/*调用删除已知结点p之后结点函数*/return1;
}
else
return0;
}
intmain（）
{
SeqLista;
cout<<"请输入单链表的长度：
length=";
cin>>a.length;
cout<<"请输入单链表中的数据：
";
for（inti=0;i{
cin>>a.data[i];
}
for（i=0;icout<cout<cout<<"请输入单链表中要删除数据的位置：
i=";
cin>>i;
a.Delete（i）;
cout<for（i=0;icout<cout<}
升级会员 