【笔试题】【day21】

目录

第一题（单链表出队）

第二题（二叉树排序树的插入和删除顺序对于结点的影响）

第三题（从任意结点出发到根的路径所经过的结点序列按其关键字有序）

第四题（堆的构建）

---

第一题（单链表出队）

用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）

A 仅修改队头指针
B 仅修改队尾指针
C 队头、队尾指针都可能要修改
D 队头、队尾指针都要修改

如果我们队中有元素，由于我们这里是单链表，所以我们的直接将head结点修改一下就可以了

 但是如果我们的链表已经只有一个元素了，我们的头尾指针都指向这个元素，然后出队一下，我们的头尾指针就都需要修改成nullpter，所以我们的头尾指针可能都有修改

C

C

第二题（二叉树排序树的插入和删除顺序对于结点的影响）

在任意一棵非空二叉排序树T1中， 删除某结点v之后形成二叉排序树 T2，再将v 插入T2形成二叉排序树T3。
下列关于T1与T3的叙述中，正确的是（ ）。
I．若 v 是 T1的叶结点，则 T1 与 T3 不同
II． 若 v 是 T1的叶结点，则 T1与 T3相同
III．若 v 不是 T1 的叶结点，则 T1 与 T3 不同
IV．若v 不是 T1 的叶结点，则 T1 与 T3 相同

A 仅 I、 III
B 仅 I、 IV
C 仅 II、 III
D 仅 II、 IV

如果是叶子节点的话，删除掉这个叶子结点再插入的位置是相同的，二正确

 如果不是叶子节点的位置的话，删除，然后重新插入的位置和我们原来的位置式不相同的，因为我们新插入的结点的位置一定是叶子结点的位置

 

C

第三题（从任意结点出发到根的路径所经过的结点序列按其关键字有序）

下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（） 

A 二叉排序树
B 哈夫曼树
C AVL树
D 堆

下面这棵二叉排序树就是无序的

 

下面这棵哈夫曼树当前状况是有序的

但是如果我们将哪些我们认为插入的结点不算，那么哈夫曼树就是无序的

 

 AVL树，下面这两条路径就是无序的

 堆在构造的时候，无论是小堆还是大堆都会构成有序的顺序。

因为根节点在进行构造树的时候，我们就是按照根节点比子树都要大，或者比子树都要小

 

D

第四题（堆的构建）

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

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

初始是一个大根堆

                7

        6                3

5             4        1        2

因为从小到大排序，我们需要建立大堆，7已经是我们最大的元素了，我们不参与我们下一次的调整，将7和最后一个元素交换位置

                2

        6                     3

5             4        1         7

调整

                6

        5                   3

2             4        1          7

此时除去7之外，我们的堆又满足了我们的顺序，所以我们的第一轮排序结束之后的结果就是

6->5->3->2->4->1->7

也就是我们的C选项

C