中国科学院计算技术研究所
试题名称：软件基础
一.        填空（每空1分）
1．        线性表可采用的存储结构有           和           二种。
2．        用于拓扑排序的图是           图。
3．        操作系统的特征是           和           。
4．        根据联接在文法符号上的属性之间的依赖关系，可把属性分为        
       和           两大类。
5．        进程间存在的制约关系可以归结为           和           两种。
6．        产生死锁的原因是           和           。
7．        对逻辑表达式的计算可采用           和           方式。
8．        有n个结点的完全二叉树的深度为           。
9．        在串的模式匹配中，若主串长为m，子串长为n，则KMP算法的时间复杂度为           。
10.        二叉树的遍历方式有           、           和           三种；图的遍历方式有           和           两种。

二.        简答
1．        （3分）什么是哈希（Hash）查找？
2．        （4分）UNIX系统中设备管理的主要特点是什么？
3．        （3分）树(A(B(E(K , L) , F) , (C(G) , D(H(M) , I , J)))所对应的二叉树表示是什么?
4．        （3分）已知初始关键字为[49，38，65，97，76，13，27，49]，现分别用直接插入排序和快速排序方法对之进行排序，请分别给出两种方法第二趟排序之后的结果。
5．        （4分）什么是地址重定位？动态重定位的结果是什么？
6．        （3分）什么是数据的逻辑结构和物理结构？
7．        （5分）程序运行的所需的一片连续存储——活动记录有哪些域？它们各有什么作用？
8．        （5分）有一C语言程序如下：
main（）
{
  int x；
  x = 25；
  printf（“%d\n”，x）；
}
经过编译联接后，由符号调试器跟踪其执行，却无法检查变量x的值，因为调试器报告“无此变量”。试解释其原因。

三.        问答题
1．        （8分）试比较Pascal程序（语法结构位置任意，空格等空白字符作为单词分隔符）和Fortran程序（语法结构位置固定，空格无意义）对词法分析的影响。

2．        （8分）下列文法是否为LR（1）文法？若是，给出分析表，若不是，是说明理由。
       S      AA
       A      aA | a

3．        （8分）设一消息缓冲区由如下信息组成：
    Sptr      指向发送进程的指针
    Nptr      指向下一个消息缓冲区的指针
    Size      消息长度
    Text      消息正文
请给出两个进程通过该类消息缓冲区进行通讯的过程。

4．        （8分）Swap指令是一条可在一个存储周期内完成交换两个字节的内容的操作的硬件指令。其功能用Pascal语言描述如下：
            procedure Swap（var a，b：integer）
              var temp：integer；
              begin
                temp：= a；
                a   ：= b：
                b   ：= temp；
              end
       请用该指令实现关锁原语Lock（w）和开锁原语Unlock（w）。

四.        算法设计
1．        （9分）二叉树的深度定义为由根结点到叶子结点的最长路径，设计一算法，计算二叉树的深度。


2．        （9分）写出堆排序（heap sort）的算法，指出其最坏情况下的时间复杂度。

中国科学院计算技术研究所
试题名称：软件基础答案
一.        填空
1．        顺序结构、链表结构
2．        有向无环图
3．        程序共行（并发）、资源共享（共享）
4．        综合属性、继承属性
5．        互斥、同步
6．        系统资源不足、进程推进顺序非法
7．        严格计算（直接计算）、短路计算
8．       
9．        O（m+n）
10.        先序、中序、后序、深度优先、广度优先

二.       
1．        由关键字直接计算记录存放位置的查找方法称为哈希查找。（3分）

2．        UNIX系统中设备管理的特点有：（4分）
(a)        块设备管理和字符设备管理具有相似的层次结构；
(b)        把字符设备作为特别文件处理；
(c)        采用了完善的缓冲技术；
(d)        引入了“预先读”、“异步写”和“延迟写”方式。

3．       
4．        直接插入排序第二趟的结果
       [38  49]  65  97  76  13  27  49
   快速排序第二趟的结果
       [13]  27  [38]  49  [49  65]  76  [97]

5．        由于一个作业装入到与其地址空间不一致的存储空间所引起的、有关地址部分的填整过程，称之为地址重定位。动态重定位的特点是：在程序执行时才进行重定位，它需要硬件的支持。

6．        逻辑结构指数据元素之间的逻辑关系；物理结构指数据结构在计算机存储中的映像。

7．        活动记录包含（答对4个即可得分）
(1)        临时工作单元：用于存放计算过程中所需的临时变量；
(2)        局部数据：用于存放对应当前活动记录的程序单元的局部数据；
(3)        保存机器态部分：用于保存当前的程序计数器、寄存器的值等等；
(4)        访问链：把当前执行的程序单元可访问的活动记录联结起来；
(5)        控制链：把所有活动记录按它们生成的次序联结起来；
(6)        实在参数
(7)        返回值

8．        该变量在编译时被优化掉了，所以无法检查其值。

三.        问答题：
1．       
(a)        Fortran的词法分析比Pascal的词法分析复杂；
(b)        Fortran语言将一行分为标号、续行、语句、注释四个区，出现在不同区域的符号具有不同的含义。词法分析器必须结合符号出现的位置才可判定其属性；而Pascal语言中的记号识别则与位置无关；
(c)        Fortran语言认为空格无意义，使得对某些符号的识别取决于后面的符号；而在Pascal语言中，每遇过一个空白字符，则认为一个记号已识别完毕。

2．        该文法不是LR（1）文法。因为其为二义文法。
            S       A1A2
可将任意输入串aa……a截取任意长度的前缀归约为A1，而将剩下的全部归约为A2。

3．       
        发送进程在发送消息之前，先在自己的内存空间设置一发送区，填入消息正文等信息，然后调用发送原语（Send）。进入发送程序后，先找到接受进程的PCB，再申请获得一消息缓冲区空间，然后互斥进入接受进程的消息队列，找到队尾，把消息缓冲区挂在队尾，把消息正文及长度等从发送区复制到消息缓冲区，最后通过V操作通知接收进程，并退出发送程序，发送进程继续执行。
        接收进程在读取消息之前，先在自己的内存空间设置一接收区，然后使用Read原语，在进入读取程序后，先通过P操作检查有无消息，然后互斥进入消息队列，移出队列中的第一个消息，并把消息从缓冲区复制到接收区，最后释放缓冲区，退出读取程序，接收进程继续执行。
4．       
        锁原语的原定义：
Lock（w）：
L：if w = 1 then  goto L  else  w ：=1
         Unlock（w）：
             w：=0
        用SWAP指令实现的锁原语：
Lock（w）：
   key：=1；
   repeat
     swap（w，key）
   until key=0；
Unlock（w）
   key：=0；
   swap（w，key）；

四.        算法设计
1．        设全局变量n存放当前树的最大深度，则程序为：
procedure visit（lev：integer；root：bitreptr）；
  begin
case
  root↑.left = nil and root↑.right =nil:
          if lev > n then n := lev;
          return;
  root↑.left = nil:
          call visit(lev+1;root↑.right);
  root↑.right = nil:
          call visit(lev+1;root↑.left);
  else
    call visit(lev+1;root↑.left);
    call visit(lev+1;root↑.right);
           end  /*case*/
         end

       begin    /*  main  */
         n := 0;
         call visit(0 , root);
         write(n);
       end  /*main*/

2．        堆排序的算法
(1)        数据结构定义
type rectype = record
              key : keytype
            end;
filetype = array [0..n] of rectype;

(2)        算法描述
procedure heapsort(var r : filetype);
  begin
for i := n div 2 downto 1 do   call sift(r , i , n);
for i :=n downto 2 do
  [ r[1]   r;  call sift(r , 1 , i-1);]
            end;  {heapsort}

          procedure sift(var r : filetype; l , m : integer);
            begin
              i := l; j := 2*i; x := r;
              while j≤m do
               [ if (j<m) and (r[j].key>r[j+1].key) then j:=j+1;
                 if x.key>r[j].key
                 then  [ r:=r[j]; i:=j; j:=2*i;]
                 else  j := m+1; ]
              r := x;
            end;  /*sift*/
(3)        最坏情况下的时间复杂度为O(nlogn)。

中国科学院计算技术研究所
试题名称：软件基础
一.        填空（1分×20）
1．        编译过程中，比较常见的中间语言有         、         、         和
             。
2．        产生死锁的主要原因是          和          ；预防死锁通常所采用   的方法有           和          。
3．        顺序存储结构实现的队列存在着           现象，因而采用环形的结   构来克服。
4．        图的遍历方式有           和          两种。
5．        在UNIX系统中，一个进程的进程控制块（PCB）是由           和
            两部分组成的，其中常驻内存的是          。
6．        快速排序在最坏情况下的时间复杂度为          。
7．        布尔表达式的计算可采用           或          方法。
8．        在UNIX系统中，一个目录项是由           和          组成的。
9．        共有n个叶子的二叉树，每个叶子的权值为Wi（1≦i≦n），其中带权路径长度最小的二叉树被称之为          。

二.        简答（5分×6）
1．        什么是地址重定位？动态地址重定位的特点是什么？

2．        给出下列自动机所描述的语言：
3．        构造一文法产生任意长的a，b串，使得|a|≦|b|≦2|a|。其中：“|a|”
表示a字符的个数；“|b|”表示b字符的个数。

4．        进程之间有哪些基本的通讯方式？它们分别有什么特点？

5．        已知下列AOE网络，请给出每个事件ai最早开始时间ei及最迟开始时间li。






6．        如果dag是二叉树的时候，可以为其生成最优目标代码。试标志下列二
   叉树，并给出执行该代码段所需的最小寄存器数。
三.        （10分）写一算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表。


四.        （15分）已知一个二叉树的前序及中序遍历结果，请写一算法，恢复该二叉树。


五.        （15分）某操作系统将消息缓冲通讯作为进程之间的基本通讯手段，SEND和RECEIVE分别为发送消息和接受消息原语。请设计一种方案，用SEND和RECEIVE原语来实现基于信号量的P，V操作。


六.        （10分）请按语法制导的定义，将后缀表达式翻译成中缀表达式。注意，不允许出现冗余括号，后缀表达式的文法如下：
          E          EE+
          E          EE*
          E          id

中国科学院计算技术研究所
试题名称：软件基础答案
一.        填空
1．        逆波兰表示、二元式、三元式、四元式。
2．        系统资源有限，进程推进次序非法；静态分配，有序分配。
3．        假溢出。
4．        深度优先，广度优先。
5．        proc结构和user结构，proc。
6．        O（  ）。
7．        严格计算，短路计算/优化计算。
8．        文件名，索引节点号。
9．        哈夫曼树/最优二叉树。

二.        简答
1．        重定位是指作业装入到与其地址空间不同的物理空间所引起的地址变换       过程；动态重定位的特点：①由硬件实现；②在程序运行过程中进行地       址变换。

2．       

3．        S        aSBS | BsaS | ε
       B        bb|b

4．        高级通讯方式（如消息传递）和低级通讯方式（互斥与同步）；高级通       讯一次传递大批数据，而低级通讯则一次交换少量信息。

5．            活动              ei                li
            a1                0                0
            a2                0                2
            a3                0                3
            a4                6                6
            a5                4                6
            a6                5                8
            a7                7                7
            a8                7                7
            a9                7                10
            a10               16               16
            a11               14               14


6．       
                                最少需要2个寄存器





三.        h:


        function reverse（h）
      begin
        p：=h；
        q：=p↑.next；p↑.next:=nil;
        if  (q↑.next==nil)  then
          begin
             q↑.next:=p;
             return(q);
          end
        r:=q↑.next;
        while (r↑.next≠nil ) do
           begin
             q↑.next:=p;
             p:=q;   q:=r;   r:=r↑.next
           end;
        q↑.next:=p;    r↑.next:=q;     return(r);
      end;




四．function restore(in)    /* in is a string */
      begin
        lth:=strlen(in);
        if (lth=0) return(nil)
        i:=i+1;
        if (lth=1) then
          begin
            new(p);
            p↑.data:=substr(in,1,1);
            p↑.left:=p↑.right:=nil;
          end
        else begin
              r:=substr(preorder,i,1);
              new(p);      p↑.data:=r;
              j:=index(in,r);
              p↑.left:=restore(substr(in,1,j-1));
              p↑.right:=restore(substr(in,j+1,lth-j));
            end
        return(p)
      end;
begin  /* main */
  i:=0;
  root:=restore(inorder);
end.

五．①所有信号量由一个叫同步进程的进程来管理，对应每个信号量设置一个
计数器（记录信号量的值）和一个等待进程链表。

②P、V操作通过调用p和v过程来实现。p和v过程将信号量S和操作
作为消息发给同步进程。然后做一个receive等待同步进程的回答。

③同步进程接收到消息后，看所要求的操作能否完成。P操作当S的值为
0时，同步进程把调用者推入队列；不发回消息，则调用者处于等待状态。
V操作总能完成，所以发回一空消息给调用者，将其解冻，同时检查S的
值是否为1和相应等待队列空否。若S=1且队列不空，则从队列中移出一
个进程，向他发送一空消息，将它解冻。

六．   S      E      {  print（E.code） }

       E      E1E2+  {  E.code:= E1.code‖’+’‖E2.code;
                        E.op=’+’;   }

       E      E1E2*  {  if E1.op=’+’ and E2.op=’+’
                        then E.code:= ‘(’‖E1.code‖‘)’‖‘*’‖‘(’‖
                                       E2.code‖‘)’;
                        else if E1.op=’+’
                            then E.code:= ‘(’‖E1.code‖‘)’‖‘*’‖E2.code;
                            else if E2.op=’+’
                                then E.code:= E1.code‖‘*’‖‘(’‖E2.code
                                           ‖‘)’;
                                else E.code:= E1.code‖‘*’‖E2.code;
                        E.op:=’*’;    }

       E      id      {  E.code:=id.lexeme;
                         E.code:=’$’;  }

中国科学院计算技术研究所
试题名称：软件基础
一.        （10分）已知序列17，31，13，11，20，35，25，8，4，11，24，40，27。请画出该序列的二叉排序树，并分别给出下列操作后的二叉树；
①插入数据9；            ②删除结点17；          ③再删除结点13。

二.        （15分）请编写一个程序，生成如下序列的前n项。
1，2，1，2，3，2，1，2，3，4，3，2，1，2，3，4，5，4，3，2，1, 2，……

三.        （15分）已知平面上（直角坐标系）的n个点，请编一个函数，求同一条直线所能通过的最多点数。

四.        （10分）下面的文法产生a的个数和b的个数相同的非空a，b串。
              S         aB | bA
              B         bS | aBB | b
              A         aS | bAA | a
     其中非终结符B推出b比a的个数多1个的串，A则反之。
(1)        说明该文法是二义的。
(2)        对上述文法略作修改，使之非二义，并产生同样的语言。略作修改的含义是：不增加非终结符。

五.        （10分）某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题。
      D               attrlist namelist | attrlist（D）
      namelist          id，namelist | id
      attrlist           A，attrlist | A
      A               decimal | fixed | float | real
D       attrlist（D）的含义是：在括号中的声明提到的所有名字有attrlist
中给出的属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字
的属性个数填入符号表。

六.        （10分）下面是一个C语言程序及其运行结果。从运行结果看函数func中四个局部变量i1，j1，f1，e1的地址间隔和它们类型的大小不一致，试分析不一致的原因。

#include <stdio.h>

func(i , j , f , e )
short i , j ;     float f1 , e1;
{
  short i1, j1;   float f1, e1;
  i1 = i;  j1 = j;  f1 = f;  e1 = e;

printf(“Addresses of i, j, f, e = %d, %d, %d, %d\n”, &i, &j, &f, &e);
printf(“Addresses of i1, j1, f1, e1 = %d, %d, %d, %d\n”, &i1, &j1, &f1, &e1);
printf(“Size of short, int, long, float, double = %d, %d, %d, %d, %d\n” ,
        sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double));
}

