Socrative 풀이 - Data Structure Part2 (Linked List & Hash Table)

더 힘든 Linked List와 Hash Table이다.
그나마 강의전날밤 Linked List를 최대한 코드를 짠덕에 이해도 어느정도 되면서
나름 괜찮게 풀었다. (나만그런가?)
오늘은 Linked List와 Hash Table에 대한 socrative 문제를 풀었다.
그래서 해당 문제 풀이를 하려고 한다.

1. 연결리스트의 요소는 메모리에 연속적으로 할당될 수 있다.(참/거짓 고르는 문제)

풀이) 연결리스트의 요소는 동적으로 수시로 할당되기 때문에 나열이 되어있으면 가능하다.
따라서 답은 참이다.

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

A. 연결 리스트는 특정 인덱스의 노드를 찾을 때 배열보다 빠르다는 장점이 있다.
B. 단일 연결 리스트에서 각 노드는 자신의 이전 노드를 알 수 없다.
C. 연결 리스트는 반드시 리스트의 끝(tail)에만 노드를 추가해야 한다.
D. 배열보다 메모리를 더 효율적으로 사용할 수 있는 자료구조이다.
E. 이중 연결 리스트는 하나의 값을 저장하기 위해 2개의 노드가 필요하다.

풀이)
A. 연결 리스트는 특정 인덱스의 노드를 찾을 때 배열보다 빠르다는 장점이 있다.
-> X, 연결리스트는 링크를 계속 타고 들어가야 하기 때문에 배열보다 느리다.
B. 단일 연결 리스트에서 각 노드는 자신의 이전 노드를 알 수 없다.
-> O, 이전 노드로 가는 링크가 없기 때문에 이후 노드만 알 수 있다.
C. 연결 리스트는 반드시 리스트의 끝(tail)에만 노드를 추가해야 한다.
-> X, 시작(head)뿐만 아니라 중간에서도 추가가 가능하다.
D. 배열보다 메모리를 더 효율적으로 사용할 수 있는 자료구조이다.
-> O, 링크로 이루어져 있어 메모리가 동적으로 할당되기 때문에 더 효율적인 사용이 가능하다.
E. 이중 연결 리스트는 하나의 값을 저장하기 위해 2개의 노드가 필요하다.
-> X, 1개의 노드와 2개의 포인터(이전 노드, 이후 노드)가 있다.

따라서 답은 B,D이다.

3. 노드가 5개인 연결 리스트의 모든 노드를 가장 효율적으로 삭제하고 싶을 때 총 몇 번의 연산이 필요한가?(단, 언어는 자바스크립트를 사용한다.)

A.1	
B.2 
C.3 
D.4 
E.5

풀이) head 부분을 한번만 자르면 나머지가 삭제되는 효과를 볼 수 있다.
(난 원래 head가 없어지면 나머지는 없는거나 마찬가지다.라고 생각했었다.ㅋㅋ)

따라서 답은 A이다.

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);

풀이)
list를 빈배열이라고 하고, 배열 안에 답이 있다고 간주하겠다.
list.insert(5);
list.insert(10);
list.insert(15);
list.insert(20); 를 각각 실행하면 [5, 10, 15, 20]
list.removeAt(0); 를 실행하면 0번째 인덱스의 값인 5가 삭제되어 [10, 15, 20]
여기서 list.removeAt(2);를 실행하면 2번째 인덱스의 값인 20이 삭제되어 [10, 15]가 된다.
여기서 list.findAt(1);를 실행하면 1번째 인덱스의 값인 15가 된다.

따라서 답은 15이다.

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

A.2 
B.4 
C.6 
D.8 
E.10

풀이)
이중 연결 리스트의 탐색방법은 연결리스트와 동일하다.
탐색방향이 일편적이고 순차적으로 노드의 수를 세어나간다.
그러므로 단일 연결 리스트와 동일하게 10번의 검색을 한다.

그래서 답은 E이다.

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);
 }

A. 1 - 3 - 5
B. 2 - 4 - 6
C. 2 - 4 - 6 - 6 - 4 - 2
D. 1 - 3 - 5 - 5 - 3 - 1
E. 1 - 2 - 3 - 4 - 5 - 6

풀이)
최초 노드 1 이 찍힌 후, 1 다음에 next 값이 있으니 재귀로 들어간다.
이 때 값은 1의 다음다음 값인 '3'이 들어가게 되고, 3 또한 next를 갖고 있다.
재귀함수가 가져가는 그 값은 바로 '5'.
그래서 1-3-5 까지 나온 후, 더이상 들어갈 수 없으니 함수가 종료되고 갖고 있던 값을 다시 반환한다.(콜스택 개념이 적용됨)
5-3-1 순으로 반환이 진행되고, 최종적으로 1-3-5-5-3-1으로 결과가 나온다.

따라서 답은 D이다.

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

A. 두 개 이상의 값에 하나의 키를 사용할 수 없다.
B. 키와 값을 한 쌍으로 저장할 수 있는 자료구조이다.
C. 해시 함수는 어떤 값이 들어오더라도 고유한 값으로 만들어 출력하기 때문에 입력 값과 출력 값을 1대1로 매핑할 수 있다.
D. 해시 테이블은 내부적으로 SHA 256 해시 함수를 사용한다.
E. 해시 함수를 통해 얻은 출력 값을 통해 입력을 생성할 수 있다.

풀이)
A : 두 개 이상의 값에 하나의 키를 사용할 수 없다.
-> O, 하나의 키에 하나의 값을 사용할 수 있다.
B. 키와 값을 한 쌍으로 저장할 수 있는 자료구조이다.
-> O, 위의 풀이와 같은 뜻이다.
C : 해시 함수는 어떤 값이 들어오더라도 고유한 값으로 만들어 출력하기 때문에 입력 값과 출력 값을 1대1로 매핑할 수 있다.
-> X, 서로 다른 문자열이 해시함수를 통해 Hash 한 결과가 같은 경우, 즉 중복되는 경우도 발생할 수 있으므로 좋은 해시함수를 써야한다.
D : 해시 테이블은 내부적으로 SHA 256 해시 함수를 사용한다.
-> X, 해시 테이블은 다른 해쉬함수도 사용할 수 있다.
E. 해시 함수를 통해 얻은 출력 값을 통해 입력을 생성할 수 있다.
-> X, 값으로는 키를 알아낼 수 없다.

따라서 답은 A,B이다.

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"));

A. I love apple
B. I love pineapple
C. ... what?
D. I need a macbook pro
E. undefined

풀이)
키 "apple"의 값을 실행하는것인데, 원래 "apple", "I love apple" 이었으나 "apple", "I need a macbook pro" 과정에서 "I need a macbook pro"로 덮어쓴다.

따라서 답은 D이다.

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-9191-2929")

A. 0
B. 1
C. 2
D. 3
E. 4

풀이)
난 key.length % 5; 여기서 % 5는 신경쓰지 않았다.
키의 글자개수가 같으면 충돌나므로 보기에서 개수가 같은것은 height, weight, mobile이다.
height에서 weight로 넘어갈때 1번, weight에서 mobile로 넘어갈때 2번으로 총 2번의 충돌이 발생한다.

따라서 답은 C이다.