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

数据结构习题练习目录

这次题目间换行还加了句号占位置,应该会更有区分度。

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

单项选择题

  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. 试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1, a2,…. an)逆置为(an, an-1,…., a1)。
  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(最多元素为 m0)为空的条件是__
    A. ST—> top !=0 B. ST—> top==0
    C. ST—> top !=m0 D. ST—> top==m0
    这里的栈是顺序栈,不是链栈,因为栈的top保存的是数值,
    顺序栈的top可以为数值,也能为指针,链栈只能为指针,
    顺序栈的指针保存可参考:数据结构简单入门/复习(三)-栈与队列(C语言)
    空栈的top是0,满栈top是m0(只保存了m0个元素,若保存方式不同,也可能为m0+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.试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1, a2,…. an)逆置为(an, an-1,…., a1)。
见函数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

数值栈运算符栈
A
数值栈运算符栈
A
数值栈运算符栈
B
A
数值栈运算符栈
B*
A
数值栈运算符栈
C
B*
A
数值栈运算符栈
B*C
A
数值栈运算符栈
B*C/
A
数值栈运算符栈
D
B*C/
A
数值栈运算符栈
B*C/D
A
数值栈运算符栈
B*C/D+
A
数值栈运算符栈
A-B*C/D+(注1)
数值栈运算符栈
E
A-B*C/D+
数值栈运算符栈
E
A-B*C/D+
数值栈运算符栈
F
E
A-B*C/D+
数值栈运算符栈
E↑F
A-B*C/D+
数值栈运算符栈
A-B*C/D+E↑F

若按书3-2所示,运算栈的栈底还有个#,但为了美观,这里省略。
整体的思想是,将所有运算符的优先级列出,在入栈时作比较,
若新元素优先级高,则将新元素入栈。
若新元素优先级低,则退栈一次,并将新结果入栈,再将新元素入栈。
若新元素为右括号(在优先级表中优先级相等),则退栈一次。

注1:上一次栈结果中的-在栈顶,+在栈底,+退栈,
实际上是两步结合,是+先退栈,再-入栈,
这是为了方便辨认出比较过程。

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注