第一單元(算法分析線性表)T

1、第一單元課后自測練習(xí)題知識點范圍：第1章緒論、第2章線性表一、選擇題1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 。A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指 。A數(shù)據(jù)的存儲結(jié)構(gòu) B數(shù)據(jù)結(jié)構(gòu) C數(shù)據(jù)的邏輯結(jié)構(gòu) D數(shù)據(jù)元素之間的關(guān)系3在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)。A邏輯 B存儲 C邏輯和存儲 D物理4在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲 。A數(shù)據(jù)的處理方法 B數(shù)據(jù)元素的類型 C數(shù)據(jù)元素之間的關(guān)系 D數(shù)據(jù)的存儲方法5算法分析的目的是 ，算法分析的兩個主要方面是 。1A找出數(shù)據(jù)結(jié)構(gòu)

2、的合理性 B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進 D分析算法的易讀性和文檔性2A空間復(fù)雜度和時間復(fù)雜度 B正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6下面程序段的時間復(fù)雜度是 。 s =0;for( I =0; i<n; i+) for(j=0;j<n;j+)s +=Bij;sum = s ;7下面程序段的時間復(fù)雜度是 。for( i =0; i<n; i+) for(j=0;j<m;j+)Aij 0;8下面程序段的時間復(fù)雜度是 。i 0；whilei<=ni+；9鏈表不具備的特點是 。A可隨機訪問任一結(jié)點 B插入刪除不需要移動元素

3、C不必事先估計存儲空間 D所需空間與其長度成正比10不帶頭結(jié)點的單鏈表head為空表的判定條件是 。Ahead = NULL B head->next =NULL Chead->next =head D head!=NULL11帶頭結(jié)點的單鏈表head為空表的判定條件是 。Ahead = NULL B head->next =NULL Chead->next =head D head!=NULL12需要分配較大空間，插入和刪除需要移動元素的線性表，其存儲結(jié)構(gòu)是 。A單鏈表 B鏈表 C線性鏈表 D順序存儲結(jié)構(gòu)13在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序

4、的時間復(fù)雜度是 。AO1 BOn COn2 DOnlog2n14在一個長度為nn>1的單鏈表上，設(shè)有指向頭結(jié)點的指針head和指向數(shù)據(jù)結(jié)點的指針p，執(zhí)行 操作與鏈表的長度有關(guān)。A刪除單鏈表中的第一個元素B刪除單鏈表中的最后一個元素C在單鏈表第一個元素前插入一個新元素D在單鏈表最后一個元素后插入一個新元素15在長度為n的順序表的第i個位置上插入一個元素1 i n+1，元素的移動次數(shù)為： 。An i + 1 Bn i Ci Di 1 16設(shè)指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，那么在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為。(A) s->

5、next=p->next；p->next=-s；(B) q->next=s； s->next=p；(C) p->next=s->next；s->next=p；(D) p->next=s；s->next=q；17下面關(guān)于線性表的表達中，錯誤的選項是哪一個？ 。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯?，不必占用一片連續(xù)的存儲單元D線性表采用鏈?zhǔn)酱鎯?，便于進行插入和刪除操作。18線性表是具有n個 的有限序列。A字符 B數(shù)據(jù)元素 C數(shù)據(jù)項 D表元素19在n個結(jié)點的線性表的順序

6、存儲結(jié)構(gòu)中，算法的時間復(fù)雜度是O1的操作是 。A訪問第i1<=i<=n個結(jié)點B在第i1<=i<=n個結(jié)點后插入一個新結(jié)點C刪除第i1<=i<=n個結(jié)點D以上都不對20假設(shè)長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為 。AO(0) BO(1) CO(n) DO(n2)21線性表a1,a2, ,an以鏈?zhǔn)椒绞酱鎯?，訪問第i位置元素的時間復(fù)雜度為 。AO(0) BO(1) CO(n) DO(n2)22單鏈表中，增加一個頭結(jié)點的目的是為了 。A使單鏈表至少有一個結(jié)點 B標(biāo)識表結(jié)點中首結(jié)點的位置C方面運算的實現(xiàn) D說明單鏈表是線性

7、表的鏈?zhǔn)酱鎯?3在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是 。Ap->next=s；s->next=p->next B s->next=p->next ；p->next=s;Cp->next=s；p->next=s->next Dp->next=s->next；p->next=s24線性表的順序存儲結(jié)構(gòu)是一種 。A隨機存取的存儲結(jié)構(gòu) B順序存取的存儲結(jié)構(gòu)C索引存取的存儲結(jié)構(gòu) DHash存取的存儲結(jié)構(gòu)25下面程序的時間復(fù)雜為 fori=1，s=0； i<=n； i+ t=1；for(j=1；j<=

8、i；j+) t=t*j；s=s+t；(A) O(n)(B) O(n2)(C) O(n3)(D) O(n4)二、填空題。1數(shù)據(jù)邏輯結(jié)構(gòu)包括 、 和 三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱 。2數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)數(shù)據(jù)間關(guān)系分為 、 、 和 4種。3在線性結(jié)構(gòu)中，第一個結(jié)點 沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 個前驅(qū)結(jié)點；最后一個結(jié)點 后續(xù)結(jié)點，其余每個結(jié)點有且只有 個后續(xù)結(jié)點。4線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。5數(shù)據(jù)結(jié)構(gòu)的根本存儲方法是 、 、 和 存儲 。6衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和 度與 度 。7評估一個算法的優(yōu)劣，

9、通常從 和 兩個方面考察。8算法的5個重要特性是 、 、 、輸入和輸出。9在一個長度為n的順序表中刪除第i個元素時，需向前移動 個元素。10在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的 結(jié)點。11在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動 個數(shù)據(jù)元素，移動數(shù)據(jù)元素的個數(shù)與 有關(guān)。12當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用 存儲結(jié)構(gòu)。13根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的一個指針個數(shù)的線性鏈表稱為 。14順序存儲結(jié)構(gòu)是通過 下標(biāo) 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過 表示元素之間的關(guān)系的。15一個算法的時間復(fù)雜度為

10、(n3+n2log2n+14n)/n2，其數(shù)量級表示為_ _。三、判斷題1在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。2抽象數(shù)據(jù)類型ADT包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。3抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)。 4順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩?5線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。 6對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。 7順序存儲方式只能用于存儲線性結(jié)構(gòu)。 8集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。 9線性表中每個元素都有一個直接前驅(qū)和

11、一個直接后繼。 10線性表就是順序存儲的表。 11取線性表的第i個元素的時間同i的大小有關(guān)。 12鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序表中效率高。 13在單鏈表中，給定任一結(jié)點的地址p，那么可用下述語句將新結(jié)點s插入結(jié)點p的后面 ：p->next = s; s->next = p->next; ( )14線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。15對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。()四、計算題在如下數(shù)組A中鏈?zhǔn)酱鎯α艘粋€線性表L，表頭指針為A 0.next，試寫出該線性表L的表示。 A 0 1 2 3 4 5 6 7 data605078903440next3572041五、閱讀算法1. LinkList mynote(LinkList L) /L是不帶頭結(jié)點的單鏈表的頭指針 if(L&&L->next) q=L；L=L>next；p=L； S1： while(p>next) p=p>next； S2： p>next=q；q>next=NULL； return L； 請答復(fù)以下問題： 1說明語句S1的功能； 2說明語句