写在前面

第一篇CSDN博客哦^_^
上个学期刚刚学过《数据结构》。然而一学期的课程下来之后，不论期末考试的成绩如何，自己上机实验的时间远远不够，动手能力太差了。⊙﹏⊙ 决定暑假再学一遍《数据结构》，毕竟是计算机专业的基础。
暑假的任务并不少（什么上大学又学习轻松又假期时间长等等都见鬼去吧 ˋ^ˊ ），一直到mooc通知要期中考试了自己才看了一点点 ╯ˍ╰ 这几天将视频补完终于是在截止日期结束之前考完了期中 ∩ˍ∩
题虽然简单，然而我要练习的是编程能力而不是做题能力啊……这门课程好就好在在PTA上配备了大量的编程练习。接下来争取将那些题一点一点做完，将我的代码写在博客里供大家批评（>﹏<）希望大家多多指教，我也会一点一点优化自己的代码 (●’◡’●)ﾉ
争取两周半后回校之前至少保证一天一道题……吧……（自己都不信QAQ）

中国大学MOOC-陈越、何钦铭-数据结构-2019夏期中考试（含答案）

判断题

1-1
在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。 (3分)
1-2
算法可以没有输入，但是必须有输出。 (2分)
1-3
已知一棵二叉树的先序遍历结果是ABC, 则CAB不可能是中序遍历结果。 (3分)
1-4
若一棵平衡二叉树的所有非叶结点的平衡因子都是0，则其必为完美二叉树。(3分)
1-5
一棵有124个结点的完全二叉树，其叶结点个数是确定的。 (3分)
1-6
所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (2分)
1-7
用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 (3分)
1-8
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。 (3分)
1-9
在一棵由包含4、5、6等等一系列整数结点构成的二叉搜索树中，如果结点4和6在树的同一层，那么可以断定结点5一定是结点4和6的父亲结点。 (3分)
1-10
通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。 (3分)

Key：1-5 FTTTT 6-10 FFFFF

单选题

2-1
将{5, 2, 7, 3, 4, 1, 6}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是：(4分)
A. 1, 2, 3, 4, 6, 7, 5
B. 1, 4, 2, 6, 3, 7, 5
C. 1, 4, 3, 2, 6, 7, 5
D. 5, 4, 3, 7, 6, 2, 1
2-2
在将数据序列（ 6, 1, 5, 9, 8, 4, 7 ）建成大根堆时，正确的序列变化过程是：(4分)
A. 6,1,7,9,8,4,5 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
B. 6,9,5,1,8,4,7 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
C. 6,9,5,1,8,4,7 → 9,6,5,1,8,4,7 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5
D. 6,1,7,9,8,4,5 → 7,1,6,9,8,4,5 → 7,9,6,1,8,4,5 → 9,7,6,1,8,4,5 → 9,8,6,1,7,4,5
2-3
循环顺序队列中是否可以插入下一个元素（）。 (4分)
A. 与队头指针和队尾指针的值有关
B. 只与队尾指针的值有关，与队头指针的值无关
C. 只与数组大小有关，与队首指针和队尾指针的值无关
D. 与曾经进行过多少次插入操作有关
2-4
已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是： (4分)
A. 39
B. 52
C. 111
D. 119
2-5
设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是：(4分)
A. h=t; t->next=h->next;
B. t->next=h->next; h=t;
C. h=t; t->next=h;
D. t->next=h; h=t;
2-6
下列函数中，哪个函数具有最快的增长速度？ (4分)
A. N²logN
B. N(logN)⁴
​C. N³
D. NlogN²
​​2-7
在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }（注：−n表示树根且对应集合大小为n），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？ (4分)
A. 1和-6
B. 4和-5
C. 8和-5
D. 8和-6
2-8
一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。 (4分)
A. 15
B. 16
C. 17
D. 47
2-9
下列代码

for(i=0; i<n; i++)
  for(j=i; j>0; j/=2)
     printf("%d\n", j);

的时间复杂度是： (4分)
A. O(N×i)
B. O(N)
C. O(N²​​)
D. O(NlogN)
2-10
若某图的深度优先搜索序列是{V1, V4, V0, V3, V2}，则下列哪个图不可能对应该序列？ (4分)
A.
B.
C.
D.
2-11
设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？ (4分)
A. 0
B. 2
C. 4
D. 5
2-12
假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为： (4分)
A. 2
B. 3
C. 4
D. 5

Key：1-6 CAACDC 7-12 BBDCBC

程序填空题

5-1
下列代码的功能是返回带头结点的单链表L的逆转链表。

List Reverse( List L )
{
    Position Old_head, New_head, Temp;
    New_head = NULL;
    Old_head = L->Next;

    while ( Old_head )  {
        Temp = Old_head->Next;
        Old_head->Next = New_head; /*(6分)*/
        New_head = Old_head;  
        Old_head = Temp; 
    }
    L->Next = New_head; /*(6分)*/
    return L;
}

5-2
下列代码的功能是将小顶堆H中指定位置P上的元素的整数键值下调D个单位，然后继续将H调整为小顶堆。

void DecreaseKey( int P, int D, PriorityQueue H )
{
   int i, key;
   key = H->Elements[P] - D;
   for ( i = P /*(6分)*/; H->Elements[i/2] > key; i/=2 )
   		H->Elements[i] = H->Elements[i/2]; /*(6分)*/
   H->Elements[i] = key;
}