数据结构(栈)练习题与答案

1、栈的“先进后出”特性是指（ ）。 A.最后进栈的元素总是最先出栈 B.同时进行进栈和出栈操作时，总是进栈优先 C.每当有出栈操作时，总要先进行一次进栈操作 D.每次出栈的元素总是最先进栈的元素 正确答案：A 2、给定一个足够大的空栈，有4个元素的进栈次序为A、B、C、D，则以C、D开头的出栈序列的个数为（ ）。 A.1 B.2 C.3 D.4 正确答案：A 解析：若出栈序列为CD…，则A、B、C进栈，C出栈，D进栈，D出栈，此后只有B出栈和A出栈一种情况，所以这样的出栈序列只有CDBA一个。 3、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是（ ）。 A.dcebfa B.cbdaef C.bcaefd D.afedcb 正确答案：D 解析：选项A操作：a进，b进，c进，d进，d出，c出，e进，e出，b出，f进，f出，a出。 选项B操作：a进，b进，c进，c出，b出，d进，d出，a出，e进，e出，f进，f出。 选项C操作：a进，b进，b出，c进，c出，a出，d进，e进，e出，f进，f出，d出。 选项D操作：a进，a出，b进，c进，d进，e进，f进，f出，e出，d出，c出，b出。 从中看到，选项D中最后连续出栈5次，不符合要求。 4、一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（ ）。 A.edcba B.decba C.dceab D.abcde 正确答案：C 解析：对于选项A，a、b、c、d、e进栈，e、d、c、b、a出栈； 对于选项B，a，b，c，d进栈，d出栈，e进栈，e出栈，c、b、a依次出栈； 对于选项C，a、b、c、d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈底到栈顶为a、b，不可能a先出栈，所以C是不可能的输出序列； 对于选项D，a进栈，a出栈，b进栈，b出栈，c进栈，c出栈，d进栈，d出栈，e进栈，e出栈。 5、当用一个数组data[0..n-1]存放栈中元素时，栈底最好（ ）。 A.设置在data[0]处 B.设置在data[n-1]处 C.设置在data[0]或data[n-1]处 D.设置在data数组的任何位置 正确答案：C 解析：栈中元素的逻辑关系呈现线性关系，这样有两个端点，最好将栈底设置在某个端点data[0]或data[n-1]处，从而方便栈运算算法的设计。 6、若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进栈的正确操作是（ ）。 A.top++; data[top]=x; B.data[top]=x; top++; C.top--; data[top]=x; D.data[top]=x; top--; 正确答案：C 7、若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进栈的正确操作是（ ）。 A.top++; data[top]=x; B.data[top]=x; top++; C.top--; data[top]=x; D.data[top]=x; top--; 正确答案：A 解析：初始栈顶指针top为0，说明data[1]端作为栈底，在进栈时top应递增，由于不存在data[0]的元素，所以在进栈时应先将top递增，再将x放在top处 8、在设计链栈时，通常采用单链表作为链栈，而不采用双链表作为链栈，其准确的原因是（ ）。 A.栈中元素是顺序存取的，用单链表就足够了 B.栈中元素是随机存取的，用单链表就足够了 C.双链表运算较单链表更复杂 D.双链表存储密度较单链表低 正确答案：A 解析：因为栈中元素是顺序存取的（指逐个存或取结构中的元素），而不是随机存取的，用单链表就足够了。 9、栈和队列的不同点是（ ）。 A.都是线性表 B.都不是线性表 C.栈只能在同一端进行插入删除操作，而队列在不同端进行插入删除操作 D.没有不同点 正确答案：C 解析：栈和队列的不同点是，栈在同一端进行插入和删除操作，而队列在不同端进行插入和删除操作。 10、设循环队列qu中数组data的下标是0～N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），元素x进队的操作是（ ）;qu.data[qu.rear]=x。 A.qu.rear++ B.qu.rear=(qu.rear+1)%N C.qu.front++; D.qu.front=(qu.front+1)%N 正确答案：B 解析：对于循环队列，进队操作仅移动队尾指针，元素x进队的操作是：qu.rear=(qu.rear+1)%N; qu.data[qu.rear]=x。 11、设循环队列qu中数组data的下标是0～N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），元素x出队的操作是（ ）;x=qu.data[qu.front]。 A.qu.rear++ B.qu.rear=(qu.rear+1)%N C.qu.front++; D.qu.front=(qu.front+1)%N 正确答案：D 解析：对于循环队列，出队操作仅移动队头指针，元素x出队的操作是：qu.front=(qu.front+1)%N;x=qu.data[qu.rear]。 12、若某循环队列有队首指针front和队尾指针rear，在队不空时出队操作仅会改变（ ）。 A.front B.rear C.front和rear D.以上都不对 正确答案：A 解析：当循环队列不空时，出队操作只能改变队头指针front。 13、通常设置循环队列qu的队空条件（front队首指针指向队首元素的前一位置，rear队尾指针指向队尾元素）是（ ）。 A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B.(qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 正确答案：D 解析：在循环队列中，通常设置队头等于队尾时表示队空。 14、设循环队列的存储空间为a[0..20]，且当前队头指针（f指向队首元素的前一位置）和队尾指针（r指向队尾元素）的值分别为8和3，则该队列中元素个数为（ ）。 A.5 B.6 C.16 D.17 正确答案：C 解析：这里MaxSize=21，其中的元素个数=(r-f+MaxSize)%MaxSize=16。 15、假设用一个不带头节点的单链表表示队列，队头在链表的（ ）位置。 A.链头 B.链尾 C.链中 D.以上都可以 正确答案：A 解析：在用单链表表示的链队中，以单链表的链头作为队头，以单链表的链尾作为队尾。 16、与顺序队相比，链队（ ）。 A.优点是可以实现无限长队列 B.优点是进队和出队时间性能更好 C.缺点是不能进行顺序访问 D.缺点是不能根据队首和队尾指针计算队的长度 正确答案：D 解析：尽管链队总是采用动态分配方式，其长度也受内存大小的限制，也不可能实现无限长队列。顺序队和链队的进队和出队操作时间均为O(1)。顺序队和链队都可以进行顺序访问。在顺序队中可以通过队头和队尾指针计算队中元素个数，而链队不能。 17、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。 A.1和5 B.2和4 C.4和2 D.5和1 正确答案：B 解析：rear=0，进队2个元素后，rear循环递增2，rear=2；front=3，出队一个元素后，front循环递增1，front=4。 18、一个循环队列中用data[0..n-1]数组保存队中元素，另设置一个队尾指针rear和一个记录队中实际元素个数的变量count，则该队中最多可以存放的元素个数是（ ）。 A.n-1 B.n C.(rear+n) % n D.(n-rear) % n 正确答案：B 解析：队满的条件为count==n。 19、已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（ ）。 A.0，0 B.0，n-1 C.n-1，0 D. n-1，n-1 正确答案：B 解析：在循环队列中，进队操作是队尾指针rear循环加1，再在该处放置进队的元素，本题要求第一个进入队列的元素存储在A[0]处，则rear应为n-1，因为这样(rear+1)%n=0。而队头指向队头元素，此时队头位置为0，所以front的初值为0。 20、在循环队列中，元素的排列顺序（ ）。 A.由元素进队的先后顺序确定 B.与元素值的大小有关 C.与队头和队尾指针的取值有关 D.与队中数组大小有关 正确答案：A 解析：在循环队列中，元素的排列顺序仅与元素进队的先后顺序有关。