방송대 방통대 자료구조 1~3강 - 자료구조의 기초, 배열과 스택 - 요약 노트 시험족보 예상문제 - 올에이클래스

자료구조 1~3강 - 자료구조의 기초, 배열과 스택

자료가 정보로 바뀌는 과정과 추상화, 자료구조와 알고리즘의 관계를 이해한 뒤 배열과 스택의 표현 및 연산을 학습한다. 1~3강의 핵심 개념을 연결해 정리하고, 강의별 예상문제 20개씩 총 60문항으로 점검한다.

제1부 1강: 자료구조란 무엇인가

1. 자료와 정보

자료(data)는 현실 세계에서 관찰이나 측정을 통해 수집한 값이나 사실이다. 길이, 무게, 온도처럼 물리적 단위로 표현할 수 있는 대상뿐 아니라 문자, 수치, 기호 등도 자료가 된다. 자료가 아무렇게나 놓여 있으면 필요한 값을 찾고 비교하기 어렵기 때문에, 컴퓨터가 처리하기 좋은 방식으로 조직해야 한다.

정보(information)는 자료를 특정 목적에 맞게 처리해 의사결정에 활용할 수 있도록 만든 결과다. 강의록의 식 I = P(D)는 자료 D가 처리 P를 거쳐 정보 I가 된다는 뜻이다. 예를 들어 연필의 재고량, 사용량, 구매 예정일이라는 자료를 분류하고 합산하면 재주문 시점을 판단하는 정보가 된다.

구분	핵심 의미	예
자료	관찰·측정으로 수집한 값 또는 사실	재고 120개, 사용량 80개
처리	분류·계산·정렬·비교 등의 변환 과정	품목별 잔량 계산
정보	판단과 의사결정에 유용하도록 정리된 처리 결과	구매가 필요한 품목과 시기

2. 추상화의 개념

추상화(abstraction)는 공통적인 개념을 이용해 같은 종류의 다양한 객체를 정의하는 과정이다. 중요하지 않은 세부 사항은 감추고 문제 해결에 필요한 핵심 특징만 드러내므로 복잡한 대상을 간결하게 설명할 수 있다. 버스의 색상이나 내부 부품을 모두 나열하지 않고 ‘사람을 운송하는 교통수단’이라는 공통 특징으로 바라보는 것이 한 예다.

자료의 추상화는 다양한 대상을 컴퓨터에 저장하고 처리하기 위해 그 의미와 구조에서 공통 특징을 뽑아 정의하는 것이다. 이때 내부의 이진수 표현이나 실제 저장 위치를 일일이 드러내지 않고 개발자들이 공통된 개념으로 소통하게 한다.

3. 자료구조와 알고리즘

자료구조(data structure)는 추상화를 통해 알고리즘에서 사용할 자료의 논리적 관계를 구조화한 것이다. 자료의 추상화와 구조화가 적절하지 않으면 소프트웨어가 비효율적으로 수행되거나 확장하기 어려워질 수 있다.

알고리즘(algorithm)은 컴퓨터가 수행할 명령어를 추상화한 유한한 집합이다. 사람의 의도와 명령을 컴퓨터에 전달하는 방법이며, 프로그램은 추상적인 자료구조와 알고리즘을 프로그래밍 언어로 구체화한 결과다. 입력 자료는 자료구조로 조직되고, 알고리즘이 이를 처리해 출력을 만든다.

자료구조의 분류	예
미리 정의된 기본 자료구조	정수, 실수, 문자
미리 정의된 파생 자료구조	배열, 구조체, 포인터
사용자 정의 자료구조	리스트, 스택, 큐, 트리, 그래프

4. 알고리즘의 조건과 성능

알고리즘은 수행 뒤 적어도 하나의 결과를 내는 출력, 실행 가능한 명령으로 이루어지는 유효성, 외부 또는 내부에서 주어지는 유한한 입력, 각 명령이 분명해야 하는 명확성, 유한한 단계 뒤 종료해야 하는 유한성을 갖춰야 한다.

