A．v1，v2，v3，v5，v4 B．v1，v2，v3，v4，v5

C．v1，v3，v4，v5，v2 D．v1，v4，v3，v5，v2

8、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（ ）。

A．顺序存储 B．链式存储 C．索引存储 D．散列存储 9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（ ）。

A．s B．s-1 C．s+1 D．n

10、如图所示，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列是（ ）。

A．A E C D B F G B．A G B F D E C C．A C E D B G F D．A B D G F E C

二、填空题

1. 设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共

有________个结点。

2. 有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是________，带权路径长度WPL为________。

3.设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为________________。 4. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。

5、设G为具有N个顶点的无向连通图，则G中至少有 条边。

6、哈夫曼树（Huffman Tree）又称 。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL 。

7、树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的 ；依次先序遍历树的 。 三、应用题

1、给定权值集合{1, 4, 2, 6, 9,}, 构造相应的哈夫曼树, 并计算它的带权路径长度。

2、对关键字序列{10，6，3，2，5，4}，构造一棵平衡二叉（排序）树并画图（要求画出建树过程）。

3、设有一个有序文件，其中各记录的关键字为（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15），当用折半查找算法查找关键字为3，8，19时，其比较次数分别为多少？

4、对有五个结点{ A,B, C, D, E}的图的邻接矩阵，

?010030?10???0????????60020?????10?0????????500?? （1）．画出逻辑图 ；

（2）．画出图的十字链表存储；

（3）．基于邻接矩阵写出图的深度、广度优先遍历序列； （4）．计算图的关键路径。

作业题（三）

一、单项选择题

1．串的长度是指（ ）

A．串中所含不同字母的个数 B．串中所含非空格字符的个数

C．串中所含不同字符的个数 D．串中所含字符的个数

2．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。

A. BA+141 B. BA+180 C. BA+222 D. BA+225

3．算法分析的两个主要方面是（ ）。

A．空间复杂性和时间复杂性 B．正确性和简明性

C．可读性和文档性 D．数据复杂性和程序复杂性

4．算法分析的目的是（ ）。

A．找出数据结构的合理性 B．研究算法中的输入和输出的关系

C．分析算法的效率以求改进 D．分析