Linked List, Hash Table

1. 연결리스트의 요소는 메모리에 연속적으로 할당될 수 있다.

① 참

② 거짓

① 참

 

2. 연결리스트에 대한 설명으로 맞는 것을 모두 고르면?

① 연결리스트는 특정 인덱스의 노드를 찾을 때 배열보다 빠르다는 장점이 있다.

② 단일 연결리스트에서 각 노드는 자신의 이전 노드를 알 수 없다.

③ 연결리스트는 반드시 리스트의 끝(tail)에만 노드를 추가해야 한다.

④ 배열보다 메모리를 더 효율적으로 사용할 수 있는 자료구조이다.

⑤ 이중 연결리스트는 하나의 값을 저장하기 위해 2개의 노드가 필요하다

② 단일 연결리스트에서 각 노드는 자신의 이전 노드를 알 수 없다.

④ 배열보다 메모리를 더 효율적으로 사용할 수 있는 자료구조이다.

 

3. 노드가 5개인 연결리스트의 모든 노드를 가장 효율적으로 삭제하고 싶을 때 총 몇 번의 연산이 필요한가?

(단, 언어는 자바스크립트를 사용한다)

① 1

② 2

③ 3

④ 4

⑤ 5

① 1

 

4. 다음과 같은 코드의 실행 결과로 적합한 것은?

const list = new LinkedList()
list.insert(5)
list.insert(10)
list.insert(15)
list.insert(20)
list.removeAt(0)
list.removeAt(2)
const value = list.findAt(1)

console.log(value)

15

 

5. 10개의 노드가 연결되어 있는 단일 연결리스트는 원하는 값을 찾기 위해 최대 10번의 검색이 필요하다. 그렇다면 10개의 노드가 연결되어 있는 이중 연결리스트는 원하는 값을 찾기 위해 최대 몇 번의 검색이 필요한가?

① 2

② 4

③ 6

④ 8

⑤ 10

⑤ 10

 

6. 데이터의 값이 아래와 같이 저장된 연결 리스트가 있다.

(head) 1 - 2 - 3 - 4 - 5 - 6 (tail)

 

alternatePrint(head)의 결과로 적합한 것은?

function alternatePrint(node) {
  if(node == null) {
  return;
 }
 console.log(node.data)
 
 if(node.next) {
 alternatePrint(node.next.next)
 }
 console.log(node.data)
}

① 1 - 3 - 5

② 2 - 4  - 6

③ 2 - 4 - 6 - 6 - 4 - 2

④ 1 - 3 - 5 - 5 - 3 - 1

⑤ 1 - 2 - 3 - 4 - 5 - 6

④ 1 - 3 - 5 - 5 - 3 - 1

 

7. 해시 테이블과 해시 함수에 대한 설명으로 반드시 참인 것을 모두 고르면?

① 두 개 이상의 값에 하나의 키를 사용할 수 없다.

② 키와 값을 한 쌍으로 저장할 수 있는 자료구조이다.

③ 해시 함수는 어떤 값이 들어오더라도 고유한 값으로 만들어 출력하기 때문에 입력 값과 출력 값을 1대1로 매핑할 수 있다.

④ 해시 테이블은 내부적으로 SHA-256 함수를 사용한다.

⑤ 해시 함수를 통해 얻은 출력 값을 통해 입력을 생성할 수 있다.

① 두 개 이상의 값에 하나의 키를 사용할 수 없다.

② 키와 값을 한 쌍으로 저장할 수 있는 자료구조이다.

 

8. 다음과 같은 코드의 실행 결과로 적합한 것은?

const hashTable = new HashTable()
hashTable.insert("apple", "I love apple")
hashTable.insert("pineapple", "I love pineapple")
hashTable.insert("mint_choco", "...what?")
hashTable.insert("apple", "I need a macbook pro")

console.log(hashTable.retrieve("apple"))

① I love apple

② I love pineapple

③ ...what?

④ I need a macbook pro

⑤ undefined

④ I need a macbook pro

 

9. HashTable이 A라는 해시 함수를 사용할 때, 다음 코드를 실행한 후 해시 충돌이 발생하는 횟수는?

function A(key) {
  return key.length % 5;
}

const hashTable = new HashTable()
hashTable.insert("name", "Kim")
hashTable.insert("age", 22)
hashTable.insert("height", 177)
hashTable.insert("weight", 65)
hashTable.insert("mobile", "010-0000-0000")

① 0

② 1

③ 2

④ 3

⑤ 4

③ 2