數(shù)據(jù)結(jié)構(gòu)試題及答案

好風(fēng)光好感動(dòng)1、線性表的邏輯順序與物理順序總是一致的。（X）2、線性表的順序存儲(chǔ)表示優(yōu)于

鏈?zhǔn)酱鎯?chǔ)表示。（X）3、線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。

（v）4、二維數(shù)組是其數(shù)組元素為線性表的線性表。（v）

5、每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除和搜索。（x）6、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏

輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面（v）7、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)

前驅(qū)和一個(gè)后繼。（x）

8、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲(chǔ)。（x）9、棧和隊(duì)

列邏輯上都是線性表。（v）10、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問(wèn)到所有結(jié)點(diǎn)（v）11、刪除二叉排

序樹(shù)中一個(gè)結(jié)點(diǎn)，再重新插入上去，一定能得到原來(lái)的二叉排序樹(shù)。（x）

12、快速排序是排序算法中最快的一種。（x）13、多維數(shù)組是向量的推廣。（x）14、一?般樹(shù)和二叉樹(shù)

的結(jié)點(diǎn)數(shù)目都可以為0。（v）15、直接選擇排序是一種不穩(wěn)定的排序方法。（x）

16、98、對(duì)一個(gè)堆按層次遍歷，不一定能得到一個(gè)有序序列°（v）17、在只有度為0和度為k的結(jié)點(diǎn)的k

叉樹(shù)中，設(shè)度為0的結(jié)點(diǎn)有nO個(gè)，度為k的結(jié)點(diǎn)有nk個(gè)，則有nOnk+10（x）18、折半搜索只適用與

有序表，包括有序的順序表和有序的鏈表。（x）

19、培棧在數(shù)據(jù)中的存儲(chǔ)原則是完進(jìn)先出。（x）20、隊(duì)列在數(shù)據(jù)中的存儲(chǔ)原則是后進(jìn)先出。（x）21、用

相鄰矩陣表示圖所用的存儲(chǔ)空間大小與圖的邊數(shù)成正比。（x）22、哈夫曼樹(shù)一定是滿二義樹(shù)。（x）

23、程序是用計(jì)算機(jī)語(yǔ)言表述的算法。（v）24、線性表的順序存儲(chǔ)結(jié)構(gòu)是通過(guò)數(shù)據(jù)元素的存儲(chǔ)地址直接反

映數(shù)據(jù)元素的邏輯關(guān)系。（v）25、用一組地址連續(xù)的存儲(chǔ)單元存放的元素一定構(gòu)成線性表。（v）26、堆

棧、隊(duì)列和數(shù)組的邏輯結(jié)構(gòu)都是線性表結(jié)構(gòu)。（v）

27、給定一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹(shù)。（x）28、只有在初始數(shù)據(jù)為逆序時(shí)，冒泡排序所

執(zhí)行的比較次數(shù)最多。（v）29、希爾排序在較率上較直接接入排序有較大的改進(jìn)。但是不穩(wěn)定的。

（v）30＞在平均情況下，快速排序法最快，堆積排序法最節(jié)省空間。（v）

，其他地址為空，如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)地址是.

A8B3

C5D9()】0.在含有n個(gè)項(xiàng)點(diǎn)有e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為。

A.cB.2c

C.n2-eD.n2-2e()l1.圖的深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的0

人先序遍歷B.中序遍歷

C.后序遍歷D.層次遍歷()12.設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)操作的

時(shí)間復(fù)雜度為

A.O(1)B.O(log2n)

CO(n)D.O(n2)()13.堆的形狀是一棵。

A.二叉排序樹(shù)B.滿二叉樹(shù)

C.完全二叉樹(shù)D.平衡二叉樹(shù)()14.一個(gè)無(wú)向連連通圖的生成樹(shù)是含有該連通圖的全部項(xiàng)點(diǎn)的。

A.極小連通子圖B.極小子圖

C.極大連通子圖D.極大子圖()15.一個(gè)序列中有10000個(gè)元素，若只想得到其中前10個(gè)最小元素，

最好采用方法

A.快速排序B.堆排序

C.插入排序D.二路歸并排序016.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為

typcdefstructnode{file:〃鏈表結(jié)點(diǎn)定義

ElemTypedata;用e:〃數(shù)據(jù)

structnode*Link;file:〃結(jié)點(diǎn)后繼指針

}ListNodc;

A.s->link=p;p->link=s;

C.s->link=p->link;p=s;

ni7鉛的鉆赤中性占的姑珈頭i

已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s,則應(yīng)執(zhí)行下列哪一個(gè)操作

A.s->link=p;p->link=s;B.s->link=p->link;p->link=s;

C.s->link=p->link;p=s;D.p->link=s;s->link=p;

ni7設(shè)助餅弟中姑占的姑松小

typedefstructnode

(用c:〃鏈表結(jié)點(diǎn)定義ElemTypedata;file:〃數(shù)據(jù)structnode*Link;file:〃結(jié)點(diǎn)后繼指針)

ListNodc;

非空的循環(huán)單鏈表加st的尾結(jié)點(diǎn)(由p所指向)滿足：

A.p->link==NULL;B,p==NULL;

C.p->link==first;D.p==first;

)18.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱(chēng)為.

A.數(shù)據(jù)B.數(shù)據(jù)元素

C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類(lèi)型

)19.在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是

A.O(l)B.()(n)

C.O(nlogn)D.O(n2)

)20.隊(duì)和棧的主要區(qū)別是_

A.邏輯結(jié)構(gòu)不同B.存儲(chǔ)結(jié)構(gòu)不同

C.所包含的運(yùn)算個(gè)數(shù)不D.限定插入和刪除的位置不同

同)21.鏈棧與順序棧相比,比較明顯的優(yōu)點(diǎn)是

A.插入操作更加方便B.刪除操作更加方便

C.不會(huì)出現(xiàn)下溢的情況D.不會(huì)出現(xiàn)上溢的情況

()22.在目標(biāo)串T[0,,nl]="xwxxyxy”中,對(duì)模式串xy”進(jìn)行子串定位操作的

結(jié)果

A.OB.2

C.3D.5

)23.已知廣義表的表頭為A,表尾為(B,Q,則此廣義表為.

A.(A,(B,C))B.(A,B,C)

C.(A,B,C)D.((A,B,C))

)24.二維數(shù)組A按行順序存儲(chǔ)，其中每個(gè)元素占1個(gè)存儲(chǔ)單元。若AHH11的存儲(chǔ)地址為420,

A[3][3]的存儲(chǔ)地址為446,貝JA[5][5]的存儲(chǔ)地址為

A.470B.471

C.472D.473

)25.二叉樹(shù)中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為.

A>。⑴B、O(n)

