数据结构习题练习（二）-顺序表示(线性表、栈和队列)-插入有序顺序表/顺序表的就地逆置

数据结构习题练习目录 这次题目间换行还加了句号占位置，应该会更有区分度。

直到看到下章题目是链表（线性表、栈和队列），我才意识到，
原来这个顺序表示还是个形容词，不只是名词…
怪不得这里面题目都用顺序存储。

单项选择题

1. 一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是__。
   A. 110 B. 108 C. 100 D. 120
2. 一个栈的入栈序列 a，b，c，d，e，则栈的不可能的输出序列是__。
   A. edcba B. decba C. dceab D. abcde
3. 若已知一个栈的入栈序列是 1，2，3，„，n，其输出序列为 p1，p2，p3，„，pn，若 p1=n，则 pi 为__。
   A. i B. n=i C. n-i+1 D. 不确定
4. 栈结构通常采用的两种存储结构是__。
   A. 顺序存储结构和链式存储结构
   B. 散列方式和索引方式
   C. 链表存储结构和数组
   D. 线性存储结构和非线性存储结构
5. 判定一个栈 ST（最多元素为 m0）为空的条件是__。
   A. ST—> top !=0 B. ST—> top==0
   C. ST—> top !=m0 D. ST—> top==m0
6. 判定一个栈 ST（最多元素为 m0）为栈满的条件是__。
   A. ST—> top!=0 B. ST—> top==0
   C. ST—> top!=m0 D. ST—> top==m0
7. 栈的特点是__，队列的特点是__。
   A. 先进先出 B. 先进后出
8. 一个队列的入列序列是 1，2，3，4，则队列的输出序列是__ 。
   A. 4，3，2，1 B. 1，2，3，4
   C. 1，4，3，2 D. 3，2，4，1
9. 判定一个队列 QU（最多元素为 m0）为空的条件是__。
   A. QU—>rear—QU—>front==m0
   B. QU—>rear—QU—>front-1==m0
   C. QU—>front==QU—>rear
   D. QU—>front==QU—>rear+1
10. 判定一个队列 QU（最多元素为 m0, m0+1= =Maxsize）为满队列的条件是__。
    A. ((QU—>rear-QU—>front)+ Maxsize)% Maxsize ==m0
    B. QU—>rear—QU—>front-1==m0
    C. QU—>front==QU—>rear
    D. QU—>front==QU—>rear+1
11. 判定一个循环队列 QU（最多元素为 m0）为空的条件是__。
    A. QU—>front==QU—>rear
    B. QU—>front !=QU—>rear
    C. QU—>front==（QU—>rear+1）%m0
    D. QU—>front !=（QU—>rear+1）%m0
12. 判定一个循环队列 QU（最多元素为 m0）为满队列的条件是__。
    A. QU—>front==QU—>rear
    B. QU—>front!=QU—>rear
    C. QU—>front==（QU—>rear+1）%m0
    D. QU—>front!=（QU—>rear+1）%m0
13. 循环队列用数组 A[0，m-1]存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是__。
    A. (rear-front+m)%m B. rear-front+1
    C. rear-front-1 D. rear-front
14. 栈和队列的共同点是__。
    A. 都是先进后出 B. 都是先进先出
    C. 只允许在端点处插入和删除元素 D. 没有共同点

填空题

1. 向量、栈和队列都是__结构，可以在向量的__位置插入和删除元素；对于栈只能在__插入和删除元素；对于队列只能在__插入元素和__删除元素。
2. 向一个长度为 n 的向量的第 i 个元素（1≤i≤n+1）之前插入一个元素时，需向后移动__个元素。
3. 向一个长度为 n 的向量中删除第 i 个元素（1≤i≤n）时，需向前移动__个元素。
4. 向栈中压入元素的操作是__。（这里的操作指的是函数原理）
5. 对栈进行退栈时的操作是__。
6. 在一个循环队列中，队首指针指向队首元素的__。
7. 从循环队列中删除一个元素时，其操作是__。
8. 在具有 n 个单元的循环队列中，队满时共有__个元素。
9. 一个栈的输入序列是 12345，则栈的输出序列 43512 是__。
10. 一个栈的输入序列是 12345，则栈的输出序列 12345 是__。

算法设计题

1. 设顺序表 va 中的数据元数递增有序。试写一算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。
2. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a₁, a₂,…. a_n）逆置为(a_n, a_n-1,…., a₁)。
3. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2 节例 3—1 的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
   A-B*C/D+E↑F

单项选择题分析

1. 一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是__。
   A. 110 B. 108 C. 100 D. 120
   元素存储地址指的是第一个地址的位置，
   例如，一个长度为2，存储在100的元素，实际占用的地址是100与101，
   因此，第一个若为100，第二个就是102，以此类推，第五个为108.
   .