main()
{
  short  i, j;   float  f, e;
  i = j = 1;  f = e = 1.0;
  func(i , j , f , e);
}

运行结果:
Addresses of i, j, f, e = -268438178, -268438174, -268438172, -268438164;
Addresses of i1, j1, f1, e1 = -268438250, -268438252, -268438256, -268438260;
Size of short , int , long , float , double = 2, 4, 4, 4, 8

七.        （5分）在UNIX系统中，对换区的功能是什么？UNIX系统V是如何对对换区进行管理的？

八.        （5分）UNIX系统V为进程之间的通信提供了哪些工具？各用于什么场合？

九.        （5分）操作系统中的文件共享有几种形式？它们是如何实现的？各有什么特点？

十.        （5分）Dijkstra（1965）提出的银行家算法的主要思想是什么？它能够用来解决实际中的死锁问题吗？为什么？

十一.        （10分）有五个批处理的作业（A，B，C，D，E）几乎同时到达一个计算中心，估计的运行时间分别为2，4，6，8，10分钟，它们的优先数分别为1，2，3，4，5（1为最低优先级）。对下面的每种调度算法，分别计算作业的平均周转时间。
①最高优先级优先；
②时间片轮转（时间片为2分钟）；
③FIFO（作业到达的顺序为C，D，B，E，A）；
④短作业优先。

