한국어
메뉴

자료 구조와 알고리즘

역폴란드 표기법(후위 표기법)으로 쓴 식 '3 4 + 2 * 5 −'를, 수가 오면 스택에 쌓고 연산자가 오면 두 값을 꺼내 계산하여 결과를 쌓는 방법으로 평가했다. 결과는 얼마인가? 여기서 연산자의 왼쪽 값은 먼저 쌓인 쪽의 값으로 한다.

  1. A−9
  2. B6
  3. C9
정답과 해설 보기

정답: C. 9

3, 4를 쌓고 +에서 꺼내어 3 + 4 = 7을 쌓습니다. 다음으로 2를 쌓고 *에서 7 × 2 = 14를 쌓습니다. 5를 쌓고 −에서 먼저 쌓인 14에서 나중의 5를 빼어 14 − 5 = 9가 결과입니다. 후위 표기법은 연산 순서가 나열 순서로 정해지므로 괄호가 필요 없으며, 보통의 식으로는 (3 + 4) × 2 − 5에 해당합니다. −9는 뺄셈의 좌우를 바꿔 계산한 값, 6은 괄호 없이 3 + 4 × 2 − 5로 읽은 값입니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 해시 테이블에서 충돌(collision)에 대한 설명으로 올바른 것은?
  2. 크기 7인 해시 테이블(위치 0~6)에 해시 함수 h(k) = k mod 7로 키 10, 17, 24, 3을 이 순서로 저장한다. 충돌했을 때는 위치를 하나씩 뒤로 옮기며(6 다음은 0) 빈 위치를 찾는 선형 탐사법을 사용한다. 키 3이 저장되는 위치는?
  3. 해시 테이블의 충돌을 처리하는 방법으로 체이닝(같은 위치의 원소를 연결 리스트로 잇는다)과 개방 주소법(표 안의 비어 있는 다른 위치를 찾는다)을 비교한 설명으로 올바른 것은? 적재율은 저장한 원소 수를 표의 크기로 나눈 값으로 한다.
  4. 배열 가운데의 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 이진 탐색을 사용하기 위한 전제 조건으로 올바른 것은?
  5. 오름차순으로 정렬된 서로 다른 1,000개의 값에서 이진 탐색으로 값을 찾는다. 1회의 비교로 '일치·더 작다·더 크다'를 알 수 있다고 하면, 찾는 경우와 찾지 못하는 경우를 모두 포함하여 비교 횟수는 최대 몇 회인가?