Stacks and queues：練習問題

A Binary Search Tree (BST) is built by inserting values in the following order: 50, 30, 70, 20, 40, 60, 80. If the root node (50) is deleted and replaced by its in-order successor, which value will be the new root of the tree?

In the context of Abstract Data Structures, what is the primary role of a hash function when implemented in a hash table?

Consider a Circular Linked List where a single pointer, last, points to the final node in the list. What is the Big O time complexity for inserting a new node at the beginning (head) of the list?

Outline how a stack data structure is used by the system to manage sub-program calls and handle returns during program execution.

A singly linked list stores nodes where each node contains data and a pointer to the next node. A developer uses an external pointer, start, pointing to the first node.
Describe the algorithm steps required to delete a node that contains a specific target value from the middle of the linked list without causing memory disconnection.

A customer service system manages incoming support tickets using abstract data structures. Each ticket has a unique integer ID, and the system dynamically processes them using a single linked list and a binary search tree (BST).

(a) State one advantage and one disadvantage of using a dynamic data structure, such as a linked list, compared to a static data structure like an array for storing support tickets. [2]

(b) The following sequence of ticket IDs arrives and is inserted in this order into an initially empty Binary Search Tree (BST):
\(45, 23, 67, 12, 34, 56, 89, 78\)

(i) State the values visited during a pre-order traversal of the resulting tree. [2]
(ii) State the values visited during an in-order traversal of the resulting tree. [1]

(c) The linked list implementation uses nodes, where each node contains data and a reference next. The pointer head points to the first node in the list. The recursive sub-program countPriority(Node current, int threshold) counts the number of tickets whose ID is greater than threshold.

Construct the recursive algorithm in pseudocode for countPriority(Node current, int threshold). [3]