#102. 期末模拟填空题

本题采用Special Judge，在比赛结束后统一评分（提交时显示WA 0为正常现象）。请将每题答案以回车分开，同一小题中若有多个填空，以题目要求为准。

例如（忽略//注释）：

13         //第1小题答案
6          //第2小题答案
i++;       //第3小题答案
6_18       //第4小题答案
1,2,3,4,5  //第5小题答案

1. 一个深度为5的完全二叉树，最多有n个节点，最少有m个节点，最多与最少的节点数相差n-m为_____

2. 将 ((A+B)*C+D）*E+F/G 转为后缀表达式_____

3. 对于一个栈，元素的入栈顺序为ABCDEFGHIJK，元素的出栈顺序为DEHGJKIFCBA，则栈深度至少为_____

4. 下图由A点至H点的独立路径数为_____

5. 使用以下代码进行数组排序，需运行!!!行代码的次数为_____

int num[] = {15,14,17,30,5,8,11};
int i, j, flag, temp;

for(i = 0; i < 6; i++)
{
    flag = 0;
    for(j = 0; j < 6 - i; j++)
    {
        if(num[j] < num[j + 1])
        {
            temp = num[j];
            num[j] = num[j + 1];
            num[j + 1] = temp;
!!!         flag++;
        }
    }
    if(flag == 0) break;
}

6. 对于归并排序，最坏情况的时间复杂度为_____，最好情况的时间复杂度为_____，平均时间复杂度为_____。（请用O(n),O(n^2),O(logn),O(nlogn)等作答，答案两两用空格隔开，注意答案最后不要带空格）

7. 若仅以{4, 5, 6, 7, 8}作为叶子节点构造带权路径最大的完全二叉树，则其带权路径长度为_____

8. 现有30个元素入栈，第1个出栈的元素是第29个入栈的元素，第5个出栈的是第30个入栈的元素，第10个出栈的是第_____个入栈的元素。

9. 存储结构通常有顺序结构、链式结构、索引结构和_____结构。

10. 当可选存储方案有邻接表和邻接矩阵时，对于一个稀疏图，采用_____存储较省空间