武汉理工大学2002年研究生入学考试试题

一．选择题（30分，每空2分。答案可能不唯一）

1．算法在发生非法操作时可以作出处理的特性称为        。

① 正确性    ② 可读性   ③ 键状性    ④  可靠性

    2．指针p所指的元素是双向链表L的尾元素的条件是   A  。若队列采用链式存储，则该链式队列   B  。

A：① P==L   ② P==NULL     ③ P->Llink==L   ④ p->Rlink==L

B：① 存在队满的情况            ② 不存在队空的情况

   ③ 入队之前必须判断队满否    ④ 出队之前必须判断队空否

3．二叉排序树是：        。

① 中序遍历得到一升序序列的二叉树

② 每一分支结点的度均为2的二叉树

③ 按层次从左到右顺序编号的二叉树

  ④ 每一分支结点的值均小于其右子树上所有结点的值（若右子树存在），又大于其左子树上所有结点的值（若左子树存在）

4．三对角矩阵a[1..n][1..n]以行为主序顺序存储，其存储始址是b，每个元素占一个存储单元，则元素a[I][j]有存储始址为       。

① b+2*j+i-2  ② b+2*i+j-2     ③ b+2*j+i-3  ④ b+2*i+j-3

    5．已知一棵二叉树的前序序列和中序序列分别是GFDBHCEA和DFHBGCAE，则该二叉树的后序序列为   A  ，层次序列为  B   ，若由森林转化得到的二叉树是非空的二叉树，则该二叉树是  C   ，如果满足条件   D  ，线索二叉树中结点p无右孩子。

A、B：① DBHFEACG  ② GFCDBEHA  ③ DHBFAECG  ④ DFGBCEHA

C：    ① 根结点无右子树  ② 根结点可能有左子树和右子树

     ③ 根结点无左子树  ④ 各结点只有一个孩子

D：① p->rchild==NULL  ② p->rtag==1  ③ p->rtag==0  ④p->rtag==NULL

    6. 一个加权连通无向图的最小生成树可以使用   A  生成。一项工程完工所需的最少时间等于某个   B  

A： ① Hash算法  ② Dijstra算法 ③ prim算法  ④ Huffman算法

B： ① AOE网中源点到汇点事件最多的路径的长度

    ② AOE网中源点到汇点的最长路径的长度

③ AOE网中源点到汇点的最短路径的长度

④AOE网中源点到汇点活动最多的路径的长度

    7.用冒泡排序的方法对n个记录进行排序，第一趟共要比较  A   对元素。对n个元素进行排序，不稳定的排序是  B   ，快速排序是一种  C   ，关键字序列  D  是一个堆。

A：① n-1  ② n/2   ③ n+1      ④ n

B：① 直接插入排序  ② 冒泡排序  ③ Shell排序  ④归并排序

C：① 插入排序      ② 交换排序  ③ 枚举排序   ④选择排序

D：① 20,76,35,23,80,54  ② 20,54,23,80,35,76

   ③ 80,23,35,76,20,54  ④ 20,35,23,80,54,76

二．判断题（10分）

（  ）1．装填（负载）因子是哈希表的一个重要参数，它反映哈希表的装满程度。

（  ）2．邻接多重表表示法对于有向图和无向图的存储都适用。

（  ）3．深（高）度为k的二叉树至多有2k-1(k>=1)个结点。

（  ）4．一个循环链表可以由所给定的头指针或者尾指针唯一确定。

（  ）5．Huffman树、平衡二叉树都是数据的逻辑结构。

（  ）6．在二叉排序（查找）树中插入的新结点，总是被插入到某个叶子和下面。

（  ）7．每个加权连通图的最小生成树都是唯一的。

（  ）8．不是所有的AOV网都有一个拓扑序列。

（  ）9．Huffman树度为1的结点数等于度为2和0的结点数之差。

（  ）10．冒泡排序和堆排序都中属于交换排序。

三．简答题（25分，1-3小题每题5分，第4小题10分）

1．简述顺序存储结构与链式存储结构在表示数据元素之间的关系上的主要区别。

2．A、B、C三个元素进栈s的次序是A、B、C， 利用push(s,x)和pop(s)表示入栈和出栈操作，写出所有可能的出栈序列和获得每个序列的相应操作，并指明哪个序列不会是出栈序列。

3．试述一种判定有向图G中是否有环（回路、圈）的方法。