성능은 주로 시간 복잡도와 공간 복잡도로 분석한다. 시간 복잡도는 실제 초를 재는 것이 아니라 입력 크기 n에 따른 기본 연산의 실행 횟수를 O(n)과 같이 표현한다. 공간 복잡도는 실행 완료에 필요한 총 메모리를 예측하며, Sp = Sc + Se로 나타낼 수 있다. Sc는 프로그램 크기와 입출력 횟수에 관계없이 필요한 고정 공간이고, Se는 실행 과정에서 자료구조와 변수에 동적으로 필요한 가변 공간이다. 실제 실행 시간을 측정할 때는 동일한 프로그램과 시스템 시계를 이용해야 비교가 의미 있다.

자료는 처리되어 정보가 되고, 자료의 논리적 관계는 자료구조로 추상화된다. 알고리즘은 그 자료구조를 다루는 명령의 추상화이며, 프로그램은 둘을 컴퓨터에서 실행할 수 있게 구체화한 것이다.

제2부 2강: 배열

1. 배열의 정의와 의미

배열(array)은 일정한 차례나 간격에 따라 원소를 나열한, 차례와 관련된 기본 자료구조다. 배열은 인덱스(index)와 원소값(value)의 쌍으로 구성된다. 모든 원소는 같은 자료형과 같은 크기의 기억 공간을 가지며, 인덱스로 원하는 원소를 직접 접근할 수 있다.

개발자가 보는 인덱스는 실제 메모리 주소와 무관한 추상화된 값이다. 프로그래밍 언어와 컴파일 과정이 이 인덱스를 물리적 주소와 연결한다. 강의록의 일반 설명은 1부터 시작하는 인덱스를 사용하지만, C 언어의 배열 인덱스는 0부터 시작하므로 문맥을 구분해야 한다.

2. 배열의 추상 자료형과 기본 연산

추상 자료형(ADT)은 객체와 관련 연산의 정의로 구성되며, 실제 자료구조를 구현하기 전의 설계 단계다. 자료형은 메모리 저장 공간을 할당하기 위한 프로그래밍 언어의 선언으로, 추상 자료형을 구체적으로 구현하는 단계다.

배열 ADT는 인덱스 집합과 같은 자료형의 원소 집합으로 볼 수 있다. 주요 연산은 크기 n의 빈 배열을 만드는 create, 유효한 인덱스 i의 값을 반환하는 retrieve, 인덱스 i에 원소 e를 저장하는 store다. retrieve와 store는 인덱스가 범위를 벗어나면 오류를 처리해야 한다.

연산	기능	조건
create(n)	크기 n인 빈 배열 생성	n은 최대 크기를 나타내는 양의 정수
retrieve(a, i)	a의 i번째 원소 반환	i가 유효한 인덱스여야 함
store(a, i, e)	a의 i번째 위치에 e 저장	i가 유효한 인덱스여야 함

3. 1차원 배열과 주소 계산

1차원 배열은 한 줄짜리 배열이며 하나의 인덱스로 원소를 구분한다. 배열 A의 첫 원소 A[0]의 시작 주소가 a이고 원소 하나의 크기가 k라면, A[i]의 주소는 a + i × k다. 따라서 A[3]의 주소는 a + 3k가 된다. 연속된 메모리를 쓰기 때문에 인덱스를 통한 직접 접근이 가능하다.

4. 2차원 배열과 저장 순서

2차원 배열은 1차원 배열을 여러 개 쌓은 것으로 생각할 수 있으며, 행과 열의 두 인덱스로 원소를 특정한다. 컴퓨터의 메모리는 선형이므로 2차원 배열도 실제로는 한 줄로 펼쳐 저장된다.

행 우선 저장은 한 행의 원소를 연속해 저장한 뒤 다음 행을 저장하고, 열 우선 저장은 한 열의 원소를 연속해 저장한 뒤 다음 열을 저장한다. C 언어의 2차원 배열은 행 우선 순서로 저장된다.

5. 희소행렬의 효율적 표현

희소행렬(sparse matrix)은 0인 원소가 0이 아닌 원소보다 상대적으로 많은 행렬이다. 모든 0을 일반 배열에 그대로 저장하면 메모리가 낭비된다. 따라서 0이 아닌 값만 행, 열, 값의 삼중항으로 모아 저장하면 공간 효율을 높일 수 있다. 이 표현은 0이 아닌 원소가 충분히 적을 때 특히 유리하다.

