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

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

選擇題

L1-11根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計算出該元素存儲地址的存儲方法是()

A)順序存儲方法

B)鏈?zhǔn)酱鎯Ψ椒?/p>

C)索引存儲方法

D)散列存儲方法

【2-8】下面程序段的時間復(fù)雜度是()for(i=0;i<n;i++)for(j=l;j<m;j++)A[i][j]=O;

A)O(n)

B)O(m+n+l)

C)0(m+n)

D)0(m*n)

13-414]下面程序段的時間復(fù)雜度為()。i=l;while(i〈=n)i=i*2;

A)0(log2n)

B)O(n)

00(n)

D)0(nlog2n)

14-421]下面程序段的時間復(fù)雜度為()0for(i=l;i<=m;++i)for(j=l;j<=n;++j)A[i,j]=i*j;

A)0(m2)

B)0(n2)

C)0(m*n)

D)0(m+n)

15-434]在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為

A)內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)

B)靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)

C)線性結(jié)構(gòu)與非線性結(jié)構(gòu)

D)緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)

16-4441若需要利用形參直接訪問實參，則應(yīng)把形參變量說明為()參數(shù)。

A)指針

B)引用

C)值

D)變量

17-445]下面程序段的時間復(fù)雜度為()for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;

A)0(m2)

B)0(n2)

C)0(m*n)

D)0(m+n)

【8-446]下面程序段的時間復(fù)雜度為()intf(unsignedintn){if(n==0n==1)return1;elsereturn

n*f(n-1);}

A)0(l)

B)0(n)

C)0(n2)

D)0(n!)

110-4601下列哪一個不屬于算法的設(shè)計目標(biāo)()。

A）可讀性

B）可執(zhí)行性

C）健壯性

D）高空間效率

[11-461】下列哪一個不是數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容（）

A）數(shù)據(jù)間的邏輯關(guān)系

B）數(shù)據(jù)大小

C）數(shù)據(jù)的存儲方式

D）數(shù)據(jù)的運算

112-468J算法指的是（）

A）計算機(jī)程序

B）解決問題的計算方法

C）排序算法

D）解決問題的有限運算序列

L14-4821某算法的空間花費s（n）=100nlog2n+0.5nL5+1000n+2000,其空間復(fù)雜度為【】

A）O（l）

B）O（n）

C）O（n,B）

D）0（nlog2n）

118-5022下面程序段的時間復(fù)雜度為（）。for（inti=0;i<m;i++）for（intj:==0;j<n;j++）a[I][j]=i*j;

A）o（m2）

B）0（n2）

C）0（m*n）

D）0（m+n）

119-514]在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成（）

A）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

B）線性結(jié)構(gòu)和非線性結(jié)構(gòu)

C）緊湊結(jié)構(gòu)和非緊揍結(jié)構(gòu)

D）動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

[20-529]若結(jié)點的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲結(jié)構(gòu)為（）

A）順序存儲結(jié)構(gòu)

B）鏈?zhǔn)酱鎯Y(jié)構(gòu)

C）索引存儲結(jié)構(gòu)

D）散列存儲結(jié)構(gòu)

11-413】在一個單鏈表中，已知q所指結(jié)點是P所指結(jié)點的前驅(qū)，若在P、q之間插入s結(jié)點，則執(zhí)行（）操

作。

A）s->next=p-next;p->next=s;

B）q->next=s;s->next=p;

C）p->next=s->next;s->next=p;

D）p->next=s;s->next=q;

（2-416]若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（）存儲方式最

節(jié)省時間。

A）單鏈表

B）雙鏈表

C）單向循環(huán)鏈表

D）順序表

13-4171使用雙向鏈表存儲數(shù)據(jù)，其優(yōu)點是可以（）。

A)提高檢索速度

B)很方便地插入和刪除數(shù)據(jù)

C)節(jié)約存儲空間

D)很快回收存儲空間

[4-4181單鏈表中，增加頭結(jié)點的目的是為了()。

A)方便運算的實現(xiàn)

B)標(biāo)識單鏈表

C)使單鏈表中至少有一個結(jié)點

D)用于標(biāo)識起始結(jié)點的位置

