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

鏈式存儲表示。（X）3、線性表若采用鏈式存儲表示時所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。

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

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

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

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

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

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

序樹中一個結(jié)點，再重新插入上去，一定能得到原來的二叉排序樹。（x）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A8B3

C5D9()】0.在含有n個項點有e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為。

A.cB.2c

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

人先序遍歷B.中序遍歷

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

時間復雜度為

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

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

A.二叉排序樹B.滿二叉樹

C.完全二叉樹D.平衡二叉樹()14.一個無向連連通圖的生成樹是含有該連通圖的全部項點的。

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

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

最好采用方法

A.快速排序B.堆排序

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

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

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

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

}ListNodc;

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

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

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

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

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é)點定義ElemTypedata;file:〃數(shù)據(jù)structnode*Link;file:〃結(jié)點后繼指針)

ListNodc;

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

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

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

)18.計算機識別、存儲和加工處理的對象被統(tǒng)稱為.

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

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

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

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

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

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

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

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

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

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

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

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

結(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按行順序存儲，其中每個元素占1個存儲單元。若AHH11的存儲地址為420,

A[3][3]的存儲地址為446,貝JA[5][5]的存儲地址為

A.470B.471

C.472D.473

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

A>。⑴B、O(n)

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

)36.假定一?個順序隊列的隊首和隊尾指針分別為f和r,則判斷隊空的條件為一。

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

C、f==OD、f==r

)37.從堆中刪除一個元素的時間復雜以為一。

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

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

)38.若需要利用形參宜接訪問實參，則應把形參變量說明為一參數(shù)。

A.指針B.引用

C.值D.變希：

)39.在一個單鏈表HL中，若要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，則執(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.在一個順序隊列中，隊首指針指向隊首元素的一位置。

A.前一個B.后一個

C.當前D.最后一個

)41.向二叉搜索樹中插入一個元素時，其時間復雜度大致力一。

AO(l)BO(log2n)

CO(n)DO(nlog2n)

)42.算法指的是

計算機程序B.解決問題的計算方法

C.排序算法D.解決問題的有限運算序列

)43.線性表采用鏈式存儲時，結(jié)點的存儲地址

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

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

)44.將長充為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為

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

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

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

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

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

A.front=front+1

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

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

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

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

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

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

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

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

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

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

C.只能是原子D.可以是子表或原子050.從堆中刪除一個元素的時間復雜

度為。02335

A、O⑴B、O(n)

C、O(log2n)D

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

A.4B.5

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

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

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

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

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

時，序列的變化情況是如下:

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.透于對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是.

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

C.二叉排序樹D.線性鏈表

)56.若需要利用形參直接訪問實參，則應把形參變量說明為.參數(shù)。

A指針B引用

D常最

)57.鏈式棧與順序棧相比,一個比較明顯的優(yōu)點是0

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

C,不會出現(xiàn)棧空的情況D.刪除操作更加方便

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

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

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依次進棧，則出棧次序不可能出現(xiàn)種情況。

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

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

)60.線性鏈表不具有的特點是.

A.隨機訪問B.不必事先估計所需存儲空間大小

C.插入與刪除時不必移動元素D.所需空間與線性表長度成正比

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

A.行號B.列號

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

則判斷隊空的條件為.

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

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

)63.棧的插入和刪除操作在..進行.

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

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

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

A.后兩個B.后一個

c.當前D.前一個

()65.下面算法的時間復雜度為一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)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的(①)以及它們之間的

(②)和運算的學科A、操作對象B、計算方法C、邏輯存儲D、數(shù)據(jù)映象A、結(jié)構(gòu)B、關(guān)系C、運算D、

算法

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

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

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

()68.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為

A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和小.緊湊結(jié)構(gòu)

C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

()69.線性表的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu)，線性表的鏈式存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu)

A、隨機存取B、順序存取

C、索引存取D、HASH存取

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

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

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

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

復雜性

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

①A、計算方法B、排序方法

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

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

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

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

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

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

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

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

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

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

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

C、*A+iD、&A+i

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

A、參數(shù)類型B、參數(shù)個數(shù)

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

)76.若需要利用形參直接訪問實參，則應把形參變星說明為參數(shù)

A、指針B.引用

