堆相关笔试题

心已赠人 2022-06-08 01:36 299阅读 0赞

> 牛客网 专项练习题

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

### (101,88,46,70,34,39,45,58,66,10)是堆() ###

A. 对
    B. 错

> 正确答案: A
> 
> 最小堆：直接父节点比两个子节点都小。  
> 最大堆：直接父节点比两个子节点都大。  
> 本题写下来，是最大堆。

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

### 下列数据结构不是多型数据类型的是（） ###

A. 堆
    B. 栈
    C. 字符串
    D. 有向图

> 正确答案: C
> 
> 多型就是数据元素的类型不确定，字符串的每个元素始终都是字符类型，而不会是别的类型，栈、堆、有向图的数据元素的元素类型不确定

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

### 下列哪一个关键码序列不符合堆的定义？ ###

A. A、C、D、G、H、M、P、Q、R、X
    B. A、C、M、D、H、P、X 、G、0、R
    C. A、D、P、R、C、Q、X 、M、H、G
    D. A、D、C、M、P、G、H、X 、R、Q

> 正确答案: C

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

### 下面有关c++静态数据成员，说法正确的是？ ###

A. 不能在类内初始化
    B. 不能被类的对象调用
    C. 不能受private修饰符的作用
    D. 可以直接用类名调用

> 正确答案: D
> 
> 来看A：  
> 通常静态数据成员在类声明中声明,在包含类方法的文件中初始化.  
> 初始化时使用作用域操作符来指出静态成员所属的类.  
> 但如果静态成员是整型或是枚举型const,则可以在类声明中初始化!!
> 
> 如果改成有的静态数据成员是可以直接在类中初始化就对了

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

### 在堆排序算法中我们用一个数组A来模拟二叉树T，如果该A\[0\]存放的是T的根节点，那么A0”>K的父亲节点是 ###

A. (K-1)/2
    B. K/2
    C. (K+1)/2
    D. 都不对

> 正确答案: A
> 
> 当数组从0开始时，下标为k的结点的父结点下标为(k-1)/2；  
> 当数组从1开始时，下标为k的结点的父结点下标为k/2；

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

### 堆是满二叉树() ###

A. 对
    B. 错

> 正确答案: B
> 
> 堆是完全二叉树，但不一定是满二叉树

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

### 有 1000 个无序的整数，希望使用最快的方式找出前 50 个最大的，最佳的选择是（ ） ###

A. 冒泡排序
    B. 基数排序
    C. 堆排序
    D. 快速排序

> 正确答案: C
> 
> 【C 】堆排序最优  
> 1、快速排序：在最理想的情况下，即划分可以使得每次分到n/2 的两个序列，复杂度为o（nlogn）。  
> 2、堆排序：无论什么情况都是o（nlogn），当然还有建堆的时间o（n），所以为n+nlogn，但是，本题只是要前五十个，所以堆排序只需要执行50次就够了：n+50logn。  
> 3、本题的条件是1000个无序整数，1000+50log1000<1000log1000，所以自然是堆排序最好。  
> p.s.：堆排序只需要一个n大小的二叉树就行了，快速排序除了n大小的数组，每次递归最少还得有logn的栈，所以堆排序的空间复杂度也优于快速排序。

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

### 最小堆\[0,3,2,5,7,4,6,8\],在删除堆顶元素0之后，其结果是（） ###

A. [3，2，5，7，4，6，8]
    B. [2，3，5，7，4，6，8]
    C. [2，3，4，5，7，8，6]
    D. [2，3，4，5，6，7，8]

> 正确答案: C
> 
> 答案：C  
> 根据堆的删除规则，删除操作只能在堆顶进行，也就是删除0元素。  
> 然后让最后一个节点放在堆顶，做向下调整工作，让剩下的数组依然满足最小堆。  
> 删除0后用8填充0的位置，为\[8,3,2,5,7,4,6\]  
> 然后8和其子节点3,2比较，结果2最小，将2和8交换，为：\[2,3,8,5,7,4,6\]  
> 然后8的下标为2，其两个孩子节点下标分别为2 \* 2+1=5,2 \* 2+2=6  
> 也就是4和6两个元素，经比较，4最小，将8与4交换，为\[2,3,4,5,7,8,6\]  
> 这时候8已经没有孩子节点了，调整完成

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

### 在用堆排序算法排序时,如果要进行增序排序,则需要采用”大根堆”() ###

A. 对
    B. 错

> 正确答案: A
> 
> 选A。  
> 因为大根堆每次生成的根都会跟最右侧没有排序的叶子节点进行交换，从而使得越大的元素越放在后面。这个特性使用数组的结构能够很清晰的表现出来。最终得到了升序排列。  
> 如果是小根堆，则每次拿到最小的跟最右侧未排过序的叶子节点进行交换，最终得到的序列是递减的。

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

### 将整数数组（ 7-6-3-5-4-1-2 ）按照堆排序的方式进行升序排列，请问在第一轮排序结束之后，数组的顺序是（） ###

A. 1-2-3-4-5-6-7
    B. 2-6-3-5-4-1-7
    C. 6-5-3-2-4-1-7
    D. 5-4-3-2-1-6-7

> 正确答案: C
> 
> 初始顺序为：7-6-3-5-4-1-2，将初始顺序调整为最大堆，发现顺序没有变，7是最大值。  
> 这时，把最大值7与堆中的最后一个数2进行调换位置，就不把最后一位算在内，将前后的6个数字调整为最大堆：6-5-3-2-4-1-7.
> 
> ![这里写图片描述][SouthEast]

[SouthEast]: /images/20220608/30f6373c9d9145bab19957745588bab5.png