计算机学科专业基础综合数据结构-栈、队列和数组(二)

计算机学科专业基础综合数据结构-栈、队列和数组(二)(总分：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.5B.2C.4D.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.SXSXSSXXB.SSSXXSXXC.SXSSXXSXD.SXSSXSXX

（分数：1.00）

A.

B.

C.

D.

√解析：[解析]此题可以用排除法来解决。由选项A、B、C所得出的栈序列分别为(1，2，4，3)、(3，2，4，1)、(1，3，2，4)，可以看出都是错误的。选项D得到的出栈序列为1，3，4，2。3.已知一个栈的进栈序列为1，2，3，…，n，其输出序列的第一个元素是i，则第j个出栈元素是______。A.j-iB.n-iC.j-i+1D.不确定

（分数：1.00）

A.

B.

C.

D.

√解析：[解析]i出栈时，1，2，…，i-l都在栈内，之后的过程中还可能有i之后的元素进栈，但究竟第j个出栈元素是哪个，不能确定。4.已知一个栈的进栈序列为1，2，3，…，n，其输出序列是p1，p2，p3，…，pn。若p1=3，则p2的值______。A.一定是2B.一定是1C.可能是1D.可能是2

（分数：1.00）

A.

B.

C.

D.

√解析：[解析]元素3第一个出栈时，元素1，2一定在栈内，下一个出栈的元素是2，不可能是1。当然还可以是元素2暂时不出栈，元素4，5，…进栈。5.已知一个栈的进栈序列为p1，p2，p3，…，pn，其输出序列是1，2，3，…，n。若p3=1，则p1的值______。A.一定是2B.可能是2C.不可能是2D.一定是3

（分数：1.00）

A.

B.

C.

√

D.解析：[解析]p3=1，输入序列为p1，p2，1，p4，…，因为p3=1，所以p3出栈前，p1，p2必在栈中。若p1出栈，则p2必先于p1出栈，因此p1不可能为2。6.以下有关顺序栈的操作中，正确的是______。A.n个元素进入一个栈后，它们的出栈顺序一定与进栈顺序相反(一次性进栈完毕后再出栈)B.若一个栈的存储空间为S[n]，则对栈的进栈和出栈操作最多只能执行n次C.栈是一种对进栈和出栈操作的次序做了限制的线性表D.空栈没有栈顶指针

（分数：1.00）

A.

√

B.

C.

D.解析：[解析]对于选项A，n个元素进栈后，出栈顺序必然与进栈的顺序相反，因此选项A正确；对于选项B，如果某元素进栈后很快又出栈，则进栈和出栈操作可以多于n次；对于选项C，栈并未对进栈和出栈次序做限制，而仅仅对进栈和出栈的位置做了限制；对于选项D，栈顶指针属于栈结构的一个分量，不会由于栈的状态变化而消失。7.在实现顺序栈的操作时，在进栈之前应先判断栈是否______，在出栈之前应先判断是否空。A.空B.满C.上溢D.下溢

（分数：1.00）

A.

B.

√

C.

D.解析：[解析]在元素进栈之前先判断栈是否已满，栈满再进栈就会发生上溢。出栈之前先判断栈是否为空，如果栈已空再出栈就会发生下溢。8.设链式栈中结点的结构为(data，link)，且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行的操作是______。A.top→link=S;B.S→link=top→+link;top→link=s;C.s→link=top;top=s;D.s→link=top;top=top→link;

（分数：1.00）

A.

B.

C.

√

D.解析：[解析]在栈顶插入元素即在链表首元结点前插入，必须首先让s后面链接上原栈顶top，再让栈顶指针指向新栈顶s，所以有s→link=top;top=s;。9.设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列最大容量为maxSize。除此之外，该队列再没有其他数据成员，则该队列的队满条件是______。A.Q.front==Q.rearB.front+Q.rear＞=maxSizeC.Q.fron==(Q.rear+1)%maxSizeD.Q.rear==(Q.front+1)%maxSize

（分数：1.00）

A.

B.

C.

√

D.解析：[解析]在不能附加其他任何数据成员的前提下，只能用牺牲一个队列元素的整除取余的方式来区分队空和队满的条件。因此，选项C正确。选项A是判断队列是否为空的条件，选项B和D则是干扰项。10.一个队列的进队顺序是1，2，3，4，则该队列可能的输出序列是______。A.1，2，3，4B.1，3，2，4C.1，4，2，3D.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.

√解析：[解析]对于链式队列，一般插入元素仅仅需要修改尾指针，但向空队列插入新元素时，需要同时修改队头指针和队尾指针。所以本题选D。12.最适合用做链式队列的链表是______。A.带有队头指针和队尾指针的循环单链表B.带有队头指针和队尾指针的非循环单链表C.只带队头指针的循环单链表D.只带队头指针的非循环单链表

（分数：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.顺序表

（分数：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.解析：[解析]可以将二维数组视为一组行向量和列向量的纵横交织，每个元素既处于一个行向量中，又处于一个列向量中。因此，需要用两个下标i和j以确定该数组元素在数组中的位置。18.多维数组实际上是由______实现的。A.一维数组B.多项式C.三元组表D.简单变量

（分数：1.00）

A.

√

B.

C.

D.解析：[解析]多维数组本质上是一维数组，是由一维数组实现的，是数组元素为一维数组的一维数组。19.在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为______。A.SA+141B.SA+144C.SA+222D.SA+255

（分数：1.00）

A.

B.

C.

D.

√解析：[解析]本题属于计算存储地址的典型题目，假设求元素a的地址，首先按行存储，求a所在行之前的所有行中元素的总和sum1，然后求a所在行a之前所有元素的总和sum2，最后用首地址加上(sum1+sum2)×每个元素所占存储空间的大小即可。由以上分析可知：A[8][5]的地址=SA+(8×10+5)×3=SA+255。20.假设某栈的输入序列是1，2，3，4，则不可能得到的输出序列是______。A.1，2，3，4B.4，1，2，3C.4，3，2，1D.1，3，4，2

（分数：1.00）

A.

B.

√

C.

D.解析：[解析]用S表示进栈操作，用X表示出栈操作，选项A、C和D的输出序列可以用操作序列SXSXSXSX、SSSSXXXX和SXSSXSXX来导出，且都是合法操作序列。只有选项B的输出序列找不到合法的操作序列。21.已知一个栈的进栈序列为1，2，3，…，n，其输出序列是p1，p2，p3，…，pn。若p1=n，则pi的值是______。A.iB.n-iC.n-i+1D.不确定

（分数：1.00）

A.

B.

C.

√

D.解析：[解析]一个出栈元素是n，则1，2，3，…，n-1都在栈内，可知后续出栈的元素依次为n-1，n-2，…，则第i个出栈元素应为n-i+1。22.已知一个栈的进栈序列为p1，p2，p3，…，pn，其输出序列是1，2，3，…，n。若p3=3，则p1的值是______。A.一定是2B.可能是2C.不可能是1D.一定是1

（分数：1.00）

A.

B.

√

C.

D.解析：[解析]当p3=3时，输入序列为p1，p2，3，p4，…因为输出的第三个元素是3，所以有多种可能：当p1=1，p2=2时，允许的进栈或出栈顺序是p1进栈，p1出栈，p2进栈，p2出栈；当p1=2，p2=1时，允许的进栈或出栈顺序是p1进栈，p2进栈，p2出栈，p1出栈；当p1，p2，3进栈不出，p4=2，p5=1时，允许的进栈或出栈顺序可以是p4进栈，p5进栈，p5出栈，p4出栈。因此可以断定p1=1或p1=2是可能的，但不是一定的。23.已知一个栈的进栈序列为p1，p2，p3，…，pn，其输出序列是1，2，3，…，n。若pn=1，则pi的值是______。A.n-i+1B.n-iC.iD.不确定

（分数：1.00）

A.

√

B.

C.

D.解析：[解析]当pn=1时，输入序列为p1，p2，p3，p4，…，pn-1，1，因为输出序列为1，2，3，…，n，所以第一次输出l时p1，p2，p3，p4，…，pn-1都应在栈内，这样可得pn-1=2，pn-2=3，…，pn-i=i+1，…，pi=n-i+1。24.当利用大小为n的数组顺序存储一个栈时，元素存储在[0…n-1]位置上，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行______语句修改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.两个栈的栈顶相加超过了栈空间的最大容量

（分数：1.00）

A.

B.

C.

√

D.解析：[解析]初始时，两个栈的栈顶设置在栈空间的两端，元素进栈时，栈顶指针相向而行，当两个栈的栈顶在栈空间的某一位置相遇时，为栈满状态。26.设链式栈中结点的结构为(data，link)，且top是指向栈顶的指针。若想摘下链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行的操作是______。A.x=top→data;top=top→link;B.top=top→link;x=top→data;C.x=top;top=top→link;D.x=top→data;

（分数：1.00）

A.

√

B.

C.

D.解析：[解析]出栈操作由两部分组成：取元素存储在其他空间和调整栈顶指针位置。为完成这两部分可以执行以下语句：x=top→data;//取元素存储在其他空间top=top→link;//调整栈顶指针位置27.设循环队列的存储容量为maxSize，队头和队尾指针分别为front和rear。若有一个循环队列Q，则可应用下列______算式计算队列元素个数。A.Q.rear-Q.frontB.Q.rear-Q.front+1C.(Q.rear-Q.front)%maxSize+1D.(Q.rear-Q.front+maxSize)%maxSize

（分数：1.00）

A.

B.

C.

D.

√解析：[解析]随着队列中元素的进队出队的交替进行，对于rear与front两指针，其相对位置不定。当rear＜front时，Q.reai-Q.front+maxSize正好是队列元素个数；当rear＞front时，可以用(Q.rear-Q.front+maxSize)%maxSize得到队列元素个数。28.设一个链式队列q的队头指针和队尾指针分别为front和rear，则判断队列为空的条件是______。A.q.front==q.rearB.q.front==NULL||q.rear==NULLC.q.rear==NULLD.q.front!=NULL

（分数：1.00）

A.

B.

√

C.

D.解析：[解析]当front==NULL或者rear==NULL时，链为空，则对应的链队也为空。29.对一个初始为空的队列Q执行操作enQueue(Q,a)，enQueue(Q,b)，deQueue(Q,x)，deQueue(Q,Y)之后，再执行isEmpty(Q)，返回的值是______。A.aB.bC.1D.0

（分数：1.00）

A.

B.

C.

√

D.解析：[解析]对一个空队列，执行两次进队操作和两次出队操作后，显然栈变为空状态，此时执行判断队列是否为空的操作Q.isEmpty()，函数返回true。30.设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b，d，c，f，e，a，g，则栈S的容量至少是______。A.1B.2C.3D.4

（分数：1.00）

A.

B.

C.

√

D.解析：[解析]根据队列的FIFO性质，出队顺序与入队顺序一致，也就是说，与出栈顺序一致。如果用S表示进栈，用X表示出栈，按照题意，进栈和出栈序列见下表。{{B}}进栈与出栈情况{{/B}}进栈序列ab进出操作SSXSSXXSSXXXSX栈的内容aabaacacdacaaeaefaeag出栈序列bdcfeag由表可知，栈中最多时有3个元素，所以栈的容量最少为3。31.已知输入序列是1234，则输入受限(仅允许由一端输入)但输出不受限(两端均可输出)的双端队列不可能得到的输出序列是______。A.4231B.1324C.3214D.2341

（分数：1.00）

A.

√

B.

C.

D.解析：[解析]设双端队列的两端为e1和e2，e1端允许输入，e1和e2端都允许输出。若在e1端输出，相当于栈；若在e2端输出，相当于队列。

对于选项A(4231)，要求先输出4，有一种进队方案：1e12e13e14e1，然后从e1端输出4，但由于2夹在1和3之间，下一个输出的不可能是2，所以选项A是不可能的输出序列。

对于选项B(1324)，一种操作顺序是1e1进1e1出2e1进3e1进3e1出2e1出4e1进4e1出。

对于选项C(3214)，一种操作顺序是1e1进2e1进3e1进3e1出2e1出1e1出4e1进4e1出。

对于选项D(2341)，一种操作顺序是1e1进2e1进2e1出3e1进3e1出4e1进4e1出1e1出。32.已知输入序列是abcd，则经过输出受限的双端队列后能得到的输出序列是______。A.dacbB.cadbC.dbcaD.dbac

（分数：1.00）

A.

B.

√

C.

D.解析：[解析]设双端队列的两端为e1和e2，e2端允许输出，e1和e2两端都允许输入。若在e1端输入，相当于队列；若在e2端输入，相当于栈。

对于选项A(dacb)，要求先输出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出；若要求下一个输出b，应执行操作ae1进be2进ce1进，队列中是cab，输出b后，下一个输出的不可能是c，选项D是不可能的输出序列。33.设求解某问题的递归算法如下：

voidF(intn)

{

if(n==1)Move(1);

else

{

F(n-1);

Move(n);

F(n-1);

}

}

在求解该算法的计算时间时，仅考虑算法Move所做的计算，且Move为常数级算法。算法F的计算时间T(n)的递推关系式为______。A.T(n)=T(n-1)+1B.T(n)=2T(n-1)C.T(n)=2T(n-1)+1D.T(n)=2T(n+1)+1

（分数：1.00）

A.

B.

C.

√

D.解析：[解析]根据题目中程序代码的递归框架可知，该程序把一个规模为n的问题转化为两个规模为n-1的同样问题外加一个常量复杂度的操作来求解，因此其递推关系为T(n)=2T(n-1)+O(1)，可近似为T(n)=2T(n-1)+1。34.一个二维数组A[10][20]按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址为______。A.226B.322C.341D.342

（分数：1.00）

A.

B.

√

C.

D.解析：[解析]此类型题目基础题部分已经讲过，A[6][2]的地址=200+6×20+2=322。35.一个二维数组A[10][20]按列存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址为______。A.226B.322C.341D.342

（分数：1.00）

A.

√

B.

C.

D.解析：[解析]此类型题目基础题部分已经讲过，A[6][2]的地址=200+2×10+6=226。36.将一个n×n的对称矩阵A的下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]在B中的存放位置是______。A.(i+3)×i/2B.(i+1)×i/2C.(2n-i+1)×i/2D.(2n-i-1)×i/2

