數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

1、一、 。選擇題。1.算法計(jì)算量的大小稱為算法的（ B ）。A、效率 B、復(fù)雜性 C、現(xiàn)實(shí)性 D、難度2.以下數(shù)據(jù)結(jié)構(gòu)中，（ B ）不是線性結(jié)構(gòu)。A、廣義表 B、二叉樹 C、稀疏矩陣 D、串3、下面程序段中，對(duì)x賦值語(yǔ)句的語(yǔ)句頻度為（ C ）。for(i=1;i<=n;i+)for(j=1;j<=n;j+) x=x+1;A、2n B、n C、n2 D、log2n4.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是（ D ）。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：插入或刪除元素方便，存儲(chǔ)密度<1, 空間利用率極低。存儲(chǔ)空間分為兩部分，一部分 結(jié)點(diǎn)值，結(jié)點(diǎn)間關(guān)系的指針。按元素序號(hào)訪問(wèn)，查找方便。順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：存

2、儲(chǔ)單元的地址相連，存儲(chǔ)的密度大=1，空間利用率高，但插入刪除時(shí)需移動(dòng)元素，不方便，靜態(tài)分配，需預(yù)先分配空間A、便于隨機(jī)存取 （順序） B、存儲(chǔ)密度高 （順序）C、無(wú)須預(yù)分配空間 D、便于進(jìn)行插入和刪除操作5.假設(shè)順序表中每一個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，且第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為100，則第8個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為（ D ）。A、106 B、107 C、124 D、1286.若線性表中經(jīng)常要存取第i個(gè)數(shù)據(jù)元素及其前趨，則宜采用（ A）存儲(chǔ)方式。A、順序表 B、帶頭結(jié)點(diǎn)的單鏈表 C、不帶頭結(jié)點(diǎn)的單鏈表 D、循環(huán)單鏈表7.在單鏈表中若經(jīng)常要?jiǎng)h除表中最后一個(gè)結(jié)點(diǎn)或在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，則宜

3、采用（ C ）存儲(chǔ)方式。A、順序表 B、用頭指針標(biāo)識(shí)的循環(huán)單鏈表 C、用尾指針標(biāo)識(shí)的循環(huán)單鏈表 D、雙向鏈表8.在一個(gè)單鏈表中的p和q兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)s，則修改鏈接的語(yǔ)句為（ ）。A、s->next=p; q->next=s; B、p->next=s->next; s->next=p;C、q->next=s->next; s->next=p; D、p->next=s; s->next=q;9.在一個(gè)長(zhǎng)度為n的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，使單鏈表仍然保持有序的算法的時(shí)間復(fù)雜度是（ C ）。A、O(1) B、O(long2n)

4、C、O(n) D、O(n2)10.要將一個(gè)順序表（a0，a1，an-1）中的數(shù)據(jù)元素ai（0<=i<=n-1）刪除，需要移動(dòng)（ C ）個(gè)數(shù)據(jù)元素。A、i B、n-i-1 C、n-i D、n-i+111.在棧中存取數(shù)據(jù)的原則是（ B ）。A、先進(jìn)先出 B、先進(jìn)后出 C、后進(jìn)先出 D、沒(méi)有限制12.若將整數(shù)1,2,3,4依次進(jìn)棧，則不可能得到的出棧序列是（ D）。A、1234 B、1324 C、4321 D、142313.在鏈棧中進(jìn)行出棧操作時(shí)（ B ）。A、需要判斷棧是否滿 B、需要判斷棧是否空 C、需要判斷棧元素的類型 D、無(wú)須對(duì)棧做任何判斷將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸，使用 棧

5、保存中間結(jié)果14.在順序棧中，若棧頂指針top指向棧頂元素的下一個(gè)存儲(chǔ)單元，且順序棧的最大容量是maxsize,則順序棧的判空條件是（ B ）。A、top=0 B、top=-1 C、top=maxsize D、top=maxsize-115. 在順序棧中，若棧頂指針top指向棧頂元素的下一個(gè)存儲(chǔ)單元，且順序棧的最大容量是maxsize,則順序棧的判滿條件是（ D ）。A、top=0 B、top=-1 C、top=maxsize D、top=maxsize-116.在隊(duì)列中存取數(shù)據(jù)元素的原則是（ A ）。A、先進(jìn)先出 B、先進(jìn)后出 C、后進(jìn)后出 D、沒(méi)有限制17.在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)

