1、计算机专业基础综合历年真题试卷汇编 1 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是_。x=2；while(xn2)x=2*x；（A）O(log 2n)（B） O(n)（C） O(nlog2n)（D）O(n 2)2 知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是_。（A）O(n)（B） O(mn)（C） O(min(m，n)（D）O(max(m，n)3 求整数 n(n0) 阶乘的
2、算法如下，其时间复杂度是_。int fact(int n)if(n=1)return 1；return n*fact(n-1)，（A）O(log 2n)（B） O(n)（C） O(nlog2n)（D）O(n 2)4 下列程序段的时间复杂度是_。count=0；for(k=1，k=n ；k*=2)for(j=1，j=n，j+)count+；（A）O(log 2n)（B） O(n)（C） O(nlog2n)（D）O(n 2)5 若元素 a， b，c ，d，e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是_。（A）dcebfa（B） cbdaef（
3、C） bcaefd（D）afedcb6 元素 a，b， c，d，e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是_。（A）3（B） 4（C） 5（D）67 一个栈的入栈序列为 1，2，3，n，其出栈序列是 P1，p 2，p 3，P n。若p2=3，则 p3 可能取值的个数是_。（A）n-3（B） n-2（C） n-1（D）无法确定8 循环队列放在一维数组 A0M-1中，end1 指向队头元素，end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1个元素。初始时为空。下列判
4、断队空和队满的条件中，正确的是_。（A）队空：end1=end2；队满：end1=(end2+1)mod M（B）队空：end1=end2；队满：end2=(end1+1)mod (M-1)（C）队空：end2=(end1+1)mod M；队满：end1=(end2+1)rood M（D）队空：end1=(end2+1)mod M；队满：end2=(end1+1)mod (M-1)9 已知循环队列存储在一维数组 A0n-1中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第 1 个进入队列的元素存储在A0处，则初始时 front 和 rear 的值
5、分别是_。（A）0，0（B） 0，n-1（C） n-1，0（D）n-1 ，n-110 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e 依次入此队列后再进行出队操作，则不可能得到的出队序列是_。（A）bacde（B） dbace（C） dbcae（D）ecbad11 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是_。（A）栈（B）队列（C）树（D）图12 设栈 S 和队列 Q 的初始状态均为空，元素 a， b，c ，d，e，f，g 依次进
6、入栈S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是b，d，c，f，e ，a，g，则栈 S 的容量至少是_。（A）1（B） 2（C） 3（D）413 已知操作符包括+、 -、(和)。将中缀表达式 a+b-a*(c+d)e-f)+g转换为等价的后缀表达式 ab+acd+ef-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是_。（A）5（B） 7（C） 8（D）1114 已知程序如下：Int S(int n)return (n=0)20：s(n-1)+n ；Void main()ciout S(1)；程序运行时使用
7、栈来保存调用过程的信息，自栈底到栈项保存的信息依次对应的是_。（A）main()S(1)S(0)（B） S(0)S(1)main()（C） main()S(0)S(1)（D）S(1)S(0)main()二、综合应用题41-47 小题，共 70 分。14 设将 n(n1) 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移 p(0pn)个位置，即将 R 中的数据由(X 0，X 1，X n-1)变换为 (Xp，X p+1，X n-1，X 0，X 1，X p-1)。 要求：15 给出算法的基本设计思想。16 根据设计思想，采用 C 或 C+或
8、Java 语言描述算法，关键之处给出注释。17 说明你所设计算法的时间复杂度和空间复杂度。17 已知一个整数序列 A=(a0，a 1，a n+1)，其中 0ain(0i n)。若存在ap1=ap2=apm=x 且 mn2(0p kn，1km)，则称 x 为 A 的主元素。例如A=(0，5，5，3，5，7，5，5)，则 5 为主元素；又如A=(0，5，5，3，5，1，5，7)，则 A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法 j 找出 A 的主元素。若存在主元素，则输出该元素；否则输出-1。 要求：18 给出算法的基本设计思想。19 根据设计思想，
9、采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。20 说明你所设计算法的时间复杂度和空间复杂度。20 已知一个带有表头结点的单链表，结点结构为： 假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点(k 为正整数)。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。要求：21 描述算法的基本设计思想。22 描述算法的详细实现步骤。23 根据设计思想和实现步骤，采用程序设计语言描述算法(使用 C、C+或 Java 语言实现)，关键之处请给出简要注释。23 假定采用带头结点的单链表保存
10、单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 ，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置(如图中字符i 所在结点的位置 p)。要求：24 给出算法的基本设计思想。25 根据设计思想，采用 C 或 C+或 JAVA 语言描述算法，关键之处给出注释。26 说明你所设计算法的时间复杂度。26 用单链表保存 m 个整数，结点的结构为：datalink，且data n(n 为正整数)。现要求设
11、计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下： 则删除结点后的 head 为： 要求：27 给出算法的基本设计思想。28 使用 C 或 C+语言，给出单链表结点的数据类型定义。29 根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。30 说明你所设计算法的时间复杂度和空间复杂度。计算机专业基础综合历年真题试卷汇编 1 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 A
12、【试题解析】 在程序中，执行频率最高的语句为“x=2*x”。设该语句共执行了 T(n)次，则 2T(n)+1n 2，故 T(n)=log2(n2)-1=log 2n-2，得 T(n)=O(log2n)。【知识模块】 数据结构2 【正确答案】 D【试题解析】 两个升序链表合并，两两比较表中元素，每比较一次确定一个元素的链接位置(取较小元素，头插法)。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，直到两个链表都到表尾，即每个元素都经过比较，时间复杂度为 O(m+n)=0(max(m，n) 。【知识模块】 数据结构3 【正确答案】 B【试题解析】 本
13、算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是 n1，每调用一次 fact()，传入该层 fact()的参数值减 1。采用递归式来表示时间复杂度有 则 T(n)=T(n-1)+1=T(n-2)+2=T(1)+n-1=O(n)，故时间复杂度为 O(n)。【知识模块】 数据结构4 【正确答案】 C【试题解析】 内层循环条件 j=n 与外层循环的变量无关，每次循环 j 自增 1，每次内层循环都执行 n 次。 外层循环条件为 k=n，增量定义为 k*=2，可知循环次数为 2k=n ，即 k=log2n。所以内层循环的时间复杂度是 O(n)，外层循环的时间复杂度是 O(log2n)。
14、对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度 T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)，选 C。【知识模块】 数据结构5 【正确答案】 D【试题解析】 选项 A 可由in、in、in、in 、out 、out 、in 、out、out、in、out、out 得到；选项 B 可由in、in、in、out、out、in、out 、out、in、out、in、out 得到；选项 C 可由in、in、out 、 in、out、out、in 、in、out、in、out、out 得到：选项 D 可由in、out、in、 in、in、in 、 in、out、
15、out、out、out 、out得到，但题意要求不允许连续三次退栈操作，故 D 不可能得到。【知识模块】 数据结构6 【正确答案】 B【试题解析】 d 为第 1 个出栈元素，则 d 之前的元素必定是进栈后在栈中停留。因而出栈顺序必为 dcba， e 的顺序不定，在任一“_”上都有可能，一共有 4 种可能。【知识模块】 数据结构7 【正确答案】 C【试题解析】 显然，3 之后的 4，5，n 都是 P3 可取的数(一直进栈直到该数入栈后马上出栈)。接下来分析 1 和 2：P 1 只能是 3 之前入栈的数(可能是 1 或 2)，当P1=1 时，P3 可取 2；当 P1=2 时，P 3 可取 1，故
16、P3 可能取除 3 之外的所有数，个数为 n-1。【知识模块】 数据结构8 【正确答案】 A【试题解析】 end1 指向队头元素，那么可知出队的操作是先从 Aend1读数，然后 end1 再加 1。end2 指向队尾元素的后一个位置，那么可知入队操作是先存数到Aend2，然后 end2 再加 1。若把 A0储存第一个元素，当队列初始时，入队操作是先把数据放到 A0，然后 end2 自增，即可知 end2 初值为 0；而 end1 指向的是队头元素，队头元素的在数组 A 中的下标为 0，所以得知 end1 初值也为 0，可知队空条件为 end1=end2；然后考虑队列满时，因为队列最多能容纳 M
17、-1 个元素，假设队列存储在下标为 0 到下标为 M-2 的 M-1 个区域，队头为 A0，队尾为AM-2，此时队列满，考虑在这种情况下 end1 和 end2 的状态，end1 指向队头元素，可知 end1=1，end2 指向队尾元素的后一个位置，可知 end2=M-2+1=M-1，所以可知队满的条件为 end1=(end2+1)mod M，选 A。【知识模块】 数据结构9 【正确答案】 B【试题解析】 根据题意，第一个元素进入队列后存储在 A0处，此时 front 和rear 值都为 0。入队时由于要执行(rear+1)n 操作，所以如果入队后指针指向 0，则 rear 初值为 n-1，而
18、由于第一个元素在 A0中，插入操作只改变 rear 指针，所以 front 为 0 不变。注意：循环队列是指顺序存储的队列，而不是指逻辑上的循环，如循环单链表表示的队列不能称为循环队列。front 和 rear”的初值并不是固定的。【知识模块】 数据结构10 【正确答案】 C【试题解析】 本题的队列实际上是一个输出受限的双端队列。A 操作：a 左入(或右入)、 b 左入、c 右入、d 右入、e 右入。B 操作：a 左入(或右入)、b 左入、c 右入、d 左入、 e 右入。D 操作：a 左入(或右入)、b 左入、c 左入、d 右入、e 左入。C 操作：a 左入(或右入) 、 b 右入、因 d 未
19、出，此时只能进队， c 怎么进都不可能在b 和 a 之间。【知识模块】 数据结构11 【正确答案】 B【试题解析】 缓冲区的概念出现在操作系统的设备管理中，其特点是先进先出。缓冲区的作用是解决主机与打印机之间速度不匹配的问题，而不应改变打印数据的顺序。若用栈，先进入缓冲区的数据则要排队到最后才能打印，显然不符题意，故选 B。【知识模块】 数据结构12 【正确答案】 C【试题解析】 由于队列的特点是先进先出，即栈 S 的出栈顺序就是队 Q 的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。栈内的最大深度为 3，故栈 S 的容量至少是 3。【知识模块】 数据结构13 【正确答案
20、】 A【试题解析】 表达式求值是栈的典型应用。中缀表达式不仅依赖于运算符的优先级，还要处理括号。后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从中缀表达式转换到后缀表达式需要用运算符进行处理，使其包含运算符优先级的信息，从而转换为后缀表达式的形式。转换过程如下表：可知，栈中的操作符的最大个数为 5。【知识模块】 数据结构14 【正确答案】 A【试题解析】 递归调用函数时，在系统栈里保存的函数信息需满足先进后出的特点，依次调用了 main()、S(1)、S(0)，故栈底到栈顶的信息依次是。main()、S(1)、S(0)。【知识模块】 数据结构二、综合应用题41
21、-47 小题，共 70 分。【知识模块】 数据结构15 【正确答案】 算法的基本设计思想： 可以将这个问题看作是把数组 ab 转换成数组 ba(a 代表数组的前 p 个元素，b 代表数组中余下的 n-p 个元素)，先将 a 逆置得到 a-1b，再将 b 逆置得到 a-1b-1，最后将整个 a-1b-1 逆置得到(a -1b-1)=ba。 设Revere 函数执行将数组元素逆置的操作，对 abcdefgh 向左循环移动 3(p=3)个位置的过程如下： Reverse(0 ， p-1)得到 cbadefgh： Reverse(p，n-1)得到 cbahgfed； Reverse(0，n-1)得到
22、defghabc。 注：Reverse 中，两个参数分别表示数组中待转换元素的始末位置。【知识模块】 数据结构16 【正确答案】 使用 C 语言描述算法如下：Void Reverse(int R，int from，int to)int i，temp ；for(i=0，i(to-from+1)2，i+)temp=Rfrom+i；Rfrom+i=Rto-i；Rto-i=temp；Reversevoid Converse(int R，int n，int p)Reverse(R，0 ，P-1)；Reverse(R，P，n-1) ；Reverse(R，0 ，n-1)；【知识模块】 数据结构17 【正确答
23、案】 上述算法中 3 个 Reverse 函数的时间复杂度分别为 O(p2)、O(n-p)2) 和 O(n2)，故所设计的算法的时间复杂度为 O(n)，空间复杂度为 O(1)。【试题解析】 考查顺序结构线性表的元素的移动操作，将数组中的序列循环左移。【知识模块】 数据结构【知识模块】 数据结构18 【正确答案】 给出算法的基本设计思想：算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素 Num。然后重新计数，确认 Num 是否是主元素。算法可分为以下两步：选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num 保存到 c 中，记录 Num 的出现次数为 1；若遇
24、到的下一个整数仍等于 Num，则计数加 1，否则计数减 1；当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复匕述过程，直到扫描完全部数组元素。判断 c 中元素是否是真正的主元素：再次扫描该数组，统计 c 中元素出现的次数，若大于 n2，则为主元素；否则，序列中不存在主元素。【知识模块】 数据结构19 【正确答案】 算法实现：int Majority(int A，int n)int i，c ，count=1；c 用来保存候选主元素，count 用来计数c=A0；设置 A0为候选主元素for(i=1；in ；i+)查找候选主元素if(Ai
25、=c)count+；对 A 中的候选主元素计数elseif(count0) 处理不是候选主元素的情况count-；else更换候选主元素，重新计数C=Ai；count=1；if(count0)for(i=count=0；in；i+)统计候选主元素的实际出现次数if(Ai=c)count+；if(countn2)return c ；确认候选主元素else return -1；不存在主元素【知识模块】 数据结构20 【正确答案】 说明算法复杂性：程序的时间复杂度为 O(n)，空间复杂度为 O(1)。【知识模块】 数据结构【知识模块】 数据结构21 【正确答案】 算法的基本设计思想：问题的关键是设计
26、一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第 k 个结点的位置。算法的基本设计思想：定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点(链表的第一个结点)。p 指针沿链表移动，当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。【知识模块】 数据结构22 【正确答案】 算法的详细实现步骤：count=0，p 和 q 指向链表表头结点的下一个结点；若 p 为空，转 ；若 count 等于 k，则 q 指向下一个结点；否则，count=count+1；p 指向
27、下一个结点，转 ；若 count 等于 k，则查找成功，输出该结点的 data 域的值，返回 1；否则，说明k 值超过了线性表的长度，查找失败，返回 0；算法结束。【知识模块】 数据结构23 【正确答案】 算法实现：typedef int ElemType；链表数据的类型定义typedef struct LNode链表结点的结构定义ElemType data；结点数据struct Lnode *link；结点链接指针 *LinkList；int Search_k(LinkList list，int k)查找链表 list 倒数第 k 个结点，并输出该结点 data 域的值LinkList p=
28、list-link，q=list-link；指针 p、 q 指示第一个结点int count=0，while(p!=NULL)遍历链表直到最后一个结点if(countk) count+；计数，若 countk 只移动 pelse q=q-link；p=p-link ；之后让 p、q 同步移动whileif(countk)return 0，查找失败返回 0else否则打印并返回 1printf(“d“，q- data)；return 1，Search k【试题解析】 考查链表的查找操作，查找链表中倒数第 k 个结点。【知识模块】 数据结构【知识模块】 数据结构24 【正确答案】 顺序遍历两个链表
29、到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。算法的基本设计思想：分别求出 str1 和 str2 所指的两个链表的长度 m 和 n；将两个链表以表尾对齐(如上图所示)：令指针 p、q 分别指向 str1 和 str2 的头结点，若 m=n，则使 p 指向链表中的第 m-n+1 个结点；若 mn，则使 q 指向链表中的第 n-m+1 个结点，即
30、使指针 p和 q 所指的结点到表尾的长度相等。反复将指针 p 和 q 同步向后移动，并判断它们是否指向同一结点。若 p 和 q 指向同一结点，则该点即为所求的共同后缀的起始位置。【知识模块】 数据结构25 【正确答案】 算法的 C 语言代码描述：LinkNode *Find_lst_Common(LinkList str1，LinkList str2)int len1=Length(str1)，len2=Length(str2)，LinkNode *p，*q，for(p*str1；len1 len2；len1-)使 p 指向的链表与 q 指向的链表等长p=p-next，for(q=str2，l
31、en1fen2；len2-)使 q 指向的链表与 p 指向的链表等长q=q-next；while (p-next!=NuLL p-next!=q-next)查找共同后缀起始点p=p-next；两个指针同步向后移动q=q-nextreturn p-next；返回共同后缀的起始点【知识模块】 数据结构26 【正确答案】 程序时间复杂度为：O(len1+len2)或 O(max(len1，len2)，其中len1、len2 分别为两个链表的长度。【试题解析】 考查链表的遍历、求表长操作。【知识模块】 数据结构【知识模块】 数据结构27 【正确答案】 算法的基本设计思想算法的核心思想是用空间换时间。使
32、用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。因为datan，故辅助数组 q 的大小为 n+1，各元素的初值均为 0。依次扫描链表中的各结点，同时检查 qdata的值，如果为 0，则保留该结点，并令qdata =1；否则，将该结点从链表中删除。【知识模块】 数据结构28 【正确答案】 使用 C 语言描述的单链表结点的数据类型定义typedef struct nodeint data；struct node *link；NODE；Typedef NODE *PNODE。【知识模块】 数据结构29 【正确答案】 算法实现void func(PNODE h，int n)PNODE p
33、=h，r；int *q，m；q=(int*)malloc(sizeof(int)*(n+1)；申请 n+1 个位置的辅助空间for(int i=0；in+1；i+)数组元素初值置 0*(q+i)=0；while(p-link!=NULL)m=p- link-data0？p-link-data ：-p-link-data ；if(*(q+m)=0)判断该结点的 data 是否已出现过*(q+m)=1；首次出现p=p-link；保留else重复出现r=p-link；删除p-link=r- linkfree(r)，free(q)；【知识模块】 数据结构30 【正确答案】 算法的时间复杂度为 O(m)，空间复杂度为 O(n)。【试题解析】 考查单链表的删除操作等。【知识模块】 数据结构
