六、代码题（40分）

1.判断一棵树是二叉排序树，写出算法设计思想，写出代码，计算时间复杂度

2.图的深度优先搜索遍历的非递归算法，写出算法设计思想和代码

3.两个数组（a1...am）和（b1...bn）存储在线性表A[1…m+n]中，要求将两个数组位置互换，写出算法设计思想和代码

五、应用题（4*5）

1.给出一组数进行非递减排序，增量序列d=｛5,3,1｝，写出希尔排序过程和结果

2.给出一组数和装填因子，用线性探查法解决冲突，要求写出哈希函数，画出哈希表，计算等概率情况下的查找成功和失败情况下的平均查找长度

3.给出中序遍历序列和后序遍历序列，要求画出二叉树，并写出先序遍历序列

4.忘记了

四、填空题（10*2）

1.程序的＿＿性是指，对输入数据进行判断，避免对输入的错误数据进行计算后得出乱七八糟的结果

2.三元组和＿＿可以用来存储特殊矩阵和稀疏矩阵

3.给出一组数和排序过程，判断是什么排序

4.计算下列代码的时间复杂度，代码大概是

while（i＜n）  i=i*2；

5.一个二维数组m*n（m和n是具体数字），按列优先存储在一维数组中，每个元素占两个字节，开始位置1024，计算某个具体位置的元素的存储位置

6.给出一组数，计算这组数构成的赫夫曼树的最短带权路径长度

7.一维数组A[m,n]存储在循环队列中，队列满的判断条件是

三、判断题（10*2）

1.折半查找判定树是一棵完全二叉树

2.一个关于大顶堆中元素大小的表述，具体忘记了

二、多选题（10*2）

1.以下时间复杂度相同的是

A. 克鲁斯卡尔算法           B. 冒泡排序

C. 迪杰斯特拉算法           D. 拓扑排序

2.对B-树的特性描述正确的是

A. 叶子结点不在同一层

B. 叶子结点有指针连接

其他两个正确选项不记得了

3.给出一组数的第二趟排序结果，可能是以下哪种排序

4.给出进栈序列，以及第几个（具体第几忘记了）出栈的元素是a，以下可能的出栈序列是

5.以下排序算法，排序趟数与初始状态无关的是

一、单选题（15*2）

1.对一个有n个顶点，e条边的无向图，删除某个顶点及其邻接边的时间复杂度是

A. ne   B. n+e   C. n    D. 不记得了

2.第六层有24个叶子结点的完全二叉树最多有几个结点

3.高度为h的完全二叉树只有度为0和2的结点，则这棵树有几个结点

4.有n个分支节点的二叉树高度是

5.一个只有尾指针rear的带头节点的单链表，删除第一个元素的算法是

选项中给出具体的算法语句

6.若一个链表只有四种操作：删除第一个结点，删除最后一个结点，在第一个结点前插入元素，在最后一个结点后插入元素，则最好用以下哪种链表储存

A. 只有尾指针的带头节点的循环双链表

B. 只有尾指针的带头节点的循环单链表

C. 只有头指针的循环单链表

D. 只有尾指针的带头节点的非循环双链表

7.一个100*100的三对角矩阵，按行优先存储在下标从0开始的一维数组中，A25,26的存储位置是

8.给出一组数是一个堆（题目没说但可判断是小顶堆），插入一个元素调整后得到的堆是

9.对串的描述错误的是

（具体选项忘记了，串在2020大纲里只涉及模式匹配，但还是考了串的基本概念）

10.有n个顶点的图的最小生成树是指

A. 有n个顶点的权值最小的连通子图

B. 有n-1条边的权值最小的连通子图

C. D选项忘记了