第一章 緒論一、選擇題1. 算法的計(jì)算量的大小稱(chēng)為計(jì)算的（ ）。A效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度2. 算法的時(shí)間復(fù)雜度取決于（ ）A問(wèn)題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B3.計(jì)算機(jī)算法指的是（1），它必須具備（2） 這三個(gè)特性。(1) A計(jì)算方法 B. 排序方法 C. 解決問(wèn)題的步驟序列 D. 調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴(kuò)充性 B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性 4一個(gè)算法應(yīng)該是（ ）。 A程序 B問(wèn)題求解步驟的描述 C要滿(mǎn)足五個(gè)基本特性 DA和C. 5. 下面關(guān)于算法說(shuō)法錯(cuò)誤的是（ ）A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問(wèn)題的算法同為該問(wèn)題編寫(xiě)的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個(gè)都是錯(cuò)誤的6. 下面說(shuō)法錯(cuò)誤的是（ ） (1)算法原地工作的含義是指不需要任何額外的輔助空間 （2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法 （3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界 （4）同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3)7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類(lèi)。A動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（ ）。A循環(huán)隊(duì)列 B. 鏈表 C. 哈希表 D. 棧9以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（ ）？ A廣義表 B. 二叉樹(shù) C. 稀疏矩陣 D. 串10以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？（ ）A棧 B. 哈希表 C. 線索樹(shù) D. 雙向鏈表 11線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。 A必須是連續(xù)的 B部分地址必須是連續(xù)的 C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以12在以下的敘述中，正確的是（）。 A線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu) B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表 C棧的操作方式是先進(jìn)先出 D隊(duì)列的操作方式是先進(jìn)后出 13以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類(lèi)型（ ）A棧 B廣義表 C有向圖 D字符串14以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹(shù) B字符串 C隊(duì) D棧15. 下列數(shù)據(jù)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)。A棧 B. 隊(duì)列 C. 完全二叉樹(shù) D. 堆16連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（ ）。A一定連續(xù) B一定不連續(xù) C不一定連續(xù) D部分連續(xù)，部分不連續(xù)17以下屬于邏輯結(jié)構(gòu)的是（ ）。A順序表 B. 哈希表 C.有序表 D. 單鏈表18.一個(gè)數(shù)據(jù)對(duì)象是（ ）的集合。 A.相同類(lèi)型的數(shù)據(jù)項(xiàng) B.相同類(lèi)型的數(shù)據(jù)元素C.不同類(lèi)型的數(shù)據(jù)項(xiàng) D.不同類(lèi)型的數(shù)據(jù)元素19. ( )是數(shù)據(jù)的基本單位。A.數(shù)據(jù)項(xiàng) B.關(guān)鍵字 C.數(shù)據(jù)元素 D.數(shù)據(jù)類(lèi)型 20.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱(chēng)為數(shù)據(jù)( )。 A.對(duì)象 B.的存儲(chǔ)結(jié)構(gòu) C.類(lèi)型 D.元素21.下列程序段的時(shí)間復(fù)雜度為( )。 for(i=0；i<5；i+) for(j=0；j<n；j+) x=x+1； A.O(5) B.O(5+n) C.O(n5 ) D.O(n)22數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的（）以及它們之間的（）和運(yùn)算等的學(xué)科。 A操作對(duì)象 B計(jì)算方法 C邏輯存儲(chǔ) D數(shù)據(jù)映象 A結(jié)構(gòu) B關(guān)系 C運(yùn)算 D算法23數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K，R），其中K是（）的有限集合，R是K上的（）的有限集合。 A算法 B數(shù)據(jù)元素 C數(shù)據(jù)操作 D邏輯結(jié)構(gòu) A操作 B映象 C存儲(chǔ) D關(guān)系24在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。 A動(dòng)態(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)25線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種 （）的存儲(chǔ)結(jié)構(gòu)。 A隨機(jī)存取 B順序存取 C索引存取 D散列存取 26算法分析的目的是（），算法分析的兩個(gè)主要方面是（）。 A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系 C分析算法的效率以求改進(jìn) D分析算法的易懂性和文檔性 A空間復(fù)雜性和時(shí)間復(fù)雜性 B正確性和簡(jiǎn)明性 C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 27計(jì)算機(jī)算法指的是（），它必具備輸入、輸出和（）等五個(gè)特性。A計(jì)算方法 B排序方法 C解決問(wèn)題的有限運(yùn)算序列 D調(diào)度方法A可行性、可移植性和可擴(kuò)充性 B可行性、確定性和有窮性 C確定性、有窮性和穩(wěn)定性 D易讀性、穩(wěn)定性和安全性 28線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說(shuō)法（）。 A正確 B不正確二、填空題1數(shù)據(jù)的物理結(jié)構(gòu)包括 的表示和 的表示。2. 對(duì)于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有 （1） ， （2） ， （3） ，_（4）四種。3數(shù)據(jù)的邏輯結(jié)構(gòu)是指 。4一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中 稱(chēng)為存儲(chǔ)結(jié)構(gòu)。5抽象數(shù)據(jù)類(lèi)型的定義僅取決于它的一組_（1）_，而與_（2）_無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_（3）_不變，都不影響其外部使用。6數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是 7. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_（1）_和_（2）_，以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的_（3）_，設(shè)計(jì)出相應(yīng)的（4）_。8 一個(gè)算法具有5個(gè)特性: （1） 、 （2） 、 （3） ，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。9 下面程序段的時(shí)間復(fù)雜度為_(kāi)。(n>1) sum=1； for (i=0;sum<n;i+) sum+=1; 10計(jì)算機(jī)執(zhí)行下面的語(yǔ)句時(shí)，語(yǔ)句s的執(zhí)行次數(shù)為 _ 。 FOR(i=l；i<n-l；i+) FOR(j=n;j>=i;j-) s; 11.下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是： i：=1； WHILE i<n DO i：=i*2;三、基礎(chǔ)知識(shí)題1數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究什么內(nèi)容的學(xué)科？2數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？3數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類(lèi)型的主要特點(diǎn)是什么？使用抽象數(shù)據(jù)類(lèi)型的主要好處是什么？ 4回答問(wèn)題（每題2分）（1）在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算之間存在著怎樣的關(guān)系？（2）若邏輯結(jié)構(gòu)相同但存儲(chǔ)結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說(shuō)法對(duì)嗎？舉例說(shuō)明之。（3）在給定的邏輯結(jié)構(gòu)及其存儲(chǔ)表示上可以定義不同的運(yùn)算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說(shuō)法對(duì)嗎？舉例說(shuō)明之。（4）評(píng)價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？5評(píng)價(jià)一個(gè)好的算法，您是從哪幾方面來(lái)考慮的？6解釋和比較以下各組概念抽象數(shù)據(jù)類(lèi)型及數(shù)據(jù)類(lèi)型 數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)抽象數(shù)據(jù)類(lèi)型算法的時(shí)間復(fù)雜性（5） 算法（6）頻度7. 根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪幾類(lèi)基本的數(shù)據(jù)結(jié)構(gòu)？8對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個(gè)方面的討論？9. 當(dāng)你為解決某一問(wèn)題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮？10. 若將數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)二元組（D，R）,說(shuō)明符號(hào)D，R 應(yīng)分別表示什么？11數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類(lèi)型有什么區(qū)別？12數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪四種基本的存儲(chǔ)方法實(shí)現(xiàn)？ 13若有100個(gè)學(xué)生，每個(gè)學(xué)生有學(xué)號(hào)，姓名，平均成績(jī)，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，寫(xiě)出這些結(jié)構(gòu)？14. 運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉一例，說(shuō)明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同，只是對(duì)于運(yùn)算的定義不同。因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性，是兩個(gè)不同的結(jié)構(gòu)。15. 在編制管理通訊錄的程序時(shí), 什么樣的數(shù)據(jù)結(jié)構(gòu)合適? 為什么?16. 試舉一例，說(shuō)明對(duì)相同的邏輯結(jié)構(gòu),同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率不同。17. 有實(shí)現(xiàn)同一功能的兩個(gè)算法A1和A2，其中A1的時(shí)間復(fù)雜度為T(mén)l=O(2n)，A2的時(shí)間復(fù)雜度為T(mén)2=O(n2)，僅就時(shí)間復(fù)雜度而言，請(qǐng)具體分析這兩個(gè)算法哪一個(gè)好。18設(shè)計(jì)一數(shù)據(jù)結(jié)構(gòu)，用來(lái)表示某一銀行儲(chǔ)戶(hù)的基本信息： 賬號(hào)、姓名、開(kāi)戶(hù)年月日、儲(chǔ)蓄類(lèi)型、存入累加數(shù)、利息、帳面總數(shù)。第二章 線性表一 、 選擇題1下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（ ）A 存儲(chǔ)密度大 B插入運(yùn)算方便 B C刪除運(yùn)算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示2下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ ）A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3線性表是具有n個(gè)（ ）的有限序列（n>0）。 A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項(xiàng) E信息項(xiàng)4若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表5某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用( )最節(jié)省時(shí)間。A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表7若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表8. 靜態(tài)鏈表中指針表示的是（ ）. A 內(nèi)存地址 B數(shù)組下標(biāo) C下一元素地址 D左、右孩子地址9. 鏈表不具有的特點(diǎn)是（ ） A插入、刪除不需要移動(dòng)元素 B可隨機(jī)訪問(wèn)任一元素 C不必事先估計(jì)存儲(chǔ)空間 D所需空間與線性長(zhǎng)度成正比10. 下面的敘述不正確的是（ ）A線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比 B. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)C. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i 的值成正比D. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)11 雙向鏈表中有兩個(gè)指針域，llink和rlink分別指向前趨及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，現(xiàn)要求刪去p所指結(jié)點(diǎn)，則正確的刪除是（ ）（鏈中結(jié)點(diǎn)數(shù)大于2，p不是第一個(gè)結(jié)點(diǎn)）Ap.llink.rlink:=p.llink; p.llink.rlink:=p.rlink; dispose(p);Bdispose(p); p.llink.rlink:=p.llink; p.llink,rlink:=p.rlink;Cp.llink.rlink:=p.llink; dispose(p); p.llink.rlink:=p.rlink;D以上A，B，C都不對(duì)。12.(1) 靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元素的時(shí)間與i無(wú)關(guān)。 (2) 靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。 (3) 靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類(lèi)似，不需做元素的移動(dòng)。以上錯(cuò)誤的是（ ） A（1），（2） B（1） C（1），（2）,(3) D.（2）13. 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ ）(1<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2) 14. 對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)15線性表（ a1,a2,an）以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為（ ）AO（i） BO（1） CO（n） DO（i-1）16非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿(mǎn)足（ ）。Ap.link=head Bp.link=NIL Cp=NIL Dp= head17循環(huán)鏈表H的尾結(jié)點(diǎn)P的特點(diǎn)是（ ）。 AP.NEXT:=H BP.NEXT:= H.NEXT CP:=H DP:=H.NEXT18在一個(gè)以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是（） A. p.next=h B. p.next=NIL C. p.next.next=h D. p.data=-119完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作是（ ）； A p.next:=s ; s.priou:=p; p.next.priou:=s ; s.next:=p.next;B p.next.priou:=s; p.next:=s; s.priou:=p; s.next:=p.next;C s.priou:=p; s.next:=p.next; p.next:=s; p.next.priou:=s ;D s.priou:=p; s.next:=p.next; p.next.priou:=s ; p.next:=s;20在雙向循環(huán)鏈表中,在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q所指向的新結(jié)點(diǎn),其修改指針的操作是( )。注:雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(llink,data,rlink)。 供選擇的答案：A p.llink：=q； q.rlink：=p； p.llink.rlink：=q；q.llink：=q；B p.llink：=q； p.llink.rlink：=q ； q.rlink：= p； q.llink:=p.llink；C q.rlink：=p； q.llink：=p.llink； p.llink.rlink：=q; p.llink：=q;D q.llink:=p.llink；q.rlink:=p； p.llink：=q；p.llink：=q； 21在非空雙向循環(huán)鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指的鏈結(jié)點(diǎn)的過(guò)程依次為:rlink(p) q; llink(p) llink(q); llink(q) p; （ ） Arlink(q) p Brlink(llink(q) p Crlink(llink(p) p Drlink(rlink(p) p 22 雙向鏈表中有兩個(gè)指針域，llink和rlink，分別指回前驅(qū)及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為（ ） A. p.llink:=q; q.rlink:=p; p.llink.rlink:=q; q.llink:=p.llink;B. q.llink:=p.llink; p.llink.rlink:=q; q.rlink:=p; p.llink:=q.rlink; C. q.rlink:=p; p.rlink:=q; p.llink.rlink:=q; q.rlink:=p;D. p.llink.rlink:=q; q.rlink:=p; q.llink:=p.llink; p.llink:=q;23在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是（ ）。A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;24在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：（ ）。Ap->next=s;s->next=p->next; B s->next=p->next;p->next=s;Cp->next=s;p->next=s->next; D p->next=s->next;p->next=s;25對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL26. 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。A (p.llink).rlink:=p.rlink (p.rlink).llink:=p.llink;B p.llink:=(p.llink).llink (p.llink).rlink:=p;C (p.rlink).llink:=p p.rlink:=(p.rlink).rlinkD p.rlink:=(p.llink).llink p.llink:=(p.rlink).rlink; 二、填空題1當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_存儲(chǔ)結(jié)構(gòu)。2線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_。3設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn) , 若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語(yǔ)句:_； _;4在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。5在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_。6對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi),在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)。7根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成_和_；而又根據(jù)指針的連接方式，鏈表又可分成_和_。8在雙向循環(huán)鏈表中,向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是_、_、_、_。9在雙向鏈表結(jié)構(gòu)中，若要求在p 指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句：s .next:=p； s .prior:= _；p .prior:=s；_:=s；10.鏈接存儲(chǔ)的特點(diǎn)是利用_來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。11.順序存儲(chǔ)結(jié)構(gòu)是通過(guò)_表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)_表示元素之間的關(guān)系的。12. 對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共 _個(gè)，單鏈 表為_(kāi)個(gè)。13. 循環(huán)單鏈表的最大優(yōu)點(diǎn)是：_。14. 已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語(yǔ)句是：_15. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是：_16. 在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：_ 17.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是：_。18. 在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是：_。 三、解答題1線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)：（1）如果有 n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？ 為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？ 2線性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，在作插入或刪除操作時(shí)，需移動(dòng)大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一定都能夠克服上述三個(gè)弱點(diǎn)，試討論之。3若較頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)？為什么？4線性結(jié)構(gòu)包括_、_、_和_。線性表的存儲(chǔ)結(jié)構(gòu)分成_和_。請(qǐng)用類(lèi)PASCL語(yǔ)言描述這兩種結(jié)構(gòu)。5線性表（a1，a2，an）用順序映射表示時(shí)，ai和ai+1（1<=i<n）的物理位置相鄰嗎？鏈接表示時(shí)呢？ 6. 說(shuō)明在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針與頭結(jié)點(diǎn)之間的根本區(qū)別；頭結(jié)點(diǎn)與首元結(jié)點(diǎn)的關(guān)系。7. 試述頭結(jié)點(diǎn),首元結(jié)點(diǎn),頭指針這三個(gè)概念的區(qū)別. 8有線性表(a1,a2,an),采用單鏈表存儲(chǔ)，頭指針為H，每個(gè)結(jié)點(diǎn)中存放線性表中一個(gè)元素，現(xiàn)查找某個(gè)元素值等于X的結(jié)點(diǎn)。分別寫(xiě)出下面三種情況的查找語(yǔ)句。要求時(shí)間盡量少。（1）線性表中元素?zé)o序。（2）線性表中元素按遞增有序。 （3）線性表中元素按遞減有序。9. 在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到任何一個(gè)結(jié)點(diǎn)?10. 如何通過(guò)改鏈的方法，把一個(gè)單向鏈表變成一個(gè)與原來(lái)鏈接方向相反的單向鏈表？11. 設(shè)單鏈表結(jié)點(diǎn)指針域?yàn)閚ext，試寫(xiě)出刪除鏈表中指針p所指結(jié)點(diǎn)的直接后繼的C語(yǔ)言語(yǔ)句。12. 設(shè)單鏈表中某指針p所指結(jié)點(diǎn)（即p結(jié)點(diǎn)）的數(shù)據(jù)域?yàn)閐ata，鏈指針域?yàn)閚ext，請(qǐng)寫(xiě)出在p結(jié)點(diǎn)之前插入s結(jié)點(diǎn)的操作（PASCAL語(yǔ)句）。 四、算法設(shè)計(jì)題1 假設(shè)有兩個(gè)按元素值遞增次序排列的線性表，均以單鏈表形式存儲(chǔ)。請(qǐng)編寫(xiě)算法將這兩個(gè)單鏈表歸并為一個(gè)按元素值遞減次序排列的單鏈表，并要求利用原來(lái)兩個(gè)單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。2. 知L1、L2分別為兩循環(huán)單鏈表的頭結(jié)點(diǎn)指針，m,n分別為L(zhǎng)1、L2表中數(shù)據(jù)結(jié)點(diǎn)個(gè)數(shù)。要求設(shè)計(jì)一算法，用最快速度將兩表合并成一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表。3在帶頭結(jié)點(diǎn)的單鏈表上，給出求表長(zhǎng)Length(L)的算法，并加入簡(jiǎn)要的注釋或說(shuō)明。4設(shè)單鏈表具有頭結(jié)點(diǎn)，且表中元素各不相同，試給出在單鏈表中查找值為"x"的結(jié)點(diǎn)的算法，并加入簡(jiǎn)要的注釋或說(shuō)明。5設(shè)單鏈表具有頭結(jié)點(diǎn)，且表中元素各不相同，試給出在單鏈表中刪除值為"x"的結(jié)點(diǎn)的算法。第三章 棧和隊(duì)列一、 選擇題1. 對(duì)于棧操作數(shù)據(jù)的原則是（ ）。A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序2. 在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否( ),在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否( )。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為( )。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的 ( )分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)( )時(shí)，才產(chǎn)生上溢。 , : A. 空 B. 滿(mǎn) C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 長(zhǎng)度 B. 深度 C. 棧頂 D. 棧底 : A. 兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn).B. 其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn). C. 兩個(gè)棧的棧頂在?？臻g的某一位置相遇. D. 兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底.3. 一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）個(gè)元素是（ ）。A. 不確定 B. n-i+1 C. i D. n-i4. 若一個(gè)棧的輸入序列為1,2,3,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不確定的5. 若已知一個(gè)棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN是n，則pi是( )。 A. i B. n-i C. n-i+1 D. 不確定6. 有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（ ）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 7. 設(shè)棧的輸入序列是1，2，3，4,則（ ）不可能是其出棧序列。A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4，8. 一個(gè)棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 29. 設(shè)一個(gè)棧的輸入序列是 1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（ ）。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 410. 某堆棧的輸入序列為a, b，c ，d,下面的四個(gè)序列中，不可能是它的輸出序列的是（ ）。A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b11. 設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作,則下面得不到的序列為（ ）。Afedcba B. bcafed C. dcefba D. cabdef12. 設(shè)有三個(gè)元素X，Y，Z順序進(jìn)棧（進(jìn)的過(guò)程中允許出棧），下列得不到的出棧排列是( )。AXYZ B. YZX C. ZXY D. ZYX13. 輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為（ ）A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop14. 若一個(gè)棧以向量V1.n存儲(chǔ)，初始棧頂指針top為n+1，則下面x進(jìn)棧的正確操作是( )。Atop:=top+1; V top:=x B. V top:=x; top:=top+1 C. top:=top-1; V top:=x D. V top:=x; top:=top-115. 若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1.m，topi代表第i個(gè)棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿(mǎn)的條件是（ ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top216. 棧在（ ）中應(yīng)用。A. 遞歸調(diào)用 B. 子程序調(diào)用 C. 表達(dá)式求值 D. A，17. 一個(gè)遞歸算法必須包括（ ）。A. 遞歸部分 B. 終止條件和遞歸部分 C. 迭代部分 D.終止條件和迭代部分18. 執(zhí)行完下列語(yǔ)句段后，i值為：（ ） int f(int x) return (x>0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 無(wú)限遞歸19. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是( )。Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd20. 表達(dá)式3* 2(4+2*2-6*3)-5求值過(guò)程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（ ），其中為乘冪 。A. 3,2,4,1,1；(*(+*- B. 3,2,8；(*- C. 3,2,4,2,2；(*(- D. 3,2,8；(*(-21. 設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲(chǔ)結(jié)構(gòu) B. 隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧22. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（ ）。A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改23. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)( )。A僅修改隊(duì)頭指針 B. 僅修改隊(duì)尾指針 C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭,隊(duì)尾指針都可能要修改24. 遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱(chēng)為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D. 線性表25. 假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m26. 循環(huán)隊(duì)列A0.m-1存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是( )。A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front27. 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 28. 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 29. 已知輸入序列為abcd 經(jīng)過(guò)輸出受限的雙向隊(duì)列后能得到的輸出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不對(duì) 30. 若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是( )。A. 1234 B. 4132 C. 4231 D. 4213 31. 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front32. 棧和隊(duì)列的共同點(diǎn)是（ ）。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)33. 棧的特點(diǎn)是（ ）,隊(duì)列的特點(diǎn)是（ ）,棧和隊(duì)列都是（ ）。若進(jìn)棧序列為1,2,3,4 則（ ）不可能是一個(gè)出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為1,2,3,4 則（ ）是一個(gè)出隊(duì)列序列。, : A. 先進(jìn)先出 B. 后進(jìn)先出 C. 進(jìn)優(yōu)于出 D. 出優(yōu)于進(jìn): A.順序存儲(chǔ)的線性結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu) C.限制存取點(diǎn)的線性結(jié)構(gòu) D.限制存取點(diǎn)的非線性結(jié)構(gòu), : A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,434. 棧和隊(duì)都是（ ）A順序存儲(chǔ)的線性結(jié)構(gòu) B. 鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)C. 限制存取點(diǎn)的線性結(jié)構(gòu) D. 限制存取點(diǎn)的非線性結(jié)構(gòu)35. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應(yīng)該是( )。A 6 B. 4 C. 3 D. 236. 用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（ ）位置。A鏈頭 B鏈尾 C鏈中37. 依次讀入數(shù)據(jù)元素序列a，b，c，d，e，f，g進(jìn)棧,每進(jìn)一個(gè)元素，機(jī)器可要求下一個(gè)元素進(jìn)?；驈棗?，如此進(jìn)行，則?？諘r(shí)彈出的元素構(gòu)成的序列是以下哪些序列？ Ad ，e，c，f，b，g，a B. f，e，g，d，a，c，bC. e，f，d，g，b，c，a D. c，d，b，e，f，a，g二、填空題 1棧是_的線性表，其運(yùn)算遵循_的原則。2_是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3. 一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是_。4. 設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過(guò)PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_，而棧頂指針值是_H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。5. 當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top1與top2，則當(dāng)棧1空時(shí)，top1為_(kāi)，棧2空時(shí) ，top2為_(kāi)，棧滿(mǎn)時(shí)為_(kāi)。6兩個(gè)棧共享空間時(shí)棧滿(mǎn)的條件_。7在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否_(1)_;在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否_(2)_；當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為_(kāi)(3)_。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的空間時(shí)，應(yīng)將兩棧的_(4)_分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_(5)_時(shí)才產(chǎn)生溢出。8. 多個(gè)棧共存時(shí)，最好用_作為存儲(chǔ)結(jié)構(gòu)。9用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_(kāi)。10. 順序棧用data1.n存儲(chǔ)數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_。11表達(dá)式23+(12*3-2)/4+34*5/7)+108/9的后綴表達(dá)式是_。12. 循環(huán)隊(duì)列的引入，目的是為了克服_。 13用下標(biāo)0開(kāi)始的N元數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，為實(shí)現(xiàn)下標(biāo)變量M加1后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)， M= _。14_又稱(chēng)作先進(jìn)先出表。15. 隊(duì)列的特點(diǎn)是_。16隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是_。17. 已知鏈隊(duì)列的頭尾指針?lè)謩e是f和r，則將值x入隊(duì)的操作序列是_。18區(qū)分循環(huán)隊(duì)列的滿(mǎn)與空，只有兩種方法，它們是_和_。19設(shè)循環(huán)隊(duì)列用數(shù)組A1.M表示，隊(duì)首、隊(duì)尾指針?lè)謩e是FRONT和TAIL，判定隊(duì)滿(mǎn)的條件為_(kāi)。20. 設(shè)循環(huán)隊(duì)列存放在向量sq.data0:M中，則隊(duì)頭指針sq.front在循環(huán)意義下的出隊(duì)操作可表示為_(kāi)，若用犧牲一個(gè)單元的辦法來(lái)區(qū)分隊(duì)滿(mǎn)和隊(duì)空（設(shè)隊(duì)尾指針sq.rear）,則隊(duì)滿(mǎn)的條件為_(kāi)。三、基礎(chǔ)知識(shí)題1名詞解釋?zhuān)簵！?名詞解釋?zhuān)宏?duì)列3什么是循環(huán)隊(duì)列？4假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。（1）試指出判別給定序列是否合法的一般規(guī)則。（2）兩個(gè)不同合法序列（對(duì)同一輸入序列）能否得到相同的輸出元素序列？如能得到，請(qǐng)舉列說(shuō)明。5. 有5 個(gè)元素，其入棧次序?yàn)椋篈，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個(gè)且D第二個(gè)出棧）的次序有哪幾個(gè)？ 6.如果輸入序列為1 2 3 4 5 6,試問(wèn)能否通過(guò)棧結(jié)構(gòu)得到以下兩個(gè)序列:4 3 5 6 1 2和1 3 5 4 2 6;請(qǐng)說(shuō)明為什么不能或如何才能得到。7. 若元素的進(jìn)棧序列為：A、B、C、D、E，運(yùn)用棧操作，能否得到出棧序列B、C、A、E、D 和D、B、A、C、E？為什么？8. 設(shè)輸入序列為a,b,c,d,試寫(xiě)出借助一個(gè)?？傻玫降膬蓚€(gè)輸出序列和兩個(gè)不能得到的輸出序列。9. 設(shè)輸入序列為2，3，4，5，6，利用一個(gè)棧能得到序列2，5，3，4，6嗎？?？梢杂脝捂湵韺?shí)現(xiàn)嗎？10. 試證明：若借助棧由輸入序列1,2,n得到輸出序列為P1,P2,Pn（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k,使Pj<Pk<Pi。11. 設(shè)一數(shù)列的輸入順序?yàn)?23456，若采用堆棧結(jié)構(gòu)，并以A和D分別表示入棧和出棧操作，試問(wèn)通過(guò)入出棧操作的合法序列。能否得到輸出順序?yàn)?25641的序列。能否得到輸出順序?yàn)?54623的序列。12.（1） 什么是遞歸程序？ （2） 遞歸程序的優(yōu)、缺點(diǎn)是什么？ （3） 遞歸程序在執(zhí)行時(shí)，應(yīng)借助于什么來(lái)完成？（4） 遞歸程序的入口語(yǔ)句、出口語(yǔ)句一般用什么語(yǔ)句實(shí)現(xiàn)？ 13. 在一個(gè)算法中需要建立多個(gè)堆棧時(shí)可以選用下列三種方案之一，試問(wèn)：這三種方案之間相比較各有什么優(yōu)缺點(diǎn)？（1）分別用多個(gè)順序存儲(chǔ)空間建立多個(gè)獨(dú)立的堆棧；（2）多個(gè)堆棧共享一個(gè)順序存儲(chǔ)空間；（3）分別建立多個(gè)獨(dú)立的鏈接堆棧。14在某程序中，有兩個(gè)棧共享一個(gè)一維數(shù)組空間SPACEN、SPACE0、SPACEN-1 分別是兩個(gè)棧的棧底。（1）對(duì)棧1、棧2，試分別寫(xiě)出（元素x）入棧的主要語(yǔ)句和出棧的主要語(yǔ)句。（2）對(duì)棧1、棧2，試分別寫(xiě)出棧滿(mǎn)、?？盏臈l件。15. 簡(jiǎn)述順序存儲(chǔ)隊(duì)列的假溢出的避免方法及隊(duì)列滿(mǎn)和空的條件。16. 舉例說(shuō)明順序隊(duì)的“假溢出”現(xiàn)象，并給出解決方案。17. 怎樣判定循環(huán)隊(duì)列的空和滿(mǎn)？18. 簡(jiǎn)要敘述循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，并寫(xiě)出其初始狀態(tài)、隊(duì)列空、隊(duì)列滿(mǎn)時(shí)的隊(duì)首指針與隊(duì)尾指針的值。 四、算法設(shè)計(jì)1假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫(xiě)相應(yīng)的初始化隊(duì)列、入隊(duì)列和出隊(duì)列算法。2借助棧(可用棧的基本運(yùn)算)來(lái)實(shí)現(xiàn)單鏈表的逆置運(yùn)算。3假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三中括號(hào)：圓括號(hào)“（”和“）”，方括號(hào)“”和“”以及花括號(hào)與“”和“”，且這三種括號(hào)可按任意的次序嵌套試用，如（. . . . . . . .( . . . .)。試?yán)脳５倪\(yùn)算編寫(xiě)判斷給定表達(dá)式中所含括號(hào)是否正確 配對(duì)出現(xiàn)的算法（可設(shè)表達(dá)式已存入字符型數(shù)組中）。第四章 串一、選擇題1下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（ ）A 串是字符的有限序列 B空串是由空格構(gòu)成的串C 模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)2 .若串S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,執(zhí)行concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)其結(jié)果為（ ）AABC#G0123 BABCD#2345 CABC#G2345 DABC#2345EABC#G1234 FABCD#1234 GABC#012343設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱(chēng)為（ ）A求子串 B聯(lián)接 C匹配 D求串長(zhǎng)4已知串S=aaab,其N(xiāo)ext數(shù)組值為（ ）。A0123 B1123 C1231 D12115串 ababaaababaa 的next數(shù)組為（ ）。A012345678999 B012121111212 C011234223456 D01230123223456字符串a(chǎn)babaabab 的nextval 為（ ）A(0,1,0,1,04,1,0,1) B(0,1,0,1,0,2,1,0,1)C(0,1,0,1,0,0,0,1,1) D(0,1,0,1,0,1,0,1,1 )7模式串t=abcaabbcabcaabdab，該模式串的next數(shù)組的值為（ ），nextval數(shù)組的值為 （ ）。