【正文】 } 習(xí)題答案 1. B 2. A, C 3. B 4. D 5. C 6. A 7. A 8. B 9. C 10. D 1. 線性結(jié)表 2. 前驅(qū)結(jié)點(diǎn)、后繼結(jié)點(diǎn) 3. s, p 4. qnext, q 5. pnext, s 6. O (1) , O (n)習(xí)題3 棧和隊(duì)列 單項(xiàng)選擇題1. 一個棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是____。 p=q。 pnext=Lnext。 { /* 對于當(dāng)前結(jié)點(diǎn)p，用頭插法將結(jié)點(diǎn)p插入到頭結(jié)點(diǎn)之后 */ p=Lnext。 NODEPTR p,q。}4. 試寫一算法，實(shí)現(xiàn)單鏈表的就地逆置(要求在原鏈表上進(jìn)行)。free(r)。 qdatab){r=q。}while(q!=L amp。 qdataa){p=q。 while(q!=L amp。void del(LinkList L,elemtype a,elemtype b){p= L。 }} 3. 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。 a[i]=a[j]。 ij。void reverse(int a[], int size){ int i,j,tmp。 return OK。i) [i+1]=[i]。amp。 for(i=。va,int x) { if(+1maxsize) return ERROR。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。 6. 對于一個具有n個結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度是__ __；在給定值為x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度是__ __。 //填空delete 。 //填空4. 在一個單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時，應(yīng)執(zhí)行以下操作：q= pnext。qnext= 。s= new Node。3. 在一個單鏈表中p所指結(jié)點(diǎn)之前插入一個s (值為e)所指結(jié)點(diǎn)時，可執(zhí)行如下操作：q=head。A. O(1)） B. O(n) C. O (n2) D. O (n*log2n) 填空題（將正確的答案填在相應(yīng)的空中）1. 單鏈表可以做__ __的鏈接存儲表示。A. n B. n/2 C. (n1)/2 D. (n+1)/2 15. 在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然有序的時間復(fù)雜度是__ __。 pnext= pnextnext；C. pnext= pnext。13. 在一個單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行____。 C. pnext=s。C. snext=pnext。 B. snext=pnext。A. snext=p。 snext=q。 snext=p。 snext=p。 pnext=s。 11. 在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行____。 prightleft=s。D. sleft=p。 pright=s。C. sleft=p。 sleft=p。B. pright=s。 prightleft=s。A. pright=s。A. head= =NULL B. headnext= =NULLC. headnext= =head D. head!=NULL9. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足____。A. 正確 B. 不正確7. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是____。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以5. 在以下的敘述中，正確的是__ _。A．隨機(jī)存取 B．索引存取 C．順序存取 D．散列存取3. 線性表的邏輯順序與存儲順序總是一致的，這種說法__ _。 習(xí)題答案 1. C , A 2. B,D 3. C 4. C, A 5. C,B 1. 線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)，非線性結(jié)構(gòu) 2. 沒有、沒有、1 3. 前驅(qū)、后續(xù)、任意多個 4. 任意多個 5. 一對一、一對多、多對多 6. 有窮性、確定性、可行性、輸入、輸出 7. 最大語句頻度：n2 ， 時間復(fù)雜度：. O (n2) 8. 最大語句頻度：n (n+1)/2 ， 時間復(fù)雜度：. O (n2) 9. 最大語句頻度：n3 ， 時間復(fù)雜度：. O (n3)10. 最大語句頻度：n ， 時間復(fù)雜度：. O (n) 11. 最大語句頻度：log2n， 時間復(fù)雜度：. O (log2n )習(xí)題2 線性表 單項(xiàng)選擇題1. 一個向量（即一批地址連續(xù)的存儲單元）第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是__ __。 算法設(shè)計(jì)題1. 試寫一算法,自大到小依次輸出順序讀入的三個數(shù)X,Y和Z的值.2. 試寫一算法,求出n個數(shù)據(jù)中的最大值。i=1。 s+=i。i=s=0。sum=s。kn。jn。in。s=0。 j++)A[i][j]=0。i++) for (j=0。for (i=0。 j++) A[i][j]=0。i++) for (j=0。for (i=0。6. 算法的五個重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。4. 在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 。2. 在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn) 前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn) 后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 個后續(xù)結(jié)點(diǎn)。① A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B. 研究算法中的輸入和輸出的關(guān)系C. 分析算法的效率以求改進(jìn) D. 分析算法的易懂性和文檔性② A. 空間復(fù)雜性和時間復(fù)雜性 B. 正確性和簡明性C. 可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性5. 計(jì)算機(jī)算法指的是① ，它必具備輸入、輸出和② 等五個特性。 ① A．算法 Ｂ．?dāng)?shù)據(jù)元素 Ｃ．?dāng)?shù)據(jù)操作 Ｄ．?dāng)?shù)據(jù)對象 ② A．操作 Ｂ．映象 Ｃ．存儲 Ｄ．關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。數(shù)據(jù)結(jié)構(gòu)練習(xí)題習(xí)題1 緒論 單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中,數(shù)據(jù)元素的① 、數(shù)據(jù)信息在計(jì)算機(jī)中的② 以及一組相關(guān)的運(yùn)算等的課程。 ① A．操作對象　　?。拢?jì)算方法　　Ｃ．邏輯結(jié)構(gòu)　?。模?dāng)?shù)據(jù)映象 ② A．存儲結(jié)構(gòu) Ｂ．關(guān)系 Ｃ．運(yùn)算 Ｄ．算法2. 數(shù)據(jù)結(jié)構(gòu)DS(Data Struct)可以被形式地定義為DS=（D，R），其中D是① 的有限集合，R是D上的② 有限集合。A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) Ｂ．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) Ｃ．線性結(jié)構(gòu)和非線性結(jié)構(gòu) Ｄ．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4. 算法分析的目的是① ，算法分析的兩個主要方面是② 。 ① A. 計(jì)算方法 B. 排序方法C. 解決問題的有限運(yùn)算序列 D. 調(diào)度方法② A. 可行性、可移植性和可擴(kuò)充性 B. 可行性、確定性和有窮性 C. 確定性、有窮性和穩(wěn)定性 D. 易讀性、穩(wěn)定性和安全性 填空題（將正確的答案填在相應(yīng)的空中）1. 數(shù)據(jù)邏輯結(jié)構(gòu)包括 、 和 三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為 。3. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 個直接前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的直接后續(xù)結(jié)點(diǎn)可以 。5. 線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。7. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時間復(fù)雜度是__ __。in。jn。8. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時間復(fù)雜度是__ __。in。 ji。9. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時間復(fù)雜度是__ __。for (i=0。i++) for (j=0。j++) for (k=0。k++) s=s+B[i][j][k]。10. 分析下面算法（程序段）給出最大語句頻度 ，該算法的時間復(fù)雜度是__ __。while (sn){ i++。 //s=s+i } 11. 分析下面算法（程序段）給出最大語句頻度 ，該算法的時間復(fù)雜度是__ __。while (i=n) i=i*2。寫出最大語句頻度，該算法的時間復(fù)雜度。 A. 110 B. 108 C. 100 D. 1202. 線性表的順序存儲結(jié)構(gòu)是一種__ _的存儲結(jié)構(gòu)，而鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種__ _的存儲結(jié)構(gòu)。A. 正確 B. 不正確4. 線