C、0(n2)D>O(log2n)

)36.假定一?個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e為f和r,則判斷隊(duì)空的條件為一。

A、f+l==rB、r+I==f

C、f==OD、f==r

)37.從堆中刪除一個(gè)元素的時(shí)間復(fù)雜以為一。

A、O(1)B、O(log2n)

C^O(n)D>O(nlog2n)

)38.若需要利用形參宜接訪問(wèn)實(shí)參，則應(yīng)把形參變量說(shuō)明為一參數(shù)。

A.指針B.引用

C.值D.變希：

)39.在一個(gè)單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)由指針p所指向的結(jié)點(diǎn)，則執(zhí)行一

o

A.q—>next=p一>next;p一>next=q;C.q—>next=p一>next;p—>next=q;

B.p—>next=q一>next;q=p;D.p—>next=q一>next;q一>next=p;

)40.在一個(gè)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的一位置。

A.前一個(gè)B.后一個(gè)

C.當(dāng)前D.最后一個(gè)

)41.向二叉搜索樹(shù)中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致力一。

AO(l)BO(log2n)

CO(n)DO(nlog2n)

)42.算法指的是

計(jì)算機(jī)程序B.解決問(wèn)題的計(jì)算方法

C.排序算法D.解決問(wèn)題的有限運(yùn)算序列

)43.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址

A.必須是不連續(xù)的B.連續(xù)與否均可

C.必須是連續(xù)的D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)

)44.將長(zhǎng)充為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為

A.O(1)B.O(n)

C.O(m)D.O(m+n)

)45.由兩個(gè)棧共享一個(gè)向星空間的好處是:

A.減少存取時(shí)間，降低下溢發(fā)生的機(jī)率B.節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率

C.減少存取時(shí)間，降低上溢發(fā)生的機(jī)率D.節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率

A.front=front+1

()46.設(shè)數(shù)組DAtAg］作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，血)nt為隊(duì)頭指針，reAr為隊(duì)

尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為

A.front=front+lB.front=(front+1)%(m-1)

C.front=(front-l)%mD.front=(front+l)%m()47.如下陳述中正確的是

A.串是一種特殊的線性表B.串的長(zhǎng)度必須大于零

C串中元素只能是字母D.空串就是空白串()48.若目標(biāo)串的長(zhǎng)充為n,模式串的長(zhǎng)度為［n/3］,則執(zhí)行模式

匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是()49.一個(gè)非空廣義表的表頭

A.O(l)B.O(n)

C.O(n2)D.O(n3)

A.不可能是子表B.只能是子表

C.只能是原子D.可以是子表或原子050.從堆中刪除一個(gè)元素的時(shí)間復(fù)雜

度為。02335

A、O⑴B、O(n)

C、O(log2n)D

O(nlog2n)()51.一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為

A.4B.5

C.6D.7()52.從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為。

A、O(n)B>o(1)

C、O(log2n)D.O(n2)()53.根據(jù)n個(gè)元素建立一棵二叉搜索樹(shù)時(shí)，其時(shí)間復(fù)雜度大致為。

A()(n)B、O(log2n)

C、O(n2)D、O(nlog2n)()54.用某種排序方法對(duì)關(guān)鍵字序列(25,84,21,47,15,27,68,35,20)進(jìn)行排序

時(shí)，序列的變化情況是如下:

20,15,21,25,47,27,68,35,84

15,20,21,25,35,27,47,68,84

15,20,21,25,27,35,47,68,84

則所采用的排序方法是.

A.選擇排序B.希爾排序

C歸并排序D.快速排序

)55.透于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是.

A.有序表B.分塊有序表

C.二叉排序樹(shù)D.線性鏈表

)56.若需要利用形參直接訪問(wèn)實(shí)參，則應(yīng)把形參變量說(shuō)明為.參數(shù)。

A指針B引用

D常最

)57.鏈?zhǔn)綏Ｅc順序棧相比,一個(gè)比較明顯的優(yōu)點(diǎn)是0

A,插入操作更加方便B.通常不會(huì)出現(xiàn)棧滿的情況

C,不會(huì)出現(xiàn)?？盏那闆rD.刪除操作更加方便

)58.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,link)。己知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前

驅(qū)，若在*勺與*臼之間插入結(jié)點(diǎn)*s,則應(yīng)執(zhí)行下列哪一個(gè)操作

A.s->link=p->link;p->link=s;B.p->link=s;s->link=q;

C.p->link=s->link;s->link=p;D.q->link=s;s->link=p;

)59.若讓元素123依次進(jìn)棧，則出棧次序不可能出現(xiàn)種情況。

A,3,2,1B.2,1,3

C.3,1,2D.1,3,2

)60.線性鏈表不具有的特點(diǎn)是.

A.隨機(jī)訪問(wèn)B.不必事先估計(jì)所需存儲(chǔ)空間大小

C.插入與刪除時(shí)不必移動(dòng)元素D.所需空間與線性表長(zhǎng)度成正比

)61.在稀疏矩陣的十字鏈接存儲(chǔ)中，每個(gè)列單鏈表中的結(jié)點(diǎn)都具有相同的.

A.行號(hào)B.列號(hào)

)62,祗善咻順序隊(duì)列的隊(duì)首和隊(duì)尾春榭如為front和rear,存放該隊(duì)列的數(shù)組長(zhǎng)度為N,

則判斷隊(duì)空的條件為.

A.(front+1)%N==rearC.front==0

B.(rcar+l)%N==frontD.front==rear

)63.棧的插入和刪除操作在..進(jìn)行.

(A).棧頂(B).棧底

(。.任意位置(D)指定位置

)64.在一個(gè)順序循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的.位置。

A.后兩個(gè)B.后一個(gè)

c.當(dāng)前D.前一個(gè)

()65.下面算法的時(shí)間復(fù)雜度為一o

intf(intn){if(n==0)return1;elsereturnn*f(n-1);)

A.0(l)B.O(n)

C.O(n2)D.O(n!)

()66.數(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、

算法

()67.數(shù)據(jù)結(jié)構(gòu)被形式地定義為(K,R),其中IV是(①)的有限集合，R是K±(②)的有限集合

①A、算法B、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯結(jié)韻

②A、操作B、映象C、存儲(chǔ)D、關(guān)系

()68.在數(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)

()69.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)

A、隨機(jī)存取B、順序存取

C、索引存取D、HASH存取

()70.算法分析的目的是(①)，算法分析的兩個(gè)主要方面是(②)

①A、找出數(shù)據(jù)結(jié)構(gòu)的合理性C、分析算法的效率以求改進(jìn)B、研究算法中的輸入和輸出的關(guān)系

D、分析算法的易懂性和文檔性