C、值D、函數(shù)

)77.下面程序段的時間復雜度為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í)行下面程序段時，執(zhí)行S語句的次數(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.下面算法的時間復雜度為。

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

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

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

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

前依次后移

個元素。

A、n-iB、n-i+1

C、n-i-lD、i

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

ANn-iB>n-i+1

C、n-i-lD、i

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

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

ANnB、n/2

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

()83.在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(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.在一個單鏈表HL中，若要在指針q所指的結(jié)點的后面插入一個由指針p所指的結(jié)點，則執(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.在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(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.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點都具有相同的

A、行號B、列號

C、元素值D、地址

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

A>。⑴B、0(n)

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

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

A、棧頂B、棧底

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

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

時，首先應執(zhí)行語句修改top指針。

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

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

素。(x)

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

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

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

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

i+1個元素。(x)

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

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

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

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

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

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

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

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

操作稱為串的模式匹配。(v)50、深度為h的非空二叉樹的第i層最多有2i-l個結(jié)點。(x)

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

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

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

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

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

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

點。

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

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

A、top++B、top-

CAtop=0D>top

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

43,2,113、2,1,3

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

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

A、前一個B、后一個

C、當前D、后面

()92.當利用大小為N的一維數(shù)組順序存儲一個循環(huán)隊列時，該隊列的最大長度為。

A、N-2B、N-1

C、ND、N+1

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

A、前移一位隊首指針B、后移一位隊首指針

C、取出隊首指針所指位置上的元素D、取出隊尾指針所指位置上的元素

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

C^f==OD^f==r

()95.假定一個鏈隊的隊首和隊尾指針分別為front和rear,則判斷隊空的條件是。

A、front==rearBfrontMNULL

C、rear!=NULLD、front==NULL四、應用題：

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

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

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

1)de,b入隊。

2)d,e出隊。

3)ij入隊。

4)b出隊。

5)n,o,p入隊。

3、設(shè)有一個順序棧S,元素$“2*4&6依次進棧,如果6個元素的出棧順序為s2,s3,s4,s6,s5,

si,則順序棧的容：彘至少應為多少？

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

5、己知稀疏矩陣如下：

10002

00300

45000

00000

00060

靖寫出該稀疏矩陣三元組表示。

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

7、請畫出下面廣義表相應的加入表頭結(jié)點的單鏈表表示,

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

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

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

為0)?

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

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

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

123456789101112

HkACDPFJXBQz

請指出結(jié)點P的父結(jié)點，左子女，右子女。給出下列二又樹的先序序列。

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

ABcnDFEnnGnnHn□,該二義樹的中序遍歷序列為：

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

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

一棵二叉樹。

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

4,5,6六個結(jié)點且以1為根，深度為4的二叉排序樹。

17、什么是線索二叉樹？為什么要線索化?

18、有n個頂點的有向連通圖最多有多少條邊?最少有多少條邊？

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

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

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

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

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

畫出圖G,畫出圖G的鄰接表。

24、考慮下圖：

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

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

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

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

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

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

27、用二分法對一個長度為10的有序表進行查找，填寫查找每個元素需要的比較次數(shù)。

下標：0123456789

比較次數(shù)：

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

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

原始序列4938271397765065

第1趟的結(jié)果

第2趟的結(jié)果

第3趟的結(jié)果

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

序時的變化過程：

1）歸并排序每歸并一次書寫一個次序。

2）快速排序每劃分一次書寫一個次序。

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

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

束時的序列：

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

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

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

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

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

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

的堆棧STACK棧頂指針為top,請在算法的空缺處填入適當內(nèi)容，使之能正常工

作。

33、設(shè)有一個順序棧S,元素si,s2,s3,s4,s5,s6依次進棧,如果6個元素的出棧順序為s2,s3,s4,s6,s5,si,則順

序棧的容量至少應為多少？

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

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

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

⑵計算該平衡二叉搜索樹在等概率下的查找成功的平均查找長度和查找不成功的平

均查找長度。

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

等概率下查找成功的平均查找長度。

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

Head(Tail(Head(Tail(Tail(A)))))37,下圖是用鄰接表存儲的圖，畫出此圖，并寫出從C點開始按深度優(yōu)先、

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

畫出該樹，并

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

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

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

a)它們在先序遍歷和中序遍歷時,得到的結(jié)點訪問序列相同；

b)它們在后序遍歷和中序遍歷時,得到的結(jié)點訪問序列相同；

0它們在先序遍歷和后序遍歷時,得到的結(jié)點訪問序列相同。

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

a)在P結(jié)點后插入S結(jié)點的語句序列是

b)在P結(jié)點前插入S結(jié)點的語句序列是

c)在表首插入S結(jié)點的語句序列是

d)在表尾插入S結(jié)點的語句序列是