中国科学院计算技术研究所
试题名称：软件基础答案
一.       

二.        Program SEQUENCE(input , output);
  var i , k , l , m , n : integer ;

BEGIN
   read(n);
   i := 1;
   write(i);
   IF n <> 1 THEN
   BEGIN
      k := 2;
      m :=1;
      FOR l=1 to n-1 DO
      BEGIN
         i := i + m;
         IF i=1 THEN
         BEGIN
            k := k + 1;
            m := -m;
         END
         IF i=k THEN
           m := -m;
         write(i);
      END
   END
END.

三.        算法要点：从n个点中任选两条构成一条直线，用“两点式”写出该直线方程。将其余的点代入方程，记录满足此方程的点数。这样的直线共有n（n-1）/2条，从中选出最多点数。

过程中的x和y分别表示第i个点的横坐标和纵坐标。
（假定前面有类型说明：type T = array [1..100] of real；）
function maxpoint（var x，y：T；n：integer）：integer；
  var i，j，k，m，mmax：integer；
  begin
mmax：=0；
for i：=1 to n-1 do
  for j：=i+1 to n do
  begin
    m：=2；
    for k：=j+1 to n do
      if (x-x[j])*(y[j]-y[k]) = (x[j]-x[k])*(y-y[j])
      then m := m + 1;
    if m>mmax then mmax := m
  end;
