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