数据结构+算法——错题总结

梦里梦外; 2022-12-19 13:22 108阅读 0赞

### 文章目录 ###

*   *  树
     *  排序

## 树 ##

叶子节点数=度为2的节点数+1  
总叶子节点数=叶子节点数+度为1的节点数+度为2的节点数

## 排序 ##

**栗子：**

> 一组记录的排序码为（46，79，56，38，40，84），一趟排序的结果为（40，38，46，56，79，84），则采用的是（）排序算法。

*  A选项起泡算法：相邻元素两两比较，一个元素大于右侧相邻元素交换位置，否则位置不变。 一趟排序为：46，56，38，40，79，84
 *  B选项直接插入：每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。  
    一趟排序为：38，40，46，79，56，84

> 找到一个最小的放最前面，其他不变

*  C选项快速：挑选一个基准元素，大于基准元素的放在其右边，小于基准元素的放在其左边，从而拆分为两部分，以此类推直到不可拆分为止。  
    以源数据第一个元素46为基准，采用双边循环法设置left和right两个指针指向数组最左和最右两端，从右指针开始，如果大于或等于基准元素则指针向左移动，如果小于基准元素则停止。转向left指针向右移动如果小于或等于基准元素则继续向右移动，如果大于基准元素则停止。交换两指针元素后，右指针继续上述操作比较，直到最后把基准元素和两指针重复元素交换位置。第一趟排序结束得出如下排序，所以C正确。  
    一趟排序为：40，38，46，56，79，84
 *  D选项2-路归并：将一个数组分成两个数组，分别对两个数组进行排序，循环第一步，直到划分出来的“小数组”只包含一个元素，只有一个元素的数组默认为已经排好序  
    一趟排序为：46，56，79合并；38，40，84合并  
    **栗子：**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center]  
    p^.llink 表示 p 的前驱结点，p^.rlink表示 p 的后继结点。删除 p 所指结点时须将 p 的前驱结点的rlink指向 p 的后继结点，将 p 的后继结点的 llink 指向 p 的前驱结点。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6e2d9f9f79c24265b24f592ead072afe.png