数据

1. 试分析下列各算法的时间复杂度。(5分)

（1）s=0;

     for i=0; i<n; i++)

for(j=0; j<n; j++)

         { scanf(“%d”,&a[i][j]);

           s+= a[i][j];

 

}                  （2分）

（2）i=1;

     while(i<=n)

        i=i*2;                （3分）

 

答案:（1）O(n2)           

  （2）O(log2n)

2．对于一个栈，设输入序列为A ,B ,C ,D ,E，F，为了得到出栈序列： C, B，E,D,A，F,需执行什么样的进栈（push）、出栈（pop）运算序列？(5分)

 

答案:push, push, push,pop,pop,push,push,pop,pop,pop,push,pop

答案

题目

先序序列: A B D F C E G H ，中序序列： B F D A G E H C;后序序列:F D B G H E C A

题目

5.假设用于通信的电文仅由8个字母(A，B，C，D，E，F，G，H)组成，字母在电文中出现的频率分别为7， 19， 2， 6， 32， 3， 21，10。

(1)试为这8个字母设计赫夫曼树;(3分)

(2) 试为这8个字母设计赫夫曼编码。(2分)

1

2

6.已知图所示的有向图，请给出

(1)邻接矩阵；（2分）

(2)邻接表。（3分）

1

2

7. 已知图的邻接表如图所示，

（1）试从顶点v0出发，写出按广度优先遍历的结果；（3分）

（2）试从顶点v0出发，写出按深度优先遍历的结果是。（2分）

答案：（1）0 1 2 3或v0，v1，v2，v3；

（2）0 1 2 3或v0，v1，v2，v3；

8对下图所示的无向图，请给出：

（1）最小生成树（3分）

（2）按普里姆（Prim）算法，请写出加入顶点的顺序（2分）

答案：（1）

(2)加入顶点的顺序: 0,5,4, 3,2, 1

9. 设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试写出采用直接插入排序方法，每趟排序结束后关键字序列的状态。(5分)

答案：直接插入排序

[2    12]   16   30   28   10   16*   20   6    18        

[2    12    16]  30   28   10   16*   20   6    18        

[2    12    16   30]  28   10   16*   20   6    18        

[2    12    16   28   30]   10   16*   20   6    18        

[2    10    12   16   28   30]   16*   20   6    18        

[2    10    12   16   16*   28   30]   20   6    18        

[2    10    12   16   16*   20   28   30]   6    18        

[2    6     10   12   16   16*   20   28   30]   18        

[2    6     10   12   16   16*    18   20   28   30]

 

10.折半查找有序表（4，6，10，12，20，30，50，70，88，100，120）。若查找表中元素50，则算法将依次与表中哪些元素比较大小才以成功结束？(5分)

答案：（30，88，50）