Applied Information Technology Engineer Exam, Subject A — Part 5: Data Structures, Searching, and Sorting

AP Subject A · Installment 5 · An independent study resource for the 2026 exam and Syllabus Ver.7.2. It is not affiliated with IPA and does not guarantee a pass. Open the series hub

Revised: 2026-10-20 Scope: the 2026 exam, based on the IPA Applied Information Technology Engineer Examination syllabus Ver.7.2 Note: Before the exam, always check the official IPA website for the current syllabus and exam information. This article is a study aid and does not guarantee a pass. It has not been reviewed or endorsed by IPA.

Learning objectives
Terminology (Korean ↔ Japanese ↔ English)
Reading complexity, and this article’s cost assumptions
Choosing a data structure: criteria and trade-offs
Searching: linear search and binary search
Sorting: algorithm characteristics and comparison table
Worked examples (four or more)
Four original practice questions
Complexity quick sheet
Common traps
Final self-check
Review suggestion (day 1 / 3 / 7)
Syllabus mapping
Sources and references
Scope boundary and next installment

1. Learning objectives

After this installment you should be able to:

Explain the characteristics of arrays, linked lists, stacks, queues, trees, and heaps, and choose a suitable structure for a given situation with a justification.
Trace stack (LIFO) and queue (FIFO) state changes accurately, step by step.
State the preconditions of binary search (sorted + random access) and count comparisons under a stated convention.
State the best/average/worst time complexity, auxiliary space, stability, and in-place property of the main sorting algorithms, together with their conditions.
Distinguish Big-O as “order of growth with input size” from “elapsed seconds.”

2. Terminology (Korean ↔ Japanese ↔ English)

Korean	Japanese	English
배열	配列	array
연결 리스트	連結リスト（リンク付リスト、線形リスト）	linked list
노드	ノード（節、セル）	node
포인터 / 링크	ポインタ / リンク	pointer / link
스택	スタック	stack
큐	キュー（待ち行列）	queue
트리	木（木構造）	tree
루트 / 리프 / 간선	根 / 葉 / 枝	root / leaf / edge
이진 탐색 트리	2分探索木	binary search tree (BST)
균형 트리	バランス木（平衡木）	balanced tree
힙	ヒープ	heap
선형 탐색	線形探索（法）	linear search
이진 탐색	2分探索（法）	binary search
정렬	整列（ソート）	sorting
안정 정렬	安定なソート（安定ソート）	stable sort
제자리 정렬	インプレースなソート（その場での整列）	in-place sort
시간 복잡도	時間計算量	time complexity
공간 복잡도	領域計算量（空間計算量）	space complexity

Terminology note: The Japanese term 「内部ソート」 (internal sort) means sorting data held in main memory. It is a different concept from an in-place sort, which uses little or no extra memory.

3. Reading complexity, and this article’s cost assumptions

3.1 Big-O is an order of growth

Notations such as O(n), O(n²), and O(log n) describe how the amount of work grows as the input size n grows.
They do not mean elapsed seconds. Two O(n log n) algorithms can differ in real time because of constant factors, memory-access patterns, and hardware. For small n, an O(n²) algorithm can even be faster.

3.2 Best, average, worst, and auxiliary space

Best case: work on the most favorable input. Example: insertion sort on already-sorted input.
Average case: expected work under an assumed input distribution.
Worst case: work on the least favorable input. When we talk about a “guarantee,” we look at the worst case.
Auxiliary space: memory an algorithm uses in addition to the space holding the input itself. An “in-place sort” is one whose auxiliary space is O(1) (or a similarly small amount).

3.3 Cost assumptions in this article

Array: elements are laid out contiguously in memory, and any position can be accessed by index in O(1).
Linked list: each node holds a link to the next node (and to the previous one, if doubly linked); reaching the k-th node requires following links from the front.
One comparison, one swap, and following one link each take constant time.

4. Choosing a data structure: criteria and trade-offs

4.1 Array (配列)

Indexed access: O(1), because the address of A[i] can be computed directly.
Insertion/deletion in the middle: usually O(n). Inserting or removing at position k requires shifting the elements after it by one place.
Advantage: contiguous layout gives good cache locality, so sequential processing is often fast in practice.
Appending to a dynamic array: amortized O(1). When capacity runs out, a larger region is allocated and everything is copied (O(n)), so O(1) is not guaranteed on every append. It means the cost per append averages to O(1) over many appends.
Syllabus terms: multidimensional array, static array, dynamic array.

