2022年2022年计算机专业基础综合-试卷 4.pdf

《2022年2022年计算机专业基础综合-试卷 4.pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机专业基础综合-试卷 4.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机专业基础综合（栈、队列和数组）- 试卷 1 ( 总分： 76.00 ，做题时间： 90 分钟 ) 一、单项选择题 ( 总题数： 21，分数： 42.00) 1. 单项选择题1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00 ）_ 解析：2. 栈和队列的主要区别在于( ) 。（分数： 2.00 ）A. 它们的逻辑结构不一样B. 它们的存储结构不一样C.所包含的运算不一样D.插入和删除运算的限定不一样解析：解析：栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。任何数据结构在针对具体问题时所包含的运算都可能

2、不同。所以正确答案是D 。3. 若循环队列以数组Q0 m一 1 作为其存储结构，变量rear 表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1)MOD m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是 ( )。（分数： 2.00 ）A.rear-length B.(rearlength+m)MOD m C.(teat一 length+1+m)MOD m D.m-length 解析：解析：按照循环队列的定义，因为元素移动按照rear=(rear+1)MOD m进行，则当数组Qm一 1 存放了元素之后，下一个入队的元素将存放到Q0 中，因

3、此队列的首元素的实际位置是(rear length+1+m)MOD m。4. 一个以向量Vn 存储的栈，其初始栈顶指针top 为 n+1，则对于 x，其正确的进栈操作是( )。（分数： 2.00 ）A.top=top+1 ；Vtop=x B.Vtop=x；top=top+1 C.top=top-1；Vtop=x D.Vtop=x；top=top-1 解析：解析：此题考查的知识点是入栈的具体操作。操作时要看栈顶的地址，先取得空间，再入栈。本题栈顶为 n+1，应该用减法，所以选C。D 是先存入，破坏原有数据，所以错。5. 为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间

4、，此时应将两栈的栈底分别设在 ( )。（分数： 2.00 ）A. 内存空间的首地址B. 内存空间的尾地址C.内存空间的两端D.内存空间的中间解析：解析：两个栈共享一个内存空间时，需要把两个栈的栈底设在内存空间的两端。6. 已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是( ) 。（分数： 2.00 ）A.dacb B.cadb C.dbca D.以上答案都不对名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 解

5、析：解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。分析选项 A，输入序列为 abcd， 输出序列为dacb， 由输出受限性质可知以da 开头的结果只有dabc， 选项 A为错误答案。分析选项 B，输入序列为abcd，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入 b，这时队列中的序列为ba。再在输出端输入c，这时队列中的序列为bac；输出 c，再输出 a；再在输出端输入d，这时队列中的序列为bd；输出 d，再输出 b。最后得到输出序列为cadb。 分析选项 C，输入序列为 abcd， 输出序列为dbca， 由输出受限性质可知以db 开头

6、的结果只有dbac， 选项 C为错误答案。7. 假设一个序列1，2，3， n 依次进栈，如果出栈的第一个元素是n，那么第 i(1 i n)个出栈的元素是( )。（分数： 2.00 ）A. 不确定B.n-i+l C.i D.n i 解析：解析：进栈的顺序是：1，2， n，且出栈的第一个元素是n，那么根据栈后进先出的特点可知，出栈的顺序依次为：n， 2，1，那么第 ni+1 个出栈元素就是第i 个进栈的元素。8. 假设一个序列1，2，3， n 依次进栈，如果第一个出栈的元素是i ，那么第 j 个出栈的元素是 ( ) 。（分数： 2.00 ）A.i-j-1 B.i-j C.j-i+1 D.不确定的解