2. 一个栈的入栈序列 a，b，c，d，e，则栈的不可能的输出序列是__。
   A. edcba B. decba C. dceab D. abcde
   仅给出入栈序列，出栈序列是确定不了的，
   例如，a入栈，a出栈，b入栈，b出栈…e入栈，e出栈，的出/入栈序列是abcde，
   而abcde入栈后，edcba才出栈，出入栈的序列刚好颠倒，
   即，入栈的元素可在任意时候出栈。
   而C选项的dceab，已知入栈顺序有abc，而出栈时，c先于a出栈，a又先于b出栈，
   这是不可能的，abc的入栈，可能的出栈仅有abc/cba/acb。
   .
3. 若已知一个栈的入栈序列是 1，2，3，„，n，其输出序列为 p1，p2，p3，„，pn，若 p1=n，则 pi 为__。
   A. i B. n=i C. n-i+1 D. 不确定
   要注意，除了入栈顺序外，题目还给了第一个出栈的数，为n，
   也就是说，最后一个入栈的，是第一个出栈的，
   因此可以判断，元素全部入栈后，才开始出栈。
   因此选C。
   .
4. 栈结构通常采用的两种存储结构是__。
   A. 顺序存储结构和链式存储结构
   B. 散列方式和索引方式
   C. 链表存储结构和数组
   D. 线性存储结构和非线性存储结构
   顺序存储就是数组存储，链式存储就是结构体的链表，
   是知识点。
   .
5. 判定一个栈 ST（最多元素为 m₀）为空的条件是__。
   A. ST—> top !=0 B. ST—> top==0
   C. ST—> top !=m₀ D. ST—> top==m₀
   这里的栈是顺序栈，不是链栈，因为栈的top保存的是数值，
   顺序栈的top可以为数值，也能为指针，链栈只能为指针，
   顺序栈的指针保存可参考：数据结构简单入门/复习（三）-栈与队列（C语言）。
   空栈的top是0，满栈top是m₀（只保存了m₀个元素，若保存方式不同，也可能为m₀+1，区别在于插入元素时使用的是top++还是++top，我没见过++top，但实现起来的确是可以的）
   .
6. 判定一个栈 ST（最多元素为 m0）为栈满的条件是__。
   A. ST—> top!=0 B. ST—> top==0
   C. ST—> top!=m0 D. ST—> top==m0
   分析同第五题。
   .
7. 栈的特点是B. 先进后出，队列的特点是A. 先进先出。
   A. 先进先出 B. 先进后出
   知识点。
   .
8. 一个队列的入列序列是 1，2，3，4，则队列的输出序列是__ 。
   A. 4，3，2，1 B. 1，2，3，4
   C. 1，4，3，2 D. 3，2，4，1
   队列是先进先出，因此不像栈有多种出栈可能性。
   .
9. 判定一个队列 QU（最多元素为 m0）为空的条件是__。
   A. QU—>rear—QU—>front==m0
   B. QU—>rear—QU—>front-1==m0
   C. QU—>front==QU—>rear
   D. QU—>front==QU—>rear+1
   题目中的破折号是减号。
   不论是顺序还是链表存储，空队列时，队头队尾都相同，
   队尾或队头只有一个为0时，不一定是空队列，
   因为循环队列的队头与队尾没有被限制在0处。
   .
10. 判定一个队列 QU（最多元素为 m0, m0+1= =Maxsize）为满队列的条件是__。
    A. ((QU—>rear-QU—>front)+ Maxsize)% Maxsize ==m0
    B. QU—>rear—QU—>front-1==m0
    C. QU—>front==QU—>rear
    D. QU—>front==QU—>rear+1
    同上，如果不是循环队列，那么直接rear-front == m0即可，
    但既然答案给出了循环队列的大小公式，那就得当成循环队列了。
    例如队列存储在1 2 3 4 5 6中，队尾队头分别是 3 5，
    那么大小应该是3-5+6=4，而不是2，因为队列从队尾进，从队头出，
    此时如果插入元素，会插在队尾的后面，即4位置，插入后队尾后移，
    队尾队头为4 5，插入后差值变小，论证了(队尾-队头+m)%m才是元素个数。
    .
11. 判定一个循环队列 QU（最多元素为 m0）为空的条件是__。
    A. QU—>front==QU—>rear
    B. QU—>front !=QU—>rear
    C. QU—>front==（QU—>rear+1）%m0
    D. QU—>front !=（QU—>rear+1）%m0
    第九题讲到了，队头队尾相同时，队列为空。
    .
12. 判定一个循环队列 QU（最多元素为 m0）为满队列的条件是__。
    A. QU—>front==QU—>rear
    B. QU—>front!=QU—>rear
    C. QU—>front==（QU—>rear+1）%m0
    D. QU—>front!=（QU—>rear+1）%m0
    如第10题，通过循环队列的大小计算公式可知。
    当然凭感觉也能知道。
    .
