【2020-MOOC-浙江大学-陈越、何钦铭-数据结构】春期中考试（附每一个题目的详细解析）

电玩女神 2023-07-20 13:46 9阅读 0赞

### 文章目录 ###

*  〇、前言
 *  一、判断题
 *  二、选择题
 *  三、程序填空题
 *  总结

# 〇、前言 #

这周开始了【MOOC-浙江大学-陈越、何钦铭-数据结构】的期中考试，感觉有点难，可能是我才学了一个月不到的原因？？？  
![在这里插入图片描述][20200403091207452.jpg_pic_center]

# 一、判断题 #

1-1、用 **邻接表** 法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。  
![在这里插入图片描述][20200403091834601.png]  
作者: DS课程组  
单位: 浙江大学

> 邻接矩阵的空间复杂度为O( n 2 n^2 n2)，与边的个数无关。  
> 邻接表的空间复杂度为O( n + e n+e n\+e)，与图中的结点个数和边的个数都有关。

--------------------

1-2、在一棵由包含4、5、6等等一系列整数结点构成的 **二叉搜索树** 中，如果结点4和6在树的同一层，那么可以断定结点5一定是结点4和6的父亲结点。  
![在这里插入图片描述][20200403091912908.png]  
作者: DS课程组  
单位: 浙江大学

> 5是6的左子树节点就是一个反例。

--------------------

1-3、如果无向图 `G` 必须进行两次 **广度优先搜索** 才能访问其所有顶点，则 `G` 一定有2个连通分量。  
![在这里插入图片描述][20200403091940917.png]  
作者: DS课程组  
单位: 浙江大学

> 连通分量：无向图的极大连通子图。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]  
> 相似但是错误的说法：如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。

--------------------

1-4、若一棵 **平衡二叉树** 的所有非叶结点的 **平衡因子** 都是0，则其必为完美二叉树。  
![在这里插入图片描述][20200403091940917.png]  
作者: 徐镜春  
单位: 浙江大学

> 平衡因子是0，代表着左右子树的高度一样。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]

--------------------

1-5、若一个结点是某二叉树的 **中序遍历序列** 的最后一个结点，则它必是该树的 **前序遍历序列** 中的最后一个结点。  
![在这里插入图片描述][20200403091912908.png]  
作者: DS课程组  
单位: 浙江大学

> 假设：  
> A  
> /  
> B  
> 中序是左一根一右顺序，前序是根一左一右顺序：
> 
>  *  前序遍历序列为A-B；
>  *  中序遍历序列为B-A；
> 
> 那么结点A是中序遍历序列的最后一个结点，但是它并不是前序遍历序列中的最后一个结点。  
> 如果【若一个结点】改成【若一个叶子结点】，那么命题为真。

--------------------

1-6、一棵有124个结点的 **完全二叉树**，其叶结点个数是确定的。  
![在这里插入图片描述][20200403091940917.png]  
作者: DS课程组  
单位: 浙江大学

> ![在这里插入图片描述][20200403112517860.png]  
> 124上限是128（ 2 7 2^7 27），下限是64（ 2 6 2^6 26），中间这些都可以是叶子结点数。  
> 补充：  
> 假设 `n0` 是度为0的节点总数（即叶子结点数），`n1` 是度为1的节点总数，`n2` 是度为2的节点总数。因为 `n= n0+n1+n2`（其中n为完全二叉树的节点总数），又因为一个度为2的节点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他节点都有父结点，得到 `n= 1+n1+2*n2`；两式把 `n2` 消去得：`n= 2*n0+n1-1`，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到 `n0=n/2` 或 `n0=(n+1)/2`。

--------------------

1-7、**算法** 可以没有输入，但是必须有输出。  
![在这里插入图片描述][20200403091940917.png]  
作者: 李廷元  
单位: 中国民用航空飞行学院

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]

--------------------

1-8、通过对 **堆栈** S操作：`Push(S,1)`, `Push(S,2)`, `Pop(S)`, `Push(S,3)`, `Pop(S)`, `Pop(S)`。输出的序列为：123。  
![在这里插入图片描述][20200403091912908.png]  
作者: DS课程组  
单位: 浙江大学

<table> 
 <thead> 
  <tr> 
   <th>堆栈内的元素</th> 
   <th>输出的元素</th> 
   <th>执行的操作</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>-</td> 
   <td>Push(S,1)</td> 
  </tr> 
  <tr> 
   <td>2，1</td> 
   <td>-</td> 
   <td>Push(S,2)</td> 
  </tr> 
  <tr> 
   <td>2 ，1</td> 
   <td>2</td> 
   <td>Pop(S)</td> 
  </tr> 
  <tr> 
   <td>3，1</td> 
   <td>2</td> 
   <td>Push(S,3)</td> 
  </tr> 
  <tr> 
   <td>3 ，1</td> 
   <td>2，3</td> 
   <td>Pop(S)</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>2，3，1</td> 
   <td>Pop(S)</td> 
  </tr> 
 </tbody> 
