京都大学 情報学研究科 知能情報学専攻 2022年2月実施 基礎科目 F2-2

标签：

• Kyoto-University
• Linked-List
• Partitioning
• Algorithm-Complexity

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

A linked list is a chain of nodes. Each node contains a value and a reference to the next node.

Q.1

Discuss two advantages of linked lists over arrays regarding computational efficiency.

Q.2

Given a linked list $L$ and a threshold $t$, reorder $L$ so that all nodes with values greater than $t$ precede all nodes with values less than or equal to $t$, while preserving the relative order of the nodes as much as possible. This operation is called partition.

For

L1: 5 -> 4 -> 2 -> 1 -> 8 -> 4 -> 3 -> null

and $t_1=4$, show $L_1$ after partition.

Q.3

A node has two fields:

• value: an integer;
• next: a reference to the next node, or null for the last node.

The type Node is a reference to such a node. The predefined function newNode() returns a node whose value and next are initialized to $0$ and null, respectively. The symbol := denotes reference assignment.

Fill the blanks (a)--(g) in Algorithm 1.

Algorithm 1
Input:  The head node head of a linked list and an integer threshold t.
Output: The head node after partition.

1:  before.head := newNode(); after.head := newNode();
2:  before := before.head; after := after.head;
3:  while head is not null do
4:      if head.value > t then
5:          before.next := (a); before := (b);
6:      else
7:          after.next := (c); after := (d);
8:      end if
9:      head := head.next;
10: end while
11: after.next := (e); before.next := (f);
12: Output (g).

Q.4

Let $n$ be the number of nodes in the input list. Give the time complexity of Algorithm 1 with reasons.

题目描述

链表由结点串联而成，每个结点保存一个值及下一结点的引用。

1. 从计算效率角度讨论链表相对于数组的两个优点。
2. partition 操作把值大于阈值 $t$ 的结点移到值不大于 $t$ 的结点之前， 并尽量保持原相对顺序。对 5 -> 4 -> 2 -> 1 -> 8 -> 4 -> 3 -> null 和 $t=4$，画出结果。
3. 补全使用两个哑元头结点稳定完成 partition 的算法空栏 (a)--(g)。
4. 设输入链表有 $n$ 个结点，求算法的时间复杂度并说明理由。

Kai

Q.1

Two advantages are:

1. Once the relevant node or its predecessor is known, insertion and deletion require only a constant number of reference changes, hence $O(1)$ time. An array generally requires shifting $O(n)$ elements.
2. A linked list can grow or shrink one node at a time without allocating a larger contiguous block and copying all existing elements. Array resizing may require an $O(n)$ reallocation and copy.

Q.2

Preserving the original order within each of the two groups gives

5 -> 8 -> 4 -> 2 -> 1 -> 4 -> 3 -> null

Q.3

The blanks are

$$\begin{array}{c|l} \text{blank}&\text{expression}\\ \hline (a)&\texttt{head}\\ (b)&\texttt{before.next}\\ (c)&\texttt{head}\\ (d)&\texttt{after.next}\\ (e)&\texttt{null}\\ (f)&\texttt{after.head.next}\\ (g)&\texttt{before.head.next} \end{array}$$

Thus each input node is appended to the tail of the appropriate stable sublist. After the loop, after.next := null terminates the second sublist and before.next := after.head.next concatenates the two sublists.

Q.4

The loop visits each of the $n$ input nodes exactly once and performs a constant number of reference operations per node. The remaining operations are constant-time, so

$$\boxed{\Theta(n)}.$$

The algorithm uses only two dummy nodes and a constant number of references, so its auxiliary space is $\Theta(1)$.