Lecture/자료구조/2004

개요

• 교수 : 박상원
• 조교 : 한민규

교재

• 이석호, "자료구조와 C", 정익사

평가

• 중간고사 : 30%
• 기말고사 : 30%
• 과제 : 30%
• 출석 : 10%
• 주의 : 5회이상 결석시 F

중간고사

• 일시 : 2004년 4월 14일
• 범위 : 1장 - 4장
• 시험문제
• Quiz : 2004년 4월 21일
  • 중간고사 시험문제 중 1문제
  • 퀴즈 점수는 중간고사 점수에 합산

기말고사

• 일시 : 2004년 6월 16일
• 범위 : 5장 - 9장
• 시험문제

교안

• Q&A

1. 소프트웨어 공학과 프로그래밍 기법
2. 순차 데이타 표현
3. 연결 데이타 표현
4. 스택
5. 큐
6. 트리
7. 이원탐색트리
8. 그래프
9. 가중치 그래프
10. 정렬
11. 균형 탐색 트리

과제

1. 연습문제 1.10, 1.18 (3월 19일까지)
2. 희소행렬의 전치행렬 구하기 (4월 7일까지)
   • 입력 : 행수, 열수, 0이 아닌 항의 갯수, 실제 항
   • 출력 : transpose 한 행렬
3. 자료구조 : 배열을 이용할 것 (p.81 참조)
   • 주의 : C와 C++ 각각으로 작성하여 제출할 것. C++로 작성할 때는 SparseMatrix 클래스를 정의하고 그 클래스의 멤버함수로 transpose 함수를 만들것.
   • 제출 : 소스 코드 및 설명 제출 후, 조교에게 프로그램 실행 결과 검사
4. 연산자 우선 순위를 고려한 수식 계산 (4월 23일까지)
   • 입력 : 중위식으로 표현된 수식

     예: 2+(32-8*12)

   • 키보드로 임의의 수식을 입력받고 그 수식의 값을 화면에 출력
   • 출력 : 후위식으로 표현한 결과와 수식연산의 결과

     예: 2 32 8 12 * - +, -62

   • 주의 : C와 C++ 각각으로 작성하여 제출할 것. C++로 작성할 경우 적당한 클래스를 정의해야 함(예: Stack)
   • 제출 : 소스 코드 및 설명 제출 후, 조교에게 프로그램 실행 결과 검사
5. 이중 연결 리스트를 이용한 덱(deque) 작성 (5월 10일까지)
   • insertFirst, insertLast, deleteFirst, deleteLast 작업을 할 수 있는 4개의 메뉴를 화면에 띄우고 사용자의 입력을 받아 적절한 작업을 수행한다. 입력 데이타는 문자열(이름)을 입력으로 받는다.
   • delete 시에는 덱에서 꺼내진 데이타를 화면에 출력한다.
   • C와 C++ 중 한가지 선택
   • 제출 : 소스 코드 및 설명 제출 후, 조교에게 프로그램 실행 결과 검사
6. 이진트리순회 (5월 24일까지)
   • 재귀적 기법을 이용하여 이진트리를 순회하는 함수 작성
   • 3가지 순회방법 : 전위, 중위, 후위 순회
   • 입력 데이타 : 입력되는 숫자를 이진탐색트리 형태로 저장
   • C와 C++ 중 한가지 선택
   • 제출 : 소스 코드 및 설명 제출 후, 조교에게 프로그램 실행 결과 검사
7. 최대 히프(max heap) 작성 (6월 7일까지)
   • 최대 히프를 배열을 이용하여 작성
   • 입력되는 데이타는 정수로 한다.
   • 메뉴 구성 : 삽입, 삭제, 종료의 3가지 메뉴로 구성
   • C와 C++ 중 한가지 선택
   • 제출 : 소스 코드 및 설명 제출 후, 조교에게 프로그램 실행 결과 검사