2017년 변리사 2차-데이터구조론-xxx-xxx [2교시]
【 문제-1 】 (30점)
효율적인 탐색을 위한 다원 트라이(multiwaytrie)자료구조에 관하여 다음의
물음에 답하시오.
key1 {analog,array,disk,debug,inbox,integer,sc,scan}
key2 {analog,array,debug,inbox,integer,output,scan,script}
key3 {xxxx. xx
xxxxxx. xx
xx1,xxxx. xx
xxxxxx. xx
xx9}
(1)다원 트라이는 어떤 경우에 유용한 자료구조인지 특징을 설명하시오.키
값이 정수인 이진 탐색 트리, 키 값이 문자열인 이진 탐색 트리, 그리고
다원 트라이의 시간 복잡도를 각각 비교 설명하시오.(8점)
(2)key1 집합에 대해 최대 레벨이 3인 다원 트라이를 왼쪽에서 오른쪽으로
단일 문자 샘플링을 사용하여 구성하고, key2 집합에 대해 최소 레벨을
갖는 다원 트라이를 구성하시오.최소 레벨 다원 트라이는 사용된 샘플링
함수를 쓰시오.(단, 숫자 번호(digitnumber)는 없다고 가정한다.루트의
레벨은 1이다.)(12점)
(3)key3 집합에 대해 숫자번호(digitnumber)를 갖는 압축 트라이(compressed
trie)를 구성하시오.(6점)
(4)다음은 다원 트라이 자료구조의 선언문이다.다원 트라이(t:다원 트라이
포인터)의 레벨(i)에서 원소(key)를 탐색하는 재귀 함수를 의사코드
(pseudocode)로 작성하시오.(4점) typedefstructtrie node*trie ptr; structtrie node{ intflag;// 노드의 유형 char*key; trie ptrchild[max size]; }; trie ptrsearchtrie(trie ptrt,char*key,inti); (이하 생략)
