1、下列选项中，不属于线性结构的是 单选题 2分

2、某线性表L含有n个元素，采用单循环链表保存，仅有尾指针指向链表的终端结点。在最后一个结点之后插入一个结点及删除第一个结点的时间复杂度分别是， 单选题 2分

3、下列应用中会用到栈的是 单选题 2分

4、设栈初始为空，入栈序列为1，2，3，4，5，下列选项中，不可能得到的出栈序列是 单选题 2分

5、已知广义表LS（（（c，（d）），（e，（f））），（g，h），（（m，n））），head（LS）是 单选题 2分

6、设线性表采用顺序存储方式保存，每个元素占8个存储单元。第1个元素的存储地，址为200，则第5个元素占用的最后一个存储单元的地址是 单选题 2分

7、一棵完全二叉树T的全部k个叶结点都在同一层中，每个分支结点都有两个孩子结点。T中包含的结点数是 单选题 2分

8、设字符集中有n个字符，对其进行哈夫曼编码，得到的哈夫曼树的结点总数是 单选题 2分

9、设图G的邻接矩阵A如下所示。G的各顶点的度依次是 单选题 2分

10、对题10-11图进行深度优先遍历，下列选项中，正确的遍历序列是 单选题 2分

11、对题10-11图进行拓扑排序，下列选项中，正确的拓扑序列是 单选题 2分

12、下列排序方法中，不是稳定排序方法的是 单选题 2分

13、已知数据序列（18，19，20，4，51，6，30，1，2）是某种排序算法第二越排序后得到的结果，则该算法可能是 单选题 2分

14、对有序表（1，3，9，12，32，41，45，62，75，77）进行二分查找，查找关键字9时，进行比较的关键字依次是 单选题 2分

15、分别使用下列数据序列建立二叉排序树，能得到高度最高的二叉树的是 单选题 2分

16、数据的运算，即对数据元素施加的操作，是定义在数据的（ ）结构上的。 填空题 2分

17、在顺序表中，因为访问任一结点的方式是（ ），所以访问每个结点的时间复杂度均为O（1）。 填空题 2分

18、带头结点的链队列可以由一个头指针和一个尾指针唯一确定。当头指针和尾指针相等时，表示队列（ ）。 填空题 2分

19、稀疏矩阵采用压缩存储，只保存非零元素，得到的顺序存储结构称为（ ）。 填空题 2分

20、广义表（（a），（b，c），（d，e，（f，g，h）））的表尾是（ ）。 填空题 2分

21、中序线索化二叉树的过程，是在中序遍历过程中用线索取代（ ）。 填空题 2分

22、在有n个顶点、e条边的无向连通图中，e的取值范围是（ ）。 填空题 2分

23、对数据序列进行升序排序。采用堆排序算法时，首先应对初始数据建立（ ）堆。 填空题 2分

24、在无序数组中进行查找操作，应使用的查找方法是（ ）。 填空题 2分

25、一棵高度为2的4阶B树中能够保存的关键字个数最多是（ ）。 填空题 2分

26、请画出题26图所示的二叉树对应的树或森林。 简答题 5分

27、求题27图从顶点A到其余各顶点的最短路径，给出各条路径包含的顶点序列及路径长度。 简答题 5分

28、有以下数据序列（20，84，19，14，23，01，68，27，55，11，10，79，12），使用二路归并排序算法将其排成升序序列。给出各越排序结果。 简答题 5分

29、设有以下关键字：15，72，52，65，23，68，散列函数H（key）=key%7，散列表空间为0~6，采用线性探查法解决冲突。请回答下列问题。（1）构造散列表。（2）计算等概率情况下查找成功时的平均查找长度。 简答题 5分

30、顺序表类型定义如下。 #define ListSize 100 typedef struct { int data[ListSize]； int length； SeqList； 阅读下列函数，并回答问题。 SeqList*f30（int*pdata，int n） { int k，m； SeqList*SL； SL=（SeqList*）malloc（sizeof（SeqList））； SL->length = 0； for（k=0；kdata[SL->length]= pdata[k]； else { for（m=SL->length；m>0；m--） SL->data[m]= SL->data[m-1]； SL->data[0]= pdata[k]； } SL->length ++； } for（k=0；klength；k++） printf（"%d，"，SL->data[k]）； return SL； } （1）若已知：int array[]={10，2，9，5，30，3}；，执行语句： f30（array，sizeof（array）/sizeof（int））; 函数f30()的输出是什么？ 函数f30()的功能是什么？ 简答题 5分

31、阅读函数f31()，并回答问题。 f31（int a[]，int n） { int k，m = 0，temp； while（a[m] 简答题 5分

32、 简答题 5分

33、待排序记录的数据类型定义如下。#define MAXSIZE 100typedef int KeyType；typedef struct {KeyType key；}RecType；typedef RecType SeqList[MAXSIZE]； 简答题 5分

34、 简答题 10分