[5-4221帶頭結(jié)點的單鏈表h為空的判斷條件是()。

A)h==NULL

B)h->next==NULL

C)h->next==h

D)h!=NULL

[6-4301在一個單鏈表HL中，若要向q所指結(jié)點之后插入一個由指針p指向的結(jié)點，則執(zhí)行

A)HL=p;p->next=HL

B)p->next=HL;HL=p

C)P->next=q->next;q->next=p

D)p->next=q->next;q=p>next

17-4351采用線性鏈表表示一個向量時，要求占用的存儲空間地址

A)必須是連續(xù)的

B)部分地址必須是連續(xù)的

0一定是不連續(xù)的

D)可連續(xù)可不連續(xù)

(8-4361采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為(

A)n

B)n/2

0(n-l)/2

D)(n+l)/2

19-437]在一個單鏈表中，若q結(jié)點是p結(jié)點的前驅(qū)結(jié)點，若在q與P之間插入結(jié)點S,則執(zhí)行(

A)s-*next=p-?-next;p-*next=s;

B)p->next=s;s-*next=q;

C)p-*next=s->next;s-?next=p;

D)q-?next=s;s-*next=p;

[12-447】線性表若是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址()o

A)必須是連續(xù)的

B)部分地址必須是連續(xù)的

0一定是不連續(xù)的

D)連續(xù)或不連續(xù)都可以

113-448J在一個長度為n的版序表的任一位置插入一個新元素的漸進(jìn)時間復(fù)雜度為()。

A)0(n)

B)0(n/2)

C)0(l)

D)0(n2)

[14-449]帶頭結(jié)點的單鏈表first為空的判定條件是：()

A)first==NULL

B)first—>next==NULL

C)first—〉next==first

D)first!=NU1L

115-462】單鏈表的優(yōu)點是()。

A)支持隨機(jī)存取

B)內(nèi)存空間利用率高

C)插入和刪除操作不需移動大量的元素

D)元素存儲地址是連續(xù)的

116-463］假設(shè)指針p指向單鏈表中的某一結(jié)點，若把P指針后面的結(jié)點刪除，只需修改下列哪個指針值即可

()。

A)p=p->next;

B)p->next=p->next->next

C)p=p->next->next;

D)p->next=p;

117-4691線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址()

A)必須是不連續(xù)的

B)連續(xù)與否均可

C)必須是連續(xù)的

D)和頭結(jié)點的存儲地址相連續(xù)

［18-470］符長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為()

A)O(1)

B)0(n)

C)0(m)

D)0(m+n)

119-483】在單項鏈表中刪除一個指定結(jié)點的后繼的時間復(fù)雜度為［］

A)O(n)

B)0(nlog2n)

00(1)

D)O(Mn)

(20-4931靜態(tài)鏈表中指針表示的是()

A)下一元素的地址

B)內(nèi)存儲器的地址

C)下一元素在數(shù)組中的位置

D)左鏈或右鏈指向的元素的地址

121-494］若長度為n的線性表采用順序存儲結(jié)構(gòu)，則在表中第i個位置(l<i<=n+l)插入一個新元素的算

法的時間復(fù)雜度為()

A)0(0)

B)O(l)

C)O(n)

D)0(n2)

［23-505］利用雙向鏈表作線性表的存儲結(jié)構(gòu)的優(yōu)點是()。

A)便于單向進(jìn)行插入和刪除的操作

B)便于雙向進(jìn)行插人和刪除的操作

C)節(jié)省空間

D)便于銷毀結(jié)構(gòu)釋放空間

124-509J向具有n個結(jié)點的堆中插入一個新元素的時間復(fù)雜度為()。

A)0(l)

B)O(n)

C)0(log2n)

D)0(nlog2n)

125-515］在以單鏈表為存儲結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用()

A)數(shù)據(jù)元素的相鄰地址表示

B)數(shù)據(jù)元素在表中的序號表示

C)指向后繼元素的指針表示

D)數(shù)據(jù)元素的值表示

126-516】設(shè)p指向單鏈表中的一個結(jié)點，s指向待插入的結(jié)點，則下述程序段的功能是()s->next

=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;

