发布时间 : 星期一 文章数据结构练习 - 第三章 - 栈和队列更新完毕开始阅读
数据结构练习第三章 栈和队列
一、选择题
1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点
2．向顺序栈中压入新元素时，应当（ ）。
A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。
A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（ ）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的
队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（ ）的线性表。
A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除
9．设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ ）。
A. n-i B. n-1-i C. n+l -i D.不能确定
10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。
A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（ ）进行。
A．队首 B．队尾 C．队前 D．队后
12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。
A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（ ）进行。
1
A．队首 B．队尾 C．队前 D．队后 14．若已有一个栈，输入序列为A，B，C，D，E，那么下面哪种序列不可能得到？（ ）
A．ABCDE B．EDCBA C．BAEDC D．ECDBA (d) 注意: 入栈和出栈操作可以交替进行，因此就可能有多种输出序列了。 15．栈和队列共同具有的特点是（ ） A.都是先进后出 B.都是先进先出
C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出 16．若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（ ）
A.1和5 B.2和4 C.4和2 D.5和1 17．一个栈的入栈序列是a，b，c，d，e，则栈的输出序列不可能是( ) ．．．A. dceab B. decba C. edcba D. abcde 18．元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为( ) A. top=top B. top=n-1 C. top=top-1 D. top=top+1 19．设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( ) A.DCBA B.CDAB C.DBAC D.DCAB
20．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( )
A.top++ B.top-- C.top不变 D.top=0 21. 关于栈和队列的说法中正确的是（ ） A．栈和队列都是线性结构
B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构
22. 设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（ ） A．a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b
23. 在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ） A．front==rear B.(front+1)%m==rear C.rear+1==front D.(rear+1)%m==front 24. 循环队列存储在数组A[0..m]中，则入队时的操作为( D)。 A. rear=rear+1 B. rear=(rear+1) % (m-1) C. rear=(rear+1) % m D. rear=(rear+1) % (m+1)
25. 顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（ ） A.s.elem［top］=e； B.s.elem［top+1］=e； s.top=s.top+1； s.top=s.top+1； C.s.top=s.top+1； D.s.top=s.top+1； s.elem［top+1］=e； s.elem［top］=e；
2
26. 循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（ ）
A.8 B.16 C.17 D.18 27. 有关栈的描述，正确的是（ ） A.栈是一种先进先出的特殊的线性表 B.只能从栈顶执行插入、删除操作 C.只能从栈顶执行插入、栈底执行删除 D.栈顶和栈底均可执行插入、删除操作
28. 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。
A. R-F B. F-R C. (R-F+M)％M D. (F-R+M)％M 29. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为（ ）。
A．3,2,5,6,4,1 B．1,5,4,6,2,3
C．2,4,3,5,1,6 D．4,5,3,6,2,1
30. 设有一个栈，元素的进栈次序为A,B,C,D,E，则下列（ ）是不可能的出栈序列。
A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A
31．在具有N个单元的顺序存储循环队列中，假定front和rear分别为对头指针和对尾指针，则判断对满的条件为（ ）。
A．front== rear B．(rear+1)%MAXSIZE==front C．front-rear==1 D．rear%MAXSIZE==front 32．一个元素进入队列的时间复杂度是（ ）。
A．O(1) B．O(n) C．O(n2) D．O(log2n)
33．若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。 A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，2
34．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是（ ）。
A.front==NULL B.front!=NULL C.rear!=NULL D.front==rear
35．若让元素a，b，c依次进栈，则出栈次序不可能出现（ ）种情况。 A．cba B．bac C．cab D．acb
36．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作应执行（ ）。
A．front->next=s; front=s; B．s->next=rear; rear=s; C． rear->next=s; rear=s; D．s->next=front; front=s; 37．栈的插入与删除操作在（ ）进行。
A.栈顶 B.栈底 C.任意位置 D.指定位置
38．当利用大小为N的一维数组顺序存储一个栈时，假定用top=－1表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。
3
A．top++； B．top--； C．top=NULL ； D．top； 39．当采用顺序存储方式存储队列时，可能出现存储空间剩余，而不允许继续入队的情况，称为（ ）。
A．溢出 B． 假溢出 C．队列不能用顺序存储方式 D．数组存储空间过小 40．当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为（ ）。
A.N-2 B.N-1 C.N D.N+1 41．从一个循环顺序队列删除元素时，首先需要（ ）。 A.前移一位队首指针 B.后移一位队首指针
C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 42．循环队列存储在数组A[0..m]中，则入队时的操作为( )。 A. rear=rear+1 B. rear=(rear+1) % (m-1) C. rear=(rear+1) % m D. rear=(rear+1) % (m+1) 43．4个园盘的Hahoi塔，总的移动次数为( )。
A.7 B. 8 C.15 D.16 44．对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
45．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 46．设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4，
47．如进栈序列1，2，3，4，5。可能得到的出栈序列为( )
A．1,2,5,3,4 B．3,1,2,5,4 C．3,2,5,4,1 D．1,4,2,3,5 E．都不可能
48．一个栈的入栈序列为A,B,C,D,E，则栈的不可能的出栈序列是( )。 A. ABCDE B. EDCBA C. DECBA D.DCEAB 49．function calc(x,y :integer) : integer; begin
if y=1 then calc :=x
else calc := calc (x,y-1)+x end;
a,b均为正整数，则 calc(a,b)=( )
A.a*(b-1) B. a*b C. a+b D. a+a 50．执行完下列语句段后，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. 无限递归 51．表达式a*(b+c)-d的后缀表达式是( )。
A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 52．允许对队列进行的操作有( )。
4