출석체크하기
컴퓨터과학과
컴퓨터과학과 입학생, 재학생, 교수, 조교, 예비입학생분들을 위한 게시판입니다.
조회 수 52 추천 수 1 댓글 3

 

  1. 자료구조의 개념

자료 구조는 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것을 말한다.

  • 자료구조는 자료의 표현과 그것과 관련된 연산이다.
  • 자료구조는 일련의 자료들을 조직하고 구조화하는 것이다.
  • 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이 가능하다.
  • 자료구조에 따라 프로그램의 실행시간이 달라진다.
     
  1. 자료구조의 분류
  • 선형구조
    • 리스트(List)
      • 선형 리스트(Linear List)
      • 연결 리스트(Linked List)
    • 스택(Stack)
    • (Queue)
    • 데큐(Deque)
  • 비선형구조
    • 트리(Tree)
    • 그래프(Graph)
       
  1. 자료 구조의 이용
  • 정렬(Sort) : 기억장치 내의 자료를 일정한 순서에 의해 나열하는
  • 검색(Search) : 기억장치 내의 자료를 찾는
  • 파일편성 : 자료를 기억 매체에 젖아할 때의 파일구조
  • 인덱스 : 파일에서 특정 자료를 빠르게 찾기 위한 색인표

 

  1. 순차 리스트(Sequential List) 아닌 것은?
    1. 배열(Array)
    1. 트리(Tree)
    1. 데크(Deque)
    2. 스택(Stack)
      • 순차 리스트란 선형 자료 구조를 말한다. 배열도 순차 리스트 구조에 속한다.
         
  2. 순차적인 선형 구조(Sequntial Linear Structure) 해당되는 자료 구조는?
    1. 트리
    2. 연결 리스트
    3. 그래프
      • 순차적인 선형 구조란 자료가 기억공간에 연속적으로 저장되는 자료구조로서 스택, , 데크, 배열 등이 해당된다. 연결 리스트(Linked List) 자료를 연속된 공간이 아닌 임의의 기억공간에 저장시키고 포인터를 따라 순차적으로 접근하기 때문에 선형 구조이기는 하지만 순차적인 선형 구조(연접 리스트) 아니다.
         
  3. 효율족인 프로그램을 작성할 가장 우섡적인 고려사항은 저장 공간의 효율성과 실행시간의 신속성이다. 자료구조의 선택은 프로그램 실행시간에 직접적인 영향을 준다. 자료구조에 관한 설명으로 거리가 것은?
    1. 자료구조는 자료의 표현과 그것과 관련된 연산이다.
    2. 자료구조는 일련의 자료들을 조직하고 구조호하하는 것이다.
    3. 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이 가능하다.
    1. 처리할 문제가 주어지면 평소에 주로 사용하던 자료구조를 적용하는 것이 좋다.
      • 자료구조에 따라 프로그램의 실행시간이 달라지므로 처리할 문제에 어울리는 적절한 자료구조를 선택하는 것이 좋다.

 

  • 선형 리스트
    • 선형 리스트는 배열과 같이 연속되는 기억장소에 저장되는 리스트를 말한다.
    • 연접 리스트(Dense List) 또는 축자 구조(Sequential Structure)라고도 한다.
    • 대표적인 선형 리스트 자료구조 : 배열(Array)
  • 특징
    • 가장 간단한 자료구조이다.
    • 접근 속도가 빠르다.
    • 중간에 자료를 삽입하기 위해서는 연속된 공간이 있어야 한다.
    • 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다.
    • 자료의 개수가 n개일 삽입 시의 평균 횟수는 𝑛+12이고, 삭제 시에는 𝑛−12이다.
    • 삽입, 삭제 자료의 이동이 필요하기 때문에 작업이 번거롭다.

# 선형 리스트는 빈 공간이 없이 차례차례 저장된다.

 

  • 연결 리스트
    • 연결 리스트는 자료들을 반ㄷ느시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시키는 자료구조이다.
  • 특징
    • 노드의 삽입, 삭제 작업이 용이하다.
    • 기억공간이 연속적으로 놓여 있지 않아도 저장이 가능하다.
    • 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억공간 이용 효율이 좋지 않다.
    • 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.
    • 중간 노드 연결이 끊어지면 다음 노드를 찾기 힘들다.
    • 희소 행렬을 연결 리스트로 표현하면 기억장소가 절약된다.
    • 트릴르 표현할 가장 적합한 자료구조이다.
  • 연결 리스트의 종류
    • 단순 연결 리스트(Singly Linked List)
    • 단순 환상 연결 리스트(Singly Circular Linked List)
    • 이중 연결 리스트(Doubly Linked List)
    • 이중 환상 연결 리스트(Doubly Circular Lunked List)
  • #
    • 노드(Node) : 자료를 젖아하는 데이터 부분과 다음 노드를 가리키는 포인터인 링크 부분으로 구성된 기억공간

Data 부분

