一、名词解释(每题2分，共10分)
1.时间复杂度
2.链栈
3.二维数组
4.森林
5.小根堆
二、判断正误(正确打√，错误划×，每题1分，共10分)
1.算法可以是无限循环。()
2.顺序表能够动态分配结点空间。()
3.队列是一种先进先出的线性表。()
4.图可用邻接表或邻接矩阵进行存储。()
5.二叉树的叶子结点数等于度为2的结点数。()
6.广义表的求表头操作得到的也是广义表。()
7.二分查找适于有序表。（）
8.假设结点总数为n，冒泡排序至多进行n-1轮排序。()
9.直接插入排序是稳定的排序算法。()
10.顺序查找方法只能用于线性表的顺序存储结构。()
三、填空(每空2分，共10分)
1.数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：集合、线性结构、()、图状结构。
2.栈是一种特殊的线性表，允许插入和删除运算的一端称为（）。
3.()是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
4.若图G中每条边都()方向，则G为无向图。
5.图的邻接矩阵是表示()之间相邻关系的矩阵。
四、选择题(单选或多选)(每题2分，共30分)
1.算法的每一步，必须有确切的定义，也就是说，对于每一步需要执行的动作必须严格、清楚地给出规定。这
是算法的()
A.正确性B.有穷性C.确定性D.可行性
2.设一棵二叉树中，度为2的结点数为8，则该二叉树的叶结点的数目为()。
A.10B.11C.12D.9
3.任何一棵二叉树的叶子结点在先根、中根和后遍历序列中的相对次序()
A.不发生改变B.发生改变C.不能确定D.以上都不对
4.关于栈的说法正确的是（）
A.后进先出B.属于非线性结构C.只能采用顺序存储D.属于散列结构
5.用单链表表示的链式队列的队头是在链表的()位置
A.表尾B.表头C.表中D.任意
6.树的叶子结点是（）。
A.度为1的结点B.根结点C.度为0的结点D.孩子结点
7.图的邻接矩阵是表示()之间相邻关系的矩阵。
A.边B.顶点C.路径D.有向边
8.一个图的生成树的顶点是图的()顶点。
A.1个B.1/3C.所有D.1/2
9.广度优先遍历算法类似于二叉树的()遍历
A.按层次B.先根C.中根D.后根
10.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用()查找方法
A.分块B.顺序C.折半D.散列
11.在对n个元素进行冒泡排序的过程中，至少需要（）趟完成。
A.n-1B.nC.1D.n/2
12.若一个元素序列基本有序，则选用()方法较快
A直接插入排序B直接选择排序C堆排序D快速排序
13.关于链式存储的说法正确的有()
A.能动态分配结点空间B.只能应用于线性表结构
C.能随机存取D.需要定义指针域
14.数据的存储结构所包括的存储方法有()
A.顺序存储方法B.链接存储方法
C.索引存储方法D.散列存储方法
15.以下哪些属于算法的特性()
A.有穷性B.确定性
C.可行性D.运行性
五、简述题(每题10分，共30分)
1.什么是特殊矩阵，对特殊矩阵压缩存储的原理是什么？
2.试描述头指针、头结点、开始结点的区别
3.简述二叉树后根遍历思想。
参考答案
一、名词解释(每题2分，共10分)
1.时间复杂度
答：程序所用算法运行时所要花费的时间代价。
2.链栈
答：栈可用链式结构来表示，栈顶为单链表的第一个结点，整个单链表称为链栈。
3.二维数组
答：二维数组Amn可看成由m个行向量组成的向量，或由n个列向量组成的向量。
4.森林
答：森林是由m(m≥0)棵互不相交的树组成的集合。
5.小根堆
答：根结点(堆顶)的关键字是堆里所有结点关键字中最小者的堆为小跟堆。
二、判断正误(每题1分，共10分)
1~5××√√×
6~10×√√√×
三、填空(每空2分，共10分)
1.树型结构2.栈顶3.队列4.没有5.顶点
四、选择题(单选或多选)(每题2分，共30分)
1C2A3C4A5B
6C7B8C9A10A
11C12A13AD14ABCD15ABC
五、简述题(每题10分，共30分)
1.什么是特殊矩阵，对特殊矩阵压缩存储的原理是什么？
答：如果矩阵中值相同的元素或零值元素在矩阵中的分布有一定的规律，则称为特殊矩阵。特殊矩阵中有很多值相同的元素或零值元素，为了节省存储空间，需要对它们进行压缩存储，即不存储或少存储这些值相同的元素或零元素，这称为矩阵的压缩存储
2.试描述头指针、头结点、开始结点的区别。
答：头结点
为了更方便的判断空表、插入和删除结点，通常在单链表的第一个结点前面加上一个附设的节点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储一些附加信息；而头结点的指针域存储链表第一个结点的地址。
如果头结点的指针域为“空”，即L-next==NULL，则表示该链表为空表
头指针
是指向链表中的第一个结点(可以是头结点，也可以是开始结点)的指针。若链表中附设了头结点，则不管线性表是否为空，头指针均不为空；若链表中不设头结点，则线性表为空时，链表的头指针为空
开始结点(即首元结点)
是指链表中存储线性表中第一个数据元素a1的结点
3.简述二叉树后根遍历思想。
答：先根遍历是先后根遍历左子树，再后根遍历右子树，再访问根结点。
六.程序分析与设计(每题5分，共10分)。
1.答：该代码段主要实现的功能为：以二叉链表为存储结构，求出二叉树高度。
2.答：
LinkListLink(LinkListL1,LinkListL2)
{
ListNode*p,*q;p=L1;q=L2;
while(p-next)p=p-next;/*遍历单链表L1，查找终端结点*/
p-next=q-next;/*将L2的开始结点连接在L1之后*/
returnL1;
}
算法时间复杂度分析：经过合并后的单链表长度为原两个单链表长度之和m+n
该算法的内层循环执行次数为L1的循环次数，为m次，故算法的时间复杂度为O(m)。
六.程序设计(每题5分，共10分)。
1.假设以下代码段中，b为指向二叉树根结点的指针
inthigh(bitreeb)
{
inth1,h2;
if(b==NULL)return0;
else
{
h1=high(b-Lchild);
h2=high(b-Rchild);
if(h1h2)return(h1+1);
elsereturn(h2+1);
}
}
试说明该代码段主要实现了什么功能？
2.已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，并分析算法的时间复杂度。