maxpoint := mmax;
      end.

四.       
1．        句子aabbab有两种不同的推导：
S  aB  aaBB  aabB  aabbS  aabbaB  aabbab；
S  aB  aaBB  aabSB  aabbAB  aabbaB  aabbab；

2．        S       aBS | bAS | aB | bA
B       aBB | b
A       bAA | a

五.        D’       { D.num = 0} D
D        attrlist { namelist.num = D.num + attrlist.num}
         namelist
D        attrlist { D1.num = D.num + attrlist.num}
          ( D1 )
namelist       id { addattr(id.entry , namelist.num) }
namelist       id , { namelist1.num = namelist.num }
              namelist1 { addattr(id.entry , namelist.num) }
attrlist         A attrlist1 { attrlist.num = attrlist1.num + 1}
attrlist         A { attrlist.num = 1}

六.        C编译是不作调用时的形参和实参一致性检查的。由于整数有short、int和long三种类型，实数有float和double两种类型，C的调用是传值的。一个整形表达式的值究竟应按short、int还是long方式传递呢。显然，这儿约定为取size最大的方式，即long方式；实数用double方式。虽然按最大size方式传递，被调用函数中形式参数（局部量）是按自己类型size取值（但要考虑边界对齐）。short型的形参是取long值4字节中的后两字节内容，float型的形参是取double值字节的前4字节。这样才出现这四个形参地址的上面结果。




