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

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

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

5、每種數據結構都應具備三種基本運算：插入、刪除和搜索。（x）6、數據結構概念包括數據之間的邏

輯結構，數據在計算機中的存儲方式和數據的運算三個方面（v）7、線性表中的每個結點最多只有一個

前驅和一個后繼。（x）

8、線性的數據結構可以順序存儲，也可以鏈接存儲。非線性的數據結構只能鏈接存儲。（x）9、棧和隊

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

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

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

的結點數目都可以為0。（v）15、直接選擇排序是一種不穩定的排序方法。（x）

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

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

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

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

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

23、程序是用計算機語言表述的算法。（v）24、線性表的順序存儲結構是通過數據元素的存儲地址直接反

映數據元素的邏輯關系。（v）25、用一組地址連續的存儲單元存放的元素一定構成線性表。（v）26、堆

棧、隊列和數組的邏輯結構都是線性表結構。（v）

27、給定一組權值，可以唯一構造出一棵哈夫曼樹。（x）28、只有在初始數據為逆序時，冒泡排序所

執行的比較次數最多。（v）29、希爾排序在較率上較直接接入排序有較大的改進。但是不穩定的。

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

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

A8B3

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

A.cB.2c

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

人先序遍歷B.中序遍歷

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

時間復雜度為

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.設單鏈表中結點的結構為

typcdefstructnode{file:〃鏈表結點定義

ElemTypedata;用e:〃數據

structnode*Link;file:〃結點后繼指針

}ListNodc;

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

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

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

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

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設助餅弟中姑占的姑松小

typedefstructnode

(用c:〃鏈表結點定義ElemTypedata;file:〃數據structnode*Link;file:〃結點后繼指針)

ListNodc;

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

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

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

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

A.數據B.數據元素

C.數據結構D.數據類型

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

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

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

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

A.邏輯結構不同B.存儲結構不同

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

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

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

C.不會出現下溢的情況D.不會出現上溢的情況

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

結果

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

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

A.470B.471

C.472D.473

)25.二叉樹中第5層上的結點個數最多為.

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.若需要利用形參宜接訪問實參，則應把形參變量說明為一參數。

A.指針B.引用

C.值D.變希：

)39.在一個單鏈表HL中，若要在指針q所指結點的后面插入一個由指針p所指向的結點，則執行一

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.線性表采用鏈式存儲時，結點的存儲地址

A.必須是不連續的B.連續與否均可

C.必須是連續的D.和頭結點的存儲地址相連續

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

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

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

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

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

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

A.front=front+1

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

尾指針，則執行出隊操作后其頭指針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］,則執行模式

匹配算法時，在最壞情況下的時間復雜度是()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的結點個數為2,度為2的結點個數為1,則度為0的結點個數為

A.4B.5

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

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

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

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

C、O(n2)D、O(nlog2n)()54.用某種排序方法對關鍵字序列(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.透于對動態查找表進行高效率查找的組織結構是.

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

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

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

A指針B引用

D常最

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

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

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

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

驅，若在*勺與*臼之間插入結點*s,則應執行下列哪一個操作

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

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

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

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

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

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

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

A.行號B.列號

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

則判斷隊空的條件為.

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

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

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

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

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

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

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.數據結構是一門研究非數值計算的程序設計問題中計算機的(①)以及它們之間的

(②)和運算的學科A、操作對象B、計算方法C、邏輯存儲D、數據映象A、結構B、關系C、運算D、

算法

()67.數據結構被形式地定義為(K,R),其中IV是(①)的有限集合，R是K±(②)的有限集合

①A、算法B、數據元素C、數據操作D、邏輯結韻

②A、操作B、映象C、存儲D、關系

()68.在數據結構中，從邏輯上可以把數據結構分為

A、動態結構和靜態結構B、緊湊結構和小.緊湊結構

C、線性結構和非線性結構D、內部結構和外部結構

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

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

C、索引存取D、HASH存取

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

①A、找出數據結構的合理性C、分析算法的效率以求改進B、研究算法中的輸入和輸出的關系

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

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

復雜性

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

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

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

②A、可執行性、可移植性和可擴充性C、確定性、有窮性和穩定性

B、可執行性、確定性和有窮性D、易謾性、穩定性和安全性

)72.線性表若采用鏈表存儲結構時，要求內存中可用存儲單元的地址.

