5、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（×） 6、循环队列也存在空间溢出问题。（√）
7、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（√） 8、栈和队列都是限制存取点的线性结构。（√）
9、队列和栈都是运算受限的线性表，只允许在表的两端进行运算（×） 10、通常使用队列来处理函数或过程的调用。（×） 11、栈与队列是一种特殊操作的线性表。（√）
12、若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. （√） 13、栈和队列都是限制存取点的线性结构。（√） 14、循环队列通常用指针来实现队列的头尾相接（×） 15、循环队列的引入，目的是为了克服假溢出现象。（ √ ）
三、单项选择题
1、栈中元素的进出原则是（ B ）
Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出
2、若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为（ C ）
Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定
3、判定一个顺序栈ST（最多元素为m）为空的条件是（ B ）
Ａ、ST->top<>0 Ｂ、ST->top=0 Ｃ、．ST->top<>m Ｄ、ST->top=m 4、判定一个队列QU（最多元素为m）为满队列的条件是（ A ） Ａ、QU->rear-QU->front= =m Ｂ、QU->rear-QU->front-1==m Ｃ、QU->front==QU->rear Ｄ、QU->front==QU->rear+1
5、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ D ）。 Ａ、r－f; Ｂ、（n＋f－r）% n; Ｃ、n＋r－f; Ｄ、（n＋r－f）% n 6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( B )。 A、1和 5 B、2和4 C、4和2 D、5和1 7、栈和队列的共同点是（ C ）。
A、都是先进先出、 B、都是先进后出 C、只允许在端点处插入和删除元素 D、没有共同点 8、栈和队都是（ C ）。
A、顺序存储的线性结构 B、链式存储的非线性结构 C、限制存取点的线性结构 D、限制存取点的非线性结构
11
9、栈与一般线性表的区别在于（ B ）。
A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同
10、有六个元素6，5，4，3，2，1 ，按顺序进栈，下列（ C ）不是合法的出栈序列。 A、5 4 3 6 1 2 B、4 5 3 1 2 6 C、 3 4 6 5 2 1 D、2 3 4 1 5 6
11、一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。
A、不确定 B、n-i+1 C、 I D、n-i
12、若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。
A、i-j-1 B、 i-j C、 j-i+1 D、 不确定的 13、设栈的输入序列是1，2，3，4,则（D ）不可能是其出栈序列。
A、 1，2，4，3 B、2，1，3，4 C、 1，4，3，2 D、4，3，1，2
14、设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。 A、5 1 2 3 4 B、 4 5 1 3 2 C、 4 3 1 2 5 D、3 2 1 5 4 15、循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。 A、rear=rear+1 B、 rear=(rear+1) mod (m-1) C、rear=(rear+1) mod m D rear=(rear+1)mod(m+1)
16、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。
A、(rear-front+m)%m B、rear-front+1 C、(front-rear+m)%m D、(rear-front)%m 17、栈在（ D ）中应用。
A、递归调用 B、子程序调用 C、表达式求值 D、以上三种
18、用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。
A、仅修改队头指针 B、仅修改队尾指针
C、队头、队尾指针都要修改 D、队头,队尾指针都可能要修改
19、设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。 A、线性表的顺序存储结构 B、队列 C、线性表的链式存储结构 D、栈
20、有六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个不是合法的出栈序列？（ ） A、5 4 3 6 1 2 B、4 5 3 1 2 6 C、 3 4 6 5 2 1 D. 2 3 4 1 5 6
四、简答题
1、说明线性表、栈与队的异同点。
12
答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。
2、顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：设置一个布尔变量以区别队满还是队空；浪费一个元素的空间，用于区别队满还是队空。使用一个计数器记录队列中元素个数（即队列长度）。
我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N
第四、五章 一、填空题
1、不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串
称为空白串。
2、设S=“A;/document/Mary.doc”，则字符串“/”的位置为 3 。
3、子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。 4、串的存储方式有顺序存储、堆分配存储和块链存储。
5、有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的地址是100，若按行主顺序存储，则A[3,5]的地址是176 和 A[5,3]的地址是208 。若按列存储，则A[7,1] 的地址是128 ，A[2,4]的地址是216 。 6、设数组a[1?60, 1?70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。
7、 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。
8、二维数组A[10][20]采用列序为主方式存储，每个元素占10个存储单元，且A[0][0]的存储地址是2000，则A[6][12]的地址是3260
9、已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 1168
10、已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]
13
的存储地址是1024, 则A[6][18]的地址是1300 11、组成串的数据元素只能是字符。
12、两个字符串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。
二、单选题
1、串是一种特殊的线性表，其特殊性体现在（ B ） Ａ、可以顺序存储 Ｂ、数据元素是一个字符 Ｃ、可以链式存储 Ｄ、数据元素可以是多个字符
2、设有两个串p和q，求q在p中首次出现的位置的运算称作（ B ） Ａ、连接 Ｂ、模式匹配 Ｃ、求子串 Ｄ、求串长
3、设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是（ D ） Ａ、BCDEF Ｂ、BCDEFG Ｃ、BCPQRST Ｄ、BCDEFEF
4、假设有60行70列的二维数组a[1?60, 1?70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ A ）。（无第0行第0列元素）
Ａ、16902 Ｂ、16904 Ｃ、14454 Ｄ、答案A, B, C均不对 5、下面关于串的的叙述中，（ B ）是不正确的。
A、串是字符的有限序列 B、空串是由空格构成的串
C、模式匹配是串的一种重要运算 D、串既可以采用顺序存储，也可以采用链式结构 6、串的长度是指（ B ）
A、串中所含不同字母的个数 B、串中所含字符的个数 C、串中所含不同字符的个数 D、串中所含非空格字符的个数 7、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是( B )
A、i(i-1)/2+j-1 B、i(i-1)/2+j C、i(i+1)/2+j-1 D、i(i+1)/2+j 8、以下关于广义表的叙述中,正确的是（ A）
A、广义表是由0个或多个单元素或子表构成的有限序列 B、广义表至少有一个元素是子表 C、广义表不能递归定义 D、广义表不能为空表
?a1,1?a2,1?A??????an,1a2,2an,2?????an,n??? 14
9、设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( B )。 A、i(i-l)/2+j B、j(j-l)/2+i C、 j(j-l)/2+i-1 D、i(i-l)/2+j-1 10、A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ B ）。
A、i（i-1）/2+j B、j（j-1）/2+I C、i（j-i）/2+1 D、j（i-1）/2+1 11、有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是（ A ）个字节。 A、288 B、283 C、276 D、282
12、有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址，假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。 A、288 B、282 C、276 D、283
13、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（B ）。 A、60 B、66 C、18000 D、33 14、对稀疏矩阵进行压缩存储目的是（ C ）。
A、便于进行矩阵运算 B、便于输入和输出 C、节省存储空间 D、降低运算的时间复杂度 15、下面说法不正确的是( A )。
A、广义表的表头总是一个广义表 B、广义表的表尾总是一个广义表 C、广义表难以用顺序存储结构 D、广义表可以是一个多层次的结构
三、简答题
1.已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？ 解：公式教材已给出，此处虽是方阵，但行列公式仍不相同；
按行存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K 按列存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K 2.递归算法比非递归算法花费更多的时间，对吗？为什么？
答：不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。
15