4．在地址空间为0--16的散列区中,对以下关键字序列

      (Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec),

   （1）构造HASH表。 H(x)=i mod 17 （或 H(x)=i % 17 ）,其中i为关键字x

中第一个字母在字母表中的序号,解决冲突的方法用线性探测法。

   （2）求出查找成功和查找失败的平均查找长度。

四．算法设计（35分）

要求： ①  用C语言、类C语言 或 类Pascal语言编写算法；

2应对算法中使用的数据类型给出必要的说明和注释。

  1．写一算法,建立双向循环链表。（10分）

  2．以二叉链为存储结构，求二叉树的深度。（10分）

  3．给定值k(1第k位上的记录，设计一个你认为最合适的算法。（15分）

武汉理工大学2003年研究生入学考试试题

一、选择题（26分，每空2分）

1．下列各项中属于逻辑结构的有        。

A. 哈希表    B. 有序表    C. 单链表    D. 顺序表

    2．由3个结点组成的二叉树的深度可能是        。

A．1  B.2     C.3      D.4

3．将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][]在B数组中的位置k等于        。

A．198  B.197     C.196      D.195

4．一棵满二叉树同时又是一棵        。

A. 完全二叉树    B. 二叉排序树    C . 正则二叉树   D. 平衡二叉树

    5．长度为n的顺序表，在任何位置上插入或删除一个元素的概率相等，插入一个元素时平均移动     个元素，删除一个元素时平均移动     个元素。

A．（n+1）/2    B.n/2        C.(n-1)/2        D.(n-2)/2

    6. 用s表示入栈操作，*表示出栈操作，栈的初态、终态均为空，入栈和出栈的操作序列可表示成仅为由s和*组成的序列。下面的序列中合法的操作序列有     。

A．s*ss*s**    B.sss**s**    C. s**s*ss*    D.sss*s*s*

    7.     是特殊的线性表。

A．队列    B.哈希表    C.栈       D.判定表

8. 表长为25的哈希表，用除留余数法公式H(key)=key % p 或H(key)=key mod p，

则p应取     为宜。

A.23      B.24       C.25        D.26

    9．任一个有向图的拓扑序列     。

A.可能不存在       B.有一个       C. 一定有多个     D.有一个可多个

    10．在下列的排序方法中，     方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。

A.快速排序  B. 冒泡排序     C.堆排序    D. 插入排序

    11．若以{4,5,6,7,8}作为权值构造Huffmen树，则该树的带权路径长度为     。

A.67      B.68      C.69        D.70

   12．设head(L)、tail()分别为取广义表表头和表尾的操作，则从广义表

L=((x,y,z),a,(u,v,w))中取出原子u的运算为     。

A.head(tail(tail(head(L))))  B.tail(head(head(tail(L)))) 

C.head(tail(head(taill(L))))  D.head(head(tail(tail(L))))

二、填空题（共32分，每空2分）

13．在单链表中设置头结点和作用是                                  。

14．线索二叉树的左线索指向其             ，右线索指向其               。

15．树在计算机内的链式存存储表示方法有         、        和          。

16．                                                    现象称为冲突。

17．用（A,B）的形式表示边，对图1的无向图，从项点A开始求最小生成树，用

Prim算法产生的边依次是                                                  ，

用Kruskal算法产生的边依次是                                             。

图1

18．用数组a[1]..a[n]表示循环队列sq，当循环队列sq满时，队有     个元素。

19．判定树常用来表示的                    查找过程。

20．直接插入排序、堆排序算法的时间复杂度分别是          、          。

21．树根的层次是1，则深度为8的完全二叉树至少有           个结点，                  拥有100个结点的完全二叉树的最大层次数是         。

22．对n个记录进行2-路归并排序，一共需要进行               趟归并。

三．简答题（47分）

23. (6分)有5个元素，其入栈次序为A,B,C,D,E，在各种可能的出栈序列中，第一个出栈元素是C且第二个出栈元素是D的出栈序列有哪几个？

24．（12分）一棵树的边的集合为{ (I,M), (I,N), (E,I), (B,E), (B,D), (C,B), (G,J), (G,K), 

(A,G), (A,F), (H,L),(A,H),(C,A) }。

（1）画出这棵树。

（2）哪个是根结点？哪些是叶子？

（3）树的深度是多少？

（4）将此树转化为相应的二叉树。

（5）将转化所得的二叉树进行后序穿线，建立后序线索树。

25．（7分）用十字链表存储稀疏矩阵的非零元，画出存放非零元的结点的结构图，并说明结点中各个域中分别存放什么内容？