4.2 Linked list (連結リスト)

Positional access / search: O(n). Reaching the k-th node requires following links from the head.
Insertion/deletion: O(1) only when the target position (node) and the links to change are already known. If the position must first be found, that search is O(n).
- To delete a node from a singly linked list, you need its predecessor. In a doubly linked list, knowing the node itself is enough to fix both neighboring links and delete it in O(1).
Disadvantages: each node stores pointer overhead, and nodes are scattered in memory, so cache locality is weaker.
Syllabus terms: singly linked list, doubly linked list, circular list.

4.3 Stack and queue

	Stack (スタック)	Queue (キュー)
Principle	LIFO (last in, first out)	FIFO (first in, first out)
Insert	push	enqueue
Remove	pop (the most recently inserted)	dequeue (the earliest inserted)
Example uses	undo history, bracket matching, managing function calls	print-job queue, request buffer, breadth-first search (BFS)

4.4 Trees, binary search trees, balanced trees, heaps

Tree: a hierarchy. The top node is the root (根), a node with no children is a leaf (葉), and a connection between nodes is an edge (枝).
Binary search tree (BST): for every node, the ordering “keys in the left subtree < the node’s key < keys in the right subtree” is maintained (handling of duplicate keys varies by implementation).
- An ordinary BST can become skewed depending on insertion order. Example: inserting 1, 2, 3, 4, 5 in that order effectively produces a list, giving worst-case O(n) search.
- A balanced BST (such as an AVL tree) keeps its height at O(log n), so search, insertion, and deletion are O(log n). A B-tree is also a balanced multiway search tree.
Heap: a complete binary tree that maintains only a parent–child ordering, such as “parent ≥ child” (max-heap).
- Peek at the maximum: O(1); insert and remove-max: O(log n) → well suited to a priority queue.
- It is not a fully sorted sequence. Siblings and nodes on different branches have no defined order.
- It is therefore unsuitable for searching for an arbitrary key (generally O(n)).

4.5 One-line selection rules

Frequent indexed access → array
Frequent insertion/deletion at a position you already hold → (doubly) linked list
Process the most recent first → stack / process in arrival order → queue
Repeatedly process the highest-priority item → heap
Frequent search and update while keeping key order → balanced BST

5. Searching

5.1 Linear search (線形探索)

Compare elements one by one from the front. No sorting is required.
Time complexity: worst case O(n); average also O(n).
Works on a linked list as is.

5.2 Binary search (2分探索)

Two preconditions:
1. The search range is sorted.
2. The middle position can be accessed directly (random access) — O(1) access by index, as in an array.
Each comparison halves the range, giving O(log n).
A sorted linked list does not automatically give O(log n). To reach the middle node you must follow links, and the total movement is roughly n/2 + n/4 + …, which sums to O(n). Even if the number of comparisons is logarithmic, the access cost is O(n), so the advantage disappears.

5.3 Comparison-count convention in this article (examples and questions)

We fix the convention before counting anything exactly.

Linear search: comparing one element with the target counts as one comparison. Even for a sorted array, we count the basic version without early termination (“stop when a value larger than the target appears”).
Binary search: indices start at 0; initially low = 0, high = n − 1. The midpoint is mid = ⌊(low + high) / 2⌋ (rounded down). Comparing A[mid] with the target and deciding “equal / less / greater” counts as one comparison (one probe).
- If equal, stop; if A[mid] < target, set low = mid + 1; if A[mid] > target, set high = mid − 1. When low > high, stop with “not found.”
- Note: some textbooks count “equal?” and “less?” as two separate comparisons, so in an exam always follow the convention stated in the question.
Under this convention, the maximum number of probes for binary search on an array of size n is ⌊log₂ n⌋ + 1.

5.4 A short note on hash-table search

The same syllabus item also lists hash-table search and synonym (collision) handling as example terms. If the hash function spreads keys evenly and the load factor is kept low, search is close to O(1) on average, but if collisions concentrate in one place it can degrade to O(n) in the worst case. Collision-handling methods include chaining and open addressing. This installment goes no further than this.

6. Sorting

6.1 Key points of each algorithm

