|
|
|
 |
 |
| 키워드 : |
|
|
| 소개글 |
데이터구조론 |
| 요약 |
2007년도 제44회 변리사 제2차시험 문제지
<과 목><데이터구조론><><응시번호><><성 명><>
【제 A-1 문】 (30점)
1. 정수 배열의 원소들을 오름차순으로 정렬하고자 한다. 배열의 초기 값이 다음과 같다고 하자.
8 7 6 5 4 3 2 1
다음의 정렬 알고리즘을 사용했을 때의 배열 내용의 변화를 단계별로 쓰시오.
(1) Insertion sort (5점)
(2) Merge sort (5점)
(3) Quick sort (5점)
- 단, pivot은 배열의 첫 번째 원소로 한다.
2. 키(key)값의 비교(comparison)와 교환(interchange)으로 이루어지는 정렬 알고리즘(sorting algorithm)의 하한(lower bound)이 Ω(nlogn)임을 결정트리(decision tree)를 이용하여 증명하시오. 단, n은 정렬하려는 원소의 개수를 의미한다.(15점)
【제 A-2 문】 (20점)
정수를 저장하는 스택을 연결 리스트(linked list)로 구현하고자 한다. 스택 연산을 위한 함수의 원형이 다음과 같을 때, C언어를 사용하여 각 함수를 정의하시오.(20점)
void initialize(stack *); // 스택 초기화
void push(int, stack *); // 스택에 원소 삽입
int pop(stack *); // 스택에서 원소 삭제한 후 리턴
int top(stack *); // top 원소 리턴
int empty(stack *); // 스택이 empty이면 1리턴, 아니면 0리턴
단, 스택은 다음과 같은 형이다.
typedef struct element {
int d; // 데이터 저장 멤버
element *next;
} element;
typedef struct stack {
int cnt; // 스택의 |
 |
|
|
 |
|
위 정보및 게시물 내용의 진실성에 대하여 보증하지 아니하며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
위 정보및 게시물 내용의 불법적 이용, 무단전재및 배포는 금지되어 있습니다.
저작권침해, 명예훼손 등 분쟁요소 발견시 하단의 저작권 침해신고를 이용해 주시기 바랍니다. |
|
공지사항이 없습니다.
데이터구조론
파일명
대표이사 : 정현준