A)結(jié)點*p與結(jié)點*s的數(shù)據(jù)域互換

B)在p所指結(jié)點的元素之前插入元素

C)在p所指結(jié)點的元素之后插入元素

D)在結(jié)點*p之前插入結(jié)點*s

L27-520J多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲方式是因為()

A)數(shù)組的元素處在行和列兩個關(guān)系中

B)數(shù)組的元素必須從左到右順序排列

O數(shù)組的元素之間存在次序關(guān)系

D)數(shù)組是多維結(jié)構(gòu)，內(nèi)存是一維結(jié)構(gòu)

128-5301在長度為n的順序表的第i(l<i<n+l)個位置上插入一個元素，元素的移動次數(shù)為()

A)n-i+1

B)n-i

C)i

D)i-1

130-544】在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)”刪除x的后繼”的語句是()

A)p=p->next;

B)p->next=p->next->next;

C)p->next=p;

D)p=p->next->next;

(32-563J求單鏈表中當(dāng)前結(jié)點的后繼和前驅(qū)的時間復(fù)雜度分別是()

A)O(n)和。⑴

B)O(1)和0(1)

C)O(1)和0(n)

D)O(n)和0(n)

135-5731能進(jìn)行二分查找的線性表,必須以()

A)順序方式存儲,且元素按關(guān)鍵字有序

B)鏈?zhǔn)椒绞酱鎯?且元素按關(guān)鍵字有序

C)順序方式存儲,且元素按關(guān)鍵字分塊有序

D)鏈?zhǔn)椒绞酱鎯?且元素按關(guān)鍵字分塊有序

(1-424］設(shè)計一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用()數(shù)據(jù)結(jié)構(gòu)最佳。

A)線性表的順序存儲結(jié)構(gòu)

B)棧

0隊列

D)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

12-427】在一個具有n個單元的順序棧中，假定以地址低端(即下標(biāo)為0的單元)作為棧底，以top作為棧頂

指針，則當(dāng)作退棧處理時，top的變化為()。

A)top不變

B)top=0

C)top=top+1

D)top=top-l

13-428】鏈棧與順序棧相比，有一個較明顯的優(yōu)點是()。

A)通常不會出現(xiàn)棧滿的情況

B)通常不會出現(xiàn)枝空的情況

C)插入操作更加方便

D)刪除操作更加方便

14-4411招一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用(

A)棧

B)隊列

C)循環(huán)隊列

D)優(yōu)先隊列

15-442】在循環(huán)隊列中用數(shù)組存放隊列元素，其隊頭和隊尾指針分別為front和rear,則當(dāng)前隊

列中的元素個數(shù)是(

A)(front-rear+1)%m

B)(rear-front+1)%m

C)(front-rear+m)%m

D)(rear-front+m)%in

(6-450J當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為()。

A)n—2

B)n—1

C)n

D)n+1

17-464】在循環(huán)隊列中(少用一個存儲空間)，隊滿的條件是()

A)(rear+1)%maxsize==front

B)raer==front

C)(front+1)%maxsize==rear

D)rear==0

19-472】設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操

作后其頭指針front值為()

A)front=front+l

B)front=(front+1)%(m-1)

C)front=(front-l)%m

D)front=(front+1)%m

110-484]在n(n>0)個元素的順序枝中刪除1個元素的時間復(fù)雜度為[]

A)O(l)

B)0(x/n)

C)0(nlog2n)

D)O(n)

[11-495】一個棧的輸入序列為ABCDE,則不可能出現(xiàn)的輸出序列是()

A)ABCDE

B)EDCBA

OCABED

D)BADGE

112-506】設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點的結(jié)構(gòu)為(data,next),且top是指向棧頂?shù)闹羔槨Ｈ粝朐阪準(zhǔn)綏５臈ｍ敳迦胍粋€

由指針S所指的結(jié)點，則應(yīng)執(zhí)行()操作。

A)top->next=s;

B）s->next=top->next;top->next=s;

C）s->next=top;top=s:

D）s->next=:=top;top===top->next;

L14-517J棧和隊列都是（）

A）限制存取位置的線性結(jié)構(gòu)

B）順序存儲的線性結(jié)構(gòu)