6、存儲(chǔ)單元的方法來(lái)區(qū)分判斷隊(duì)滿和隊(duì)空的條件，front和rear分別為隊(duì)頭和隊(duì)尾指針，他們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxsize，則隊(duì)列的判空條件是（ A ）。A、front=rear B、front!=rear C、front=rear +1 D、front=(rear+1)%maxsize18. 在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分判斷隊(duì)滿和隊(duì)空的條件，front和rear分別為隊(duì)頭和隊(duì)尾指針，他們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxsize，則隊(duì)列的判滿條件是（ D ）。A、front=rear B、

7、front!=rear C、front=rear +1 D、front=(rear+1)%maxsize19. 在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分判斷隊(duì)滿和隊(duì)空的條件，front和rear=-為隊(duì)頭和隊(duì)尾指針，他們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxsize，則隊(duì)列的長(zhǎng)度是（ C ）。A、rear- front B、rear- front+1 C、(rear- front+maxsize)%maxsize D、(rear- front+1)%maxsize20設(shè)長(zhǎng)度為n的鏈隊(duì)列采用單循環(huán)鏈表表示，若只設(shè)一個(gè)頭指針指向隊(duì)首元素，則入隊(duì)操作的時(shí)間

8、復(fù)雜度為（ B ）。A、O(1) B、O(n) C、O(long2n) D、O(n2)21.下面關(guān)于串的敘述中，（B）是不正確的。A、模式匹配是串的一種重要運(yùn)算 B、空串是由空格構(gòu)成的串C、串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ) D、串是字符的有限序列22.串是一種特殊的線性表，其特殊性體現(xiàn)在（ D ）。A、可以順序存儲(chǔ) B、數(shù)據(jù)元素是一個(gè)字符C、可以鏈?zhǔn)酱鎯?chǔ) D、數(shù)據(jù)元素可以是多個(gè)字符23.串的長(zhǎng)度是指（ B ）。A、串中所含不同字母的個(gè)數(shù) B、串中所含字符的個(gè)數(shù)C、串中所含不同字符的個(gè)數(shù) D、串中所含非空格字符的個(gè)數(shù)24.設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法

9、稱為（ C ）。A、求子串 B、連接 C、模式匹配 D、求串長(zhǎng)25.若串S=software，其子串的個(gè)數(shù)是（ A ）。A、8 B、37 C、36 D、926.常對(duì)數(shù)組進(jìn)行的兩種操作是（ C ）。順序存儲(chǔ)A、建立與刪除 B、索引與修改 C、查找與修改 D、查找與索引27.數(shù)組A05，06的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先的次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A5，5的地址是（ A ）。A、1175 B、1180 C、1205 D、121028.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是（ C ）。A、便于進(jìn)行矩陣運(yùn)算 （缺點(diǎn) ） B、便于輸入和輸出 （缺點(diǎn) ）C、節(jié)省存儲(chǔ)空間 D、降低運(yùn)算的時(shí)

10、間復(fù)雜度 （缺點(diǎn) ）29.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（ B ）的線性表。A、散列存儲(chǔ) B、順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C、壓縮存儲(chǔ) D、索引存儲(chǔ)30.若查找每個(gè)記錄的概率相等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為（ B ）。A、(n-1)/2 B、n/2 C、(n+1)/2 D、n31.適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（ D ）。A、鏈表方式存儲(chǔ)，元素?zé)o序 B、鏈表方式存儲(chǔ)，元素有序C、順序方式存儲(chǔ)，元素?zé)o序 D、順序方式存儲(chǔ)，元素有序32.當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度（ ）。

11、A、必定快 B、不一定快C、在大多數(shù)情況下要快 D、取決于表遞增還是遞減33.樹形結(jié)構(gòu)是指元素之間存在一種（ D ）。A、一對(duì)一關(guān)系 B、多對(duì)多關(guān)系 C、多對(duì)一關(guān)系 D、一對(duì)多關(guān)系34.在一棵二叉樹上第四層的結(jié)點(diǎn)數(shù)最多為（ D ）。第i層至多有 2i-1個(gè)節(jié)點(diǎn)A、2 B、4 C、6 D、835.一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為（ A ）。A、2k-1 B、2k-1 C、2k+1 D、2k36.一棵深度為k的完全二叉樹的最少結(jié)點(diǎn)數(shù)為（ A ）。A、2k-1 B、2k-1 C、2k+1 D、2k37.一棵深度為k的完全二叉樹的最多結(jié)點(diǎn)數(shù)為（ A ）。A、2k-1 B、2k-1 C、2k+1 D、

