【正文】 習(xí)題1一、單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是指（A ）。 2. 數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為（C ）。 3. 樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ D ）。 4. 設(shè)語句x++的時(shí)間是單位時(shí)間，則以下語句的時(shí)間復(fù)雜度為（ B ）。for(i=1。 i=n。 i++)for(j=i。 j=n。 j++)x++。(1) () (n) ()5. 算法分析的目的是（C），算法分析的兩個(gè)主要方面是（A）。（1） （2） 6. 計(jì)算機(jī)算法指的是（C），它具備輸入，輸出和（B）等五個(gè)特性。（1） （2） ，可移植性和可擴(kuò)充性 ，確定性和有窮性，有窮性和穩(wěn)定性 ，穩(wěn)定性和安全性7. 數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲方式，在存儲空間使用的靈活性上，鏈?zhǔn)酱鎯Ρ软樞虼鎯σ?B ）。 8. 數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程出現(xiàn)是在（ D ）年。 9. 數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點(diǎn)（ B ）。 ，后半句錯(cuò) ，后半句對10. 計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（ B ）。 二、填空題 1. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是__線性結(jié)構(gòu) 和___非線性結(jié)構(gòu)______________。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是___集合_____________、_____線性_____________、_____樹_____________和______圖____________。3. 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是__________________的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是__________________的。4. 一個(gè)算法的效率可分為__________________效率和__________________效率。5. 在樹型結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有__________________結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且只有__________________個(gè)前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有__________________結(jié)點(diǎn)；其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以__________________。6. 在圖型結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以__________________。7. 線性結(jié)構(gòu)中元素之間存在__________________關(guān)系；樹型結(jié)構(gòu)中元素之間存在__________________關(guān)系；圖型結(jié)構(gòu)中元素之間存在__________________關(guān)系。8. 下面程序段的時(shí)間復(fù)雜度是__________________。for(i=0。in。i++)for(j=0。jn。j++)A[i][j]=0。9. 下面程序段的時(shí)間復(fù)雜度是__________________。i=s=0。while(sn){ i++。 s+=i。}10. 下面程序段的時(shí)間復(fù)雜度是__________________。s=0。for(i=0。in。i++)for(j=0。jn。j++)s+=B[i][j]。sum=s。11. 下面程序段的時(shí)間復(fù)雜度是__________________。i=1。while(i=n)i=i*3。12. 衡量算法正確性的標(biāo)準(zhǔn)通常是____________________________________。13. 算法時(shí)間復(fù)雜度的分析通常有兩種方法，即___________和___________的方法，通常我們對算法求時(shí)間復(fù)雜度時(shí)，采用后一種方法。三、求下列程序段的時(shí)間復(fù)雜度。1. x=0。for(i=1。in。i++)for(j=i+1。j=n。j++)x++。2. x=0。for(i=1。in。i++)for(j=1。j=ni。j++) x++。3. int i,j,k。for(i=0。in。i++)for(j=0。j=n。j++) { c[i][j]=0。for(k=0。kn。k++) c[i][j]=a[i][k]*b[k][j]}4. i=n1。while((i=0)amp。amp。A[i]!=k))j。return (i)。5. fact(n){ if(n=1) return (1)。 else return (n*fact(n1))。}習(xí)題1參考答案一、單項(xiàng)選擇題1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B二、填空題1. 線性結(jié)構(gòu)，非線性結(jié)構(gòu)2. 集合，線性，樹，圖3. 一對一，一對多或多對多4. 時(shí)間，空間5. 前趨，一，后繼，多6. 有多個(gè)7. 一對一，一對多，多對多8. O()9. O()10. O()11. O(logn)12. 程序?qū)τ诰脑O(shè)計(jì)的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。13. 事后統(tǒng)計(jì)，事前估計(jì)三、算法設(shè)計(jì)題 1. O() 2. O() 3. O(n) 4. O(n) 5. O(n)習(xí)題2一、單項(xiàng)選擇題 1. 線性表是________。A．一個(gè)有限序列，可以為空 B．一個(gè)有限序列，不可以為空C．一個(gè)無限序列，可以為空 D．一個(gè)無限序列，不可以為空2. 在一個(gè)長度為n的順序表中刪除第i個(gè)元素(0=i=n)時(shí)，需向前移動 個(gè)元素。A．ni B．ni+l C．ni1 D．i3. 線性表采用鏈?zhǔn)酱鎯r(shí)，其地址________。A．必須是連續(xù)的 B．一定是不連續(xù)的C．部分地址必須是連續(xù)的 D．連續(xù)與否均可以 4. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較________個(gè)元素結(jié)點(diǎn)。A．n/2 B．n C．（n+1）/2 D．（n1）/2 5. 在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是____。A． pnext=s。 sprior=p。 pnextprior=s。 snext=pnext。B． sprior=p。 snext=pnext。 pnext=s。 pnextprior=s。C． pnext=s。 pnextprior=s。 sprior=p。 snext=pnext。D． sprior=p。 snext=pnext。 pnextprior=s。 pnext=s。 6. 設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要刪除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為________。A．pnext=pnextnext。 B．p=pnext。C．p=pnextnext。 D．pnext=p。 7. 在一個(gè)長度為n的順序表中向第i個(gè)元素(0 in+l )之前插入一個(gè)新元素時(shí)，需向后移動______個(gè)元素。A．ni B．ni+l C．ni1 D．i8. 在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行A．snext=pnext。 pnext=sB．qnext=s。 snext=pC．pnext=snext。 snext=pD．pnext=s。 snext=q9. 以下關(guān)于線性表的說法不正確的是______。 A．線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B．線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C．線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。D．存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼。10. 線性表的順序存儲結(jié)構(gòu)是一種_______的存儲結(jié)構(gòu)。 A．隨機(jī)存取 B．順序存取 C．索引存取 D．散列存取11. 在順序表中，只要知道_______，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲地址。A．基地址 B．結(jié)點(diǎn)大小 C．向量大小 D．基地址和結(jié)點(diǎn)大小12. 在等概率情況下，順序表的插入操作要移動______結(jié)點(diǎn)。 A．全部 B．一半 C．三分之一 D．四分之一13. 在______運(yùn)算中，使用順序表比鏈表好。 A．插入 B．刪除 C．根據(jù)序號查找 D．根據(jù)元素值查找14. 在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是_______。 A．O(1) B．O(n) C．O(n2) D．O(log2n)15. 設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳, B, C, D, E,下列是不可能的出棧序列__________。A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A 16. 在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為______。A．top不變 B．top=0 C．top D．top++17. 向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行______。A．hsnext=s。 B．snext=hs。 hs=s。C．snext=hsnext。hsnext=s。 D．snext=hs。 hs=hsnext。 18. 在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為________。A．rear％n= = front B．（front+l）％n= = rearC．rear％n 1= = front D．(rear+l)％n= = front 19. 在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為________。A．rear％n= = front B．front+l= rearC．rear= = front D．(rear+l)％n= front20. 在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為________。A．front=frontnext 　 B．rear=rearnextC．rear=frontnext 　D．front=rearnext二、填空題 1. 線性表是一種典型的_________結(jié)構(gòu)。2. 在一個(gè)長度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移____個(gè)元素。3. 順序表中邏輯上相鄰的元素的物理位置________。4. 要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需_______一個(gè)位置，移動過程是從_______向_______依次移動每一個(gè)元素。5. 在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過_______決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過_______決定的。6. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_______結(jié)點(diǎn)，另一個(gè)指向_______結(jié)點(diǎn)。7. 當(dāng)對一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用_______存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用_______存儲結(jié)構(gòu)為宜。8. 順序表中邏輯上相鄰的元素，物理位置_______相鄰，單鏈表中邏輯上相鄰的元素，物理位置_______相鄰。9. 線性表、棧和隊(duì)列都是_______結(jié)構(gòu)，可以在線性表的______位置插入和刪除元素；對于棧只能在_______位置插入和刪除元素；對于隊(duì)列只能在_______位置插入元素和在_______位置刪除元素。10. 根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為_________和_______；而根據(jù)指針的聯(lián)接方式，鏈表又可分為________和_________。11. 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是________。12. 對于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為______，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_______。 13. 對于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_______，作退棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_______，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明棧的可用最大容量為_______。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的_______分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_______時(shí)才產(chǎn)生上溢。14. 設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push,