Link 부분

 

  • 포인터(Pointer) : 현재 2위치에서 다음 노드의 위치를 알려주는 요소
    • 프런트 포인터(F, Front Pointer) : 리스트를 구성하는 최초의 노드 위치를 가리키는 요소
    • 포인터(Null Pointer, Nil Pointer) : 0 또는 , \0으로 표시하며, 마지막 녿브의 링크 부분에 일반적으로 사용하는 것으로, 다음 노드가 없음을 나타내는 포인터
  • 희소 행렬(Sparrse Matrix) 행렬의 요소 많은 항들이 0으로 되어 있는 형태로, 기억장소를 절약하기 위해 링크드 리스트를 이용하여 저장한다.
  • 트리는 정점(Node) 선분(Branch, 가지) 이용하여 사이클을 이루지 않도록 구성한 Graph 특수한 형태이다.
  1. 선형 리스트의 특징이 아닌 것은?
    1. 가장 간단한 데이터 구조 하나이다.
    2. 배열과 가팅 연속되는 기억장소에 저장되는 리스트를 말한다.
    3. 기억장소 효율을 나타내는 메모리 밀도가 1이다.
    1. 데이터 항목을 추가, 삭제하는 것이 용이하다.
      • 선형 리스트는 배열과 같이 연속되는 공간에 차례대로 저장된 구조로 데이터를 추가하거나삭제할 자료의 이동이 많으므로 불편하다.
         
  2. 연결 리스트에 대한 설명으로 거리가 것은?
    1. 노드의 삽입이나 삭제가  쉽다.
    1. 노드들이 포인터로 연결되어 검색이 빠르다.
    1. 연결을 해주는 포인터를 위한 추가 공간이 필요하다.
    2. 연결 리스트 중에서 중간 노드 연결이 끊어지면 다음 노드를 찾기 힘들다.
      • 포인터로 연결되어 있어 포인터를 찾아가는 시간이 필요하므로 선형 리스트에 비해 접근 속도가 느리다.
         
  3. 연결 리스트에 대한 설명으로 거리가 것은?
    1. 노드의 삽입과 삭제가 용이하다.
    2. 연속적으로 기억공간이 없어도 저장이 가능하다.
    1. 연접 리스트나 배열보다 기억공간이 절약된다.
    1. 희소 행렬을 표현하는데 사용된다.
      • 포인터를 저장시킬 공간이 필요하므로 연접 리스트에 비해 기억 공간이 낭비된다.
         
  4. 희소 행렬을 연결 리스트로 표현할 가장 장점은?
    1. 기억장소가 절약된다.
    1. 임의 위치 액세서가 가능하다.
    2. 이진 검색이 가능하다.
    3. 행렬 간의 연산을 줄일 있다.
      • 희소 행렬은 행렬의 요소 많은 항들이 9으로 되어 있는 형태로, 연결 리스트에서는 포인터를 이용하여 필요 없는 0 제외하고 기억시킬 있으므로 기억장소가 절약된다.
         
  5. 포인터를 사용하여 리스트를 나타냈을 때의 설명 옳지 않은 것은?
    1. 새로운 노드의 삽입이 쉽다.
    2. 기억공간이 많이 소요된다.
    3. 리스트를 여러 개의 리스트로 분리하기 쉽다.
    1. 노드를 리스트에서 삭제하기 어렵다.
      • 포인터와 링크는 같은 말이다. 링크는 다음 노드의 위치를 가리킨느 주소로서 리스트에서 특정 노드를 삭제할 때는 노드와 연결된 링크를 끊으면 간단하게 삭제된다.

 

 

  • 스택
  • 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다.
  • 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO) 방식으로 자료를 처리한다.
    • TOP
      • 스택으로 할당된 기억공간에 갖아 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소
      • 스택 포인터(SP, Stack Pointer)라고도 한다.
    • Bottom : 스택의 가장 밑바닥이다.

 

  • 삽입

Top=Top+1
if Top > M Then
   Overflow
else
  X(Top) <- item

스택 포인터(Top)을 1 증가시킨다.
스택 포인터가 스택의 크기보다 크면 Overflow
그렇지 않으면 item이 가지고 있는 값의 스택의 Top 위치에 삽입한다.

  • M : 스택의 크기
  • TOP : 스택 포인터
  • X : 스택의 이름
  • Overflow : 스택으로 할당받은 메모리 부분이 마지막 주소가 M번지라고 , Top Pointer 값이 M보다 커지면 스택의 모든 기억장소가 채워져 있는 상태이므로 이상 자료를 삽입할 없어 Overflow 발생시킨다.
     
  • 삭제

if Top = 0 Then
   Underflow
else
  item <- X(Top)
  Top = Top-1