12、2k38.樹最適合用來(lái)表示（ B ）。A、有序數(shù)據(jù)元素 B、元素之間具有層次關(guān)系的數(shù)據(jù)C、無(wú)序數(shù)據(jù)元素 D、元素之間無(wú)聯(lián)系的數(shù)據(jù)39.設(shè)森林F中有3棵樹，其中樹的結(jié)點(diǎn)數(shù)依次為M1，M2，M3，則與F對(duì)應(yīng)的二叉樹的根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)數(shù)為（ D ）。A、M1 B、M1+M2 C、M3 D、M2+M340.討論樹、森林和二叉樹的關(guān)系，是為了（ B ）。A、借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)樹的一些運(yùn)算B、將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)C、將樹、森林轉(zhuǎn)換為二叉樹D、體現(xiàn)一種技巧，沒(méi)有什么實(shí)際意義41.一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ C ）。A、250 B、500 C、50

13、1 D、50542下列說(shuō)法中正確的是（ D ）。A、任何一個(gè)二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2B、任何一個(gè)二叉樹中每個(gè)結(jié)點(diǎn)的度都可以大于2 最大是2C、任何一個(gè)二叉樹中結(jié)點(diǎn)的度均為2D、任何一個(gè)二叉樹中結(jié)點(diǎn)的度可以小于243在下列情況中，可稱為二叉樹的是（ C ）。A、每個(gè)結(jié)點(diǎn)至多有兩棵子樹的樹B、每個(gè)結(jié)點(diǎn)只有一棵左子樹的樹C、每個(gè)結(jié)點(diǎn)至多有兩棵子樹的有序樹D、每個(gè)結(jié)點(diǎn)只有一棵右子樹的樹44.下面幾組編碼集合中，不是前綴編碼的是（ ）。A、0，10，110，1111 B、11，10，001，101，0001C、00，010，0110，1000 D、b，c，aa，ac，aba，abb，abc45.

14、圖中有關(guān)路徑的定義是（ A ）。A、由頂點(diǎn)和相鄰頂點(diǎn)構(gòu)成的邊所形成的序列B、由不同頂點(diǎn)所形成的序列C、由不同邊所形成的序列D、上述定義都不是帶權(quán)路徑長(zhǎng)度WPL=權(quán)值i*路徑長(zhǎng)度l完全二叉樹的路徑長(zhǎng)度=46.以下說(shuō)法正確的是（ B ）。A、連通分量是無(wú)向圖中的極小連通子圖B、強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖C、在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧<a,b>D、對(duì)有向圖G，如果從任意頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問(wèn)到每個(gè)頂點(diǎn)，則該圖一定是完全圖47.要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（ A ）條弧。A、n-1 B、n C、n+1 D、2n4

15、8.( B )的鄰接矩陣是對(duì)稱矩陣。A、有向圖 B、無(wú)向圖 C、AOV網(wǎng) D、AOE網(wǎng)49.以下說(shuō)法不正確的是（ C ）。A、圖的遍歷是從給定的源點(diǎn)出發(fā)訪問(wèn)圖中的每一個(gè)頂點(diǎn)且僅訪問(wèn)一次B、圖的遍歷算法有兩種：深度優(yōu)先和廣度優(yōu)先C、圖的深度遍歷不適合用于有向圖D、圖的深度遍歷是一個(gè)遞歸過(guò)程50.在圖采用鄰接表存儲(chǔ)時(shí)求最小生成樹的Prim算法的時(shí)間復(fù)雜度為（ B ）。鄰接矩陣儲(chǔ)存則是C Prim算法的時(shí)間復(fù)雜度是（     o(n*n)   ），適用于求（    稠密 

16、  ）圖的最小生成樹；kruskal算法的時(shí)間復(fù)雜度是（    O（eloge）   ），適用于求（    稀疏  ）圖的最小生成樹。A、O(n) B、O(n+e) C、O(n2) D、O(n3)51.在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（ D ）。有向圖G可拓?fù)渑判虻呐袆e條件是 不存在環(huán)A、G中有弧<Vi，Vj> B、G中有一條Vi到Vj的路徑C、G中沒(méi)有弧<Vi，Vj> D、G中有

