日本筑波大学计算机专业院生入学考试G.pdf

平成年度 筑波大学大学院博士課程 情報工学研究科 専攻 筑波大学大学院博士課程 情報工学研究科 専攻 博士前期課程 （一般入学試験 月期第次） 試験問題 基礎科目(情報基礎) 博士前期課程 （一般入学試験 月期第次） 試験問題 基礎科目(情報基礎) 注意事項 1. 試験開始合図、問題中見。 2. 解答用紙定欄、研究科、専攻、受験番号記入。 3. 問題全部 8 （表紙除）。 4. 解答用紙 2 枚（罫線有） 、下書用紙（白紙） 1 枚配布。 5. 問題全部 2 問。問題 I 解答 1 枚目、問題 II 解答 2 枚目解答用紙、 必分記入。 6. 解答記述、問題 I解答、問題 II解答、必明記。 平成年月日 ( E n g l i s h v c r s i o n i s a t P a g c s 5 a n d a f t e r . ) 問題I 解答、1 枚 目 解答用紙記入 。 解答用紙、 問題 I 解答 明記 。 問題I 単純挿入 法 ( s t r a i g h t i n s e n i O n s O r t ) 、 法( s h u t t l C S O r t ) 呼 、 挿 入 用 法。図 1 法1 示 。配 列a 0 , , a E n - 1 、 a i 前部分 。 、 a i 値w 。 a 0 , 。 , a i - 1 部分、 w 入 位置 探。 位置j 。 配列範囲 a E j , 。 , a i - 1 a j + 1 , , a i 。 最後、 w o j 格納 。 操作、 最後 繰 返。 以 下 設 間 答 。 酉 己 夕u a 配列a ( 1 後) 0 1 + 1 i l t i + 1 n - 1 図1 単純挿入 法1 ( 1 ) 以 下 、 単純挿入 法配列 a r r a y l 昇順( a s c c n d i n g o r d e r ) C 言語記述一部。関数s h i f t ( ) 、 単純挿入 法 配列 範 囲 関数 。関数 m a i n ( ) 実行時 、 画 面 出力 示 。 v o i d p r i n t _ a r r a y ( i n t a , i n t n ) i n t i ; f O r ( i = 0 ; l n ; + + ) p r i n t f ( % d , a i ) ; p r i n t f ( : : n : ) ; l v o i d i n s e r t i o n _ s o r t ( i n t i n t w , , ; i f ( n = 1 ) r e t u r n ; f O r ( i 1 ; n ; + + ) p r i n t f ( 1 i = = % d : : : , i ) ; W = a i ; f O r ( j = 0 ; i s h i f t ( a , j , i ) ; a j = W ; a , i n t n ) p r i n t _ a r r a y ( a , n ) ; ( A ) ; j + + ) p r i n t f ( : = i % d : 1 1 , i ) ; p r i n t _ a r r a y ( a , n ) ; 1 次続 1 i n t a r r a y l 8 0 , 3 5 , 5 , 4 0 , 6 5 , ; m a n ( ) i n s e r t i o n _ s o r t ( a r r a y l , 5 ) ; ( 2 ) 小問( 1 ) 、 空欄 鯉目 埋 完成 。 ( 3 ) 以 下 s h i f t ( ) 、 単純挿入 法配列要素 関数 。 空 欄( | 】百 ) 埋 完 成 。 v o i d s h i f t ( i n t a , i n t f i r s t , i n t l a s t ) . i n t p ; | | | | : 1 1 1 1 1 1 1 1 : : 島 丁 | “I I ( 4 ) 単純挿入 法要素比較回数答 。 、 配列要素数n 。 ( 5 ) 単 純挿入 卜 法要素移動回数答。 、 配列要素数n 。 2 ( 6 ) 法( S h c l l S S O r t ) 、 与 配列d 番 地 化 法 。k 番目 a k , a k + d , a k + d * 2 , ( k = 0 , , d - 1 ) 、 単純挿 入 法 同方 法 。 法 、d 減 、 最後 d 。以 下 、 s h e l l _ s o r t ( ) 、d 4 , 2 , 1 順 減 法配列 関数 。空欄 ( 0 ) 埋 完成 。 v o i d i n s e r t i o n = s o r t _ d ( i n t a , i n t n , i n t d ) i n t w , , , k ; i f ( n = d ) r e t u r n ; f O r ( k = 0 ; k f O r ( i = d + k ; i n t d i m E = 1 , 2 , 4 ; v o i d s h e l l _ s o r t ( i n t a , i n t l ; f O r ( l | ( M ) ; | n s e r t i o n _ s o r t _ d ( a , ( I ) W 二a i ; f O r ( j = k ; j ( | s h i f t _ d ( a , , , d ) ; a j = W ; c F M 1 7 : 撃) n t n ) | ) I 1 1 1 ; | | I I I ( 0 ) n , d i m E l ) ; ) ; ( L ) ) I v o i d s h i f t _ d ( i n t a , i n t f i r s t , i n t l a s t , i n t d ) 省略 3 問題 解答2 枚目解答用紙記入. 解答用紙問題 解答明記 . | 1 票識 ) 言 O O O I 問題 図 交差路 設置 信号機 考 . _ = , 以下設間答 . ( 1 ) = = C = , y , g 。, , 3 , C 信号機 島, 鳥, 表示色集合, , , g 赤, 黄 , 青対応元表。R B B 二項関係, R c C 二項関係, 次式成 立 . 。 R B ( r ) = r , , g , t B ( ) = r , t B ( g ) = r 。 L c ( r ) = r , R / c ( ) = , t c ( g ) = g , , B , c C , R B ( ) = R , R c ( ) = R / c C 。 , 以下問 答 . ( D R B R c 元示. ) R B 逆 関係R 元 示 . ) 3 C 二項 関係R B c R 底用表 , R B c 元 示 . ( 2 ) 設問( 1 ) R B 基信号機t 携 制御 論理回路設計 . , 論 理回路入力l , 2 3 . , 論理回路出力 z 7 ( J = 1 , 2 , , 6 ) , 用信号機状態 ( 点灯, 消灯) 制御 。図示 信号機 1 6 番号付 , = 1 限 点灯 , 4 = 0 限 J 消灯 . , 以下問代数範疇答 . ( 静下表空欄 埋 , 出力z 7 ( J = 1 , 2 , 一, 6 ) 真理値表 作成 。 , * d O n t C a r e 意味 . ) 出 力z 4 論理式積和標準形 示。 ) 出力z 4 図作成, 最簡形論理式示. ) ) 求論理式正論理( p o s i t i v e l o g i c , a c t i v e h i g h ) 1 aZ lZ Z 4Z Z 0 100 0 1 10 01 01 0110 10 1 0 1 1 1 * 11 * 1l1 * 表回路図描 . 4 W r i t e t h c a n s w e r s o f P r o b l e l l l l i n t h c f i r s t a n s w c r s h e e t , c l c a r l y i n d i c a t i n g a h c a d i n g “P r o b l c n n I “ P r o b l e m I S t r a i g h t i n s c r t i o n s o r t , a l s o k n o w n a s s h u t t l e s o r t , i s a s o l t i n g a l g o r i t h m t h a t u s e s i n s c r t i o n a n d s h i f t i n g . F i g u r c l s h o w s o n c s t e p o f t h i s s o r t i n g a l g o n t h m . I n a n a r r a y a 0 , 。 , a n - 1 , t h e i r s t p a r t b e f o r c a i i S S O n C d . L e t t h c v a l u e o f a i b e w . I n t h e f i r s t p a r t a 0 , , a i - 1 , t h C s o r t i n g a 1 8 0t h m f i n d s t h c p o s i l o n f o r w . L e t t h i s p o s i t i o n b c j . T h e s O r t i n g a l g ot h m s h i f t s t h e a r r a y r a n g e a j , , a i - 1 t O a j + 1 , , a i . F i n a l l y , t h c s o r t i n g a l g ot h m p u t s w i n t o a j . T h c s O r t i n g a l g ot h m r c p c a t s t h i s s t c p u n t i l t h c l a s t e l e m e n t . A n s w e r t h c f o l l o w i n g q u c s t i o n s . A r r a y a A r r a y a ( A f t e r o n e s t e p ) F i g u r c 1 0 n e s t e p o f t h c s t r a i g h t i n s e r t i o n s o r t i n g a l g o r i t h m . ( 1 ) T h e f 0 1 l o w i n g p r o g r a m i s a p r o g r a m f r a g m c n t t h a t s o r t s t h e a r r a y a r r a y l i n a s c e n d i n g o r d e r b y u s i n g s t r a i g h t i n s c n i O n s O n , wt t c n i n t h e C l a n g u a g e . T h c f l l n c l o n s h i f t ( ) i s a f u n c l o n t h a t s h i f t s a r a n g e o f a n a r r a y i n s t r a i g h t i n s e n i o n s o . W h e n t h c f u n c u o n m a i n ( ) i s e x e c u t c d , w h a t i s t h e o u t p u t o f t h i s p r o g r a m l o t h c d i s p l a y ? v o i d p r i n t _ a r r a y ( i n t a , i n t n ) i n t i ; f O r ( i 0 ; n ; 1 + + ) p r i n t f ( : : % d : : , a i ) ; p r i n t f ( n i : ) ; v o i d i n s e r t i o n _ 5 0 r t ( i n t a , i n t n ) i n t w , , ; i f ( n = 1 ) r e t u r n ; f O r ( i = 1 ; n ; 1 + + ) p r i n t f ( : : i = % d : , i ) ; p r i n t _ a r r a y ( a , n ) ; W a i ; f O r ( j = 0 ; j i s h i f t ( a , j , i ) ; a j = W ; p r i n t f ( 1 : i = % d : : : , i ) ; p r i n t _ a r r a y ( a , n ) ; ( A ) ; j + + ) i c O n t i n t t s O n t h n t t t p a O l l 5 i n t a r r a y l = 8 0 , 3 5 , 1 5 , 4 0 , 6 5 , ; m a n ( ) i n S e r t i O n T s o r t ( a r r a y l , 5 ) ; ( 2 ) I n t h e p r O g r a l n J Q u e s u O n ( 1 ) O V e , , l m t h e b O X A 】 a n d c O m c t e t h e p g r a m . ( 3 ) I n t h e f 0 1 l o w i n g p g r a m , S h i f t ( ) i s a f u n c t i o n t h a t s h i f t s a r a n g e O f a n a r r a y i n s , a i g h t i n s r t i o n s o . F H l i n t h e b o x e s ( 】t O 直 】 a n d c o m p l e t e t h e p r o g r a m . v o d s h i f t ( i n t a E , i n t f i r s t , n t l a s t ) i n t p ; 7 ? : : 井 里誕 i p : C C M I ; : l p ( 4 ) A n s w e r t h e o r d e r o f g r o w t h o f e l e m e n t c o m p a s o n s o f s t r a i g h t i n s e r t i o n s o r t i f w e l e t t h e n u m b e r a r r a y e l e m e n t s b c n . ( 5 ) A n s w e r t h e o r d e r o f g r o w t h o f c l c m c n t m o v e m e n t s o f s t r a l g h t i n s e o n s o r t i f w c l c t t h e n u m b e r o f a r r a y e l e m c n t s b e n . 6 ( 6 ) S h e n s s o r t i s a s o r t a l g o t h m t h a t d i v i d c s a g i v e n a r r a y i n t o d g r O u p s u s i n g d a s a n i n d e x g a p . T h i s a l g ot h m s o r t s t h c k t l l g r o u p a k , a k + d , a k + d * 2 , ( k = 0 , . 。, d - 1 ) b y u s i n g t h e s a m c r r l e t h o d a s s t r a i g h t i n s e r t i o n s o r t . T h e a l g o t h n l d e c r c a s c s t h c g a p d u n t i l l . I n t h c f o l l o w i n g p r o g r a m , S h e l l _ s o r t ( ) i s a f u n c d o n t h a t s o s a n a r r a y u J n g S h e l l s s o w i t h d i m i n i s h i n g g a p s 4 , 2 , a n d l . F i n i n t h e b O x c s ( F 】 t O 0 ) a n d c o m p l e t c t h e p g r a m . v o i d i n s e r t i o n _ s o r t _ d ( i n t a , i n t n , i n t d ) i n t w , , , k ; i f ( n = d ) r e t u r n ; f O r ( k = 0 ; k ( F ) ; k ( G ) | ) f O r ( i = d + k ; i l ( H ) ; i l ( I ) ) W = a i ; f O r ( j k ; j ( ) | j l ( | ) ) c o n t i n u e ; s h i f t _ d ( a , , , d ) ; a j = W ; i n t d i m = 1 , 2 , 4 ; v o i d s h e l l _ 5 0 r t ( i n t a , i n t n ) i n t l ; f O r ( 1 1 ( M ) ; ( N ) | 0 ) I J ) i n s e r t i o n _ s o r t _ d ( a , n , d i m E l ) ; v o i d s h i f t _ d ( i n t a , i n t f i r s t , i n t l a s t , i n t d ) “ 7 W r i c t h c a n s w c r s o f P r o b l c F n I I i n t h c s c c o n d a n s w c r s h e c t , c l c a r l y i n d i c a t i n g a h c a d i n g P r o b l c m I I . P r o b l e l l l I I C o n s i d c r t h e t r a f E c s i g n a l s p o s i t i o n c d a t a r o a d i n t c r s c c t i o n a s s h o w n i n t h c f l g u r e . 2 n s 、v c r t h c f o l l o w i n g q u c s t i o n s . O m m ,4 乳祠 C 鵬 t h a t t h e t r a t t c s i g n a l s S / , , a n d s c c a l l i n d i c a t e , r c s p c c t i v c l y a n d r , y , a n d g t h c c l c m c l l t s c o r r c s p o n d i n g t o r c d , y c l l o w , a n d g r c c n , r c s p c c t i v c l y . W h c n J 、B i S t h C b i n a r c l a t i o n f r o m t o 3 a n d R c t h c b i n a r c l a t i o n f r o m / t o C , t h c f o l l o w i n g c q u a t i o n s h o l d . R B ( r ) = , , g , R B ( ) = r ) , f B ( g ) = , 。 R c ( / ) = , R / c ( ) = , a n d t c ( g ) = ( g . N o t e t h a t R B ( ) = ( b l R 4 8 b ) a n d R c ( ) = ( C l R c , W h C n A l l s w c r t h C f o l l o 、 / i n g q u c s t i o n s . ( a ) D e s c b c t h c c l c m c n t s o f J 、B a n d R c , r c s p c c t c l y . ( b ) D e s c t t b c t h c e l c m c l l t s o f R t t t h a t i s t h c i n v c r s c r e l a t i o n o f J 、B . ( c ) R c p r c s c n t R B c t h a t i s t h c b i n a v r e l a t i o n f r o m B t o C b y u s i n g R 琺 , a l l d d e s c r i b c t h c c l c m c n t s o f R B c . ( 2 ) B a s c d O n f 、3 0 f t h c q u c s t i o n ( 1 ) , W C d C S i g n a l o g i c a l c i r c u i t f o r c o l l t r o l l i n g t h c l a m p s o f t h c t r a f f l c s i g n a l s t t a n d 銑T h C i n p u t s t o t h c l o g i c a l c i r c u i t a r c l , 2 a n d 為 T h C O u t p u t s f r o m t h c l o g i c a l c i r c u i t a r c z J ( = 1 , 2 , , 6 ) t h a t d e c i d c t h c s t a t c o f c a c h l a n l p ( l i g l l t i n g o r n o n - l i g h t i n g ) . E a c h l a r n p i s n u m b c r c d f r o m l t o 6 a s s h o w n i n t h c f l g u r c , a n d t h c J t h l a m p i s l i g h t i n g o n l y w h