第1题：
以下哪一个不是队的基本运算?（ ）
A)从队列中删除第i个元素
B)从队尾插入一个新元素
C)将队列置为空队列
D)读取队头元素的值
第2题：
对于长度为n的顺序表，插入或删除表中元素的时间复杂度为【 】 ；对于顺序栈或队列，插入或删除表中元素的时间复杂度为【 】。
第3题：
● 栈和队列都是线性的数据结构。以下关于栈和队列的叙述中，正确的是 （37） 。
（37）A. 栈适合采用数组存储，队列适合采用循环单链表存储
B. 栈适合采用单链表存储，队列适合采用数组存储
C. 栈和队列都不允许在元素序列的中间插入和删除元素
D. 若进入栈的元素序列确定，则从栈中出来的序列也同时确定
答案：B
顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。
第4题：
第5题：
试题四（共15分）
阅读下列说明和C代码，回答问题1至问题 3，将解答写在答题纸的对应栏内。
【说明】
堆数据结构定义如下：
在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图4-1 是一个大顶堆的例子。
堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对应于两类堆结构，优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶堆，最小优先队列采用小顶堆。以下考虑最大优先队列。
假设现已建好大顶堆A，且已经实现了调整堆的函数heapify(A, n, index)。
下面将C代码中需要完善的三个函数说明如下：
（1）heapMaximum(A)：返回大顶堆A中的最大元素。
（2）heapExtractMax(A)：去掉并返回大顶堆 A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆。
（3）maxHeapInsert(A, key)：把元素key插入到大顶堆 A的最后位置，再将 A调整成大顶堆。
优先队列采用顺序存储方式，其存储结构定义如下：
define PARENT(i) i/2
typedef struct array{
int *int_array; //优先队列的存储空间首地址
int array_size; //优先队列的长度
int capacity; //优先队列存储空间的容量
} ARRAY;
【C代码】
（1）函数heapMaximum
int heapMaximum(ARRAY *A){ return （1） ; }
（2）函数heapExtractMax
int heapExtractMax(ARRAY *A){
int max;
max = A->int_array[0];
（2） ;
A->array_size --;
heapify(A,A->array_size,0); //将剩余元素调整成大顶堆
return max;
}
（3）函数maxHeapInsert
int maxHeapInsert(ARRAY *A,int key){
int i,*p;
if (A->array_size == A->capacity) { //存储空间的容量不够时扩充空间
p = (int*)realloc(A->int_array, A->capacity *2 * sizeof(int));
if (!p) return -1;
A->int_array = p;
A->capacity = 2 * A->capacity;
}
A->array_size ++;
i = （3） ;
while (i > 0 && （4） ){
A->int_array[i] = A->int_array[PARENT(i)];
i = PARENT(i);
}
（5） ;
return 0;
}
【问题 1】（10分）
根据以上说明和C代码，填充C代码中的空（1）～（5）。
【问题 2】（3分）
根据以上C代码，函数heapMaximum、heapExtractMax和 maxHeapInsert的时间复杂度的紧致上界分别为 （6） 、 （7） 和 （8） （用O 符号表示）。
【问题 3】（2分）
若将元素10插入到堆A =〈15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1〉中，调用 maxHeapInsert函数进行操作，则新插入的元素在堆A中第 （9） 个位置（从 1 开始）。
第6题：
依次在初始队列为空的队列中插入元素a,b,c,d(设此设备最多容纳五个元素)。接着做了两次删除操作，此时，还可以向队列中插()个元素
A2
B1
C0
D3
第7题：
以下关于栈和队列的叙述中，错误的是（ ）。
A.栈和队列都是线性的数据结构 B.栈和队列都不允许在非端口位置插入和删除元素 C.一个序列经过一个初始为空的栈后，元素的排列次序一定不变 D.一个序列经过一个初始为空的队列后，元素的排列次序不变
第8题：
队列的“先进先出”特性是指()。
A.最早插入队列中的元素总是最后被删除
B.当同时进行插入、删除操作时，总是插入操作优先
C.每当有删除操作时，总是要先做一次插入操作
D.每次从队列中删除的总是最早插入的元素
第9题：
第10题：