C）鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)

D）限制存取位置的非線性結(jié)構(gòu)

115-518］若數(shù)組s［0..n-1］為兩個棧si和s2的共用存儲空間，且僅當(dāng)s［0..nT］全滿時，各棧才不能進(jìn)行進(jìn)

棧操作，則為這兩個棧分配空間的最佳方案是：si和s2的棧頂指針的初值分別為（）

A）1和n+1

B）1和n/2

C）—1和n

D）-1,和n+1

116-531】對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為（）

A）順序表

B）用頭指針表示的單循環(huán)鏈表

C）用尾指針表示的單循環(huán)鏈表

D）單錐表

117-5321若進(jìn)棧序列為a,b,c,則通過入出棧操作可能得到的a,b,c的不同排列個數(shù)為（）

A）4

B）5

06

D）7

119-559］棧的插入和刪除操作在（）進(jìn)行。

A）棧頂

B）棧底

C）任意位置

D）指定位置

120-5601假定一個鏈隊的隊首和隊尾指針分別為front和rear,則判斷隊空的條件為（）。

A）front==rear

B）front!=NULL

Orear!=NULL

D）front==NULL

121-565］若允許表達(dá)式內(nèi)多種括號混合嵌套，則為檢查表達(dá)式中括號是否正確配對的算法，通常選用的輔助

結(jié)構(gòu)是（）

A）棧

B）線性表

C）隊列

D）二叉排序樹

12-431］在一棵深度為5的完全二叉樹中，至少含有個結(jié)點。1+2+4+8+1

A）15

B）16

030

D）31

C3-452J在一棵樹中，（）沒有前驅(qū)結(jié)點

A）分支結(jié)點

B）葉結(jié)點

C）樹根結(jié)點

D）空結(jié)點

14-453】在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（）。

A）2

B）1

C）0

D）-l

15-4651某非空二叉樹共有葉結(jié)點15個，沒有度為1的結(jié)點，則該樹共有（）個結(jié)點。（［性質(zhì)1］二

叉樹上終端結(jié)點數(shù)等于雙分支結(jié)點數(shù)加lo）

A）29

B）28

C）27

D）不能確定

16-466】某二叉樹的中序遍歷為：bdaec,后序遍歷為：dbeca,則前序遍歷為（）。

A）abdce

B）adbce

C）abdec

D）bdace

17-476］在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為（）

A）4

B）5

06

D）7

（8-4871高度為h（h>0）的二叉樹最少有個結(jié)點［］

A）h

B）h-1

C）h+1

D）2h

19-497】對二叉樹的結(jié)點從1開始編號，要求每個結(jié)點的編號大于其左孩子（如果有的話）的編號，而小于其

右（孩子如果有的話）的編號，則可以采用（）次序的遍歷實現(xiàn)二叉樹的結(jié)點編號

A）前序

B）中序

C）后序

D）層次遍歷

112-508］一棵具有35個結(jié)點的完全二又樹的高度為（）。假定空樹的高度為一1。

A）5

B）6

C）7

D）8

113-5371下列陳述中正確的是（）

A）二叉樹是度為2的有序樹

B）二叉樹中結(jié)點只有一個孩子時無左右之分

C）二叉樹中必有度為2的結(jié)點

D）二叉樹中最多只有兩棵子樹，并且有左右之分

114-5491一棵含18個結(jié)點的二叉樹的高度至少為（）

A）3

B)4

05

D)6

【15-550】已知二叉樹的先序序列為ABDECF,中序序列為DBEAFC,則后序序列為()

A)DEBAFC

B)DEFBCA

ODEBCFA

D)DEBFCA

LI6-5691除第一層外，滿二叉樹中每一層結(jié)點個數(shù)是上一層結(jié)點個數(shù)的()

A)1/2倍

B)1倍

02倍

D)3倍

12-425］在具有n個葉子的哈夫曼樹中，其結(jié)點總數(shù)為()o

A)不確定

B)2n

C)2n+1

D)2n-1

13-4299已知10個數(shù)據(jù)元素為(54,28,16,34,73,62,95,60,26,43),按依次插入結(jié)點的方法生成一