Bubble sort: repeat passes that compare and swap adjacent elements. Each pass moves the maximum of the remaining range to its end. Best case O(n) on already-sorted input only with a “stop if no swap occurred” flag (early exit). Average and worst O(n²). Stable, in-place.
Selection sort: find the minimum of the remaining range and swap it to the front. The number of comparisons is n(n−1)/2 regardless of input, so O(n²) in all cases. Because it swaps distant elements, it is generally unstable. In-place.
Insertion sort: insert the next key into its proper place in the sorted prefix. With the standard implementation on already-sorted or nearly sorted input, best case O(n). Average and worst O(n²). Stable, in-place.
Shell sort: an insertion-sort family method that performs insertion sorting among elements a gap apart, shrinking the gap until a final pass with gap 1. Its time complexity depends on the gap sequence and cannot be stated as one universal bound. Generally unstable.
Merge sort: repeatedly merge pairs of small sorted groups (runs) into larger ones. O(n log n) in all cases. Stable. A typical array implementation needs O(n) auxiliary space.
Quick sort: repeatedly partition around a pivot into a smaller side and a larger side. Average O(n log n), worst O(n²) (for example, always choosing the last element as pivot on already-sorted input). Generally unstable. Space depends on the implementation, the recursion stack, and the pivot strategy (partitioning itself can be done in place, but the call stack uses O(log n) on average and can reach O(n) in the worst case of a naive implementation).
Heap sort: build a max-heap in the array, then repeatedly swap the root (maximum) with the last element and restore the heap. O(n log n). In-place. Generally unstable.

6.2 Comparison table

Algorithm	Best	Average	Worst	Auxiliary space	Stability	In-place
Bubble (with early exit)	O(n)	O(n²)	O(n²)	O(1)	stable	yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	generally unstable	yes
Insertion (standard)	O(n)	O(n²)	O(n²)	O(1)	stable	yes
Shell	depends on gap sequence	depends on gap sequence	depends on gap sequence	O(1)	generally unstable	yes
Merge (array)	O(n log n)	O(n log n)	O(n log n)	O(n)	stable	no (typical implementation)
Quick	O(n log n)	O(n log n)	O(n²)	depends on implementation, stack, pivot strategy	generally unstable	partitioning can be in place
Heap	O(n log n)※	O(n log n)	O(n log n)	O(1)	generally unstable	yes

※ Assuming distinct keys. Bubble sort without an early-exit flag is O(n²) even in the best case.

6.3 What stability means

A sort is stable if elements with equal keys keep their original relative order after sorting. Example: sorting [2a, 2b, 1] (a and b mark the original order) with selection sort swaps the minimum 1 with the front element 2a, giving [1, 2b, 2a]. The order of 2a and 2b has been reversed, so selection sort is unstable on this input.

7. Worked examples

Example 1: Choosing a structure for each scenario

Scenario	Choice	Reason
Keep appending sensor readings and frequently read “the k-th value”	dynamic array	indexed access O(1), append amortized O(1)
“Undo” in an editor	stack	undo the most recent action first (LIFO)
Process print jobs in arrival order	queue	FIFO
Repeatedly treat the most urgent patient first, with new patients arriving at any time	heap (priority queue)	insert and remove-max O(log n)
Keep member IDs in order with frequent search/insert/delete, plus range queries	balanced BST	search/update O(log n); in-order traversal lists keys in order
The node under the cursor is already known, and insertion/deletion there is frequent	doubly linked list	node and links are known, so O(1)

Example 2: Stack and queue state transitions

In the same order: insert A and B, remove one, insert C and D, remove two. In each state, the left side is the “earlier inserted” side.

Stack (right end is the top)

Step	Operation	Removed	State
0	(start)	–	[ ]
1	push A	–	[A]
2	push B	–	[A, B]
3	pop	B	[A]
4	push C	–	[A, C]
5	push D	–	[A, C, D]
6	pop	D	[A, C]
7	pop	C	[A]

Removal order: B, D, C. Remaining: [A].

Queue (left end is the front)

Step	Operation	Removed	State
0	(start)	–	[ ]
1	enqueue A	–	[A]
2	enqueue B	–	[A, B]
3	dequeue	A	[B]
4	enqueue C	–	[B, C]
5	enqueue D	–	[B, C, D]
6	dequeue	B	[C, D]
7	dequeue	C	[D]

Removal order: A, B, C. Remaining: [D].

Example 3: Linear search vs binary search

Sorted array (indices 0–9, n = 10):

Index	0	1	2	3	4	5	6	7	8	9
Value	3	8	12	17	21	26	30	34	41	47

The convention is that of Section 5.3.

(a) Search for 34

Linear search: 3, 8, 12, 17, 21, 26, 30, 34 → 8 comparisons (found at index 7).
Binary search:

