天津理工大学数据结构2014复习提纲(2)

⑵ 用Dijkstra算法求从v1出发到各顶点的最短路径。 P159 图 5-36

5、 用Floyd算法求下图中每对顶点间的最短路径。 P159 图 5-37

6、 用邻接矩阵表示图时，若图中有100个顶点和100条边，则形

成的邻接矩阵中有多少个元素？有多少个非零元素？是否为稀疏矩阵？

7、 用邻接矩阵表示图时，矩阵中元素的个数与顶点个数是否相

关？与边的条数是否相关？

8、 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向

强连通图至少有多少条边？

9、 对于有n个顶点的无向图，若采用邻接矩阵表示如何判断以下

问题：

⑴ 图中有多少条边？

⑵ 任意两个顶点i和j之间是否有边相连？ ⑶ 任意一个顶点的度是多少？ 第六章 数据结构的程序实现

1、阐述数据结构在问题建模中的重要作用。 第七章 检索与基本算法

1、 若对大小为n的顺序表和有序表分别进行顺序检索，在等概率

的前提下，工况时的平均检索长度是否相同：

⑴ 检索不成功，即表中没有关键字值等于给定值k的记录；

⑵ 检索成功，表中只有一个关键字值等于给定值k的记录； ⑶ 检索成功，表中有若干个关键字值等于给定值k的记录，依次检索要求能全部找出所有关键值等于给定值k的记录。

2、 对长度为20的有序表进行二分法检索，画出他的一棵判定树，

并求出在等概率情况下检索成功和不成功时的平均检索长度。 3、 对于10000个项的线性表，若采用等分区间顺序检索方法进行

检索，问：

⑴ 每块的理想长度为多少？此时把线性表划分成多少个块？ ⑵ 平均检索长度为多少？假定在等概率情况下讨论。 ⑶ 若每块长度为40，请平均检索长度为多少？

4、 设结点序列为（60，30，90，50，120，70，40，80），用二叉

检索树的插入算法，画出按此结点序列建立的一棵二叉检索树T1；再用二叉检索树的删除算法，画出依次删除结点40，70，60之后的二叉检索树T2。 5、 已知长度为12的表如下所示：

（Jan,Feb，Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec） ⑴ 按表中元素的顺序依次插入一棵初始为空的二叉检索树中，画出最终的二叉检索树，并求在等概率情况下检索成功时的平均检索长度。

⑵ 若先对表中元素排序成有序表，求在等概率情况下进行二分法检索时检索成功的平均检索长度。

⑶ 构造一棵二叉平衡树，求在等概率情况下进行二分法检索时检

索成功的平均检索长度。

6、 具有n个结点的二叉检索树有多少种不同的形态？一个高度为

h的二叉平衡树至少有多少个结点？具有n个结点的二叉平衡树的最大高度和最小高度各是多少？

7、 给定关键字序列为（19，14，23，1，68，20，84，27，55，11，

10，79），设哈希表长为13，哈希函数为h（k）=k： ⑴ 画出用线性探索法消除地址冲突时所构造的哈希表。 ⑵ 画出用链地址法消除地址冲突时所构造的哈希表。 ⑶ 并求出以上两种哈希表的平均检索长度。

8、设计一个算法，求出指定结点在二叉检索树中的层次数。

第八章 排序与基本算法

1、 什么是排序？什么是内排序？什么是外排序？

2、 给定排序码序列为（17，8，21，35，32，15，21，25，12，23），

分别写出： ? 直接插入排序

? 希尔排序（增量为5，2，1） ? 二路插入排序 ? 折半插入排序 ? 共享栈插入排序 ? 冒泡排序 ? 快速排序

? 直接选择排序 ? 树形选择排序 ? 堆排序 ? 二路归并排序 ? 基数排序

3、 在冒泡排序方法中，什么情况下排序码会朝着与最终位置相反

的方向移动？是举例说明。

4、 对于n个排序码进行快速排序时，所需的比较次数与排序码的

初始序列有关。当n=7时，回答下列问题：

⑴ 在最好的情况下需要进行多少次比较？请说明理由。 ⑵ 给出在最好情况下的排序码初始序列的一个实例。 ⑶ 在最坏的情况下需要进行多少次比较？请说明理由。 ⑷ 给出在最坏情况下的排序码初始序列的一个实例。 5、 写出快速排序的非递归算法，并回答下面问题：

⑴ 在非递归实现排序快速排序时，通常要用一个栈来保存待排序区间的两个端点。这个栈能否用队列来代替？为什么？ ⑵在非递归实现排序快速排序时，可根据基准把待排序区间分割为两个区间。若下一趟先对较短的区间进行排序。证明在这种情况下快速排序所需栈的深度为O（nlogn）。

6、 若排序码有11个，为了完成树形选择排序，至少需要进行多少

次关键字值的比较？

7、 判断下列序列是否为堆。若不是堆则把它们调整为堆：

? （100，85，98，77，80，60，82，40，20，10，66） ? （100，98，85，82，80，77，66，60，40，20，10） ? （100，85，40，77，80，60，66，98，82，10，20） ? （10，20，40，60，66，77，80，82，85，98，100） 8、 希尔排序、直接选择排序、快速排序、堆排序都是不稳定的排

序方法，举例说明。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库天津理工大学数据结构2014复习提纲(2)在线全文阅读。