[소프트웨어 개발] 1. 자료구조

40. 다음 트리의 차수(degree)는?

① 2 ② 3
③ 4 ④ 5


>> 정답 2번

 

트리의 차수 특정 노드에서 뻣어나가는 간선들의 수 중 가장 큰 수를 의미한다. 

A는 2개

B는 3개

C는 1개

D, F는 0개

E는 2개

H.I도 0개

 

그 중 3개가 제일 크므로 3번이 정답니다.

 

21. 다음 중 선형 구조로만 묶인 것은?
① 스택, 트리 ② 큐, 데크
③ 큐, 그래프 ④ 리스트, 그래프


>> 정답 2번
데크가 모르지만 비선형 구조에는 그래프와 트리가 들어가 있다. 
그를 제외하면 남은건 큐와 데크다

22. 다음 트리의 차수(degree)와 단말 노드(terminal node)의 수는?

① 차수:4, 단말 노드: 4
② 차수:2, 단말 노드: 4
③ 차수:4, 단말 노드: 8
④ 차수:2, 단말 노드: 8

>> 정답 2번

 

트리의 차수는 특정 노드에서 뻣어나간 간선 수가 가장 큰 것을 의미하며

단말 노드는 터미널노드 이다. 가장 마지막에 있는 노드의 숫자를 의미한다.

 

따라서 트리의 차수는 가장 큰 수 인 2개이다.

A는 2개

B는 1개

C는 2개

D는 0개

E는 2개

F는 0개

G, H는 0개

단말 노드는 터미널 노드이므로 D, G, H, F가 해당된다. 그래서 4개이다.

 

25. 그래프의 특수한 형태로 노드(Node)와 선분(Branch)으로 되어 있고, 정점 사이에 사이클(Cycle)이 형성되어 있지 않으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조는?
① tree ② network
③ stack ④ distributed


>> 정답 1번

트리는 비선형 구조로 노드와 간선(=선분)으로 이루어져 있고 순환(사이클)이 없는 그래프이다.

스택 = 선형 자료구조 후입선출



26. 스택에 대한 설명으로 틀린 것은?
① 입출력이 한쪽 끝으로만 제한된 리스트이다.
② Head(front)와 Tail(rear)의 2개 포인터를 갖고 있다.
③ LIFO 구조이다.
④ 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)가 발생한다.


>> 정답 2번

2번은 큐의 설명이다. 스택의 경우 top과 bottom이다.

lifo = 후입선출을 표현하는 영어줄임말


30. 자료구조에 대한 설명으로 틀린 것은?
① 큐는 비선형구조에 해당한다.
② 큐는 First In – First Out 처리를 수행한다.
③ 스택은 Lasrt In – First out 처리를 수행한다.
④ 스택은 서브루틴 호출, 인터럽트 처리, 수식 계산 및 수식 표기법에 응용된다.


>> 정답 1번
큐는 선형구조에 해당한다.
비선형 구조에 해당하는건 트리와 그래프이다

 

 

33. 다음은 스택의 자료 삭제 알고리즘이다. ⓐ에 들어 갈 내용으로 옳은 것은? (단, Top: 스택포인터, S: 스택의 이름)

If Top＝0 Then
(   ④   )
Else {
remove S(Top)
Top＝Top－1
}

① Overflow ② Top＝Top＋1
③ Underflow ④ Top＝Top



>> 정답 3번

내용이 꽉차서 넘치면 오버플로우 내용이 없는데 삭제하면 언더플로우다

 

---

https://www.youtube.com/watch?v=8pTpLhHaByw&list=PLKpxllD6C8Cli4UZqnDG4_77OU6XeF6e_&index=1 

---

자료구조

자료를 어떻게 구조하고 어떻게 연산할것인지를 정의한 것

데이터 성격에 맞는 자료구조가 있다.
어떤 자료 구조냐에 따라 속도의 차이가 있다.

효율적인 프로그램 작성시 고려사항 = 저장공간의 효율성과 실행시간의 신속성


선형구조 = 순서가 있는 구조
순서가 있다는 말은? 절차와 비슷하다.
ex) 카세트 테이프

1. 배열 array
같은 타입의 데이터가 나열되어 있는 정적인 자료구조 (정적 = 배열의 길이 수정이 안됨)
> 메모리 낭비 발생
> 첨자와 변수를 이용한 반복적 데이터 처리에 적합


2. 배열 + 데이터 편집 기능 =선형 리스트 연속 = 연속리스트

> 연속적인 공간에 데이터를 넣고 뺀다.
> 중간에 삽입하면 기존의 데이터에 밀리기 때문에 수정보다는 조회가 더 잘 어울린다. 
> 배열(첨자)를 사용한다. 

3. 선형 리스트 - 연결 = 연결리스트

> 수정이 용이한 리스트
> 비연속적이고 첨자로 접근할 수 없다. 
> 다음 데이터의 위치를 저장하고 있는 변수 = 포인터가 반드시 필요하다.
노드 = 데이터 + 포인터
> 위치를 기억하는 포인터 덕분에 연속적인 공간을 사용할 필요가 없기 때문에 삽입 삭제가 용이하다
> 연결리스트는 다음 노드를 찾아가는 시간이 필요하다. 노드는 데이터 보다 공간차이가 크다

4. 스택 stack
> 노드의 입출력이 한곳에서 시작한다.
> 가장 처음에 들어간 노드가 가장 마지막에 나온다. last in first out = 후입선출
> 가장 아래깔려있는 노드의 포인터 = botton
> 가장 위에 올려있는 노드의 포인터를 = top
> 스택이 꽉찬 상태에서 push(삽입)시 오버플로우(overflow)
> 스택이 텅 빈 상태에서 pop(삭제)을 하게 되면 언더플로우(underflow)

5. 큐 queue
> 입출력이 반대쪽에서 이루어지는 구조 ex) 터널
> 가장 먼저 들어온 노드가 가장 먼저 나갑 first in first out = 선입선출
> 가장 앞에 있는 노드의 포인터 = front
> 가장 뒤에 있는 노드의 포인터 = rear


비선형 구조 ex) 유튜브
5. 그래프 graph
> 노드와 그 노드를 잇는 간선(edge)로 이루어진 형태의 자료구조
> 노드간 관계를 파악하기 쉽도록 구성된 형태
> 그래프에서 순환되는 형태를 제거하면 트리가 된다

6. 트리 tree
> 순서가 없는 자료구조,
> 순환을 하지 않는 그래프의 형태
> 간선 = 선분, 가지, 링크 등
> 가장 위에 있는 루트로드 root node
> 가장 아래에 있는 터미널노드 terminal node
> 특정 노드에서 뻗어나간 가지의 개수를 나타내는 디그리 degree
> 이전 레벨의 부모노드 parent node, 다음 레벨의 자식노드 child node, 같은 부모를 가진 형제노드 sibiling node
> 가장 많은 가짓수를 나타내는 트리의 디그리 degree of tree