【正文】 數(shù)據(jù)結(jié)構(gòu)習(xí)題答案第一節(jié) 概 論一、選擇題1．要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性，這意味著( )。A．?dāng)?shù)據(jù)元素具有同一的特點(diǎn) *B．不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致 C．每個(gè)數(shù)據(jù)元素都一樣 D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等2．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的( (1) )以及它們之間的( (2) )和運(yùn)算的學(xué)科。(1) A．操作對象 B．計(jì)算方法 *C．物理存儲 D．?dāng)?shù)據(jù)映像(2) A．結(jié)構(gòu) *B．關(guān)系 C．運(yùn)算 D．算法3．?dāng)?shù)據(jù)結(jié)構(gòu)被形式地定義為(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。 (1) A．算法 *B．?dāng)?shù)據(jù)元素 C．?dāng)?shù)據(jù)操作 D．邏輯結(jié)構(gòu) (2)A．操作 B．映像 C．存儲 *D．關(guān)系4．在數(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)5．線性表的順序存儲結(jié)構(gòu)是一種( )的存儲結(jié)構(gòu)。*A．隨機(jī)存取 B．順序存取 C．索引存取 D．Hash存取6．算法分析的目的是( )。A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出的關(guān)系 *C．分析算法的效率以求改進(jìn) D．分析算法的易懂性和文檔性7．計(jì)算機(jī)算法指的是( (1) )，它必須具備輸入、輸出和( (2) )等五個(gè)特征。 (1) A．計(jì)算方法 B．排序方法 *C．解決某一問題的有限運(yùn)算序列 D．調(diào)度方法 (2) A．可行性、可移植性和可擴(kuò)充性 *B．可行性、確定性和有窮性 C．確定性，有窮性和穩(wěn)定性 D．易讀性、穩(wěn)定性和安全性8．線性表若采用鏈表存儲結(jié)構(gòu)，要求內(nèi)存中可用存儲單元的地址( )。A．必須是連續(xù)的 B．部分必須是連續(xù)的 C．一定是不連續(xù)的 *D．連續(xù)不連續(xù)都可以9．在以下的敘述中，正確的是( )。A．線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu) *B．二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表 C．棧的操作方式是先進(jìn)先出 D．隊(duì)列的操作方式是先進(jìn)后出10．根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù)據(jù)組織形式，其中解釋錯(cuò)誤的是( )。*A．集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散 B．線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鎖鏈” C．樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹 D．圖狀結(jié)構(gòu)中的各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接11．以下說法正確的是( )。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位 B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位 C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合 *D．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合二、判斷題╳1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位?！?．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合?！?．?dāng)?shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映像分別稱為存儲結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。╳4．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位?！?．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。√6．?dāng)?shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中實(shí)際的存儲形式。╳7．算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。√8．順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。三、填空題1．所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的____邏輯關(guān)系_____。2，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容___數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、對數(shù)據(jù)施加的操作___。3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)包括_____集合結(jié)構(gòu)___、_____線性結(jié)構(gòu)___、____樹型結(jié)構(gòu)_____和__圖狀結(jié)構(gòu)_____四種類型。4．在線性結(jié)構(gòu)中，開始結(jié)點(diǎn)__沒有_前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有__一個(gè)_個(gè)前驅(qū)結(jié)點(diǎn)。5．在樹形結(jié)構(gòu)中，根結(jié)點(diǎn)只有___一個(gè)___，其余每個(gè)結(jié)點(diǎn)有且只有___一個(gè)___前驅(qū)結(jié)點(diǎn)；葉結(jié)點(diǎn)沒有___后繼__結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以有__任意個(gè)__6．在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)可以有___任意個(gè)___。7．算法的五個(gè)重要特性是__可行性___、___確定性___、___有窮性___、___輸入__、___輸出__。8．下列程序段的時(shí)間復(fù)雜度是__O（n）___。 for (i=1；i=n；i++) A[i，i]=0；9．下列程序段的時(shí)間復(fù)雜度是__ O（n2）___。 S=0； for(i=1；i=n；i++) for(j=1；j=n；j++) s=s+B[i,j]； sum=s；10．存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的___物理__實(shí)現(xiàn)。11．從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)看，通常所說的“數(shù)據(jù)”應(yīng)分成三個(gè)不同的層次，即__數(shù)據(jù)__、__數(shù)據(jù)元素_和__數(shù)據(jù)項(xiàng)___。12．根據(jù)需要，數(shù)據(jù)元素又被稱為__結(jié)點(diǎn)__、__記錄__、___元素__或__頂點(diǎn)_。13．通常，存儲結(jié)點(diǎn)之間可以有___順序存儲__、____鏈?zhǔn)酱鎯_、____索引存儲__、___散列存儲_四種關(guān)聯(lián)方式，稱為四種基本存儲方式。14．通常從___確定性___、__可讀性_、___健壯性__、_高效性__等幾方面評價(jià)算法(包括程序)的質(zhì)量。15．一個(gè)算法的時(shí)空性能是指該算法的_時(shí)間復(fù)雜度___和___空間復(fù)雜度_，前者是算法包含的__計(jì)算量__，后者是算法需要的___存儲量__。16．在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是__問題規(guī)模__的函數(shù)。17．常見時(shí)間復(fù)雜度的量級有：常數(shù)階O(__1_)、對數(shù)階O(__log2n___)、線性階O(__n__)、平方階O(_n2_)和指數(shù)階O(__2n_)。通常認(rèn)為，具有指數(shù)階量級的算法是__不可行__的。18．?dāng)?shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的__設(shè)計(jì)__和__實(shí)現(xiàn)__。19．?dāng)?shù)據(jù)對象是性質(zhì)相同的__數(shù)據(jù)元素_的集合。20．抽象數(shù)據(jù)類型是指一個(gè)__數(shù)學(xué)模型__以及定義在該模型上的一組操作。四、應(yīng)用題1．分析下列程序段的時(shí)間復(fù)雜度。 …… i=1； WHILE (i=n) i=i*2； ……答：O(log2n)2．?dāng)⑹鏊惴ǖ亩x及其重要特性。答：算法是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。算法應(yīng)該具有下列特性：可行性、確定性、有窮性、輸入和輸出。3．簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對象。答：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識別和處理的符號的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。4．邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么關(guān)系？答：在數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是密切相關(guān)的，存儲結(jié)構(gòu)不僅將數(shù)據(jù)元素存儲到計(jì)算機(jī)中，而且還要表示各數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)與計(jì)算機(jī)無關(guān)，存儲結(jié)構(gòu)是數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示。5．將數(shù)量級210，n，n2，n3，nlog2n，log2n，2n，n!，(2／3)n，n2／3按增長率進(jìn)行排列。答：(2／3)n，210，log2n，n2／3，n，nlog2n，n2，n3，2n，n!6．設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：D={k1，k2，k3，…，k9}，R={k1，k3，k1，k8，k2，k3，k2，k4，k2，k5，k3，k9，k5，k6，k8，k9，k9，k7，k4，k6}，畫出這個(gè)邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？答：圖略。開始結(jié)點(diǎn)kk2，終端結(jié)點(diǎn)kk7。7．，給出它的邏輯結(jié)構(gòu)，并說出它是什么類型的邏輯結(jié)構(gòu)。答：數(shù)據(jù)邏輯結(jié)構(gòu)為：D={k1，k2，k3，…，k8}，R={k1，k2，k1，k3，k3，k5，k3，k4，k4，k7，k4，k6，k5，k8}，其邏輯結(jié)構(gòu)類型為樹型結(jié)構(gòu)。8．分析下列程序的時(shí)間復(fù)雜度(設(shè)n為正整數(shù))。 (1)int rec(int n) {if(n==1)return(1)； else return(n*rec(n1))； } (2)x=91；y=100； While (y0) if(x10) y； (3)i=1；j=0； while(i+j=n) if(ij)j++； else i++。 (4)x=n；y=0；while(x=(y+1)*(y+1)) y++；答：(1) O(n) (2) O(1) (3) O(n) (4) O(n1/2)9．設(shè)n為正數(shù)。試確定下列各程序段中前面加記號@的語句的頻度： (1)i=1；k=0； while(i=n1) {@k+=10*i； i++； ) (2) k=0； for(i=1；i=n；i++) for(j=i；j=n：j++) @k++；答：(1)n1 (2)n+(n1)+……+1=n(n+1)/2第二節(jié) 線性表一、選擇題1．線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)代表一個(gè)( )。 *A．?dāng)?shù)據(jù)元素 B．?dāng)?shù)據(jù)項(xiàng) C．?dāng)?shù)據(jù) D．?dāng)?shù)據(jù)結(jié)構(gòu)2．線性表L=(a1，a2，…，ai，…，an)，下列說法正確的是( )。 A．每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼 B．線性表中至少要有一個(gè)元素 C．表中諸元素的排列順序必須是由小到大或由大到小的 D．*除第一個(gè)元素和最后一個(gè)元素外其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼3．順序表是線性表的( )。 A．鏈?zhǔn)酱鎯Y(jié)構(gòu) *B．順序存儲結(jié)構(gòu) C．索引存儲結(jié)構(gòu) D．散列存儲結(jié)構(gòu)4．對于順序表，以下說法錯(cuò)誤的是( )。 * A．順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對地址 B．順序表的所有存儲結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列 C．順序表的特點(diǎn)是：邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰 D．順序表的特點(diǎn)是：邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中5．對順序表上的插入、刪除算法的時(shí)間復(fù)雜度分析來說，通常以( )為標(biāo)準(zhǔn)操作。 A．條件判斷 *B．結(jié)點(diǎn)移動 C．算術(shù)表達(dá)式 D．賦值語句6．對于順序表的優(yōu)缺點(diǎn)，以下說法錯(cuò)誤的是( )。 A．無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲空間 B．可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn) *C．插入和刪除操作較方便 D．由于順序表要求占用連續(xù)的空間，存儲分配只能預(yù)先進(jìn)行(靜態(tài)分配)7．在含有n個(gè)結(jié)點(diǎn)的順序存儲的線性表中，在任一結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)所需移動結(jié)點(diǎn)的平均次數(shù)為( )。 A．n *B．n/2 C．(n1)/2 D．(n+1)/28．在含有n個(gè)結(jié)點(diǎn)的順序存儲的線性表中，刪除一個(gè)結(jié)點(diǎn)所需移動結(jié)點(diǎn)的平均次數(shù)為( )。 A．n B．n/2 *C．(n1)/2 D．(n+1)/29．帶頭結(jié)點(diǎn)的單鏈表為空的條件是( )。A．head=NULL *B．headnext=NULL C．headnext=head D．head!=NULL10．非空單循環(huán)鏈表head的尾結(jié)點(diǎn)*p滿足( )。 A．pnext=NULL B．p=NULL *C．pnext=head D．p=head11．在雙循環(huán)鏈表的*p結(jié)點(diǎn)之后插入*s結(jié)點(diǎn)的操作是( )。 A．pnext=s；sprior=p；pnextprior=s；snext=pnext； B．pnext=s；pnextprior=s；sprior=p：snext=pnext； C．sprior=p；snext=pnext；pnext=s；pnextprior=s； *D．sprior=p；snext=pnext；pnextpror=s；pnext=s；12. 在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和*p之間插入結(jié)點(diǎn)*s，則執(zhí)行( )。 A．snext=pnext；pnext=s； B．pnext=snext；snext=p； *C．qnext=s。 snext=p； D．pnext=s。 snext=q；13. 在一個(gè)單鏈表中，若*p結(jié)點(diǎn)不是最后結(jié)點(diǎn)。在*p之后插入結(jié)點(diǎn)*s，則執(zhí)行( )。 A．snext=p；pnext=s。 *B．snext=pnext；pnext=s； C．snext=pnext； p=s； D．pnext=s； snext=p。14. 若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)元素，則采用( )存儲方式最節(jié)省時(shí)間。 *A．順序表 B. 單鏈表 C．雙鏈表 D．單循環(huán)鏈表15．設(shè)rear是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針，則刪除表頭結(jié)點(diǎn)的操作可表示為( )。 A．p=rear；rear=rearnext； free(p) B．rear=rearnext；free(rear)； C．rear=rearnextnext； free(rear)； *D．p=rearn