②A、空間復(fù)雜性和時(shí)間復(fù)雜性C、可讀性和文檔性B、正確性和簡(jiǎn)明性D、數(shù)據(jù)復(fù)雜性和程序

復(fù)雜性

)71.計(jì)算機(jī)算法指的是(①)，它必具備輸入、輸出和(②)等五個(gè)特性

①A、計(jì)算方法B、排序方法

C、解決萊一問(wèn)題的有限運(yùn)算序列D、調(diào)度方法

②A、可執(zhí)行性、可移植性和可擴(kuò)充性C、確定性、有窮性和穩(wěn)定性

B、可執(zhí)行性、確定性和有窮性D、易謾性、穩(wěn)定性和安全性

)72.線性表若采用鏈表存儲(chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址.

A、必須是連續(xù)的B、部分池址必須是連續(xù)的

C、一定是不連續(xù)的D、連續(xù)不連續(xù)都可以

)73.在以下的敘述中，正確的是

A、線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)C、棧的操作方式是先進(jìn)先出

B、二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表D、隊(duì)列的操作方式是先進(jìn)后出

)74.一個(gè)數(shù)組元素A[i]與的表示等價(jià)。

A、*(A+i)B、A+i

C、*A+iD、&A+i

)75.對(duì)于兩個(gè)函數(shù)，若函數(shù)名相同，但只是不同則不是重載函數(shù)。

A、參數(shù)類(lèi)型B、參數(shù)個(gè)數(shù)

C、函數(shù)類(lèi)型D、函數(shù)變房

)76.若需要利用形參直接訪問(wèn)實(shí)參，則應(yīng)把形參變星說(shuō)明為參數(shù)

A、指針B.引用

C、值D、函數(shù)

)77.下面程序段的時(shí)間復(fù)雜度為ofor(inti=0;i<m;i++)for(intj=0;jVn;j++)A[i]fi]=i*h

A、O(m2)B、O(n2)

CAO(m*n)D>O(m+n)

)78.執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為。

fbr(inti=l;i<=n;i++)ft)r(intj=l;j<=i;j++)S;

A、n2B、n2/2

C、n(n+l)D>n(n+l)/2

)79.下面算法的時(shí)間復(fù)雜度為。

intf(unsignedintn){if(n==011n==l)return1;elsereturnn*f(n-l);)

A、O(1)B、O(n)

C、O(n2)D、O(n!)

)80.在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素(Yivn+1)之前插入一個(gè)新元素時(shí);需要從后向

前依次后移

個(gè)元素。

A、n-iB、n-i+1

C、n-i-lD、i

()81.在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(IWiMn+l)時(shí)，需要從前向后依次前移個(gè)元素。

ANn-iB>n-i+1

C、n-i-lD、i

()82.在一個(gè)長(zhǎng)度為n的線性表中順序查找值為x的元素時(shí)，查找時(shí)的平均查找長(zhǎng)度(即x同元素的平均比

較次數(shù)，假定查找每個(gè)元素的概率都相等)為。

ANnB、n/2

C、(n+l)/2D>(n-l)/2

()83.在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行。

ANHL=p;p->next=HL;C、p->next=HL;p=HL;

B、p->next=HL;HL=p;D>p->next=HL->next;HL->next=p:

()84.在一個(gè)單鏈表HL中，若要在指針q所指的結(jié)點(diǎn)的后面插入一個(gè)由指針p所指的結(jié)點(diǎn)，則執(zhí)行。

A、q->ncxt=p->ncxt;p->ncxt=q;C>q->ncxt=p->ncxt;p->ncxt=q;

B、p->next=q->next;q=p;D^p->ncxt=q->ncxt;q->ncxt=p;

()85.在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行。

A、p=q->next;p->next=q->next;CAp=q->next;q->next=p->next;

B、p=q->next;q->next=p;D>q->next=q->next->next;q->nexl=q;

()86.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)行單鏈表中的結(jié)點(diǎn)都具有相同的

A、行號(hào)B、列號(hào)

C、元素值D、地址

()87.設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為n,則求廣義表深度算法的時(shí)間復(fù)雜度為。

A>。⑴B、0(n)

C^0(n2)D、O(log2n)

()88.棧的插入與刪除操作在曲行。

A、棧頂B、棧底

C、任意位置D、指定位置

()89.當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top二N表示棧空，則向這個(gè)棧插入一個(gè)元素

時(shí)，首先應(yīng)執(zhí)行語(yǔ)句修改top指針。

31、快速排序法是一種穩(wěn)定性排序法。(x)32、算法一定要有輸入和輸出。(x)33、算法分析的目的旨

在分析算法的效率以求改進(jìn)算法。(v)34、非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接后繼元

素。(x)

35、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不僅有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，還有索引結(jié)構(gòu)與散列結(jié)構(gòu)。(x)36、若頻繁

地對(duì)線性表進(jìn)行插入和刪除操作，該線性表采用順序存儲(chǔ)結(jié)構(gòu)更合適。(x)37、若線性表采用順序存儲(chǔ)

結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素占用4個(gè)存儲(chǔ)單元，第12個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為144,則第1個(gè)數(shù)據(jù)元素的存儲(chǔ)地

址是101。(x)38、若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)元素之前需要移動(dòng)表中n-

i+1個(gè)元素。(x)

39、符號(hào)p-〉next出現(xiàn)在表達(dá)式中表示p所指的那個(gè)結(jié)點(diǎn)的內(nèi)容。(x)40、要將指針p移到它所指的結(jié)點(diǎn)

的下一個(gè)結(jié)點(diǎn)是執(zhí)行語(yǔ)句p_p_>nexto(x)41、若某堆棧的輸入序列為1,2,3,4，則4,31,2不可能是堆棧的

輸出序列之一。(v)42、線性鏈表中各個(gè)鏈結(jié)點(diǎn)之間的地址不一定要連續(xù)。(v)

43、程序就是算法，但算法不一?定是程序。(v)44、線性表只能采用順序存儲(chǔ)結(jié)構(gòu)或者鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

(v)45.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)指針來(lái)間接反映數(shù)據(jù)元素之間邏輯關(guān)系的。(v)46、除插入和刪

除操作外，數(shù)組的主要操作還有存取、修改、檢索和排序等。(x)

47、稀疏矩陣中0元素的分布有規(guī)律，因此可以采用三元組方法進(jìn)行壓縮存儲(chǔ)。(v)48、不管堆棧采用

何種存儲(chǔ)結(jié)構(gòu)，只要堆棧不空，可以任意刪除一個(gè)元素。(v)49,確定串T在串S中首次出現(xiàn)的位置的

操作稱(chēng)為串的模式匹配。(v)50、深度為h的非空二叉樹(shù)的第i層最多有2i-l個(gè)結(jié)點(diǎn)。(x)