17、一條Vj到Vi的路徑52.下列關(guān)于AOE網(wǎng)的敘述中不正確的是（ ）。A、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B、任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C、所有關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提前完成D、某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成AOE網(wǎng)為邊表示活動(dòng) 的 網(wǎng)，是一個(gè)帶權(quán)的（有向圖，其長(zhǎng)度最長(zhǎng)的 路徑 稱為 關(guān)鍵路徑。在AOE網(wǎng) 中，從源點(diǎn)到匯點(diǎn)路徑上各活動(dòng) 時(shí)間總和最長(zhǎng)的 路 徑稱為（ 關(guān)鍵 路徑 ）。 9、AOV網(wǎng)中,結(jié)點(diǎn)表示（ 活動(dòng) ,邊表示（活動(dòng) 時(shí)間的優(yōu)先關(guān)系 ）。AOE網(wǎng)中,結(jié)點(diǎn)表示（事 件 ）,邊表示（ 活動(dòng) 10、在 AOV網(wǎng) 中，存在環(huán)

18、意味著（ 某項(xiàng)活動(dòng)應(yīng)以自己為先決條件 ），這是荒謬的；對(duì)程序 的 數(shù)據(jù) 流圖來(lái)說(shuō)，它表明存在（ 死循環(huán)53.當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為（ B ）。A、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D、數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同54.散列表的平均查找長(zhǎng)度（ A ）。A、與處理沖突方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B、與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C、與處理沖突方法有關(guān)，與表的長(zhǎng)度也有關(guān)D、與處理沖突方法無(wú)關(guān)，與表的長(zhǎng)度也無(wú)

19、關(guān)55.內(nèi)部排序算法的穩(wěn)定性是指( B )。A、該排序算法不允許有相同的關(guān)鍵字記錄B、該排序算法允許有相同的關(guān)鍵字記錄C、平均時(shí)間為O(nlogn)的排序算法D、以上都不對(duì)56.在下列排序算法中，算法（ D ）的時(shí)間復(fù)雜度與初始排序序列無(wú)關(guān)。A、直接插入排序 B、冒泡排序C、快速排序 D、簡(jiǎn)單選擇排序57.一組記錄的關(guān)鍵字為（46,79,56,38,40,84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)記錄得到的一次劃分結(jié)果為（ C ）。A、（38,40,46,56,79,84） B、（40,38,46,79,56,84）C、（40,38,46,56,79,84） D、（40,38,46,84

20、,56,79）58.對(duì)關(guān)鍵字序列（70,55,100,15,33,65,50,40,95）進(jìn)行直接插入排序時(shí)，把65插入，需要比較（ ）次關(guān)鍵字。A、2 B、3 C、6 D、859.當(dāng)待排序序列基本有序時(shí)，以下排序方法中，（ B ）最不利于其優(yōu)勢(shì)的發(fā)揮。A、直接選擇排序 B、快速排序C、冒泡排序 D、直接插入排序60.在待排序序列局部有序時(shí)，效率最高的排序算法是（ B ）。A、直接選擇排序 B、快速排序C、歸并排序 D、直接插入排序61.若需要利用形式參數(shù)直接訪問(wèn)修改實(shí)參值，則應(yīng)將形參說(shuō)明為（ ）。A、指針 B、值參數(shù) C、局部變量 D、全局變量62.執(zhí)行下面程序段的時(shí)間復(fù)雜度為（ C ）。f

21、or(i=0;i<m;i+)for(j=0;j<n;j+) aij=i*j;A、O(m2) B、O(mn) C、O(n2) D、O(m+n)63.執(zhí)行下面程序段時(shí)，語(yǔ)句S的執(zhí)行次數(shù)為（ D ）。for(i=0;i<=n;i+)for(j=0;j<=i;j+) S;A、n2 B、n2/2 C、n(n+1) D、(n+1)(n+2)/264.為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配的問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要打印輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（ C ）。汽車加油站、模擬打印機(jī)緩沖區(qū)、CPU分時(shí)系統(tǒng)等