배열의 빠른 직접 접근은 연속 저장과 고정된 원소 크기에서 나온다. 반면 크기 변경이나 중간 삽입·삭제에는 많은 원소 이동이 필요할 수 있다.

제3부 3강: 스택

1. 스택의 개념

스택(stack)은 객체와 객체가 저장되는 순서를 기억하는 자료구조다. 0개 이상의 원소를 갖는 유한 순서 리스트이며, 삽입과 삭제가 한쪽 끝인 top에서만 일어난다. 가장 먼저 들어간 자료가 가장 나중에 나오는 후입선출(LIFO) 구조다.

2. 스택의 추상 자료형과 연산

스택 ADT의 핵심 연산은 빈 스택을 생성하는 CreateStack, top에 원소를 넣는 Push, top의 원소를 삭제해 반환하는 Pop이다. 고정 크기 스택이 가득 찬 상태에서 push하면 overflow, 빈 스택에서 pop하면 underflow가 발생하므로 StackIsFull과 StackIsEmpty 검사가 필요하다.

배열로 구현할 때 빈 스택의 top을 -1로 두는 방식이 흔하다. 삽입은 stack[++top] = item처럼 top을 먼저 증가시킨 뒤 저장하고, 삭제는 stack[top--]처럼 현재 원소를 반환한 뒤 top을 감소시킨다. 전위·후위 감소의 위치가 결과에 영향을 준다는 점을 주의해야 한다.

3. 스택의 응용

스택은 지역변수의 메모리 할당과 회수를 관리하는 시스템 스택, 서브루틴과 재귀 호출의 복귀 주소 관리, 연산자 우선순위에 따른 수식 계산, 인터럽트 처리 뒤 돌아갈 명령 위치 저장, 컴파일러와 순환 호출 관리 등에 사용된다.

4. 중위·전위·후위 표기

표기법	연산자의 위치	A와 B를 더하는 예
중위 표기법	피연산자 사이	A + B
전위 표기법	피연산자 앞	+ A B
후위 표기법	피연산자 뒤	A B +

중위식을 후위식으로 바꿀 때는 연산자 우선순위를 고려해 계산 단위마다 괄호를 묶고, 각 괄호 안의 연산자를 오른쪽으로 이동한 뒤 괄호를 제거한다. 예를 들어 A - ((B + K) / D)는 A B K + D / -가 된다.

후위식을 계산할 때는 식을 왼쪽부터 읽는다. 피연산자는 스택에 push하고, 연산자를 만나면 두 값을 pop해 연산한 뒤 결과를 다시 push한다. 이때 먼저 pop한 값이 오른쪽 피연산자, 나중에 pop한 값이 왼쪽 피연산자다. 예를 들어 369*+는 6×9를 먼저 계산해 54를 만들고 3+54를 계산하여 57이 된다.

스택 문제는 top의 변화와 피연산자 순서가 핵심이다. push는 삽입 전 포화 여부, pop은 삭제 전 공백 여부를 검사하고, 뺄셈과 나눗셈에서는 두 번의 pop 순서를 바꾸지 않아야 한다.

핵심 개념 정리

1강은 자료가 처리를 거쳐 정보가 되는 관계, 추상화, 자료구조와 알고리즘, 알고리즘의 조건과 복잡도를 다룬다. 2강은 인덱스와 원소값의 쌍인 배열, 배열 ADT, 연속 저장에 따른 주소 계산, 2차원 배열의 행·열 우선 저장, 희소행렬의 삼중항 표현을 설명한다. 3강은 후입선출 구조인 스택, push·pop과 오류 조건, top을 이용한 배열 구현, 중위·전위·후위 표기 및 후위식 계산을 다룬다.

시험에서는 I = P(D), 알고리즘의 다섯 조건, Sc와 Se의 구분, 배열 주소식 a + i×k, C 언어의 행 우선 저장, 희소행렬의 행·열·값 표현, 스택의 LIFO 원리, top 증감 순서, 후위식 계산의 피연산자 순서를 정확히 구분해야 한다.

1강 예상문제 20선: 자료구조 기초

1. I = P(D)가 뜻하는 관계는?