51、滿二叉樹(shù)也是完全二叉樹(shù)。(v)52.已知一棵二叉樹(shù)的前序序列和后序序列可以唯一地構(gòu)造出該二

叉樹(shù)。(x)53、非空二叉排序樹(shù)的任意一棵子樹(shù)也是二叉排序樹(shù)。(v)54、對(duì)一棵二叉排序樹(shù)進(jìn)行前序

遍歷一定可以得到一個(gè)按值有序的序列。(x)

55、一個(gè)廣義表的深度是指該廣義表展開(kāi)后所含括號(hào)的層數(shù)。(v)56,散列表的查找效率主耍取決于所

選擇的數(shù)列函數(shù)與處理沖突的方法。(v)57、序列初始為逆序時(shí)，冒泡排序法所進(jìn)行的元素之間的比較

次數(shù)最多。(v)58、已知指針P指向鍵表L中的某結(jié)點(diǎn)，執(zhí)行語(yǔ)句P=P->next不會(huì)刪除該鏈表中的結(jié)

點(diǎn)。

(v)59>在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。

(v)60.如果■?個(gè)串中的所有字符均在另一串中出現(xiàn)，則說(shuō)前者是后者的子串。(x)

A、top++B、top-

CAtop=0D>top

()90.若讓元素1,2,3依次進(jìn)棧，則出棧次序不可能出現(xiàn)種情況。

43,2,113、2,1,3

C、3,1,2D、1,3,2

()91.在一個(gè)循環(huán)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的位置c

A、前一個(gè)B、后一個(gè)

C、當(dāng)前D、后面

()92.當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為。

A、N-2B、N-1

C、ND、N+1

()93.從一個(gè)循環(huán)順序隊(duì)列刪除元素時(shí)，首先需要。

A、前移一位隊(duì)首指針B、后移一位隊(duì)首指針

C、取出隊(duì)首指針?biāo)肝恢蒙系脑谼、取出隊(duì)尾指針?biāo)肝恢蒙系脑?/p>

()94.假定一個(gè)循環(huán)順序隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e為f和r,則判斷隊(duì)空的條件是of十仁=rB、r+l==f

C^f==OD^f==r

()95.假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針?lè)謩e為front和rear,則判斷隊(duì)空的條件是。

A、front==rearBfrontMNULL

C、rear!=NULLD、front==NULL四、應(yīng)用題：

1、棧和隊(duì)列都是特殊線性表，其特殊性是什么？

2、設(shè)有一順序隊(duì)列sq,容量為5,初始狀態(tài)sq.front=sq.rear=0,劃出作完下列操作的隊(duì)列及其頭尾指針變化狀

態(tài)，若不能入隊(duì)，簡(jiǎn)述理由后停止。

1)de,b入隊(duì)。

2)d,e出隊(duì)。

3)ij入隊(duì)。

4)b出隊(duì)。

5)n,o,p入隊(duì)。

3、設(shè)有一個(gè)順序棧S,元素$“2*4&6依次進(jìn)棧,如果6個(gè)元素的出棧順序?yàn)閟2,s3,s4,s6,s5,

si,則順序棧的容：彘至少應(yīng)為多少？

4、將兩個(gè)棧存入數(shù)組V[L.m]中應(yīng)如何安排最好?這時(shí)棧空、棧滿的條件是什么？

5、己知稀疏矩陣如下：

10002

00300

45000

00000

00060

靖寫(xiě)出該稀疏矩陣三元組表示。

6,廣義表A=(2力,94),9,(￡8)))其長(zhǎng)度,及深度。

7、請(qǐng)畫(huà)出下面廣義表相應(yīng)的加入表頭結(jié)點(diǎn)的單鏈表表示,

D(A(x,y,L(a,b)),B(z,A(x,y,L(a,b))))。

8、一棵具有n個(gè)結(jié)點(diǎn)的理想平衡二叉樹(shù)(即除離根最遠(yuǎn)的最底層外其他各層都是滿的，最底層

有若干結(jié)點(diǎn))有多少層？若設(shè)根結(jié)點(diǎn)在第()層，則樹(shù)的高度h如何用n來(lái)表示(注意n可能

為0)?

9、設(shè)二叉樹(shù)后根遍歷為BAC,畫(huà)出所有可能的二叉樹(shù)。

10、假設(shè)一棵二叉樹(shù)的層序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,請(qǐng)畫(huà)出該樹(shù)。

11、有一個(gè)完全二叉樹(shù)按層次順序存放在一維數(shù)組中，如下所示：

123456789101112

HkACDPFJXBQz

請(qǐng)指出結(jié)點(diǎn)P的父結(jié)點(diǎn)，左子女，右子女。給出下列二又樹(shù)的先序序列。

13、已知某非空二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，樹(shù)中結(jié)點(diǎn)的數(shù)據(jù)信息依次存放在一個(gè)一維數(shù)組中,

ABcnDFEnnGnnHn□,該二義樹(shù)的中序遍歷序列為：

14、設(shè)一棵二叉樹(shù)的前序序列為12345678.9.其中序序列為2.3.154.7.8.69試畫(huà)出該二叉樹(shù)。

15、已知一組元素為(46,25,78,62,12,37,70,29),試畫(huà)出按元素排列次序插入生成的

一棵二叉樹(shù)。

16、由于元素插入的次序不同，所構(gòu)成的二叉排序樹(shù)也有不同的狀態(tài)，請(qǐng)畫(huà)出一棵含有1,2,3,

4,5,6六個(gè)結(jié)點(diǎn)且以1為根，深度為4的二叉排序樹(shù)。

17、什么是線索二叉樹(shù)？為什么要線索化?

18、有n個(gè)頂點(diǎn)的有向連通圖最多有多少條邊?最少有多少條邊？

19、下期中給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)1出發(fā)，對(duì)它進(jìn)行深度優(yōu)先遍歷得到的頂點(diǎn)序列是:

進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列是：

21、什么是哈夫曼(Huffman)樹(shù)？

22、已知結(jié)點(diǎn)a,b,c,d及其權(quán)值寫(xiě)出哈夫曼樹(shù)的構(gòu)造過(guò)程。

abed

752423、已知圖G={V,E)

V={a,b,c,d,e}

E={(a,b),(b,d),(c,d),(d,e),(e,a),(a,c)J

畫(huà)出圖G,畫(huà)出圖G的鄰接表。

24、考慮下圖：

1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(shù)。

2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)。

3)根據(jù)普里姆(Prim)算法，求它的最小生成樹(shù)。

若采用以第一個(gè)元素為分界元素的快速排序法，則一趟掃描的結(jié)果是:

26、一個(gè)對(duì)象序列的排序碼為{46,79,56,38,40,84},采用快速排序以位于最左位置的對(duì)象為基準(zhǔn)而得到的