棵二叉排序樹后，查找值為62的結(jié)點所需用比較的次數(shù)為()。

A)2

B)3

04

D)5

［4-4321從一棵深度為h的二叉搜索樹中查找一個元素時，其時間復(fù)雜度為。

A)O(h)

B)0(h2)

C)0(log2h)

D)0(n*log2h)

15-433］由權(quán)值分別為3,8,10,2,6的葉子結(jié)點生成一棵哈夫曼樹，該樹中雙分支結(jié)點數(shù)為

A)2

B)3

04

D)5

L12-5741為使平均查找長度達(dá)到最小,當(dāng)由關(guān)鍵字集合｛05,11,21,25,37,40,41,62,84｝構(gòu)建二叉排序樹時，第

一個插入的關(guān)鍵字應(yīng)為()

A)05

B)37

C)41

D)62

12-455］在有向圖中每個頂點的度等于該頂點的()。

A)入度

B)出度

C)入度與出度之和

D)入度與出度之差

［11-523］若＜vi,vj＞是有向圖的一條邊，則稱()

A)vi鄰接于vj

15）丫上鄰接于\”

C）vi和vj相互鄰接

D）vi與vj-不相鄰接

L15-551J無向圖中一個頂點的度是指圖中（）

A）通過該頂點的簡單路徑數(shù)

B）與該頂點相鄰接的頂點數(shù)

C）通過該頂點的回路數(shù)

D）與該頂點連通的頂點數(shù)

I19-576J下列說法正確的是（）o

A）無向圖中的極大連通子圖叫做連通分量

B）有向圖中的極大連通子圖叫做連通分量

0無向圖中的極大強(qiáng)連通子圖叫做強(qiáng)連通分量

D）有向圖中的極大強(qiáng)連通子圖叫做強(qiáng)連通分量

某無序表具有N個數(shù)據(jù)，若采用順序查找算法，且每個數(shù)據(jù)查找的概率相等，那么查找失敗時，平均查找長度

ASL=（）

A）N-1

B）N

C）（N+l）/2

D）N（N-l）/2

14-4671能采用二分查找的數(shù)據(jù)結(jié)構(gòu)是（）

A）線性表

B）二叉樹

C）有序表

D）哈希表

19-558】在一個長度為n的線性表中順頃序查找值為x的元素時，在等概率情況下查找成功時的平均查找長度

為（）o

A）n

B）n/2

0（n+l）/2

D）（n-l）/2

[10-577】對線性表進(jìn)行二分法查找，其前提條件是（）.

A）線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序

B）線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序

C）線性表以順序方式存儲，并且按關(guān)鍵碼值排好序

D）線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序

12-456]在基于排序碼比較的排序算法中，（）算法的最壞情況下的時間復(fù)雜度不高于O（nlog2n）。

A）起泡排序

B）希爾排序

C）歸并排序

D）快速排序

14-489】冒泡排序在最好情況下時間復(fù)雜度為[]

A）O（l）

B）0（nlog2n）

C）0（n）

D）O（n2）

16-527】如果在排序過程中，每次均將一個待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的子表中的適當(dāng)位

置，則該排序方法稱為（）

A)插入排序

B)歸并排序

C)冒泡排序

D)堆排序

[10-572】快速排序在最壞情況下的時間復(fù)雜度是()

A)0(n21og2n)

B)0(n2)

C)0(nlog2n)

D)0(log2n)

111-579]下列排序算法中()算法是不穩(wěn)定的。

A)起泡排序

B)直接插入排序

C)基數(shù)排序

D)快速排序

112-580】一個對象序列的排序碼為{46,79,56,38,40,84),采用快速排序(以位于最左位置的對象為

基準(zhǔn)而)得到的第一次劃分結(jié)果為：

A){38,46,79,56,40,84}

B){38,79,56,46,40,84}

C){40,38,46,79,56,84}

D){38,46,56,79,40,84}

38,40,46,56,79,84

113-6031某內(nèi)部排序方法的穩(wěn)定性是指()

A)該排序算法不允許有相同的關(guān)鍵字記錄

B)該排序算法允許有相同的關(guān)鍵字記錄

C)平均時間為O(nlogn)的排序方法

