2、荿薃蚂袃肈莆薈袂膁薁蒄羁芃莄螂羀羃蕿蚈罿肅莂薄羈芇薈薀羇莀蒀衿羇聿芃螅羆膁葿蚁羅芄节薇肄羃蒇蒃肃肆芀螂肂膈蒅蚈肁莀芈蚄肁肀薄薀肀膂莆袈聿芅薂螄肈莇莅蚀膇肇薀薆螄腿莃蒂螃芁薈袁螂肁莁螇螁膃蚇蚃螀芅蒀蕿蝿莈节袇蝿肇蒈螃袈膀芁虿袇节蒆薅袆羂艿蒁平成１５年度技術士第一次試験（専門科目）１６ 情報工学部門Ⅳ 次の３０問題のうち２５問題を選択して解答せよ。（専門科目解答欄に１つマークすること。） Ⅳ－１ 正規表現に関連する次の文章のうちで誤っているものを選べ。 ① 正規表現は構文上の操作として、連接、選択、巾の３つの演算によって構成されるが、これらの操作のいろいろの変形も使用されている。 ② プログラ
3、ミング言語における整数の構文は通常、正規表現によって、 ＜数字＞＜数字＞＊｜＜符号＞＜数字＞＜数字＞＊ と表される。 ③ 正規表現で許される言語全体と正規文法で表される言語全体とは一致する。 ④ 正規表現で表される言語は非決定性有限状態オートマトンで認識できる。 ⑤ 非決定性有限状態オートマトンを、それと同値な決定性有限状態オートマトンに変換すると、状態数は最大ｎ２倍程度に増加する。 推定正解 ① Ⅳ－２ アルゴリズムの計算量に関する次の文章のうちで誤っているものを選べ。 ① あるアルゴリズムの計算量を決めるためには、そのアルゴリズムの基本演算（操作）と、具体的な個々の問題
4、の「大きさ」の定義とを定める必要がある。 ② あるアルゴリズムの平均計算量とは、問題の大きさが等しいようなすべての入力データに対する、計算量の平均をとったものである。 ③ Ｏ（ｎ３）とＯ（２ｎ２＋ｎ２）とは、Ｏ－記法つまり漸近計算量としては同じである。 ④ ソート済みの配列で表現された表の二分岐探索の計算量は、最悪の場合も平均の場合も、Ｏ（ｎ２）である。 ⑤ 単純挿入法などのほとんどの単純なソートアルゴリズムの計算量はＯ（ｎ２）である。
推定正解 ④ Ⅳ－３ 数値誤差に関する次の文章のうちで誤っているものを選べ。 ① 入力誤差あるいはデータ誤差とは、コンピュータに入力する際の値の
5、表現と真の値との差をいう。 ② 計算機へのデータ入力において１０進２進変換による誤差が生じる。これも入力誤差となる。 ③ 打ち切り誤差とは、無限級数の値の計算など、数学的な無限小演算を途中で打ち切ったために生じる誤差をいう。 ④ 丸め誤差とは、計算機内部表現における浮動小数点数の演算における、丸め操作による誤差をいう。 ⑤ 浮動小数点の演算において、桁落ちの現象は乗除算演算の際に生じる。 推定正解 ⑤ Ⅳ－４ 次のＣ言語プログラムを実行することを考える。（ア）、（イ）を正しく埋めたも
のを選べ。structpair{inta;intb;};voidf(structpair**s{s[
6、1]->a=100;}main(){ structpair*A[10]; structpairB; B.a=50; A[1]=&B; （ア） printf("%d",A[1]->a);}出力結果は（イ）となる。 ア イ ① f(A); 50 ② f(A); 100 ③ f(&A); 50 ④ f(A[1]); 50 ⑤ f(A[1]); 100 推定正解 ② Ⅳ－５ Ｃ言語で、再帰関数fを次のように定義する。intf(intx,inty,intz){ if(x==y)returnz;elseif(x>y)returnf(x-y,y,z+1);else
7、returnf(x,y-x,z+1);} 関数呼び出しf(24,16,0)の返す値はいくつか。 なお、x==yはxがyに等しいことを表す。 ① ２ ② ８ ③ ２４ ④ ４２ ⑤ ２４１６ 推定正解 ① Ⅳ－６ 整数型の配列a[0],a[1],...a[n]には、 a[0]=0, a[i]=i+2(1≦i≦n-2), a[n-1]=1,a[n]=2 のように値が入っているものとする。