第一次劃分結(jié)果為：

27、用二分法對(duì)一個(gè)長(zhǎng)度為10的有序表進(jìn)行查找，填寫(xiě)查找每個(gè)元素需要的比較次數(shù)。

下標(biāo)：0123456789

比較次數(shù)：

28、若對(duì)序列(49,38,27,13,97,76,50,65)采用泡排序法(按照道的大小從小到大)進(jìn)行排序，請(qǐng)分別在下表

中寫(xiě)出每一趟排序的結(jié)果。

原始序列4938271397765065

第1趟的結(jié)果

第2趟的結(jié)果

第3趟的結(jié)果

第4趟的結(jié)果29、給出一組關(guān)鍵字：29,18,25,47,58,12,51,10,分別寫(xiě)出按下列各種排序方法進(jìn)行排

序時(shí)的變化過(guò)程：

1）歸并排序每歸并一次書(shū)寫(xiě)一個(gè)次序。

2）快速排序每劃分一次書(shū)寫(xiě)一個(gè)次序。

3）堆排序先建成一個(gè)堆，然后每從堆頂取下一個(gè)元素后，將堆調(diào)整一次。

30、給出一組關(guān)鍵字'1=（12,2,16,30,8,28,4,10,20,6,18）o寫(xiě)出用下列算法從小到大排序時(shí)第一趟結(jié)

束時(shí)的序列：

1）希爾排序（第一趟排序的增量為5）

2）快速排序（選第一個(gè)記錄為樞軸（分隔））

3）鏈?zhǔn)交鶖?shù)排序（基數(shù)為10）31、若雜湊表的地址范圍為|0:9],雜湊函數(shù)為H（key）=（key2+2）MOD

9,并旦采用鏈地址方法處理沖突，請(qǐng)畫(huà)出元素7,4,536,2.891依次插入該雜湊表以后，該雜湊表的狀態(tài)。

32、已知二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，鏈結(jié)點(diǎn)的構(gòu)造為Ichild|data|rchHd,根結(jié)點(diǎn)的指針為T(mén)。

下面是利用中序遍歷的方法統(tǒng)計(jì)二叉樹(shù)中度為1的結(jié)點(diǎn)的個(gè)數(shù)的算法，算法中設(shè)也了一順序存儲(chǔ)結(jié)構(gòu)

的堆棧STACK棧頂指針為top,請(qǐng)?jiān)谒惴ǖ目杖碧幪钊脒m當(dāng)內(nèi)容，使之能正常工

作。

33、設(shè)有一個(gè)順序棧S,元素si,s2,s3,s4,s5,s6依次進(jìn)棧,如果6個(gè)元素的出棧順序?yàn)閟2,s3,s4,s6,s5,si,則順

序棧的容量至少應(yīng)為多少？

34、設(shè)有一個(gè)關(guān)犍碼的輸入序列（55,31,11,37,46,73,63,

02,07）,（1）從空樹(shù)開(kāi)始構(gòu)造平衡二叉搜索樹(shù)，畫(huà)出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹(shù)的形態(tài)。若發(fā)生不

平衡，指明需做的平衡旋轉(zhuǎn)的類(lèi)型及平衡旋轉(zhuǎn)的結(jié)果。

⑵計(jì)算該平衡二叉搜索樹(shù)在等概率下的查找成功的平均查找長(zhǎng)度和查找不成功的平

均查找長(zhǎng)度。

35、關(guān)犍碼的輸入序列｛55,31,11,37,46,73,63,02,07｝請(qǐng)計(jì)算在二分法查找、二叉排序樹(shù)兩種的情況下

等概率下查找成功的平均查找長(zhǎng)度。

36、廣義表A=(a,b,(c,d),(e,(f,g?)?計(jì)算下面式子的值

Head(Tail(Head(Tail(Tail(A)))))37,下圖是用鄰接表存儲(chǔ)的圖，畫(huà)出此圖，并寫(xiě)出從C點(diǎn)開(kāi)始按深度優(yōu)先、

廣度優(yōu)先遍歷該圖的結(jié)果。

畫(huà)出該樹(shù)，并

39、判斷卜.列序列是否為堆，如果不是請(qǐng)調(diào)整為堆，如果是請(qǐng)判斷是什么類(lèi)型的堆(101,88,46,70,34,39,

45,58,66,10)40、假設(shè)一棵二叉樹(shù)的層序序列是ABCDEFGH1J和中序序列是DBGEHJACIF,請(qǐng)畫(huà)出該樹(shù)。

41、找出所有滿足下列條件的二義樹(shù)

a)它們?cè)谙刃虮闅v和中序遍歷時(shí),得到的結(jié)點(diǎn)訪問(wèn)序列相同；

b)它們?cè)诤笮虮闅v和中序遍歷時(shí),得到的結(jié)點(diǎn)訪問(wèn)序列相同；

0它們?cè)谙刃虮闅v和后序遍歷時(shí),得到的結(jié)點(diǎn)訪問(wèn)序列相同。

42、已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，其中P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)。

a)在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是

b)在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是

c)在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是

d)在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是

(1)P->next=S;

(2)P->next=P->next->.next;

(3)P->next=S->next;

(4)S->ncxt=P->next;

(5)S->ncxt=L;

(6)S->next=NIL;

⑺Q=P；

(8)WHILEP->nextoQ

P=P->ncxt;

(9)WHILEP->next!=NULL

P=P->next;

(10)P=Q;

(D)P=L;

(12)L=S;

(13)L=P;43、已知樹(shù)T的先序遍歷序列為ABCDEFGHIJKL,后序遍歷序列為CBEFDJIKLHGA,請(qǐng)畫(huà)

出樹(shù)Tc

44、對(duì)關(guān)鍵字序列(72,87,61,23,94,16,5,58)進(jìn)行堆排序、快速排序、直接選擇排序，使之關(guān)鍵字遞增有

序，請(qǐng)寫(xiě)出每個(gè)排序的前三趟結(jié)果。

45、請(qǐng)畫(huà)出廣義表D的圖形表示

D=(D,(a,b),((a,b),c),())46.若一二叉樹(shù)有2度結(jié)點(diǎn)100個(gè)，則其葉結(jié)點(diǎn)有多少個(gè)？該二叉樹(shù)可以有多少個(gè)1度

頂點(diǎn)？

47、對(duì)于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道?個(gè)指向鏈表1」某結(jié)點(diǎn)的指針p,能否將P所指

結(jié)點(diǎn)的數(shù)據(jù)元素與其確實(shí)存在的直接前驅(qū)交換？靖對(duì)每一種鏈表作出判斷，若可以，寫(xiě)出程序段：

否則說(shuō)明理由。

單鏈表和患循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)為datenext

雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為priordatenext⑴單鏈表(2)單循環(huán)鏈表

