6.向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此 时需要修改相关()个指针域的值。 A.2 B.3 C.4 D.5 7.在一个具有n个顶点的有向图的邻接矩阵表示中，删除一条边<i,j>需要的时间复杂 度为( )。 A.O(1) B.O(i) C.O(n) D.O(n2) 8.在一棵B树中，当插人一个元素时，若最终引起树根结点的分裂，则新树的高度比原 树的高度()。 A.减1 B.减2 C.增1 D.增2 9.对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与()有关。 A.n B.m C.n/m D.n*m 得 分 评卷人 二、填空题（在横线处填写合适的内容。每小题2分，共14分） 1.链表只适用于 查找。 2.归并排序算法的时间复杂度为 3.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有 个结点。 4.假定一棵树的广义表表示为a(b,c,d(e,f),g(h),则结点f的层数为 假定 树根结点的层数为0。 5.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的 继续搜索。 766. 棵AVL 树插入元 对最小 整过程 时需要修改相关( )个指针域的值。 A. 2 c. 4 B. 3 D. 5 7. 邻 接 一条 需要 度为( )。 A.O(l) B.O(i) C.O(n) D. 0(n2 ) 8. 棵B 插入 起 树根 新树 树的高度( )。 A. 减1 B. 减2 c. D. 增2 9. 对存 索长度 )有关。 A. n c. n/m 得分|评卷人 B. m D. 长m 二、填空题(在横线处填写合适的内容。每小题 1. 2. 序 算 法 杂度 3. 尾 指 个结点 4. 广 义 为a ，c , g (h) ) ，则结点 f的层数为。假定 树根结点的层数为 5. 搜 索 素 时 给 定 继续搜索。 76