数据结构第六-九章自测题及解答.docVIP

《数据结构》非线性部分内容2(第六－九章)自测题(时间：3:00小时)

注：本自测题仅供自测用，不代表期末考试观点，如无雷同，敬请谅解！第PAGE13页共NUMPAGES13页

概念题（每空0.5分，共45分）

1．对于集合这逻辑结构来说，其中的数据元素之间也可以有各种各样的非逻辑关系，但任何一对数据元素之间没有________关系，即没有________关系。

2．查找表按其所包括的运算的不同分为________查找表和________查找表。

3．查找表中主关键字指的是________，次关键字指的是________。

4．静态查找表包括________、________、________三种基本运算。

5．动态查找表包括________、________、________、________、________五种基本运算。

6．假定key为主关键字，若顺序表中第n个元素的键值为K，则顺序查找算法的查找长度为1；若第1个元素的键值为K，则查找长度为________；若表中无键值等于K的元素，则查找长度为________。

7．二分查找在查找成功时的查找长度不超过________，其平均查找长度为________，当n较大时约等于________。

8．静态查找表的三种不同实现各有优缺点。其中，________查找效率最低但限制最少。________查找效率最高但限制最强。而________查找则介于上述二者之间。

9.二叉有哪些信誉好的足球投注网站树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。

10.在表示一棵二叉有哪些信誉好的足球投注网站树的二叉链表上，要找键值比某结点X的键值________的结点，只需通过结点X的左指针到它的左子树中去找。。

11.中序遍历一棵二叉有哪些信誉好的足球投注网站树所得的结点访问序列是键值的________序列。

12.二叉有哪些信誉好的足球投注网站树上的查找长度不仅与________有关，也与二叉有哪些信誉好的足球投注网站树的________有关。

13.在随机情况下，含有n个结点的二叉有哪些信誉好的足球投注网站树的平均查找长度为________，其时间效率很高。

14.折半查找的查找效率与树的形态有关。当二叉有哪些信誉好的足球投注网站树退化为一条单支时，查找算法退化为________查找，平均查找长度上升为________。

15.有n个结点的AVL树的深度与________是同数量级的，因而在它上面进行查找的平均查找长度也与________同数量级。

16.平衡二叉有哪些信誉好的足球投注网站树上任一结点的平衡因子只可能是________、________或________。

17.在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为________，比较二次查找成功的结点数为________，比较五次查找成功的结点数为________。总的平均查找长度为________。

18.按组织形式的不同，通常有________与________两类散列表。

19.对闭散列表来说，________的方法就是处理冲突的方法。

20.________是散列表的一个重要参数，它反映出散列表的装满程度；在散列存储中，该值越大，则________。

21.图有、等存储结构，遍历图有、等方法。

22.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。

23.如果n个顶点的图是一个环，则它有棵生成树。

24.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为；若采用邻接表存储，则空间复杂度为。

25.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为；若采用邻接表存储时，该算法的时间复杂度为；若是采用广度优先遍历算法的时间复杂度为；同样若用邻接表存储，该算法的时间复杂度为。

26.图的BFS生成树的树高比DFS生成树的树高。

27.用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为；用克鲁斯卡尔(Kruskal)算法的时间复杂度是。若要求一个稀疏图G的最小生成树，最好用算法来求解；若要求一个稠密图G的最小生成树，最好用算法来求解