D

[解析] 循环队列目前的元素个数可简单地用rear-front求得，如果所得为负数，再加数组总容量即可(若rear-front不为负数，则不加容量)。本题rear的值无从知晓，故元素个数不确定。

D

[解析] 存储空间为S(1:m)，说明存储空间为S[1]、S[2]、…、S[m]共m个空间，S[m]位于栈底，S[1]位于栈顶。初始状态top=m+1说明top不指向任何元素，栈为空。入栈与退栈操作使top变化，但只能在1～m+1范围内变化，top=m+1时表示栈空，top不可能为0。

D

[解析] 存储空间为S(1:m)，说明存储空间为S[1]、S[2]、…、S[m]共m个空间，由初始状态为top=0知S[1]位于栈底，S[m]位于栈顶。初始状态top=0说明top不指向任何元素，栈为空。入栈与退栈操作使top变化，但只能在0～m范围内变化，top=0时表示栈空，top不可能为m+1。

D

[解析] 存储空间为S[1:50)，说明存储空间为S[1]、S[2]、…、S[50]共50个空间，由初始状态为top=0知S[1]位于栈底，S[50]位于栈顶。初始状态top=0说明top不指向任何元素，栈为空。入栈与退栈操作使top变化，但只能在0～50范围内变化，top=0时表示栈空，top不可能为51。

D

[解析] 存储空间为S(1:60)，说明存储空间为S[1]、S[2]、…、S[60]共60个空间，S[60]位于栈底，S[1]位于栈顶。初始状态top=61说明top不指向任何元素，栈为空。入栈与退栈操作使top变化，top=1时，表示S[1]、S[2]、…、S[60]都具有元素，故有60个元素。

D

[解析] 堆栈既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的栈。带链的栈本身是个链表，需由各结点的指针域分别决定下一个元素，其中的元素必须由第一个元素一个链接一个地找下来，仅由top、bottom的值无法确定其中有几个元素。

D

[解析] 队列既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的队列。带链的队列本身是个链表，需由各结点的指针域分别决定下一个元素，其中的元素必须由第一个元素一个链接一个地找下来，仅由front、rear的值无法确定其中有几个元素。

B

[解析] 队列既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的队列。带链的队列空的条件是front=rear=NULL。现front与rear的值相等且不为NULL，说明链表中只有一个元素，故队列中的元素个数为1。

B

[解析] 队列既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的队列。带链的队列空的条件是front=rear=NULL。如front与rear的值相等且为NULL，说明链表为空(有0个元素)；如果相等且不为NULL，说明链表中有一个元素。

B

[解析] 堆栈既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的栈。带链的栈空的条件是top=bottom=NULL。如top=bottom且不为NULL，说明有一个元素。

B

[解析] 堆栈既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的栈。带链的栈空的条件是top=bottom=NULL。现top=bottom且不为NULL，说明有一个元素。

B

[解析] 存储空间为S(1:50)，说明存储空间为S[1]、S[2]、…、S[50]共50个空间，S[50]位于栈底，S[1]位于栈顶。初始状态top=51说明top不指向任何元素，栈为空。入栈与退栈操作使top变化，top=50时，表示只有S[50]这一个空间具有元素，故有一个元素。

B

[解析] 循环链表最末端结点的指针域不为0，而是又指回第一个结点的链表。队列既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)，而即使用链表存储也不一定要用循环链表存储。循环队列是队列采用数组存储，且当新数据在队尾用完最后一个空间后，还允许反过头来使用第一个空间。

C

[解析] 完全二叉树可以用数组按层次存储，即顺序存储结构，但它是非线性结构。双向链表每个结点有2个指针域：左指针域指向它的前一结点，右指针域指向它的后一结点。二叉树的链式存储结构也称为二叉树链表(二叉链表)，二叉链表是采用链式存储方式的二叉树，它的本质是树，因此是非线性结构。二叉链表与双向链表是两种不同的链表。多重链表是含有任意个数指针域的链表，也可以是线性结构。

B

[解析] 堆栈既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的栈。带链的栈空的条件是top=bottom=NULL。带链的栈各结点存储空间一般动态分配。虽然栈底一般不变，但如果栈底指针指向的元素出栈后，再入栈新元素，由于新元素的空间动态分配，因而栈底指针也是会变化的。队列既可用数组存储(称为顺序存储)，也可用链表存储(称为链式存储)。用链表存储时，又称为带链的队列。带链的队列空的条件是front=rear=NULL，而不能仅仅是front=rear；如front=rear且它们不为NULL，说明有一个元素。

