【正文】 。 A．98 B．100 C．102 D．10610．在順序存儲的線性表（a1……an）中，刪除任意一個結點所需移動結點的平均移動次數(shù)為( ) A．n B．n／2 C．(n1)/2 D．（n＋l）/211．在線性表的下列存儲結構中，讀取第i個元素花費的時間最少的是（）。 A．ni B．ni＋1 C．n－i－1 D．i＋18．如果某鏈表中最常用的操作是取第i個結點及其前驅，則采用( )存儲方式最節(jié)省時間。 A．O（long2n） B．O（l） C．O（n2） D．O（n）6．線性表是( )。 A．O(n) B．O(1) C．O(n2） D．O（long2n） 4．線性表采用鏈式存儲時，其地址( )。 A．ni B．ni+1 C．ni1 D．i+12．從一個具有n個元素的線性表中查找其值等于x的結點時，在查找成功的情況下，需平均比較( )個元素結點。6．將下列函數(shù)，按它們在n→∝時的無窮大階數(shù)，從小到大排序。4. 該算法的時間復雜度為：log3(n)。 if（i＞sqrt(n) ) printf（”％d is a prime number.＼n”，n）； else printf（”％d is not a prime number.＼n”，n）；｝1. 該算法的時間復雜度為：O(mn)。while（i＜＝n） i=i*3。 j++） for（k=0；k＜n；k＋＋） c［i］［j］＋＝a［i］［k］*b[k][j]。 j＋＋） c[i][j]=0；for（i=0；i＜m；i＋＋） for（j=o。 i＋＋）for（j＝0 。 ｝ 3．寫出以下算法的時間復雜度： for（i＝0。（）四、綜合題 1．用大O形式表示下面算法的時間復雜度： for（i=0；i＜m；i十十） for（j=0；j＜n；j＋＋） A[i][j]=i*j； 2．寫出下面算法的時間復雜度： i＝0； s=0； while(s＜n） ｛ i++。 () 14. 判斷一個算法的好壞主要以下幾個標準：正確性、有窮性、健壯性和可行性。()12. 數(shù)據(jù)結構的基本操作的設置的最重要的準則是，實現(xiàn)應用程序與存儲結構的獨立。()10. 在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。（） 8．具有存取任一元素的時間相等這一特點的存儲結構稱為隨機存取結構。 6．數(shù)據(jù)結構、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像分別稱為存儲結構、結點、數(shù)據(jù)域。() 4．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（） 2．數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（運行時間、所占據(jù)空間） 空間復雜度（SPace ComPlexity）也是度量一個算法好壞的標準，它所描述的是算法在運行過程中所占用_____________的大小。（可行性） 1判斷一個算法的好壞主要以下幾個標準：________、________、________、_________。并且，在任何條件下，算法只能有惟一的一條執(zhí)行路徑，即只要輸人是相同的就只能得到____________的輸出結果。（有限序列、有窮性、確定性、可行性、輸入、輸出）1算法的_______性是指算法必須能夠在執(zhí)行有限個步驟之后結束，并且每個步驟都必須在有窮的時間內(nèi)完成。（散列存儲或哈希存儲） 1所謂算法（Algorithm）是對特定問題求解步驟的一種描述，它是指令的其中每個指令表示一個或多個操作。（順序存儲） 1_______方式是種存儲方法，不要求邏輯上相鄰的結點在物理上也相鄰，即數(shù)據(jù)元素可以存儲在任意的位置上。（非線性結構、線性結構、非線性機構） 1____________方式是指邏輯上相鄰的結點被存儲到物理上也相鄰的存儲單元中。在這種邏輯結構中，所有結點均可以有多個前驅和多個后繼。（線性結構） 數(shù)據(jù)邏輯結構的四種基本類型中，____________中的元素是一種一對多的關系。（存儲結構、存儲結構） 數(shù)據(jù)邏輯結構可以分為四種基本的類型，_______結構中的元素除了僅僅只是同屬于一個_________________，不存在什么關系。（邏輯關系、邏輯關系、數(shù)學模型） 數(shù)據(jù)的________指數(shù)據(jù)元素及其關系在計算機存儲器內(nèi)的表示。邏輯結構是從________上描述數(shù)據(jù)，它與具體存儲無關，是獨立于計算機的。例如構成一個數(shù)據(jù)元素的字段、域、屬性等都可稱之為________。（數(shù)據(jù)、數(shù)據(jù)） 數(shù)據(jù)元素是數(shù)據(jù)的______，有些情況下也稱為元素、結點、頂點、記錄等。A．哈夫曼樹 C. 二叉排序樹 D. 棧12．以下屬于邏輯結構的是（ ）。j++) x=x+1。i++） for(j=0。A．循環(huán)隊列 B. 鏈表 C. 哈希表 D. 棧9．在下面的程序段中，對x的賦值語句的頻度為（ ）for（i=0。A．找出算法的合理性 B．研究算法的輸人與輸出關系C．分析算法的有效性以求改進 D．分析算法的易懂性5. 算法的時間復雜度取決于（ ）A．問題的規(guī)模B待處理數(shù)據(jù)的初態(tài) C. A和B6．一個算法應該是（ ）。A．動態(tài)結構和靜態(tài)結構 B．緊湊結構和非緊湊結構C．線性結構和非線性結構 D．邏輯結構和存儲結構3．線性表的邏輯順序和存儲順序總是一致的，這種說法（）。數(shù)據(jù)結構習題集（自編）第一章 緒論一、選擇題1．數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中的操作對象以及它們之間的（）和運算的學科。 A．結構 B．關系 C．運算 D．算法2．在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（）。 A．正確 B．不正確 C．無法確定 D．以上答案都不對4．算法分析的目的是（）。A．程序 B．問題求解步驟的描述 C．要滿足五個基本特性 D．A和C. 7. 下面關于算法說法錯誤的是（ ）A．算法最終必須由計算機程序實現(xiàn)C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的8．以下與數(shù)據(jù)的存儲結構無關的術語是（ ）。in。jn。A． 2n B．n C．n2 D．log2n 10．以下數(shù)據(jù)結構中，（ ）是非線性數(shù)據(jù)結構A．樹 B．字符串 C．隊列 D．棧11. 下列數(shù)據(jù)中，（ ）是線性數(shù)據(jù)結構。A．順序表 B. 哈希表 D. 單鏈表二、填空題_______是信息的載體，是對客觀事物的符號表示，它能夠被計算機識別、存儲、加工和處理，________是對能夠有效的輸人到計算機中并且能夠被計算機處理的符號的總稱。（基本單位）________是數(shù)據(jù)不可分割的最小單元，是具有獨立含義的最小標識單位。（數(shù)據(jù)項、數(shù)據(jù)項） 數(shù)據(jù)的邏輯結構是指數(shù)據(jù)之間的________。因此邏輯結構可以看作是從具體問題抽象出來的______________。_________是邏輯結構在計算機里的實現(xiàn)，也稱之為映像。（集合、集合） 數(shù)據(jù)邏輯結構的四種基本類型中，________中的元素是一種一對一的關系，這種結構的特征是：若結構是非空集，則有且只有一個開始結點和一個終端結點，并且所有結點最多只能有一個直接前驅和一個直接后繼。（樹形結構） 圖型結構或圖狀結構是一種________的關系。（多對多） 有時也可將樹型結構、集合和圖型結構稱為__________，這樣數(shù)據(jù)的邏輯結構就可以分為__________和________兩大類。這種存儲結構只存儲結點的數(shù)值，不存儲結點之間的關系，結點之間的關系是通過存儲單元的相鄰關系隱含的表示出來的。（鏈式存儲） 1_________方式是利用結點關鍵字的值直接計算出該結點存儲單元地址，然后將結點按某種方式存人該地址的一種方法。算法的五個重要特性是__________、__________、__________、__________和__________。（有窮性） 1算法的________性是指算法中的每一個步驟必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。（確定性、相同） 1算法的____________性又稱為算法的能行性，是指算法中描述的操作是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。（正確性、可讀性、健壯性、時間效率和空間效率） 1算法分析是對一種算法所消耗的計算機資源的估算，其中包括計算機_________的長短和___________________的大小。（存儲空間）三、判斷題 1．順序存儲方式只能用于存儲線性結構。（） 3．算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。()5．數(shù)據(jù)的邏輯結構是指各元素之間的邏輯關系，是根據(jù)用戶需要而建立的。（） 7．數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機中實際的存儲形式。9．算法實際上就是程序，程序也一定是算法。()11. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()13. 數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系,它依賴于計算機的儲存結構。() 15．算法的時間復雜度T（n）=O(f(n))表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率與函數(shù)f(n)的增長率相同。 s+=i。 i＜m。 j＜t。 jt。4．寫出下面算法的時間復雜度：i=1。5．求下面函數(shù)中各條語句的頻度和算法的時間復雜度：prime（int n）｛ int i＝2； while ((n％i）！=0＆＆i＜sqrt(n) ) i++。2. 該算法的時間復雜度為：O()3. 該算法的時間復雜度為：O(mnt)。5. 該算法的時間復雜度為：O()。 n, nn3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+logn從小到大排列為：logn, n1/2+logn, n, nlogn, n2+logn，n3, nn3+7n5, 2n/2, (3/2)n, n!,第二章 線性表一、選擇題 1．在一個長度為n的順序表中刪除第i個元素（0i=n）時，需要向前移動( )個元素。 A．n/2 B．n C．(n1)/2 D．(n +1)/2 3．對一個具有n個元素的線性表，建立其單鏈表的時間復雜度為( )。 A． 必須是連續(xù)的 B．一定是不連續(xù)的 C．部分地址必須連續(xù) D．連續(xù)與否均可以 5．在一個具有n個結點的有序單鏈表中插人一個新的結點，使得鏈表仍然有序，該算法的時間復雜度是( )。 A．一個有限序列，可以為空 B．一個有限序列，不可以為空 C．一個無限序列，可以為空 D．一個無限序列，不可以為空7．在一個長度為n的順序表中，向第i個位置（0一1＜n＋1）插入一個新元素時，需要向后移動( )個元素。 A．單鏈表 B．雙向鏈表 C．單循環(huán)鏈表 D．順序表9．一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（）。 A．單鏈表 B．雙鏈表 C．循環(huán)鏈表 D．順序表12．若某鏈表中最常用的操作為在最后一個結點之后插入一個結點和刪除最后一個結點，則采用（）存儲方式最節(jié)省時間。 A．pnext=pnextnext B．pnext=pnextC．p=pnextnext D．p=pnext。 A．snext=pnext。 B．qnext=s。C．pnext=snext。 D．pnext=s。 15．在單鏈表中附加頭結點的目的是為了（ ）。 A．不再需要頭指針了 B．從表中任意一個結點出發(fā)都能掃描到整個鏈表 C．已知某個結點的位置后，能夠容易找到它的前