① 정보를 처리하면 자료가 사라진다. ② 자료를 처리하면 정보가 만들어진다. ③ 자료와 정보는 항상 동일하다. ④ 처리 없이 정보가 자동 생성된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
자료 D에 처리 P를 적용한 결과가 정보 I라는 뜻이다.

2. 자료에 대한 설명으로 가장 적절한 것은?

① 항상 의사결정이 끝난 최종 결론이다. ② 오직 문자로만 표현된다. ③ 처리된 2차 결과만을 뜻한다. ④ 관찰이나 측정으로 수집한 값 또는 사실이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
자료는 현실 세계에서 수집한 값이나 사실이며, 처리 전의 원재료에 해당한다.

3. 정보의 특징으로 옳은 것은?

① 자료를 목적에 맞게 처리해 판단에 활용할 수 있다. ② 물리적 단위로 표현되는 원자료만을 뜻한다. ③ 자료와 무관하게 생성된다. ④ 분류와 처리 과정을 거칠 수 없다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
정보는 자료를 처리해 의사결정에 유용한 형태로 만든 결과다.

4. 연필의 재고량과 사용량을 품목별로 계산해 구매 시기를 정한 것은?

① 자료 수집 이전의 가설 ② 알고리즘의 유한성 ③ 정보 ④ 메모리 주소

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
재고량과 사용량이라는 자료를 처리해 구매 판단에 활용했으므로 정보다.

5. 추상화의 핵심 역할은?

① 모든 객체의 차이를 빠짐없이 나열한다. ② 불필요한 세부를 감추고 공통된 핵심 특징을 드러낸다. ③ 물리적 저장 주소만 공개한다. ④ 프로그램을 반드시 길게 만든다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
추상화는 복잡한 대상에서 공통적이고 중요한 특성을 뽑아 간결하게 표현한다.

6. 자료의 추상화에 대한 설명으로 옳은 것은?

① 자료의 의미와 구조에서 공통 특징을 뽑아 정의한다. ② 자료의 실제 이진 표현을 항상 노출한다. ③ 모든 자료를 하나의 값으로 삭제한다. ④ 저장 위치만으로 자료를 정의한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
자료의 추상화는 컴퓨터 저장과 처리를 위해 공통 특징을 중심으로 대상을 정의한다.

7. 자료구조의 정의로 가장 적절한 것은?

① 컴퓨터의 전원 장치다. ② 프로그램 실행 시간만을 뜻한다. ③ 자료를 처리하지 않고 버리는 규칙이다. ④ 알고리즘에서 사용할 자료의 논리적 관계를 구조화한 것이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
자료구조는 자료의 논리적 관계를 조직해 알고리즘이 효율적으로 다룰 수 있게 한다.

8. 알고리즘이란?

① 자료가 저장된 물리 주소의 목록이다. ② 무한히 계속되는 모호한 지시다. ③ 컴퓨터가 수행할 명령어를 추상화한 유한한 집합이다. ④ 사용자 정의 자료형만을 뜻한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
알고리즘은 문제 해결을 위해 컴퓨터가 실행할 명확하고 유한한 명령의 집합이다.

9. 자료구조와 알고리즘의 관계로 옳은 것은?

① 자료구조는 입력 자료의 추상화이고 알고리즘은 수행 명령의 추상화다. ② 둘은 모두 물리적 메모리 주소만 표현한다. ③ 알고리즘은 자료구조 없이 항상 동일하게 작동한다. ④ 자료구조가 출력이고 알고리즘이 입력이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
자료구조는 다룰 자료를 조직하고 알고리즘은 그 자료에 수행할 절차를 정의한다.

10. 다음 중 사용자 정의 자료구조에 해당하는 것은?

① 정수 ② 스택 ③ 실수 ④ 문자

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
강의록의 분류에서 리스트·스택·큐·트리·그래프는 사용자 정의 자료구조다.

11. 알고리즘의 출력 조건은?

① 입력이 반드시 무한해야 한다. ② 명령이 모호해도 된다. ③ 종료하지 않아야 한다. ④ 수행 뒤 적어도 한 가지 결과를 생성해야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
알고리즘은 실행 결과로 하나 이상의 출력을 만들어야 한다.

12. 알고리즘의 명확성에 대한 설명은?