26．（12分）对n个结点的有向图，采用邻接矩阵和邻接表表示时，如何判断下列问题：

（1）图中有多少条边？

（2）任意两个顶点i和j是否有边相连？

（3）任意一个顶点的度是多少？

27．（10分）依次输入序列（62, 68, 30, 61, 25, 14, 53, 47, 90, 84）中的元素，生成一棵二叉排序树。

四．算法设计（45分，每小题15分）

要求： ①  用C语言、类C语言 或 类Pascal语言编写算法；

3应对算法中使用的数据类型给出必要的说明和注释。

  28．用带头结点的循环链表作为队列的存储表示，不设头指针而只设一个尾指针rear指向队尾结点。试写了该链式队列的出队算法。

  29．二叉树采用二叉链作为存储结构，写一递归算法计算二叉树的深度。

  30．已知(r1, r2, ……, rn) 是一个小顶堆，写一算法，使得增加一个元素rn +1后(r1, r2, ……, rn，rn +1)仍是一个堆。

武汉理工大学2004年研究生入学考试试题

1．在供选择的答案中选择1—4个正确的答案（60分，每小题３分）

（1）数据结构研究的内容涉及        。

A. 数据如何组织    B. 数据如何存储

C. 数据的运算如何实现    D. 算法用什么语言来描述

（2）将长度为n的单链表接在长度为m的单链表之后的算法的时间复杂度为：

      A．O（m+n）  B.O(n)     C.O(m)      D.O(m*n)

（3）i=1; j=n; x=r[1];