22、方面。A、樹 B、棧 C、隊(duì)列 D、圖65.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素a、b、c、d、e、f、g依次進(jìn)入棧S。如果每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序?yàn)閎dcfeag，則棧S的容量至少是（ ）。A、1 B、2 C、3 D、466.某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，元素a、b、c、d、e依次入隊(duì)，則不可能得到的出隊(duì)順序是（ C ）。A、bacde B、dbace C、dbcae D、ecbad二、 填空題。1數(shù)據(jù)的邏輯結(jié)構(gòu)包括（ 線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu) ，存儲(chǔ)結(jié)構(gòu)包括（ 順序存儲(chǔ) ）、（ 鏈接存儲(chǔ) ）、（ 索引存儲(chǔ) ）、（散列存儲(chǔ) ）。2.

23、數(shù)據(jù)結(jié)構(gòu)的主要研究?jī)?nèi)容是（ 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算3.冒泡排序算法的時(shí)間復(fù)雜度是（ n2 ）。4.下面程序段的時(shí)間復(fù)雜度是（ ）。sum=1; for(i=0; sum<n; i+)sum+=1;5.為了便于討論，有時(shí)將含有n(n>=0)個(gè)節(jié)點(diǎn)的線性結(jié)構(gòu)表示成（a1，a2，an），其中每個(gè)ai代表一個(gè)（ ），a1稱為（ ）節(jié)點(diǎn)，an稱為（ ）節(jié)點(diǎn)，i稱為ai在線性表中的（ ）。對(duì)任意一對(duì)相鄰節(jié)點(diǎn)ai，ai+1（1<=i<=n），ai稱為ai+1的（ ），ai+1稱為ai的（ ）。6.線性結(jié)構(gòu)的基本特征是：若至少含有兩個(gè)節(jié)點(diǎn)，則除起始節(jié)點(diǎn)沒(méi)有直接（ 前驅(qū) ）

24、外，其他節(jié)點(diǎn)有且僅有一個(gè)直接（ 直接前驅(qū) ）；除終端節(jié)點(diǎn)沒(méi)有直接（ 后繼 ）外，其他節(jié)點(diǎn)有且僅有一個(gè)直接（ 后繼 ）。7.線性表的常見(jiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有（ 單向鏈表 ）、（ 雙向鏈表 ）、（ 循環(huán)鏈表 ）。8.在順序表（a1，a2，an）的第i（1<=i<=n）個(gè)位置之前插入一個(gè)新的數(shù)據(jù)元素，會(huì)引起（ i/2 ）個(gè)數(shù)據(jù)元素的移動(dòng)操作。9.在線性表的單鏈表存儲(chǔ)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，用于存儲(chǔ)數(shù)據(jù)元素本身；另一個(gè)是（ 結(jié)點(diǎn)指針 ），用于存儲(chǔ)后繼結(jié)點(diǎn)的地址。10.在線性表的順序存儲(chǔ)結(jié)構(gòu)中可實(shí)現(xiàn)快速的隨機(jī)存取，而在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中則只能進(jìn)行（ 插入 ）存取。11.順序表中邏輯上

25、相鄰的數(shù)據(jù)元素，其物理位置（ 一定 ）相鄰，而在單鏈表中邏輯上相鄰的數(shù)據(jù)元素，其物理位置（ 不一定 ）相鄰。12.在含有N個(gè)結(jié)點(diǎn)的單鏈表，若要?jiǎng)h除一個(gè)指定的結(jié)點(diǎn)p則首先必須找到（ 頭指針 ），其時(shí)間復(fù)雜度為（ ）。13.線性表通常采用（ 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ）和（ 順序存儲(chǔ)結(jié)構(gòu) ）兩種存儲(chǔ)結(jié)構(gòu)。若線性表的長(zhǎng)度確定或變化不大，則適合采用（ 順序存儲(chǔ)結(jié)構(gòu) ）進(jìn)行存儲(chǔ)。14.在僅設(shè)置了尾指針的循環(huán)鏈表中，訪問(wèn)第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度（ ）。15.棧是一種操作受限制的特殊線性表，其特殊性體現(xiàn)在插入和刪除操作都限制在表的一端進(jìn)行。允許插入和刪除操作的一端稱為（ ），二另一端稱為（ ）。16.棧有兩種存儲(chǔ)結(jié)構(gòu)，分