① 명령 수가 무한해야 한다. ② 출력이 없어야 한다. ③ 각 명령의 의미가 분명하고 애매하지 않아야 한다. ④ 메모리를 전혀 사용하지 않아야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
명확성은 수행할 각 단계가 누구에게나 분명하게 해석되어야 한다는 조건이다.

13. 알고리즘의 유한성이 의미하는 것은?

① 입력이 항상 하나여야 한다. ② 유한한 단계 후 반드시 종료해야 한다. ③ 모든 명령이 동시에 수행되어야 한다. ④ 출력은 숫자여야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
유한성은 알고리즘이 끝없이 실행되지 않고 정해진 단계 안에 끝나야 한다는 뜻이다.

14. 시간 복잡도 O(n)가 직접 나타내는 것은?

① 실제 실행 시간을 초 단위로 잰 값 ② 프로그램 파일의 바이트 수 ③ 사용자 수의 정확한 합 ④ 입력 크기에 따른 기본 연산 실행 횟수의 증가 양상

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
시간 복잡도는 특정 컴퓨터의 초 단위 시간이 아니라 입력 크기와 연산 횟수의 관계를 표현한다.

15. 공간 복잡도의 고정 공간 Sc에 해당하는 것은?

① 컴파일 시 정해져 실행 내내 필요한 프로그램 공간 ② 입력 크기에 따라 늘어나는 동적 자료구조 공간 ③ 재귀 호출 깊이에 따라 늘어나는 공간 ④ 실행 중 새로 할당되는 변수 공간

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
Sc는 프로그램 크기처럼 실행 전에 정해지고 실행 동안 고정적으로 필요한 공간이다.

16. 공간 복잡도 식으로 옳은 것은?

① Sp = Sc - Se ② Sp = Sc × 0 ③ Sp = Sc + Se ④ Sp = Se / Sc

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
총 공간 Sp는 고정 공간 Sc와 가변 공간 Se의 합으로 나타낸다.

17. 가변 공간 Se의 예로 적절한 것은?

① 컴파일된 명령어의 고정 크기 ② 프로그램 이름의 길이 ③ 항상 일정한 상수 저장 공간 ④ 입력 크기에 따라 동적으로 늘어나는 자료구조 공간

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
Se는 실행 과정과 입력 크기에 따라 달라지는 자료구조와 변수의 메모리다.

18. 알고리즘의 실제 실행 시간을 비교할 때 필요한 조건은?

① 서로 다른 하드웨어만 사용한다. ② 실행 가능한 같은 프로그램과 동일한 측정 환경을 사용한다. ③ 실행 파일 없이 추측한다. ④ 입력 크기를 기록하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
실측 시간은 하드웨어와 환경의 영향을 받으므로 동일 조건과 시스템 시계를 사용해야 한다.

19. 자료구조의 추상화가 부적절할 때 생길 수 있는 문제는?

① 항상 메모리 사용량이 0이 된다. ② 모든 알고리즘이 자동 최적화된다. ③ 소프트웨어가 비효율적으로 수행되거나 확장하기 어려워질 수 있다. ④ 자료가 곧바로 정보가 된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
잘못 조직된 자료는 연산 비용을 키우고 프로그램 확장을 어렵게 만들 수 있다.

20. 프로그램에 대한 설명으로 가장 적절한 것은?

① 자료구조와 알고리즘을 프로그래밍 언어로 구체화한 것이다. ② 알고리즘과 무관한 물리 장치다. ③ 자료를 수집하기 전의 사실이다. ④ 추상화만 있고 실행은 불가능한 개념이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
프로그램은 추상적인 자료구조와 알고리즘을 컴퓨터가 실행할 수 있게 표현한 결과다.

2강 예상문제 20선: 배열

1. 배열을 구성하는 기본 쌍은?

① 행과 열만 ② 주소와 알고리즘만 ③ 인덱스와 원소값 ④ 스택과 큐

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
배열은 각 순서를 나타내는 인덱스와 그 위치의 원소값으로 구성된다.

2. 배열의 특징으로 옳은 것은?

