數(shù)據(jù)結(jié)構(gòu)與算法 習(xí)題及解答 機(jī)械自考版 -第1-4章 緒論-數(shù)組、廣義表和串

第一章緒論一、單項(xiàng)選擇題1．在數(shù)據(jù)結(jié)構(gòu)與算法中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為_(kāi)_______。A．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) B．線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)C．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) D．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)答案：B。從邏輯角度看，基本的數(shù)據(jù)結(jié)構(gòu)包括4類(lèi)，分別是集合、線(xiàn)性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)。其中，樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)屬于非線(xiàn)性結(jié)構(gòu)。集合也可以使用線(xiàn)性結(jié)構(gòu)表示。2．?dāng)?shù)據(jù)元素可以細(xì)分為_(kāi)_______。A．?dāng)?shù)據(jù)項(xiàng) B．字符 C．二進(jìn)制位 D．?dāng)?shù)據(jù)記錄答案：A。根據(jù)定義，數(shù)據(jù)元素可以細(xì)分為數(shù)據(jù)項(xiàng)。字符和二進(jìn)制位都是表示數(shù)據(jù)的具體單位（選項(xiàng)B和C都是錯(cuò)誤的）。數(shù)據(jù)元素有時(shí)稱(chēng)為記錄（選項(xiàng)D錯(cuò)誤）。3．如果說(shuō)線(xiàn)性結(jié)構(gòu)中元素之間是一對(duì)一的關(guān)系，則樹(shù)結(jié)構(gòu)中元素之間的關(guān)系是________。A．一對(duì)一的 B．一對(duì)多的 C．多對(duì)多的 D．不確定的答案：B。線(xiàn)性結(jié)構(gòu)中，除首元素和尾元素外，每個(gè)元素有唯一的直接前驅(qū)和唯一的直接后繼，所以對(duì)于每個(gè)元素而言，它對(duì)應(yīng)唯一的直接后繼，形成一對(duì)一的關(guān)系。在樹(shù)結(jié)構(gòu)中，每個(gè)元素僅有唯一的直接前驅(qū)，但可以有多個(gè)直接后繼，所以是一對(duì)多的關(guān)系。當(dāng)然，樹(shù)中的根（最前面的元素）和葉結(jié)點(diǎn)（后面的元素）除外。圖結(jié)構(gòu)中是多對(duì)多的關(guān)系，每個(gè)元素可以有多個(gè)直接前驅(qū)，也可以有多個(gè)直接后繼。4．在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間均為一個(gè)對(duì)一個(gè)的關(guān)系，稱(chēng)為_(kāi)_______。A．線(xiàn)性結(jié)構(gòu) B．樹(shù)結(jié)構(gòu) C．圖結(jié)構(gòu) D．集合結(jié)構(gòu)答案：A。基本概念。具體說(shuō)明請(qǐng)參見(jiàn)第一章第3題的答案。5．下列選項(xiàng)中，不屬于數(shù)據(jù)結(jié)構(gòu)常用存儲(chǔ)方式的是________。A．順序存儲(chǔ)方式 B．鏈?zhǔn)酱鎯?chǔ)方式 C．分布存儲(chǔ)方式 D．散列存儲(chǔ)方式答案：C。數(shù)據(jù)結(jié)構(gòu)與算法課程中沒(méi)有討論分布存儲(chǔ)方式，除了選項(xiàng)中給定的A、B和D以外，還討論了索引存儲(chǔ)方式。這是數(shù)據(jù)結(jié)構(gòu)中常用的4種存儲(chǔ)方式。6．算法分析要評(píng)估的兩個(gè)主要方面是________。A．正確性和簡(jiǎn)明性 B．時(shí)間復(fù)雜度和空間復(fù)雜度C．可讀性和可維護(hù)性 D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性答案：B。算法的正確性是必須的，簡(jiǎn)明性、可讀性、可維護(hù)性等都不是算法要評(píng)估的內(nèi)容（選項(xiàng)A和選項(xiàng)C均錯(cuò)誤），它們都屬于算法應(yīng)具備的眾多特性中的內(nèi)容。數(shù)據(jù)復(fù)雜性是數(shù)據(jù)本身的狀態(tài)，也不是算法要評(píng)估的，程序復(fù)雜性說(shuō)得不明確（選項(xiàng)D錯(cuò)誤）。算法要評(píng)估的是時(shí)間復(fù)雜度和空間復(fù)雜度。7．下列選項(xiàng)中，定義抽象數(shù)據(jù)類(lèi)型時(shí)不需要做的事情是________。A．給出類(lèi)型的名字 B．定義類(lèi)型上的操作C．實(shí)現(xiàn)類(lèi)型上的操作 D．用某種語(yǔ)言描述抽象數(shù)據(jù)類(lèi)型答案：C。定義抽象數(shù)據(jù)類(lèi)型時(shí)，需要給類(lèi)型命名（選項(xiàng)A），需要指明相關(guān)的操作有哪些（選項(xiàng)B），需要使用程序語(yǔ)言或是自然語(yǔ)言描述抽象數(shù)據(jù)類(lèi)型（選項(xiàng)D）。在確定了存儲(chǔ)結(jié)構(gòu)之后才能具體實(shí)現(xiàn)操作過(guò)程，所以在定義抽象數(shù)據(jù)類(lèi)型階段，不涉及這些操作的實(shí)現(xiàn)。A．O(n) B．O(n2) C．O(2n) D．O(logn)答案：C基本概念。一般而言，算法的效率用算法時(shí)間復(fù)雜度進(jìn)行衡量，算法效率從高到低依次是：常數(shù)階O(1)，對(duì)數(shù)階O(logn)，線(xiàn)性階O(n)，線(xiàn)性對(duì)數(shù)階O(nlogn)，多項(xiàng)式階O(n2)，指數(shù)階O(2n)。9．________。x=2;while(x<n/2) x=2*x;A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)答案：A。n是輸入規(guī)模。x從2開(kāi)始，每次倍增，達(dá)到或超過(guò)n/2時(shí)倍增的次數(shù)與log2n的大小相當(dāng)。10．設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下列程序片段的時(shí)間復(fù)雜度是________。x=1;while(n>=(x+1)*(x+1)) x=x+1;A．O(n1/2) B．O(log2n) C．O(n) D．O(nlog2n)答案：A。11．設(shè)計(jì)求斐波那契數(shù)列前n項(xiàng)的算法時(shí)，適宜使用的算法策略是________。A．分治法 B．遞推法 C．遞歸法 D．窮舉法答案：B。參見(jiàn)本章算法設(shè)計(jì)題2的解答。二、填空題1．在數(shù)據(jù)結(jié)構(gòu)與算法課程中，將所有能輸入計(jì)算機(jī)并被計(jì)算機(jī)程序處理的符號(hào)集合稱(chēng)為_(kāi)_________。答案：數(shù)據(jù)?；靖拍?。2．構(gòu)成數(shù)據(jù)的基本單位是__________。答案：數(shù)據(jù)元素。基本概念。在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)元素是構(gòu)成數(shù)據(jù)的基本單位，同時(shí)，也是作為一個(gè)整體進(jìn)行研究。3．?dāng)?shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式稱(chēng)為數(shù)據(jù)的__________。答案：存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，物理結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示及存儲(chǔ)方式。數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)關(guān)系是無(wú)關(guān)的。4．?dāng)?shù)據(jù)結(jié)構(gòu)包括4類(lèi)，分別是集合、線(xiàn)性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)和__________。答案：圖結(jié)構(gòu)。基本概念。5．構(gòu)成索引表的基本內(nèi)容是__________。答案：索引項(xiàng)。索引表由索引項(xiàng)組成，索引項(xiàng)指示數(shù)據(jù)元素所在的物理位置。通過(guò)索引項(xiàng)，可以加快數(shù)據(jù)元素的查找速度。6．一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束，這個(gè)特性是算法的__________。答案：有窮性?；靖拍?。算法必須滿(mǎn)足5個(gè)重要特性：有0或多個(gè)輸入值、有1或多個(gè)輸出值、有窮性、確定性和可行性。7．設(shè)A={1,3,-4,5,-6,4,6,-3,-2,6}，調(diào)用MaxSeq(A,n,C);后，C[1]的值是________。答案：9。函數(shù)MaxSeq是求數(shù)組A的最大子數(shù)組，結(jié)果是{4,6,-3,-2,6}，C[1]中保存的這個(gè)子數(shù)組最后一個(gè)元素在A(yíng)中的下標(biāo)，得到9。三、解答題1．舉例說(shuō)明計(jì)算機(jī)能處理哪些數(shù)據(jù)？【參考答案】計(jì)算機(jī)能處理的數(shù)據(jù)多種多樣，大到可以是一幅地圖、一本書(shū)、一部電影，小到可以是一個(gè)字符，甚至是計(jì)算機(jī)中的一位?？梢允菙?shù)值型的數(shù)據(jù)，也可以是非數(shù)值型的數(shù)據(jù)。既可以是簡(jiǎn)單結(jié)構(gòu)的，也可以是復(fù)雜結(jié)構(gòu)的。2．線(xiàn)性結(jié)構(gòu)中，如何理解元素之間是一對(duì)一的關(guān)系？【參考答案】線(xiàn)性結(jié)構(gòu)中，除表頭元素和表尾元素外，每個(gè)元素有唯一的直接前驅(qū)和唯一的直接后繼。所以對(duì)于每個(gè)元素而言，當(dāng)有直接后繼時(shí)，它與其直接后繼形成一對(duì)一的關(guān)系。3．定義代表交通工具的抽象數(shù)據(jù)類(lèi)型vehicle，添加必要的數(shù)據(jù)和操作。【參考答案】對(duì)于vehicle，可以定義表示其基本屬性的數(shù)據(jù)，包括品牌brand、顏色color、價(jià)格price等。相應(yīng)的操作可以是設(shè)置最大速度setSpeed(intspeed)、設(shè)置自重setdeadweight(intweight)等。ADTvehicle{ //交通工具的抽象數(shù)據(jù)類(lèi)型定義 數(shù)據(jù)部分： brand： //品牌，字符串 color： //顏色，字符串 price： //價(jià)格，實(shí)型 speed： //最大速度，實(shí)型 deadweight： //自重，實(shí)型，單位噸 操作部分： setSpeed(speed)： //設(shè)置最大速度 輸入：speed 輸出：是否設(shè)置成功 前提條件：設(shè)置的speed值不能超出限制 setdeadweight(weight)： //設(shè)置自重 輸入：weight 輸出：是否設(shè)置成功 前提條件：設(shè)置的weight值不能超出限制}4．定義表示復(fù)數(shù)的抽象數(shù)據(jù)類(lèi)型?！緟⒖即鸢浮繌?fù)數(shù)由實(shí)部和虛部表示，實(shí)部和虛部都是實(shí)型值。相應(yīng)的操作有算術(shù)操作。ADTcomplex{ //復(fù)數(shù)的抽象數(shù)據(jù)類(lèi)型定義 數(shù)據(jù)部分： real： //實(shí)部，實(shí)型 imaginary： //虛部，實(shí)型 操作部分： add(complex1,complex2)： //加法 輸入：兩個(gè)復(fù)數(shù) 輸出：它們的和 前提條件：兩個(gè)復(fù)數(shù)正確 sub(complex1,complex2)： //減法 輸入：兩個(gè)復(fù)數(shù) 輸出：它們的差 前提條件：兩個(gè)復(fù)數(shù)正確 multiplication(complex1,complex2)： //乘法 輸入：兩個(gè)復(fù)數(shù) 輸出：它們的積 前提條件：兩個(gè)復(fù)數(shù)正確 division(complex1,complex2)： //除法 輸入：兩個(gè)復(fù)數(shù) 輸出：它們的商 前提條件：兩個(gè)復(fù)數(shù)正確}5．為什么不使用算法的絕對(duì)運(yùn)行時(shí)間來(lái)衡量算法的時(shí)間效率？【參考答案】同一個(gè)算法處理不同數(shù)量的數(shù)據(jù)時(shí)，所花費(fèi)的絕對(duì)運(yùn)行時(shí)間可能不同。同一個(gè)算法處理相同數(shù)量的數(shù)據(jù)時(shí)，在不同配置的電腦上的絕對(duì)運(yùn)行時(shí)間也可能不同。所以，使用算法的絕對(duì)運(yùn)行時(shí)間不能有效衡量算法的時(shí)間效率。6．評(píng)估算法的空間效率時(shí)，需要考慮占用的哪些存儲(chǔ)空間？【參考答案】算法運(yùn)行過(guò)程中，臨時(shí)占用的空間大小是要考慮的存儲(chǔ)空間。算法代碼占用的空間、算法中初始數(shù)據(jù)占用的存儲(chǔ)空間不考慮在內(nèi)。四、算法設(shè)計(jì)題1．試設(shè)計(jì)一個(gè)算法，使用最少的比較次數(shù)找出三個(gè)不同整數(shù)a,b,c的中值?！緟⒖即鸢浮縤ntmiddle(inta,intb,intc){ if(a>b){ if(b>c)returnb; //a>b>c elseif(a>c)returnc; //a>c>b elsereturna; //c>b>a } else{ if(a>c)returna; //b>a>c elseif(b>c)returnc; //b>c>a elsereturnb; //c>b>a }}2．試設(shè)計(jì)一個(gè)算法，對(duì)于給定的正整數(shù)n，列出斐波那契數(shù)列的前n項(xiàng)，要求空間復(fù)雜度為O(1)?！緟⒖即鸢浮快巢瞧鯏?shù)列的前兩項(xiàng)均為1，從第三項(xiàng)開(kāi)始，每一項(xiàng)都是其前兩項(xiàng)之和。使用整型變量f1、f2和f3表示數(shù)列中相鄰三項(xiàng)的值，初始時(shí)，f1和f2的值均為1。然后計(jì)算新的項(xiàng)f3=f1+f2，計(jì)算后用f2的值更新f1，用f3的值更新f2。voidfibonacci(intn){ intf1=1,f2=1,f3,i; if(n<=0){ printf("n值錯(cuò)誤\n"); return; } elseif(n==1){ printf("1\n"); return; } else{ printf("11"); for(i=3;i<=n;i++){ f3=f1+f2; printf("%d",f3); f1=f2; f2=f3; } printf("\n"); }}第二章線(xiàn)性表一、單項(xiàng)選擇題1．下列選項(xiàng)中，不屬于鏈表特點(diǎn)的是________。A．插入、刪除時(shí)不需要移動(dòng)元素 B．可隨機(jī)訪(fǎng)問(wèn)任一元素C．不必事先估計(jì)存儲(chǔ)空間 D．所需空間與元素個(gè)數(shù)成正比答案：B。鏈表中的元素可以不必保存在相鄰的地址空間中，所以當(dāng)鏈表中的元素個(gè)數(shù)有變化時(shí)，其他的元素不必像順序表那樣進(jìn)行移動(dòng)（選項(xiàng)A）。而且鏈表占用的空間隨需分配，隨用隨分配，不必提前預(yù)估數(shù)量（選項(xiàng)C），表中有多少個(gè)元素就分配多少個(gè)表結(jié)點(diǎn)（選項(xiàng)D）。但要訪(fǎng)問(wèn)鏈表中的元素時(shí)，只能從表頭開(kāi)始，沿指針的指示逐個(gè)結(jié)點(diǎn)地查找下去，所以不能像在數(shù)組中那樣通過(guò)下標(biāo)定位到所需的地址，即不能實(shí)現(xiàn)隨機(jī)訪(fǎng)問(wèn)。2．下列關(guān)于線(xiàn)性表的敘述中，錯(cuò)誤的是________。A．線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)方式，便于進(jìn)行插入和刪除操作B．線(xiàn)性表采用順序存儲(chǔ)方式，便于進(jìn)行插入和刪除操作C．線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)方式，不必占用一片連續(xù)的存儲(chǔ)單元D．線(xiàn)性表采用順序存儲(chǔ)方式，必須占用一片連續(xù)的存儲(chǔ)單元答案：B。線(xiàn)性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，各元素要連續(xù)存放（選項(xiàng)D正確），當(dāng)有插入和刪除操作時(shí)，通常會(huì)導(dǎo)致其他元素的移動(dòng)（選項(xiàng)B錯(cuò)誤）。當(dāng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，因?yàn)楦鹘Y(jié)點(diǎn)的地址并不要求是相鄰的（選項(xiàng)C正確），所以插入和刪除操作不會(huì)引起其他元素的移動(dòng)（選項(xiàng)A正確）。3．若一個(gè)線(xiàn)性表分別采用下列存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)中，則讀取一個(gè)指定位置（序號(hào)）的元素所花費(fèi)時(shí)間最少的是________。A．順序表 B．單向鏈表 C．雙向鏈表 D．循環(huán)鏈表答案：A。采用順序存儲(chǔ)結(jié)構(gòu)保存線(xiàn)性表時(shí)，要讀取一個(gè)指定位置（序號(hào)）的元素可以直接通過(guò)下標(biāo)訪(fǎng)問(wèn)，下標(biāo)與元素在內(nèi)存中存儲(chǔ)地址是一個(gè)簡(jiǎn)單的計(jì)算公式，因?yàn)榭梢設(shè)(1)訪(fǎng)問(wèn)線(xiàn)性表任一位置的元素，是花費(fèi)時(shí)間最少的（選項(xiàng)A正確）。對(duì)于采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)保存的線(xiàn)性表，無(wú)論是單向鏈表（選項(xiàng)B）、雙向鏈表（選項(xiàng)C），還是循環(huán)鏈表（選項(xiàng)D），要讀取指定位置（序號(hào)）的元素均需要從鏈表首結(jié)點(diǎn)開(kāi)始進(jìn)行計(jì)數(shù)，這樣，操作的時(shí)間復(fù)雜度均為O(n)。4．下列關(guān)于線(xiàn)性表的敘述中，錯(cuò)誤的是________。A．除第一個(gè)元素外均有唯一的前驅(qū)B．除最后一個(gè)元素外均有唯一的后繼C．元素的個(gè)數(shù)可以是0，此時(shí)表為空表D．元素的個(gè)數(shù)若為無(wú)窮，則表為無(wú)窮表答案：D?；靖拍睢Ｔ跀?shù)據(jù)結(jié)構(gòu)中，線(xiàn)性表是一個(gè)有限元素的序列。5．下列關(guān)于線(xiàn)性表L的敘述中，正確的是________。A．L是由n個(gè)相同元素組成的離散數(shù)據(jù)序列B．L中任意一個(gè)元素有且僅有唯一直接前驅(qū)C．可以在L中進(jìn)行取元素、查找或排序等操作D．不能在L的任意位置插入或刪除一個(gè)元素答案：C。基本概念。線(xiàn)性表是由n個(gè)相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)元素組成的有限序列（A錯(cuò)誤）；L中除第一個(gè)元素之外，其他元素有且僅有唯一的直接前驅(qū)，第一個(gè)元素沒(méi)有直接前驅(qū)（B錯(cuò)誤）；在線(xiàn)性表中可以進(jìn)行插入、刪除、取元素值、查找或排序等操作，所以C是正確的，D是錯(cuò)誤的。6．若線(xiàn)性表L最常用的操作是訪(fǎng)問(wèn)任一位置的元素和在最后進(jìn)行插入和刪除運(yùn)算，為使操作的時(shí)間復(fù)雜度好，則下列選項(xiàng)中，為L(zhǎng)選擇的存儲(chǔ)結(jié)構(gòu)為_(kāi)_______。A．順序表 B．雙向鏈表C．帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表 D．單循環(huán)鏈表答案：A。采用順序存儲(chǔ)結(jié)構(gòu)保存線(xiàn)性表時(shí)，能以O(shè)(1)訪(fǎng)問(wèn)線(xiàn)性表任一位置的元素。要在線(xiàn)性表中間位置進(jìn)行插入和刪除時(shí)，會(huì)引發(fā)部分元素在數(shù)組中的移動(dòng)，但如果僅在最后位置進(jìn)行插入和刪除，則避免了元素的移動(dòng)，操作也能達(dá)到O(1)。選項(xiàng)B、C和D都是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，雖然它們進(jìn)行插入和刪除操作時(shí)能達(dá)到O(1)，但訪(fǎng)問(wèn)任一位置元素時(shí)，平均情況下，僅能達(dá)到O(n)。綜合來(lái)看，選擇順序表更合適。7．線(xiàn)性表L中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，為使操作的時(shí)間復(fù)雜度好，則下列選項(xiàng)中，為L(zhǎng)選擇的存儲(chǔ)結(jié)構(gòu)為_(kāi)_______。A．單鏈表 B．僅有頭指針的單循環(huán)鏈表C．雙向鏈表 D．僅有尾指針的單循環(huán)鏈表答案：D。4個(gè)選項(xiàng)給出的都是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。根據(jù)題意，操作的位置是表尾和表頭，所以要選擇能快速訪(fǎng)問(wèn)這兩個(gè)位置的結(jié)構(gòu)。單鏈表中僅有表頭指針，能快速訪(fǎng)問(wèn)表頭，但不能快速訪(fǎng)問(wèn)表尾。單循環(huán)鏈表中，通過(guò)頭指針能快速訪(fǎng)問(wèn)表頭位置，訪(fǎng)問(wèn)表尾也是不方便的。雙向鏈表也是類(lèi)似的。選項(xiàng)D給出的鏈表，通過(guò)尾指針可以快速訪(fǎng)問(wèn)到表尾結(jié)點(diǎn)，實(shí)現(xiàn)在其之后的插入，也能通過(guò)表尾結(jié)點(diǎn)的next指針快速找到表頭結(jié)點(diǎn)，實(shí)現(xiàn)刪除操作。所以，僅有尾指針的單循環(huán)鏈表是最合適的結(jié)構(gòu)。8．為了提供全程對(duì)號(hào)的高速鐵路售票系統(tǒng)，保證每一位旅客從上車(chē)到下車(chē)期間都有獨(dú)立座位，短途乘客下車(chē)后該座位可以銷(xiāo)售給其他乘客，鐵路公司設(shè)計(jì)了基于內(nèi)存的系統(tǒng)，系統(tǒng)中需要描述座位信息和每個(gè)座位的售票情況。保存座位信息和每個(gè)座位售票情況的數(shù)據(jù)結(jié)構(gòu)分別是________。A．?dāng)?shù)組，數(shù)組 B．?dāng)?shù)組，鏈表C．鏈表，數(shù)組 D．鏈表，鏈表答案：B。高鐵上，每節(jié)車(chē)廂都有自己固定的座位數(shù)，不變化，所以可以使用數(shù)組來(lái)描述座位。但每個(gè)座位的售票情況是隨時(shí)變化的，應(yīng)當(dāng)使用動(dòng)態(tài)的結(jié)構(gòu)來(lái)描述，故選用鏈表來(lái)描述。9．若長(zhǎng)度為n的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，則在其第i(0≤i≤n)個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為_(kāi)_______。A．O(1) B．O(i) C．O(n) D．O(n2)答案：C。順序表中，插入操作會(huì)導(dǎo)致從插入位置至表尾的全部元素依次后移一個(gè)位置。平均情況下，要移動(dòng)一半的元素，所以時(shí)間復(fù)雜度是O(n)。10．對(duì)于含n個(gè)元素采用順序存儲(chǔ)的線(xiàn)性表，訪(fǎng)問(wèn)位置i（0≤i≤n-1）處的元素和在位置i（0≤i≤n）插入元素的時(shí)間復(fù)雜度分別為_(kāi)_______。A．O(n)和O(n) B．O(n)和O(1) C．O(1)和O(n) D．O(1)和O(1)答案：C。順序表中，訪(fǎng)問(wèn)結(jié)點(diǎn)時(shí)可以根據(jù)下標(biāo)直接計(jì)算地址，所以時(shí)間復(fù)雜度是O(1)。而插入結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(n)。11．線(xiàn)性表(a0,a1,…,an-1)以鏈接方式存儲(chǔ)時(shí)，訪(fǎng)問(wèn)位置i的元素的時(shí)間復(fù)雜度為_(kāi)_______。A．O(1) B．O(i-1) C．O(i) D．O(n)答案：D。鏈?zhǔn)酱鎯?chǔ)線(xiàn)性表時(shí)，如果要訪(fǎng)問(wèn)表中的結(jié)點(diǎn)，通常會(huì)從表頭開(kāi)始，逐個(gè)結(jié)點(diǎn)依次遍歷過(guò)來(lái)，平均而言，要訪(fǎng)問(wèn)表中一半的元素。12．在帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表head中，指向尾結(jié)點(diǎn)的指針p滿(mǎn)足的條件是________。A．p==NULL B．p==headC．p->next==head D．p->next==NULL答案：C。若單循環(huán)鏈表head非空，則必有尾結(jié)點(diǎn)，尾結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)，也就是說(shuō)，p指向結(jié)點(diǎn)的next值應(yīng)該等于head的值（選項(xiàng)C正確）。若指針p的值是NULL（選項(xiàng)A），則表示指針p沒(méi)有指向任何結(jié)點(diǎn)。若p==head（選項(xiàng)B），則表示p與頭指針指向相同，而頭指針指向的是頭結(jié)點(diǎn)（虛擬結(jié)點(diǎn)），在非空鏈表中，尾結(jié)點(diǎn)不是頭結(jié)點(diǎn)。如果不是循環(huán)鏈表，則尾結(jié)點(diǎn)的next值為NULL（選項(xiàng)D）。13．帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是________。A．head==NULL B．head!=NULLC．head->next==head D．head->next==NULL答案：D。帶頭結(jié)點(diǎn)的空單鏈表是僅含有頭結(jié)點(diǎn)（虛擬結(jié)點(diǎn)）的鏈表，頭結(jié)點(diǎn)的next值為NULL，即它沒(méi)有后繼結(jié)點(diǎn)。因?yàn)楹蓄^結(jié)點(diǎn)，故頭指針head在任何時(shí)刻都不能為空（選項(xiàng)A錯(cuò)誤）。對(duì)于空表與非空表，head!=NULL（選項(xiàng)B）都是成立的，所以用這個(gè)條件不能判定表是否為空。head->next==head表明頭結(jié)點(diǎn)的next指針又指向頭結(jié)點(diǎn)，這是空循環(huán)鏈表的狀態(tài)。head->next==NULL表示的是頭指針指向的結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)，這正是空鏈表要滿(mǎn)足的條件。14．在雙向循環(huán)鏈表中，在指針p所指結(jié)點(diǎn)之后插入指針s所指結(jié)點(diǎn)的操作是________。A．p->next=s;s->prev=p;p->next->prev=s;s->next=p->next;B．p->next=s;p->next->prev=s;s->prev=p;s->next=p->next;C．s->prev=p;s->next=p->next;p->next=s;p->next->prev=s;D．s->prev=p;s->next=p->next;p->next->prev=s;p->next=s;答案：D。解答這樣的題目時(shí)，畫(huà)圖是個(gè)不錯(cuò)的方法。比如，執(zhí)行了選項(xiàng)A中前兩個(gè)語(yǔ)句（p->next=s;s->prev=p;）后，得到的鏈表狀態(tài)如圖2-1所示。pp…AB…Xs圖2-1對(duì)應(yīng)于選項(xiàng)A的單鏈表其中，第3個(gè)語(yǔ)句“p->next->prev=s;”是將結(jié)點(diǎn)X的prev指針又指回自己，這顯然是錯(cuò)誤的。其他的3個(gè)選項(xiàng)，可以畫(huà)出類(lèi)似的鏈表狀態(tài)。15．在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行的操作是________。A．s->next=p->next;p->next=s; B．p->next=s->next;s->next=p;C．q->next=s;s->next=p; D．p->next=s;s->next=q;答案：C。以選項(xiàng)A為例，執(zhí)行了其中的兩條語(yǔ)句后，單鏈表的狀態(tài)如圖2-2所示。這表明，結(jié)點(diǎn)s插入在了結(jié)點(diǎn)p的后面，而不是插入在q和p之間。ppqs………BC…X圖2-2對(duì)應(yīng)于選項(xiàng)A的單鏈表16．在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是終端結(jié)點(diǎn)，在p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)，則執(zhí)行的操作是________。A．s->next=p;p->next=s; B．s->next=p->next;p->next=s;C．s->next=p->next;p=s; D．p->next=s;s->next=p;答案：B。17．下列關(guān)于帶頭結(jié)點(diǎn)的單向循環(huán)鏈表L的敘述中，正確的是________。A．L中最后一個(gè)結(jié)點(diǎn)的指針域要指向頭結(jié)點(diǎn)B．循環(huán)鏈表的長(zhǎng)度為L(zhǎng)中數(shù)據(jù)元素個(gè)數(shù)加1C．因?yàn)長(zhǎng)是環(huán)形的，所以無(wú)法計(jì)算鏈表長(zhǎng)度D．L中最后一個(gè)結(jié)點(diǎn)的指針域指向首個(gè)數(shù)據(jù)結(jié)點(diǎn)答案：A。帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的基本形態(tài)如圖2-3所示，不論是否有數(shù)據(jù)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針均是指向頭結(jié)點(diǎn)的（選項(xiàng)A正確，選項(xiàng)D錯(cuò)誤）。鏈表的長(zhǎng)度為所包含的數(shù)據(jù)元素的個(gè)數(shù)，與鏈表的長(zhǎng)度為L(zhǎng)中數(shù)據(jù)元素個(gè)數(shù)加1是否有頭結(jié)點(diǎn)無(wú)關(guān)（選項(xiàng)B錯(cuò)誤），與鏈表中是否有環(huán)無(wú)關(guān)（選項(xiàng)C錯(cuò)誤）。b)b)帶頭結(jié)點(diǎn)的非空單向循環(huán)鏈表LABCDa)帶頭結(jié)點(diǎn)的空單向循環(huán)鏈表L圖2-3帶頭結(jié)點(diǎn)的單向循環(huán)鏈表18．含6個(gè)元素的線(xiàn)性表保存在如下所示的數(shù)組中，它表示的是一個(gè)靜態(tài)________。表元素關(guān)鍵字表元素之間的聯(lián)系0631618522051310344501257816691007A．單鏈表 B．雙向鏈表C．單向循環(huán)鏈表 D．雙向循環(huán)鏈表答案：C。靜態(tài)鏈表是使用一維數(shù)組實(shí)現(xiàn)的鏈表。在本題中，使用“表元素之間的聯(lián)系”來(lái)反映各個(gè)結(jié)點(diǎn)之間的關(guān)系（鏈接），其作用類(lèi)似鏈表中的next。數(shù)組中保存了7個(gè)值，線(xiàn)性表中的元素值是6個(gè)，表明數(shù)組下標(biāo)0處保存的特殊結(jié)點(diǎn)。根據(jù)給出的表元素之間的關(guān)系，可以畫(huà)出如圖2-4所示的鏈表。headhead20516185910078162501103463圖2圖2-4帶頭結(jié)點(diǎn)的單向循環(huán)鏈表根據(jù)圖示，鏈表為帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表，頭結(jié)點(diǎn)（虛擬結(jié)點(diǎn)）是下標(biāo)為0的元素。二、填空題1．線(xiàn)性表是一個(gè)有限序列，組成線(xiàn)性表的是n（n≥0）個(gè)__________。答案：同類(lèi)型的數(shù)據(jù)元素。線(xiàn)性表的定義要求組成線(xiàn)性表的數(shù)據(jù)元素是同類(lèi)型的。2．不帶頭結(jié)點(diǎn)的單鏈表L（head為頭指針）為空的判定條件是__________。答案：head==NULL。不帶頭結(jié)點(diǎn)的空單鏈表中一個(gè)結(jié)點(diǎn)都沒(méi)有，頭指針的值為NULL。3．帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L（head為頭指針）為空的條件是__________。答案：head->next==head或是head->prev==head帶頭結(jié)點(diǎn)的空雙向循環(huán)鏈表中僅有一個(gè)頭結(jié)點(diǎn)，且這個(gè)結(jié)點(diǎn)的next指針和prev指針都指向結(jié)點(diǎn)本身，即與head指向相同。4．在帶頭結(jié)點(diǎn)的單鏈表中，當(dāng)刪除某一指定結(jié)點(diǎn)時(shí)，必須要找到該結(jié)點(diǎn)的__________。答案：前驅(qū)。被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)，變?yōu)楸粍h除結(jié)點(diǎn)原前驅(qū)結(jié)點(diǎn)的后繼，所以要找到前驅(qū)結(jié)點(diǎn)，并修改它的next值。5．在數(shù)組中保存的鏈表稱(chēng)為_(kāi)_________。答案：靜態(tài)鏈表。基本概念。6．設(shè)一個(gè)非空的靜態(tài)鏈表保存在數(shù)組中，以-1表示表尾所在結(jié)點(diǎn)為表尾結(jié)點(diǎn)，則含-1的單元個(gè)數(shù)最多為_(kāi)_________。答案：2。7．若線(xiàn)性表中每個(gè)元素占size個(gè)單元，采用順序存儲(chǔ)方式，第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置是1000，則線(xiàn)性表第i個(gè)元素的存儲(chǔ)位置Loc(ai)=__________。答案：1000+(i-1)size。在順序存儲(chǔ)方式下，數(shù)組下標(biāo)與線(xiàn)性表元素的位置的對(duì)應(yīng)關(guān)系可以通過(guò)公式LOC(ai)=LOC(a0)+id（教材公式2-2）進(jìn)行計(jì)算。根據(jù)題目，第一個(gè)數(shù)據(jù)元素是線(xiàn)性表中的a0，即第1個(gè)數(shù)據(jù)元素保存在數(shù)組下標(biāo)為0的位置，公式中的d為size，則第i個(gè)元素保存在數(shù)組下標(biāo)為i-1的位置，元素i的存儲(chǔ)位置LOC(ai)=1000+(i-1)size。三、解答題1．在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？【參考答案】在單鏈表中進(jìn)行插入和刪除操作時(shí)，都要找到操作位置結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。但根據(jù)線(xiàn)性表當(dāng)前指針的原始定義，前驅(qū)結(jié)點(diǎn)是不能通過(guò)當(dāng)前指針直接找到的。所以，修改當(dāng)前指針指向的結(jié)點(diǎn)，讓其前移一個(gè)位置，即指向操作位置的前驅(qū)結(jié)點(diǎn)。這樣修改后，通過(guò)當(dāng)前指針很容易訪(fǎng)問(wèn)到插入和刪除操作所涉及的各個(gè)結(jié)點(diǎn)。但當(dāng)操作位置是第一個(gè)結(jié)點(diǎn)時(shí)，或是單鏈表是空表時(shí)，當(dāng)前指針的指向又成為特殊情況，需要單獨(dú)處理。為了能統(tǒng)一處理各種情況，給單鏈表添加一個(gè)虛擬結(jié)點(diǎn)，即頭結(jié)點(diǎn)，從而減少實(shí)現(xiàn)插入和刪除操作時(shí)對(duì)特殊情況的判定及處理情況。2．什么是單鏈表中的頭結(jié)點(diǎn)、第一個(gè)數(shù)據(jù)結(jié)點(diǎn)和頭指針？【參考答案】單鏈表中保存線(xiàn)性表中各數(shù)據(jù)的結(jié)點(diǎn)是數(shù)據(jù)結(jié)點(diǎn)，這些結(jié)點(diǎn)中的第一個(gè)是第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。它的前面是一個(gè)虛擬結(jié)點(diǎn)，稱(chēng)為頭結(jié)點(diǎn)。一個(gè)特殊的指向單鏈表中最前面結(jié)點(diǎn)的指針是頭指針。如果單鏈表中一個(gè)結(jié)點(diǎn)都沒(méi)有，則頭指針為空。3．假設(shè)線(xiàn)性表L=(51,40,19,15,24,36)，使用線(xiàn)性表ADT中定義的方法，列出刪除19時(shí)對(duì)應(yīng)的語(yǔ)句序列?！緟⒖即鸢浮縤f(isEmpty(&L)==FALSE){ intpos,x; pos=find(&L,19); if(pos>=0)removeList(&L,pos,&x);}4．已知線(xiàn)性表中一個(gè)元素占8個(gè)字節(jié)，一個(gè)指針占2個(gè)字節(jié)，數(shù)組的大小為20個(gè)元素。在順序及鏈?zhǔn)絻煞N存儲(chǔ)方式中，線(xiàn)性表應(yīng)該采用哪種方式保存？為什么？【參考答案】設(shè)線(xiàn)性表中元素個(gè)數(shù)為n。單純考慮空間復(fù)雜度。采用順序存儲(chǔ)時(shí)，占用的空間大小=208=160個(gè)字節(jié)。采用鏈?zhǔn)酱鎯?chǔ)時(shí)，不妨設(shè)采用單鏈表存儲(chǔ)，占用的空間大小=n(8+2)=10n個(gè)字節(jié)。列方程，10n=160，求得n=16。即若線(xiàn)性表中元素個(gè)數(shù)少于16個(gè)時(shí)，采用單鏈表保存更好，元素個(gè)數(shù)多于16個(gè)時(shí)，采用數(shù)組保存更好。等于16個(gè)時(shí)，兩種方式保存的效果是一樣的。5．在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪(fǎng)問(wèn)到表中的任何一個(gè)結(jié)點(diǎn)?【參考答案】在單鏈表和雙向鏈表中，如果是從頭結(jié)點(diǎn)或第一個(gè)數(shù)據(jù)結(jié)點(diǎn)出發(fā)，能訪(fǎng)問(wèn)到表中的任一結(jié)點(diǎn)，但從其他結(jié)點(diǎn)出發(fā)，都只能訪(fǎng)問(wèn)到該結(jié)點(diǎn)及其全部的后繼結(jié)點(diǎn)，它的前驅(qū)結(jié)點(diǎn)是訪(fǎng)問(wèn)不到的。6．線(xiàn)性表(a0,a1,…,an-1)采用順序存儲(chǔ)方式時(shí)，ai和ai+1（0≤i<n-1）的物理位置相鄰嗎？采用鏈?zhǔn)椒绞綍r(shí)呢？【參考答案】采用順序存儲(chǔ)方式時(shí)，ai和ai+1（0≤i<n-1）的物理位置是相鄰的。采用鏈?zhǔn)酱鎯?chǔ)時(shí)，ai和ai+1（0≤i<n-1）的物理位置不一定是相鄰的?？赡芟噜徱部赡懿幌噜?。7．試分析雙向鏈表中插入、刪除、查找等基本操作的時(shí)間復(fù)雜度?！緟⒖即鸢浮吭陔p向鏈表中進(jìn)行插入和刪除操作時(shí)，如果給定了當(dāng)前指針，則插入操作和刪除操作的時(shí)間復(fù)雜度均為O(1)，因?yàn)椴僮鬟^(guò)程中不需要進(jìn)行元素的移動(dòng)，也不需要將當(dāng)前指針從表頭后移到當(dāng)前位置。查找操作的時(shí)間復(fù)雜度是根據(jù)查找目標(biāo)在鏈表中的位置而定的。若在雙向鏈表中一定能找到查找目標(biāo)，則最優(yōu)情況下，比較1次就能找到，時(shí)間復(fù)雜度為O(1)。最壞的情況下，需要進(jìn)行n次比較，時(shí)間復(fù)雜度為O(n)。平均來(lái)看，需要查找約一半的鏈表，所以時(shí)間復(fù)雜度是O(n)。8．靜態(tài)鏈表中，如何同時(shí)保存單鏈表及空閑空間鏈表？【參考答案】：靜態(tài)鏈表采用的一片連續(xù)區(qū)域（數(shù)組）作為鏈表的存儲(chǔ)空間。為有效使用存儲(chǔ)空間，提高空間的使用效率，對(duì)于數(shù)組中所有未曾使用過(guò)的單元必定是保持一片連續(xù)單元，這樣可以使用整型變量unused記錄這片連續(xù)單元的首位置，凡是下標(biāo)大于等于unused且不越界的單元，均為空閑單元。對(duì)于數(shù)組中曾經(jīng)使用過(guò)且目前空閑的所有單元，建立一個(gè)靜態(tài)的空閑單元鏈表將其鏈接起來(lái)，用整型變量available記錄這個(gè)鏈表首結(jié)點(diǎn)的下標(biāo)。9．靜態(tài)鏈表中，unused的作用是什么？【參考答案】：靜態(tài)鏈表采用的一片連續(xù)區(qū)域（數(shù)組）作為鏈表的存儲(chǔ)空間。為有效使用存儲(chǔ)空間，提高空間的使用效率，對(duì)于數(shù)組中所有未曾使用過(guò)的單元必定是保持一片連續(xù)單元，這樣可以使用整型變量unused記錄這片連續(xù)單元的首位置，凡是下標(biāo)大于等于unused且不越界的單元，均為空閑單元。四、算法閱讀題1．在如主教材圖2-13b所示的帶頭結(jié)點(diǎn)的非空循環(huán)鏈表中保存了若干整數(shù)。算法average求出這些整數(shù)的平均值。請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容將算法補(bǔ)充完整。floataverage(LinkListhead){ LinkNode*p; intcounter=0,sum=0; if(head==NULL){ printf("鏈表錯(cuò)誤\n"); returnFALSE; } if(（1）)printf("這是一個(gè)空鏈表\n"); else{ p=head->next; while(（2）){ counter++; sum+=p->data; p=p->next; } } return（3）;}【參考答案】（1）head->next==head（2）p!=head（3）sum*1.0/counter對(duì)于（1），根據(jù)后面輸出的內(nèi)容可知，這里需要補(bǔ)上判定空表的條件。帶頭結(jié)點(diǎn)的空循環(huán)鏈表只含有一個(gè)頭結(jié)點(diǎn)，且該結(jié)點(diǎn)的next域指向結(jié)點(diǎn)本身。對(duì)于（2），根據(jù)題意，循環(huán)體中要對(duì)表中的全部結(jié)點(diǎn)進(jìn)行處理。進(jìn)入循環(huán)之前，指針p指向了第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。while循環(huán)的結(jié)束條件是什么呢？當(dāng)指針p轉(zhuǎn)回到表頭時(shí)，表明已經(jīng)處理完全部的數(shù)據(jù)結(jié)點(diǎn)，此時(shí)循環(huán)可以結(jié)束。也就是在p沒(méi)有指向頭結(jié)點(diǎn)時(shí)，循環(huán)不結(jié)束。當(dāng)p==head時(shí)表明p指向頭結(jié)點(diǎn)，當(dāng)p!=head時(shí)表明p沒(méi)有指向頭結(jié)點(diǎn)。對(duì)于（3），返回的是表中元素的平均值。while循環(huán)體中已經(jīng)計(jì)算了全部元素的和及元素個(gè)數(shù)，兩個(gè)值做除法就可以了。注意不要進(jìn)行整除，兩個(gè)整數(shù)相除，結(jié)果可能除不盡，是個(gè)實(shí)型值。2．單鏈表的結(jié)點(diǎn)及鏈表定義如下：typedefstructnode{ intdata; //數(shù)據(jù)域 structnode*next; //指針域}LinkNode;typedefLinkNode*LinkList; //單鏈表算法largest找出這些整數(shù)中的最大值。請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容將算法補(bǔ)充完整。intlargest(LinkListhead){ LinkNode*p; intmaxitem; if(head==NULL){ printf("鏈表錯(cuò)誤\n"); returnFALSE; } if(（1）)printf("這是一個(gè)空鏈表\n"); else{ p=head->next; maxitem=p->data; p=p->next; while(p!=NULL){ if(（2）)（3）; p=p->next; } } returnmaxitem;}【參考答案】（1）head->next==NULL（2）p->data>maxitem（3）maxitem=p->data對(duì)于（1），空單鏈表中僅含有一個(gè)頭結(jié)點(diǎn)，頭指針指向結(jié)點(diǎn)的next域?yàn)镹ULL。根據(jù)題意，要記錄表中元素的最大值，這由if語(yǔ)句來(lái)完成。顯然，if的條件是篩選最大值，后面的語(yǔ)句是將最大值保存下來(lái)。return語(yǔ)句中返回的是maxitem的值，意味著這個(gè)變量是用來(lái)保存最大值的，所以（3）的內(nèi)容很容易寫(xiě)下來(lái)，就是將當(dāng)前結(jié)點(diǎn)中的值賦給maxitem。那么，當(dāng)前結(jié)點(diǎn)需要滿(mǎn)足什么條件呢？是要大于原來(lái)保存的maxitem值，這是（2）要填寫(xiě)的內(nèi)容。3．閱讀程序，并回答下列問(wèn)題。intcounterofodd(LinkListhead){ LinkNode*p; intcounter=0; if(head==NULL){ printf("鏈表錯(cuò)誤\n"); returnFALSE; } if(head->next==NULL)printf("這是一個(gè)空鏈表\n"); else{ p=head->next; while(p!=NULL){ if(p->data%2!=0)counter++; p=p->next; } } returncounter;}（1）若單鏈表head中保存的是(1,3,5,7,10)，則執(zhí)行counterofodd(head)后，返回的結(jié)果是什么？（2）counterofodd()的功能是什么？【參考答案】（1）返回的結(jié)果是4。（2）counterofodd()的功能是統(tǒng)計(jì)單鏈表head中保存的奇數(shù)的個(gè)數(shù)。五、算法設(shè)計(jì)題1．教材中表2-1給出一個(gè)線(xiàn)性表操作示例，請(qǐng)采用順序存儲(chǔ)方式保存線(xiàn)性表，編程使用基本操作驗(yàn)證表中的結(jié)論?！緟⒖即鸢浮框?yàn)證程序的main函數(shù)實(shí)現(xiàn)如下。//采用順序表存儲(chǔ)，驗(yàn)證基本操作#include<stdio.h>#include"SeqList.h"intmain(intargc,char**argv){ LinearListlisttest; inti,temp; printf("采用順序表保存線(xiàn)性表\n"); if(initList(&listtest)==FALSE){ printf("初始化失敗\n"); return0; }elseprintf("完成初始化\n"); for(i=0;i<6;i++) if(!insertList(&listtest,i,2*i)) printf("插入錯(cuò)誤\n"); display(&listtest); if(!removeList(&listtest,3,&temp))printf("刪除錯(cuò)誤\n"); else{ printf("刪除的3號(hào)元素是：%d\n",temp); printf("刪除后，"); display(&listtest); } if(!setValue(&listtest,3,-10)) printf("修改值出錯(cuò)\n"); else{ printf("修改3號(hào)元素的值，"); display(&listtest); } if(!getValue(&listtest,3,&temp))printf("獲取值出錯(cuò)\n"); elseprintf("獲取3號(hào)元素的值：%d\n",temp); printf("查找10的結(jié)果:%d\n",find(&listtest,10)); printf("查找9的結(jié)果:%d\n",find(&listtest,9)); return0;}2．教材中表2-1給出一個(gè)線(xiàn)性表操作示例，請(qǐng)采用鏈?zhǔn)酱鎯?chǔ)方式保存線(xiàn)性表，編程使用基本操作驗(yàn)證表中的結(jié)論?！緟⒖即鸢浮框?yàn)證程序的main函數(shù)實(shí)現(xiàn)如下。//采用帶頭結(jié)點(diǎn)的單鏈表驗(yàn)證基本操作#include<stdio.h>#ifndefLinearList#defineLinearList#include"LinkedList.h"#endif//typedefLinkListLinearList;intmain(intargc,char**argv){ LinkListhead,pre; inti,temp; Positionpos; printf("采用單鏈表保存線(xiàn)性表\n"); if(initList(&head)==FALSE){ printf("初始化失敗\n"); return0; }elseprintf("完成初始化\n"); for(i=0;i<6;i++) if(!insertList(&head,i,2*i)) printf("插入錯(cuò)誤\n"); display(&head); if(!removeList(&head,3,&temp))printf("刪除錯(cuò)誤\n"); else{ printf("刪除的3號(hào)元素是：%d\n",temp); printf("刪除后，"); display(&head); } if(!setValue(&head,3,-10)) printf("修改值出錯(cuò)\n"); else{ printf("修改3號(hào)元素后："); display(&head); } if(!getValue(&head,3,&temp))printf("獲取值出錯(cuò)\n"); elseprintf("獲取3號(hào)元素的值：%d\n",temp); printf("查找10的結(jié)果:%d\n",find(&head,10)); printf("查找9的結(jié)果:%d\n",find(&head,9)); return0;}3．教材中表2-1給出一個(gè)線(xiàn)性表操作示例，請(qǐng)采用靜態(tài)鏈?zhǔn)酱鎯?chǔ)方式保存線(xiàn)性表，編程使用基本操作驗(yàn)證表中的結(jié)論。【參考答案】驗(yàn)證程序的main函數(shù)實(shí)現(xiàn)如下。#include<stdio.h>#include"ArrayList.h"intmain(intargc,char**argv){ ArrayListlisttest; inttemp,i; initList(&listtest); displayList(listtest); for(i=0;i<6;i++) if(!insertArrayList(&listtest,i,2*i)) printf("插入錯(cuò)誤\n"); displayList(listtest); displayArray(listtest); if(!removeArrayList(&listtest,3,&temp)) printf("刪除錯(cuò)誤\n"); else{ printf("刪除的元素是：%d\n",temp); printf("刪除后，"); displayList(listtest); } if(!setValue(&listtest,3,-10))printf("修改值出錯(cuò)\n"); else{ printf("修改3號(hào)元素的值，"); displayList(listtest); } if(!getValue(&listtest,3,&temp))printf("獲取值出錯(cuò)\n"); elseprintf("獲取3號(hào)元素的值：%d\n",temp); printf("查找10的結(jié)果:%d\n",find(&listtest,10)); printf("查找9的結(jié)果:%d\n",find(&listtest,9)); displayList(listtest); displayArray(listtest); return0;}4．教材中表2-1給出一個(gè)線(xiàn)性表操作示例，請(qǐng)采用帶頭結(jié)點(diǎn)的雙向鏈表存儲(chǔ)方式保存線(xiàn)性表，編程使用基本操作驗(yàn)證表中的結(jié)論?！緟⒖即鸢浮縤ntmain(intargc,char**argv){ ArrayListlisttest; inttemp,i,a[]={618,205,103,501,781,910}; Positionpos; initList(&listtest); printf("初始化靜態(tài)數(shù)組后的狀態(tài)：\n"); displayArray(listtest); for(i=0;i<6;i++) if(!insertSortArrayList(&listtest,a[i])) printf("插入錯(cuò)誤\n"); displayList(listtest); displayArray(listtest); if((pos=find(&listtest,501))!=ERROR) { if(!removeArrayList(&listtest,pos,&temp)) printf("刪除錯(cuò)誤\n"); else{ printf("刪除的元素是：%d\n",temp); printf("刪除501后，"); displayList(listtest); } } if((pos=find(&listtest,103))!=ERROR) { if(!removeArrayList(&listtest,pos,&temp)) printf("刪除錯(cuò)誤\n"); else{ printf("刪除的元素是：%d\n",temp); printf("刪除103后，"); displayList(listtest); } } printf("靜態(tài)數(shù)組狀態(tài)：\n"); displayArray(listtest); if(!insertSortArrayList(&listtest,301)) printf("插入錯(cuò)誤\n"); printf("插入301之后："); displayList(listtest); printf("靜態(tài)數(shù)組狀態(tài)：\n"); displayArray(listtest); return0;}5．設(shè)有一個(gè)正整數(shù)序列組成的有序單鏈表（按遞增次序有序，且允許有相等的整數(shù)存在），試編寫(xiě)能實(shí)現(xiàn)下列功能的算法：（1）確定在序列中比正整數(shù)x大的數(shù)有幾個(gè)（相同的數(shù)只計(jì)算一次，如有序序列{10,20,30,30,40,41,50,50,51}中比30大的數(shù)有4個(gè)）；（2）將單鏈表中比正整數(shù)x小的數(shù)按遞減次序重排，仍放置在單鏈表中；如保存有序序列{10,20,30,30,40,41,50,50,51}的單鏈表中，將比40小的數(shù)重排后，得到的單鏈表中保存的序列是{30,30,20,10,40,41,50,50,51}。（3）將比x大的偶數(shù)從單鏈表中刪除。【參考答案】（1）程序?qū)崿F(xiàn)如下所示。intlargerthanx(LinkListhead,intx){ intcounter=0,lastone; LinkNode*p; if(head==NULL){ printf("鏈表錯(cuò)誤\n"); returnFALSE; } if(head->next==NULL)printf("這是一個(gè)空鏈表\n"); else{ p=head->next; lastone=p->data-1; while(p!=NULL){ if(p->data>x){ if(p->data>lastone){ counter++; lastone=p->data; } } p=p->next; } } returncounter;}因?yàn)閱捂湵碛行?，所以，如果有相同的整?shù)，則它們一定是相鄰的。使用變量lastone記錄前一個(gè)整數(shù)，如果當(dāng)前整數(shù)與lastone相等，則不計(jì)數(shù)。lastone的初值設(shè)為比第一個(gè)整數(shù)小的任何數(shù)即可。（2）程序?qū)崿F(xiàn)如下所示。intreversesmallthanx(LinkListhead,intx){ LinkNode*left,*middle,*right,*temp; if(head==NULL){ printf("鏈表錯(cuò)誤\n"); returnFALSE; } if(head->next==NULL){ printf("這是一個(gè)空鏈表\n"); returnTRUE; } else{ temp=left=head->next; if(left!=NULL)middle=left->next; while(middle!=NULL&&middle->data<x){ right=middle->next; middle->next=left; left=middle; middle=right; } if(middle==NULL){ temp->next=NULL; head->next=left; } else{ temp->next=middle; head->next=left; } } returnTRUE;}將單鏈表中比正整數(shù)x小的數(shù)按遞減次序重排，實(shí)際上是將單鏈表前面的若干結(jié)點(diǎn)逆置。與教材第二章第五節(jié)中給出的reverse有些類(lèi)似，但情況更復(fù)雜一些。當(dāng)找不到比x小的元素時(shí)，單鏈表維持不變。當(dāng)所有元素均小于x時(shí)，整個(gè)鏈表逆置。當(dāng)部分元素小于x時(shí)，只逆置前面的這些元素，逆置后的子表還要與原來(lái)的后半部分子表拼起來(lái)。（3）程序?qū)崿F(xiàn)如下所示。intremoveevenlargethanx(LinkListhead,intx){ LinkNode*current; intk,pos=0; if(head==NULL){ printf("鏈表錯(cuò)誤\n"); returnFALSE; } if(head->next==NULL){ printf("這是一個(gè)空鏈表\n"); returnTRUE; } else{ current=head; while(current->next!=NULL){ if(current->next->data>x&¤t->next->data%2==0){ removeList(&head,pos,&k); } else{ current=current->next; pos++; } } } returnTRUE;}刪除滿(mǎn)足條件的元素時(shí)，可以調(diào)用單鏈表中實(shí)現(xiàn)的remove操作。要注意的是，刪除一個(gè)結(jié)點(diǎn)后，當(dāng)前指針current不改變，此時(shí)，current不后移，繼續(xù)判斷它指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)。但如果沒(méi)有刪除結(jié)點(diǎn)，則current需要后移一個(gè)位置。6．在單鏈表L中保存了若干整數(shù)。實(shí)現(xiàn)算法將L分為兩個(gè)單鏈表L1和L2，其中L1中保存奇數(shù)，L2中保存偶數(shù)?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intpartition(LinkList*L,LinkList*L1,LinkList*L2){ LinkNode*L1curr,*L2curr; LinkNode*temp; if((*L)==NULL){ printf("鏈表錯(cuò)誤\n"); return0; } initList(L1); initList(L2); if((*L)->next==NULL){ printf("這是一個(gè)空鏈表\n"); returnTRUE; } else{ temp=(*L)->next; L1curr=*L1; L2curr=*L2; while(temp!=NULL){ (*L)->next=temp->next; temp->next=NULL; if(temp->data%2==0){ L2curr->next=temp; L2curr=L2curr->next; (*L2)->data++; } else{ L1curr->next=temp; L1curr=L1curr->next; (*L1)->data++; } temp=(*L)->next; } } returnTRUE;}將單鏈表L拆分為兩個(gè)單鏈表L1和L2，實(shí)際上就是從L中刪除一個(gè)結(jié)點(diǎn)，然后根據(jù)結(jié)點(diǎn)中值的奇偶性，或是將結(jié)點(diǎn)添加到L1中，或是將結(jié)點(diǎn)添加到L2中。因?yàn)閯h除和插入都是依次進(jìn)行的，所以，設(shè)置一個(gè)當(dāng)前工作指針記錄三個(gè)鏈表的當(dāng)前位置。7．已知帶頭結(jié)點(diǎn)的單鏈表的每個(gè)結(jié)點(diǎn)中保存一個(gè)整數(shù)，數(shù)據(jù)結(jié)點(diǎn)有n個(gè)。請(qǐng)?jiān)O(shè)計(jì)算法以判斷該鏈表中保存的值是否構(gòu)成斐波那契數(shù)列中的前n項(xiàng)。若是算法返回1，否則返回0。【參考答案】程序?qū)崿F(xiàn)如下所示。intisFibonacci(LinkListhead){ LinkNode*p1,*p2,*p3; intf1=1,f2=1,f3,i; if(head==NULL){ printf("鏈表錯(cuò)誤\n"); returnFALSE; } if(head->next==NULL){ printf("這是一個(gè)空鏈表\n"); returnFALSE; } if(head->data==1&&head->next->data==1)returnTRUE; if(head->data==2&&head->next->data==1&&head->next->next->data==1) returnTRUE; p1=head->next; if(p1->data!=1)returnFALSE; p2=p1->next; if(p2->data!=1)returnFALSE; p3=p2->next; while(p3!=NULL&&p3->data==p1->data+p2->data){ p1=p2; p2=p3; p3=p3->next; } if(p3==NULL)return1; elsereturnFALSE;}斐波那契數(shù)列中含有多個(gè)整數(shù)值，如果整數(shù)的個(gè)數(shù)少于3個(gè)，則為特殊情況，程序中需要對(duì)此進(jìn)行特殊的處理。即單鏈表中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)少于3個(gè)時(shí)，需要單獨(dú)進(jìn)行判定。前兩個(gè)結(jié)點(diǎn)中的整數(shù)都是1。當(dāng)結(jié)點(diǎn)個(gè)數(shù)大于等于3個(gè)時(shí)，從第三個(gè)結(jié)點(diǎn)開(kāi)始，一直到尾結(jié)點(diǎn)，判定每個(gè)結(jié)點(diǎn)中保存的整數(shù)是否是相鄰的前兩個(gè)結(jié)點(diǎn)中值的和。8．實(shí)現(xiàn)算法，判斷帶頭結(jié)點(diǎn)的單鏈表中所保存的整數(shù)，是否構(gòu)成遞增有序序列。若是遞增有序序列，則算法返回1；若不是有序序列，則算法返回0?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intisincrease(LinkListhead){ LinkNode*p; intcurrmax; if(head==NULL){ printf("鏈表錯(cuò)誤\n"); returnFALSE; } if(head->next==NULL){ printf("這是一個(gè)空鏈表\n"); returnTRUE; } p=head->next; //第一個(gè)數(shù)據(jù)結(jié)點(diǎn) currmax=p->data; p=p->next; while(p!=NULL&&p->data>=currmax){ currmax=p->data; p=p->next; } if(p==NULL)returnTRUE; elsereturnFALSE; }9．設(shè)線(xiàn)性表元素為整數(shù)，其中可能有相同的元素。試設(shè)計(jì)一個(gè)算法刪除表中重復(fù)的元素（即相同元素只保留一個(gè)），使刪除后表中各元素均不相同。給出在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式下的實(shí)現(xiàn)程序。【參考答案】線(xiàn)性表如果有序，則很容易刪除表中的重復(fù)元素。但當(dāng)線(xiàn)性表無(wú)序時(shí)，需要進(jìn)行更多的比較才能實(shí)現(xiàn)。采用順序存儲(chǔ)方式的程序?qū)崿F(xiàn)如下所示。intunique(SeqList*L){ inti,j,k,len; intNA=-65535; //NA用來(lái)做標(biāo)記 len=L->n; for(i=1;i<len;i++) for(j=0;j<i;j++){ if(L->element[i]==L->element[j])L->element[i]=NA; } k=1; for(i=1;i<len;i++){ if(L->element[i]!=NA){ L->element[k++]=L->element[i]; } } L->n=k; returnTRUE;}從數(shù)組中刪除一個(gè)重復(fù)元素時(shí)，后面的元素都要依次向前移動(dòng)。為避免過(guò)多的元素移動(dòng)，當(dāng)發(fā)現(xiàn)重復(fù)元素時(shí)，僅對(duì)重復(fù)元素進(jìn)行標(biāo)記，而不是立即進(jìn)行刪除。當(dāng)查找到所有重復(fù)元素后，再將剩余元素依次保存到數(shù)組最前面的若干位置中。使用NA標(biāo)記要?jiǎng)h除的元素。采用鏈?zhǔn)酱鎯?chǔ)方式的程序?qū)崿F(xiàn)如下所示。voidunique(LinkListhead){ LinkNode*p,*current; intk,pos=0,currpos=0; if(head==NULL){ printf("鏈表錯(cuò)誤\n"); return; } if(head->next==NULL){ printf("這是一個(gè)空鏈表\n"); return; } if(head->data==1)return; current=head; pos=1; currpos=0; while(current!=NULL&¤t->next!=NULL){ p=current; pos=currpos; while(p->next!=NULL){ if(p->next->data==current->data){ removeList(&head,pos,&k); } else{ p=p->next; pos++; } } current=current->next; currpos++; } return; }current是當(dāng)前指針，指示當(dāng)前結(jié)點(diǎn)。使用另一個(gè)指針p從當(dāng)前位置開(kāi)始向后依次掃描結(jié)點(diǎn)。當(dāng)p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)中的值與current所指結(jié)點(diǎn)中的值相等時(shí)，刪除重復(fù)結(jié)點(diǎn)，即刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)?？梢哉{(diào)用removeList函數(shù)完成刪除操作。因?yàn)閯h除函數(shù)的第二個(gè)參數(shù)是位置，所以使用currpos記錄current指向的結(jié)點(diǎn)的位置值，使用pos記錄p指向結(jié)點(diǎn)的位置值。當(dāng)p指向表尾時(shí)，表示一輪掃描完成，current指向下一個(gè)結(jié)點(diǎn)，繼續(xù)同樣的查重及刪除操作。10．設(shè)有兩個(gè)按元素值遞增有序排列的單鏈表A和B。試實(shí)現(xiàn)算法，將它們合并成一個(gè)單鏈表C，要求C的元素值仍按遞增有序排列（允許C中有值相同的元素）?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。voidmergelist(LinkList*A,LinkList*B,LinkList*C){ LinkNode*pA=*A,*pB=*B,*pC=*C,*temp; while(pA->next!=NULL&&pB->next!=NULL){ if(pA->next->data<pB->next->data){ temp=pA->next; pA->next=temp->next; temp->next=NULL; pC->next=temp; (*A)->data--; } else{ temp=pB->next; pB->next=temp->next; temp->next=NULL; pC->next=temp; (*B)->data--; } pC=pC->next; (*C)->data++; } if(pA->next==NULL){ pC->next=pB->next; pB->next=NULL; (*C)->data+=(*B)->data; } else{ pC->next=pA->next; pA->next=NULL; (*C)->data+=(*A)->data; } return;}因?yàn)閮蓚€(gè)單鏈表A和B是遞增有序的，合并后的鏈表也要求是遞增有序的，所以可以分別從前向后掃描A和B。使用三個(gè)工作指針?lè)謩e指向A、B和C的當(dāng)前位置。比較A和B當(dāng)前結(jié)點(diǎn)中元素的值，將更小值的結(jié)點(diǎn)移至鏈表C中。這個(gè)思想是二路歸并排序中兩個(gè)有序歸并段合并的思想?？梢詤⒖嫉?章第五節(jié)的相關(guān)內(nèi)容。11．已知帶頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)定義如下：typedefintELEMType;typedefstructnode{ //單鏈表結(jié)點(diǎn) ELEMTypedata; //數(shù)據(jù)域 structnode*next; //指針域}LinkNode;typedefLinkNode*LinkList; //單鏈表請(qǐng)編寫(xiě)函數(shù)intappendList(LinkListhead,ELEMTypex)，將x插入到head指向的單鏈表的表尾?！緟⒖即鸢浮縤ntappendList(LinkList*head,ELEMTypex){ LinkNode*p,*temp; p=(LinkList)malloc(sizeof(LinkNode)); p->data=x; p->next=NULL; temp=*head; while(temp->next!=NULL){ temp=temp->next; } temp->next=p; returnTRUE;}12．已知鏈表結(jié)點(diǎn)及帶頭結(jié)點(diǎn)的單鏈表定義如下：typedefintELEMType;typedefstructnode{ //單鏈表結(jié)點(diǎn) ELEMTypedata; //數(shù)據(jù)域 structnode*next; //指針域}LinkNode;typedefLinkNode*LinkList; //單鏈表請(qǐng)編寫(xiě)函數(shù)intdeleteNode(LinkListhead,ElemTypex)，將在head指向的單鏈表中刪除data等于x的結(jié)點(diǎn)，如果刪除成功，函數(shù)返回值為1，刪除失敗，返回值為0?！緟⒖即鸢浮縤ntdeleteNode(LinkList*head,ELEMTypex){ LinkNode*p=*head,*temp; while(p!=NULL&&p->next!=NULL&&p->next->data!=x) { p=p->next; } if(p!=NULL&&p->next!=NULL&&p->next->data==x) { temp=p->next; p->next=p->next->next; free(temp); returnTRUE; } elsereturnFALSE; }13．判定給定的單鏈表中是否存在環(huán)？如果存在，函數(shù)返回1，否則返回0?！緟⒖即鸢浮縤ntisRing(LinkList*head){ LinkNode*p1=*head,*p2=*head; if(*head==NULL){ printf("鏈表錯(cuò)誤\n"); returnERROR; } if((*head)->next==NULL){ printf("這是一個(gè)空鏈表\n"); returnFALSE; } if(p2->next->next!=NULL){ p2=p2->next->next; p1=p1->next; } elsereturnFALSE; while(p1!=p2&&p2!=NULL){ p2=p2->next; if(p2!=NULL){ p1=p1->next; p2=p2->next; } elsereturn FALSE; } if(p1==p2)returnTRUE; elsereturnFALSE;}

第三章棧和隊(duì)列一、單項(xiàng)選擇題1．棧操作數(shù)據(jù)的原則是________。A．先進(jìn)先出 B．后進(jìn)先出 C．后進(jìn)后出 D．隨機(jī)處理答案：B。棧的特性是后進(jìn)先出。選項(xiàng)A是隊(duì)列的特性。有些情況下，可以將選項(xiàng)C理解為先進(jìn)先出，這也是隊(duì)列的特性。選項(xiàng)D既不是棧的特性，也不是隊(duì)列的特性。2．入棧序列是a1,a3,a5,a2,a4,a6，出棧序列是a5,a4,a2,a6,a3,a1，則棧的容量最小是________。A．2 B．3 C．4 D．5答案：C。用圖3-1表示棧狀態(tài)的變化情況。a1入棧a3入棧a5入棧a5出棧a2入棧a4入棧a4a5a2a2a3a3a3a3a3a1a1a1a1a1a1a4出棧a2出棧a6入棧a6出棧a3出棧a1出棧a2a6a3a3a3a3a1a1a1a1a1圖3-1棧圖3-1棧的狀態(tài)可以看到，在a4入棧后，棧中有4個(gè)元素，這是棧含元素最多的時(shí)刻。所以棧的容量最小是4。3．6個(gè)元素6,5,4,3,2,1依次進(jìn)棧，不能得到的出棧序列是________A．5,4,3,6,1,2 B．4,5,3,1,2,6 C．3,4,6,5,2,1 D．2,3,4,1,5,6答案：C?？梢允褂貌僮鬟^(guò)程來(lái)描述。得到選項(xiàng)A的操作過(guò)程是：push(6),push(5),pop(5),push(4),pop(4),push(3),pop(3),pop(6),push(2),push(1),pop(1),pop(2)。得到選項(xiàng)B的操作過(guò)程是：push(6),push(5),push(4),pop(4),pop(5),push(3),pop(3),push(2),push(1),pop(1),pop(2),pop(6)。得到選項(xiàng)D的操作過(guò)程是：push(6),push(5),push(4),push(3),push(2),pop(2),pop(3),pop(4),push(1),pop(1),pop(5),pop(6)。對(duì)于選項(xiàng)C，push(6),push(5),push(4),push(3),pop(3),pop(4)，此時(shí)棧頂元素是5，得不到元素6。4．輸入序列為A,B,C，借助于棧將其變?yōu)镃,B,A，經(jīng)過(guò)的棧操作為_(kāi)_______。A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,popC．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop答案：B。對(duì)應(yīng)于選項(xiàng)A的操作序列，得到的出棧序列是A,B,C。對(duì)應(yīng)于選項(xiàng)C的操作序列，得到的出棧序列是B,A,C。對(duì)應(yīng)于選項(xiàng)D的操作序列，得到的出棧序列是A,C,B。實(shí)際上，出棧序列與入棧序列互逆，所以必然是將所有元素依次入棧，然后依次出棧。5．若一個(gè)棧存儲(chǔ)在數(shù)組V[n]中，設(shè)棧空時(shí)棧頂指針top=n-1，則下列選項(xiàng)中，能正確表示x入棧的是________。A．top=top+1;V[top]=x; B．V[top]=x;top=top+1;C．V[top]=x;top=top-1; D．top=top-1;V[top]=x;答案：C。根據(jù)題意，棧頂指針指向的是棧頂元素旁邊的空位置，所以入棧時(shí)，元素x直接寫(xiě)入top所示的位置，然后top移至下一個(gè)空位置。又因?yàn)闂？諘r(shí)top指向的是數(shù)組下標(biāo)最大處，則意味著入棧時(shí)top應(yīng)向下標(biāo)減小的方向改變。6．用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)________。A．僅需要修改隊(duì)頭指針，不需要修改隊(duì)尾指針B．僅需要修改隊(duì)尾指針，不需要修改隊(duì)頭指針C．隊(duì)頭指針一定要修改，隊(duì)尾指針也一定要修改D．隊(duì)頭指針一定要修改，隊(duì)尾指針可能要修改答案：D。用不帶頭結(jié)點(diǎn)的單鏈表保存隊(duì)列時(shí)，通常需要兩個(gè)指針?lè)謩e指向隊(duì)頭結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)。出隊(duì)時(shí)，要從隊(duì)頭刪除一個(gè)結(jié)點(diǎn)，此時(shí)必須修改隊(duì)頭指針，讓它指向被刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)。如果隊(duì)列中還有其他結(jié)點(diǎn)，則隊(duì)尾指針不會(huì)變化。但如果刪除結(jié)點(diǎn)后隊(duì)列變?yōu)榭贞?duì)列，則還需要修改隊(duì)尾指針。7．下列鏈隊(duì)列的操作中，不可能修改隊(duì)尾指針的是________。A．入隊(duì)操作 B．清空隊(duì)列操作C．出隊(duì)操作 D．判隊(duì)列是否為空答案：D。入隊(duì)操作肯定會(huì)修改隊(duì)尾指針。出隊(duì)操作通常僅修改隊(duì)頭指針，但如果出隊(duì)后隊(duì)列為空，則也會(huì)修改隊(duì)尾指針。清空隊(duì)列的操作既修改隊(duì)頭指針，也修改隊(duì)尾指針。而判隊(duì)列是否為空，僅需要查看指針的值，不會(huì)進(jìn)行修改。8．循環(huán)隊(duì)列Q（最多元素為MaxSize），front指向隊(duì)頭元素所在位置，rear指向隊(duì)尾元素后的空位置，則循環(huán)隊(duì)列為滿(mǎn)的條件是________。A．Q.rear==Q.front B．Q.rear+1==Q.frontC．Q.rear==Q.front+1 D．(Q.rear+1)%MaxSize==Q.front答案：D?；靖拍睢⒖冀滩闹袌D3-14及圖3-16。9．用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí)應(yīng)進(jìn)行的操作是________。A．僅修改頭指針 B．頭、尾指針均不需要修改C．僅修改尾指針 D．頭、尾指針都可能要修改答案：D。出隊(duì)操作肯定要修改隊(duì)頭指針，如果出隊(duì)后隊(duì)列為空，則隊(duì)尾指針也要修改。10．假設(shè)以數(shù)組A[0..m-1]存放循環(huán)隊(duì)列的元素，隊(duì)頭指針front指向隊(duì)頭元素，隊(duì)尾指針rear指向隊(duì)尾元素后的空位置，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為_(kāi)_______。A．(rear-front+m)%m B．rear-front+1C．(front-rear+m+1)%m D．(rear-front)%m答案：A。循環(huán)隊(duì)列有兩種基本形態(tài)，如圖3-2a和圖3-2b示。a0…am-1↑front↑reara)循環(huán)隊(duì)列示意圖一…v……u…↑rear↑frontb)循環(huán)隊(duì)列示意圖二對(duì)于圖3-2a，隊(duì)列中的元素個(gè)數(shù)=rear-front。對(duì)于圖3-2b，隊(duì)列中的元素個(gè)數(shù)=rear+m-front。兩個(gè)表達(dá)式可以統(tǒng)一表示為(rear-front+m)%m。11．棧和隊(duì)列的共同點(diǎn)是________。A．都是后進(jìn)先出 B．都是先進(jìn)先出C．只允許在端點(diǎn)處插入和刪除元素 D．沒(méi)有共同點(diǎn)答案：C。棧具有后進(jìn)先出的特點(diǎn)，而隊(duì)列具有先進(jìn)先出的特點(diǎn)。所以選項(xiàng)A和B都不正確。棧的插入和刪除操作都在表的一端進(jìn)行，隊(duì)列的插入和刪除分別在表的兩端進(jìn)行。所以，選項(xiàng)C中概括的特點(diǎn)是棧和隊(duì)列共同具有的。12．循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，