7、析：解析：此题考查的知识点是栈的后进先出特点。若输出序列的第一个元素是i ，只能说明前i 1 个元素均入栈，而第j 个元素何时入、出栈并不能确定，所以选D。9. 已知当前栈中有n 个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为 ( )。（分数： 2.00 ）A.n 一 1 B.n C.n+1 D.n 2 解析：解析：由于栈中有n 个元素是执行进栈操作，但是发生上溢，则说明此栈中最多可以包含n 个数据元素，即栈的最大容量为n。10. 设有 5 个元素 a，b，c，d，e 顺序进栈，下列几个选项中，不可能的出栈序列是( )。（分数： 2.00 ）A.a ，

8、b，c，d，e B.d ，e，c，b，a C.a ，c，e，b，d D.c ，b，a，d，e 解析：解析：由进栈出栈规则可知，对于a，b，c，d，e 顺序进栈的五个元素，A、B、D均为可能的出栈序列，所以选C。11. 有 6 个元素按 6，5，4，3，2，1 的顺序依次进栈，不合法的出栈序列是( ) 。（分数： 2.00 ）A.543612 B.453126 C.346521 D.234156 解析：解析：此题考查的知识点是栈的后进先出特点。考查出栈序列，要保证先入栈的一定不能在后入栈的前面出栈， C 选项中的 6 在 5 前入栈， 5 没有出栈， 6 却出栈了，所以不合法。其他都符合规律。所

9、以选C。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 12. 有 5 个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈的次序不包括 ( )。（分数： 2.00 ）A.CDEBA B.CDBEA C.CDBAE D.CDAEB 解析：解析：以元素C，D最先出栈的次序有三个：CDEBA 、CDBEA 、CDBAE 。13. 对于 4 个元素依次进栈，可以得到( )种出栈序列。（分数： 2.00

10、）A.10 B.12 C.14 D.16 解析：解析： n 个入栈元素可得到种出栈序列。本题4 个元素，可有14 种出栈序列。14. 现有两栈，其共享空间为V1m，topi代表第 i 个栈 (i=1 ，2)栈顶，栈 1 的底在 V1 ，栈 2 的底在 Vm ，若两栈均采用顺序存储方式存储，则栈满的条件是( )。（分数： 2.00 ）A. top2一 top1=0 B.top1+1=top2 C.top1+top2=m D.top1=top2 解析： 解析： 此题考查的知识点是入栈的具体操作。判断栈是否满要看两个栈顶是否相邻，当 top1+1=top2或 top21=top1时都表示栈满，所以选

