DS(50分）
一。（15分）
   回答下列各题，并简要说明理由，每题3分
1。 什么是线形表？线形表的各元素类型是否必须是同一类型？为什么？
2。线形表有两种不同的继承形式，顺序的和链接的存储结构，
    在使用时，如何确定使用哪种存储结构？
3。给出一个二叉树的前序和中序遍历序列，要求写出后序遍历序列。
4。（记不清楚具体数字了，大概的数字把）
    一个文件用B+树做索引，给定文件大小2000000 B，每个页块大小为4000 B,
    每个指针大小为5 B。每个记录是200 B,其中关键码为5 B.
    问：
       1）应采用多少阶B+树?
       2)该文件索引块数目。
5。下列哪些可以做Hash函数？哪些效果不好？哪些效果好？
    其中，n为Hash表的表长；Random(n)可以产生一个0---n=1 的随机数；
    p(n)为小于n的最大素数。
       1）Hash(key) = key/n;
       2) Hash(key) = 1;
       3) Hash(key) = (key + Random(n)) % n;
       4) Hash(key) = key % p(n);
二。（5分）
    证明：一棵二叉树的前序，中序，后序遍历序列中，叶结点的相对位置是不变的
三。（15分）
    1） 给定一组关键码，要求依次插入建立一棵AVL树，大约12个关键码左右，
       （和03年那个真题只是关键码的不同）
        需要旋转的时候，要求标出旋转的类型：左单旋，右单旋，先左后右双旋，先右后
左双旋。
    2）在建成的这棵AVL树上，依次删除关键码****（四个），要求：
           如果需要旋转，那要标出旋转类型；用中序的直接前驱代替关键码
四。（15分）
    1）将书上284页的Dijkstra算法挖去5个空，让添。（5分）
       具体字母有差别，但是确实就是那个算法，我按照书上的来了。
         void ShortestPath(Graph<T> G, int v, int n)
         {
              for (int i = 0; i < n; i++){  //n为图的顶点数目
                   dist[i] = Edge[v][i];
                   s[i] = 0;
                   if (i != v && dist[i] < MaxNum)
                        1空;
                   else
                        path[i] = -1;
              }
              s[v] = 1;
              dist[v] = 0;
              for (int i = 0; i < n - 1; i++){
                   float min = MaxNum;
                   int u = v;
                   for (int j = 0; j < n; j++){
                        if( 2空 && dist[j] < min){
                              u = j;
                              min = dist[j];
                        }
                        }
                    }
               3空；
               for (int w = 0; w < n; w++){
                   if( 4空 && Edge[u][w] < MaxNum && dist[u] + Edge[u][w] < dist
[w]){
                        dist[w] = dist[u] + Edge[u][w];
                        5空；
                   }
               }
           }
     2）（10分）
         定义了一个Max{***********}，即顶点i到其余各顶点的最短路径的最大值，
         让写一个算法求 这个Max{***********}的最小值。

　　13. WiKi　 14.《四十二行圣经》

　　二、简答（选作两道，25*2，共50分）

　　1.美国联邦通讯委员会（FCC）对电子媒介管制时所遵循的基本原则？

　　2.传播业的主要经济特征？

　　3. BT（BitTorrent）和电驴（Emule）下载的相同和不同？

　　三、论述题（40分）

　　创新之本