D)以上都不對

[14-6041對關(guān)鍵碼序列28,16,32,12,60,2,5,72快速排序，從小到大的一次劃分結(jié)果為()

A)(2,5,12,16)28(60,32,72)

B)(5,16,2,12)28(60,32,72)

C)(2,16,12,5)28(60,32,72)

D)(5,16,2,12)28(32,60,72)

填空題

已知指針P指向單鏈表中某個結(jié)點，則語句P->next=p->next->next的作用是刪除P結(jié)點的直接后繼

結(jié)點一°

某二叉樹中序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則前序序列是一―EACBD

GF

一棵深度為h的滿二叉樹上的結(jié)點總數(shù)為上一棵深度為h的完全二叉樹上的結(jié)點總數(shù)的最小值為

h__,最大值為2"-1。

3個結(jié)點可構(gòu)成_五一棵不同形態(tài)的樹。

3個節(jié)點可以構(gòu)成—五一棵不同形態(tài)的二叉樹。

具有n個node的二叉樹的形態(tài)有

1/(n+l)C(n,2n)

取n=3有所求

=1/4*3!=5

對于一棵具有n個結(jié)點的二叉樹，當(dāng)它為一棵—完全一二叉樹時具有最小高度，即為logm+1,當(dāng)它為一棵

單支樹時具有—最大—高度，即為一n一。

對于一棵具有30個結(jié)點的二叉樹，若一個結(jié)點的編號為5,則它的左孩子結(jié)點的編號為10.右孩子結(jié)

點的編號為11.雙親結(jié)點的編號為(5T)/2=2。

已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。

前序序列：A,B,C,D,E,F,G,H,I,J

中序序列：C,B,A,E,F,D,I,H,J,G

后序序列：C,B,F,E,I,J,H,G,D,A

某二叉樹中序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則前序序列是EABCDGF。

編程題

按所給函數(shù)頭編寫一個算法，從表頭指針為HL的單鏈表中查找出具有最大值的結(jié)點，該最大值由函數(shù)返回，若

單鏈表為空則中止運行。

ElemTypeMaxValue(LNode*HL)

(

if(HL==NULL){

cerr?“ListisEmpty!”?endl;

exit(1);

)

else{

ElemTypemax=HL->data;

for(HL=HL->next;HL;HL=HL->next){

if(max<HL->data)max=HL->data;

}

returnmax;

)

)

建立一個順序存儲的線性表，并實現(xiàn)線性表的就地逆置，并打印測試逆置前后的線性表。

ElemTypelist[6]=<1,3,5,7,9,6};LNode*HL=newLNode;//表頭

inti;LNode*tmp;

for(i=0,tmp=HL;i<6;){〃建立鏈?zhǔn)酱鎯€性表

tmp->data=list[i];

tmp->next=NULL;

cout<〈''<<tmp->data;

if(i<5){

tmp->next=newLNode;

tmp=tmp->next;

)

)

LNode*cur=HL,*pre=NULL;〃就地逆置

while(cur){

tmp=cur->next;

cur->next=pre;pre=cur;

cur=tmp;

)

while(pre){cout<〈''pre->data;pre=pre->next;}//打印

已知指針ha和hb分別指向兩個單鏈表的頭結(jié)點，編寫完整算法完成將ha和hb連接在一起，即令其中一個表

的首元結(jié)點連接在另一個表的最后一個結(jié)點之后，he指向鏈接后的單鏈表。

LNode*cat_link(LNode*la,LNode*lb)//la是halb是hb函數(shù)返回新單鏈表頭結(jié)點地址返回he