A、必須是連續的B、部分池址必須是連續的

C、一定是不連續的D、連續不連續都可以

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

A、線性表的線性存儲結構優于鏈表存儲結構C、棧的操作方式是先進先出

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

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

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

C、*A+iD、&A+i

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

A、參數類型B、參數個數

C、函數類型D、函數變房

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

A、指針B.引用

C、值D、函數

)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.執行下面程序段時，執行S語句的次數為。

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同元素的平均比

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

ANnB、n/2

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

()83.在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執行。

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所指的結點的后面插入一個由指針p所指的結點，則執行。

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所指向結點的后繼結點，則執行。

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.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結點都具有相同的

A、行號B、列號

C、元素值D、地址

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

A>。⑴B、0(n)

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

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

A、棧頂B、棧底

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

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

時，首先應執行語句修改top指針。

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

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

素。(x)

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

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

結構，每個數據元素占用4個存儲單元，第12個數據元素的存儲地址為144,則第1個數據元素的存儲地

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

i+1個元素。(x)

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

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

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

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

(v)45.線性表的鏈式存儲結構是通過指針來間接反映數據元素之間邏輯關系的。(v)46、除插入和刪

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

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

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

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

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

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

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

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

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

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

點。

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

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

A、top++B、top-

CAtop=0D>top

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

43,2,113、2,1,3

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

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

A、前一個B、后一個

C、當前D、后面

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

A、N-2B、N-1

C、ND、N+1

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

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

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

()94.假定一個循環順序隊列的隊首和隊尾指針分別為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、設有一順序隊列sq,容量為5,初始狀態sq.front=sq.rear=0,劃出作完下列操作的隊列及其頭尾指針變化狀

態，若不能入隊，簡述理由后停止。

1)de,b入隊。

2)d,e出隊。

3)ij入隊。

4)b出隊。

5)n,o,p入隊。

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

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

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

5、己知稀疏矩陣如下：

10002

00300

45000

00000

00060

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

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

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

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

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

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

為0)?

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

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

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

123456789101112

HkACDPFJXBQz

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

13、已知某非空二叉樹采用順序存儲結構，樹中結點的數據信息依次存放在一個一維數組中,

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

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

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

一棵二叉樹。

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

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

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

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

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

進行廣度優先遍歷得到的頂點序列是：

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

22、已知結點a,b,c,d及其權值寫出哈夫曼樹的構造過程。

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出發，求它的深度優先生成樹。

2)從頂點E出發，求它的廣度優先生成樹。

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

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

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

第一次劃分結果為：

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

下標：0123456789

比較次數：

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

中寫出每一趟排序的結果。

原始序列4938271397765065

第1趟的結果

第2趟的結果

第3趟的結果

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

序時的變化過程：

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

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

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

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

束時的序列：

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

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

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

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

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

下面是利用中序遍歷的方法統計二叉樹中度為1的結點的個數的算法，算法中設也了一順序存儲結構

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

作。

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

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

34、設有一個關犍碼的輸入序列（55,31,11,37,46,73,63,

02,07）,（1）從空樹開始構造平衡二叉搜索樹，畫出每加入一個新結點時二叉樹的形態。若發生不

平衡，指明需做的平衡旋轉的類型及平衡旋轉的結果。

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

均查找長度。

35、關犍碼的輸入序列｛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點開始按深度優先、

廣度優先遍歷該圖的結果。

畫出該樹，并

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

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

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

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

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

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

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

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

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

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

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