① 모든 원소가 같은 자료형과 같은 크기의 기억 공간을 가진다. ② 원소마다 반드시 다른 자료형을 가진다. ③ 삽입과 삭제가 top에서만 일어난다. ④ 물리적으로 흩어진 위치만 사용한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
배열 원소는 동질적이며 같은 크기로 연속 배치되어 직접 접근을 지원한다.

3. 개발자가 사용하는 배열 인덱스의 성격은?

① 물리 주소 그 자체다. ② 항상 1부터만 시작한다. ③ 원소값과 항상 같다. ④ 실제 메모리 주소와 분리된 추상화된 값이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
인덱스는 개발자에게 제공되는 논리적 순서이며 컴파일 과정에서 실제 주소와 연결된다.

4. C 언어 배열 인덱스의 시작값은?

① 1 ② 0 ③ -1 ④ 배열 크기

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
C 언어의 첫 배열 원소는 인덱스 0으로 접근한다.

5. 추상 자료형 ADT의 구성은?

① 객체와 그 객체에 적용되는 연산의 정의 ② 메모리 주소와 전압 ③ 컴파일러와 운영체제 ④ 입력 장치와 출력 장치

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
ADT는 구현 세부보다 자료 객체와 허용되는 연산을 정의하는 설계 수준의 개념이다.

6. 자료형과 추상 자료형의 관계로 옳은 것은?

① ADT가 반드시 물리 주소만 정의한다. ② 자료형은 연산을 전혀 포함할 수 없다. ③ 자료형은 ADT를 프로그래밍 언어로 구현하는 선언 단계다. ④ 둘은 항상 의미가 반대다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
추상 자료형이 논리적 설계라면 자료형은 메모리를 할당하도록 구체화한 구현이다.

7. create(n) 연산의 기능은?

① i번째 값을 삭제한다. ② 크기가 n인 빈 배열을 생성하고 반환한다. ③ 스택의 top을 감소시킨다. ④ 희소행렬을 전치한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
배열 ADT의 create는 지정한 최대 크기의 빈 배열을 만든다.

8. retrieve(a, i)의 결과는?

① 항상 배열의 크기 ② 배열의 첫 주소만 ③ 새로운 빈 배열 ④ 유효한 i에 해당하는 배열 a의 원소값

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
retrieve는 인덱스가 유효할 때 해당 위치의 값을 반환한다.

9. store(a, i, e)의 기능은?

① 배열 전체를 삭제한다. ② 배열 a의 i번째 위치에 원소 e를 저장한다. ③ i번째 주소를 출력만 한다. ④ 스택을 생성한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
store는 유효한 인덱스 위치에 새 원소값을 기록하는 연산이다.

10. retrieve나 store에서 i가 배열 범위를 벗어나면?

① 자동으로 스택이 된다. ② 첫 원소를 항상 반환한다. ③ 메모리 주소가 0이 된다. ④ 오류를 처리해야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
유효하지 않은 인덱스 접근은 배열 경계를 넘으므로 오류 처리 대상이다.

11. 1차원 배열의 정의로 옳은 것은?

① 하나의 인덱스로 각 원소를 구분하는 한 줄짜리 배열이다. ② 두 인덱스가 반드시 필요하다. ③ 0이 아닌 값만 저장한다. ④ LIFO 방식으로만 접근한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
1차원 배열은 한 개의 순서 축을 가지며 하나의 인덱스로 원소를 선택한다.

12. A[0]의 주소가 a, 원소 크기가 k일 때 A[i]의 주소는?

① a + k/i ② a - i×k ③ a + i×k ④ i + k

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
연속 저장에서 i개 원소만큼 이동하므로 시작 주소에 i×k를 더한다.

13. A[0]의 주소가 a이고 원소 크기가 k일 때 A[3]의 주소는?

① a + k ② 3a + k ③ a - 3k ④ a + 3k

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
세 원소의 크기만큼 시작점에서 이동하므로 a + 3k다.

14. 2차원 배열에 대한 설명으로 옳은 것은?

① 행과 열의 두 인덱스로 원소를 특정한다. ② 인덱스를 사용할 수 없다. ③ 원소 크기가 모두 달라야 한다. ④ 항상 희소행렬이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
2차원 배열은 행과 열 위치를 나타내는 두 인덱스로 원소를 구분한다.

15. 행 우선 저장의 순서는?