13. 循环队列用数组 A[0，m-1]存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是__。
    A. (rear-front+m)%m B. rear-front+1
    C. rear-front-1 D. rear-front
    同第10题。
    .
14. 栈和队列的共同点是__。
    A. 都是先进后出 B. 都是先进先出
    C. 只允许在端点处插入和删除元素 D. 没有共同点
    AB首先排除，
    基本的栈和队列都是不能插队的，也就是不能在非端点处进行插入删除操作。

填空题分析

1. 向量、栈和队列都是线性结构，可以在向量的任意位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和队首删除元素。
   知识点。
   .
2. 向一个长度为 n 的向量的第 i 个元素（1≤i≤n+1）之前插入一个元素时，需向后移动n-i+1个元素。
   题目说长度为n，且i的取值范围有n+1个，
   则表示插入到第n+1个元素前，是插入到最后一个的意思，
   插入到最后一个无需后移元素，即因此答案为n-i+1。
   .
3. 向一个长度为 n 的向量中删除第 i 个元素（1≤i≤n）时，需向前移动n-i个元素。
   当i=n时，需向前移动0个元素，因此答案为n-i。
   .
4. 向栈中压入元素的操作是先移动栈顶指针，后存入元素。
   这题问的是函数实现原理，我第一眼都懵了。
   我一直用的是*(S.top++)=e;，是先存元素再移动指针，
   但书上给的例子是S.top++;S.data[S.top];，使先移动指针再存入元素。
   只能说自学是真的不行，这个知识点都能出题目了，我还用了其他的定义方式。
   .
5. 对栈进行退栈时的操作是先取出元素，后移动栈顶指针。
   因为退栈后，退栈元素无法被读取了，因此必须先取出元素，后移动指针。
   .
6. 在一个循环队列中，队首指针指向队首元素的前一个位置。
   循环队列中，队首不放元素，这样可以防止队满时Q.front==Q.rear，与队空冲突。
   因此，队首元素实际上是队首指针.next，
   即队首指针在队首元素前一个位置。
   .
7. 从循环队列中删除一个元素时，其操作是先移动队首元素，后取出元素。
   反着实现也可以，但既然题目这么出了，那大概就是这种操作时公认的吧。
   .
8. 在具有 n 个单元的循环队列中，队满时共有n-1个元素。
   这就是第6题提到的，队首指针不放元素导致的。
   .
9. 一个栈的输入序列是 12345，则栈的输出序列 43512 是不可能的。
   入栈为1234，且4第一个出，则1、2、3的出栈顺序必然是321。
   .
10. 一个栈的输入序列是 12345，则栈的输出序列 12345 是可能的。
    入一个出一个。
    .

算法设计题分析

1.设顺序表 va 中的数据元数递增有序。试写一算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。
见函数insertSortArray()
如果用realloc会更美观，但realloc只能重分配malloc生成的，
所以在insertSortArray用malloc函数新生成了返回数组。

2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a₁, a₂,…. a_n）逆置为(a_n, a_n-1,…., a₁)。
见函数transpose()

/* 
   1.设顺序表 va 中的数据元数递增有序。
   试写一算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。
   算法函数：insertSortArray()

   2.试写一算法，实现顺序表的就地逆置，
   即利用原表的存储空间将线性表（a1, a2,…. an）逆置为(an, an-1,…., a1)。
   算法函数：transpose()
*/

#include <stdio.h>
#include <stdlib.h>

int* transpose(int *va, int vaSize);
int* insertSortArray(int *va, int v, int vaSize);
void printArray(int *va, int vaSize);

int main() {
    int va[] = { 1,3,5,7,9 };
    int vaSize = sizeof(va)/sizeof(int);

    printArray(va, vaSize);
    //printArray(insertSortArray(va, 4, vaSize), vaSize+1);
    printArray(transpose(va, vaSize), vaSize);

    system("PAUSE");
    return 0;
}

int* insertSortArray(int *va, int v, int vaSize) {
    int i, *returnVa, hasInsert=0;
    returnVa = (int*)malloc(sizeof(int)*(vaSize + 1));
    for (i = 0; i<vaSize; i++) {
        if (va[i] > v && hasInsert == 0) {
            returnVa[i] = v;
            hasInsert = 1;
        }
        returnVa[i+hasInsert] = va[i];

    }
    return returnVa;
}

void printArray(int *va, int vaSize) {
    int i;
    for (i = 0; i < vaSize; i++) {
        printf("%d ", va[i]);
    }
    puts("");
}

int* transpose(int *va, int vaSize) {
    int i, temp;
    for (i = 0; i < vaSize / 2; i++) {
        temp = va[i];
        va[i] = va[vaSize - 1 - i];
        va[vaSize - 1 - i] = temp;
    }
    return va;
}

3.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2 节例 3—1 的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
A-B*C/D+E↑F