京都大学 情報学研究科 知能情報学専攻 2019年8月実施 情報学基礎 F-1
Author
祭音Myyura
Description
Q.1
A hash table is an effective data structure for implementing the operations, e.g. INSERT, SEARCH, and DELETE, in computer systems.
(1.1) What is the advantage of hash tables compared ot directly addressing into an array?
(1.2) Given a hash table of size
(1.3) Given a hash function
Q.2
Breadth first search (BFS) and depth first search (DFS) are two algorithms for traversing trees or graphs.
(2.1) Given a set of vertices
where an adjacency list
(2.2) Give the visited vertices in an alphabetical order for the graph given in (2.1) using BFS and DFS, respectively.
Assume that both algorithms are initially called with the vertex
(2.3) Give a recursive algorithm for DFS in a graph.
Kai
Q.1
(1.1)
Operations | Array Time Complexity | Hash Table Time Complexity |
---|---|---|
Index Access | N/A | |
Key Access | N/A | |
Search | ||
Insertion | ||
Deletion |
Compared to array, hash table provides constant time for searching, insertion and deletion operations on average, offers a high-speed data retrieval and manipulation.
(1.2)
(Note: Linear probing is a strategy for resolving collisions, by placing the new key into the closest following empty cell)
[0, 7, 1, 3, 11, 9, ]
(1.3)
Under the assumption of uniform hashing, we will use linearity of expectation to compute this.
Suppose that all the keys are totally ordered
Q.2
(2.1)

(2.2)
BFS
s, a, c, d, b, e
DFS
s, a, c, b, d, e
(2.3)
DFS(G, u)
u.visited = true
for each v ∈ G.adj(u)
if v.visited == false
DFS(G, v)
main()
for each u ∈ G
u.visited = false
for each u ∈ G
DFS(G, u)