자료구조 논문 (1)
1. 객관식 문제(문항당 2점, 총 20점)
1. 스택과 큐의 공통된 특징은 다음과 같습니다 ().
A. 엔드포인트에서만 요소의 삽입과 삭제를 허용합니다
B. 모두 선입, 마지막 출국
C. 모두 선입선출입니다
D. 공통 기반이 없다
2. 링크된 방식으로 저장된 큐는 삽입 작업을 수행할 때 삽입됩니다 ().
A. 머리 포인터만 수정됨 B. 헤드와 테일 포인터를 수정해야 합니다
C. 꼬리 포인터만 수정 D. 머리와 꼬리 포인터는 수정이 필요할 수 있습니다
3. 다음 데이터 구조 중 비선형 구조는 무엇인가요? ( )
A. 큐 B. 스택 C. 선형 테이블 D. 이진 트리
4. 2차원 배열 A[m][n]가 존재한다면, A[0][0]가 644(10)에 저장되고 A[2][2]가 676(10)에 저장된다고 가정할 때, 각 요소는 공간을 차지하며, 여기서 A[3][3][3](10)는 저장되어 있나요? 각주 (10)는 십진수로 표현된다고 나와 있습니다.
A.688 B.678 C.692 D.696
5. 트리는 ( )를 표현하는 데 가장 적합합니다.
A. 순서가 정해진 데이터 요소 B. 순서가 없는 데이터 요소
C. 요소 간 분기 계층적 관계를 가진 데이터, D. 요소 간 연결이 없는 데이터
6. 이진 트리의 k번째 계층에 있는 최대 노드 수는 ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. 1차원 배열 A[19]에 저장된 18개의 요소로 구성된 순서 표가 있다면, 첫 번째 요소를 A[1]에 배치하고 이진 탐색을 수행하면, 비교 순서의 첨자는 ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. n개의 레코드 파일을 빠르게 정렬하면 필요한 보조 저장 공간은 대체로 동일합니다
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. 해시 저장용 선형 테이블(7, 34, 55, 25, 64, 46, 20, 10)에서, 해시 함수로 H(K)=K %9를 선택하면 해시 주소가 1인 ( ) 요소가 존재한다.
A.1 B.2 C.3 D.4
10. 6개의 노드가 있는 무방향 그래프, 그리고 그래프는 연결된 그래프를 보장하기 위해 최소 ( ) 이상의 간선을 가져야 합니다.
A.5 B.6 C.7 D.8
2. 빈칸 채우기 (빈칸당 1점, 총 26점)
1. 알고리즘의 품질은 보통 네 가지 측면에서 평가됩니다: _________, _________, _________, _________.
2. 알고리즘의 시간 복잡도는 (n3+n2log2n+14n)/n²이며, 그 크기의 순서는 ________로 표현됩니다.
3. 트리의 일반화된 표가 A(C,D(E,F,G), H(I,J))로 표현된다면, 트리에 포함된 노드 수는 __________이고, 트리의 깊이는 ___________이며, 트리의 차수는 _________이다.
4. 접미사 공식 9 2 3 +- 10 2 / - 의 값은 __________. 중간 공식(3+4X)-2Y/3에 대응하는 접미사 공식은 _______________________________입니다.
5. 이진 트리가 연결 리스트와 함께 저장된다면, 각 노드는 데이터 필드 외에도 왼쪽 자식과 오른쪽 자식으로 가는 두 개의 포인터를 가집니다. 이 저장 구조에서 n개의 노드를 가진 이진 트리는 총 ________개의 포인터 필드를 가지며, 이 중 ________ 포인터 필드는 주소를 저장하고 ________________ 포인터는 빈 포인터입니다.
6. n개의 정점과 E-바 간선을 가진 방향 그래프와 무방향 그래프의 경우, 해당 인접 테이블에는 각각 _______간선과 ________개의 간선 노드가 있다.
7. AOV 네트워크는 ___________________ 그래프입니다.
8. 정점이 n개인 무방향 완전 그래프에서는 간선이 ________개이고, 정점이 n개인 방향 완전 그래프에서는 간선이 ________ 개입니다.
9. 선형 표가 (12,23,74,55,63,40)라고 가정할 때, 동일한 잔여의 원소들이 키 % 4 조건에 따라 하위 표가 되면, 얻어진 네 개의 부분표는 ____________________________, ___________________, _______________________, __________________________이다.
10. B_ 트리에 요소를 삽입하는 과정에서, 트리의 루트 노드가 최종적으로 분할되면 새 트리의 높이가 원래 트리보다 ___________ 됩니다.
11. 힙 정렬 과정에서 분기 노드를 체로 걸러내는 시간 복잡도는 ________하며, 전체 힙 정렬 과정의 시간 복잡도는 ________.
12. 빠른 정렬, 힙 정렬, 병합 정렬에서는 정렬_________ 안정적입니다.
자료구조 논문 (2)
1. 객관식 문제 (24점)
1. 다음의 선형 표 설명은 부정확하다().
(A) 선형 테이블은 순차적으로 저장되며 연속된 저장 공간을 차지해야 합니다
(b) 선형 테이블은 체인 형태이며 연속적인 저장 공간을 차지하지 않습니다
(C) 삽입 및 삭제 작업을 용이하게 하기 위해 체인 저장 장치로 선형 테이블이 구현됩니다
(d) 삽입 및 삭제 작업을 용이하게 하기 위해 순차 저장 장치로 선형 테이블을 구현합니다
2. 허프만 트리의 총 리프 노드 수가 m이고, 이진 연결 리스트를 저장 구조로 사용한다면, 허프만 트리에는 총 ( ) 빈 포인터 필드가 있습니다.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. 순차 루프 큐 Q[0:M-1]의 헤드 포인터와 테일 포인터가 각각 F와 R이고, 헤드 포인터 F는 항상 헤드 요소의 이전 위치를 가리키고, 테일 포인터 R은 항상 테일 요소의 현재 위치를 가리키면, 루프 큐 내 요소 수는 ( )입니다.
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. 이진 트리의 중간 순서 탐색 순서가 ABCD이고 이전 순서 탐색 순서가 CABD라면, 다음 순서로 이진 트리를 탐색하여 얻은 순서는 ()입니다.
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5. 완전히 방향이 없는 그래프에 n개의 정점이 있다고 가정하면, 완전히 방향이 없는 그래프에는 ( ) 간선이 존재한다.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. 이진 트리에 2000개의 노드가 있다고 가정하면, 이진 트리의 최소 높이는 ( )입니다.
(A) 9 (B) 10 (C) 11 (D) 12
7. 방향 그래프에 n개의 정점이 있다고 가정하자, 인접 테이블에는 방향 그래프에 대응하는 헤더 노드가 있다.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. 초기 레코드 키워드 시퀀스 집합(5, 2, 6, 3, 8)을 설정하고, 첫 번째 레코드 키워드 5를 기반으로 빠른 정렬 결과가 ( )입니다.
(A) 2,3,5,8,6 (B) 3,2,5,8,6
(C) 3,2,5,6,8 (D) 2,3,6,5,8
2. 빈칸 채우기 (24점)
1. 해시 조회 기술을 효과적으로 적용하기 위해서는 ____________________와 __________________________ 두 가지 문제를 해결해야 합니다.
2. 다음 프로그램 세그먼트의 기능은 데이터 x를 스택에 구현하며, 밑줄에 올바른 문장을 채워야 합니다.
typedefstruct {int s[100]; 내트 상단; } sqstack;
Void Push(sqstack&stack,int x)
{
if(stack.top==m-1) printf("overflow");
그렇지 않으면 {____________________; _________________; }
}
3. 이진 정렬 트리를 중간 순서로 순회하여 얻은 수열은 ___________ 수열(정렬된 채워진 순서 또는 무순서 순서)이다.
4. 빠른 정렬의 가장 큰 시간 복잡도는 ___________이며, 평균 시간 복잡도는 __________입니다.
5. 이진수 내 차수가 0인 노드의 수가 N0이고 차수가 1인 노드 수가 N1이라면, 이진 트리에서 차수가 2인 노드의 수는 _________이다; 이진 연결 리스트가 이진 트리의 저장 구조로 사용된다면, 이진 트리에는 빈 포인터 필드가 _______ 존재합니다.
6. 특정 무방향 그래프에서 정점과 간선의 수가 각각 n과 e이고, 모든 정점의 차수의 합이 d라고 가정하면, e = _______이다.
7. 초기 레코드 키워드 시퀀스가 (55, 63, 44, 38, 75, 80, 31, 56)이라면, 스크리닝 방법으로 설정된 초기 힙은 ___________________________됩니다.
8. 방향 그래프의 인접 테이블 저장 구조는 다음과 같다는 것이 알려져 있습니다: 정점 1에서 DFS 탐색의 출력 시퀀스는 다음과 같습니다:
, BFS 통과의 출력 수열은 다음과 같습니다.
자료구조 논문 (3)
1. 객관식 문제 (질문당 1점, 총 20점)
1. 데이터 구조의 이진 형태가 A=(D,R), D={01,02,03,04,05,06,07,08,09}, R={r}, r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}이라면, 데이터 구조 A는 ( )입니다.
(A) 선형 구조 (B) 트리 구조 (C) 물리적 구조 (D) 그래픽 구조
2. 다음 프로그램의 시간 복합체는 ()
for(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i; J++) t=t*j; s=s+t; }
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3. 포인터 변수 p를 단일 연결 리스트에서 노드 A를 가리키도록 설정하세요. 단일 연결 리스트에서 노드 A를 삭제하면 포인터의 연산 순서를 ()로 변경해야 합니다.
(A) q=p->다음; p->data=q->data; p->next=q->next; free(q);
(B) q=p->다음; q->data=p->data; p->next=q->next; free(q);
(C) q=p->다음; p->next=q->next; free(q);
(D) q=p->다음; p->data=q->data; free(q);
4. 정렬해야 할 n개의 레코드 키워드가 있을 경우, ( ) 보조 레코드 단위가 힙 정렬에 필요합니다.
(A) 1 (B) n (C) nlog2n (D) n2
5. 초기 키워드 레코드 키워드가 (20, 15, 14, 18, 21, 36, 40, 10)이라면, 20을 기준으로 기록한 빠른 정렬 종료 후 결과는 ( )입니다.
(A) 10, 15, 14, 18, 20, 36, 40, 21
(B) 10, 15, 14, 18, 20, 40, 36, 21
(C) 10, 15, 14, 20, 18, 40, 36, 2l
(D) 15, 10, 14, 18, 20, 36, 40, 21
6. 이진 정렬 트리에 n개의 노드가 있다고 가정하면, 이진 정렬 트리의 평균 조회 길이는 ( )입니다.
(A) O(1) (b) O(로그2n) (C) (D) O(n2)
7. 무방향 그래프 G에 n개의 정점 e 간선이 있다고 가정하면, 해당 인접 테이블의 헤더 노드와 테이블 노드 수는 ( )입니다.
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. 강한 연결 그래프에 n개의 정점이 있다고 가정하면, 강한 연결 그래프에는 최소 ( ) 개의 간선이 존재한다.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. 정렬해야 할 레코드 키워드가 5000개이므로, 가장 작은 10개 레코드 키워드를 가장 빠르게 선택해야 할 경우, 다음 ( ) 방법을 사용할 수 있습니다.
(A) 빠른 정렬 (B) 힙 정렬 (C) 병합 정렬 (D) 정렬 삽입
10. 다음 네 가지 유형의 ( )가 가장 큰 공간적 복잡성을 가진다.
(A) 삽입 정렬 (B) 버블링 정렬 (C) 힙 정렬 (D) 병합 정렬
2. 빈칸 채우기 (빈칸당 1점, 총 20점)
1. 데이터의 물리적 구조는 주로 두 가지 상황을 포함합니다: _____________와 ______________.
2. 완전 이진 트리에 500개의 노드가 있다면, 이진 트리의 깊이는 __________; 완전한 이진 트리의 저장 구조로 이진 연결 리스트를 사용한다면, 빈 포인터 필드가 ___________ 있습니다.
3. 입력 시퀀스가 1, 2, 3이라면, 스택의 동작 후 ___________ 가지 다른 출력 시퀀스를 얻을 수 있습니다.
4. 인접 행렬 A[n][n]를 그래프 G의 저장 구조로 사용하면, 인접 행렬 내 행 i 행의 모든 요소의 합은 정점 i의 ________과 같고, 열인 i의 모든 요소의 합은 정점 i의 ________과 같다.
5. 허프만 트리에 노드가 n개라면, 차수가 1인 노드가 ________ 존재한다.
6. 방향 그래프 G에 방향성 간선을 가진 정점 e가 n개이고, 차수에 들어오는 모든 정점의 합이 d이라면, e와 d의 관계는 _________한다.
7. 이진 정렬 트리의 노드를 __________ 탐색하면 키워드(채워진 키워드, 중간, 사후 키워드)의 점진적 시퀀스를 얻을 수 있습니다.
8. 조회 테이블에 100개의 요소가 있다면, 이분법 탐색 방법을 사용해 데이터 요소 X를 찾을 때, 데이터 요소 X가 조회 테이블에 있는지 확인하기 위해 최대 ________번까지 비교해야 합니다.
9. 순차 저장 구조를 가진 스택이든 체인 저장 구조를 가진 스택이든, 인스택과 아웃스택 연산의 시간 복잡도는 ____________.
10. n개의 노드를 가진 완전 이진 트리로, 위에서 아래, 왼쪽에서 오른쪽으로 1부터 순서대로 번호가 매겨지면, i번째 노드의 부모 노드는 ____________, 오른쪽 자식 노드의 번호는 ___________이다.
11. 기록된 키워드의 초기 집합이 (72, 73, 71, 23, 94, 16, 5)이라면, 레코드 키워드 72를 기반으로 한 빠른 정렬 결과가 ___________________________됩니다.
12. 방향 그래프 G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>} 집합이 있다면, 그래프의 위상 수열은 ____________________된다.
13. 다음 알고리즘은 순차 해시 리스트에서 x의 값을 가진 키워드를 구현하므로, 밑줄에 올바른 문장을 입력해 주세요.
struct record{int key; 다른 이들; };
IntHashsqSearch(struct 레코드 해시테이블[ ],int k)
{
인티,J; j=i=k % p;
while (해시테이블[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; 만약 (i==j) 반환(-1); }
만약 (_______________________) 이면(j)를 반환한다; 그렇지 않으면 반환(-1);
}
14. 다음 알고리즘은 이진 정렬 트리에서 키 값 k를 구현하므로, 밑줄에 올바른 문장을 입력해 주세요.
TypeDefstruct Node{int key; struct node *lchild; struct node *rchild; }비트리;
bitree *bstsearch(bitree *t, int k)
{
만약 (t==0) 이면 return(0); 그렇지 않으면 (t!=0)
만약 (t->key==k)_____________; 그렇지 않으면 (t->key>k) t=t->lchild; else_____________;
}
자료구조 시험지 (1) 답변을 참조하라.
1. 객관식 문제 (질문당 2점, 총 20점)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. 빈칸 채우기 (빈칸당 1점, 총 26점)
1. 정확성, 가독성, 강력함, 그리고 높은 효율성
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5.2n n-1 n+1
6.e 2e
7. 방향성 및 비회로
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. 1 덧셈
11.O(log2n) O(nlog2n)
12. 통합
다른 시험 문제의 답은 다음과 같이 확인할 수 있습니다:
관광객 여러분, 이 게시물의 숨겨진 내용을 보고 싶으시다면 부탁드립니다 회답
|
게시됨 2014. 11. 25. 오후 12:46:30
|
|
|
게시됨 2014. 12. 30. 오전 12:10:55