(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、已知樹T的先序遍歷序列為ABCDEFGHIJKL,后序遍歷序列為CBEFDJIKLHGA,請畫

出樹Tc

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

序，請寫出每個排序的前三趟結(jié)果。

45、請畫出廣義表D的圖形表示

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

頂點？

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

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

否則說明理由。

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

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

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

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

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

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

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

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

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

ABCDEF

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

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

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

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

⑵計算該平衡二叉搜索樹在等概率下的查找成功的平均瓷找長度和查找不成功的平均查找長度。

51、求下列廣義表運算的結(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>畫出下列廣義表的圖形表示：

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

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

2)請寫出下面鏈表表示的廣義表

54、一棵二叉樹如圖:

1）寫出對此樹進行中序、先序、后續(xù)遍歷時得到的結(jié)點序歹人

2）畫出樹的后序線索二叉樹。

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

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

57、已知一個圖如下所示，寫出其臨接矩陣,

則可以得到所有頂點序列為什么？

61、設(shè)與一棵樹T所對應的二叉樹為BT,則與T中的葉子結(jié)點所對應的BT中的結(jié)點也一定是葉子結(jié)點。

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

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

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

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

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

(v)

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

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

會失效掉隨機存取功能。(x)

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

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

若一個有向圖的鄰接矩陣中，對角線以下元素均為0,則該圖的拓撲有序序列必定存在。(v)

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

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

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

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

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

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

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

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

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

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

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

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

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

公式為：

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

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

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

61、何為隊列上溢？一?般用什么方法解決，簡述之。

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

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

2)給出圖的拓撲序列；

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

對于下圖，請給出對應白........12….一；鄰接表表示和逆鄰接表表

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

65、對于下圖的樹，請分別用中序、先序的方法寫出其遍歷結(jié)果。

2）求初等概率情況下查找july的查找長度。

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

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

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

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

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

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

后樹的情況：

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

72、請畫出下列二叉樹的中序線索化前趨鏈樹，后序線索化后繼鏈樹。

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

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

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

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

76、試比較線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。

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

78、將兩個棧存入數(shù)組中應如何安排最好?這時棧空棧滿的條件是什么？

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

空間，使得對任一個棧，僅當這部分空間全滿時才發(fā)生上溢。

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

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

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

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

BE

后根遍歷。

84、

85、有n個頂點的有向連通圖最多有多少條邊?最少有多少條邊？

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

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

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

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

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

89、請給出下圖的鄰接矩陣和鄰接表。

h

90、請畫出下圖中的極大連通子圖。

成最小生成樹的各條邊的并入順序。畫出最小生成樹。并寫出廣度優(yōu)先和深度優(yōu)先的結(jié)點遍歷順序。

什么時動態(tài)查找，什么叫平均查

找長度,

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

找成功的平均查找長度。

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

測的開放地址法解決沖突，則在該散列表上進行檢索的平均檢索長度為多少，若利用連地址法處理沖

突，則在該散列表上進行檢索的平均查找長度為多少？設(shè)地址空間為9。請畫出算列表。

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

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

平均查找長度。

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

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},分別畫出冒泡排序、快速排序過程的圖示。

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

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

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

序，請寫出每個排序的前三趟結(jié)果。

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

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é)點的雙向循環(huán)鏈表的頭才旨針,

⑴寫出下列程序的功能。

(2)當鏈表中結(jié)點數(shù)分別為1和6(不包括頭結(jié)點)時，請寫出程序中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、寫出按后序序列遍歷中序線索樹的算法.

5、寫出計算樹深度的算法。

6、寫出計算樹葉子結(jié)點的算法。

7、寫出計算寧符串長度的算法。

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

⑴該算法完成什么功能？

⑵算法中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.試編寫一算法，以完成在帶頭結(jié)點單鏈表L中第i個位置前插入元素X的操作。

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

請編寫算法計算一二叉樹所有度數(shù)為2的結(jié)點個數(shù)。

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

法。

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

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

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

遞歸算法。

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

時間。

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

XYZYX都算是中心對稱的字符串。要求用盡可能少的時間完成判斷(提示：將

一半字符先依次進棧)。

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

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

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

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

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

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

20、寫出在中序線索二叉樹中結(jié)點*臼的右子樹中插入一個結(jié)點*s的算法。

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

點按從左到有的次序訪問。

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

Bitrcptr*bstscarch(t,k)

Bitreptr*k;

Keytypek;

{if(t==null)

returnnull;