3. 空格串是________________________________。 4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。

5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为 ，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为 ，图的深度或广度优先搜索遍历时的空间复杂度均为 。

6、一个图的 表示法是唯一的，而 表示法是不唯一的。 三、算法

设二叉树采用二叉链表结构，试设计一个算法统计给定二叉树中的一度结点数目。 四、应用题

1、对关键字无序序列(36，25，48，12，65，43，20，58)进行直接选择排序，请写出每一趟排序的结果。（10分）

2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。（10分）

3

、

已

知

A 9 3 2C B 8 D 5 E 4 6 1 F 2 G 记录关键字集合为

（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况）

4、设被查找文件有4095个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比较次数为多少？

作业题（二）

、单项选择题

1. 有六个元素6，5，4，3，2，1 哪一个不是合法的出栈序列？（ A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2. 栈和队都是（ ）

A．顺序存储的线性结构 B. 线性结构

C. 限制存取点的线性结构 D. 非线性结构

3、顺序查找法适合于存储结构为（A．散列存储 存储

的顺序进栈，问下列）

链式存储的非限制存取点的 ）的线形表。

B．顺序存储或链接

C．压缩存储 D．索引存储 4、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。

A．（100，80， 90， 60， 120，110，130） B．（100，120，110，130，80， 60， 90） C．（100，60， 80， 90， 120，110，130） D． (100，80， 60， 90， 120，130，110) 5、折半查找的平均比较次数为（ ）。

A．n B．n/2 C．log2n D．log2(n+1) 6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）

A．必定快 B．不一定

C．在大部分情况下要快 D．取决于表递增还是递减

7、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（ ）。