アルゴリズムとデータ構造判断選択プログラム埋め込み緒論
1-1(neuDS)データの物理構造とは、コンピュータにおけるデータの実際の記憶形態をいう.T 1-2 N^2/1000 is O(N). F 1−32^NとN^Nは同じ成長速度を示した.F 1−4アルゴリズム解析の2つの主要な側面は時間的複雑度と空間的複雑度の解析である.T 1−5データの論理構造は、コンピュータの記憶構造に依存するデータ要素間の順序関係を示す.F 1-6(neuDS)アルゴリズムには出力が必要であるが、入力しなくてもよい.T 1−7アルゴリズムは特定のプログラム設計言語とは独立しており,特定のコンピュータとは無関係である.T`1−8アルゴリズムの複雑度の増加傾向を漸進的表現で解析した.T 1−9 O(n^2),O(1+2+・・+n)に対応するアルゴリズムは時間的複雑度が同じである.T 1−10データの論理構造は,データ要素自体の内容や形式とは無関係である.T 1−11データ項目は、データの最小単位である.T 1−12データ要素はデータの最小単位である.F 1−13データの論理構造とは、データの各データ項目間の論理関係をいう.F 1−14データ構造の概念は、データ間の論理構造、コンピュータにおけるデータの記憶方式、およびデータの演算の3つの態様を含む.T 1−15データ構造の抽象的な動作の定義は具体的な実装と関連している.F 1−16抽象データ型は、コンピュータの内部表現および実装とは無関係である.T 1-17「データ構造」学科「データ構造」は数値計算のプログラム設計問題を研究する学科である.F 1-18 logN^2 is O(N). T 1-19 n^0.01 is O(logn). F
2-1以下データ構造についての言い方で正しいのは_A__. A.データ構造の論理構造が、その記憶構造Bとは独立したデータ構造の記憶構造が、そのデータ構造の論理構造Cとは独立したデータ構造の論理構造が、そのデータ構造の記憶構造Dを一意に決定する.データ構造は、その論理構造と記憶構造のみによって決定される
2−2以下のプログラム区間の時間的複雑度は(A)である.x=90; y=100; while(y>0) if(x>100) { x=x-10; y–; } else x++; A.O(1) B.O(N) C.O(N^2) D.O(log2 N)
2-3あるデータオブジェクトは3つの要素A,B,Cで構成され,要素間関係の集合は{,},このデータオブジェクトの論理構造は(C)A.線形構造B.ツリー型構造C.グラフ構造D.集合構造であるである.
2−4所与のプログラム時間複雑度の繰返し式:T(1)=1,T(N)=2 T(N/2)+N.プログラム時間の複雑度は、C A.O(logn)B.O(N)C.O(Nlogn)D.O(N^2)である
2-5次の関数の中で、どの関数が最も遅い成長速度を持っていますか:B A.N^1.5 B.NlogN^2 C.N 2 logN D.N(logN)2
2−6次のセグメントはアルゴリズム(A)の原則に反する.
A.貧乏性B.確定性C.実行可能性D.丈夫性
2−7次のセグメントを実行する場合のS文の実行頻度は(D)である.
A.n^2 B.n^2/2 C.n(n+1) D.n(n+1)/2
2−8アルゴリズム解析の目的は(A)である.A.データ構造の合理性を探し出すB.アルゴリズム中の入力と出力の関係を研究するC.アルゴリズムの効率を分析してD.分析アルゴリズムの分かりやすさとドキュメント性を改善する
2−9データを格納する際には、通常、各データ要素の値だけでなく(C)も格納する.A.データの処理方法B.データ要素の種類C.データ要素間の関係D.データの格納方法
2−10以下のプログラムの時間的複雑度は(C)である.
A.O(m^2) B.O(n^2) C.O(m × n) D.O(m + n)
2−11次のプログラムの時間的複雑度は(A)である.
A.O(m × n × t) B.O(m + n + t) C.O(m + n × t) D.O(m × t + n)
2−12あるアルゴリズムの時間的複雑度はO(n^2)であり,このアルゴリズムの(D)を示す.(2点)A.問題規模はn^2 B.問題規模はn^2に比例するC.実行時間はn^2 D.実行時間はn^2に比例する
2-13以下のセグメントの時間的複雑度はB
A.O(n) B.O(√n) C.O(n2) D.O(nlgn)
2−14データのコンピュータメモリにおける表現は(A)である.A.データの記憶構造B.データ構造C.データの論理構造D.データ要素間の関係
2−15以下のデータの論理構造に関する記述では,(A)が正しい.A.データの論理構造は、データ要素間の関係の記述であるB.データの論理構造は、コンピュータにおけるデータの記憶方式C.データの論理構造を反映している.
2−16以下のアルゴリズムに関する説で誤っているのは(A)である.A.アルゴリズムとプログラムはすべて具体的なコンピュータと具体的なプログラミング言語から独立しているB.プログラムはプログラミング言語で表すアルゴリズムC.フローチャートはアルゴリズムの図形化記述D.プログラム記述アルゴリズムであるが、アルゴリズムは必ずしもプログラムではない
2−17アルゴリズム解析の目的は(C)である.A.データ構造の合理性を探し出すB.アルゴリズム中の入力と出力の関係を研究するC.アルゴリズムの効率を分析してD.分析アルゴリズムの可読性と簡明性を改善する
2−18対のアルゴリズム解析の前提は(B)である.A.アルゴリズムは簡単でなければならないB.アルゴリズムは正確でなければならないC.アルゴリズムの構造性が強いD.アルゴリズムは通用しなければならない
2-19アルゴリズム設計の要求良いアルゴリズムを設計するには、正確性、A.可用性B.可読性C.信頼性D.実現可能性
2−20次のコードセグメントの時間的複雑さは(B)である.
A.O(1) B.O(mn) C.O(m^2) D.O(n^2)
2−21次のコードセグメントの時間的複雑さは(B)である.
A.O(n) B.O(n^2) C.O(n^3) D.O(2^n)
2-22次のコード
の時間的複雑度は、B A.O(N^3)B.O(N^4)C.O(N^5)D.O(N^6)
5-1アルゴリズムの実行時間を測定する次のプログラムは、ある関数Fの実行時間を測定する.空白に適当な内容を記入し、その手順を完了してください.
実行結果の例
注意:図のデータはサンプルのみで、実際の結果は異なる場合があります.
2-1以下データ構造についての言い方で正しいのは_A__. A.データ構造の論理構造が、その記憶構造Bとは独立したデータ構造の記憶構造が、そのデータ構造の論理構造Cとは独立したデータ構造の論理構造が、そのデータ構造の記憶構造Dを一意に決定する.データ構造は、その論理構造と記憶構造のみによって決定される
2−2以下のプログラム区間の時間的複雑度は(A)である.x=90; y=100; while(y>0) if(x>100) { x=x-10; y–; } else x++; A.O(1) B.O(N) C.O(N^2) D.O(log2 N)
2-3あるデータオブジェクトは3つの要素A,B,Cで構成され,要素間関係の集合は{,},このデータオブジェクトの論理構造は(C)A.線形構造B.ツリー型構造C.グラフ構造D.集合構造であるである.
2−4所与のプログラム時間複雑度の繰返し式:T(1)=1,T(N)=2 T(N/2)+N.プログラム時間の複雑度は、C A.O(logn)B.O(N)C.O(Nlogn)D.O(N^2)である
2-5次の関数の中で、どの関数が最も遅い成長速度を持っていますか:B A.N^1.5 B.NlogN^2 C.N 2 logN D.N(logN)2
2−6次のセグメントはアルゴリズム(A)の原則に反する.
void sam()
{
int n=2;
while (n%2==0) n+=2;
printf(“%d”,n);
}
A.貧乏性B.確定性C.実行可能性D.丈夫性
2−7次のセグメントを実行する場合のS文の実行頻度は(D)である.
for(int i=0;i<n;i++)
for(int j=1;j<=i;j++)
S;
A.n^2 B.n^2/2 C.n(n+1) D.n(n+1)/2
2−8アルゴリズム解析の目的は(A)である.A.データ構造の合理性を探し出すB.アルゴリズム中の入力と出力の関係を研究するC.アルゴリズムの効率を分析してD.分析アルゴリズムの分かりやすさとドキュメント性を改善する
2−9データを格納する際には、通常、各データ要素の値だけでなく(C)も格納する.A.データの処理方法B.データ要素の種類C.データ要素間の関係D.データの格納方法
2−10以下のプログラムの時間的複雑度は(C)である.
for(i = 0; i < m; i++)
for(j = 0; j < n; j++ )
A[i][j] = i*j;
A.O(m^2) B.O(n^2) C.O(m × n) D.O(m + n)
2−11次のプログラムの時間的複雑度は(A)である.
for(i = 0; i < m; i++)
for(j = 0; j < t; j++)
c[i][j] = 0;
for(i = 0; i < m; i++)
for(j = 0; j < t; j++)
for(k = 0; k < n; k++)
c[i][j] = c[i][j]+a[i][k] * b[k][j];
A.O(m × n × t) B.O(m + n + t) C.O(m + n × t) D.O(m × t + n)
2−12あるアルゴリズムの時間的複雑度はO(n^2)であり,このアルゴリズムの(D)を示す.(2点)A.問題規模はn^2 B.問題規模はn^2に比例するC.実行時間はn^2 D.実行時間はn^2に比例する
2-13以下のセグメントの時間的複雑度はB
for (int i = 0; i * i < n; i++) {
printf("%d
", i);
}
A.O(n) B.O(√n) C.O(n2) D.O(nlgn)
2−14データのコンピュータメモリにおける表現は(A)である.A.データの記憶構造B.データ構造C.データの論理構造D.データ要素間の関係
2−15以下のデータの論理構造に関する記述では,(A)が正しい.A.データの論理構造は、データ要素間の関係の記述であるB.データの論理構造は、コンピュータにおけるデータの記憶方式C.データの論理構造を反映している.
2−16以下のアルゴリズムに関する説で誤っているのは(A)である.A.アルゴリズムとプログラムはすべて具体的なコンピュータと具体的なプログラミング言語から独立しているB.プログラムはプログラミング言語で表すアルゴリズムC.フローチャートはアルゴリズムの図形化記述D.プログラム記述アルゴリズムであるが、アルゴリズムは必ずしもプログラムではない
2−17アルゴリズム解析の目的は(C)である.A.データ構造の合理性を探し出すB.アルゴリズム中の入力と出力の関係を研究するC.アルゴリズムの効率を分析してD.分析アルゴリズムの可読性と簡明性を改善する
2−18対のアルゴリズム解析の前提は(B)である.A.アルゴリズムは簡単でなければならないB.アルゴリズムは正確でなければならないC.アルゴリズムの構造性が強いD.アルゴリズムは通用しなければならない
2-19アルゴリズム設計の要求良いアルゴリズムを設計するには、正確性、A.可用性B.可読性C.信頼性D.実現可能性
2−20次のコードセグメントの時間的複雑さは(B)である.
for ( i=0; i<n; i++ )
for ( j=0; j<m; j++ )
a[i][j]=0;
A.O(1) B.O(mn) C.O(m^2) D.O(n^2)
2−21次のコードセグメントの時間的複雑さは(B)である.
x=0;
for( i=1; i<n; i++ )
for ( j=1; j<=n-i; j++ )
x++;
A.O(n) B.O(n^2) C.O(n^3) D.O(2^n)
2-22次のコード
if ( A > B ) {
for ( i=0; i<N*N/100; i++ )
for ( j=N*N; j>i; j-- )
A += B;
}
else {
for ( i=0; i<N*2; i++ )
for ( j=N*3; j>i; j-- )
A += B;
}
の時間的複雑度は、B A.O(N^3)B.O(N^4)C.O(N^5)D.O(N^6)
5-1アルゴリズムの実行時間を測定する次のプログラムは、ある関数Fの実行時間を測定する.空白に適当な内容を記入し、その手順を完了してください.
#include
#include
int F(int x);
int main()
{
clock_t t1, t2;
double t;
int x, y;
printf("x = ? ");
scanf("%d", &x);
t1 =clock() (2 );
y = F(x);
t2 =clock() (2 );
t =(double)(t2-t1) / CLOCKS_PER_SEC (3 );
printf("y = %d
", y);
printf("It took %.2f second(s)
", t);
return 0;
}
int F(int x)
{
......
}
実行結果の例
x = ? 25
y = 3712
It took 1.25 second(s)
注意:図のデータはサンプルのみで、実際の結果は異なる場合があります.