11、B，而 A，C没有任何意义。D表示已经出现覆盖了，也是错的。15. 一个递归算法必须包括( ) 。（分数： 2.00 ）A. 递归部分B. 终止条件和递归部分C.迭代部分D.终止条件和迭代部分解析：解析：此题考查的知识点是递归算法的组成部分。一个递归算法主要包括终止条件和递归部分，所以选 B。A 不全面， C、D不是递归算法。16. 执行完下列语句段后，i 值为 ( )。 int f(int x)return(x0)?x，x*f(x 1)：2)； i=f(f(1); （分数： 2.00 ）A.2 B.4 C.8 D.无限递归解析：解析： 此题考查的知识点是递归算法的分析。根据题意可计算f(0)

12、=2 ，f(1)=2 ，f(2)=4 ，所以选 B。17. 表达式 a*(b+c) 一 d 的后缀表达式是 ( )。（分数： 2.00 ）A.abcd*+ 一B.abe+*d C.abc*+d D.一+*abcd 解析：解析：此题考查的知识点是利用栈完成表达式的中后缀转换。顺序扫描表达式，操作数顺序输出，而运算符的输出顺序根据算术运算符的优先级确定。保证栈外运算符优先级比栈内低，若高则入栈，否则出栈输出。本题中输出顺序为a 输出， *进栈， ( 进栈， b 输出， +进栈， c 输出，此时 ) 低于 +，所以“ +”输名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

13、 - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - 出。“)”与“(”相等，出栈删除，一低于*，所以 * 出栈，此时输出序列为abe+*，一入栈，输出d，输出一，结束。所以选B。18. 为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为( ) 的数据结构。（分数： 2.00 ）A. 队列B. 多维数组C.栈D.线性表解析：解析：此题考查的知识点是栈的应用。要处理参数及返回地址，需要后进先出规则，应选C。A是先进先出规则， B是普通的存储结构，D是普通的逻辑结构。19. 若用一个大小为6 的数组来实

14、现循环队列，且当前rear 和 front的值分别为0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front的值分别为 ( ) 。（分数： 2.00 ）A.1 和 5 B.2 和 4 C.4 和D.5 和 1 解析：解析：此题考查的知识点是队列的特征。此题考查顺序存取时的位置计算，按顺时针计算，所以删除 front+l，插入 rear+1 ，计算后 rear=2 ，front=4，应选 B 。20. 队尾已到达一维数组的最高下标，不能再插入元素， 然而队中元素个数小于队列的长度，这种现象称作( ) 。（分数： 2.00 ）A. 上溢B. 下溢C.假溢出D.队列满解析：解析

15、：解析：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质( 队尾插入和队头删除) ，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数却小于队列的长度 ( 容量 ) 。21. 已知有一维数组A0m n 一 1 ，若要对应为m行、 n 列的矩阵，将元素Ak(0 km n)表示成矩阵的第 i 行、第 j 列的元素 (0 i （分数： 2.00 ）A.i=k n，j=k m B.i=k m ，j=k m C.i=k n，j=k n D.i=k m ，j=k n 解析：解析： 本题是求一维数组向二维数组转化的问题。最简单的方法是把数组A的第 0n 一 1 共

16、n 个元素放到数组 B 的第一行， 数组 A的第 n2n1 共 n 个元素放到数组B的第二行中， 依此类推， 数组 A的最后 n 个元素放到数组B 的最后一行中。求 Ak 在数组 B中的位置，应先确定Ak 处在哪一行，显然应该是 kn 行；然后再确定处在kn 行的哪一列，显然是kn。二、综合应用题 ( 总题数： 14，分数： 34.00) 22. 综合应用题41-47 小题。_ 解析：23. 简述栈、队列、循环队列的定义。（分数： 2.00 ）_ 正确答案： ( 正确答案： (1) 栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈

17、也称后进先出(LIFO) 表。 (2) 队列是允许在一端插入而在名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 另一端删除的线性表， 允许插入的一端叫队尾， 允许删除的一端叫队头。 最先插入队的元素最先离开( 删除 ) ，故队列也常称先进先出(FIFO) 表。 (3) 循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。 )

18、 解析：假设以 I 和 O分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由I 和 O组成的序列表示。 （分数： 4.00 ）(1). 试指出判别给定序列是否合法的一般规则。（分数：2.00 ）_ 正确答案： ( 正确答案：通常有两条规则。第一是给定序列中I 的个数和 O的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，I 的个数要大于或等于O的个数。 ) 解析：(2). 两个不同合法序列( 对同一输入序列 ) 能否得到相同的输出元素序列?如能得到，请举例说明。（分数：2.00 ）_ 正确答案： ( 正确答案：可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的

19、合法序列 ABC和 BAC均可得到输出元素序列ABC 。对于合法序列ABC ，我们使用本题约定的101010 操作序列；对于合法序列 BAC ，我们使用IIOOIO 操作序列。 ) 解析：24. 有 5 个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈 ( 即 C第一个且 D 第二个出栈 ) 的次序有哪几个 ? （分数： 2.00 ）_ 正确答案： ( 正确答案： 3 个：C，D，E，B，A；C，D，B，E，A；C，D ，B，A，E。 提示：此题考查的知识点是栈的后进先出特点。按题意，C先出，说明A，B 已入栈， D出栈再出栈， E可以入栈就出栈，可以有序列

20、 C，D，E，B，A。也可以 B先出 E再入，再出，得序列C ，D，B，E，A。还可以 B，A 都出栈后， E再入栈出栈，得序列C，D，B，A ，E。只有这三种情况。) 解析：为了增加内存空间的利用率和减少溢出的可能性，通常采用两个栈利用同一块存储空间的方法。通常两个栈的栈底设在内存空间的两端，而栈顶相向，迎面增长。已知有两个栈s1、s2 都采用顺序栈方式，并且共享一个存储区 0 maxsize 1 。 设计共享存储空间的两个栈s1、s2 的入栈和出栈算法。要求：（分数：4.00 ）(1). 给出算法的基本设计思想。（分数：2.00 ）_ 正确答案： ( 正确答案：栈s1、s2 共享向量空间，

21、将两栈栈底设在向量两端。初始时，sl 栈顶指针为 -1 ，s2 栈顶为 maxsize 。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。) 解析：(2). 根据设计思想，采用C 或 C+或 Java 语言描述算法，关键之处给出注释；（分数：2.00 ）_ 正确答案： ( 正确答案：算法设计如下： #define maxsize 两栈共享顺序存储空间所能达到的最多元素数 #define elemtp int 假设元素类型为整型 typedef struct elemtp stackmaxsize；栈空间 int top2； top 为两个栈顶指针 stk； stk s； s

22、 是如上定义的结构类型变量，为全局变量 入栈操作： int push(int i，int x) 入栈操作。 i 为栈号， i=0 表示左边的栈sl ，i=1 表示右 边的栈s2， X是入栈元素。入栈成功返回1， 否则返回 0 if(i1)printf(栈号输入不对 ) ； exit(0)； if(S top1一 s top0=1)printf(”栈已满 n”)； return(0)； switch(i) case 0： S stack+s top E0=x；return 1；break ； case 1：Sstack 一 stop1=X；return 1； 退栈操作：elemtp pop(in

23、t i) if(i1)printf(”栈号输入错误 n”)；exit(0)； switch(i) case 0：if(S top0=-1)printf(”栈空 n”)；return一 1； else return sstackstop0-； case 1：if(S top1=maxsize)printf(”栈空 n”)；return-1； else return s stackstop1+； ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - -

24、- - - - 解析：25. 一个 nn的对称矩阵，如果以行或列为主序存入内存，则其容量为多少? （分数： 2.00 ）_ 正确答案： ( 正确答案： n(n+1) 2( 压缩存储 ) 或 n 2 ( 不采用压缩存储 ) 。) 解析：26. 设有一个 nn的上三角矩阵 (a ij ) ，将其上三角中的元素按先行后列的顺序存于数组Bm中，使得Bk=a ij且 k=f 1 (i)f 2 (j)+c，请推导出函数f 1、f 2和常数 c，要求 f 1和 f 2中不含常数项。（分数： 2.00 ）_ 正确答案： ( 正确答案：上三角矩阵第1 行有 n 个元素，第i 一 1 行有 n 一(i 一 1)+

25、1 个元素，第 1 行到第i 一 1 行是等腰梯形，而第i 行上第 j 个元素 ( 即 a ij ) 是第 i 行上第 j-i+1个元素，故元素a ij在一维数组中的存储位置 ( 下标 k) 为： k=(n+(n 一(i一 1)+1)(i一 1) 2+(j-i+1)=(2n-i+2)(i一 1)2+j-i+1 进一步整理为：) 解析：27. 已知有一整数序列a 1，a 2，a 3， a n 。栈 A中只保存整数，即序列中元素为整数时允许其入栈。设计一个算法实现如下功能；用栈结构存储入栈的整数，当a i一 1 时，将 a i进栈；当 a i =-1时，输出栈顶整数并出栈。（分数： 2.00 ）_

26、 正确答案： ( 正确答案： #define maxsize 栈空间容量void InOutS(int smaxsize) int top=0 ： top 为栈顶指针， 定义 top=0 时为栈空 for(i=1；i= 0&x= 0&xj)printf(”序列非法 n”)；exit(0)； i+； 不论 Ai是I或O ，指针i 均后移 if(j!=k)printf(”序列非法 n”)；return(false)； elseprintf(”序列合法 n”)；return(true)； ) 解析：30. 设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个

27、结点有两个域：ch 和 link ，其中 ch 域为字符类型。（分数： 2.00 ）_ 正确答案： ( 正确答案：表达式中的括号有以下三对：(、)、，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对；否则，结论表达式括号不配对。 int Match(LinkedList 1a) 算术表达式存储在以la 为头结点的单循环链表中，本算法判断括号是否正确配对 char s ； s 为字符栈，容量足够大p=la 一link ； p 为工作指针，指向待处理结点Stack Init(s)； 初始化栈s

28、 while(p!=la) 循环到头结点为止switch(p一ch) case(： push(s ，p 一ch) ；break ； case)： if(StackEmpty(s)StackGetTop(s)!= () pfintf(”括号不配对n”)； return(0)； else pop(S)； break ； case ：push(s ，p 一ch)；break ； case：if(StackEmpty(s)StackGetTop(s)!=) printf(”括号不配对 n”)； return(0)； else pop(s) ；break ； case：push(s ，P一ch) ；br

29、eak ： case：if(StackEmpty(s)StackGetTop(s)!= ) printf(”括号不配对 n”)；return(0)； else pop(s)； break ； P=p一link ；后移指针 while if(StackEmpty(S)printf(”括号配对 n”)；return(1)； elseprintf(”括号不配对 n”)；return(0)； ) 解析：31. 请利用两个栈s1 和 s2 来模拟一个队列。已知栈的三个运算定义如下： (1)push(st，x)：元素 x 入 st栈； (2)pop(st，x) ：st 栈顶元素出栈，赋给变量x； (3)s

30、empty(st)：判 st 栈是否为空。那么如何利用栈的运算来实现该队列的三个运算： (1)enqueue ：插入一个元素入队列； (2)dequeue：删除一个元素出队列 ; (3)queue_empty：判队列为空。(请写明算法的思想及必要的注释。) （分数： 2.00 ）_ 正确答案： ( 正确答案：栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈sl 和 s2 模拟一个队列时， s1 作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1 退栈并逐个压入栈 s2 中，s1 中最先入栈的元素，在s2 中处于栈顶。 s2 退栈，相当于队列的出队，实现了先进先出。显

31、然，只有栈 s2 为空且 s1 也为空，才算是队列空。 (1)int enqueue(stack sl，elemtp x) sl 是容量为 n 的栈，栈中元素类型是elemtp 。本算法将X入栈，若入栈成功返回1，否则返回0 if(topl=n&!sempty(s2) topl是栈 s1 的栈顶指针， 是全局变量printf( ”栈满” )； return(0)； sl 满 s2 非空，这时sl 不能再入栈 if(topl=n&sempty(s2) 若 s2 为空，先将sl 退栈，元素再压栈到 s2 while(!sempty(s1)pop(sl，x) ；push(s2 ，x) ； push(

32、sl ，x) ：return(1)； x 入栈，实现了队列元素的入队 (2)void dequeue(stack s2，s1) s2 是输出栈，本算法将s2 栈项元素退栈，实现队列元素的出队 if(!sempty(s2) 栈 s2 不空，则直接出队 pop(s2 ，x) ；printf(”出队元素为”， x) ； else 处理 s2 空栈 if(sempty(s1)printf(”队列空” )；exit(0)； 若输入栈也为空，则判定队空 else 先将栈 s1 倒入 s2 中，再作出队操作 while(!sempty(s1)pop(sl，X)；push(s2 ，x) ； pop(s2，x)

33、 ； s2 退栈相当于队列出队printf(”出队元素”，x) ： (3)int queue_empty() 本算法判用栈sI 和 s2 模拟的队列是否为空if(sempty(s1)&sempty(s2)return(1)；队列空 else return(0)； 队列不空 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 解析：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -