loading（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。
A．2 B．3 C．4 D． 6 说明：由于一个元素出栈后即进入队列，而队列是“先进先出”，所以出队的序列就是出栈的序列。
（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（ ）。
A．top不变 B．top=0 C．top-- D．top++
（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构 B．队列 C. 线性表的链式存储结构 D. 栈
（11）用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
说明：题目的意思是，用单链表实现队列，头指针指向第一个元素结点（首元结点），不使用头结点。不然的话，象课本p65图3.13的情形，删除操作只可能修改头结点中的指针，头指针永远不变。
由于队列是“先进先出”的，所以删除的一定是队列第一个元素，当队列元素只剩一个时，删除后需同时修改头、尾指针。
（12）循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。 A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 说明：数组长度是m+1而不是m。
（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
A. (rear+1)%n==front B. rear==front C．rear+1==front D. (rear-l)%n==front 说明：题目指的是课本p63图3.11所示的循环队列。
（14）栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 说明：栈的“端点”是栈顶，队列的“端点”是队头。
（15）一个递归算法必须包括（ ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分 说明：“迭代”是循环的另一种说法。
第4章 串、数组和广义表
1．选择题
（1）串是一种特殊的线性表，其特殊性体现在（ ）。
A．可以顺序存储 B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符 （2）下面关于串的的叙述中，（ ）是不正确的？ A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算
D．串既可以采用顺序存储，也可以采用链式存储 （3）串“ababaaababaa”的next数组为（ ）。
A．012345678999 B．012121111212 C．011234223456 D．0123012322345 （4）串“ababaabab”的nextval为（ ）。
A．010104101 B．010102101 C．010100011 D．010101011 （5）串的长度是指（ ）。
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数 （6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。
A．808 B．818 C．1010 D．1020
说明：按行序存储时，A[5,5]位于第5行第5列，之前有4行，每行100个元素，所在第5行前面有4个元素，因此在A[5,5]前面一共有4*100+4=404个元素。从基地址10开始存放，每个元素两个单元，所以A[5,5]的存储地址是10+404*2=818。
一般的计算公式是：loc(i,j)=BA+[(i-1)*n+(j-1)]*L，其中BA是基地址，n是数组列数，L是每个元素占用的单元数。注意按此公式计算时，i、j必须是从1数起的。
（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（ ）。
A．BA+141 B．BA+180 C．BA+222 D．BA+225
说明：按列序存储，A[5,8]前面有7列，每列8个元素，所在的第8列上方有4个元素（因为在第5行），因此A[58]前面共有7*8+4=60个元素，每个元素3个字节，故存储地址为BA+60*3=BA+180。
（8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A．13 B．32 C．33 D．40
说明：这道题没有说明按上三角还是下三角存储。假设按下三角存储，则a85前面有7行，第1行只有一个元素，第2行有2个元素，依次类推，前7行共有1+2+…+7=28个元素，a85所在的第8行前面有4个元素，于是前面共有28+4=32个元素，从地址1开始存储，
每个元素一个字节，因此存储地址为1+32=33。
若按上三角存储，则存储的是a85对称的元素a58，其存储地址为38。
（9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i A．i*(i-1)/2+j B．j*(j-1)/2+i C．i*(i+1)/2+j D．j*(j+1)/2+i 说明：此题计算的是aij在数组B中的下标而不是存储地址，只要计算从数组第1个元素开始，到aij共有几个元素。 aij前面共有i-1行，第1行在B中只存储一个元素，第2行存储2个元素，依次类推，前i-1行共存储了1+2+…+(i-1)=i*(i-1)/2个元素，aij位于第i行第j列，这一行到aij为止存储了j个元素，因此B中到aij为止共有i*(i-1)/2+j个元素。 （10）二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8，列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。 A．A[8,5] B．A[3,10] C．A[5,8] D．A[0,9] 说明：因为每个元素占用的单元数都相同，所以只要计算所存储的元素个数即可。 当按行优先存储时，A[8,5]前面有8行（行号从0数起），每行10个元素，所在的第8行前面有4个元素，因此存储到A[8,5]之前共有8*10+4=84个元素。 按列优先存储时，若要存储在相同位置，则前面同样必须有84个元素，因为每列有9个元素，所以列号一定要大于[84/9]=9，由此即知只有选择项B符合要求。 （11）设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ ）。 A．(i-1)*n+j B．(i-1)*n+j-1 C．i*(j-1) D．j*m+i-1 说明：从第一行开始，在B中依次存储A中每个元素，存储到A[i,j]共有多少个元素，下标就是多少。A[i,j]前面有i-1行，每行n个元素，共有(i-1)*n个元素；所在的第i行到A[i,j]为止有j个元素，因此下标为(i-1)*n+j。 （12）数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。 A．55 B．45 C．36 D．16 （13）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。 A．(g) B．(d) C．c D．d 说明：Tail(A)= (b,(c,d),(e,(f,g))) Tail(Tail(A))=Tail(b,(c,d),(e,(f,g)))= ((c,d),(e,(f,g))) Head(Tail(Tail(A)))=Head ((c,d),(e,(f,g)))=(c,d) Tail(Head(Tail(Tail(A))))=Tail(c,d)=(d) Head(Tail(Head(Tail(Tail(A)))))=Head(d)=d （14）广义表((a,b,c,d))的表头是（ C ），表尾是（ B ）。 A．a B．( ) C．(a,b,c,d) D．(b,c,d) （15）设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。 A．1和1 B．1和3 C．1和2 D．2和3