データ構造論文(1)
1. 選択式問題(1問2点、合計20点)
1. スタックとキューの共通の特徴は( )。
A. エンドポイントでの要素の挿入と削除のみを許可する
B. 先着最後の出番
C. 先着先着先着です
D. 共通の基盤が存在しない
2. リンク方式で保存されたキューは挿入操作を行う際に挿入されます()。
A. ヘッドポインターのみが修正される B. ヘッドポインターとテールポインタは修正しなければならない
C. テールポインタのみを修正する D. ヘッドポインタとテールポインタを変更する必要がある場合があります。
3. 以下のデータ構造のうち、非線形構造はどれか? ( )
A. キュー B. スタック C. 線形テーブル D. バイナリツリー
4. 二次元配列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[3]の添字は( )
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回1点、合計26点)
1. アルゴリズムの品質は通常、_________、_________、_________、_________の4つの側面から評価されます。
2. アルゴリズムの時間計算量は (n3+n2log2n+14n)/n2 であり、その桁数は ________ と表されます。
3. 木の一般化テーブルがA(C,D(E,F,G),H(I,J))と表されると、木に含まれるノード数は__________、木の深さは___________、木の次数は_________である。
4. 接尾辞式9 2 3 +- 10 2 / -の値は__________です。 中間の式(3+4X)-2Y/3に対応する接尾辞式は_______________________________です。
5. 二分木が連結リストで保存されている場合、各ノードはデータフィールドに加えて左の子と右の子への2つのポインタを持ちます。 この記憶構造では、nノードを持つ二分木には合計________ポインタフィールドがあり、そのうち________ポインタフィールドはアドレスを保存し、________________ポインタは空のポインタです。
6. n頂点とEバー辺を持つ有向グラフと無向グラフの場合、対応する隣接テーブルにはそれぞれ_______辺ノードと________辺ノードがあります。
7. AOVネットワークは___________________グラフです。
8. 頂点数がn個の無向完全グラフでは辺が________本、頂点数がn個の有向完全グラフでは________辺が存在する。
9. 線形表が(12,23,74,55,63,40)であると仮定すると、同じ余りの要素がキー%4条件に従って部分表になると、得られる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. HASHルックアップ技術を効果的に適用するためには、____________________と__________________________の2つの問題を解決する必要があります。
2. 次のプログラムセグメントの関数はデータxをスタックに変換し、正しい文を下線に記入する必要があります。
typedefstruct {int s[100]; イントトップ; } sqstack;
ヴォイドプッシュ(sqstack&stack,int x)
{
もし(stack.top==m-1) printf(「オーバーフロー」);
そうでなければ{____________________; _________________; }
}
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問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->next; q->data=p->data; p->next=q->next; free(q);
(C) q=p->next; p->next=q->next; free(q);
(D) q=p->next; 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(log2n) (C) (D) O(n2)
7. 無向グラフGに頂点eの辺がn個あると仮定すると、対応する隣接テーブルのヘッダーノードとテーブルノードの数は( )。
(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. 以下の4種類の( )は空間的複雑さが最も大きい。
(A) 挿入ソート (B) バブルソート (C) ヒープソート (D) マージソート
2. 空欄を埋める(1回1点、合計20点)
1. データの物理的構造は主に2つの状況、_____________と______________を含みます。
2. 完全二分木に500のノードがある場合、その深さは__________; 完全な二分木の保存構造として二分連結リストを使うと、空のポインタフィールド___________存在します。
3. 入力列が1、2、3であれば、スタックの作用後に___________異なる出力列が得られます。
4. グラフGの記憶構造として隣接行列A[n][n]を用いる場合、隣接行列iの行のすべての要素の和は頂点iの________に等しく、列iのすべての要素の和は頂点iの________に等しくなります。
5. ハフマン木にノードがn個ある場合、ハフマン木には次数が1のノードが________つ存在します。
6. 方向性グラフGに方向性のある辺を持つ頂点eがn個存在し、次数に入るすべての頂点の和がdであれば、eとdの関係は_________となります。
7. バイナリソートツリーのノードを__________巡査することで、キーワードの増分列(filled、middle、posterior)を得ることができます。
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 (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; もし(i==j)を返すなら(-1); }
もし(_______________________)なら(j)を返す。 それ以外の場合は(-1);
}
14. 以下のアルゴリズムは二値ソートツリーの鍵値kを実装しています。アンダースコアの正しい文を記入してください。
typedefstruct node{int key; structノード *lchild; structノード *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
もし(t==0)なら(0)を返す; それ以外の場合は(t!=0)
もし (t->key==k)_____________; そうでなければ (t->key>k) t=t->lchild; else_____________;
}
データ構造テストペーパー(1)回答を参照
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回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 0:10:55