신입 웹개발자 기술면접(자료구조)

자료구조

전산 기본

• 배열과 링크드 리스트의 차이점에 대해서 설명해 주세요.

         

          ㄴ>배열은 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근 가능하기에 속도 빠름,

               배열 특성상 삽입/삭제 취약함 모든 데이터 변경해야해서

                 

                연결리스트 인덱스 대신 이전 및 다음 위치 기억, 링크 따라가야만 접근 가능 속도 느림,

                 삽입/삭제 용이

                

             

 

• 스택과 큐에 대해서 설명해 주세요.

        

            ㄴ> 스택 => LIFO 마지막에 넣은것이 첫번째로 나온다 ,삽입 push ,삭제 pop ,스택오버플로우

 

                  큐=> FIFO 먼저 들어온것이 먼저 나간다. enQueue ,deQueue ,머리와 꼬리 구분

 

• 해시테이블에 대해서 설명해 주세요.

           ㄴ> 키,값 으로 데이터 저장. 내부적으로 배열을 사용하여 데이터 저장 key값에

                 해시함수 적용하여 고유 index생성하고 이를 활용하여 저장,검색 저장장소 =버킷,슬롯

트리

• 포화(Perfect) 이진트리, 완전(Complete) 이진트리, 정(Full) 이진트리의 차이점에 대해 각각 설명해주세요.

            ㄴ> 포화 이진트리(Perfect Binary Tree): 모든 레벨에서 노드가 꽉 차있는 트리 의미.

                                                                포화 이진트리는 완전,정 만족.

 

                 완전 이진트리(Complete Bianry Tree): 마지막 레벨을 제외한 나머지 노드들은

                    꽉차있어야하며 마지막 레벨의 노드도 왼쪽으로 몰려있어야함.

 

                 정 이진트리(Full Binary Tree): 트리의 모든 노드가 0개 혹은 2개 자식을 가지는 경우

                         즉 자식 하나만 가진 노드가 없어야 한다.

 

                 

 

• 그래프와 트리의 차이점에 대해서 설명해 주세요.

 

         ㄴ> 그래프: 2개 이상의 경로 가능 노드들 사이에 무방향/방향에서 양방향 경로 가능,

               루트 노드 개념x, 사이클 , 셀프 루프,루프,순회 가능 ,네트워크 모델

 

               트리: 그래프의 특이 케이스 "최소 연결 트리"라고도 함 두 정점 사이 반드시 1개의 경로

                       루프,순회 없음, 한개의 루트 노드만 존재, top-bottom 혹은 bottom-top

                        계층 모델.

 

• 힙 자료구조에 대해 설명해 주세요.

  

          ㄴ> 완전 이진 트리의 구조로 가장 작은 수, 가장 큰수 자주 꺼낼때 유용

 

                 최대 힙: 각 노드의 키 값이 그 자식노드의 키값보다 큰 힙

 

                 최소 힙 : 각 노드의 키값이 그 자식노드의 키값보다 작은 힙

 

• 힙의 삽입과 삭제는 어떻게 이루어지나요?

 

           ㄴ>힙의 삽입: 말단 노드에 데이터 삽입=> 부모노드와 크기 비교=>반복후 위치

 

                 힙의 삭제: 루트 노드 삭제 =>마지막 노드를 루트로 이동=> 루트 자식노드간의 크기비교=>

                                연산 종료

                                

 

• B-Tree에 대해서 설명해 주세요.

           ㄴ> db 와 파일 시스템에서 널리 사용되는 트리 자료구조, 이진트리 확장하여

                 많은 자식 가짐.  대량의 데이터 처리시 유용 ,균형을 맞추는 트리

 

                  노드의 자료수가 N이라면 자식의 수는 N+1, 자료 정렬된 상태여야한다.

                  루트 노드는 적어도 2개이상의 자식. (ex. 5차 b-트리라면 자식노드 5개 의미 )