计算机专业基础综合数据结构（栈、队列和数组）模拟试卷1
单选题
1.栈和队列的主要区别在于( )。(D)
A. 它们的逻辑结构不一样
B. 它们的存储结构不一样
C. 所包含的运算不一样
D. 插入和删除运算的限定不一样
解析：栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。任何数据结构在针对具体问题时所包含的运算都可能不同。所以正确答案是D。
2.若循环队列以数组Q[0.，m—1]作为其存储结构，变量rear表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)MOD m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。(C)
A. reat一length
B. (rear—length+m)MOD m
C. (rear—length+1+m)MOD m
D. m—length
解析：按照循环队列的定义，因为元素移动按照rear=(rear+1)MOD m进行，则当数组Q[m—1]存放了元素之后，下一个入队的元素将存放到Q[O]中，因此队列的首元素的实际位置是(rear—length+1+m)MOD m。
3.一个以向量V[n]存储的栈，其初始栈顶指针top为n+1，则对于x，其正确的进栈操作是( )。(C)
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
解析：此题考查的知识点是入栈的具体操作。操作时要看栈顶的地址，先取得空间，再入栈。本题栈项为n+1，应该用减法，所以选C。D是先存入，破坏原有数据，所以错。
4.为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在( )。(C)
A. 内存空间的首地址
B. 内存空间的尾地址
C. 内存空间的两端
D. 内存空间的中间
解析：两个栈共享一个内存空间时，需要把两个栈的栈底设在内存空间的两端。
5.已知输入序列为abed，经过输出受限的双端队列后，能得到的输出序列是( )。(B)
A. daeb
B. eadb
C. dbea
D. 以上答案都不对
解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。
分析选项A，输入序列为abcd，输出序列为dacb，由输出受限性质可知以da开头的结果只有dabc，选项A为错误答案。
分析选项B，输入序列为abcd，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入b，这时队列中的序列为ba。再在输出端输入c，这时队列中的序列为bac；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输出d，再输出b。最后得到输出序列为cadb。
分析选项C，输入序列为abcd，输出序列为dbca，由输出受限性质可知以db开头的结果只有dbac，选项C为错误答案。
6.假设一个序列1，2，3，…，n依次进栈，如果出栈的第一个元素是n，那么第i(1≤i≤n)个出栈的元素是( )。(B)
A. 不确定
B. n—i+1
C. i
D. n—i
解析：进栈的顺序是：1，2，…，n，且出栈的第一个元素是n，那么根据栈后进先出的特点可知，出栈的顺序依次为：n，…，2，1，那么第n—i+1个出栈元素就是第i个进栈的元素。
7.假设一个序列1，2，3，…，n依次进栈，如果第一个出栈的元素是i，那么第j个出栈的元素是( )。(D)
A. i-j一1
B. i-j
C. j-i+1
D. 不确定的
解析：此题考查的知识点是栈的后进先出特点。若输出序列的第一个元素是i，只能说明前i—1个元素均入栈，而第j个元素何时入、出栈并不能确定，所以选D。
8.已知当前栈中有n个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为( )。(B)
A. n一1
B. n
C. n+1
D. n／2
解析：由于栈中有n个元素是执行进栈操作，但是发生上溢，则说明此栈中最多可以包含n个数据元素，即栈的最大容量为n。
9.设有5个元素a，b，c，d，e顺序进栈，下列几个选项中，不可能的出栈序列是( )。(C)
A. a，b，c，d，e
B. d，e，c，b，a
C. a，c，e，b，d
D. c，b，a，d，e
解析：由进栈出栈规则可知，对于a，b，c，d，e顺序进栈的五个元素，A、B、D均为可能的出栈序列，所以选C。
10.有6个元素按6，5，4，3，2，1的顺序依次进栈，不合法的出栈序列是( )。(C)
A. 543612
B. 453126
C. 346521
D. 234．156
解析：此题考查的知识点是栈的后进先出特点。考查出栈序列，要保证先入栈的一定不能在后入栈的前面出栈，C选项中的6在5前入栈，5没有出栈，6却出栈了，所以不合法。其他都符合规律。所以选C。
11.有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈的次序不包括( )。(D)
A. CDEBA
B. CDBEA
C. CDBAE
D. CDAEB
解析：以元素C，D最先出栈的次序有三个：CDEBA、CDBEA、CDBAE。
12.对于4个元素依次进栈，可以得到( )种出栈序列。(C)
A. 10
B. 12
C. 14
D. 16
解析：n个入栈元素可得到
本文档预览：3000字符，共16365字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
