2017年MBA考研《计算机数据结构》历年试题（3）

2017年MBA考研《计算机数据结构》历年试题填空题

1. 设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：　　 1) s->next=___________;2) p->next=s;3) t=p->data;

4) p->data=___________;5) s->data=t;

2. 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。

3. 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。

4. 对一组初始关键字序列(40，50，95，20，15，70，60，45，10)进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。

5. 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的角度来考虑则最好选择________排序。

6. 设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。

7. 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。

8. 设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。

9. 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_______________________。

10. 设无向图G(如右图所示)，则其最小生成树上所有边的权值之和为_________________。