26、別是（ ）和（ ）；以這兩種存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的棧分別稱為（ ）和（ ）。17.在不帶頭結(jié)點(diǎn)的鏈棧中，若棧頂指針top直接指向棧頂元素，則將一個(gè)新結(jié)點(diǎn)p入棧時(shí)修改鏈接的語(yǔ)句為（ ）和（ ）。18. 在不帶頭結(jié)點(diǎn)的鏈棧中，若棧頂指針top直接指向棧頂元素，則將棧頂元素出棧時(shí)修改鏈接的語(yǔ)句為（ ）、（ ）和（ ）。19. 隊(duì)列也是一種操作受限制的特殊線性表，與棧不同的是，隊(duì)列中所有的插入操作均限制在表的一端進(jìn)行，而所有的刪除操作都限制在表的另一端進(jìn)行，允許插入的一端稱為（ ），允許刪除的一端稱為（ ）。20.由于隊(duì)列的插入和刪除操作分別在隊(duì)頭和隊(duì)尾進(jìn)行，因此，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中需要設(shè)置兩個(gè)指針?lè)謩e指向（

27、）和（ ），這兩個(gè)指針又分別稱為（ ）和（ ）。21.循環(huán)順序隊(duì)列是將順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的環(huán)，首尾相連的狀態(tài)是通過(guò)數(shù)學(xué)上的（ ）運(yùn)算來(lái)實(shí)現(xiàn)的。22.在循環(huán)順序隊(duì)列中，若規(guī)定當(dāng)front=rear時(shí)，循環(huán)隊(duì)列為空，當(dāng)front=(rear+1)%maxsize時(shí)，循環(huán)隊(duì)列為滿，則入隊(duì)操作時(shí)隊(duì)尾指針變化的相應(yīng)語(yǔ)句為（ ）；出隊(duì)操作時(shí)隊(duì)尾指針變化的相應(yīng)語(yǔ)句為（ ）。23.無(wú)論是順序棧還是順序隊(duì)列，插入元素時(shí)必須先進(jìn)行（ ）判斷，刪除元素時(shí)必須先進(jìn)行（ ）判斷；而鏈?；蜴滉?duì)列中，插入元素不必進(jìn)行?；蜿?duì)列是否為滿的判斷，只要在刪除元素時(shí)先進(jìn)行?；蜿?duì)列是否為空的判斷。24.含零個(gè)字符的串

28、稱為（ ）。任何串中所含（ ）的個(gè)數(shù)稱為該串的長(zhǎng)度。25.當(dāng)且僅當(dāng)兩個(gè)串的（ ）相等并且各個(gè)對(duì)應(yīng)位置上的字符都（ ）時(shí)，這兩個(gè)串相等。一個(gè)串中任意個(gè)連續(xù)字符組成的序列稱為該串的（ ），該串稱為它的所有子串的（ ）。26.通常采用（ ）存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)組。對(duì)二維數(shù)組可有兩種存儲(chǔ)方法：一種是以（ ）為主序的存儲(chǔ)方式，另一種是以（ ）為主序的存儲(chǔ)方式。27.所謂稀疏矩陣是指（ ）。28.在一棵度為m的樹中，如果度為1的結(jié)點(diǎn)有n1個(gè)，度為2的結(jié)點(diǎn)有n2個(gè)，度為m的結(jié)點(diǎn)有nm個(gè)，則這棵樹中的葉子結(jié)點(diǎn)的個(gè)數(shù)為（ ）。29.樹的存儲(chǔ)結(jié)構(gòu)包括（ ）、（ ）和（ ）。30.若一棵完全二叉樹的第4層有7個(gè)節(jié)點(diǎn)，則

29、這棵完全二叉樹的結(jié)點(diǎn)的總數(shù)為（ ）。31.在哈夫曼樹中，任何一個(gè)結(jié)點(diǎn)的度都是（ ）。32.若對(duì)一棵完全二叉樹按層次從0 開(kāi)始進(jìn)行結(jié)點(diǎn)編號(hào)，且每層按從左到右的順序編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0 的結(jié)點(diǎn)存儲(chǔ)到A0中，其余類推，則Ai的左孩子編號(hào)為（ ），右孩子編號(hào)為（ ），雙親編號(hào)為（ ）。33.具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為（ ）。34.在有向圖的鄰接矩陣表示中計(jì)算第i個(gè)頂點(diǎn)入度的方法是（ ）。35.構(gòu)造連通網(wǎng)的最小生成樹的兩個(gè)典型算法是（ ）和（ ）。36.有向圖G可拓?fù)渑判虻呐袆e條件是（ ）。37.AOV網(wǎng)中，頂點(diǎn)表示（ ），弧表示（ ）。AOE網(wǎng)中，頂點(diǎn)表示