⑶雙向鏈表47、已知散列函數(shù)為ll(kc滬kcy%7,散列表長(zhǎng)度為7(散列地址空間為0..6),待散列序列為:

(25,48,32,50,68)o要求：

⑴根據(jù)以上條件構(gòu)造一散列表，并用線性探測(cè)法解決有關(guān)地址沖突；

⑵若要用該散列表查找元素68,給出所需的比較次數(shù)。

48、已知一組鍵值序列為(38,64.73,52,40,37,56,43),試采用快速排序法對(duì)該組序列作升序排序，并給出

每一趟的排序結(jié)果。

49、已知某二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如圖所示，試畫(huà)出該二叉樹(shù)。

ABCDEF

50、設(shè)有一個(gè)關(guān)鍵碼的輸入序列_________

{55,31,11,37,46.73,63,0：

07W)從空樹(shù)開(kāi)始構(gòu)造平衡二叉搜索樹(shù)，畫(huà)出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹(shù)的形態(tài)。

若發(fā)生不平衡，指明需做的平衡旋轉(zhuǎn)的類(lèi)型及平衡旋轉(zhuǎn)的結(jié)果。

⑵計(jì)算該平衡二叉搜索樹(shù)在等概率下的查找成功的平均瓷找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。

51、求下列廣義表運(yùn)算的結(jié)果：

1)HEAD(p,h,w);TAIL(b,k,p,h);HEAD((a,b),(c,d));TAIL(a,b),(c,d);

2)HEAD(TAIL(((a,b),(c,d))))TAIL(HEAD((a,b),(c,d)))52>畫(huà)出下列廣義表的圖形表示：

1)D(A()),B(c),C(a,L(b,c,d))Jl020,aJ3(Jl))J3(n))53、完成下列要求:

1)請(qǐng)畫(huà)出下列廣義表的存儲(chǔ)結(jié)構(gòu)((((a),b)),((0,(d)),(c,f)))

2)請(qǐng)寫(xiě)出下面鏈表表示的廣義表

54、一棵二叉樹(shù)如圖:

1）寫(xiě)出對(duì)此樹(shù)進(jìn)行中序、先序、后續(xù)遍歷時(shí)得到的結(jié)點(diǎn)序歹人

2）畫(huà)出樹(shù)的后序線索二叉樹(shù)。

55、具有3個(gè)節(jié)點(diǎn)的樹(shù)和具有3個(gè)節(jié)點(diǎn)的二叉樹(shù)它們的所有不同形態(tài)有哪些?

56、將下列森林轉(zhuǎn)化為二叉樹(shù)。

57、已知一個(gè)圖如下所示，寫(xiě)出其臨接矩陣,

則可以得到所有頂點(diǎn)序列為什么？

61、設(shè)與一棵樹(shù)T所對(duì)應(yīng)的二叉樹(shù)為BT,則與T中的葉子結(jié)點(diǎn)所對(duì)應(yīng)的BT中的結(jié)點(diǎn)也一定是葉子結(jié)點(diǎn)。

(x)62、若圖G的最小生成樹(shù)不唯一，則G的邊數(shù)一定多于『1,并且權(quán)值最小的邊有多條(其中n為G

的頂點(diǎn)數(shù))。(v)63、給出不同的輸入序列建造二叉排序樹(shù)，一定得到不同的二叉排序樹(shù)。(v)64、由

于希爾排序的最后一趟與直接插入排序過(guò)程相同，因此前者一定比后者花費(fèi)的時(shí)間多。(x)

65、程序越短，程序運(yùn)行的時(shí)間就越少。(x)66、采用循環(huán)倍表作為存儲(chǔ)結(jié)構(gòu)的隊(duì)列就是循環(huán)隊(duì)列。

(x)67、堆棧是一種插入和刪除操作在表的一端進(jìn)行的線性表。(v)68、一個(gè)任意串是其自身的子串。

(v)

69、哈夫曼樹(shù)一定是完全二叉樹(shù)。(x)70、帶權(quán)連通圖中某一頂點(diǎn)到圖中另一定點(diǎn)的最短路徑不一定唯

一。(v)7K折半查找方法可以用于按值有序的線性鏈表的查找。(x)72、稀疏矩陣壓縮存儲(chǔ)后，必

會(huì)失效掉隨機(jī)存取功能。(x)

73、由一棵二叉樹(shù)的前序序列和后序序列可以唯一確定它。(x)74-.在n個(gè)結(jié)點(diǎn)的元向圖中，若邊數(shù)在

于n-1,則該圖必是連通圖。(x)75、在完全二叉樹(shù)中，若某結(jié)點(diǎn)元左孩子，則它必是葉結(jié)點(diǎn)。(v)76、

若一個(gè)有向圖的鄰接矩陣中，對(duì)角線以下元素均為0,則該圖的拓?fù)溆行蛐蛄斜囟ù嬖凇?v)

77、樹(shù)的帶權(quán)路徑長(zhǎng)度最小的二又樹(shù)中必定沒(méi)有度為1的結(jié)點(diǎn)。(v)78、二叉樹(shù)可以用。豆度W2的有

序樹(shù)來(lái)表示。(x)79、一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹(shù)。(x)80、101,88,46,70,34,

39,45,58,66,10)是堆；(v)

81、將一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)后，根結(jié)點(diǎn)沒(méi)有?左子樹(shù)；(x)82、用樹(shù)的前序遍歷和中序遍歷可以導(dǎo)出樹(shù)的

后序遍歷；(v)83、在非空線性鏈表中由p所指的結(jié)點(diǎn)后面插入一個(gè)由q所指的結(jié)點(diǎn)的過(guò)程是依次執(zhí)行

語(yǔ)句：q->ncxt=p->ncxt;p->ncxt=qo(v)84、非空雙向循環(huán)鏈表中由q所指的結(jié)點(diǎn)后面插入一個(gè)由p指

的結(jié)點(diǎn)的動(dòng)作依次為：p->prior=q,p->next=q->next,q->ne>:t=p,q->prior->next*一p0(x)

85、刪除非空鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧(設(shè)棧頂指針為top)的一個(gè)元素的過(guò)程是依次執(zhí)行:p=top,top二

p->ncxt,free(p)o(v)86哈希的查找無(wú)需進(jìn)行關(guān)鍵字的比較。

