MBA考研《计算机数据结构》模拟试题（3）

《计算机数据结构》模拟试题填空题

1. 设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需要比较_____________次。

2. 快速排序算法的平均时间复杂度为____________，直接插入排序算法的平均时间复杂度为___________。

3. 设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。

4. 设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。

5. 设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有_________个空指针域。

6. 设指针变量p指向单链表中结点A，则删除结点A的语句序列为：

q=p->next;p->data=q->data;p->next=___________;feee(q);

7. 数据结构从逻辑上划分为三种基本类型：___________、__________和___________。

8. 设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________;用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。

9. 设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是________。

10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_____________________。