스택 포인터가 0이면 스택의 바닥이므로 더 이상 삭제할 자료가 없으므로 Undderflow를 처리한다.
그렇지 않으면, Top 위치에 있는 값을 item으로 옮기고 스택 포인터를 1 감소시킨다.

  • 스택에 기억되어 있는  자료를 삭제시킬 때에는 제일 먼저 삭제할 자료가 있는지 없는지부터 확인한다.
  • Underflow : Top Pointer 주소 0 가지고 있다면 스택에는 삭제할 자료가 없으므로 Underflow 발생시킨다.
  • 스택의 응용분야
    • 프로그램 호출 복귀주소를 저장할
    • 함수 호출의 순서 제어
    • 인터럽트가 발생하여 복귀주소를 저장할
    • 후위 표기법(Postfix Notation)으로 표현된 수식을 연산할
    • 0주소 지정방식 명령어 자료 저장 방식을 사용할
    • 재귀(Recursive) 프로그램의 순ㄴ서 제어
    • 컴파일러를 이용한 언어 번역

 

회원가입 후 로그인을 하면 모든 광고가 사라집니다
  • ?
    떠히님 2021.11.07 15:05

    비회원은 작성 1년 이내의 댓글을읽을 수 없습니다.

    로그인 후에 바로 열람 가능합니다
  • ?
    큐런 2021.11.26 19:24

    비회원은 작성 1년 이내의 댓글을읽을 수 없습니다.

    로그인 후에 바로 열람 가능합니다
  • ?
    이메일이사라짐 2021.11.30 16:15

    비회원은 작성 1년 이내의 댓글을읽을 수 없습니다.

    로그인 후에 바로 열람 가능합니다

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
Hot글 3학년 컴퓨터 과학과 편입하고 보니 8 쑤국새 2021.09.07 146
공지 공부자료를 공유해주시면 다음 후배들에게 큰 도움이 됩니다. 1 file 방송대커뮤니티 2021.11.07 45
공지 포인트 코인을 얻는방법 (파일 다운로드 방법) 294 updatefile 방송대커뮤니티 2021.01.06 1943
253 3학년 3-2 컴파일러구성 (기말시험, 대체시험, 하계계절시험 기출문제) 2015~2019 3 file 제로스 2021.11.29 13
252 3학년 3-2 컴퓨터구조 (기말시험, 대체시험, 하계계절시험 기출문제) 2015~2019 3 file 제로스 2021.11.29 17
251 2학년 2-2 선형대수 기말시험, 대체시험, 하계계절시험 기출문제 2015~2019 file 제로스 2021.11.29 8
250 2학년 2-2 자료구조 기말시험, 대체시험, 하계계절시험 기출문제 2015~2019 file 제로스 2021.11.29 11
249 2학년 2-2 프로그래밍언어론 기말시험, 대체시험, 하계계절시험 기출문제 2015~2019 file 제로스 2021.11.29 4
248 일반글 <C++프로그래밍> 교과목 기말대비 김남희 튜터님 온라인 특강 안내 제로스 2021.11.28 11
247 2학년 선형대수, 자료구조, 프로그래밍언어론(15~19 기말,대체 기출시험모음) 12 file 서예지(국문과) 2021.11.08 41
246 1학년 [컴과1] C++프로그래밍, 멀티미디어시스템, 컴퓨터과학개론(15~19 기말,대체 기출시험모음) 7 file 서예지(국문과) 2021.11.08 33
245 3학년 [컴과3] JSP프로그래밍, UNIX시스템, 데이터베이스설계 및 구현 (15~19 기말,대체 기출시험모음) 26 updatefile 서예지(국문과) 2021.11.08 43
244 3학년 [컴과3] 컴파일러구성, 컴퓨터구조 (15~19 기말,대체 기출시험모음) 10 file 서예지(국문과) 2021.11.08 26
243 4학년 [컴과4] HTML5, 시뮬레이션, 인공지능(15~19 기말,대체 기출시험모음) 2 file 서예지(국문과) 2021.11.08 10
242 4학년 [컴과4] 컴퓨터그래픽스, 컴퓨터보안 15~19 기말,대체 기출시험모음 file 서예지(국문과) 2021.11.08 7
241 4학년 [컴과4] 모바일앱프로그래밍, 소프트웨어공학, 정보통신망(15~19 기말,대체 기출시험모음) file 서예지(국문과) 2021.11.08 10
240 3학년 HTML 웹프로그래밍, 데이터베이스시스템, 디지털논리회로 (15~19기말, 대체 기출시험 자료모음) 1 file 서예지(국문과) 2021.11.08 12
239 3학년 [컴과3] (알고리즘, 운영체제 기말시험) 기출문제모음 기말,대체,계절시험 file 서예지(국문과) 2021.11.08 16
238 1학년 C프로그래밍, 유비쿼터스컴퓨팅개론 file 서예지(국문과) 2021.11.08 11
237 1학년 [컴과1] 인터넷과 정보사회 file 서예지(국문과) 2021.11.08 10
236 2학년 [컴과2] Java 프로그래밍, Visual C++ 프로그래밍, 이산수학 file 서예지(국문과) 2021.11.08 16
235 3학년 그래픽커뮤니케이션 기말대비입니다. file 서예지(국문과) 2021.11.08 5
234 1학년 [컴퓨터과학기초] 총정리 1-2 1 file 서예지(국문과) 2021.11.08 8
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 13 Next
/ 13