公共基础——数据结构与算法2
数据结构与算法
1、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是( )。
A、12345ABCDE B、EDCBA54321
C、ABCDE12345 D、 54321EDCBA
参考答案：B【解析】栈是先进后出的原则组织数据，所以入栈最早的最后出栈，所以选择B。
2、下列叙述中正确的是( )。
A、栈是一种先进先出的线性表
B、队列是一种后进先出的线性表
C、栈与队列都是非线性结构
D、以上三种说法都不对
参考答案：D【解析】栈是一种先进后出的线性表，队列是一种先进先出的线性表，栈与队列都是线性结构。
3、下列关于栈叙述正确的是( )。
A、算法就是程序
B、 设计算法时只需要考虑数据结构的设计
C、 设计算法时只需要考虑结果的可靠性
D、以上三种说法都不对
参考答案：D【解析】算法是指解题方案的准确而完整的描述，算法不等于程序，也不等于计算方法，所以A错误。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。
4、下列叙述中正确的是( )。
A、有一个以上根结点的数据结构不一定是非线性结构
B、只有一个根结点的数据结构不一定是线性结构
C、循环链表是非线性结构D、双向链表是非线性结构
参考答案：B【解析】线性结构应满足：有且只有一个根结点与每个结点最多有一个前件，也最多有一个后件，所以B正确。所以有一个以上根结点的数据结构一定是非线性结构，所以A错误。循环链表和双向链表都是线性结构的数据结构。
5、下列关于栈的叙述中，正确的是（ ）。
A、栈底元素一定是最后入栈的元素
B、 栈顶元素一定是最先入栈的元素
C、栈操作遵循先进后出的原则
D、以上说法均错误
参考答案：C【解析】栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈的修改是按后进先出的原则进行的。因此，栈称为先进后出表，或"后进先出"表，所以选择C。
6、下列关于栈的叙述中，正确的是（ ）。
A、栈底元素一定是最后入栈的元素
B、 栈顶元素一定是最先入栈的元素
C、栈操作遵循先进后出的原则
D、以上说法均错误
参考答案：C【解析】栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈的修改是按后进先出的原则进行的。因此，栈称为先进后出表，或"后进先出"表，所以选择C。
8、下列数据结构中，能够按照"先进后出"原则存取数据的是( )。
A、循环队列 B、栈 C、 队列 D、二叉树
参考答案：B【解析】栈是按先进后出的原则组织数据的。队列是先进先出的原则组织数据。
9、下列与队列结构有关联的是（ ）。
A、函数的递归调用 B、数组元素的引用
C、多重循环的执行 D、先到先服务的作业调度
参考答案：D【解析】队列的修改是依先进先出的原则进行的，D正确。
10、下列叙述中正确的是( )。
A、循环队列有队头和队尾两个指针，因此，循环队列是非线性结构
B、在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
C、在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
D、循环队列中元素的个数是由队头指针和队尾指针共同决定
参考答案：D【解析】循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的，所以A错误；在循环队列中只需要队头指针与队尾两个指针来共同反映队列中元素的动态变化情况，所以B与C错误。
11、下列数据结构中，属于非线性结构的是( )。
A、循环队列 B、 带链队列 C、二叉树 D、 带链栈
参考答案：C【解析】树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构。
12、对于循环队列，下列叙述中正确的是( )。
A、队头指针是固定不变的
B、队头指针一定大于队尾指针
C、队头指针一定小于队尾指针
D、队头指针可以大于队尾指针，也可以小于队尾指针
参考答案：D【解析】循环队列的队头指针与队尾指针都不是固定的，随着入队与出队操作要进行变化。因为是循环利用的队列结构所以对头指针有时可能大于队尾指针有时也可能小于队尾指针。
13、下列关于栈叙述正确的是( )。
A、栈顶元素最先能被删除 B、栈顶元素最后才能被删除
C、栈底元素永远不能被删除 D、 栈底元素最先被删除
参考答案：A解析】栈是先进后出的数据结构，所以栈顶元素最后入栈却最先被删除。栈底元素最先入栈却最后被删除。所以选择A。
14、设循环队列的存储空间为Q(1: 35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为（ ）。
A、 15 B、 16 C、20 D、 0或35
参考答案：D【解析】在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。在循环队列中进行出队、入队操作时，头尾指针仍要加１，朝前移动。只不过当头尾指针指向向量上界时，其加１操作的结果是指向向量的下界０。由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时，头尾指针均相等。答案为D选项。
15、 下列叙述中正确的是（ ）。
A、循环队列中的元素个数随队头指针与队尾指针的变化而动态变化
B、循环队列中的元素个数随队头指针的变化而动态变化
C、循环队列中的元素个数随队尾指针的变化而动态变化
D、以上说法都不对
参考答案：A【解析】在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。所以循环队列中的元素个数与队头指针和队尾指针的变化而变化，A正确。
16、下列叙述中正确的是( )。
A、循环队列有队头和队尾两个指针，因此，循环队列是非线性结构
B、在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
C、在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
D、循环队列中元素的个数是由队头指针和队尾指针共同决定
参考答案：D【解析】循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的，所以A)错误；在循环队列中只需要队头指针与队尾两个指针来共同反映队列中元素的动态变化情况，所以B与C错误。
17、 支持子程序调用的数据结构是( )。
A、栈 B、树 C、队列 D、二叉树
参考答案：A【解析】栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点，因此本题的答案为A。