1、计算机学科专业基础综合数据结构-栈、队列和数组(二)及答案解析(总分：53.00，做题时间：90 分钟)一、B单项选择题/B(总题数：37，分数：37.00)1.对一个初始为空的栈 s执行操作 Push(s，5)，Push(s，2)，Push(s，4)，Pop(s，x)，getTop(s，x)后，x的值应是_。 A.5 B.2 C.4 D.0（分数：1.00）A.B.C.D.2.用 S表示进栈操作，用 X表示出栈操作，若元素的进栈顺序是 1，2，3，4，为了得到出栈顺序1，3，4，2，相应的 S和 X的操作序列为_。 A.SXSXSSXX B.SSSXXSXX C.SXSSXXSX D.SXS
2、SXSXX（分数：1.00）A.B.C.D.3.已知一个栈的进栈序列为 1，2，3，n，其输出序列的第一个元素是 i，则第 j个出栈元素是_。 A.j-i B.n-i C.j-i+1 D.不确定（分数：1.00）A.B.C.D.4.已知一个栈的进栈序列为 1，2，3，n，其输出序列是 p1，p 2，p 3，p n。若 p1=3，则 p2的值_。 A.一定是 2 B.一定是 1 C.可能是 1 D.可能是 2（分数：1.00）A.B.C.D.5.已知一个栈的进栈序列为 p1，p 2，p 3，p n，其输出序列是 1，2，3，n。若 p3=1，则 p1的值_。 A.一定是 2 B.可能是 2 C.
3、不可能是 2 D.一定是 3（分数：1.00）A.B.C.D.6.以下有关顺序栈的操作中，正确的是_。 A.n个元素进入一个栈后，它们的出栈顺序一定与进栈顺序相反(一次性进栈完毕后再出栈) B.若一个栈的存储空间为 Sn，则对栈的进栈和出栈操作最多只能执行 n次 C.栈是一种对进栈和出栈操作的次序做了限制的线性表 D.空栈没有栈顶指针（分数：1.00）A.B.C.D.7.在实现顺序栈的操作时，在进栈之前应先判断栈是否_，在出栈之前应先判断是否空。 A.空 B.满 C.上溢 D.下溢（分数：1.00）A.B.C.D.8.设链式栈中结点的结构为(data，link)，且 top是指向栈顶的指针。若
4、想在链式栈的栈顶插入一个由指针 s所指的结点，则应执行的操作是_。 A.toplink=S; B.Slink=top+link;toplink=s; C.slink=top;top=s; D.slink=top;top=toplink;（分数：1.00）A.B.C.D.9.设一个循环队列 QmaxSize的队头指针为 front，队尾指针为 rear，队列最大容量为 maxSize。除此之外，该队列再没有其他数据成员，则该队列的队满条件是_。 A.Q.front=Q.rear B.front+Q.rear=maxSize C.Q.fron=(Q.rear+1)%maxSize D.Q.rear
5、=(Q.front+1)%maxSize（分数：1.00）A.B.C.D.10.一个队列的进队顺序是 1，2，3，4，则该队列可能的输出序列是_。 A.1，2，3，4 B.1，3，2，4 C.1，4，2，3 D.4，3，2，1（分数：1.00）A.B.C.D.11.对于链式队列，在执行插入操作时_。 A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改（分数：1.00）A.B.C.D.12.最适合用做链式队列的链表是_。 A.带有队头指针和队尾指针的循环单链表 B.带有队头指针和队尾指针的非循环单链表 C.只带队头指针的循环单链表 D.只带队头指针的非循环单链
6、表（分数：1.00）A.B.C.D.13.最不适合用做链式队列的链表是_。 A.带有队头指针的双向非循环链表 B.带有队头指针的双向循环链表 C.只带队尾指针的双向循环链表 D.只带队尾指针的循环单链表（分数：1.00）A.B.C.D.14.为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结应该是_。 A.栈 B.队列 C.树 D.图（分数：1.00）A.B.C.D.15.在将递归算法转换成对应的非递归算法时，通常需要使用_保存中间结果。 A.链表 B.栈 C.队列 D.顺序表（分数
7、：1.00）A.B.C.D.16.一个递归算法必须包括_。 A.递归部分 B.结束条件和递归部分 C.迭代部分 D.结束条件和迭代部分（分数：1.00）A.B.C.D.17.在二维数组中，每个数组元素同时处于_个向量中。 A.0个 B.1个 C.2个 D.n个（分数：1.00）A.B.C.D.18.多维数组实际上是由_实现的。 A.一维数组 B.多项式 C.三元组表 D.简单变量（分数：1.00）A.B.C.D.19.在二维数组 A910中，每个数组元素占用 3个存储单元，从首地址 SA开始按行连续存放。在这种情况下，元素 A85的起始地址为_。 A.SA+141 B.SA+144 C.SA+
8、222 D.SA+255（分数：1.00）A.B.C.D.20.假设某栈的输入序列是 1，2，3，4，则不可能得到的输出序列是_。 A.1，2，3，4 B.4，1，2，3 C.4，3，2，1 D.1，3，4，2（分数：1.00）A.B.C.D.21.已知一个栈的进栈序列为 1，2，3，n，其输出序列是 p1，p 2，p 3，p n。若 p1=n，则 pi的值是_。 A.i B.n-i C.n-i+1 D.不确定（分数：1.00）A.B.C.D.22.已知一个栈的进栈序列为 p1，p 2，p 3，p n，其输出序列是 1，2，3，n。若 p3=3，则 p1的值是_。 A.一定是 2 B.可能是
9、2 C.不可能是 1 D.一定是 1（分数：1.00）A.B.C.D.23.已知一个栈的进栈序列为 p1，p 2，p 3，p n，其输出序列是 1，2，3，n。若 pn=1，则 pi的值是_。 A.n-i+1 B.n-i C.i D.不确定（分数：1.00）A.B.C.D.24.当利用大小为 n的数组顺序存储一个栈时，元素存储在0n-1位置上，假定用 top=n表示栈空，则向这个栈插入一个元素时，首先应执行_语句修改 top指针。 A.top+; B.top-; C.top=0; D.top=n;（分数：1.00）A.B.C.D.25.为了增加内存空间的利用率和减少溢出的可能，在两个栈共享一片
10、连续的存储空间时，应将两个栈的栈顶(初始的时候栈底和栈顶重合；元素进栈时，两栈顶相向运动)分设在这片存储空间的两端，当_时才产生上溢。 A.两个栈的栈顶同时到达栈空间的中心点 B.其中一个栈的栈顶到达栈空间的中心点 C.两个栈的栈顶在栈空间的某一位置相遇 D.两个栈的栈顶相加超过了栈空间的最大容量（分数：1.00）A.B.C.D.26.设链式栈中结点的结构为(data，link)，且 top是指向栈顶的指针。若想摘下链式栈的栈顶结点，并将被摘除结点的值保存到 x中，则应执行的操作是_。 A.x=topdata;top=toplink; B.top=toplink;x=topdata; C.x=
11、top;top=toplink; D.x=topdata;（分数：1.00）A.B.C.D.27.设循环队列的存储容量为 maxSize，队头和队尾指针分别为 front和 rear。若有一个循环队列 Q，则可应用下列_算式计算队列元素个数。 A.Q.rear-Q.front B.Q.rear-Q.front+1 C.(Q.rear-Q.front)%maxSize+1 D.(Q.rear-Q.front+maxSize)%maxSize（分数：1.00）A.B.C.D.28.设一个链式队列 q的队头指针和队尾指针分别为 front和 rear，则判断队列为空的条件是_。 A.q.front=
12、q.rear B.q.front=NULL|q.rear=NULL C.q.rear=NULL D.q.front!=NULL（分数：1.00）A.B.C.D.29.对一个初始为空的队列 Q执行操作 enQueue(Q,a)，enQueue(Q,b)，deQueue(Q,x)，deQueue(Q,Y)之后，再执行 isEmpty(Q)，返回的值是_。 A.a B.b C.1 D.0（分数：1.00）A.B.C.D.30.设栈 S和队列 Q的初始状态均为空，元素 a，b，c，d，e，f，g 依次进入栈 S。如果每个元素出栈后立即进入队列 Q，且 7个元素出队的顺序为 b，d，c，f，e，a，g，
13、则栈 S的容量至少是_。 A.1 B.2 C.3 D.4（分数：1.00）A.B.C.D.31.已知输入序列是 1234，则输入受限(仅允许由一端输入)但输出不受限(两端均可输出)的双端队列不可能得到的输出序列是_。 A.4231 B.1324 C.3214 D.2341（分数：1.00）A.B.C.D.32.已知输入序列是 abcd，则经过输出受限的双端队列后能得到的输出序列是_。 A.dacb B.cadb C.dbca D.dbac（分数：1.00）A.B.C.D.33.设求解某问题的递归算法如下：void F(int n)if(n=1) Move(1);elseF(n-1);Move(
14、n);F(n-1);在求解该算法的计算时间时，仅考虑算法 Move所做的计算，且 Move为常数级算法。算法 F的计算时间T(n)的递推关系式为_。 A.T(n)=T(n-1)+1 B.T(n)=2T(n-1) C.T(n)=2T(n-1)+1 D.T(n)=2T(n+1)+1（分数：1.00）A.B.C.D.34.一个二维数组 A1020按行存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元素占 1个存储字，则 A62的地址为_。 A.226 B.322 C.341 D.342（分数：1.00）A.B.C.D.35.一个二维数组 A1020按列存放于一个连续的存储空间中，A0
15、0的存储地址是 200，每个数组元素占 1个存储字，则 A62的地址为_。 A.226 B.322 C.341 D.342（分数：1.00）A.B.C.D.36.将一个 nn的对称矩阵 A的下三角部分按行存放在一个一维数组 B中，A00存放于 B0中，那么第 i行的对角元素 Aii在 B中的存放位置是_。 A.(i+3)i/2 B.(i+1)i/2 C.(2n-i+1)i/2 D.(2n-i-1)i/2（分数：1.00）A.B.C.D.37.设有一个 n阶的三对角线矩阵 A的对角元素 Aij可存放于一个一维数组 B中，要求行下标必须满足 0in-1，而列下标必须满足_。 A.0jn-1 B.i
16、-1ji+1 C.0ji D.ijn（分数：1.00）A.B.C.D.二、B综合应用题/B(总题数：2，分数：16.00)Legendre多项式定义如下：（分数：8.00）(1).编写一个递归算法，计算该多项式的值。（分数：4.00）_(2).编写一个非递归算法，计算该多项式的值。（分数：4.00）_设有一个 nn的对称矩阵 A。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。把它们按行存放于一个一维数组 B中，并称之为对称矩阵 A的压缩存储方式。试问：（分数：8.00）(1).存放对称矩阵 A上三角部分或下三角部分的一
17、维数组 B有多少元素?（分数：4.00）_(2).若在一维数组 B中从 0号位置开始存放，则对称矩阵 A中的任意一个元素 aij在只存上三角部分的情形下(如下面一维数组 B的存储情况)应存于一维数组的什么下标位置?给出计算公式。 对称矩阵 A： 只存 A的上三角部分： （分数：4.00）_计算机学科专业基础综合数据结构-栈、队列和数组(二)答案解析(总分：53.00，做题时间：90 分钟)一、B单项选择题/B(总题数：37，分数：37.00)1.对一个初始为空的栈 s执行操作 Push(s，5)，Push(s，2)，Push(s，4)，Pop(s，x)，getTop(s，x)后，x的值应是_。
18、 A.5 B.2 C.4 D.0（分数：1.00）A.B. C.D.解析：解析 连续执行 3次元素进栈操作后，栈内的数据为 5，2，4，此时执行退栈操作 1次，栈内元素为 5和 2，栈顶读到 x中应为 2。2.用 S表示进栈操作，用 X表示出栈操作，若元素的进栈顺序是 1，2，3，4，为了得到出栈顺序1，3，4，2，相应的 S和 X的操作序列为_。 A.SXSXSSXX B.SSSXXSXX C.SXSSXXSX D.SXSSXSXX（分数：1.00）A.B.C.D. 解析：解析 此题可以用排除法来解决。由选项 A、B、C 所得出的栈序列分别为(1，2，4，3)、(3，2，4，1)、(1，3，
19、2，4)，可以看出都是错误的。选项 D得到的出栈序列为 1，3，4，2。3.已知一个栈的进栈序列为 1，2，3，n，其输出序列的第一个元素是 i，则第 j个出栈元素是_。 A.j-i B.n-i C.j-i+1 D.不确定（分数：1.00）A.B.C.D. 解析：解析 i 出栈时，1，2，i-l 都在栈内，之后的过程中还可能有 i之后的元素进栈，但究竟第j个出栈元素是哪个，不能确定。4.已知一个栈的进栈序列为 1，2，3，n，其输出序列是 p1，p 2，p 3，p n。若 p1=3，则 p2的值_。 A.一定是 2 B.一定是 1 C.可能是 1 D.可能是 2（分数：1.00）A.B.C.D
20、. 解析：解析 元素 3第一个出栈时，元素 1，2 一定在栈内，下一个出栈的元素是 2，不可能是 1。当然还可以是元素 2暂时不出栈，元素 4，5，进栈。5.已知一个栈的进栈序列为 p1，p 2，p 3，p n，其输出序列是 1，2，3，n。若 p3=1，则 p1的值_。 A.一定是 2 B.可能是 2 C.不可能是 2 D.一定是 3（分数：1.00）A.B.C. D.解析：解析 p 3=1，输入序列为 p1，p 2，1，p 4，因为 p3=1，所以 p3出栈前，p 1，p 2必在栈中。若 p1出栈，则 p2必先于 p1出栈，因此 p1不可能为 2。6.以下有关顺序栈的操作中，正确的是_。
21、A.n个元素进入一个栈后，它们的出栈顺序一定与进栈顺序相反(一次性进栈完毕后再出栈) B.若一个栈的存储空间为 Sn，则对栈的进栈和出栈操作最多只能执行 n次 C.栈是一种对进栈和出栈操作的次序做了限制的线性表 D.空栈没有栈顶指针（分数：1.00）A. B.C.D.解析：解析 对于选项 A，n 个元素进栈后，出栈顺序必然与进栈的顺序相反，因此选项 A正确；对于选项 B，如果某元素进栈后很快又出栈，则进栈和出栈操作可以多于 n次；对于选项 C，栈并未对进栈和出栈次序做限制，而仅仅对进栈和出栈的位置做了限制；对于选项 D，栈顶指针属于栈结构的一个分量，不会由于栈的状态变化而消失。7.在实现顺序栈
22、的操作时，在进栈之前应先判断栈是否_，在出栈之前应先判断是否空。 A.空 B.满 C.上溢 D.下溢（分数：1.00）A.B. C.D.解析：解析 在元素进栈之前先判断栈是否已满，栈满再进栈就会发生上溢。出栈之前先判断栈是否为空，如果栈已空再出栈就会发生下溢。8.设链式栈中结点的结构为(data，link)，且 top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针 s所指的结点，则应执行的操作是_。 A.toplink=S; B.Slink=top+link;toplink=s; C.slink=top;top=s; D.slink=top;top=toplink;（分数：1.00）A.B
23、.C. D.解析：解析 在栈顶插入元素即在链表首元结点前插入，必须首先让 s后面链接上原栈顶 top，再让栈顶指针指向新栈顶 s，所以有 slink=top;top=s;。9.设一个循环队列 QmaxSize的队头指针为 front，队尾指针为 rear，队列最大容量为 maxSize。除此之外，该队列再没有其他数据成员，则该队列的队满条件是_。 A.Q.front=Q.rear B.front+Q.rear=maxSize C.Q.fron=(Q.rear+1)%maxSize D.Q.rear=(Q.front+1)%maxSize（分数：1.00）A.B.C. D.解析：解析 在不能附加
24、其他任何数据成员的前提下，只能用牺牲一个队列元素的整除取余的方式来区分队空和队满的条件。因此，选项 C正确。选项 A是判断队列是否为空的条件，选项 B和 D则是干扰项。10.一个队列的进队顺序是 1，2，3，4，则该队列可能的输出序列是_。 A.1，2，3，4 B.1，3，2，4 C.1，4，2，3 D.4，3，2，1（分数：1.00）A. B.C.D.解析：解析 由队列的 FIFO性质可知，出队序列为 1，2，3，4。11.对于链式队列，在执行插入操作时_。 A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改（分数：1.00）A.B.C.D. 解析：解析
25、对于链式队列，一般插入元素仅仅需要修改尾指针，但向空队列插入新元素时，需要同时修改队头指针和队尾指针。所以本题选 D。12.最适合用做链式队列的链表是_。 A.带有队头指针和队尾指针的循环单链表 B.带有队头指针和队尾指针的非循环单链表 C.只带队头指针的循环单链表 D.只带队头指针的非循环单链表（分数：1.00）A.B. C.D.解析：解析 在链头删除元素，在链尾插入元素，因此需要队头指针和队尾指针。这种情况下使用非循环单链表比较方便。13.最不适合用做链式队列的链表是_。 A.带有队头指针的双向非循环链表 B.带有队头指针的双向循环链表 C.只带队尾指针的双向循环链表 D.只带队尾指针的循
26、环单链表（分数：1.00）A. B.C.D.解析：解析 即使是双向链表，如果是非循环链表，只有队头指针也是不够的。14.为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结应该是_。 A.栈 B.队列 C.树 D.图（分数：1.00）A.B. C.D.解析：解析 通常用于输入或输出的缓冲区都是采用先进先出的队列。15.在将递归算法转换成对应的非递归算法时，通常需要使用_保存中间结果。 A.链表 B.栈 C.队列 D.顺序表（分数：1.00）A.B. C.D.解析：解析 在递归程序时作为
27、递归工作栈是栈的一个典型应用，用于开辟每一层递归程序调用时需要的局部变量空间、实际参数的拷贝空间和记录返回上一层调用的返回地址等。16.一个递归算法必须包括_。 A.递归部分 B.结束条件和递归部分 C.迭代部分 D.结束条件和迭代部分（分数：1.00）A.B. C.D.解析：解析 递归算法必须包括递归体和结束条件。结束条件是可以直接求解的，无需再递归处理；递归体在不能直接求解的情况下把问题通过递归调用化为更简单的子问题求解，每递归一层就向问题的最终解决推进一步。17.在二维数组中，每个数组元素同时处于_个向量中。 A.0个 B.1个 C.2个 D.n个（分数：1.00）A.B.C. D.解析
28、：解析 可以将二维数组视为一组行向量和列向量的纵横交织，每个元素既处于一个行向量中，又处于一个列向量中。因此，需要用两个下标 i和 j以确定该数组元素在数组中的位置。18.多维数组实际上是由_实现的。 A.一维数组 B.多项式 C.三元组表 D.简单变量（分数：1.00）A. B.C.D.解析：解析 多维数组本质上是一维数组，是由一维数组实现的，是数组元素为一维数组的一维数组。19.在二维数组 A910中，每个数组元素占用 3个存储单元，从首地址 SA开始按行连续存放。在这种情况下，元素 A85的起始地址为_。 A.SA+141 B.SA+144 C.SA+222 D.SA+255（分数：1.
29、00）A.B.C.D. 解析：解析 本题属于计算存储地址的典型题目，假设求元素 a的地址，首先按行存储，求 a所在行之前的所有行中元素的总和 sum1，然后求 a所在行 a之前所有元素的总和 sum2，最后用首地址加上(sum1+sum2)每个元素所占存储空间的大小即可。 由以上分析可知：A85的地址=SA+(810+5)3=SA+255。20.假设某栈的输入序列是 1，2，3，4，则不可能得到的输出序列是_。 A.1，2，3，4 B.4，1，2，3 C.4，3，2，1 D.1，3，4，2（分数：1.00）A.B. C.D.解析：解析 用 S表示进栈操作，用 X表示出栈操作，选项 A、C 和
30、D的输出序列可以用操作序列SXSXSXSX、SSSSXXXX 和 SXSSXSXX来导出，且都是合法操作序列。只有选项 B的输出序列找不到合法的操作序列。21.已知一个栈的进栈序列为 1，2，3，n，其输出序列是 p1，p 2，p 3，p n。若 p1=n，则 pi的值是_。 A.i B.n-i C.n-i+1 D.不确定（分数：1.00）A.B.C. D.解析：解析 一个出栈元素是 n，则 1，2，3，n-1 都在栈内，可知后续出栈的元素依次为 n-1，n-2，则第 i个出栈元素应为 n-i+1。22.已知一个栈的进栈序列为 p1，p 2，p 3，p n，其输出序列是 1，2，3，n。若 p
31、3=3，则 p1的值是_。 A.一定是 2 B.可能是 2 C.不可能是 1 D.一定是 1（分数：1.00）A.B. C.D.解析：解析 当 p3=3时，输入序列为 p1，p 2，3，p 4，因为输出的第三个元素是 3，所以有多种可能：当 p1=1，p 2=2时，允许的进栈或出栈顺序是 p1进栈，p 1出栈，p 2进栈，p 2出栈；当 p1=2，p 2=1时，允许的进栈或出栈顺序是 p1进栈，p 2进栈，p 2出栈，p 1出栈；当 p1，p 2，3 进栈不出，p 4=2，p 5=1时，允许的进栈或出栈顺序可以是 p4进栈，p 5进栈，p 5出栈，p 4出栈。因此可以断定 p1=1或 p1=2
32、是可能的，但不是一定的。23.已知一个栈的进栈序列为 p1，p 2，p 3，p n，其输出序列是 1，2，3，n。若 pn=1，则 pi的值是_。 A.n-i+1 B.n-i C.i D.不确定（分数：1.00）A. B.C.D.解析：解析 当 pn=1时，输入序列为 p1，p 2，p 3，p 4，p n-1，1，因为输出序列为 1，2，3，n，所以第一次输出 l时 p1，p 2，p 3，p 4，p n-1都应在栈内，这样可得 pn-1=2，p n-2=3，p n-i=i+1，p i=n-i+1。24.当利用大小为 n的数组顺序存储一个栈时，元素存储在0n-1位置上，假定用 top=n表示栈空
33、，则向这个栈插入一个元素时，首先应执行_语句修改 top指针。 A.top+; B.top-; C.top=0; D.top=n;（分数：1.00）A.B. C.D.解析：解析 根据题意，栈底应在下标 n-1的位置上，因此进栈时栈顶指针应该先减 1，向栈空间的底端延伸。25.为了增加内存空间的利用率和减少溢出的可能，在两个栈共享一片连续的存储空间时，应将两个栈的栈顶(初始的时候栈底和栈顶重合；元素进栈时，两栈顶相向运动)分设在这片存储空间的两端，当_时才产生上溢。 A.两个栈的栈顶同时到达栈空间的中心点 B.其中一个栈的栈顶到达栈空间的中心点 C.两个栈的栈顶在栈空间的某一位置相遇 D.两个栈
34、的栈顶相加超过了栈空间的最大容量（分数：1.00）A.B.C. D.解析：解析 初始时，两个栈的栈顶设置在栈空间的两端，元素进栈时，栈顶指针相向而行，当两个栈的栈顶在栈空间的某一位置相遇时，为栈满状态。26.设链式栈中结点的结构为(data，link)，且 top是指向栈顶的指针。若想摘下链式栈的栈顶结点，并将被摘除结点的值保存到 x中，则应执行的操作是_。 A.x=topdata;top=toplink; B.top=toplink;x=topdata; C.x=top;top=toplink; D.x=topdata;（分数：1.00）A. B.C.D.解析：解析 出栈操作由两部分组成：取
35、元素存储在其他空间和调整栈顶指针位置。为完成这两部分可以执行以下语句： x=topdata;/取元素存储在其他空间 top=toplink;/调整栈顶指针位置27.设循环队列的存储容量为 maxSize，队头和队尾指针分别为 front和 rear。若有一个循环队列 Q，则可应用下列_算式计算队列元素个数。 A.Q.rear-Q.front B.Q.rear-Q.front+1 C.(Q.rear-Q.front)%maxSize+1 D.(Q.rear-Q.front+maxSize)%maxSize（分数：1.00）A.B.C.D. 解析：解析 随着队列中元素的进队出队的交替进行，对于 r
36、ear与 front两指针，其相对位置不定。当rearfront 时，Q.reai-Q.front+ maxSize 正好是队列元素个数；当 rearfront 时，可以用(Q.rear-Q.front+maxSize)%maxSize得到队列元素个数。28.设一个链式队列 q的队头指针和队尾指针分别为 front和 rear，则判断队列为空的条件是_。 A.q.front=q.rear B.q.front=NULL|q.rear=NULL C.q.rear=NULL D.q.front!=NULL（分数：1.00）A.B. C.D.解析：解析 当 front=NULL或者 rear=NULL
37、时，链为空，则对应的链队也为空。29.对一个初始为空的队列 Q执行操作 enQueue(Q,a)，enQueue(Q,b)，deQueue(Q,x)，deQueue(Q,Y)之后，再执行 isEmpty(Q)，返回的值是_。 A.a B.b C.1 D.0（分数：1.00）A.B.C. D.解析：解析 对一个空队列，执行两次进队操作和两次出队操作后，显然栈变为空状态，此时执行判断队列是否为空的操作 Q.isEmpty()，函数返回 true。30.设栈 S和队列 Q的初始状态均为空，元素 a，b，c，d，e，f，g 依次进入栈 S。如果每个元素出栈后立即进入队列 Q，且 7个元素出队的顺序为
38、b，d，c，f，e，a，g，则栈 S的容量至少是_。 A.1 B.2 C.3 D.4（分数：1.00）A.B.C. D.解析：解析 根据队列的 FIFO性质，出队顺序与入队顺序一致，也就是说，与出栈顺序一致。如果用 S表示进栈，用 X表示出栈，按照题意，进栈和出栈序列见下表。 B进栈与出栈情况/B进栈序列 ab进出操作 SS XS S X XS S X XXSX栈的内容 aabaacacdacaaeaefaea g出栈序列 b d c f ea g由表可知，栈中最多时有 3个元素，所以栈的容量最少为 3。31.已知输入序列是 1234，则输入受限(仅允许由一端输入)但输出不受限(两端均可输出)
39、的双端队列不可能得到的输出序列是_。 A.4231 B.1324 C.3214 D.2341（分数：1.00）A. B.C.D.解析：解析 设双端队列的两端为 e1和 e2，e1 端允许输入，e1 和 e2端都允许输出。若在 e1端输出，相当于栈；若在 e2端输出，相当于队列。对于选项 A(4231)，要求先输出 4，有一种进队方案：1 e12e13e14e1，然后从 e1端输出 4，但由于 2夹在 1和 3之间，下一个输出的不可能是 2，所以选项 A是不可能的输出序列。对于选项 B(1324)，一种操作顺序是 1e1进 1e1出 2e1进 3e1进 3e1出 2e1出 4e1进 4e1出 。
40、对于选项 C(3214)，一种操作顺序是 1e1进 2e1进 3e1进 3e1出 2e1出 1e1出 4e1进 4e1出 。对于选项 D(2341)，一种操作顺序是 1e1进 2e1进 2e1出 3e1进 3e1出 4e1进 4e1出 1e1出 。32.已知输入序列是 abcd，则经过输出受限的双端队列后能得到的输出序列是_。 A.dacb B.cadb C.dbca D.dbac（分数：1.00）A.B. C.D.解析：解析 设双端队列的两端为 e1和 e2，e2 端允许输出，e1 和 e2两端都允许输入。若在 e1端输入，相当于队列；若在 e2端输入，相当于栈。对于选项 A(dacb)，要
41、求先输出 d，必须 abc都输入后再执行操作 de2进 de2出 (相当于进栈出栈)，但下一个要输出 a，就必须执行操作 ae1进 be1进 ce1进 ，队列中是 cba，再执行 ae2出 ，然而下一个不可能输出 c，所以选项 A是不可能的输出序列。对于选项 B(cadb)，一种操作顺序是 ae1进 be1进 ce2进 ce2出 ae2出 de2进 de2出 be2出 ，是可能的输出序列。对于选项 C(dbca)，相当于上一题中的 A项(4231)，是不可能的输出序列。对于选项 D(dbac)，与选项 A类似，要求先输出 d，必须先输入 abc后再执行操作 de2进 de2出 ；若要求下一个输
42、出 b，应执行操作 ae1进 be2进 ce1进 ，队列中是 cab，输出 b后，下一个输出的不可能是 c，选项 D是不可能的输出序列。33.设求解某问题的递归算法如下：void F(int n)if(n=1) Move(1);elseF(n-1);Move(n);F(n-1);在求解该算法的计算时间时，仅考虑算法 Move所做的计算，且 Move为常数级算法。算法 F的计算时间T(n)的递推关系式为_。 A.T(n)=T(n-1)+1 B.T(n)=2T(n-1) C.T(n)=2T(n-1)+1 D.T(n)=2T(n+1)+1（分数：1.00）A.B.C. D.解析：解析 根据题目中程序
43、代码的递归框架可知，该程序把一个规模为 n的问题转化为两个规模为 n-1的同样问题外加一个常量复杂度的操作来求解，因此其递推关系为 T(n)=2T(n-1)+O(1)，可近似为 T(n)=2T(n-1)+1。34.一个二维数组 A1020按行存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元素占 1个存储字，则 A62的地址为_。 A.226 B.322 C.341 D.342（分数：1.00）A.B. C.D.解析：解析 此类型题目基础题部分已经讲过，A62的地址=200+620+2=322。35.一个二维数组 A1020按列存放于一个连续的存储空间中，A00的存储地址是 2
44、00，每个数组元素占 1个存储字，则 A62的地址为_。 A.226 B.322 C.341 D.342（分数：1.00）A. B.C.D.解析：解析 此类型题目基础题部分已经讲过，A62的地址=200+210+6=226。36.将一个 nn的对称矩阵 A的下三角部分按行存放在一个一维数组 B中，A00存放于 B0中，那么第 i行的对角元素 Aii在 B中的存放位置是_。 A.(i+3)i/2 B.(i+1)i/2 C.(2n-i+1)i/2 D.(2n-i-1)i/2（分数：1.00）A. B.C.D.解析：解析 第 i行前面存有 i行，元素个数为 1+2+i=(i+1)i/2，第 i行中第 i列前有 i个元素，则 Aii在 B中的存放位置为(i+1)i/2+i=(i+3)i/2。37.设有一个 n阶的三对角线矩阵 A的对角元素 A