① 한 열을 저장한 뒤 다음 열로 간다. ② 대각 원소만 저장한다. ③ 한 행을 연속 저장한 뒤 다음 행을 저장한다. ④ 0이 아닌 원소만 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
행 우선은 같은 행의 열 방향 원소를 먼저 연속 배치한다.

16. 열 우선 저장의 순서는?

① 한 행 전체를 먼저 저장한다. ② 한 열을 연속 저장한 뒤 다음 열을 저장한다. ③ 원소값을 내림차순 정렬한다. ④ top의 원소만 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
열 우선은 같은 열의 행 방향 원소를 먼저 연속 배치한다.

17. C 언어의 2차원 배열 저장 방식은?

① 행 우선 저장 ② 열 우선 저장 ③ 무작위 저장 ④ 삼중항 저장만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
강의록은 C 언어의 2차원 배열이 행 우선 순서로 저장된다고 설명한다.

18. 희소행렬의 정의로 옳은 것은?

① 모든 원소가 0이 아닌 행렬이다. ② 행과 열이 하나뿐인 배열이다. ③ 원소가 문자열인 행렬이다. ④ 0인 원소가 0이 아닌 원소보다 상대적으로 많은 행렬이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
희소행렬은 대부분의 원소가 0인 행렬이다.

19. 희소행렬을 효율적으로 저장하는 삼중항은?

① 주소, 크기, top ② 행, 열, 값 ③ 입력, 처리, 정보 ④ 연산자, 피연산자, 괄호

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
0이 아닌 원소만 그 행 위치, 열 위치, 값과 함께 기록한다.

20. 희소행렬의 삼중항 표현이 유리한 경우는?

① 모든 원소가 서로 다를 때 ② 모든 원소가 0이 아닐 때 ③ 0이 아닌 원소가 전체에 비해 매우 적을 때 ④ 배열 인덱스가 없을 때

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
0이 많은 행렬에서는 0을 생략하고 유효 값만 저장해 메모리를 절약할 수 있다.

3강 예상문제 20선: 스택

1. 스택의 자료 저장 원리는?

① 선입선출(FIFO) ② 무작위 접근만 ③ 우선순위가 가장 낮은 항목부터 ④ 후입선출(LIFO)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
스택은 가장 나중에 삽입된 원소가 가장 먼저 삭제되는 후입선출 구조다.

2. 스택에서 삽입과 삭제가 일어나는 위치는?

① bottom과 middle에서 동시에 ② top ③ 임의의 인덱스 ④ 행렬의 대각선

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
push와 pop은 모두 스택의 한쪽 끝인 top에서 수행된다.

3. 스택에 대한 설명으로 옳은 것은?

① 반드시 무한한 원소를 가진다. ② 두 끝에서만 삽입한다. ③ 0개 이상의 원소를 갖는 유한 순서 리스트다. ④ 원소의 순서를 기억하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
스택은 유한한 순서 리스트이며 원소가 하나도 없는 빈 스택도 허용한다.

4. CreateStack 연산의 기능은?

① 지정된 최대 크기의 빈 스택을 생성한다. ② top 원소를 삭제한다. ③ 모든 원소를 정렬한다. ④ 중위식을 즉시 계산한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
CreateStack은 사용할 수 있는 빈 스택을 만들어 반환한다.

5. Push 연산의 기능은?

① bottom 원소를 삭제한다. ② 스택의 크기를 항상 0으로 만든다. ③ 스택의 top에 원소를 삽입한다. ④ 모든 원소를 출력한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
push는 새 원소를 스택의 가장 위에 추가한다.

6. Pop 연산의 기능은?

① top의 원소를 삭제하고 반환한다. ② 스택 아래에 원소를 추가한다. ③ 배열 주소를 계산한다. ④ 새 스택을 생성하기만 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
pop은 현재 가장 위에 있는 원소를 제거하면서 그 값을 돌려준다.

7. 고정 크기 스택이 가득 찼는데 push하면 발생하는 것은?

① 스택 underflow ② 행 우선 저장 ③ 시간 복잡도 0 ④ 스택 overflow

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
가득 찬 스택에 더 삽입할 공간이 없을 때 overflow가 발생한다.

8. 빈 스택에서 pop하면 발생하는 것은?

