008 학년도중등교사신규임용후보자선정경쟁시험 ( ) 교시정보 컴퓨터 ( ) 문항 ( 80 ) 점작성시간 ( 50 ) 분감독관확인 ꄫ 문답지전체면수가맞는지확인하시오. 문답지모든면의상단해당란에수험번호와성명을쓰시오. 지워지거나번지지않는흑색필기구를사용하여답안을작성하시오. 답안을수정할때에는두줄 ( ) 을긋고수정할내용을쓰시오. 다음의경우에는채점하지않고 0 점으로처리합니다. 연필로작성된문항 수정테이프나수정액을사용하여수정된문항 개인정보가노출되어있거나불필요한표시가되어있는문답지전체 각문항에대한답은문답지의답란에쓰되, 주어진조건에맞게쓰시오. [~. 다음글을읽고물음에답하시오. 최근컴퓨터과학의원리를교육하기위하여언플러그드 (unplugged) 교육방법이대두되고있다. 이방법은컴퓨터없이컴퓨터를 학습하는방법으로이를통해컴퓨터과학의원리및개념을다양한오프라인활동과게임및퍼즐등을활용하여가르칠수있다. K 교사는이러한언플러그드교육방법으로 GIF 이미지의압축원리를지도하기위하여다음과같은학습활동지를준비하였다. ( 단, 학습활동지에있는원본이미지( 꽃 ) 에서는흰색, 는빨간색, 는노란색, 는초록색, 는파란색을 나타낸다.) < 학습활동지> 원본이미지( 꽃 ) GIF 압축과정 단계( 문자표현) 단계 단계(LZW) WWRRRRWW WRW a WRRYYRRW WRYRW b WRRYYRRW WRYRW WWRRRRWW WRW a GWBWG c GWBWG c WGGBBGGW d WWGGGGWW WGW e 조건. 원본이미지는왼쪽에서오른쪽방향으로, 위쪽에서아래쪽방향으로압축하여표현한다. 조건. 압축과정은 단계 단계 단계의순서로진행된다.. K 교사가위 < 학습활동지 > 를이용하여학생들에게 GIF 압축과정을설명하고자한다. GIF 압축과정 단계, 단계, 단계의내용을 K 교사가어떻게설명할수있을지각각 줄이내로기술하시오. [ 점 단계: 단계: 단계:. 위 < 학습활동지 > 의 ~ 에들어갈내용을쓰고, 단계에적용된압축기술을무엇이라고하는지영어약자로쓰시오. [ 점 압축기술 : 면 )
. 다음은협동학습방법을적용한컴퓨터수업상황이다. 이수업상황에서가장두드러지게나타난협동학습의특징 가지를쓰고, 이수업에적용된협동학습모형의이름을영어약자로쓰시오. [ 점 L 교사는고등학교컴퓨터수업시간에 HTML 태그를가르쳤다. L 교사는 0명의학급학생들을 5명씩 8개의집단으로나누 고, 퀴즈에대비해서집단별로공부를하게한후, 개인별로 차에걸쳐퀴즈를보았다. L 교사는, 차퀴즈에서각개인의향 상된점수를합해서집단별점수를계산하고, 50 점이상이향상된집단을모두시상하기로하였다. 각집단은집단향상점수로 할수있기때문에 50 점이상을목표로하였고, 학생들은자신이점수를많이향상시킬수록집단의점수향상에기여 HTML 태그를열심히공부하였다. 학생들은퀴즈에서향상된점수로평가받는것을누구나노력에의해집 단의성공에기여할수있는공평한방식으로받아들였다. 협동학습의특징 :,, 협동학습모형의이름 :. 최근교수 학습환경에많이적용되고있는 위키 (Wiki) 의개념을 줄이내로기술하고, 위키를웹기반협력학습에적용할경우학습자집단의지식측면에서기대할수있는대표적인장점을 줄이내로기술하시오. [ 점 개념 : 장점 : 5. 유비쿼터스컴퓨팅시대를맞이하여신기술들이적용된 u- 러닝, u- 오피스, u- 헬스케어등이보편화될전망이다. 다음사례들 은신기술이교육분야에적용될수있는상황을설명한것이다. 각사례에적용된신기술관련요소중가장적합한것한 개를 < 표 > 에서찾아 ~ 의빈칸에기호 ( ㄱ, ㄴ, ㄷ등 ) 로쓰시오. [ 점 사례 학생증에전자태그(tag) 가부착되어있어서학생이교실에들어오면태그에저장되어있는신 상정보가안테나를통하여판독기(reader) 로전송된다. 판독기는이정보를받아서학교호스트 컴퓨터와교신하여출석체크가신속하게이루어진다. 네트워크수요가급격히증가함에따라학생들이가지고있는이동용무선정보기기는이제 8 비트(bit) 주소체계를적용한인터넷주소를갖게되었다. 디지털방식의통신과방송이융합된멀티미디어이동방송서비스가등장하면서, 학생들은이 동하는도중에휴대폰을이용하여공중파방송을보면서학습할수있게되었다. 신기술관련요소 < 표> ㄱ. CDMA ㄴ. DMB ㄷ. FDMA ㄹ. GVM ㅁ. JAVA ㅂ. IPv ㅅ. IPv6 ㅇ. KVM ㅈ. RFID ㅊ. TDMA ㅋ. UDTV ㅌ. UMPC ㅍ. VoIP ㅎ. WIPI 면 )
6. 다음 < 지도내용 > 은컴퓨터수업시간에 K 교사가이진수체계를설명하기위하여구상한내용이다. 아래 < 표 > 는이 < 지 도내용 > 에대하여 K 교사가가네 (R. Gagné) 의수업목표진술요소에따라수업목표를진술한것이다. ~ 의빈칸을 채우시오. [ 점 < 지도내용> 교사는손가락을이용하여이진수에대한설명을한다. 손가락이구부러졌을때를 0, 손가락이펴졌을때를 로하면, 손가락의 구부러진상태와펴진상태로최대 0 가지를나타낼수있음을알게한다. 일반적으로컴퓨터에서사용하는 8개의영문자를 표현하는데는 < 표> 7 비트만으로도충분하다는것을이해하게한다. 수업목표진술요소 수업목표의진술 손가락을구부렸을때를 0, 폈을때를 로표현하면 도구 (tools) 구부리거나펴서숫자를세는것으로 이진수체계를 학습능력 (capability to be learned) 이해하고활용할수있다. 7. 다음은 005 년 월에발표된 초 중등학교정보통신기술교육운영지침 의내용영역과개정된기본방향의주요내용을제시한것이다. ~ 의빈칸을채우시오. [ 점 내용영역 정보사회의생활 개정된기본방향 정보통신기술교육 정보기기의이해 종합활동 소양교육 + + 교과활용교육 8. 다음은입력데이터 7,, 8 을이중연결리스트에오름차순으로삽입하는 C 프로그램이다. sorted_insert() 함수의 ~ 을 쓰시오. [ 점 #include <stdio.h> #include <stdlib.h> typedef struct DN { int val; struct DN *prev; struct DN *next; DNODE; void sorted_insert(int); DNODE *head, *tail; void main(void) { head = (DNODE*)malloc(sizeof(DNODE)); tail = (DNODE*)malloc(sizeof(DNODE)); head->next = tail; head->prev = head; tail->next = tail; tail->prev = head; sorted_insert(7); sorted_insert(); sorted_insert(8); void sorted_insert(int k) { DNODE *s, *i; s = head->next; while (s->val <= k && s!= tail) s = ➀ ; i = (DNODE*)malloc(sizeof(DNODE)); i->val = k; ➁ = i; i->prev = ➂ ; s->prev = i; i->next = s; 면 )
9. 다음은우선순위기반선점형운영체제에서태스크의동작을보여주는 < 그림 > 과 < 설명 > 이다. 이그림이어떤현상을나타낸 것인지해당용어를쓰시오. 그리고이현상을해결하기위한방법을 줄이내로쓰시오. [ 점 용어 : 해결방법 : < 그림> < 설명> 실선으로표현된부분은해당태스크가실행중임을의미한다. 빗금친부분은해당태스크가세마포어를획득하여사용중임을의미한다. 에서태스크 은세마포어를획득한다. 에서태스크 은태스크 을선점한다. 에서태스크 은세마포어를획득하려고한다. 에서태스크 는태스크 을선점한다. 5에서태스크 은작업을재개한다. 6에서태스크 은세마포어를반환한다. 0. 유한버퍼를사용하는생산자 / 소비자문제에서동기화를위해모니터 (monitor) 를사용한다고할때, 다음 < 가정 > 을참조하여 이모니터프로그램이적절히동작할수있도록 ~ 를쓰시오. [ 점 < 가정> ᄀ ᄂ ᄃ 생산자프로세스는 put() 하여데이터를버퍼에입력한다. 소비자프로세스는 get() 함수를사용 함수를사용 하여버퍼의데이터를읽어들인다. 모니터프로그램에서버퍼의개수는 하나이고, 버퍼는정수값을가진다. monitor producer_consumer_monitor { int buf; /* 버퍼 */ boolean is_full = false; semaphore mutex =, full =, empty = ; int get() { if (is_full == ) wait(full); wait(mutex); ; signal(mutex); ; return buf; /* get */ void put(int value) { if (is_full == true) wait(empty); wait(mutex); buf = value; is_full = true; signal(mutex); ; /* put */ /* producer_consumer_monitor */. 아래그림은 비트 (bit) 의이진곱셈을처리하는 배열승산기의조합회로도이다. 승수의비트는각각 과, 피승수의 비트는 과, 출력결과는,,, 이다. X 과 X 의조합회로도를각각그리시오. ( 단, X 는단일게이트 6 개를사용하 여회로도를그리시오.) [5 점 배열승산기의조합회로도 X의조합회로도 X 의조합회로도( 단일게이트 6 개사용) 면 )
. 다음은그래프에관한알고리즘이다. < 가정 > 과 < 알고리즘 > 을참조하여트리를구성하시오. 트리를구성하는동안선택된간선을순서대로간선의집합 T 에작성하고, 이알고리즘의이름과평균시간복잡도 (Big-Oh 표기법 ) 를쓰시오. [ 점 < 가정> ᄀ 그래프는정점(vertex) 들의집합과간선(edge) 들의집합으 로구성된다. ᄂ T 는트리간선의집합이다. ᄃ TV 는트리정점의집합이다. ᄅ그래프의간선은두정점간비용을포함한다. < 알고리즘 > T = { ; /* 간선은비어있다. */ TV = {; /* 정점 부터시작한다. */ while (T의간선수가 n- 보다적음) { u TV이고 v TV 인최저비용간선을 (u, v) 라함; if ( 그런간선이없음) break; v를 TV 에추가; (u, v) 를 T 에추가; if (T의간선수가 n- 보다적음) printf("failure"); < 그래프> < 트리> 선택된간선의집합 : T = {(, ), (, ), (, ), (, ), (, ), (, ) ( 단, 간선 (, ) 는트리정점 과 사이의간선을의미한다.) 알고리즘의이름 : 평균시간복잡도(Big-Oh 표기법) :. 다음은사원의정보를유지하는 < 사원 > 릴레이션이다. 사원은한부서에소속되어있고부서와상관없이여러프로젝트의수행에참여한다. 한프로젝트에는여러명의담당자가존재하며, 한명의담당자는하나의프로젝트만을담당할수있다. 아래에제시한 < 사원 > 릴레이션에대하여정규화를수행하는과정에서각정규형에따른모든함수종속다이어그램을그리시 오. 이때각과정에는앞단계에서정규화를수행한함수종속다이어그램도같이그려릴레이션의모든속성이름이나타나 도록하시오. ( 단, < 사원 > 릴레이션의기본키는 ( 번호, P 번호 ) 이다.) [ 점 < 사원> P 는프로젝트를의미한다. 번호이름부서 P번호 5 김영호김영호정석우정석우정석우이영희이영희김수철김수철이영희 영업영업기획기획기획영업영업개발개발기획 P0 P0 P0 P0 P0 P0 P0 P0 P0 P0 P담당자김민수박성민김민수최성국박성민최성국서윤희최수희서윤희박성민 전화번호 정규화수행과정 NF NF NF BCNF 5 면 )
. JK 플립플롭 (Flip/Flop) 개를사용하여 mod- 동기식카운터 (counter) 를설계하고자한다. 다음 < 순차표 > 와 JK 플립플롭 에대한 < 제어입력형태표 >, 그리고 < 설명 > 을참조하여 < 여기표 ( 천이표 )> 를작성하고, ~ 의빈칸에간소화된논리식의 결과를쓰시오. [ 점 ᄀ < 설명> 현재상태 0 이다음상태 0 으로변하면천이형태를 0 으로한다. ᄂ현재상태 0 이다음상태 로변하면천이형태를 로한다. ᄃ현재상태 이다음상태 0 으로변하면천이형태를 로한다. ᄅ 현재상태 이다음상태 로변하면천이형태를 로한다. < 순차표> 계수 출력 상태할당 C p Q B Q A S 0 0 0 S 0 0 S 0 S S 0 0 S 0 < 제어입력형태표> 천이형태 제어입력 J K 0 0 0 < 여기표( 천이표)> 현재상태 다음상태 천이형태 제어입력 Q B Q A Q B Q A F/F B F/F A J B K B J A K A < 논리식> F/F A J K A = A = F/F B J K B = B = 5. 다음은고객의정보를유지하는 < 고객 > 릴레이션과고객의 DVD 대여정보를유지하는 < 대여 > 릴레이션이다. 한고객은같은 DVD 를동시에대여할수없으며, 한고객에대한특정 DVD 대여횟수는누적되어유지된다. 아래에서제시된 결과릴레이션 은 < 고객 > 과 < 대여 > 릴레이션에대하여조인질의문을수행한결과생성된릴레이션이다. 결과릴레이션 이이만들어질수있도록 연산자 IN 을사용한부속질의문과조인을이용한질의문을 SQL 로작성하시오. 그리고이를조인할때비교횟수를줄인가장 효율적인관계대수식으로표현하시오. ( 단, where 절의조건식은 AND 연산자를한번만사용하고, 조인질의문작성은 join predicate NATURAL JOIN 을사용하시오.) [ 점 < 고객> < 대여> 결과릴레이션 고객번호이름주소전화번호 5 6 7 이성호 정수영 이소라 김서영 최우석 김민우 박상일 신림동 금천동 신림동 광안동 금천동 신림동 금천동 0-0- -6 0- -5 0-9 5-8 고객번호 5 DVD번호 D0 D0 D0 D0 D0 D0 D0 D0 D0 D0 대여횟수 6 5 9 6 8 7 이름 이성호이소라최우석 전화번호 0- -6-5 부속질의문 조인질의문 select select from from where IN where ; ; 관계대수식 6 면 )
6. 비지역변수의참조방법으로정적체인사용기법과디스플레이사용기법이있다. 아래의프로그램에서프로시저 C 가첫번째호출되어실행중일때의정적체인사용기법과디스플레이사용기법의활성레코드상태를나타내기위하여아래그림에정적링크, 동적링크, 디스플레이를그리시오. 그리고비지역변수참조시실행시간의관점에서디스플레이사용기법이정적체인사용기법보다더우수한이유를 줄이내로기술하시오. [ 점 program main(input, output); var x,y : integer; procedure A; begin x := x+y; write(x, "in A"); B; y := y+ end; {A procedure B; procedure C; begin x := +y; write(x, "in D") end; {C begin x := +x; if (x < 5) then A; else C; write(x, "in B") end; {B begin x := ; y := ; B; x := x+y; write(x, "in Main") end. {main 정적체인사용기법의활성레코드상태 디스플레이사용기법의활성레코드상태 정적링크동적링크동적링크디스플레이 이유 : 7. 아래의왼쪽시계는 시간은 60 분, 하루는 시간 (0 분 ) 인일상에서사용하는시계이며, 오른쪽시계는 시간이 80 분, 하루가 6 시간인가상시계이다. 왼쪽시계의오전 7 시 0 분은오른쪽시계로오전 시 7 분 ( 초를나타내는소수점은버린다고가정 ) 이된다. 아래의 C 언어로작성한 time_convert() 는이러한시간변환을계산하는함수이다. ~ 를채우시오. ( 단, 은수, 는변수, 과 는변수와수를이용한수식이다.) [ 점 /* lh : 왼쪽시계시를나타내는변수, lm : 왼쪽시계분을나타내는변수, rh : 오른쪽시계시를나타내는변수, rm : 오른쪽시계분을나타내는변수 */ void time_convert(int lh, int lm, int *rh, int *rm) { int tlm, /* 왼쪽시계의현재시간을분으로계산한값 */ trm; /* 왼쪽시계의현재시간을오른쪽시계의분으로계산한값 */ tlm = lh * 60 + lm; trm = int(( / 0 ) * ); *rh = int( ); *rm = ; 7 면 )
8. 다음 < 그림 > 과 < 표 > 는토큰전달에의한 FDDI(Fiber Distributed Data Interface) 접근방식을보여주고있다. < 조건 > 을참조하여 ~ 5 를채우시오. [5 점 < 그림> < 토큰도착시각지국의처리순서> 용어설명. THT 를계산한다. : 계산식 THT = l. 으로재설정한다.. 지국은자신의동기데이터를전송한다.. 지국은 THT 의값이양수일동안비동기데이터를전송한다. TTRT(Target Token Rotation Time) : 토큰이링을한바퀴순회하는데걸리는평균시간을나타낸다. TRT(Token Rotation Timer) : 토큰이링을한바퀴순환하는실제시간을나타낸다. THT(Token Holding Timer) : 지국의전송가능시간을나타낸다. < 조건>. 토큰링은 개의지국(Node) 만을연결한다.. TTRT는 0 시간단위 (time unit) 이다.. 토큰이한지국에서다음지국으로이동하는데걸리는시간은 시간단위 (time unit) 이다.. 각지국은한번에 개의동기데이터단위 (data unit) 를 시간단위 (time unit) 에전송한다. 5. 각지국은버퍼에서대기하고있는많은비동기데이터를가지고있다. 6. 라운드 0 에서토큰은지국과지국사이를움직이고, 각지국은 TRT를 0 으로설정하며, 이라운드에서는데이터전송이일어나지않는다. < 표> 토큰도착시각지국의처리내용 라운드 Node Node Node Node 0 Arriving Time = 0 Arriving Time : TRT is now THT = 6 Syn Data : THT is now Asyn Data : Arriving Time = Arriving Time : TRT is now 0 THT = Syn Data : THT is now - Asyn Data : 0 Arriving Time = Arriving Time : TRT is now THT = - Syn Data : THT is now - Asyn Data : 0 Arriving Time = Arriving Time : 7 TRT is now THT = - Syn Data : THT is now -6 Asyn Data : 5 9. 아래 -- 트리에 를삽입한후의 -- 트리를그리고, 를삽입하기전의 -- 트리에서 를삭제한후의 -- 트리를그리시오. -- 트리는 - 트리에비해삽입과삭제알고리즘이간단하다는장점이있다. 그이유를 줄이내로기 술하시오. [ 점 -- 트리 삽입후의 -- 트리 삭제후의 -- 트리 5 8 6 7 9 0 알고리즘이간단한이유 : 8 면 )
0. 해시에서충돌이발생할때해시테이블의빈버킷을찾기위한함수로써, 아래의 linear_probing() 함수는해시주소를 씩증가시키는선형조사법 (linear probing) 을적용한함수이며, double_hash() 함수는해시주소를임의의상수로증가시키는이중해시법 (double hash) 을적용한함수이다. 아래의입력데이터에대해이두함수를각각실행한후만들어진해시테이블의내용을적으시오. 그리고두해시테이블의결과를비교했을때, 이중해시법에서는선형조사법의어떠한문제가해결되었는지 줄이내로설명하시오. [ 점 < 가정> ᄀ #define EMPTY - /* 해시테이블초기화값 */ ᄃ 해시테이블은 EMPTY 로초기화되어있다. #define DELETED - /* 삭제된후의버킷값 */ ᄅ 해시테이블에저장되는 key 값은 0 이상의정수이다. #define TABLE_SIZE /* 해시테이블크기 */ ᄆ hash_func() 함수는 key % TABLE_SIZE 수식값을반환한다. ᄂ 데이터는 EMPTY 나 DELETED 값을갖는곳에서만삽입할수있다. ᄇ a[ 는해시테이블, key 는저장할입력데이터이다. 선형조사법적용함수 이중해시법적용함수 int increment_val(int key) { if (key < 0) return ; else return 5; int linear_probing(int key, int a[) { int t_loc, t_loc; t_loc = t_loc = hash_func(key); while (a[t_loc!= EMPTY && a[t_loc!= DELETED) { t_loc = (t_loc + ) % TABLE_SIZE; if (t_loc == t_loc) return -; /* 해시테이블 full */ a[t_loc = key; /* key 값을해시테이블에저장 */ return t_loc; int double_hash(int key, int a[) { int t_loc, t_loc; t_loc = t_loc = hash_func(key); while (a[t_loc!= EMPTY && a[t_loc!= DELETED) { t_loc = (t_loc + increment_val(key)) % TABLE_SIZE; if (t_loc == t_loc) return -; /* 해시테이블에삽입할수없음 */ a[t_loc = key; /* key 값을해시테이블에저장 */ return t_loc; 입력데이터 linear_probing() 함수를실행한후의해시테이블 double_hash() 함수를실행한후의해시테이블 a[0 a[ a[ a[ a[ a[5 a[6 a[7 a[8 a[9 a[0 a[0 a[ a[ a[ a[ a[5 a[6 a[7 a[8 a[9 a[0, 5,, 5, 6 해결된문제 : 9 면 )
. 여러트랜잭션들이아무런제약없이데이터베이스에동시에접근할수있도록허용된다면기본적으로 가지형태의문제가발생하게된다. 아래표안에있는 가지형태의트랜잭션들에대해동시성제어를하지않고수행할때발생하는문제점을 ~ 의빈칸에 단어이내로쓰시오. 그리고이러한문제점이발생하는이유를 줄이내로기술하시오. [ 점 T read(x) read(y) x = x + y read(z) rollback T 시간 T x = x * T read(x) read(y) x = x + y 시간 T x = x + T read(x) x = x + read(y) y = y * write(y) 시간 T read(x) x = x * read(y) y = y + write(y) 문제점이발생하는이유 :. 일반적으로구문분석은하향 (top-down) 방식의구문분석 (LL 파싱 ) 보다상향 (bottom-up) 방식의구문분석 (LR 파싱 ) 을더많이사용한다. 하향방식의구문분석에서필연적으로발생하는문제점을 줄이내로기술하시오. 그리고아래의문법에대해 FIRST 와 FOLLOW 를구하고 SLR 파싱테이블을작성하시오. ( 단, SLR 파싱테이블은생성된상태수만큼만채우고, ACTION 테이블의 shift 는 s 상태번호 ( 예 : s), reduce 는 r 생성규칙번호 ( 예 : r), GOTO 테이블은상태번호 ( 예 : ) 만으로표기하시오.) [ 점 < 문법 > G = ({S, C, {c, d, P, S) P : () S CC () C ac () C b 하향방식구문분석의문제점 : FIRST와 FOLLOW FIRST(S) = { FIRST(C) = { FOLLOW(S) = { FOLLOW(C) = { SLR 파싱테이블( 상태수만큼만채우시오.) ACTION 테이블 GOTO 테이블상태번호 a b $ S C 0 s s accept 5 6 7 - 수고하셨습니다 - 0 면 )