(v)87、?個(gè)好的哈赤函數(shù)應(yīng)使函數(shù)值均勻的分布在存儲(chǔ)空間的有效地址范圍內(nèi)，以盡可能減少?zèng)_突。(5

8、試問(wèn)在直接插入排序、希爾排序、快速排序、歸并排序、二分法排序、直接選擇排序中，哪些

排序是穩(wěn)定的？哪些是不穩(wěn)定的，哪個(gè)排序平均比較次數(shù)最少？哪個(gè)排序要求內(nèi)存容量最多？

59、哈希表中使用哈希函數(shù)H(key)=3*key%11,并采用開(kāi)放定址法處理沖突，隨機(jī)探測(cè)再散列的下一地址

公式為：

dl=H(key)di=(di-l+7*key)%11(1=23-試在0到10的散列地址空間中對(duì)關(guān)鍵字序列(22,

41,53,46,30,13,01,67)畫(huà)出Hash表示意圖，并求在等概率情況下查找成功的平均查找長(zhǎng)度。

60、什么是內(nèi)部排序？什么是排序方法的穩(wěn)定性？說(shuō)出你所學(xué)過(guò)的三個(gè)穩(wěn)定算法，一個(gè)不穩(wěn)定算法。

61、何為隊(duì)列上溢？一?般用什么方法解決，簡(jiǎn)述之。

62、載入下圖所示的有權(quán)圖G,回答下列問(wèn)題：

I)給出從結(jié)點(diǎn)vl出發(fā)按深度優(yōu)先搜索遍歷圖所得的結(jié)點(diǎn)序列；

2)給出圖的拓?fù)湫蛄校?/p>

3)給出從結(jié)點(diǎn)vl到結(jié)點(diǎn)8的最短路徑和關(guān)鍵路徑。

對(duì)于下圖，請(qǐng)給出對(duì)應(yīng)白........12….一；鄰接表表示和逆鄰接表表

樹(shù)，分別用孩子鏈表和孩子兄弟鏈表法畫(huà)出存儲(chǔ)結(jié)構(gòu)。

65、對(duì)于下圖的樹(shù)，請(qǐng)分別用中序、先序的方法寫(xiě)出其遍歷結(jié)果。

2）求初等概率情況下查找july的查找長(zhǎng)度。

67、數(shù)組以行優(yōu)先的順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址為100,每個(gè)元素占3個(gè)存儲(chǔ)長(zhǎng)度的

存儲(chǔ)空間，則元素A[5J,8]的存儲(chǔ)地址為多少？

68、設(shè)有一組關(guān)鍵字（17,13,153,29,35,21）需插入到表長(zhǎng)為12的表中,請(qǐng)回答下列問(wèn)題:

1）自己設(shè)計(jì)一個(gè)合理的散列函數(shù)2）用自己設(shè)計(jì)的函數(shù)將上述關(guān)鍵字插入到散列表中，畫(huà)出其結(jié)構(gòu)；

并指出用線性探測(cè)法解決沖突構(gòu)造散列表的裝填因子為多少？

69、己知-?棵三階B-樹(shù)如下圖所示，假定依次從中刪除關(guān)鍵字46,24,52,8,93和80試畫(huà)出每次刪除結(jié)點(diǎn)

后樹(shù)的情況：

71、令s='aaab',t='abcaaa',u='abcaabbabcabaacbacbaaa',分別求出他們的next值。

72、請(qǐng)畫(huà)出下列二叉樹(shù)的中序線索化前趨鏈樹(shù)，后序線索化后繼鏈樹(shù)。

{As,Bx,Ca,D\vw,Ae,CfEcld,Fap,Goi,Fab,

Hrc}74、試在如圖所示線索化的二叉樹(shù)中，查找指定結(jié)點(diǎn)E的后繼結(jié)點(diǎn)、C

的前驅(qū)結(jié)點(diǎn)，并說(shuō)明找到結(jié)果的原因。

75、什么是數(shù)據(jù)結(jié)構(gòu)?

76、試比較線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。

77、堆棧和隊(duì)列都是特殊線性表，其特殊性是什么？

78、將兩個(gè)棧存入數(shù)組中應(yīng)如何安排最好?這時(shí)?？諚M的條件是什么？

79、內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m）,提供給兩個(gè)棧S1和S2使用，怎樣分配這部分存儲(chǔ)

空間，使得對(duì)任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。

80、給出數(shù)組intA[3---8,2-6];當(dāng)它在內(nèi)存中按行存放和按列存放時(shí)，分別寫(xiě)出數(shù)組元素A[i,j]的地址計(jì)

算公式（設(shè)每個(gè)元素占兩個(gè)存儲(chǔ)單元）。

81、若一二叉樹(shù)有2度結(jié)點(diǎn)1（）0個(gè)，則其葉結(jié)點(diǎn)有多少個(gè)？該二叉樹(shù)可以有多少個(gè)1度頂點(diǎn)？

82、如圖所示的二叉樹(shù)完成中序遍歷、后續(xù)遍歷、先序遍歷，并畫(huà)出后續(xù)線索化的二叉樹(shù)。

BE

后根遍歷。

84、

85、有n個(gè)頂點(diǎn)的有向連通圖最多有多少條邊?最少有多少條邊？

86、什么是哈夫曼(Huffman)樹(shù)？

87、已知圖G={V,E)V={a,b,c,d,c}E={(a,b),(b,d),(c,d),(d,e),(e,a),(a,c)}畫(huà)出圖G,畫(huà)出圖G的鄰接表。

88、設(shè)一個(gè)有向圖為G=(V,E),其中V={vl,v2,v3,v4),E=

{<v2M>,vv2,v3>,vv4,vl>,<vl,v4>,<v4,v2：>},n出該有向圖，并求出每個(gè)結(jié)點(diǎn)的入度和出度，畫(huà)出相應(yīng)的鄰接

矩陣、鄰接表和逆鄰接農(nóng)。

89、請(qǐng)給出下圖的鄰接矩陣和鄰接表。

h

90、請(qǐng)畫(huà)出下圖中的極大連通子圖。

成最小生成樹(shù)的各條邊的并入順序。畫(huà)出最小生成樹(shù)。并寫(xiě)出廣度優(yōu)先和深度優(yōu)先的結(jié)點(diǎn)遍歷順序。

什么時(shí)動(dòng)態(tài)查找，什么叫平均查

找長(zhǎng)度,

93、用序列(46,88,45,39,70,58,101,10,66,34)建立一個(gè)二叉徘序樹(shù)，畫(huà)出該樹(shù)，并求在等概率情況下查

找成功的平均查找長(zhǎng)度。