(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、對關鍵字序列(72,87,61,23,94,16,5,58)進行堆排序、快速排序、直接選擇排序，使之關鍵字遞增有

序，請寫出每個排序的前三趟結果。

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

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

頂點？

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

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

否則說明理由。

單鏈表和患循環鏈表的結點結構為datenext

雙向鏈表的結點結構為priordatenext⑴單鏈表(2)單循環鏈表

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

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

⑴根據以上條件構造一散列表，并用線性探測法解決有關地址沖突；

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

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

每一趟的排序結果。

49、已知某二叉樹的順序存儲結構如圖所示，試畫出該二叉樹。

ABCDEF

50、設有一個關鍵碼的輸入序列_________

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

07W)從空樹開始構造平衡二叉搜索樹，畫出每加入一個新結點時二叉樹的形態。

若發生不平衡，指明需做的平衡旋轉的類型及平衡旋轉的結果。

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

51、求下列廣義表運算的結果：

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)請畫出下列廣義表的存儲結構((((a),b)),((0,(d)),(c,f)))

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

54、一棵二叉樹如圖:

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

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

55、具有3個節點的樹和具有3個節點的二叉樹它們的所有不同形態有哪些?

56、將下列森林轉化為二叉樹。

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

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

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

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

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

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

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

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

(v)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

排序是穩定的？哪些是不穩定的，哪個排序平均比較次數最少？哪個排序要求內存容量最多？

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

公式為：

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

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

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

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

62、載入下圖所示的有權圖G,回答下列問題：

I)給出從結點vl出發按深度優先搜索遍歷圖所得的結點序列；

2)給出圖的拓撲序列；

3)給出從結點vl到結點8的最短路徑和關鍵路徑。

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

樹，分別用孩子鏈表和孩子兄弟鏈表法畫出存儲結構。

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

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

67、數組以行優先的順序存儲，設第一個元素的首地址為100,每個元素占3個存儲長度的

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

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

1）自己設計一個合理的散列函數2）用自己設計的函數將上述關鍵字插入到散列表中，畫出其結構；

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

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

后樹的情況：

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

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

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

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

的前驅結點，并說明找到結果的原因。

75、什么是數據結構?

76、試比較線性表的順序存儲結構和鏈式存儲結構的優缺點。

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

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

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

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

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

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

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

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

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、設一個有向圖為G=(V,E),其中V={vl,v2,v3,v4),E=

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

矩陣、鄰接表和逆鄰接農。

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

h

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

成最小生成樹的各條邊的并入順序。畫出最小生成樹。并寫出廣度優先和深度優先的結點遍歷順序。

什么時動態查找，什么叫平均查

找長度,

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

找成功的平均查找長度。

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

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

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

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

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

平均查找長度。

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

15386184

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

30,28,5,10},分別畫出冒泡排序、快速排序過程的圖示。

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

每一趟的排序結果。

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

序，請寫出每個排序的前三趟結果。

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

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

voiddel(structnode*head)

{q=head;

p=q->ncxt;

\vhilc(()&&())

(q=p；

；)

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

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

⑴寫出下列程序的功能。

(2)當鏈表中結點數分別為1和6(不包括頭結點)時，請寫出程序中while循環體的執行次數。

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、寫出計算樹葉子結點的算法。

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

8、試寫出以帶頭結點單鏈表為存儲結構實現簡單選擇排序的算法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.試編寫一算法，以完成在帶頭結點單鏈表L中第i個位置前插入元素X的操作。

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

請編寫算法計算一二叉樹所有度數為2的結點個數。

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

法。

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

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

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

遞歸算法。

15、設計一個算法，刪去串中第I個字符開始的J個字符，說明算法所用的存儲結構，并估計算法的執行

時間。

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

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

一半字符先依次進棧)。

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

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

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

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

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

slVs2,則輸出一個負數。不能用strcmp函數。

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

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

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

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

Bitrcptr*bstscarch(t,k)

Bitreptr*k;

Keytypek;

{if(t==null)

returnnull;