</table>

--------------------

1-9、在用数组表示的 **循环队列** 中，`front` 值一定小于等于 `rear` 值。  
![在这里插入图片描述][20200403091912908.png]  
作者: DS课程组  
单位: 浙江大学

> 循环队列！！！

--------------------

1-10、在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为 `O(1)` 和 `O(N)`。  
![在这里插入图片描述][20200403091912908.png]  
作者: DS课程组  
单位: 浙江大学

> 都是O(N)。

--------------------

# 二、选择题 #

2-1、下列哪个函数是O(N)的？  
![在这里插入图片描述][20200403092611314.png]  
**答案：A**  
作者: DS课程组  
单位: 浙江大学

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 4]

--------------------

2-2、先序遍历图示 **二叉树** 的结果为  
![在这里插入图片描述][20200403092640932.png]  
![在这里插入图片描述][20200403092655233.png]  
**答案：B**  
作者: DS课程组  
单位: 浙江大学

> 先序遍历是根–左--右。

--------------------

2-3、若某图的 **深度优先搜索** 序列是\{V1, V4, V0, V3, V2\}，则下列哪个图不可能对应该序列？  
![在这里插入图片描述][20200403092727521.png]  
**答案：C**  
作者: 陈越  
单位: 浙江大学

> C应该是1，4，3，0，2。

--------------------

2-4、已知一棵 **完全二叉树** 的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是：  
![在这里插入图片描述][20200403092749924.png]  
**答案：C**  
作者: DS课程组  
单位: 浙江大学

> 完全二叉树比起满二叉树，只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。  
> 第6层有叶结点，则完全二叉树的高度可能为6或7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2=16个叶结点，故完全二叉树的结点个数最多为  2 7 − 1 − 16 = 111 2^7-1-16=111 27−1−16=111 个结点。

--------------------

2-5、已知表头元素为c的 **单链表** 在内存中的存储状态如下表所示：  
![在这里插入图片描述][20200403092803242.png]  
现将 `f` 存放于 `1014H` 处，并插入到单链表中，若 `f` 在逻辑上位于 `a` 和 `e` 之间，则 `a`、`e`、`f` 的“链接地址”依次是：  
![在这里插入图片描述][2020040309284633.png]  
**答案：D**  
作者: DS课程组  
单位: 浙江大学

> `f` 在逻辑上位于 `a` 和 `e` 之间，则 `a` 的链接地址为1014，即 `f` 的地址，`f` 的链接地址为1010，即 `e` 的地址，其他的链接地址则不变。

--------------------

2-6、对 **最小堆（小顶堆）** \{1,3,2,12,6,4,8,15,14,9,7,5,11,13,10\} 进行三次删除最小元的操作后，结果序列为：  
![在这里插入图片描述][20200403092911843.png]  
**答案：C**  
作者: DS课程组  
单位: 浙江大学

> 硬算。

--------------------

2-7、在一个不带头结点的非空 **链式队列** 中,假设 `f` 和 `r` 分别为队头和队尾指针,则插入 `s` 所指的结点运算是( )。  
![在这里插入图片描述][20200403092932202.png]  
**答案：B**  
单位: 浙江大学城市学院

> 队列尾部插入元素。

--------------------

2-8、表达式 `a*(b+c)-d` 的 **后缀表达式** 是：  
![在这里插入图片描述][20200403093019473.png]  
**答案：A**  
作者: DS课程组  
单位: 浙江大学

> 后缀表达式。

--------------------

2-9、一棵 **二叉树** 中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。  
![在这里插入图片描述][20200403092955967.png]  
**答案：B**  
作者: 严冰  
单位: 浙江大学城市学院

> ![在这里插入图片描述][20200403144754207.png]

--------------------

2-10、在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是\{ 1, -4, 1, 1, -3, 4, 4, 8, -2 \}（注：−n表示树根且对应集合大小为n），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？  
![在这里插入图片描述][20200403093048303.png]  
**答案：B**  
作者: DS课程组  
单位: 浙江大学

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 5]

--------------------

2-11、设一段文本中包含字符\{a, b, c, d, e\}，其出现频率相应为\{3, 2, 5, 1, 1\}。则经过哈夫曼编码后，文本所占字节数为：  
![在这里插入图片描述][20200403093109616.png]  
**答案：C**  
作者: DS课程组  
单位: 浙江大学

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 6]

--------------------

2-12、下列函数

int func ( int n )
    {    int i = 0, sum = 0;
        while ( sum < n )  sum += ++i;
        return i;
    }

的时间复杂度是：  
![在这里插入图片描述][20200403093145394.png]  
**答案：B**  
作者: 考研试卷  
单位: 浙江大学

