10．若原始数据接近无序，则选用 快速排序 最好。
11．对于n个记录的集合进行归并排序，所需要的平均时间为： O（log2n） 。 12．在插入排序、归并排序、快速排序中，排序是不稳定的有： 快速排序 。 13．对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是 54，72，60，96，80 。
14．对于n个记录的集合进行，若对其进行快速排序，在最坏的情况下所需要的时间是
O(n2) 。
15．在最坏情况下，在第i趟直接插入排序中，要进行 i-1 次关键字的比较。
三．选择题
1．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，这种排序方法叫（ C ）。 A．选择 B．交换 C．插入 D．归并 2．快速排序方法在（ C ）情况下最不利于发挥其长处。
A．要排序的数据量太大 B．要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数
3．排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为: ( D )。
A．希尔排序 B．归并排序 C．插入排序 D. 选择排序 4．在待排序的元素序列基本有序的前提下，效率最高的排序方法是：（ A ）。 A．直接插入 B．冒泡排序 C．希尔排序 D．选择排序 5．每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（ C ）。
A．冒泡排序 B．堆排序 C．快速排序 D. 归并排序 6．排序是根据（ A ）的大小重新安排各元素的顺序。
A．关键字 B．数组 C．元素件 D．结点 7．堆的形状是一棵（ D ）。
A．二叉排序树 B．满二叉树 C．不是二叉树 D. 完全二叉树 8．稳定的排序方法是指在排序前后，关键字值相等的不同记录间的前后相对位置（ B ）。 A．保持相反 B．保持不变 C．不定 D．无关 9．下述几种排序方法中，要求内存量最大的是：（ D ）。
A．插入排序 B．选择排序 C．快速排序 D. 归并排序 10．直接插入排序的方法是（ B ）的排序方法。
A．不稳定 B．稳定 C．外部 D．选择 11．直接插入排序的方法要求被排序的数据（ B ）存储。
A．必须链表 B．必须顺序 C．顺序或链表 D．可以任意
12．设有1000个无序元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（ B ）排序法。
A．冒泡排序 B．堆排序 C．快速排序 D. 归并排序 13．用快速排序法对n个元素进行排序时，最坏情况下的执行时间为（ A ）
A．O（n2） B．O（log2n） C．O（nlog2n） D. O（n）
14．一个数据序列的关键字为：（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：（ C ）
A． （38，40，46，56，79，84） B．（40，38，46，79，56，84） C．（40，38，46，56，79，84） D．（40，38，46，56，79，84）
15．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ D ）。
A．选择排序 B．希尔排序 C．归并排序 D.快速排序
第四章
一．判断题
（√）（1）栈是运算受限制的线性表。
（√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。 （×）（3）栈一定是顺序存储的线性结构。 （×）（4）空栈就是所有元素都为0的栈。
（×）（5）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。 （√）（6）一个栈的输入序列为：A，B，C，D，通过入出栈操作可以输出序列：A，B，C，D。
（×）（7）在C或C++语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。 （√）（8）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。 （√）（9）在栈中插入或删除一个元素应遵守的“后进先出”的原则。 （√）（10）进位制的换算算法是栈的应用。 （√）（11）队列是限制在两端进行操作的线性表。
（√）（12）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。 （×）（13）在链队列做出队操作时，会改变front指针的值。
（√）（14）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。 （√）（15）队列是一种“先进先出”的线性表。 （×）（16）在循环链队列中无上溢出现象。 （×）（17）栈和队列都是顺序存储的线性结构。 （√）（18）栈和队列都是属于线性结构。
（×）（19）顺序队和循环队的队满和队空的判断条件是一样的。 （√）（20）在队列中插入或删除一个元素应遵守的”先进先出”的原则。
二．填空题
1．在栈中存取数据遵从的原则是： 后进先出 。
2．在有n个元素的栈中，进栈操作的时间复杂度为 O（1）。 3．后进先出的线性表称为 栈 。
4．在顺序栈中，当top=MAXLEN-1时，表示 栈满 。 5. 栈是输入、输出受限制的 线性表 。
6．在有n个元素的栈中，出栈操作的时间复杂度为 O（1）。 7．在栈结构中，允许插入、删除的一端称为 栈顶 。
8．顺序栈S存在数组S->data[0..MAXLEN-1]中，出栈操作时要执行的语句有：S->top -- 。
9．在顺序栈中，当栈顶指针top=-1时，表示 栈空 。
10．向一个栈顶指针为top的链栈插入一个新结点*p时，应执行 p->next=top； 和top=p； 操作。
11．同一栈的各元素的类型 相同 。 12．栈只能在 栈顶 插入和删除元素。
13．已知顺序栈S，在对S进行出栈操作之前首先要判断 栈是否空 。
14．若进栈的次序是A、B、C、D、E，执行三次出栈操作以后，栈顶元素为 B 。 15．从一个栈删除元素时，首先取出栈顶元素，然后再移动 栈顶指针 。 16．在队列中存取数据应遵从的原则是 先进先出 。
17．设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O（n）。
18．在队列中，允许插入的一端称为 队尾 。
19．设长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为 0（1） 。
20．设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队空的标志为 front==rear 。 21．队列在进行出队操作时，首先要判断队列是否为 空 。
22．设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为 front==(rear+1)% MAXLEN 。
23．在一个链队列中，若队头指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为： front==rear && front <>NULL 。 24．队列结构的元素个数是 可变的 。
25．设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 0（1） 。
26．设长度为n的链队列用单循环链表表示，若只设尾指针，则入队操作的时间复杂度为
0（1） 。
27．链队列为空时，LQ->front->next= NULL 。
28．设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，当rear 29．向一个循环队列中插入元素时，首先要移动队尾指针，然后再向指针所指位置 写入 新的元素。 30．队列Q经过InitQueue (Q)；InQueue (Q，a)； InQueue (Q，b)；GetHead (Q，x)后，x的值是 a 。 三．选择题 1．顺序栈判空的条件是（ C ） A．top==0 B．top==1 C．top==-1 能的出站顺序为 ( D ) A．1234 B．1243 C．1324 D．1423 3．插入和删除只能在一端进行的线性表，称为( C )。 A．队列 B．循环队列 C．栈 D．循环栈 4．链栈与顺序栈相比，有一个比较明显的优点是（ B ）。 A．插入操作根加方便 B．通常不会出现栈满的情况。 C．不会出现栈空的情况 D．删除操作根加方便 5．在栈中，出栈操作的时间复杂度为( A )。 A．O(1) B．O(log2n) C．0(n) D．O(n) 6．带头结点的链栈LS的示意图如下，栈顶元素是（ A ） LS H A B C D Λ A．A B．B C．C D．D 7．元素A,B,C,D依次进栈以后，栈顶元素是（ D ） A．A B．B C．C D．D C．循环链表 D．变量 8．顺序栈存储空间的实现使用（ B ）存储栈元素。 A．链表 B．数组 9．在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ）。 A．已固定 B．不固定 C．可以改变 D．动态变化 10．当栈中的元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为（ C ）。 A．n-1 B．n+1 C．n D．n/2 11．栈与一般线性表的区别在于 ( B )。 A．数据元素的类型不同 B．运算是否受限制 C．数据元素的个数不同 D．逻辑结构不同 12．设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是 2 D．top==m 2．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，下列不可 B，D，C，F，E，A，则栈的容量至少应是 ( A )。 A．3 B．4 C．5 D． 6 13．在栈顶一端可进行（ D ）操作。 A．插入 B．删除 C．进栈 D．插入和删除 14．从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 ( D )命令。 A．x=top;top=top->next; B．top=top->next;x=top->data; C．x=top->data; D．x=top->data;top=top->next; 15．在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列 ( B )命令。 A．HS->next=S; B．S->next=HS->next;HS->next=S; C．S->next=HS->next;HS=S; D．S->next=HS;HS=HS->next; 16．在队列中存取数据应遵循的原则是( A )。 A．先进先出 B．后进先出 C．先进后出 D．随意进出 17．设长度为n的链队列用单循环链表表示，若只设头指针，则人队操作的时间复杂度为( C )。 A．O(1) B．O(log2n) C．O(n) D．O(n) 18．一个循环队列一旦说明，其占用空间的大小（ A ）。 A．已固定 B．可以变动 C．不能固定 D．动态变化 19．当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（ B ）。 A．n-2 B．n-1 C．n D．n+1 20．设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为( A )。 A．O(1) B．O (log2n) C．O(n) D．O(n) 21．队列是限定在（ D ）进行操作的线性表。 A．中间 B．队头 C．队尾 D．端点 22．若进队的序列为：A，B，C，D，则出队的序列是（ C ）。 A．B，C，D，A C．A，B，C，D B．A，C，B，D D．C，B，D，A 22 23．从一个顺序循环队列删除一个元素时，首先需要做的操作是（ B ）。 A．队头指针减1 B．取出队头指针所指的元素 C．队头指针加1 D．取出队尾指针所指的元素 24. 在一个顺序存储的循环队列中，队头指针指向队头元素的（ A ）位置。 A．前一个 B．后一个 C．后面 D．当前 25．四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队头元素是（ B ）。 A． A B． B C． C D． D