已阅:
161
数据结构习题练习目录
这次题目间换行还加了句号占位置,应该会更有区分度。
直到看到下章题目是链表(线性表、栈和队列),我才意识到,
原来这个顺序表示还是个形容词,不只是名词…
怪不得这里面题目都用顺序存储。
单项选择题
- 一个向量第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址是__。
A. 110 B. 108 C. 100 D. 120 - 一个栈的入栈序列 a,b,c,d,e,则栈的不可能的输出序列是__。
A. edcba B. decba C. dceab D. abcde - 若已知一个栈的入栈序列是 1,2,3,„,n,其输出序列为 p1,p2,p3,„,pn,若 p1=n,则 pi 为__。
A. i B. n=i C. n-i+1 D. 不确定 - 栈结构通常采用的两种存储结构是__。
A. 顺序存储结构和链式存储结构
B. 散列方式和索引方式
C. 链表存储结构和数组
D. 线性存储结构和非线性存储结构 - 判定一个栈 ST(最多元素为 m0)为空的条件是__。
A. ST—> top !=0 B. ST—> top==0
C. ST—> top !=m0 D. ST—> top==m0 - 判定一个栈 ST(最多元素为 m0)为栈满的条件是__。
A. ST—> top!=0 B. ST—> top==0
C. ST—> top!=m0 D. ST—> top==m0 - 栈的特点是__,队列的特点是__。
A. 先进先出 B. 先进后出 - 一个队列的入列序列是 1,2,3,4,则队列的输出序列是__ 。
A. 4,3,2,1 B. 1,2,3,4
C. 1,4,3,2 D. 3,2,4,1 - 判定一个队列 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 - 判定一个队列 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 - 判定一个循环队列 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 - 判定一个循环队列 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 - 循环队列用数组 A[0,m-1]存放其元素值,已知其头尾指针分别是 front 和 rear,则当前队列中的元素个数是__。
A. (rear-front+m)%m B. rear-front+1
C. rear-front-1 D. rear-front - 栈和队列的共同点是__。
A. 都是先进后出 B. 都是先进先出
C. 只允许在端点处插入和删除元素 D. 没有共同点
填空题
- 向量、栈和队列都是__结构,可以在向量的__位置插入和删除元素;对于栈只能在__插入和删除元素;对于队列只能在__插入元素和__删除元素。
- 向一个长度为 n 的向量的第 i 个元素(1≤i≤n+1)之前插入一个元素时,需向后移动__个元素。
- 向一个长度为 n 的向量中删除第 i 个元素(1≤i≤n)时,需向前移动__个元素。
- 向栈中压入元素的操作是__。(这里的操作指的是函数原理)
- 对栈进行退栈时的操作是__。
- 在一个循环队列中,队首指针指向队首元素的__。
- 从循环队列中删除一个元素时,其操作是__。
- 在具有 n 个单元的循环队列中,队满时共有__个元素。
- 一个栈的输入序列是 12345,则栈的输出序列 43512 是__。
- 一个栈的输入序列是 12345,则栈的输出序列 12345 是__。
算法设计题
- 设顺序表 va 中的数据元数递增有序。试写一算法,将 x 插入到顺序表的适当位置上,以保持该表的有序性。
- 试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1, a2,…. an)逆置为(an, an-1,…., a1)。
- 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,并仿照教科书3.2 节例 3—1 的格式,画出对下列算术表达式求值时操作数栈和运算符栈的变化过程:
A-B*C/D+E↑F
单项选择题分析
- 一个向量第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址是__。
A. 110 B. 108 C. 100 D. 120
元素存储地址指的是第一个地址的位置,
例如,一个长度为2,存储在100的元素,实际占用的地址是100与101,
因此,第一个若为100,第二个就是102,以此类推,第五个为108.
. - 一个栈的入栈序列 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。
. - 若已知一个栈的入栈序列是 1,2,3,„,n,其输出序列为 p1,p2,p3,„,pn,若 p1=n,则 pi 为__。
A. i B. n=i C. n-i+1 D. 不确定
要注意,除了入栈顺序外,题目还给了第一个出栈的数,为n,
也就是说,最后一个入栈的,是第一个出栈的,
因此可以判断,元素全部入栈后,才开始出栈。
因此选C。
. - 栈结构通常采用的两种存储结构是__。
A. 顺序存储结构和链式存储结构
B. 散列方式和索引方式
C. 链表存储结构和数组
D. 线性存储结构和非线性存储结构
顺序存储就是数组存储,链式存储就是结构体的链表,
是知识点。
. - 判定一个栈 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,但实现起来的确是可以的)
. - 判定一个栈 ST(最多元素为 m0)为栈满的条件是__。
A. ST—> top!=0 B. ST—> top==0
C. ST—> top!=m0 D. ST—> top==m0
分析同第五题。
. - 栈的特点是B. 先进后出,队列的特点是A. 先进先出。
A. 先进先出 B. 先进后出
知识点。
. - 一个队列的入列序列是 1,2,3,4,则队列的输出序列是__ 。
A. 4,3,2,1 B. 1,2,3,4
C. 1,4,3,2 D. 3,2,4,1
队列是先进先出,因此不像栈有多种出栈可能性。
. - 判定一个队列 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处。
. - 判定一个队列 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才是元素个数。
. - 判定一个循环队列 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
第九题讲到了,队头队尾相同时,队列为空。
. - 判定一个循环队列 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题,通过循环队列的大小计算公式可知。
当然凭感觉也能知道。
. - 循环队列用数组 A[0,m-1]存放其元素值,已知其头尾指针分别是 front 和 rear,则当前队列中的元素个数是__。
A. (rear-front+m)%m B. rear-front+1
C. rear-front-1 D. rear-front
同第10题。
. - 栈和队列的共同点是__。
A. 都是先进后出 B. 都是先进先出
C. 只允许在端点处插入和删除元素 D. 没有共同点
AB首先排除,
基本的栈和队列都是不能插队的,也就是不能在非端点处进行插入删除操作。
填空题分析
- 向量、栈和队列都是线性结构,可以在向量的任意位置插入和删除元素;对于栈只能在栈顶插入和删除元素;对于队列只能在队尾插入元素和队首删除元素。
知识点。
. - 向一个长度为 n 的向量的第 i 个元素(1≤i≤n+1)之前插入一个元素时,需向后移动n-i+1个元素。
题目说长度为n,且i的取值范围有n+1个,
则表示插入到第n+1个元素前,是插入到最后一个的意思,
插入到最后一个无需后移元素,即因此答案为n-i+1。
. - 向一个长度为 n 的向量中删除第 i 个元素(1≤i≤n)时,需向前移动n-i个元素。
当i=n时,需向前移动0个元素,因此答案为n-i。
. - 向栈中压入元素的操作是先移动栈顶指针,后存入元素。
这题问的是函数实现原理,我第一眼都懵了。
我一直用的是*(S.top++)=e;
,是先存元素再移动指针,
但书上给的例子是S.top++;S.data[S.top];
,使先移动指针再存入元素。
只能说自学是真的不行,这个知识点都能出题目了,我还用了其他的定义方式。
. - 对栈进行退栈时的操作是先取出元素,后移动栈顶指针。
因为退栈后,退栈元素无法被读取了,因此必须先取出元素,后移动指针。
. - 在一个循环队列中,队首指针指向队首元素的前一个位置。
循环队列中,队首不放元素,这样可以防止队满时Q.front==Q.rear,与队空冲突。
因此,队首元素实际上是队首指针.next,
即队首指针在队首元素前一个位置。
. - 从循环队列中删除一个元素时,其操作是先移动队首元素,后取出元素。
反着实现也可以,但既然题目这么出了,那大概就是这种操作时公认的吧。
. - 在具有 n 个单元的循环队列中,队满时共有n-1个元素。
这就是第6题提到的,队首指针不放元素导致的。
. - 一个栈的输入序列是 12345,则栈的输出序列 43512 是不可能的。
入栈为1234,且4第一个出,则1、2、3的出栈顺序必然是321。
. - 一个栈的输入序列是 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
若按书3-2所示,运算栈的栈底还有个#,但为了美观,这里省略。
整体的思想是,将所有运算符的优先级列出,在入栈时作比较,
若新元素优先级高,则将新元素入栈。
若新元素优先级低,则退栈一次,并将新结果入栈,再将新元素入栈。
若新元素为右括号(在优先级表中优先级相等),则退栈一次。
注1:上一次栈结果中的-在栈顶,+在栈底,+退栈,
实际上是两步结合,是+先退栈,再-入栈,
这是为了方便辨认出比较过程。
近期评论