94、已知一個(gè)線性表(38,25,74,63,52,48),假定采用h(k戶k%7計(jì)算散列地址進(jìn)行散列存儲(chǔ)，若引用線性探

測(cè)的開(kāi)放地址法解決沖突，則在該散列表上進(jìn)行檢索的平均檢索長(zhǎng)度為多少，若利用連地址法處理沖

突，則在該散列表上進(jìn)行檢索的平均查找長(zhǎng)度為多少？設(shè)地址空間為9。請(qǐng)畫(huà)出算列表。

96、已知長(zhǎng)度為12的表：(Jan,Fed,Ma^,Apr,May,Jun,Aug,Sep,Oct,Nov,Dec)按表中元素的順序，

依次插入一棵初始為空的二叉排序樹(shù)，畫(huà)出插完之后的二叉排序樹(shù)，并求其在等概率情況下，查找成功的

平均查找長(zhǎng)度。

98、有數(shù)列函數(shù)為h(k)二k%11,如果用二次探測(cè)在散列的方式解決沖突，49應(yīng)放入哪？

15386184

[56、37、59、41、98、47>94、50、63、52、42、54、60、72、86、90}100、有一組關(guān)鍵字{14,15.

30,28,5,10},分別畫(huà)出冒泡排序、快速排序過(guò)程的圖示。

101、已知一組鍵值序列為(38,64,73,52,40,37,56,43),試采用快速排序法對(duì)該組序列作升序排序，并給出

每一趟的排序結(jié)果。

102、對(duì)關(guān)鍵字序列(72,87,61,23,94,16,5,58)進(jìn)行堆排序、快速排序、直接選擇排序，使之關(guān)鍵字遞增有

序，請(qǐng)寫(xiě)出每個(gè)排序的前三趟結(jié)果。

五、程序題1、已知二叉樹(shù)用下面的順序結(jié)構(gòu)存儲(chǔ)?，寫(xiě)出中序遍歷該二叉樹(shù)的算法。

leftdateright2>下列算法為刪除單鏈表中值為X的算法，將程序填完整

voiddel(structnode*head)

{q=head;

p=q->ncxt;

\vhilc(()&&())

(q=p；

；)

if(p==null)printf("error");

else{;free(p);printf("success!");}}3、以下函數(shù)中，h是帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表的頭才旨針,

⑴寫(xiě)出下列程序的功能。

(2)當(dāng)鏈表中結(jié)點(diǎn)數(shù)分別為1和6(不包括頭結(jié)點(diǎn))時(shí)，請(qǐng)寫(xiě)出程序中while循環(huán)體的執(zhí)行次數(shù)。

Intfbx(structnode*h){structnodep,q;

intj=l;

p=h->next;

q=h->prior;whilc(p!=q&&p->prior!=q)

{if(p->data==q->data){p=p->next;q=q->prior;j++;)

elsej=0;}

returno)；}4、寫(xiě)出按后序序列遍歷中序線索樹(shù)的算法.

5、寫(xiě)出計(jì)算樹(shù)深度的算法。

6、寫(xiě)出計(jì)算樹(shù)葉子結(jié)點(diǎn)的算法。

7、寫(xiě)出計(jì)算寧符串長(zhǎng)度的算法。

8、試寫(xiě)出以帶頭結(jié)點(diǎn)單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎn)單選擇排序的算法9、閱讀下列算法，并回答下列問(wèn)題：

⑴該算法完成什么功能？

⑵算法中R[n+1]的作用是什么？

Voidsort(clcmtypcr[|,intn){intk,i;for(k=n-l;k>=I;k—)if(r[k]>r[k?1])

{r[n+l]=r[k];

for(i=k+l;r[i]<r[n+l];i++)4i-l]=r[i];r[i-

l]=r[n+l]；)10.試編寫(xiě)一算法，以完成在帶頭結(jié)點(diǎn)單鏈表L中第i個(gè)位置前插入元素X的操作。

11、二義樹(shù)是由所有度數(shù)不大于2的結(jié)點(diǎn)構(gòu)成的一種特定樹(shù)，若某結(jié)點(diǎn)度為2,則該結(jié)點(diǎn)有左右兩個(gè)孩子，

請(qǐng)編寫(xiě)算法計(jì)算一二叉樹(shù)所有度數(shù)為2的結(jié)點(diǎn)個(gè)數(shù)。

12、試設(shè)計(jì)一個(gè)算法在中序線索化的樹(shù)中，求指定結(jié)點(diǎn)P在后序遍歷序列中的前驅(qū)結(jié)點(diǎn)，要求用非遞歸算

法。

13、若X和Y是兩個(gè)單鏈表存儲(chǔ)的串，設(shè)計(jì)一個(gè)算法，找出X中第一個(gè)不在Y中出現(xiàn)的字符。

14、試設(shè)計(jì)一個(gè)算法在中序線索化的樹(shù)中，求指定結(jié)點(diǎn)P在后序遍歷序列中的前驅(qū)結(jié)點(diǎn)，要求用非

LxQ_EQ盅2sA....|Xn四~HY1II?1Y2I」….Nn四

遞歸算法。

15、設(shè)計(jì)一個(gè)算法，刪去串中第I個(gè)字符開(kāi)始的J個(gè)字符，說(shuō)明算法所用的存儲(chǔ)結(jié)構(gòu)，并估計(jì)算法的執(zhí)行

時(shí)間。

16、設(shè)有單鏈表中存放著N個(gè)字符，試設(shè)計(jì)算法判斷字符串是否中心對(duì)稱(chēng)關(guān)系，例如：XYZZYX,

XYZYX都算是中心對(duì)稱(chēng)的字符串。要求用盡可能少的時(shí)間完成判斷(提示：將

一半字符先依次進(jìn)棧)。

提示:我們?cè)O(shè)H為指向鏈表頭結(jié)點(diǎn)的指針，單鏈表每個(gè)結(jié)點(diǎn)包括兩個(gè)域:分別是date,next分別代表數(shù)據(jù)

域和指針域,s為定義的棧。

17、設(shè)計(jì)一個(gè)算法將任意輸入的N個(gè)數(shù)，按輸入的順序(或逆序)鏈接成一個(gè)單鏈表。

18、試設(shè)計(jì)一個(gè)算法，求單鏈表中數(shù)據(jù)侑為X)的元素的地址。

19、試編一個(gè)程序，將兩個(gè)字符串si和s2進(jìn)行比較，若sl>s2則輸出一個(gè)正數(shù)；若sl=s2,則輸出0;若

slVs2,則輸出一個(gè)負(fù)數(shù)。不能用strcmp函數(shù)。

20、寫(xiě)出在中序線索二叉樹(shù)中結(jié)點(diǎn)*臼的右子樹(shù)中插入一個(gè)結(jié)點(diǎn)*s的算法。

21、給定一棵用鏈表表示的二叉樹(shù)，其根指針為t,試寫(xiě)出從根開(kāi)始，按層次遍歷二叉樹(shù)的算法，同層的節(jié)

點(diǎn)按從左到有的次序訪問(wèn)。

22、完成在二叉排序樹(shù)中查找結(jié)點(diǎn)的程序

Bitrcptr*bstscarch(t,k)

Bitreptr*k;

Keytypek;

{if(t==null)

returnnull;