Probe	low	high	mid	A[mid]	Decision
1	0	9	4	21	21 < 34 → low = 5
2	5	9	7	34	found

→ 2 comparisons.

(b) Search for 10 (absent)

Linear search: basic version without early termination, so all 10 elements are compared → 10 comparisons, then “not found.”
Binary search:

Probe	low	high	mid	A[mid]	Decision
1	0	9	4	21	21 > 10 → high = 3
2	0	3	1	8	8 < 10 → low = 2
3	2	3	2	12	12 > 10 → high = 1
–	2	1	–	–	low > high → not found

→ 3 comparisons.

(c) Worst case: for n = 10, ⌊log₂ 10⌋ + 1 = 3 + 1 = 4 comparisons. Example: searching for 47 probes mid = 4 (21), 7 (34), 8 (41), 9 (47) — 4 comparisons.

Example 4: Tracing sorting passes

Input: [5, 2, 9, 1, 6] (ascending).

(a) Bubble sort — compare adjacent pairs from the left and swap if the left one is larger. One comparison = comparing two adjacent elements once.

Pass 1 (4 comparisons):

Pair	Swap?	Result
(5, 2)	yes	[2, 5, 9, 1, 6]
(5, 9)	no	[2, 5, 9, 1, 6]
(9, 1)	yes	[2, 5, 1, 9, 6]
(9, 6)	yes	[2, 5, 1, 6, 9]

→ 4 comparisons, 3 swaps. The maximum 9 is fixed at the end.

Pass 2 (3 comparisons, excluding the fixed end): (2, 5) no swap → (5, 1) swap [2, 1, 5, 6, 9] → (5, 6) no swap. 3 comparisons, 1 swap.

Pass 3 (2 comparisons): (2, 1) swap [1, 2, 5, 6, 9] → (2, 5) no swap. 2 comparisons, 1 swap.

Pass 4 (1 comparison): (1, 2) no swap.

Total: 4 + 3 + 2 + 1 = 10 comparisons (= n(n−1)/2), 5 swaps. Note: for 5 elements that are already sorted, with an early-exit flag the sort stops after pass 1 with 4 comparisons (= n − 1) and 0 swaps.

(b) Insertion sort — same input. One comparison = comparing the current key with one element of the sorted part. Stopping because the front of the array is reached is not counted as a comparison. A “shift” = moving one element one place to the right.

Step	Key	Comparisons made	Comparisons	Shifts	Result
1	2	5 > 2 (shift), front reached	1	1	[2, 5, 9, 1, 6]
2	9	5 > 9? no → stop	1	0	[2, 5, 9, 1, 6]
3	1	9 > 1, 5 > 1, 2 > 1 (all shift), front reached	3	3	[1, 2, 5, 9, 6]
4	6	9 > 6 (shift), 5 > 6? no → stop	2	1	[1, 2, 5, 6, 9]

Total: 7 comparisons, 5 shifts. Both the 5 bubble swaps and the 5 insertion shifts equal the number of inversions in the input: (5, 2), (5, 1), (2, 1), (9, 1), (9, 6) = 5. Because of the “do not shift on equal keys (compare with >)” rule, insertion sort is stable.

(c) Merge-sort rounds — input [6, 3, 8, 1, 7, 2, 5, 4] (n = 8). Start with runs of length 1 and merge neighboring pairs of runs. One comparison = comparing the front elements of the two runs once. When one run is exhausted, the rest is copied without comparison.

Round	Result	Comparisons
1 (1+1 → 2)	[3, 6] [1, 8] [2, 7] [4, 5]	1 + 1 + 1 + 1 = 4
2 (2+2 → 4)	[1, 3, 6, 8] [2, 4, 5, 7]	3 + 3 = 6
3 (4+4 → 8)	[1, 2, 3, 4, 5, 6, 7, 8]	7

Total: 17 comparisons. There are log₂ 8 = 3 rounds, and each round moves all 8 elements, so total work is of order n log n. A separate array is needed to hold merge results, so auxiliary space is O(n).

8. Four original practice questions

All four questions below are original questions written independently for this article; no past exam questions were used. Choices are labeled ア, イ, ウ, エ following the IPA exam format (ア = 1st, イ = 2nd, ウ = 3rd, エ = 4th).

Question 1 (choosing a data structure)

The number of elements n is large, and both of the following operations are performed frequently. You want the worst-case time complexity of each operation to be O(log n) or better. If an array is used, assume its capacity is reserved in advance and no reallocation occurs.

