二叉树，其所有结点的度的总和是_____________。
8
对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个
______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结
点序列是该算术表达式的__________________。
9
对于一棵具有
个结点的二叉树，用二叉链表存储时，其指针总数
为_____________个，其中_______________个用于指向孩子，_________________
个指针是空闲的。
10若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存
储到一维数组A中，即编号为0的结点存储到A0中。其余类推，则Ai元
素的左孩子元素为________右孩子元素为_______________，双亲元素为
____________。
11在线性表的散列存储中，处理冲突的常用方法有
________________________和_____________________________两种。
12当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用
_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳
定时，宜采用________________________排序。
三、1
运算题（每题6分，共24分）已知一个65稀疏矩阵如下所示，
00001
0
0
00
0

01000
00002
50000


00700
大全
f实用文档
试：
（1）
写出它的三元组线性表；
（2）
给出三元组线性表的顺序存储表示。
2
设有一个输入数据的序列是462578621280试画出
从空树起，逐个输入各个数据而生成的二叉搜索树。
3
对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表
中的边结点都是按照终点序号从小到大的次序链接的，试写出：1从顶点①出发进行深度优先搜索所得到的深度优先生成树；
2从顶点②出发进行广度优先搜索所得到的广度优先生成树；
4
已知一个图的顶点集V和边集E分别为：
V1234567
E213236434
54651576162
65
若存储它采用邻接表，并且每个顶
点邻接表中的边结点都是按照终点序
图6
号从小到大的次序链接的，按主教材
中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。
四、
阅读算法（每题7分，共14分）
1
i
tPrimei
t


i
ti1
i
txi
tsqrt

whileix
if
i0break
ifixretur
1
elseretur
0

1
指出该算法的功能；
2
该算法的时间复杂度是多少？
2
写出下述算法的功能：
voidAJadjlistGLi
tii
t


QueueQ
I
itQueueQ
couti
大全
f实用文档
visiteditrueQI
sertQiwhileQueueEmptyQ
i
tkQDeleteQedge
odepr