30、（ ），弧表示（ ）。38.順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為（ ）次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)最多為（ ）。39.在順序表（8,11,15,19,25,25,30,33,42,48,50）中，用二分法（折半法）查找關(guān)鍵碼值20，需進(jìn)行的關(guān)鍵碼比較次數(shù)為（ ）。40.一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵（ ）樹而變成一個(gè)有序序列，構(gòu)造樹的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。41.執(zhí)行排序操作時(shí)，根據(jù)使用的存儲(chǔ)器可將排序算法分為（ ）和（ ）。42.在對(duì)一組記錄序列（50,40,95,20,15,70,60,45,80）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄6

31、0插入到有序表中時(shí)，為尋找插入位置需比較（ ）次。43.在直接插入排序和直接選擇排序中，若初始序列基本有序，則選用（ ）法效率更高。44.在對(duì)一組記錄序列（50,40,95,20,15,70,60,45,80）進(jìn)行直接選擇排序時(shí)，第4次交換和選擇后，未排序記錄為（ ）。45.n個(gè)記錄的冒泡排序算法所需的最多移動(dòng)次數(shù)為（ ），最少移動(dòng)次數(shù)為（ ）。46.對(duì)n個(gè)結(jié)點(diǎn)進(jìn)行快速排序，最多的比較次數(shù)為（ ）。47.在歸并排序中，若待排序記錄的個(gè)數(shù)為20，則共需要進(jìn)行（ ）趟歸并。48.內(nèi)部排序算法的穩(wěn)定性是指（ ）。49.一棵二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為5，度為2的結(jié)點(diǎn)有3個(gè)，則這棵二叉樹中的葉子結(jié)點(diǎn)的個(gè)

32、數(shù)為（ ）。50.一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)的個(gè)數(shù)為（ ）。51.變量的作用域是指（ ）。52.抽象數(shù)據(jù)類型具有（ ）和（ ）的特點(diǎn)。53.一種抽象類型包括（ ）、（ ）和（ ）。54.在線性結(jié)構(gòu)、樹狀結(jié)構(gòu)和圖結(jié)構(gòu)中，數(shù)據(jù)元素之間分別存在著（ ）、（ ）和（ ）聯(lián)系。55.算法是規(guī)則的有限集合，是為解決特定問(wèn)題而規(guī)定的（ ）。56.算法具有 有窮性/確定性/可行性/輸入/輸出/確定性/和輸出/五大特性。57. 線性表通常采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。在順序表中，線性表的長(zhǎng)度在定義數(shù)組時(shí)就已確定，是（ ）保存；在鏈表中，整個(gè)鏈表由“頭指針”來(lái)指示，單鏈表的長(zhǎng)度是（ ）保存。

33、三、 判斷題。1.給定任意一棵樹都可以找到一棵對(duì)應(yīng)的二叉樹。（ ）2.一棵樹的前序遍歷和后序遍歷序列分別與它的對(duì)應(yīng)二叉樹的前序遍歷和后序遍歷序列是一致的。（ ）3.哈夫曼樹的結(jié)點(diǎn)個(gè)數(shù)不可能是偶數(shù)。（ ）4. 二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值。（ ）5算法就是程序。（ ）6無(wú)向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣不一定是對(duì)稱的。（ ）7一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等。（ ）8. 查找n個(gè)關(guān)鍵字的散列表時(shí)，平均查找長(zhǎng)度與n無(wú)關(guān)。（ ）9由二叉樹的中序表示和前序表示可以導(dǎo)出二叉樹的后序表示。（ ）10線性結(jié)構(gòu)只能用順序結(jié)構(gòu)存

