【正文】 第一章　緒論一、選擇題( )是數(shù)據(jù)的基本單位。 A) 數(shù)據(jù)結(jié)構(gòu) 　　B)數(shù)據(jù)元素 　　C)數(shù)據(jù)項 　　　D)數(shù)據(jù)類型以下說法不正確的是( )。 Ａ)數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)之間的邏輯結(jié)構(gòu)。 Ｂ)數(shù)據(jù)類型可看成是程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。Ｃ)數(shù)據(jù)項是組成數(shù)據(jù)元素的最小標(biāo)識單位。 Ｄ)數(shù)據(jù)的抽象運算不依賴具體的存儲結(jié)構(gòu)。計算機(jī)算法是解決問題的有限運算序列,它具備輸入、輸出和（　?。┑?個特性。A)可執(zhí)行性、可移植性和可擴(kuò)充性　　　　B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性 　　　　　　D)易讀性、穩(wěn)定性和安全性一般而言，最適合描述算法的語言是( )。 A)自然語言 B)計算機(jī)程序語言 C)介于自然語言和程序設(shè)計語言之間的偽語言 D)數(shù)學(xué)公式通常所說的時間復(fù)雜度指( )。A)語句的頻度 　　 B)算法的時間消耗C)漸近時間復(fù)雜度 　　 D)最壞時間復(fù)雜度A算法的時間復(fù)雜度為O(n3)，B算法的時間復(fù)雜度為O(2n)，則說明( )。 A)對于任何數(shù)據(jù)量，A算法的時間開銷都比B算法小 B)隨著問題規(guī)模n的增大，A算法比B算法有效 C)隨著問題規(guī)模n的增大，B算法比A算法有效 D)對于任何數(shù)據(jù)量，B算法的時間開銷都比A算法小算法分析的目的是（ ）。A)找出數(shù)據(jù)結(jié)構(gòu)的合理性 　　　　B)研究算法中的輸入和輸出的關(guān)系C)分析算法的效率以求改進(jìn) 　　　D)分析算法的易懂性和文檔性下面程序段的時間復(fù)雜度為（ ）。 for( i=0。 im。 i++) for( j=0。 jn。 j++) a[i][j]=i*j。A)O(m2) B) O(n2) C) O(m*n) D) O(m+n)下面算法的時間復(fù)雜度為( )。 int f ( int n ) { if ( n= =0 || n= =1 ) return 1。 else return n*f (n1)。 }A) O(1) B) O(n) C) O(n2) D) O(n!)二、填空題數(shù)據(jù)的( 　　)結(jié)構(gòu)依賴于計算機(jī)語言。在線性結(jié)構(gòu)中，第一個結(jié)點（ ）前驅(qū)結(jié)點,其余每個結(jié)點有且只有（ ）個前驅(qū)結(jié)點；最后一個結(jié)點（ ）后繼結(jié)點；其余每個結(jié)點有且只有（ ）個后繼結(jié)點。在樹形結(jié)構(gòu)中,樹根結(jié)點沒有（ ）結(jié)點，其余每個結(jié)點有且只有（ ）個前驅(qū)結(jié)點；葉子結(jié)點沒有（ 　?。┙Y(jié)點，其余每個結(jié)點的后繼結(jié)點可以（ 　　　 ）。 在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著( 　　 ) 、（ ）和（ ）的關(guān)系。 評價一個算法優(yōu)劣的兩個主要指標(biāo)是（ ）和（ ）。數(shù)據(jù)的邏輯結(jié)構(gòu)被分為( )、( )、( )和( )四種。數(shù)據(jù)的存儲結(jié)構(gòu)被分為( )、（ ）、（ ）、（ ）四種.算法的時間復(fù)雜度除了與問題的規(guī)模有關(guān)外，還與輸入實例的( 　)有關(guān)。三、問答題與算法題 簡述下列概念：數(shù)據(jù)元素：數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)類型：數(shù)據(jù)的邏輯結(jié)構(gòu)及其4種類型：數(shù)據(jù)的存儲結(jié)構(gòu)及其4種方式：設(shè)兩個算法在同一臺機(jī)器上執(zhí)行，其執(zhí)行時間分別是 n2和2 n ，要使前者快于后者，n至少需要多大？有時為比較兩個同數(shù)量級的算法優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用”O(jiān)”記號表示。如：設(shè)T1 ( n ) = n log n + 100 n + 256 = n log n + O ( n ) 。 T2 ( n ) = n log n 2 n = n log n –O( n ) 。這兩個式子表示，當(dāng)n足夠大時，T1 ( n )優(yōu)于T2 ( n )，因為前者的系數(shù)因子小于后者。請用此方法表示下列函數(shù)，并指出當(dāng)n足夠大時，哪一個較優(yōu)，哪一個較劣。 (1 ) T1 ( n ) = 5n 2 3 n +60 log n 。 (2 ) T2 ( n ) = 3 n 2 +1000 n + 3 log n 。 (3 ) T3 ( n ) = 8 n 2 + 3 log n 。 　　 (4 ) T4 ( n ) = n 2 + O ( n ) 。計算執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為。 for(i=1。 i=n。 i++) for( j=1。 j=i。 j++) S。第二章　線性表一、 選擇題線性表是具有n個（　?。┑挠邢扌蛄小? A) 數(shù)據(jù)項；　B) 數(shù)據(jù)元素；　C) 數(shù)據(jù)對象；　D) 表元素。以下關(guān)于線性表的說法不正確的是( )。 A) 線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B) 線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。 C) 線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。 D) 存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。線性表的順序存儲結(jié)構(gòu)是一種( )的存儲結(jié)構(gòu)。 A) 隨機(jī)存取　 B) 順序存取 　 C) 索引存取 　　D) 散列存取在順序表中，只要知道( )，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。A) 基地址 　B) 結(jié)點大小 　 C) 線性表大小 　　D) 基地址和結(jié)點大小下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ ）A) 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B) 線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C) 線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D) 線性表采用鏈接存儲，便于插入和刪除操作。線性表采用鏈表存儲時其存儲地址要求（　　?。?。A) 必須是連續(xù)的；　　B) 部分地址必須是連續(xù)的；C) 必須是不連續(xù)的；　D) 連續(xù)和不連續(xù)都可以。一個長度為n的線性表順序存儲，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需要從后向前依次后移 ( ) 個元素。A) ni B) ni+1 　　　 C) ni1 　 D) i( )運算中，使用順序表比鏈表好。 A) 插入 　B) 刪除 　　　C) 根據(jù)序號查找　　　　D) 根據(jù)元素值查找向具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是( )。 A) O(1) 　　 B) O(n) 　　 C) O(n2) 　　　　D) O(log2n)在一個長度為n的順序存儲的線性表中，刪除第i個元素(1≤i≤n)時，需要從前向后依次前移( )個元素。A) ni 　　　 B) ni+1 　　　 C) ni1 　　 D) i1在一個長度為n的線性表中順序查找值為x的元素時，平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 ( )。A) n B) n/2 　　　 C) (n+1)/2 　 D) (n1)/21在一個帶頭結(jié)點的單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行的語句是( )。 A) HL = p。 pnext = HL?！　? 　 B) pnext = HL。 HL = p。 C) pnext = HL。 p = HL。 　　　D) pnext = HLnext。 HLnext = p。1在一個單鏈表HL中，若要在指針q所指的結(jié)點的后面插入一個由指針p所指的結(jié)點，則執(zhí)行( )。 A) qnext = pnext 。 pnext = q。 　　 B) pnext = qnext。 q = p。 C) qnext = pnext。 pnext = q。 　　D) pnext = qnext 。 qnext = p。1在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(zhí)行( )。A) p = qnext 。 pnext = qnext。 　 B) p = qnext 。 qnext = p。C) p = qnext 。 qnext = pnext。 　 D) qnext = qnextnext。 qnext = q。1在雙向鏈表中，在指針p所指的結(jié)點前插入一個指針q所指的結(jié)點，操作是（ ）。A) pPrior=q?！Next=p?！PriorNext=q?！Prior=q；B) pPrior=q。　pPriorNext=q?！Next=p。　qPrior=pPrior。C) qNext=p。　qPrior=pPrior。　pPriorNext=q?！Prior=q。D) qPrior=pPrior。　qNext=q。　pPrior=q?！next=q。二、 填空題對于一個具有n個結(jié)點的單鏈表，在已知結(jié)點*p的后插入一個新結(jié)點的時間復(fù)雜度為（　　　　?。?在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（　　　?。?。根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成（　　　　　?。┖停ā　　　　　　。?。順序存儲結(jié)構(gòu)是通過( )表示元素之間的關(guān)系的。鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過( )表示元素之間的關(guān)系的。對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改( )個指針，單鏈表為( )個。循環(huán)單鏈表的最大優(yōu)點是( 　 ) 。在無頭結(jié)點的單鏈表中，第1個結(jié)點的地址存放在頭指針中，其他結(jié)點的存儲地址存放在( 　　　 )結(jié)點的next域中。帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是（　　　　　　　　　　　?。．?dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用( 　　　 )存儲結(jié)構(gòu)。求順序表和單鏈表的長度算法的時間復(fù)雜度分別是 ( 　　　 )和 ( 　　　 )。順序表存儲結(jié)構(gòu)的優(yōu)點是( )、( )、( )；缺點是 ( )。1單鏈表存儲結(jié)構(gòu)的優(yōu)點是( )、 ( )；缺點是 ( )、 ( )。1在單鏈表中，設(shè)置頭結(jié)點的作用是 ( ) 。1鏈接存儲的特點是利用( )來表示數(shù)據(jù)元素之間的邏輯關(guān)系。1帶頭結(jié)點的雙循環(huán)鏈表DL為空表的條件是：( )。1以下算法的功能是：在一個非遞減的順序表中，刪除所有值相等的多余元素。在畫線處填上適當(dāng)?shù)恼Z句，將程序補(bǔ)充完整。 define maxlen 100 typedef struct { elemtype a[ maxlen ] 。 int length 。 } sqlist 。void delequil ( sqlist amp。 S ) { int j=1 , i = 2 。 while ( _________________ ) { if ( [ i ] != [ j ] ) { ____________ 。 ______________ 。 } i ++ 。 } ______________ 。 }16．設(shè)雙鏈表的結(jié)點的存儲結(jié)構(gòu)如下：刪除鏈表中指針p所指結(jié)點的兩步主要操作是：Llink Data Rlinkp( )， ( )。三、 問答題與算法題試描述頭指針、頭結(jié)點、首結(jié)點的區(qū)別、并說明頭指針和頭結(jié)點的作用。何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜?為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?下述算法的功能是什么?LinkList ABC(LinkList L){ // L 是無頭結(jié)點單鏈表　if( Lamp。amp。Lnext ){ Q=L。 L=Lnext。 P=L。　　while (Pnext) P=Pnex