七.       
(1)        “扩充”内存的一种手段。将内存中处于睡眠状态的进程暂时换到磁盘对换区，将内存区让位于就绪的进程；
(2)        管理采用的数据结构为“对换映射表”：
maddr —— 可用盘区始址；
misize —— 该区的可用盘块数。
(3)        采用分区分配和首次适应分配算法。释放时要进行相邻区的合并。

八.        UNIX系统V提供的工具有：
(1)        Sleep/Wakeup：核心态进程的同步；
(2)        软中断信号机制（signal/kill）：同一用户进程间的通讯（小数据量）；
(3)        基于文件系统的pipe机制：进程间大数据量的通讯；
(4)        共享存储器、信号量集和消息传递机制。

九.       
(1)        采用全路径名访问他人文件。共享时间短；
(2)        采用目录表项之间的链接。即使一个用户目录中的表项直接指向另一个目录中的表项。长久共享。
(3)        采用基本文件目录和符号文件目录的组织方式，便于用户文件的共享。

十.       
(1)        它代表解决死锁问题的一种策略。在实施资源分配之前，先计算该次分配后所产生的状态是否安全，即是否存在一种顺序，使所有进程都能执行结束。若安全，则分配；否则，拒绝分配；
(2)        该算法虽有很好的理论意义，但在实际系统中却很难使用。因为算法所假设的条件，如：进程可知申请资源的最大数目、系统中进程数目固定等，在实现环境中并不成立，所以由不成立的前提导出的结果很难说明正确的。

