1、栈、队列和数组模拟试卷 1 及答案与解析一、单项选择题1 数据元素之间的关系称为( )。【北京理工大学 2006 九、2(1 分)】（A）操作（B）结构（C）数据对象（D）数据集合2 (多选 )一个算法具有 ( )等特点。【华中科技大学 2007 二、17(2 分)】（A）有 0 个或多个输入量（B）健壮性（C）正确性（D）可行性3 下面程序的时间复杂性为( )。【南京理工大学 2004 一、4(1 分)】for(int i=0；im；j+)for(int j=0；jn；j+ )aij=i*j；（A）O(n 2)（B） O(m*n)（C） O(m2)（D）O(m+n)4 在下列算法中，“x=x
2、*2”的执行次数是( )。【华中科技大学 2006 一、16(2 分)】int suanfa(int n)int i，j，x=1;for(i=0；in；i+)for(j=i；jn;j+)x=x*2 ；return x；（A）m(n+1)2（B） Nlog2n（C） n2（D）n(n 一 1)25 执行下列算法 suanfa2(1000)，输出结果是( ) 。 【华中科技大学 2006 一、17(2分)】void suanfa2(int n)int i=i;while(i=n)i*=2；printf(“d”，i);（A）2000（B） 512（C） 1024 （D）2 10006 当 n 足够大
3、时下述函数中渐近时间最小的是( )。【哈尔滨工业大学 2005 二、4(1 分)】（A）T(n)=nlog 2n=1000log2n（B） T(n)=nlog23=1 000log2n（C） T(n)=n2=1000log2n（D）T(n)=2nlog 2n=1 000log2n7 下面算法时间复杂度是( )。【华中科技大学 2006 一、18(2 分)】int suanfa3(int n)int i=i，s=l；while(sn)s+=+ireturn i；（A）O(n)（B） O(22)（C） O(log2n)（D）8 下列函数中渐进时间复杂度最小的是( )。【暨南大学 2011 一、2(
4、2 分)】（A）T1(n)=log 2n+5000n（B） T2(n)=n28000n（C） T3(n)=n2+5000n（D）T4(n)=2nlog 2n 一 1000n9 某算法的时间复杂度为 O(n2)，表明该算法的( ) 。【武汉大学 20061（A）问题规模是 n2（B）执行时间等于 n2（C）执行时间与 n2 成正比（D）问题规模与 n2 成正比10 数据结构和数据类型的形式定义分别为：【西南交通大学 2005】Data-Structure=(D，R)DataType=(D，R，p)试选择 D、R、P 的确切含义。( )（A）数据（B）数据元素（C）数据对象（D）关系（E）存储结构
5、11 在汉诺塔递归中，假设碟子的个数为 n，则时间复杂度为( )。【南开大学2005】（A）O(n)（B） O(n2)（C） O(22)（D）12 判定一个栈(最多元素为 m)为空的条件是( ) 。（A）ST 一top 1=0（B） ST 一 top=0（C） ST 一 top!=m（D）ST 一top=m13 判定一个栈(最多元素为 m)为满的条件是( ) 。（A）ST 一top!=0（B） ST 一 top=0（C） ST 一 top!=m 一 1（D）ST 一top=m 一 114 设有一个顺序栈 S，元素 s1，s 2，s 3，s 4，s 5，s 6 依次进栈，如果 6 个元素的出栈顺
6、序为 s2， s 3，s 4，s 6，s 5，s 1，则顺序栈的容量至少应为 ( )。（A）5（B） 4（C） 3（D）215 表达式 a*(b+c)一 d 的后缀表达式是( )。（A）abcd*+一（B） abe-4-*d（C） abc*+d（D）一+*abcd16 栈在( ) 中应用。（A）递归调用（B）子程序调用（C）表达式求值（D）A，B，C17 设 abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为( )。（A）fedcba（B） bcafed（C） dcefba（D）cabdef18 假设以数组 Am存放循环队列的元素，其头、尾指针分别为 front
7、 和 rear，则当前队列中的元素个数为( )。（A）(rearfront)m（B） (frontrear+m)m（C） (rearfront+m)m（D）rearfront+119 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0和 3，当从队列中删除一个元素，再加上两个元素后，则 rear 和 front 的值分别为( )。（A）1 和 5（B） 4 和 2（C） 2 和 4（D）5 和 220 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时( )。（A）仅修改队头指针（B）仅修改队尾指针（C）队头、
8、队尾指针都不要修改（D）队头、队尾指针都可能要修改21 已知输入序列为 abed，经过输出受限的双端队列后，能得到的输出序列是( )。（A）daeb（B） eadb（C） dbea（D）以上答案都不对22 循环队列用数组 A0，m 一 1存放其元素值，已知其头尾指针分别为 front和 rear，则当前元素个数为( ) 。（A）(rearfront+m)MODm（B） rearfront+1（C） rear 一 front 一 1（D）rearfront23 队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作( )。（A）上溢（B）下溢（C）假溢出（D）
9、队列满24 栈和队列的主要区别在于( )。（A）它们的逻辑结构不一样（B）它们的存储结构不一样（C）所包含的运算不一样（D）插入和删除运算的限定不一样25 若循环队列以数组 QO，m 一 1作为其存储结构，变量 rear 表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1)MOD m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。（A）rear 一 length（B） (rear 一 length+m)MOD m（C） (rearlength+1+m)MOD，m（D）mlength26 将一个 41，100，1，100的 i
10、 对角矩阵按行优先顺序存储在一维数组B1，298中，A 中元素 A6665在 B 数组中的位置 K 为( )。（A）33i+32（B） 33i+33（C） 32i+33（D）32i+3227 一个 10090 的稀疏矩阵，有 10 个非 O 元素，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是( )。（A）60（B） 66（C） 18000（D）3328 已知有一维数组0，mn1，若要对应为 m 行、n 列的矩阵，将元素 Ak(0kmn) 表示成矩阵的第 i 行、第 j 列的元素(0im ，0jn)，则下面的对应关系是( )。（A）i=k n ，j=k m（B） i=km，j
11、=km（C） i=kn，j=kn（D）i=k m ，j=k n29 设有 10 阶矩阵 A，其对角线以上的元素 aij(1j10，1ij)均取值为一 3，其他矩阵元素为正整数，现将矩阵 A 压缩存储放在一维数组 Fm中，则 m 为( )。（A）45（B） 46（C） 55（D）5630 若对 n 阶对称矩阵 A1，n，1，n以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组 B1，n(n+1)2 中，则在B 中确定 aij(ij) 的位置 k 的关系是( )。（A）i(i 一 1)2+j（B） j(j 一 1)2+i（C） i(i+1)2+j（D）j(j+1)2+
12、i二、简答题31 设 a，b， c 三个元素的进栈次序是 a，b，c，符号 push 与 pop 分别表示对堆栈进行一次进栈操作与一次出栈操作。32 简述队列与循环队列。33 顺序队列如何解决假溢出问题?三、计算题34 n 阶对称矩阵(a ij)nn 采用压缩存储存放于一维数组 Fm中，从 FO开始存储，给出矩阵的压缩存储方式及任一矩阵元素 aij(Oi，jn 一 1)的地址计算公式，并计算 m。四、综合题35 给定 nm 矩阵 Aab，cd，并设 Ai，jAij+1(aib，cjd 一 1)和Ai，j+1Ai+1j(aib 一 l，cjd)。设计算法判断 x 的值是否在 A 中，要求时间为
13、O(m+n)。栈、队列和数组模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 B2 【正确答案】 B3 【正确答案】 B4 【正确答案】 A5 【正确答案】 C6 【正确答案】 B7 【正确答案】 A8 【正确答案】 A9 【正确答案】 C10 【正确答案】 C,D11 【正确答案】 C12 【正确答案】 B【试题解析】 对于栈来说，栈空的条件就是栈顶指针指向了 O 的位置( 有些情况是“一 1”的位置)时，表示栈空。【知识模块】 栈、队列和数组13 【正确答案】 D【试题解析】 对于栈来说，栈满的条件就是栈顶指针指向了 m 一 1 的位置。【知识模块】 栈、队列和数组14 【正确答案】
14、 C【试题解析】 顺序栈的容量为 3。【知识模块】 栈、队列和数组15 【正确答案】 B【知识模块】 栈、队列和数组16 【正确答案】 D【试题解析】 栈的基本应用有数制转换(十转 N)，括号匹配的检验，表达式求值，汉诺(Hanoi)塔；队列的基本应用是模拟事件发生的先后顺序。【知识模块】 栈、队列和数组17 【正确答案】 D【试题解析】 本题为考试中经常出现的题型，需要理解。【知识模块】 栈、队列和数组18 【正确答案】 C【试题解析】 此题和循环队列的判空、判满属于一类问题，只要画出这种队列的各种情形问题就自然解决了。【知识模块】 栈、队列和数组19 【正确答案】 B【试题解析】 此题主要
15、考查循环队列的操作过程，考生只要熟悉该过程即可选出正确答案。当然有些考生会误选择选项 D，原因是对数组下标问题尚未搞清楚。【知识模块】 栈、队列和数组20 【正确答案】 D【试题解析】 出队操作时队头和队尾都有可能被修改。【知识模块】 栈、队列和数组21 【正确答案】 B【试题解析】 输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。分析选项 A，输入序列为 abcd，输出序列为 dacb，由输出受限性质可知以 da 开头的结果只有 dabc，选项 A 为错误答案。分析选项 B，输入序列为abcd，输出序列为 cadb，其输入输出顺序为：先在输出端输入 a，然后在非输出端输
16、入 b，这时队列中的序列为 ba，再在输出端输入 c，这时队列中的序列为bac；输出 c，再输出 a；再在输出端输入 d，这时队列中的序列为 bd；输出 d，再输出 b。最后得到输出序列为 cadb。分析选项 C，输入序列为 abcd，输出序列为dbca，由输出受限性质可知以 db 开头的结果只有 dbac，选项 C 为错误答案。【知识模块】 栈、队列和数组22 【正确答案】 A【试题解析】 循环链表中判断链表为空的条件是：front=rear。判断链表为满的条件是：(rear+1)MOD m=front；即在循环链表中，少用一个元素的空间以区分队空和队满，在这种情况下，求循环队列中元素的个数
17、的方法是(rear 一 front+m) MOD m。【知识模块】 栈、队列和数组23 【正确答案】 C【试题解析】 用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除) ，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度(容量)。【知识模块】 栈、队列和数组24 【正确答案】 D【试题解析】 栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时所包含的运算都可能不同。所以正确答案是 D。【知识模块】 栈、队列和数组25 【正确答案】 C【试题解析】
18、 按照循环队列的定义，因为元素移动按照 rear=(rear+1)MOD m 进行，则当数组 Qm 一 1存放了元素之后，下一个人队的元素将存放到 QO中，因此队列的首元素的实际位置是(。rearlength+1+m)MODm。【知识模块】 栈、队列和数组26 【正确答案】 B【知识模块】 栈、队列和数组27 【正确答案】 B【试题解析】 此题考查的知识点是稀疏矩阵的压缩存储。按三元组的定义，该矩阵大小为 113，每个整型数占 2 字节，总字节数为 332=66，应选 B。【知识模块】 栈、队列和数组28 【正确答案】 C【试题解析】 本题是求一维数组向二维数组转化的问题。最简单的方法是把数组
19、A 的第 0n 一 1 共 n 个元素放到数组 B 的第一行，数组 A 的第 n2n1 共 n 个元素放到数组 B 的第二行中，依此类推，数组 A 的最后 n 个元素放到数组 B 的最后一行中。求 Ak在数组 B 中的位置，应先确定 Ak处在哪一行，显然应该是kn 行；然后再确定处在 kn 行的哪一列，显然是 kn。【知识模块】 栈、队列和数组29 【正确答案】 D【试题解析】 考查矩阵压缩存储。对角线以下元素都需要存储，因此共需要121011=55，对角线以上的元素都是一 3，因此只需要存储一次，利用一个存储单元，故该矩阵只需用 55+1=56 个元素来表示。【知识模块】 栈、队列和数组30
20、 【正确答案】 B【试题解析】 将对称矩阵 A 中的下三角的元素存放于 B 数组中，若求 aij(ij)的位置 k 的关系，答案为 A，即 i(一 1)2+j。但是，本题求 aij(ij)的位置 k 的关系，aij(ij)这个元素没被存放，也就是说需要找到与 aij(ij)这个元素相等的元素 aij，这就需要将备选答案 A 中 i(i 一 1)2+j 的 i 与 j 互换，因此正确答案为 B，即 j(j一 1) 2+i。【知识模块】 栈、队列和数组二、简答题31 【正确答案】 (1)本题考查栈这个数据结构，它是一个先进后出的结构，只要注意栈的这个特点即可。所有可能的出栈序列以及操作序列：abc
21、 push(a)；pop(a)；push(b)；pop(b)；push(c)；pop(c)；bac push(a)；push(b)；pop(b)；pop(a)；push(c)；pop(c)；cba push(a)；push(b)；push(c) ；pop(c)；pop(b)；pop(a)；acb push(a)；pop(a)；push(b)；push(c)；pop(c)；pop(b)；bca push(a)；push(b)；pop(b)；push(c) ；pop(c)；PoP(a)；(2)不可能的序列是 cab。因为 c 是第一个出栈的元素，所以此时 a，b 均在栈中压着，它们的出栈次序只能是
22、：先 b 后 a。【知识模块】 栈、队列和数组32 【正确答案】 (1)队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出(FIFO)表。(2)循环队列是解决 “假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“ 牺牲一个存储单元 ”或“作标记”的方法解决“ 队满”和“ 队空”的判定问题。【知识模块】 栈、队列和数组33 【正确答案】 设顺序存储队列用一维数组 Qm表示，其中 m 为队列中元素个数，队列中元素在向量中的下标从 D 到 m 一 1。设队头指针为 front，队尾指针是
23、rear，约定 front 指向队头元素的前一位置， rear 指向队尾元素。当 front=一 1时队空，rear=m 一 1 时为队满。由于队列的性质(“删除” 在队头而“插入”在队尾)，所以当队尾指针 rear=m 一 1 时，若 front一 1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有人队操作，会造成假“溢出” 。其解决办法有两种：一是将队列元素向前“ 平移 ”(占用 O 至 rear 一 front1)；二是将队列看成首尾相连，即循环队列(O，m 一 1)。在循环队列下，仍定义 front=rear 时为队空，而判断队满则用两种办法：一种解法是用“牺牲一个单元 ”，即
24、rear+1=front(准确的是(rear+1) m=front ，m 是队列容量)时为队满。另一种解法是“设标记” 方法，如设标记 tag，tag=0 的情况下，若删除时导致：front=rear 为队空；tag ：1 情况下，若因插入导致 front=rear 则为队满。【知识模块】 栈、队列和数组三、计算题34 【正确答案】 矩阵的压缩存储方式为：只存储下三角矩阵，且以行为优先顺序，aij 元素存放于数组 Fm的第 k 个元素，则 k 与 ij 之间关系为：1+2+3+(i 一 1)+(j 一 1)=i(i 一 1)2+(j 一 1)=k；m=1+2+3+n=n(k+1)2。【知识模块】 栈、队列和数组四、综合题35 【正确答案】 矩阵的特征：每列对应元素后边的大于前边的，每行对应元素下边的大于上边的，所以 Ab，c 是第一列最大的，最后一行最小的，从它开始逐个找，如果 x 大于 Ab，c，说明 x 的列数大于 c，反之说明 x 的行数小于 6。i=b； j=c；d0if(Ai，jx)j=j+1；else if(Ai，jx)i=i 一 1：Break；while(i=a and j=d)【知识模块】 栈、队列和数组
