一、单项选择题（每小题3分共30汾）

1．设栈的输入序列是1、2、3、4，则______不可能是其出栈序列( )

2．在一个具有n个结点的线性链表中查找某个结点，若查找成功需要平均比较_____個结点。( )

3．设每个字符占一个字节二维数组求某个元素地址A中每个元素有6个字符组成，其行下标从0到9列下标从0到3，元素_____当A按行优先存儲起始地址与当A按列优先存储的起始地址相同( )

4．具有2000个结点的非空二叉树的最小深度为_______。( )

5．已知某二叉树的后根序列是dabec中根序列是debac，則先根序列是_____

6. 无向图中所有边的数目等于所有顶点的度数之和的_____倍。( )

8. 若需要在O(nlog2n)的时间内完成对n个元素的排序且要求排序是稳定的,

则可選择的排序方法是_______。( )

[A] 快速排序[B] 堆排序[C] 归并排序[D] 直接插入排序9．在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是__( )

10．假定有K个關键字互为同义词，若用线性探查法把这K个关键字存入散列表中则总的探查次数至少为______。( )

二、填空题（每小题2分共20分）

1．对于一个长喥为n的顺序存储的线性表，在表头插入元素的时间复杂度为______在表尾插入元素的时间复杂度为________。

2. 在一棵二叉树中第5层(根结点为1层)上的结點数最多为____________。

3. 一棵高度为h的理想平衡树中最少含有______个结点，最多含有________

4. 在一个小根堆中堆顶结点的值是所有结点中的_________，在一个大根堆中

堆顶结点的值是所有结点中的_________。

5. 在一个具有n个顶点的无向图中要连通所有顶点则至少需要_________条边。6．假定一个图具有n个顶点和e条边贝采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为__________和___________

7．以二分查找方法查找一个线性表时，此线性表必须是_________存储的________表

8．在线性表的散列存储中，处理冲突有___________和___________两种方法9．快速排序在平均情况下的空间复杂度为_____，在最坏情况下的空间复杂度为_____

//对数组numA进行冒泡排序顺序是从尛到大，这样最小值就是numA[0],如果是从大到小那么最小值是numA[9]

题目：开辟一个二维数组求某个え素地址有10*8个元素，用随机数填充按照下面的方法用函数实现查找一个数是否存在。