1、栈与队列模拟试卷 3 及答案与解析一、单项选择题1 一个栈的输入序列为 1，2，3，n，若输出序列的第一个元素是 n，输出第i(1in)个元素是( ) 。（A）不确定（B） n-i+l（C） i（D）ni2 若一个栈的输入序列为 l，2，3，n，输出序列的第一个元素是 i，则第 j 个输出元素是( ) 。（A）i-j-1（B） i-j（C） j-i+1（D）不确定3 若已知一个栈的入栈序列是 1，2，3，n，其输出序列为p1，p 2，p 3，p n，若 pn 是 n，则 pi 是( )。（A）i（B） n-i（C） n-i+l（D）不确定4 有 6 个元素 6，5，4，3，2，1 的顺序进栈，
2、下列不合法的出栈序列是( )。（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，65 若一个栈以向量 Vn存储，初始栈顶指针 top 为 n+l，则下面 x 进栈的正确操作是( )。（A）top=top+1；Vtop=x（B） Vtop=x；top=top+1（C） top=top-1；Vtop=x（D）Vtop=x ；top=top-16 若栈采用顺序存储方式存储，现两栈共享空间 V1m ，topi代表第 i 个栈(i=l，2)栈顶，栈 1 的底在 V1，栈 2 的底在 Vm，则栈满的条件是( )。（A）top2-top1 =0
3、（B） top1+1=top2（C） top1+top2=m（D）top1=top27 栈在( )中应用。（A）递归调用（B）子程序调用（C）表达式求值（D）A，B，C8 一个递归算法必须包括( )。（A）递归部分（B）终止条件和递归部分（C）迭代部分（D）终止条件和迭代部分9 执行完下列语句段后，i 值为( )。int f(int x)return(x0)?x*f(x 一 1)：2)；int i；i=f(f(1)；（A）2（B） 4（C） 8（D）无限递归10 表达式 a*(b+C)一 d 的后缀表达式是( )。（A）abCd*+-（B） abC+*d-（C） abC*+d-（D）-+*ab
4、Cd11 递归过程或函数调用时，处理参数及返回地址，要用一种称为( )的数据结构。（A）队列（B）多维数组（C）栈（D）线性表12 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为( )。（A）1 和 5（B） 2 和 4（C） 4 和 2（D）5 和 113 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储， a11 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a85 的存储地址为( )。（A）13（B） 33（C） 1 8（D）40
5、14 Ann是对称矩阵，将下面三角(包括对角线)以行序存储到一维数组 Tn(n+1)2中，则对任一上三角元素 aij对应 Tk的下标 k 是( )。（A）i(i1) 2+j（B） j(j 一 1)2+i（C） i(ji)2+1（D）j(i1) 2+115 设二维数组 Amn(即 m 行 n 列)按行存储在数组 B1mn中，则二维数组元素 Aij在一维数组 B 中的下标为( )。（A）(i 1)n+j（B） (i 一 1)n+j-1（C） i(j 一 1)（D）jm+i l16 有一个 10090 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节
6、数是( )。（A）60（B） 66（C） 18000（D）33二、综合题17 有 5 个元素，其入栈次序为：A，B，C，D，E ，在各种可能的出栈次序中，以元素 C，D 最先出栈(即 C 第一个且 D 第二个出栈)的次序有哪几个?18 如果输入序列为 1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，l，2 和 l，3，5，4，2，6；请说明为什么不能或如何才能得到。19 顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为：listarrayn1，队列头指针为 front，队列尾指针为rear，则 listarrayrear表
7、示下一个可以插入队列的位置。请解释其原因。20 一个 nn 的对称矩阵，如果以行或列为主序存入内存，则其容量为多少?21 设有上三角矩阵(a ij)nn，将其上三角中的元素按先行后列的顺序存于数组 Bm中，使得 Bk=aij 且 k=f1(i)+f2(j)+C，请推导出函数 f1、f 2 和常数 C，要求 f1 和 f2 中不含常数项。22 设有两个栈 s1、s2 都采用顺序栈方式，并且共享一个存储区maxsize 一 1，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 s1、s2 有关入栈和出栈的操作算法。23 请利用两个栈 s1 和 s2 来模拟一个队列。已知
8、栈的三个运算定义如下：PUSH(ST，x)：元素 x 入 ST 栈；POP(ST，x)：ST 栈顶元素出栈，赋给变量 x；Sempty(ST)：判 ST 栈是否为空。那么，如何利用栈的运算来实现该队列的 3 个运算：(1)enqueue：插入一个元素入队列；(2)deqtleue：删除一个元素出队列；(3)q_empty：判队列为空。24 双端队列(duque)是一个可以在任一端进行插入和删除的线性表。现采用一个一维数组作为双端队列的数据存储结构，使用 c 语言描述如下：#deftne maxsize 32数组中可容纳的元素个数typedef struct datatype elemmaxsi
9、ze；int endl，end2；duque；试编写两个算法 add(duque QU，datatype x，int tag)和 delete(duque QU，datatype&x，int tag)用以在此双端队列的任一端进行插入和删除。当 tag=0 时在左端 endl 端操作，当 tag=1 时在右端 end2 端操作。25 已知 q 是一个非空队列，s 是一个空栈。仅用队列和栈的 ADT()函数和少量工作变量，使用 Pascal 或 C 语言编写一个算法，将队列 Q 中的所有元素逆置。(1)栈的 ADT()函数有：makeEmpty(s)； 置空栈push(s，value)；新元素 v
10、alue 进栈pop(s)； 出栈，返回栈顶值isEmpty(s)； 判栈空否(2)队列的 ADT()函数有：enQUeue(q，value)；元素 value 进队deQueue(q)； 出队列，返回队头值isEmpty(q)； 判队列空否26 线性表中元素存放在数组 A(1n)中，元素是整型数。试写出递归算法求出数组 A 中的最大和最小元素。27 设数组 A2n中存放有 n 个负数和 n 个正数，且随机存放。现要求按负数、正数相问存放，请写出实现此要求的算法。算法要求：不能使用额外的存储空间，但可使用少量工作单元，算法的时间复杂度应为 O(n)。28 设有一个长度为 n 的由“0” 和“1
11、” 元素组成的输入序列，存于数组 An中。设计一个算法，依次让每个元素通过一个栈 s(容量n)而得到一个输出序列，使得输出序列中“0”元素都出现在“1”元素之前。输出序列存人数组 Bn中。29 给定一个整数数组 BN，数组 B 中连续的相等元素构成的子序列称为平台。试设计算法，求出 B 中最长平台的长度。30 给定 nm 矩阵 Aab，cd，并设 Ai， jAi，j+1(0ib，cjd 一 1)和 Ai， jAi+1，j(0ib1，ejd)。设计一算法判定 x 的值是否在 A 中，要求时间复杂度为 D(m+n)。31 设二维数组 A1m，1n含有 mn 个整数。(1)写出算法 (Pascal
12、过程或 C 函数)：判断二维数组 A 中所有元素是否互不相同并输出相关信息(yes no) 。(2)试分析算法的时间复杂度。32 已知两个定长数组 A、B，它们分别存放两个非降序有序序列，请编写程序把数组 B 序列中的数逐个插入到数组 A 序列中，完成后两个数组中的数分别有序 (非降序)并且数组 A 中所有的数都不大于数组 B 中的任意一个数。要求，不能另开辟空间，也不能对任意一个数组进行排序操作。例如，数组 A 为：4，12，28；数组 B 为：1，7，9，29，45输出结果为：1，4，7(数组 A)9，12，28，29，45(数组 B)33 设数组 An中，An 一 2k+1n 一 k和
13、An 一 k+1n中元素各自从小到大排好序，试设计一个算法使 An 一 2k+1n按从小到大次序排好序。要求空间复杂度为 O(1)，并分析算法所需的计算时间。34 设 A100是一个记录构成的数组， B100是一个整数数组，其值介于 1100，现要求按 B100的内容调整 A 中记录的次序，比如，当 B1=11 时，则要求将A1的内容调整到 A11中去。规定可使用的附加空间为 D(1)。35 给定有 m 个整数的递增有序数组 A1m和有 n 个整数的递减有序数组B1n ，试写出算法：将数组 A 和 B 归并为递增有序数组 C1m+n 。(要求：算法的时间复杂度为 D(m+n)栈与队列模拟试卷
14、3 答案与解析一、单项选择题1 【正确答案】 B【试题解析】 此题考查的知识点是栈的后进先出特点。若输出序列的第一个元素是 n，说明前 n 一 1 个元素均入栈，出栈时只能按入栈顺序后进先出，所以选 B。因为是从后向前数，所以出栈的第 i 个元素并不是人栈时的 i，而 ni 是第 i 一 1元素，所以 C、D 都错，因为能确定出栈元素，所以 A 也错。【知识模块】 栈与队列、数组2 【正确答案】 D【试题解析】 此题考查的知识点是栈的后进先出特点。若输出序列的第一个元素是 i，只能说明前 i 一 1 个元素均入栈，而第 j 个元素何时入、出栈并不能确定，所以选 D。【知识模块】 栈与队列、数组
15、3 【正确答案】 D【试题解析】 此题考查的知识点是栈的后进先出特点。输出序列的最后一个元素是 n，其前面的序列是不确定的。比如入栈序列为 1，2，3，出栈序列可以是l，2，3，也可以是 2，1，3，所以 pi 不确定，应选 D。【知识模块】 栈与队列、数组4 【正确答案】 C【试题解析】 此题考查的知识点是栈的后进先出特点。考查出栈序列，要保证先人栈的一定不能在后入栈的前面出栈，C 选项中的 6 在 5 前人栈，5 没有出栈，6却出栈了，所以不合法。其他都符合规律。所以选 C。【知识模块】 栈与队列、数组5 【正确答案】 C【试题解析】 此题考查的知识点是人栈的具体操作。操作时要看栈顶的地址
16、，先取得空间，再入栈。本题栈顶为 n+1，应该用减法，所以选 C。D 是先存人，破坏原有数据，所以错。【知识模块】 栈与队列、数组6 【正确答案】 B【试题解析】 此题考查的知识点是入栈的具体操作。判断栈是否满要看两个栈顶是否相邻，当 top1+l=top2，或 top2一 1=top1时都表示栈满，所以选 B，而A、C 没有任何意义。D 表示已经出现覆盖了，也是错的。【知识模块】 栈与队列、数组7 【正确答案】 D【试题解析】 此题考查的知识点是栈的应用。由于栈的特殊性质，所以在递归调用、子程序调用、表达式求值时都要用到，所以选 D。A 、B、C 不全面。【知识模块】 栈与队列、数组8 【正
17、确答案】 B【试题解析】 此题考查的知识点是递归算法的组成部分。一个递归算法主要包括终止条件和递归部分，所以选 B。A 不全面，C、D 不是递归算法。【知识模块】 栈与队列、数组9 【正确答案】 B【试题解析】 此题考查的知识点是递归算法的分析。根据题意可计算 f(0)=2， f(1)=2，f(2)=4 ，所以选 B。【知识模块】 栈与队列、数组10 【正确答案】 B【试题解析】 此题考查的知识点是利用栈完成表达式的中后缀转换。顺序扫描表达式，操作数顺序输出，而运算符的输出顺序根据算术运算符的优先级确定。保证栈外运算符优先级比栈内低，若高则入栈，否则出栈输出。本题中输出顺序为 a 输出，*进栈
18、，(进栈，b 输出，+进栈，C 输出，此时)低于+ ，所以“+”输出。“)”与“(”相等，出栈删除，一低于*，所以*出栈，此时输出序列为 abC+*，一人栈，输出 d，输出一，结束。所以选 B。【知识模块】 栈与队列、数组11 【正确答案】 C【试题解析】 此题考查的知识点是栈的应用。要处理参数及返回地址，需要后进先出规则，应选 C。A 是先进先出规则，B 是普通的存储结构，D 是普通的逻辑结构。【知识模块】 栈与队列、数组12 【正确答案】 B【试题解析】 此题考查的知识点是队列的特征。此题考查顺序存取时的位置计算，按顺时针计算，所以删除 front+1，插入 rear+l，计算后 rear
19、=2，front=4 ，应选B。【知识模块】 栈与队列、数组13 【正确答案】 B【试题解析】 此题考查的知识点是顺序存储数组的地址计算。从 0 存起时，公式为 aij=i(i1)2+j1(ij)，本题从 1 开始存，通过计算 a85=33，应选 B。【知识模块】 栈与队列、数组14 【正确答案】 B【试题解析】 此题考查的知识点是顺序存储数组的地址计算。从 0 存起时，aij对应的 Tk=j(j 一 1)2+i 一 1(ij) ，从 1 存起时 Tk=j(j 一 1)2+i(ij) ，应选 B。【知识模块】 栈与队列、数组15 【正确答案】 A【试题解析】 此题考查的知识点是顺序存储数组的地
20、址计算。要先计算前 i 一 1行的个数为(i 一 1)n，再加上第 i 行的 j 个元素即为所求。所以应选 A。【知识模块】 栈与队列、数组16 【正确答案】 B【试题解析】 此题考查的知识点是稀疏矩阵的压缩存储。按三元组的定义，该矩阵大小为 113，每个整型数占 2 字节，总字节数为 332=66，应选 B。【知识模块】 栈与队列、数组二、综合题17 【正确答案】 3 个：C，D，E，B，A；C，D，B，E ，A ；C，D，B，A，E【试题解析】 此题考查的知识点是栈的后进先出特点。按题意，C 先出，说明A、B 已人栈，D 出栈，再出栈，E 可以入栈就出栈，可以有序列C，D，E，B，A；也可
21、以 B 先出“E” 再人，再出，得序列 C，D，B，E，A ；还可以 B、A 都出栈后，E 再入栈出栈，得序列 C，D ，B，A ，E。只有这三种情况。【知识模块】 栈与队列、数组18 【正确答案】 只能得到序列 1，3，5，4，2，6，原因见解析。【试题解析】 此问题考查的知识点是栈的后进先出特点。输入序列为 1，2，3，4，5，6，不能得出 4，3，5，6，1，2，其理由是，输出序列最后两元素是 1，2，前面 4 个元素(4，3，5，6)得到后，栈中元素剩 1，2 两个元素，且 2 在栈顶，不可能栈底元素 1 在栈顶元素 2 之前出栈。得到1，3，5，4，2，6 的过程如下：1 入栈并出栈
22、，得到部：分输出序列；然后 2 和 3入栈，3 出栈，部分输出序列变为：1，3；接着 4 和 5 人栈，5，4 和 2 依次出栈，部分输出序列变为 l，3，5，4，2；最后 6 人栈并退栈，得最终结果为：l，3，5，4，2，6。【知识模块】 栈与队列、数组19 【正确答案】 栈的特点是后进先出，队列的特点是先进先出。初始时设栈 s1和栈 s2 均为空。(1)用栈 s1 和 s2 模拟一个队列的输入。设 sl 和 s2 容量相等。分以下三种情况讨论：若 s1 未满，则元素入 s1 栈；若 s1 满，s2 空，则将 s1 全部元素退栈，再压栈人 s2，之后元素人 s1 栈；若 s1 满，s2 不空
23、(已有出队列元素)，则不能人队。(2)用栈 s1 和 s2 模拟队列出队(删除)。若栈 s2 不空，退栈，即是队列的出队；若s2 为空且 sl 不空，则将 s1 栈中全部元素退栈，并依次压入 s2 中，s2 栈顶元素退栈，这就是相当于队列的出队。若栈 s1 为空并且 s2 也为空，队列空，不能出队。(3)判队空。若栈 s1 为空，并且 s2 也为空，才是队列空。【试题解析】 此问题考查的知识点是顺序存放的队列数据量问题。循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队列的满与空问题。例如：在队列长 10 的循环队列中，若假定队头指针 front 指向队头元素的前一位
24、置，而队尾指针指向队尾元素，则 front=3，rear=7 的情况下，连续出队 4个元素，则 front=rear 为队空；如果连续入队 6 个元素，则 front=rear 为队满。如何判断这种情况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。即假设 front=rear 为队空，而(rear+1) 表长=front 为队满，或通过设标记 tag。若 tag=0，front=rear 则为队空；若 tag=l，因入队而使得：front=rear，则为队满。本题中队列尾指针 rear，指向队尾元素的下一位置，listarrayrear表示下一个人队的元素。在这种情况下，我们可规定，队
25、头指针 front 指向队首元素。当front=rear 时为队空，当(rear+1) n=front 时为队满。出队操作 (在队列不空情况下)队头指针是 front=(front+1)n 。【知识模块】 栈与队列、数组20 【正确答案】 n(n+1) 2(压缩存储)或 n2(不采用压缩存储)。【试题解析】 此问题考查的知识点是数组的存放问题。对称矩阵可以只存上三角或下三角。所用空间为 1，2，3，n 之和。【知识模块】 栈与队列、数组21 【正确答案】 上三角矩阵第 1 行有 n 个元素，第 il 行有 n 一(i 一 1)+1 个元素，第 1 行到第 il 行是等腰梯形，而第 i 行上第
26、j 个元素(即 aij)是第 i 行上第 j 一 i+1个元素，故元素 aij 在一维数组中的存储位置(下标 k)为： k=(n+(n 一(i1)+1)(i1)2+(j 一 i+1)=(2n 一 i+2)(i 一 1)2+j 一 i+1 进一步整理为：k=(n+12)ii22+j 一 n。则得 f1(i)=(n+12)ii 22，f 2(j)=j，c=一 n。【试题解析】 此问题考查的知识点是上三角矩阵的存储方式。【知识模块】 栈与队列、数组22 【正确答案】 #define maxsize 两栈共享顺序存储空间所能达到的最多元素数#define elemtp int假设元素类型为整型type
27、def structelemtp stackmaxsize；栈空间int top2；top 为两个栈顶指针stk；stk S；s 是如上定义的结构类型变量，为全局变量(1)入栈操作int push(int i，int X)入栈操作。i 为栈号，i=0 表示左边的栈 sl，i=1 表示右边的栈 s2，x 是人栈元素。入栈成功返回 1，否则返回 0if(i0 i1)printf(”栈号输入不对”)；exit(0)；if(s top1一 stop0=1)printf(”栈已满n”)；return(0)；switch(i)case 0：Sstack+s top0=x ；return(1) ；break
28、；case 1：Sstack-S top1=X ；return(1) ； push(2)退栈操作elemtp pop(int i)退栈算法。i 代表栈号，i=0 时为 s1 栈，i-1 时为 s2 栈。退栈成功返回退栈元素，否则返回一 1if(i0i 1)printf(“栈号输入错误n”)；exit(0)；switch(i)case 0：if(S top0=一 1)printf(”栈空n”) ； return(一 1)；else return(sstacks top0一)；case 1：if(S top1=maxsizeprintf(“栈空n”) ；return( 一 1)；else retu
29、rn(sstacks top1+)；算法结束【试题解析】 此问题考查的知识点是栈的基本操作。两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1 栈顶指针为一 1， s2 栈顶为 maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。实现时请注意算法中两栈人栈和退栈时的栈顶指针的计算，可以用两栈共享空间示意图表示，s1栈是通常意义下的栈，而 s2 栈人栈操作时，其栈顶指针左移 (减 1)，退栈时，栈顶指针右移(加 1)。【知识模块】 栈与队列、数组23 【正确答案】 (1)int enqueue(stack s1，elemtp x)s1 是容量为 n 的栈，栈中
30、元素类型是 elemtp。本算法将 x 入栈，若入栈成功返回 1，否则返回 0if(topl=n!Sempty(s2)topl 是栈 s1 的栈顶指针，是全局变量IDrintf(”栈满”)；return(0)；sl 满 s2 非空，这时 s1 不能再人栈if(topl=：nSempty(s2)若 s2 为空，先将 sl 退栈，元素再压栈到 s2while(!Sempty(s1) POP(s1，x)；PUSH(s2 ，x) ；PUSH(sl，x)；return(1)；x 入栈，实现了队列元素的入队(2)void deqoeue(stack s2，s1)s2 是输出栈，本算法将 s2 栈顶元素退栈
31、，实现队列元素的出队if(!Sempty(s2)栈 s2 不空，则直接出队POP(s2， x)；printf(” 出队元素为 ”，x)；else处理 s2 空栈if(sempty(s1)lorintf(”队列空”) ；exit(0) ；若输入栈也为空，则判定队空else先将栈 s1 倒人 s2 中，再作出队操作while(! Sempty(s1)POP(s1，x)；PUSH(s2 ，x)；POP(s2，x)；s2 退栈相当队列出队printf(”出队元素 ”，x)；结束算法 dequue(3)int q_empty()本算法判用栈 s1 和 s2 模拟的队列是否为空if(Sempty(s1)&
32、Sempty(s2)return(1)；队列空else retum(0)；队列不空【试题解析】 此问题考查的知识点是栈、队列的基本操作。用两个栈 sl 和 s2 模拟一个队列时，sl 作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈 s1 退栈并逐个压入栈 s2 中，s1 中最先入栈的元素，在 s2 中处于栈顶。s2 退栈，相当于队列的出队，实现了先进先出。显然，只有栈 s2 为空且 sl 也为空，才算是队列空。实现时可以假定栈 s1 和栈 s2 容量相同。出队从栈 s2 出，当 s2 为空时，若 s1 不空，则将 s1 倒入 s2 再出栈。入队在 sl，当 s1 满后，若
33、s2 空，则将 81 倒入 s2，之后再人队。因此队列的容量为两栈容量之和。元素从栈 s1 倒入 s2，必须在 s2 空的情况下才能进行，即在要求出队操作时，若 s2 空，则不论 s1 元素多少(只要不空)，就要全部倒入 s2 中。【知识模块】 栈与队列、数组24 【正确答案】 int add(eque Qu，datatype x，int tag)在双端队列 Qu 中插入元素 x，若插入成功，返回插入元素在 QU 中的下标；插入失败返回一 1。tag=0 表示在 endl 端插入；tag=1 表示在 end2 端插入if QUendl=QUend2 prinfl(“队满”)；return(一
34、1)；switch(tag)case 0：在 endl 端插入QUendl=x ；插入 XQUendl： (QUendl-1)MOD maxsize ；修改 endlreturn(QU endl+1)MOD maxsize)；返回插入元素的下标case 1：在 end2 端插入QUend2=X；QUend2=(QUend2+1)MOD maxsize；return(QU end2 一 1)MOD maxsize； addint delete(eque QU，datatype x，int tag 1)本算法在双端队列 QU 中删除元素 x，tag=0 时从 endl 端删除，tag=1 时从en
35、d2 端删除。删除成功返回 1，否则返回 0 if(QHendl+1)MOD maxsize=QU end2 printf(”队空”)；return(0) ；switch(tag)case 0：从 endl 端删除i=(QUendl+1)MOD maxsize；i 是 endl 端最后插入的元素下标while(i!=QUend2)&(QU elemi!=X)i=(i+1)MOD maxsize；查找被删除元素 x 的位置if(QUelemi-x)&(i!=QUend2)j=i；while(j 一 1+maxsize)MOD maxsize!=QHendl)QHelemj=QUelem(j 一
36、1+maxsize)MOD maxsize；j=(j 一 1+maxsize)MOD maxsize；移动元素，覆盖达到删除QUendl=(Quendl+1)MOD maxsize；修改 endl 指针return(1)；else return(0)；结束从 endl 端删除case 1：从 end2 端删除 i=(QUend2 1+maxsize)MOD maxsize；i 是 end2 端最后插入的元素下标while(i!=Quendl)&(QU elemi!=x)i=(i 一 1+maxsize)MOD maxsize；查找被删除元素 X 的下标if(QUelemi=x)&(i!：Que
37、ndl) 被删除元素找到j=i；while(j+1)MOD maxsize!=QUend2)Quelemj=QUelem(j+1)MOD maxsize ；j=(j+1)MOD maxsize；移动元素，覆盖达到删除QUend2=(QUend21+maxsize)MOD maxsize；修改 end2 指针return(1)；返回删除成功的信息else return(0)；删除失败结束在 end2 端删除结束 delete【知识模块】 栈与队列、数组25 【正确答案】 void invert(queue q)q 是一个非空队列，本算法利用空栈 s 和已给的几个栈和队列的 ADT()函数，将队列
38、 q 中的元素逆置makeEmpty(s)；置空栈while(!isEmpty(q)队列 q 中元素出队value=deQueue(q)；push(s ，value) ；将出队元素压人栈中while(!isEmpty(s)栈中元素退栈value：pop(s)；enQueue(q，value) ；将出栈元素人队列 q算法 invert 结束【试题解析】 此问题考查的知识点是队列和栈的特点和操作。根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个退栈的元素成为队列中第一个
39、元素，最后退栈的元素(出队时第一个元素)成了最后入队的元素，从而实现了原队列的逆置。【知识模块】 栈与队列、数组26 【正确答案】 int MinMaxValue(int A，int n，int*max，int*min)一维数组 A 中存放有 n 个整型数，本算法递归地求出其中的最小数 if(n0)if(*max0)int temp；temp=Aforward；Aforward=Aback；Aback=temp；【试题解析】 此问题考查的知识点是顺序存放数据的查找问题。相间存放，说明如果所有负数在奇数位置上，则所有正数在偶数位置上，反之亦然。假设把所有负数都在奇数位置上，所有正数都在偶数位置上
40、，则 A0，A2 ，A2n 一 2位置应该都存放负数，A1，A3 ，A2n-1位置上应该存放正数。可以设计两个索引 forward 和 back，初始分别执行第一个位置和最后一个位置，forward 每次都递增 2，back 每次都递减 2，直到 forward 所指位置的元素为正数，back 所指元素为负数，然后交换 forward 和 back 所指元素。一直到遍历完数组中的所有元素。【知识模块】 栈与队列、数组28 【正确答案】 void sorder(int A，int B) int i，J=0；stack S；for(i=0；it)t=ij+1；k=j；局部最长平台i+；J=i；新平
41、台起点printf(”最长平台长度d，在 B 数组中起始下标为d” ，t ，k)； Platform【试题解析】 此问题考查的知识点是线性结构的查找问题。可以用 t 代表最长平台的长度，用 k 指示最长平台在数组 B 中的起始位置 (下标)。用 j 记住局部平台的起始位置，用 i 指示扫描 b 数组的下标，i 从 0 开始，依次和后续元素比较，若局部平台长度(ij)大于 1 时，则修改最长平台的长度 k(1=ij)和其在 B 中的起始位置(k=j)，直到 B 数组结束，t 即为所求。【知识模块】 栈与队列、数组30 【正确答案】 void search(datatype A ，int a ，b
42、，C，d，datatype X)nxm 矩阵 A，行下标从 a 到 b，列下标从 C 到 d，本算法查找 X 是否在矩阵A 中i=a；j=d；flag=0 ； flag 是成功查到 X 的标志while(i=C)if(AiJ=x)flag=1；break；else if(AiJx)j 一一； else i+；if(flag)printf(“Ad d=d”，i，j，x)；假定 x 为整型else printf(”矩阵 A 中无d 元素”，x)；算法 search 结束【试题解析】 此问题考查的知识点是矩阵的查找。由于矩阵中元素按行和按列都已排序，要求查找时间复杂度为 0(m+n)，因此不能采用常
43、规的二层循环的查找。可以先从右上角(i=a，j=d)元素与 x 比较，只有三种情况：一是 Ai，jx，这情况下向 j 小的方向继续查找；二是 Ai，jAi，j)或向左(当 xB0)x=Am 一 1；Am 一 1=B0；交换 Am 一 1和 B0j=1；while(j=0&Aix)Ai+1=Ai 一一 ；寻找 B0的插入位置Ai+1=x；算法结束【试题解析】 此问题考查的知识点是线性结构的查找。题目要求调整后数组 A 中所有数均不大于数组 B 中所有数。因两数组分别有序，实际是要求数组 A 的最后一个数 Am 一 1不大于数组 B 的第一个数 B0。由于要求将数组 B 的数插入到数组 A 中。因
44、此比较 Am 一 1和 BO，如 Am 一 1B0，则交换。交换后仍保持数组 A 和数组 B 有序。重复以上步骤，直到 Am 一 1B0为止。【知识模块】 栈与队列、数组33 【正确答案】 void adjust(int A，int n)数组 An 一 2k+1nk和nk+1n中元素分别升序，算法使 An一 2k+1n升序i=nk；j=nk+1 ；while(AiAj)x=Ai；Ai=Aj；值小者左移，值大者暂存于 xk=j+1；while(kAk)Ak 一 1=Ak+；调整后段有序Ak 一 1=x；i 一一；j 一一；修改前段最后元素和后段第一元素的指针算法结束【试题解析】 此问题考查的知识
45、点是合并两个有序序列。题目中数组 A 的相邻两段分别有序，要求将两段合并为一段有序。由于要求附加空间复杂度为 D(1)，所以将前段最后一个元素与后段第一个元素比较，若正序，则算法结束；若逆序则交换，并将前段的最后一个元素插入到后段中，使后段有序。重复以上过程直到正序为止。最佳情况出现在数组第二段n 一 k+1n中值最小元素 An 一 k+1大于等于第一段值最大元素 An 一 k，只比较一次无须交换。最差情况出现在第一段的最小值大于第二段的最大值，两段数据间发生了 k 次交换，而且每次段交换都在段内发生了平均(k 一 1)次交换，时间复杂度为 O(n)。【知识模块】 栈与队列、数组34 【正确答
46、案】 void CountSort(rectype A，int B)A 是 100 个记录的数组，B 是整型数组，本算法利用数组 B 对 A 进行计数排序int i，j，n=100；i=1：while(i=0)if(ai=0)ck+=bj 一一 ；算法结束【试题解析】 此问题考查的知识点是线性结构的查找。数组 A 和数组 B 的元素分别有序，欲将两数组合并到数组 C，使数组 C 仍有序，应将数组 A 和数组 B 复制到数组 C，只要注意数组 A 和数组 B 数组指针的使用，以及正确处理一个数组读完数据后将另一个数组余下的元素复制到数组 C 中即可。因为不允许另辟空间，而是利用数组 A(空间足够大)，则初始 k=m+n 一 1。【知识模块】 栈与队列、数组