① 스택 overflow ② 스택 underflow ③ 희소행렬 변환 ④ 배열 인덱스 증가

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
삭제할 원소가 없는 빈 스택에서 pop을 시도하면 underflow가 발생한다.

9. 배열 스택에서 빈 상태의 top을 -1로 두었다. 첫 push 뒤 top은?

① 0 ② -2 ③ 1 ④ 스택 크기와 항상 같다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
삽입 전에 top을 증가시키므로 -1에서 0이 되고 첫 원소가 stack[0]에 저장된다.

10. 삽입 코드 stack[++top] = item의 의미는?

① 저장 후 top을 감소시킨다. ② top을 바꾸지 않는다. ③ 현재 원소를 삭제한다. ④ top을 먼저 증가시킨 뒤 그 위치에 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
전위 증가 연산이므로 top 증가가 배열 접근보다 먼저 수행된다.

11. 삭제 코드 stack[top--]의 의미는?

① top을 먼저 감소시킨 뒤 아래 원소를 사용한다. ② 현재 top 원소를 사용한 뒤 top을 감소시킨다. ③ top을 증가시켜 삽입한다. ④ 스택을 초기화한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
후위 감소이므로 현재 top 위치의 값을 반환한 다음 top이 하나 줄어든다.

12. 다음 중 스택의 응용이 아닌 것은?

① 서브루틴 복귀 주소 관리 ② 연산자 우선순위에 따른 수식 계산 ③ 배열 원소를 물리 주소와 무관하게 임의 정렬하는 기능 ④ 인터럽트 후 복귀 지점 저장

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
호출 관리와 수식 계산은 LIFO가 필요한 대표 응용이지만 보기의 임의 정렬은 스택 고유 용도가 아니다.

13. 재귀 호출 관리에 스택이 적합한 이유는?

① 가장 오래된 호출만 즉시 삭제하기 때문이다. ② 모든 호출을 동시에 실행하기 때문이다. ③ 호출 순서를 기억할 필요가 없기 때문이다. ④ 가장 최근 호출의 실행 상태부터 복원해야 하기 때문이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
재귀 호출은 마지막에 시작한 호출이 먼저 끝나므로 LIFO 구조와 맞는다.

14. 중위 표기법의 특징은?

① 연산자를 항상 맨 앞에 쓴다. ② 연산자를 항상 맨 뒤에 쓴다. ③ 연산자를 두 피연산자 사이에 쓴다. ④ 연산자를 쓰지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
A+B처럼 연산자가 피연산자 사이에 위치하는 방식이 중위 표기법이다.

15. A+B의 전위 표기는?

① + A B ② A B + ③ A + B ④ B A +

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
전위 표기법은 연산자를 피연산자 앞에 두므로 + A B다.

16. A+B의 후위 표기는?

① + A B ② A B + ③ A + B ④ + B A

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
후위 표기법은 연산자를 두 피연산자 뒤에 둔다.

17. A-((B+K)/D)의 후위 표기로 옳은 것은?

① A B - K + D / ② - A / + B K D ③ A B K + D / - ④ A B K D + / -

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
괄호 안의 B+K를 먼저 BK+로 만들고 D로 나눈 뒤 마지막에 A에서 빼므로 ABK+D/-다.

18. 후위식을 계산할 때 피연산자를 만나면?

① 즉시 두 값을 pop한다. ② 무조건 버린다. ③ 연산자로 바꾼다. ④ 스택에 push한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
피연산자는 이후 연산자가 나타날 때 사용할 수 있도록 스택에 저장한다.

19. 후위식에서 뺄셈 연산자를 만나 두 값을 pop할 때 계산 순서는?

① 먼저 pop한 값 - 나중에 pop한 값 ② 나중에 pop한 값 - 먼저 pop한 값 ③ 두 값을 항상 더한다. ④ pop 순서는 무관하다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
첫 pop은 오른쪽 피연산자, 두 번째 pop은 왼쪽 피연산자이므로 순서를 지켜야 한다.

20. 후위식 369*+의 계산 결과는?

① 57 ② 27 ③ 18 ④ 81

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
6과 9를 곱해 54를 만들고 남아 있던 3을 더하므로 57이다.