(

if(la&&lb){

LNode*lc=la;

while(la->next)la=la->next;

la->next=lb;

return1c;

elsereturnla?la:lb;

)

設(shè)一帶頭結(jié)點的雙向循環(huán)鏈表表示的線性表L=(al,a2,……an),試寫時間復(fù)雜度為0(n)的算法，將L改建為

L=(al,a3,...an,a4,a2)o

voidre_L(LNode*L)

(

LNode*t=L->right;

LNode*w=L->left;

intv=0;

while(t!=w){

v++;

if(v%2==0){

LNode*s=t;

t=t->right;

s->left->right=t;

t->left=s->left;

w->right->left=s;

s->right=w->right;

w->right=s;

s->left=w;

)

elset=t->right;

)

)

遞增有序表以單鏈表作為存儲結(jié)構(gòu)，刪除表中所有值大于mink且小于mark的元素。

voiddel_min_max(LNode*L,Elemtypemink,Elemtypemaxk)

{

LNode*p,*u,*q;

p二u=L;

while(p){

if(p->data>mink&&p->data<mark){

q=p->next;

deletep;

u->next=p=q;

)

else{u=p;p=p->next;}

)

)

遞增有序表A和B以單鏈表作為存儲結(jié)構(gòu)，編寫算法將A表和B表中原有結(jié)點歸并成一個按照元素值非遞增有

序的有序表C。例如:A=(l,2,3,4,6),B=(2,3,5,7,9),則0(9,7,6,5,4,3,3,2,2,1)。

//la是(1,2,3,4,6)1b是(2,3,5,7,9)

LNode*ABC(LNode*la,LNode*lb)

(

LNode*tmp,*pre=NULL;

While(la&&lb){

tmp=newLNode

if(la->data<=lb->data){

tmp->data=la->data;

tmp->next=pre;

pre=tmp;

la=la->next;

else{

tmp->data=lb->data;

tmp->next=pre;

pre=tmp;

lb=lb->next;

)

)

While(la){

tmp=newLNode

tmp->data=la->data;

tmp->next=pre;

pre=tmp;

la=la->next;

)

While(lb){

tmp=newLNode

tmp->data=lb->data;

tmp->next=pre;

pre=tmp;

lb=lb->next;

)

returntmp;

)

假設(shè)以遞增有序單鏈表表示集合A和B,現(xiàn)要求不破壞集合A和集合B,令構(gòu)造一個集合C,其元素為A和B的

交集。

LNode*ABC(LNode*la,LNode*lb)〃la是集合Alb是集合B函數(shù)返回值New為集合C

{

LNode*tmp,*tb,*New=newLNode;

tmp=New;

if(la&&lb){

while(la){

tb=lb;

while(la->data!=tb->data&&tb!=NULL)tb=tb->next;

if(tb!=NULL&&la->data==tb->data){

tmp->data=la->data;

)

la=la->next;

if(la&&tb&&tb->next){

tmp->next=newLNode;

tmp=tmp->next

)

elsetmp->next=NULL;

returnNew;

閱讀下面的算法

LinkListmynote(LinkListL)

{//L是不帶頭結(jié)點的單鏈表的頭指針

if(L&&L->next){

q=L;L=L—>next;p=L;

SI:while(p->next)p=p—>next;

S2:p—>next=q;q—>next=NULL;

)

returnL;

)

請回答下列問題：

(1)說明語句SI的功能；查詢鏈表的尾結(jié)點

(2)說明語句組S2的功能；把原來的表頭移動到表尾(招第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點)

(3)設(shè)鏈表表示的線性表為(al,a2,…,an),寫出算法執(zhí)行后的返回值所表示的線性表。

執(zhí)行后的結(jié)果：(a2,a3,…,an,al)

試編寫將兩個有序鏈表并為一個有序鏈表的算法。

LNode*_new(LNode*la,LNode*lb)

(

LNode*tmp,*New=newLNode;

tmp=New;

While(la&&lb){

if(la->data<=lb->data){

tmp->data=la->data;

la=la->next;

)

else{

tmp->data=lb->data;

lb=lb->next;

)

if((la&&lb)||la||lb){

tmp->next=newLNode;

tmp=tmp->next

)

elsetmp->next=NULL;

)

While(la){

tmp->data=la->data;

la=la->next;

if(la){

tmp->next=newLNode;

tmp=tmp->next

)

elsetmp->next=NULL;

)

While(lb){

tmp->data=lb->data;

lb=lb->next;

if(lb){

tmp->next=newLNode;

tmp=tmp->next

)

elsetmp->next=NULL;

)

returnNew;

)

已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為：

structBinTreeNode(ElemTypedata;BinTreeNode*left,bright;};

其中data為結(jié)點值域，left和right分別為指向