| 数据结构习题练习（二） | 您所在的位置：网站首页 › 栈满的条件是 › 数据结构习题练习（二） |
|
文章首发及后续更新：https://mwhls.top/1006.html 新的更新内容请到mwhls.top查看。 无图/格式错误请到上方的文章首发页面查看。 数据结构习题练习目录 这次题目间换行还加了句号占位置，应该会更有区分度。 直到看到下章题目是链表（线性表、栈和队列），我才意识到，原来这个顺序表示还是个形容词，不只是名词...怪不得这里面题目都用顺序存储。 单项选择题 一个向量第一个元素的存储地址是 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==0C. ST—> top !=m0 D. ST—> top==m0判定一个栈 ST（最多元素为 m0）为栈满的条件是__。A. ST—> top!=0 B. ST—> top==0C. ST—> top!=m0 D. ST—> top==m0栈的特点是__，队列的特点是__。A. 先进先出 B. 先进后出一个队列的入列序列是 1，2，3，4，则队列的输出序列是__ 。A. 4，3，2，1 B. 1，2，3，4C. 1，4，3，2 D. 3，2，4，1判定一个队列 QU（最多元素为 m0）为空的条件是__。A. QU—>rear—QU—>front==m0B. QU—>rear—QU—>front-1==m0C. QU—>front==QU—>rearD. QU—>front==QU—>rear+1判定一个队列 QU（最多元素为 m0, m0+1= =Maxsize）为满队列的条件是__。A. ((QU—>rear-QU—>front)+ Maxsize)% Maxsize ==m0B. QU—>rear—QU—>front-1==m0C. QU—>front==QU—>rearD. QU—>front==QU—>rear+1判定一个循环队列 QU（最多元素为 m0）为空的条件是__。A. QU—>front==QU—>rearB. QU—>front !=QU—>rearC. QU—>front==（QU—>rear+1）%m0D. QU—>front !=（QU—>rear+1）%m0判定一个循环队列 QU（最多元素为 m0）为满队列的条件是__。A. QU—>front==QU—>rearB. QU—>front!=QU—>rearC. QU—>front==（QU—>rear+1）%m0D. QU—>front!=（QU—>rear+1）%m0循环队列用数组 A[0，m-1]存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是__。A. (rear-front+m)%m B. rear-front+1C. 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==0C. 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==0C. ST—> top!=m0 D. ST—> top==m0分析同第五题。.栈的特点是B. 先进后出，队列的特点是A. 先进先出。A. 先进先出 B. 先进后出知识点。.一个队列的入列序列是 1，2，3，4，则队列的输出序列是__ 。A. 4，3，2，1 B. 1，2，3，4C. 1，4，3，2 D. 3，2，4，1队列是先进先出，因此不像栈有多种出栈可能性。.判定一个队列 QU（最多元素为 m0）为空的条件是__。A. QU—>rear—QU—>front==m0B. QU—>rear—QU—>front-1==m0C. QU—>front==QU—>rearD. QU—>front==QU—>rear+1题目中的破折号是减号。不论是顺序还是链表存储，空队列时，队头队尾都相同，队尾或队头只有一个为0时，不一定是空队列，因为循环队列的队头与队尾没有被限制在0处。.判定一个队列 QU（最多元素为 m0, m0+1= =Maxsize）为满队列的条件是__。A. ((QU—>rear-QU—>front)+ Maxsize)% Maxsize ==m0B. QU—>rear—QU—>front-1==m0C. QU—>front==QU—>rearD. 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—>rearB. QU—>front !=QU—>rearC. QU—>front==（QU—>rear+1）%m0D. QU—>front !=（QU—>rear+1）%m0第九题讲到了，队头队尾相同时，队列为空。.判定一个循环队列 QU（最多元素为 m0）为满队列的条件是__。A. QU—>front==QU—>rearB. QU—>front!=QU—>rearC. QU—>front==（QU—>rear+1）%m0D. QU—>front!=（QU—>rear+1）%m0如第10题，通过循环队列的大小计算公式可知。当然凭感觉也能知道。.循环队列用数组 A[0，m-1]存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是__。A. (rear-front+m)%m B. rear-front+1C. 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 #include 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 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- 数值栈运算符栈BA- 数值栈运算符栈B*A- 数值栈运算符栈CB*A- 数值栈运算符栈B*CA- 数值栈运算符栈B*C/A- 数值栈运算符栈DB*C/A- 数值栈运算符栈B*C/DA- 数值栈运算符栈B*C/D+A- 数值栈运算符栈A-B*C/D+(注1) 数值栈运算符栈EA-B*C/D+ 数值栈运算符栈E↑A-B*C/D+ 数值栈运算符栈FE↑A-B*C/D+ 数值栈运算符栈E↑FA-B*C/D+ 数值栈运算符栈A-B*C/D+E↑F若按书3-2所示，运算栈的栈底还有个#，但为了美观，这里省略。整体的思想是，将所有运算符的优先级列出，在入栈时作比较，若新元素优先级高，则将新元素入栈。若新元素优先级低，则退栈一次，并将新结果入栈，再将新元素入栈。若新元素为右括号（在优先级表中优先级相等），则退栈一次。 注1：上一次栈结果中的-在栈顶，+在栈底，+退栈，实际上是两步结合，是+先退栈，再-入栈，这是为了方便辨认出比较过程。 |
| CopyRight 2018-2019 实验室设备网 版权所有 |