> 进行t次循环后，`sum = (k+1)*k/2 < n`，左侧约等于 `k*k`，则 `t` 等于 `sqrt(n)`，时间复杂度为O( n ( 1 / 2 ) n^\{(1/2)\} n(1/2))。

--------------------

# 三、程序填空题 #

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;	//需要填写的语句
            New_head = Old_head;  
            Old_head = Temp; 
        }
    	L->Next=New_head;				//需要填写的语句
        return L;
    }

> 以前我们用漫画讲过，可以自行查看，[【手绘漫画】面试必考之图解逆转单链表/单链表逆序][Link 1]。

--------------------

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

void IncreaseKey( int P, int D, PriorityQueue H )
    { 
       int i, key;
       key = H->Elements[P] + D;
       for ( i = P;								//需要填写的语句
       		H->Elements[i/2] < key;
       		i/=2 )  
    		H->Elements[i] = H->Elements[i/2];	//需要填写的语句
    	H->Elements[i] = key;
    }

> 与插入类似。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 7]

# 总结 #

简单总结下，光看课和课件是不够的的，还是建议看看课程的书。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]  
我放在公众号里了，欢迎自行去取！

回复【浙江大学】即可获得，这可是我花了积分在CSDN上下的啊！！！

![在这里插入图片描述][2020033119171520.png]

> **如果有幸帮到你，请帮我点个【赞】，给个【关注】！如果能顺带【评论】给个鼓励，我将不胜感激。**

***如果想要更多的资源，欢迎关注 @我是管小亮，文字强迫症MAX~***

***回复【数据结构】即可获取我为你准备的大礼。***

***想看更多文（段）章（子），欢迎关注微信公众号「程序员管小亮」~***

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 1]

[20200403091207452.jpg_pic_center]: /images/20230528/15fd15ed95a946f0ac170491fc5b642e.png
[20200403091834601.png]: /images/20230528/9437316785e94bbfa058c12e802d4f7d.png
[20200403091912908.png]: /images/20230528/0c3e147308cf4a02ac7a7d20563228c5.png
[20200403091940917.png]: /images/20230528/a9e2b04d1eef422c836d1733369f37a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: /images/20230528/f0cc026659eb4769b04fb57baf41cd94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: /images/20230528/0a577bd6ca3e4624bb7c72d38818801a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]: /images/20230528/4d7ec914c0724003b16ecde0cfc7f8d5.png
[20200403112517860.png]: /images/20230528/db1b2ef410034d49a185f43bf3fdb3e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]: /images/20230528/741c4860c5aa419bb207eead2b9c29c7.png
[20200403092611314.png]: /images/20230528/0048e3e668534dad8886c08497512fcf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 4]: /images/20230528/9aa2898320aa4da596d67d5a0b49fc9e.png
[20200403092640932.png]: /images/20230528/9fb12d851aa5429f8b77fbef53aba20c.png
[20200403092655233.png]: /images/20230528/78f09de1b1d547c5aecdece57b6f2f3b.png
[20200403092727521.png]: /images/20230528/e4a9b62190aa46d38da311fd56e1751b.png
[20200403092749924.png]: /images/20230528/5d3028fb310c4d94a5524770b66ba874.png
[20200403092803242.png]: /images/20230528/4f4bb494794f406e9fdd9b54b99ee241.png
[2020040309284633.png]: /images/20230528/26030bde2c3c460ca31f3233ef4e403c.png
[20200403092911843.png]: /images/20230528/b06aec917ac84ec0a8b3e2fd695b2735.png
[20200403092932202.png]: /images/20230528/c9b5b0b900a546419f8f0ac0a351f2e6.png
[20200403093019473.png]: /images/20230528/ce74970de3e84236af1664e2e81964d1.png
[20200403092955967.png]: /images/20230528/d7efbf16d6ac4d559b81fd05cd5c8ba3.png
[20200403144754207.png]: /images/20230528/e1c0cc75ad1345ed813ee1cb89a18250.png
[20200403093048303.png]: /images/20230528/6453c48fe36b493880620901a8568d0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 5]: /images/20230528/e895227f15534efda3d01194c4b4f199.png
[20200403093109616.png]: /images/20230528/643730ad3f314f0dbe56ad30691df3e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 6]: /images/20230528/c143c6dc566f4880bd1261fae8ee18e7.png
[20200403093145394.png]: /images/20230528/46a45ba1497e4d99b198bf590b573a79.png
[Link 1]: https://blog.csdn.net/TeFuirnever/article/details/105157764
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 7]: /images/20230528/c6c76c9f5fe14b00a22e72d155b1a887.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/93367e39e21f4574b672d8cb0a885e4f.png
[2020033119171520.png]: /images/20230528/cbd89f18b4914d8fa93ef97b690fa29c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/ccac9be1591946b1a336dcf5198b65d9.png