（分数：1.00）

A.

√

B.

C.

D.解析：[解析]第i行前面存有i行，元素个数为1+2+…+i=(i+1)×i/2，第i行中第i列前有i个元素，则A[i][i]在B中的存放位置为(i+1)×i/2+i=(i+3)×i/2。37.设有一个n阶的三对角线矩阵A的对角元素A[i][j]可存放于一个一维数组B中，要求行下标必须满足0≤i≤n-1，而列下标必须满足______。A.0≤j≤n-1B.i-1≤j≤i+1C.0≤j≤iD.i≤j≤n

（分数：1.00）

A.

B.

√

C.

D.解析：[解析]三对角线矩阵属于带状矩阵，如图所示。带状矩阵下标范围可以表示为i-1≤j≤i+1，因此本题选B。[*]二、{{B}}综合应用题{{/B}}(总题数：2，分数：16.00)Legendre多项式定义如下：

（分数：8.00）(1).编写一个递归算法，计算该多项式的值。（分数：4.00）__________________________________________________________________________________________

正确答案：(递归算法可以根据函数的定义来编写。floatLegendre_(floatx,intn){if(n==0)return1;if(n==1)returnx;return((2*n-1)*x*Legendre(x,n-1)-(n-1)*Legendre(x,n-2))/n;})解析：(2).编写一个非递归算法，计算该多项式的值。（分数：4.00）__________________________________________________________________________________________

正确答案：(使用迭代法的非递归算法：从多项式的定义中可以看出，要求Legendre(x,n)，必须先求Legendre(x,n-1)和Legendre(x,n-2)，递归结束于Legendre(x,0)和Legendre(x,1)。只要用backone保存Legendre(x,n-1)，用backtwo保存Legendre(x,n-2)，即可求Legendre(x,n)。不需要使用栈编写非递归算法。用这种思路编写的非递归算法代码如下：floatLegendre(floatx,intn){floatcurrent,backone,backtwo;inti;if(n==0)return1;if(n==1)returnx;backone=x;backtwo=1;for(i=2;i＜=n;++i){current=((2*n-1)*x*backone-(n-1)*backtwo)/n;ba