자료구조 출석수업시험 정리

자료구조 출석수업시험 정리

1. 배열과 연결리스트의 특성비교

1) 배열의 특성

1 순차적 메모리할당방식이다.

2 순차적 임의적으로 접근할 수 있는 선형 자료구조이며 접근방법은 직접접근방법이다 

-> 표현이 간단하고 원소의 접근이 빠르지만 삽입 삭제의 효율이 떨어진다 .

3 <인덱스 ,원소 > 쌍의 집합

4 원소들은 모두 같은 형(type), 같은 크기를 갖는다  .

2) 연결리스트의 특성

1 원소의 물리적 순서와 리스트의 논리적 순서가 같지 않은 비순차 표현이다.

2 원소를 저장할 때 이 원소의 다음 원소에 대한 주소도 함께 저장해야 한다.

3 노드 (<원소, 주소> 쌍) 의 저장 구조를 갖는다  .

4 각 노드는 자료필드와 다음 노드의 주소 값을 가지는 링크 필드로 구성되는 자료구조이다.

5 삽입 /삭제시 원소 이동 발생이 없어 편리하다 .

2. 순환의 개념 및 특성

- 자기 자신의 프로시저를 호출하는 방식을 이용하여

복잡한 문제를 직접 간단하게 풀 수 있는 작은 문제로 분할하여 해결하려는 방법으로

분할정복의 특성을 가진 문제에 적합하다.

3. 배열의 행우선과 열우선의 개념 및 주소 계산공식

1) 행우선

1. 2차원 배열을 먼저 행 별로 분할하여 이 행을 차례로 연결시켜

   하나의 가상적인 차원 배열로 만들어 사상하는 것이다. -> 열의 주소가 먼저 변함.

2.  2 차원 a[m, n]에서 a[0,0]의 주소가 k 라 할 때 임의의 원소 a[i, j]의

주소계산 공식은  k + i * n + j  가 된다.

즉 현재의 주소 + 임의원소 행의 값 *열의 총수 + 임의원소 열의 값이다.

2) 열우선

1. 2차원 배열을 먼저 열 별로 분할하여 이 열을 차례로 연결시켜

   하나의 가상적인 차원 배열로 만들어 사상하는 것이다 ->행의 주소가 먼저 변함.

2 주소계산 공식은  k + j * m + i 가 된다 .

즉 현재의 주소 + 임의원소 열의 값 * 행의 총수  +  임의원소 행의 값이다.

4. 스택과 큐의 특성 비교 및 활용의 예

1) 스택의 특성

1 자료의 입력과 출력이 한쪽 끝에서만 이루어진다.

2 후입선출리스트이다. LIFO

3 PUSH( 삽입), POP(삭제) . 연산이 있다

4 1 개의 인덱스인 TOP 포인터로 삽입과 삭제가 이루어는 순서리스트이다.

5 응용분야로 시스템스택, 서브루틴호출, 수식계산, 인터럽트처리, 컴파일러, 순환호출

등에 사용된다.

2) 큐의 특성

1.  한쪽 끝에서는 삭제, 다른 한쪽 끝에서는 삽입되는 1차원 배열의 선형리스트를 의미한다.

2.  선입선출리스트이다. FIFO

3 . 2 개의 인덱스 front( 삭제), rear(삽입 )로 삽입, 삭제가 이루어진다.

4.  응용분야로는 작업 스케줄링과 버퍼관리에 보편적으로 이용된다.

5. 단순연결리스트와 이중연결리스트의 특성비교

1) : 단순열결리스트

1.  자료를 저장하는 데이터필드와 다음노드를 가리키는 포인터를 저장하는 링크필드로 구성된

노드 (2개의 필드) 로 연결되어있다 .

2 다음 노드로의 이동은 쉽지만 삽입하거나 삭제할 때 선행노드를 알아야 하는 문제점이 있다.

2) : 이중연결리스트

1. 자료를 저장하는 데이터필드와 후속노드를 가리키는 포인터를 저장하는 RLINK 필드 ,

선행노드를 가리키는 포인터를 저장하는  LLINK 필드로 구성된 노드 (3개필드) 로 연결되어있다 .

2. 선행노드를 쉽게 찾을 수 있다.

6. 트리의 순회방법 설명

1)  이진트리순회에서  L, D, R,이 각각 좌측으로 이동, 자료 인쇄, 우측으로 이동 이라는

3개의 작업을 나타낼 때 우측보다 좌측을 먼저 순회하는 방법으로는 가 있다 LDR, LRD, DLR .

2) 이 세 가지 순회를 각각 중위순회, 후위순회, 전위순회라하며

산술표기식  INFIX 표기, POSTFIX 표기, PREFIX 표기와 유사하다.

1.  중위순회 (LDR): 좌측으로 이동, 자료의 인쇄, 우측으로 이동의 순서로 순회한다.

2.  후위순회 (LRD): 좌측으로 이동, 우측으로 이동, 자료의 인쇄 순으로 순회한다.

3. 전위순회 (DLR): 자료의 인쇄, 좌측으로 이동, 우측으로 이동의 순서로 순회한다.