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