專升本數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

1、1. 填空（ ）是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。（ ）是數(shù)據(jù)的最小單位，（ ）是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（ ）、（ ）、（ ）和（ ）。 數(shù)據(jù)的存儲結(jié)構(gòu)主要有（ ）和（ ）兩種基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲兩方面的內(nèi)容：（ ）和（ ）。 算法具有五個特性，分別是（ ）、（ ）、（ ）、（ ）、（ ）。 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為算法語言。 在一般情況下，一個算法的時間復(fù)雜度是（ ）的函數(shù)。 設(shè)待處理問題的規(guī)模為n，若一個算法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級的形

2、式為（ ），若為n*log25n，則表示成數(shù)量級的形式為（ ）。2. 選擇題 順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的，鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的。A 線性結(jié)構(gòu) B 非線性結(jié)構(gòu) C 存儲位置 D 指針 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（ ）。A 樹 B 圖 C 線性表 D 集合 算法指的是（ ）。A 對特定問題求解步驟的一種描述，是指令的有限序列。B 計算機程序 C 解決問題的計算方法 D 數(shù)據(jù)處理 下面（ ）不是算法所必須具備的特性。A 有

3、窮性 B 確切性 C 高效性 D 可行性 算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中輸入和輸出的關(guān)系C 分析算法的效率以求改進 D 分析算法的易讀性和文檔性E 空間性能和時間性能 F 正確性和簡明性G 可讀性和文檔性 H 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3. 判斷題 算法的時間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作：插入、刪除和查找。 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實現(xiàn)是唯一的。4. 分析以下各程序段，并用大O記號表示

4、其執(zhí)行時間。 i=1; k=0; while (in-1) k=k+10*i;i+; i=1; k=0; do k=k+10*i;i+; while (i=n) y=0; while (y+1)*(y+1)=n) y=y+1; i=1; j=0; while (i+jj) j+; else i+; for (i=1; i=n; i+) for ( j=1; j=i; j+) for ( k=1; k=j; k+) x+;5 設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D=1, 2, 3, 4, 5, 6，R=(1, 2),(2, 3),(2, 4),(3, 4),(3, 5),(3, 6),(4, 5),(4

5、, 6)。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。學(xué)習(xí)自測及答案1順序存儲結(jié)構(gòu)的特點是（ ），鏈接存儲結(jié)構(gòu)的特點是（ ）。2. 算法在發(fā)生非法操作時可以作出處理的特性稱為（ ）。3. 常見的算法時間復(fù)雜度用大記號表示為：常數(shù)階( )、對數(shù)階( )、線性階 ( )、平方階( )和指數(shù)階( )。4將下列函數(shù)按它們在n 時的無窮大階數(shù)，從小到大排列。 n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n5對下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分別畫出對應(yīng)的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。 A=(D，R)，其中D=a1, a2, a3, a4，R= B=(D，R)，其中D=a, b, c, d, e, f，R=, C=( D，R)，其中D=a，b，c，d，e，f，R=, D=(D，R)，其中D=1, 2, 3, 4, 5, 6， R=(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)