B

[解析] 循环队列的队头指针与队尾指针相同可能队列空，也可能队列满。

C

[解析] 循环队列目前的元素个数可简单地用rear-front求得，如果所得为负数，再加数组总容量即可(若rear-front不为负数，则不加容量)。带链的队列和带链的栈本身都是链表，需由各结点的指针域分别决定下一个元素，其中的元素必须由第一个元素一个链接一个地找下来，仅由指针的值无法确定其中有几个元素。

D

[解析] 只有完全二叉树才能采用顺序存储(即按数组方式将二叉树一层一层存储)，非完全二叉树前面各层可能缺少一些结点，无法按顺序一层一层存储，因为无法存储缺少哪些结点。

C

[解析] 在栈中，只能在栈顶进行插入和删除，栈顶指针的动态变化就可决定栈中元素的个数。循环队列目前的元素个数可简单地用rear-front求得，如果所得为负数，再加数组总容量即可(若rear-front不为负数，则不加容量)。链表需由各结点的指针域分别决定下一个元素，其中的元素必须由第一个元素一个链接一个链接地找下来，仅由指针的值无法确定其中有几个元素。

C

[解析] 可根据R中两两元素对画图如下：f-a-c-e-d-b，每元素前后各有一个元素(除首尾外)，则是线性结构。

D

[解析] 可根据R中两两元素对画图如下：a-b-c-d-e-f-(又指回a)，构成回路，因而是非线性结构。

A

[解析] 循环队列目前的元素个数可简单地用rear-front求得，如果所得为负数，再加数组总容量即可(若rear-front不为负数，则不加容量)。front=rear=25时，元素个数为0或0+50=50。若元素个数为0，插入一个元素，则元素个数为1；若元素个数为50，说明队列已满，再插入一个元素无法容纳，会发生溢出错误(上溢错误)。

C

[解析] 在链式存储的有序表中无法进行二分查找，仍然进行顺序查找。平均情况是(n+1)/2次，最坏情况是n次。寻找最大项无论如何都要查看所有的数据，与数据原始排列顺序没有多大关系，无所谓最坏情况和最好情况，或说平均情况与最坏情况下的时间复杂度是相同的。在顺序存储的线性表中进行对分查找，最坏比较log₂n次，最好比较一次，显然平均不是log₂n次。

B

[解析] 在最坏情况下，冒泡排序的比较次数是n(n-1)/2=20×19/2=190。

A

[解析] 循环队列是用数组保存队列的一种存储结构，只不过数组元素循环使用，因而是顺序存储而不是链式存储。队列是线性结构。

B

[解析] 树中的结点数=所有结点的度数加1。树的度为3，说明最大分支为3，即只有分支度为0、1、2、3四种情况的结点。设叶子结点(度为0的结点)为x个，则所有结点的度数表示为3×3+2×0+1×4+0×x。根据“树中的结点数=所有结点的度数加1”可列方程得3+0+4+x=3×3+2×0+1×4+0×x+1。解方程得x=7。

C

[解析] 栈是先进后出的数据结构，插入和删除元素均在栈顶进行；队是先进先出的数据结构，队尾插入、队头删除。将序列中的前4个元素依次入栈，栈中的元素情况：栈底-A-B-C-D-栈顶。4个元素依次入队，队列的元素情况：队头-E-F-G-H-队尾。将栈中的元素依次退栈得到的序列为D,C,B,A；将队列中的元素依次退队得到的序列为E,F,G,H。

C

[解析] 双向链表具有两个指针域，一个指向下一结点，另一个指向上一结点，而双向链表是线性结构。树为非线性结构，具有一个根结点，而无论具有几个叶子结点都不能改变树是非线性结构的事实。具有两个元素的线性结构如○-○也可认为其中一个结点为根，另一个结点为叶子。具有两个根结点，说明下一结点具有两个前驱(或中间断开的结构)；具有两个叶子结点，说明上一结点具有两个后继(或中间断开的结构)。这些情况都说明必为非线性结构(因为线性结构要求所有结点都必须只有一个前驱、一个后继)。

C

[解析] 二叉链表是二叉树的链表存储方式，是链式存储结构，但逻辑上它是树，是非线性结构。数组、链表、队列逻辑上都是线性结构，而存储结构彼此不同：二维数组仍是数组存储，存储结构是顺序存储的；循环队列是用数组保存的队列，也是顺序存储的；双向链表是链表存储的(具有两个指针域，分别指向下一结点和上一结点)，是链式结构。

C

[解析] 循环链表也是链表，只不过最后一个结点的指针域不为空，而指回第一个结点。链表各结点的存储空间一般是不连续的。为链表设置头结点，是为程序设计的方便，头结点不使用数据域，不保存数据，而只使用指针域，指向链表真正的第一个结点。这样无论表是否为空，头结点都会存在(表为空时只是头结点的指针域的内容为空)，无论对于空表还是非空表，在程序处理时方法就可以统一了。

B

[解析] 树中的结点数=所有结点的度数加1。树的度为3，说明最大分支为3，即只有度为0、1、2、3四种情况的结点。设叶子结点(度为0的结点)为x个，度为2的结点数为y个，则所有结点的度数表示为3×3+2×y+1×4+0×x。根据“树中的结点数=所有结点的度数加1”可列方程得：30=3×3+2×y+1×4+0×x+1。解方程得y=8。又3+y+4+x=30，代入y得3+8+4+x=30，解方程得x=15。

C

[解析] 二分查找最多需要的比较次数为log₂n，且向上取整，log₂97=6.59，向上取整得7。

A

[解析] 数组、链表、队列都是线性结构。注意二叉链表是二叉树用链表存储的存储结构，逻辑上它是树，是非线性结构。

D

[解析] 循环链表最后一个结点的指针域不为空，而指回第一个结点，所以可以从中间任意位置出发都能访问到表中其他结点。单向链表若从中间任意位置出发，则只能访问到表中后面的结点，无法访问前面的结点。双向链表中的结点有两个指针域，可访问前一结点，但从中间任意位置出发要么向前只访问前向的所有结点，要么向后只访问后面的所有结点，而从同一位置无法访问到全部的所有结点。二叉链表是二叉树的链表存储结构，也只能向下访问下层结点，无法访问上层结点。

B

[解析] 树的度为3，说明最大分支为3，即只有度为0、1、2、3四种情况的结点。设总结点数为x，度为2的结点数为y，则x=3+y+4+15，即y=x-22，此为方程①。又根据“树中的结点数：所有结点的度数加1”得方程：x=3×3+2×y+1×4+0×15+1。即x=14+2×y，此为方程②。将方程①代入方程②得x=14+2×(x-22)，解方程得x=30。

B

[解析] 数组是线性表的一种，长度固定，而链表的长度不固定，可随需要分配结点空间。线性表中各元素的数据类型必须相同，对线性表可以做插入、删除、查找、排序、寻找最大值等多种运算。矩阵可被看作是下一行衔接在上一行的行尾形成的直线序列，因而也为线性结构。

D

[解析] 给定包含n个不同元素的数组A[1..n]，如果存在i＜j且A[i]＞A[j]，则(i,j)称为数组A的一个逆序。快速排序法的基本思想是任取序列中某个元素为基准元素，将序列划分为左右两个子序列，左侧子序列都小于或等于基准元素，右侧子序列都大于基准元素，接下来分别对两个子序列重复上述过程。快速排序法不是对两个相邻元素进行比较，可以实现通过一次交换而消除多个逆序，但由于均与基准元素比较，但也可能会产生新的逆序。

B

[解析] 最坏情况下，寻找最大项无论如何需查看表中的所有元素，n个元素比较次数为n-1。同时寻找最大项与最小项，需要为判断较大值和较小值分别进行比较，会有更多的比较次数。有序表的插入最坏情况下是插入到表中的最后一个元素的后面位置，则会比较n次。顺序查找要逐个查看所有元素，也会比较n次。

D

[解析] 树的度为3，说明最大分支为3，即只有度为0、1、2、3四种情况的结点。设总结点数为x，度为3的结点数为y，则x=y+3+4+15，即y=x-22，此为方程①。又根据“树中的结点数=所有结点的度数加1”得方程x=3×y+2×3+1×4+0×15+1，即x=3×y+11，此为方程②。将方程①代入方程②得x=3×(x-22)+11，x不能得到整数解，故不可能有这样的树。

A

[解析] 非空线性结构中，只有一个结点(即第一个结点)没有前件，只有一个结点(即最后一个结点)没有后件，其他结点均只有一个前件、一个后件。向量满足这样的规律，也是线性结构。树为非线性结构，具有一个根结点，而无论具有几个叶子结点都不能改变树是非线性结构的事实。