Quiz 4 测验 4

Question 1 (1 mark) 问题1（1分）

Consider the following interface for a List ADT:
考虑列表 ADT 的以下接口：

#ifndef LIST_H
#define LIST_H

#include <stdbool.h>

typedef struct list *List;

// Creates a new empty list
List ListNew(void);

// Frees memory allocated to the list
void ListFree(List l);

// Inserts an item at the end of the list
void ListInsertEnd(List l, int item);

// Removes an item from the end of the list and returns it
int ListRemoveEnd(List l);

// Returns the size of the list (i.e., the number of items in the list)
int ListSize(List l);

// Returns true if the list is empty, and false otherwise
bool ListIsEmpty(List l);

#endif

Assume that the ADT implementation is correct, and contains the following struct definitions:
假设 ADT 实现是正确的，并且包含以下结构定义：

struct list {
    struct node *head;
    struct node *tail;
    int size;
};

struct node {
    int val;
    struct node *next;
};

Suppose a user of the List ADT created an instance of the list like this:
假设 List ADT 的用户创建了一个列表实例，如下所示：

List myList = ListNew(); 

After performing some operations on the list, the user would like to print a message if the list is empty. Which of the following is a correct way to achieve this? Select all that apply.
在列表上执行一些操作后，如果列表为空，用户希望打印一条消息。以下哪项是实现此目标的正确方法？选择所有适用的选项。

if (myList == ListNew()) {
    printf("The list is empty!\n");
}

if (ListSize(myList) == 0) {
    printf("The list is empty!\n");
}

if (ListIsEmpty(myList) == 0) {
    printf("The list is empty!\n");
}

if (myList->size == 0) {
    printf("The list is empty!\n");
}

if (myList->tail == NULL) {
    printf("The list is empty!\n");
}

Question 2 (1 mark) 问题2（1分）

Consider the following stack operations:
考虑以下堆栈操作：

push 9
push 7
pop
push 2
push 8
push 4
push 3
pop
pop
push 6
pop
pop
push 1
push 5

Starting with an empty stack, perform the operations in the given order and list the items in the stack in order from bottom to top. Enter your answer as a series of space-separated integers. For example, if you think the stack contains the elements 3, 1 and 4, with 3 at the bottom and 4 at the top, then you should enter
从一个空栈开始，按照给定的顺序执行操作，并按照从下到上的顺序列出栈中的项。以一系列空格分隔的整数形式输入您的答案。例如，如果您认为堆栈包含元素 3、1 和 4，其中 3 在底部，4 在顶部，那么您应该输入

3 1 4

Question 3 (1 mark) 第三题（1分）

Consider the following queue operations:
考虑以下队列操作：

enqueue 1
enqueue 6
enqueue 9
dequeue
enqueue 5
enqueue 2
dequeue
dequeue
enqueue 7
enqueue 8
enqueue 4
dequeue
enqueue 3

Starting with an empty queue, perform the operations in the given order and list the items in the queue in order from front to back. Enter your answer as a series of space-separated integers. For example, if you think the queue contains the elements 3, 1 and 4, with 3 at the front and 4 at the back, then you should enter
从一个空队列开始，按照给定的顺序执行操作，并按照从前到后的顺序列出队列中的项目。以一系列空格分隔的整数形式输入您的答案。例如，如果您认为队列包含元素 3、1 和 4，其中 3 在前面，4 在后面，那么您应该输入

3 1 4 

Question 4 (1 mark) 第4题（1分）

Which of the following is the result of inserting these values in the order given into an initially empty binary search tree?
以下哪项是将这些值按照给定顺序插入到最初为空的二叉搜索树的结果？

4  5  7  3  6  1  2

Question 5 (1 mark) 第5题（1分）

Which of the following sequences, if inserted into an initially empty binary search tree, would result in the tree having the maximum possible height? Select all that apply.
如果将以下哪个序列插入到最初为空的二叉搜索树中，会导致树具有最大可能的高度？选择所有适用的选项。

Question 6 (1 mark) 第6题（1分）

What is the post-order traversal of this tree?
这棵树的后序遍历是什么？

    5
   / \
  2   7
 / \   \
1   4   8

Enter your answer as a sequence of space-separated integers. For example, if you think the answer is [1, 2, 3] then you should enter
以空格分隔的整数序列形式输入您的答案。例如，如果您认为答案是 [1, 2, 3] 那么您应该输入

1 2 3

Do not use commas or square brackets.
不要使用逗号或方括号。

Question 7 (1 mark) 第7题（1分）

Consider the following sequence of numbers:
考虑以下数字序列：

3  1  5  4  6

Which of the following statements is true? Select all that apply.
以下哪项陈述是正确的？选择所有适用的选项。

3  1  5  4  6

3  1  5  4  6

3  1  5  4  6

3  1  5  4  6

Question 8 (1 mark) 第8题（1分）

Which of the following BST operations are O(h) in the worst case, where h is the height of the BST? Select all that apply.
以下哪些 BST 操作在最坏情况下的复杂度为 O(h)，其中 h 是 BST 的高度？选择所有适用的选项。