数据结构习题(3)

后边。

Move5（list r，int n）

11

第三章 栈和队列

一、单项选择题

1. 对于栈操作数据的原则是（ ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 1.链式栈与顺序栈相比，一个比较明显的优点是( ) A.插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便

2.在一个顺序存储的循环队列中，队头指针指向队头元素的( )

A.前一个位置 B.后一个位置 C.队头元素位置 D.队尾元素的前一位置 3.栈和队列都是（ ）。

A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存储点的线性结构 D.限制存储点的非线性结构

4.设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是( ) 。 A.1,2,3,4,5 B.1,4,3,2,5 C.4，1,3,2,5 D.1,3,2,5,4

5. 假定一个带头结点的链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL

6. 设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为（ ）次。 A．n B．n+1 C．n+2 D．n-1 7.向顺序栈中压入新元素时，应当（ ）。

A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行 8.用单链表表示的链式队列的队头在链表的（ ）位置。

A．链头 B．链尾 C．链中 D.任意位置 9.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。 A. n-2 B. n-1

C. n

D. n+1

10．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）

A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 11．由两个栈共享一个向量空间的好处是：（ ）

A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率

12

C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率 12. 对于栈操作数据的原则是（ ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

13. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点.

B. 其中一个栈的栈顶到达栈空间的中心点.

C. 两个栈的栈顶在栈空间的某一位置相遇.

D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 14. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）

A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop

15. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 16. 栈和队列的共同点是（ ）。

A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点

18. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的

19. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 20. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。 A．top=top+1; V [top]=x B. V [top]=x; top=top+1 C. top=top-1; V [top]=x D. V [top]=x; top=top-1

21. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底

13

在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。

A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 22. 栈在（ ）中应用。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 23. 一个递归算法必须包括（ ）。

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 24. 执行完下列语句段后，i值为：（ ） int f(int x)

{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));

A．2 B. 4 C. 8 D. 无限递归 25. 表达式a*(b+c)-d的后缀表达式是( )。

A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd

26. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈

27. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改

28. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。

A．仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

29. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表

30. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m

31. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )

14

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

32. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对 33. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。

A. (rear+1) MOD n=front B. rear=front

C．rear+1=front D. (rear-l) MOD n=front

34. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A． 6 B. 4 C. 3 D. 2

二、填空题

1．若一个栈以数组V[1..n]存储，初始栈顶指针为top，元素X的入栈操作为______________。 2. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为___________的线性表。 3. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_________的对象。

4.设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为 。

5.通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。

6.在一个链式栈中，若栈顶指针等于NULL则为________。 7．栈顶的位置是随着_____操作而变化的。

8．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个队列元素时，头指针 。

9.循环队列用数组A[0..m-1]存放其元素值。已知其头尾指针分别是front和rear，则当前队列中的元素个数是 ，判断队空的条件是 。

10．循环队列Q中，front和rear分别指示队列头元素及队尾元素的位置，最大队列长度为maxsize，则判断队空的条件是 ，队满的条件是 。

11.队列的插入操作在 进行，删除操作在 进行。

12.在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个队列元素时，头指针 。

13．栈是___ ____的线性表，其运算遵循_______的原则。 14．____ ___是限定仅在表尾进行插入或删除操作的线性表。

15. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题(3)在线全文阅读。