Add a new element (with a priority value).
Remove the element with the highest current priority.

Which data structure is most appropriate?

ア An unsorted array (append at the end)
イ A singly linked list kept sorted in descending order of priority
ウ A binary heap (max-heap)
エ A queue (FIFO)

Answer: ウ

Explanation:

ア: Adding at the end is O(1), but removing the maximum requires scanning everything, O(n). Condition not met.
イ: Removal takes the head node, O(1), but adding requires following links to find the right position, worst case O(n). Condition not met.
ウ: Adding places the element at the end and moves it up (height at most ⌊log₂ n⌋), O(log n); removal takes the root and restores the heap downward, O(log n). Both operations meet the condition. Correct.
エ: Being FIFO, it removes “the earliest inserted element,” not the highest-priority one. Choosing by priority would require scanning everything, O(n). Condition not met.

Question 2 (stack/queue transitions)

There are an empty stack S and an empty queue Q. Perform the following operations in order.

push 1 onto S
push 2 onto S
push 3 onto S
pop from S and enqueue the value into Q
pop from S and enqueue the value into Q
push 4 onto S
pop from S and enqueue the value into Q

Then dequeue repeatedly until Q is empty. In what order are the values removed?

ア 4, 2, 3
イ 3, 2, 4
ウ 1, 2, 3
エ 3, 2, 1

Answer: イ

Explanation (state trace):

Step	S (right is top)	Q (left is front)
1–3	[1, 2, 3]	[ ]
4	[1, 2] (pop 3)	[3]
5	[1] (pop 2)	[3, 2]
6	[1, 4]	[3, 2]
7	[1] (pop 4)	[3, 2, 4]

Dequeuing from Q gives the insertion order: 3, 2, 4. The value 1 remains in S.

ア 4, 2, 3: wrong — treats Q as LIFO, removing the last inserted first.
イ 3, 2, 4: matches the trace above. Correct.
ウ 1, 2, 3: wrong — treats S as FIFO. (Then steps 4 and 5 remove 1 and 2; after step 6, S = [3, 4], so step 7 removes 3, giving Q = [1, 2, 3].)
エ 3, 2, 1: wrong — ignores step 6’s push 4, or mistakenly runs it after step 7, so step 7 removes 1.

Question 3 (binary-search condition and comparison count)

Binary-search for 51 in the following array B (indices 0–14, n = 15). The convention is that of Section 5.3 (mid = ⌊(low + high) / 2⌋; one three-way decision against A[mid] counts as one comparison).

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Value	4	9	13	18	22	27	31	36	40	45	51	56	62	68	75

Which choice correctly states both the number of comparisons and the conditions for applying binary search?

ア 3 comparisons. As long as the data is sorted, it can be applied to a linked list with the same efficiency.
イ 4 comparisons. It can also be applied to an array whose data is not sorted.
ウ 11 comparisons. The data must be sorted.
エ 4 comparisons. The data must be sorted, and the middle position must be directly accessible.

Answer: エ

Explanation (trace):

Probe	low	high	mid	B[mid]	Decision
1	0	14	7	36	36 < 51 → low = 8
2	8	14	11	56	56 > 51 → high = 10
3	8	10	9	45	45 < 51 → low = 10
4	10	10	10	51	found

→ 4 comparisons. (This also equals the maximum for n = 15: ⌊log₂ 15⌋ + 1 = 4.)

ア: Wrong count (mistakes ⌊log₂ 15⌋ = 3 for the count). Also, a linked list cannot reach the middle node in O(1), so access cost becomes O(n); it is not “the same efficiency.”
イ: The count is right, but on an unsorted array the decision to “discard half” is invalid, so binary search cannot be used.
ウ: 11 is the number of comparisons for linear search to reach index 10 (the 11 values 4, 9, …, 51). It is not the binary-search count.
エ: Both the count of 4 and the two conditions (sorted, direct access) are correct. Correct.

Question 4 (sort behavior, complexity, stability)

Which statement about sorting algorithms is correct?

ア With a standard implementation, insertion sort makes n − 1 key comparisons when sorting n data items that are already in ascending order into ascending order, and it is a stable sort.
イ Quick sort has worst-case time complexity O(n log n) no matter how the pivot is chosen.
ウ Selection sort finishes in O(n) on already-sorted data.
エ Heap sort is a stable sort and needs an auxiliary array the same size as the input (O(n)).

Answer: ア