while ( i { while (i=x) j--;

r[i]=r[j]; 

while (ir[i]=r[j];

   }

  r[j]=x;

上述程序段的时间复杂度为：

      A．O(n）  B.O(n2)     C.O(1)      D.O(nlog2n)

（4）队列的“先进先出”特性是指        。

A. 最后插入队列中的元素总是最后被删除

B. 当同时进行插入、删除操作时，总是插入操作优先

C. 每当有删除操作时，总要先做一次插入操作

D. 每次从队中删除的总是最早插入的元素

（5）在一个具有n个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和

      的差为：

A．10        B.20         C. 0        D.5

（6）树的后序遍历序列与     其对应的二叉树（以孩子-兄弟链存储的二叉树）的遍历序列是一致的。

A．前序遍历    B.中序遍历    C. 后序遍历    D.层次遍历

（7）下列关于二叉树遍历的叙述中, 正确的有:

    　A. 若一个结点是某二叉树中序的最后一个结点, 则必是该二叉树的前序最后一个结点.

      B. 若一个结点是某二叉树前序的最后一个结点, 则必是该二叉树的中序最后一个结点.

      C. 若一个叶子是某二叉树中序的最后一个结点, 则必是该二叉树的前序最后一个结点.

      D. 若一个叶子是某二叉树前序的最后一个结点, 则必是该二叉树的中序最后一个结点.

（8）将一组无序的数据重新排列成有序序列, 其方法有:  

A.拓扑排序  B.快速排序   C.堆排序  D.基数排序

（9）已知某二叉树的结点的后序序列是BDECA, 中序序列是BADCE, 则前序序列是:

A.AEDCB       B.ABCDE       C. CDABC      D.BDECA

（10）对{05,46,13,55,94,17,42 }进行基数排序, 一趟排序的结果是:

A.05,46,13,55,94,17,42 　  B. 05,13,17,42,46,55,94

C.42,13,94,05,55,46,17     D. 05,13,46,55,17,42,94

（11）每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有     叶子。

A.    B.  C.      D. 

图1

（12）图1所示无向网络，从顶点v1开始按普里姆方法构造最小生成树，依次选取的

       5条边是        。

A. ( v2，v1), ( v2，v6), ( v6，v5), ( v2，v3), ( v5，v4)

B. ( v6，v5), ( v6，v2), (v2，v3), ( v5，v4), ( v2，v1)

C. ( v1，v2), ( v2，v6), ( v2，v3), ( v5，v6), ( v5，v4)

D. ( v6，v5), ( v2，v6), ( v2，v1), ( v5，v4), ( v2，v

（13）B+树是        。

A. 一种AVL树              B. 索引表的一种组织形式

C. 一种高度不小于1的树    D. 一种与二进制Binary有关的树

（14）图G=（V，E），其中，Ｖ＝｛1,2,3,4｝，Ｅ＝｛(1,2),(1,3),(1,4),(2,1),(2,3),(2,4)｝

　　　深度优先遍历图Ｇ的遍历序列有：

A.１２３４  B.２３４１   C.４３２１　 D.３２１４

（15）元素进栈的次序为:A,B,C,D,E。可能的出栈序列是

A.　ABCDE　  B. CBADE　   C. DCABE  　 D. ACBED  

（16）将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号,根结点的编号为1,则编号为49结点的左孩子编号是:

    　　A. 98　    B. 99    C. 50    D. 48

（17）在下面几组关键字中,哪个是小顶堆

        A.{05,42,13,55,94,17,46}        B.{05,46,13,55,94,17,46,42}

        C.{05,42,17,94,55,13,46}        D.{94,42,55,01,17,13,46}

（18）下列４个排序算法中，哪些是稳定的？

A.插入排序  B.快速排序   C.堆排序  D.归并排序

（19）有一字符序列{Q,H,C,Y,P,A,M,S,R,D,F,X}, 问新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}  

       是下列哪个排序算法一趟排序的结果

        A. 起泡排序      B. 快速排序   C. 直接选择排序  D. 都不是

（20）下三角矩阵a[n][n]压缩到一维数组Ｂ[1]..B[n*(n+1)/2]中，若按行主序存 

       储，则A[i][j]对应在Ｂ中的存储位置为：

2．简答题（45分，每小题9分）

（21）线性表与广义表的区别是什么？线性表有哪几种存储结构？广义表呢？画出广义表Ｌ（a，(b,c),  (d) ）的存储结构图。

（22）hash表与其它的查找方法的本质上的区别是什么？在地址空间为0--16的散列区中,对关键字序列

          (Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec),

       构造HASH表。 H(x)=i mod 17 （或 H(x)=i % 17 ），其中i为关键字中第一个字母在字母表中的序号(a..z 对应１..26), 解决冲突的方法用链地址法。

（23）什么是排序？简述归并排序的方法。对关键字序列

｛13,45,55,12,79,11,88,90｝

      进行归并排序，要求写出每一趟的排序结果。

（24）一个有11个结点的树以左孩子-右兄弟链表存储 (静态二叉链表)，如下表所示。① 求该树及对应的二叉树；② 建立一个前序线索链表(不画树的形态，用“-”表示线索)。

　　　　　  1     2     3    4     5     6     7    8     9     10     11

3．算法设计（45分，每小题15分）

要求： ①  用类C语言 或 类Pascal语言编写算法；

②  在算法中给出必要的类型描述和注释。

（26）以顺序表为存储结构，写一算法，删除线性表中从第i个元素开始的k个元素。

（27）以单链表为存储结构，完成如下运算：删除该链表中其值为x的结点，并将它插入到表首。写一算法实现。

（28）以二叉链为存储结构，写一算法，判断一个二叉树是否是二叉排序树。

武汉理工大学2005年研究生入学考试试题

2．在供选择的答案中选择1—4个正确的答案（60分，每小题2分）

计算机算法是指:  （1）  ，算法分析的目的是:  （2）  ，评价算法的标准是  (3)  。算法在发生非法操作时可以作出处理的特性称为  (4)  。下列算法的时间复杂度和空间复杂度分别是   (5)  。

int  fib( int n) {

if (n<=1) return n;

    else return  fib(n-1)+fib(n-2);

}

(1) A. 解决某一问题的查找方法      B. 解决某一问题的排序方法         

C. 解决某一问题的有限运算      D. 解决某一问题的无限运算

(2) A. 找出数据结构的合理性        B. 研究算法的输入和输出的关系

C. 分析算法的效率以求改进      D. 分析算法的可读性和文档性

(3) A. 正确性    B. 可读性    C.健壮性        D. 高效率及低存储量

(4) A. 键状性    B. 可行性    C.终止性        D. 可靠性

(5) A. T(n)=O(1),S(n)=O(1)        B. T(n)=O(n),S(n)=O(n)

    C. T(n)=O(2n),S(n)=O(1)       D. T(n)=O(2n),S(n)=O(n)

线性表的两种存储结构是  (6)  ，在顺序表中插入、删除一个元素，移动次数取决于哪些因素  (7)   。 

(6) A. 线性结构和非线性结构        B. 顺序结构和非顺序结构

C. 逻辑结构和物理结构          D. 内部结构和外部结构

(7) A. 结点存放顺序                 B. 线性表的长度    

C. 插入或删除位置             D. 每个结点有多少个字段

栈的“后进先出”特性是指 （8）  。若5个元素的出栈序列是1,2,3,4,5，则进栈序列不可能是  （9）  。当4个元素的进栈序列给定以后，由这4个元素构成的可能的出栈序列共有  （10）  种。

(8)  A. 最先入栈的元素总是最后被删除

B. 当同时进行插入、删除操作时，总是插入操作优先

C. 每当有删除操作时，总要先做一次插入操作

D. 每次从栈中删除的总是最后插入的元素

(9)  A. 3,1,2,5,4    B. 2,3,1,5,4    C. 3,1,4,2,5    D. 2,4,3,1,5

(10) A. 14        B. 16       C. 17        D. 24

对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用  （11）  次序的遍历实现编号。

(11) A．先序            B.  中序            C. 后序        D. 从根开始的层次遍历

某二叉树的先序序列和后序序列正好相反，则该二叉树一定是  （12）  的二叉树。若二叉树结点的前序序列是abcd，后序序列是dcba，则该二叉树  （13）  。

(12) A．空或只有一个结点                B. 高度等于其结点数

C. 任一结点无左孩子                D. 任一结点无右孩子

(13) A. 每个分支结点都没有左孩子    B. 每个分支结点都只有一个孩子

C. 每个分支结点都没有右孩子    D. 深(高)度一定为4

   若用二叉链表来存储具有m个叶子、n个分支结点的树，则二叉链表中有  (14)  个左指针域为空的结点，有  (15)  个右指针域为空的结点。

(14) A. m       B. m-1       C. m+1        D. 2m

(15) A. n        B. n-1       C. n+1         D. 2n

n个结点的二叉树中如果有m个叶子，则有  (16)  个度为1的结点，  (17)  个度为2的结点。

(16) A. n-2m+1  B. n-m-1      C. n-2m-1     D. n+2m-1

(17) A. m       B. m-1       C. m+1        D. 2m

下图所示无向网络，构造最小生成树的方法有 （18）  。广度优先遍历序列是： 

  （19）。

(18) A. floyd算法  B. Dijstra算法   C. prim算法  D. kruskal算法

(19) A.1,2,3,5,4,6          　  B. 5,3,1,6,2,4

C.6,3,4,5,2,1,             D. 2,1,6,4,3,5

由权序列{1,2,4,5,10}构造哈夫曼树，其带权路径长度值为  (20)  。根据使用频率为五个字符设计的哈夫曼编码可能是  (21)  。

(20) A. 33    B. 44    C. 34    D. 54

(21) A. 1100，1101，111，10，0       B. 1100，1101，111，10，1

C. 0011，0010，001，01，1       D. 1011，1010，100，10，0

将一组无序的数据重新排列成有序序列, 其方法有  （22）  。在  （23）  提

供的４个排序算法中，哪些是不稳定的，在  （24）  算法中，可能会出现下面情况：初始数据有序时，花费的时间反而最多。在线性表中个元素已经有序排列的情况下，执行 （25）排序，可以尽快结束排序过程。对{45,46,13,25,94,75,23 }构造（大顶堆），其结果是  （26）  。

(22) A.拓扑排序      B.快速排序     C.二叉排序树   D.haffman树

(23) A.简单选择排序  B.快速排序     C.堆排序       D.SHELL排序

(24) A.堆排序        B.快速排序     C.堆排序       D.直接插入排序

(25)  A.堆    B. 起泡    C. 基数        D. 快速

(26) A.94,46,75,25,45,13,23     B. 94,75,46,45,25,23,13

C.94,46,13,25,45,75,23     D. 45,46,13,25,94,75,23

在有序表（2,4,6,8,10,12,14,16,18,20,22）上用折半查找方法查找元素16，需要进行  （27）  次元素的比较，查找元素9，依次被比较的元素是  （28）  。

(27) A. 3         B. 4           C. 5           D. 10

(28) A.12,4,6,8    B. 10,4,6,8      C. 12,10,6,8    D. 12,6,8,10 

散列查找的时间复杂度是 （29）  。在散列查找过程中，可用  （30）  来处理冲突。

(29) A. O(n)    B. O(1)   C. O(log2n)  D. O(nlog2n)

(30) A. 除留余数法  B. 数字分析法  C. 线性探测法  D. 链地址法

2．图表计算题（45分，每小题9分）

(31) 已知二叉树结点的中序序列是cgbahedjfi，后序序列是gbchejifda，请画出这棵二叉树的逻辑结构图。

(32) 如果一个树T中有n1个度为1的结点，n2个度为2的结点，……,nm个度为m的结点，求该树中的叶子个数。

(33) 对关键字序列｛161,738, 92, 485, 637, 101, 21, 530, 791, 306｝进行快速排序（写出每一趟的结果）。

(34) 先以｛18,45, 12,79,11, 15,42,90｝构造二叉排序树，再插入88，并将该树调整为平衡二叉排序树。画出构造的二叉排序树、插入88后的二叉排序树和调整后的平衡二叉排序树。

(35)图G的邻接表如下，求出其拓扑序列。

3．算法设计（45分，每小题15分）

要求： ①  用类C语言 或 类Pascal语言编写算法；

②  在算法中给出必要的类型描述和注释。

(36) 以顺序表为存储结构, 写一算法，删除线性表中所有值为x的元素。

(37) 以单链表为存储结构，写一算法将线性表逆置，即将（a1,a2,,,,an）=>(an,…,a2,a1)。

(38) 以孩子-兄弟链表为存储结构，写一算法，求树的度。

    武汉理工大学

一、选择题（每小题2分，共10分）

1．若线性表最常用的操作是存取第I个元素及其前驱的值，则采用（    ）存储方式节省时间。

A．单链表        B. 双链表        C. 单循环链表        D. 顺序表

2．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（    ）次序的遍历实现编号。

A．先序            B.  中序            C. 后序        D. 从根开始的层次遍历

3．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（    ）的二叉树。

A．空或只有一个结点                B. 高度等于其结点数

C. 任一结点无左孩子                D. 任一结点无右孩子

4．下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlog2n)的是（    ）。

A．堆排序            B.  冒泡排序            C. 直接选择排序        D. 快速排序

5．下列排序算法中，（    ）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

A．堆排序            B.  冒泡排序            C. 快速排序        D. 直接插入排序

二、判断题（每小题1分，共8分）

1．（    ）在循环队列中，若尾指针Real大于头指针Front，则其元素数为Real-Front。

2．（    ）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。

3．（    ）二叉树只能采用二叉链表来存储。

4．（    ）有向图用邻接矩阵表示后，顶点I的出度等于第I行中非0且非∞的元素个数。

5．（    ）图G的某一最小生成树的代价一定小于其他生成树的代价。

6．（    ）给定结点数的平衡二叉树的高度是唯一的。

7．（    ）只有在初始数据表为倒序时，冒泡排序所执行的比较次数最多。

8．（    ）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶子结点”上。

三、填空（每小题2分，共14分）

1．在单链表中，删除指针P所指结点的后继结点的语句是（    ）。

2．已知完全二叉树的第八层有8个结点，则其叶子结点数是（    ）。

3．有n个顶点的强连通有向图G至少有（    ）条弧。

4．求最短路径的DIJKSTRA算法的时间复杂度为（    ）。

5．在有序表A[1，20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元素的下标依次为（    ）。

6．直接选择排序算法所执行的元素交换次数最多为（    ）。

7．下列排序算法中，稳定的排序算法是（    ）（选择排序，堆排序，快速排序，直接插入排序）。

四、解答下列各题(38分)

1．一棵二叉树的先序序列和中序序列分别如下，画出该二叉树。(6分)

    先序序列ABCDEFGHIJ    

中序序列CBEDAGHFJI

2．对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。(8分)

    4，  5，  6，  7，  10，  12，  15，  18，  23   

3．图G的邻接表如下，完成下列各题：(8分)

    (1)画出从顶点5出发进行广度遍历所生成的生成树。

(2)判断其中是否存在有向回路，若不存在，求出其拓扑序列。

4．对下列数据表，写出采用快速排序算法排序的每一趟的结果。(8分)

    (60，20，31，1，5，44，55，61，200，30，80，150，4，29)

5．已知哈希表地址空间为0．．8，哈希函数为H(k)=k % 7，采用线性探查法处理冲突。将下面数据序列依次存入该散列表中，并求出在等概率下的平均查找长度。(8分)

    100，20，21，35，3，78，99，45

   0       1         2       3         4       5         6       7         8

1．已知单循环链表L中至少有两个结点，每个结点的两个字段为data和next，其中字段data的类型为整型。设计算法以判断该链表中的每个元素的值是否小于其后续两个结点的值的和，若满足，返回true，否则返回false。

2．设计算法按后序次序打印二叉树T中所有叶子结点的值，并返回其结点数。

3．写出在二叉排序树中查找值为x的元素的算法。