34、放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)存放。（ ）11稀疏矩陣壓縮存儲(chǔ)后，不影響其失去隨機(jī)存取的功能。（ ）12在一個(gè)大根堆中，最小元素不一定在最后。（ ）13對(duì)個(gè)記錄采用快速排序方法進(jìn)行排序，最壞情況下所需時(shí)間復(fù)雜度是O(nlog2n)。（ ） 14如果一個(gè)二叉樹中沒(méi)有度為的結(jié)點(diǎn)，則比為滿二叉樹。（ ）15在高級(jí)語(yǔ)言（如或者PASCAL）中，指針類型是原子類型。（ ）16. 只要還有可用空間，鏈棧和鏈隊(duì)就不會(huì)出現(xiàn)棧滿或隊(duì)滿的情況。（ ）17. 在執(zhí)行某排序算法的過(guò)程中，出現(xiàn)了排序碼朝著與最終排序序列相反方向移動(dòng)的現(xiàn)象，則稱該算法是不穩(wěn)定的。（ ）18. AOE網(wǎng)所表示的工程至少所需的時(shí)間等于從源點(diǎn)到

35、匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。（ ）19. 在單鏈表中，頭結(jié)點(diǎn)是必不可少的。（ ）20. 循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)完全相同，只是結(jié)點(diǎn)間的連接方式不同。（ ）21. 內(nèi)部排序是指排序過(guò)程完全在內(nèi)存中進(jìn)行的排序。（ ）22. 拓?fù)渑判蚴侵附Y(jié)點(diǎn)的值是有序排列。（ ）23. 在采用線性探測(cè)法處理沖突的散列表中，所有同義詞在表中相鄰。（ ）24.順序棧在棧滿的情況下不能做進(jìn)棧操作，否則將產(chǎn)生“上溢”。（ ）25. 頭指針就是頭結(jié)點(diǎn)。（ ）26.空串與空格串是相同的。（ ）27.構(gòu)造哈希函數(shù)的兩個(gè)原則是：函數(shù)本身便于計(jì)算；計(jì)算出來(lái)的地址絕對(duì)不能發(fā)生沖突。（ ）28. 如果某排序算法是不穩(wěn)定的，則該排序

36、方法沒(méi)有實(shí)際應(yīng)用價(jià)值。（ ）29.隊(duì)列中，允許插入的一端叫做隊(duì)尾，允許刪除的一端則稱為隊(duì)頭。（ ）30.用鄰接矩陣存儲(chǔ)圖，所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。（ ）31. 二叉排序樹的查找和折半查找的時(shí)間性能相同。（ ）32. AOV網(wǎng)的拓?fù)湫蛄惺俏ㄒ坏?。?）33. 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（ ）34. 連通分量是無(wú)向圖中的極小連通子圖。（ ）35在循環(huán)隊(duì)列（少用一個(gè)元素空間）中front 指向?qū)︻^元素位置，rear 指向隊(duì)尾元素的后一位置，則隊(duì)滿的條件是front= =rear。（ ）四、按要求完成下列各題。1. 編寫一個(gè)算法，

37、實(shí)現(xiàn)在非遞減的有序單鏈表中插入一個(gè)值為x的數(shù)據(jù)元素，并使單鏈表仍然保持有序。2.對(duì)于給定的一組關(guān)鍵碼：503,087,512,061,908,170,897,275, 653,426，分別畫出應(yīng)用直接插入排序、簡(jiǎn)單選擇排序、冒泡排序、快速排序以及歸并排序?qū)υ撔蛄羞M(jìn)行排序中各趟的結(jié)果序列。3.已知世界六大城市為：北京（Pe）、紐約（N）、巴黎（Pa）、倫敦（L）、東京（T）、墨西哥（M），表6-1給出了這六大城市之間的交通里程。請(qǐng)完成以下要求：（1）畫出這六大城市的交通網(wǎng)絡(luò)圖；（2）畫出該圖的鄰接表結(jié)構(gòu)；（3）畫出該圖按權(quán)值遞增的順序來(lái)構(gòu)造的最小生成樹。 表6-1 世界六大城市交通里程城市PeN

38、PaLTMPe109828121124N109585510832Pa825839792L815539589T211089795113M1243292891134.已知圖的鄰接矩陣如下：V1V2V3V4V5V6V7V8V8V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000當(dāng)用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，且鄰接表都按序號(hào)從大到小排序時(shí)，試寫出：（1） 以頂點(diǎn)V1為出發(fā)點(diǎn)的深度優(yōu)先遍歷序列；（2） 以頂點(diǎn)V1為出發(fā)點(diǎn)的廣度優(yōu)先遍歷序列；（3） 該圖的拓?fù)溆行蛐蛄小?. 假設(shè)用于通訊的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)