十一.        平均周转时间            
①        T = 22；
②        T = 19.2；
③        T = 19.2；
④        T = 14。

中科院计算机技术研究所
数据结构与程序设计

一、选择题 (20 分 每空2分)
1.___ 的遍历仍需要栈的支持。
1.前序线索树 2.中序线索树 3.后序线索树
2.若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为___。
1.n-1 2.[n/m]-1 3.[(n-1)/(m-1)] 4.[n/(m-1)]-1 5.[(n+1)/(m+1)]-1
3.最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度∑wh最小的树,其中对最优二叉树,n表示___,对最优查找树,n表示___; 构造这两种树均___。
1.结点数 2.叶结点数 3.非叶结点数 4.度为二的结点数 5.需要一张n各关键字的有序表 6.需要对n个关键字进行动态插入 7.需要n个关键字的查找概率表 8.不许要任何前提
4.对于前序遍历与中序遍历结果相同的二叉树为___; 对于前序遍历与后序遍历结果相同的二叉树为___。
1.一般二叉树 2.只有根结点的二叉树 3.根结点无左孩子的二叉树 4.根接点无右孩子的二叉树 5.所有结点只有左子树的二叉树 6所有结点只有右子树的二叉树
5.m路B+树是一棵___, 其结点中关键字最多为___个, 最少为___个。
1.m路平衡查找树 2.m路平衡索引树 3.m路trie树 4.m路键树 5.m-1 6.m 7 m+1 8.[m/2]-1 9.[m/2] 10.[m/2]+1
二、填空题(10 分,每空一分)
1.对于给定的n个元素,可以构造出的逻辑结构有___,___,___,___四种。
2.具有n个关键字的B-树的查找路径长度不会大于___。
3.克鲁斯卡尔算法的时间复杂度为___, 他对___图较为适合。
4.深度为k(设根的层数为1)的完全二叉树至少有___个结点, 至多有___个结点, k和结点数n之间的关系是___。
三、问答题(10 分,每题5分)
1.一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1.但一个恰有一个顶点的入度为0， 其他顶点入度为一的有向图却不一定是一棵有向树。请举例说明之。
2.若有n个元素以构成一个小根堆，那么如果增加一个元素为K(n+1)，请用文字简要 说明你如何在log2(n) 的时间内将其重新调整为一个堆？
四、阅读下述程序,指出程序的输出。(10 分)
void g(int**);
main(){
  int line[100],i;
  int *p=line;
  for(i=0;i<100;i++){
    *p=i;
    g(&p);
  }
  for(i=0;i<100;I++)printf("%d\n",line);
}
void g(int**p){
  (**p)++;
  (*p)++;
}
五、编程题。(共50分,要求写出设计思想和程序注解)
1.设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法, 将此链表的记录按照key递增的次序进行就地排序.(10分)
2.给定一个整数数组b[0..N-1], b中连续相等元素构成的子序列称为平台.试设计算法,求出b中最长平台的长度.(20分)
3.自由树(即无环连通图) T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的直径定义为MAX d(u,v) 这里d(u,v)表示顶点u 到顶点v的最短路径长度(路径长度为路径中所含的边数).试写一算法求T的直径,并分析算法的时间复杂度(时间复杂度越小得分越高)

谢谢楼主提供~！
:am