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

習(xí)題一

一、單選題

1.下列四種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是，列隊(duì)屬于

A.集合B.線性結(jié)構(gòu)C.樹(shù)形結(jié)構(gòu)D.圖形結(jié)構(gòu)

2.線性結(jié)構(gòu)各數(shù)據(jù)元素之間存在著的關(guān)系，圖形結(jié)構(gòu)數(shù)據(jù)元素之間存在

__的關(guān)系。

A.無(wú)關(guān)B,一■對(duì)一,C.一■對(duì)多D.多對(duì)多

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

4.算法中的基本操作重復(fù)執(zhí)行的頻度稱(chēng)為算法的;除了考慮存儲(chǔ)數(shù)據(jù)結(jié)

構(gòu)本身所占用的空間外，實(shí)現(xiàn)算法所用輔助空間的多少稱(chēng)為算法的O

A.時(shí)間復(fù)雜度B.空間復(fù)雜度C.硬件復(fù)雜度D軟件復(fù)雜度

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

①A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出關(guān)系

C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性

②A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性

C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

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

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

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

②A.可行性、可移植性和可擴(kuò)充性B.可行性、確定性和有窮性

C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性

線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說(shuō)法

A.正確B.不正確

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

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

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

二、填空題（將正確的答案填在相應(yīng)的空中）

1.數(shù)據(jù)邏輯結(jié)構(gòu)包括集合、、和四種類(lèi)

型，樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱(chēng)為o

2.線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有

個(gè)直接前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有

且僅有個(gè)直接后繼結(jié)點(diǎn)。

3.在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)

前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以o

4.在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以。

5.線性結(jié)構(gòu)中元素之間存在關(guān)系，樹(shù)形結(jié)構(gòu)中元素直接存在關(guān)

系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。

6.算法的五個(gè)重要特性是、、、、

7.下列程序段的時(shí)間復(fù)雜度是

for(i=0;i<n;i++)

for(j=0;j<m;j++)

a[i皿=0;

8.下列程序段的時(shí)間復(fù)雜度是

i=s=0;

while(s<n)

(

i++；

S+=I；

)

9.下列程序段的時(shí)間復(fù)雜度是

s=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

s+=b[ij[jj;

sum=s;

10.下列程序段的時(shí)間復(fù)雜度是

i=l；

while（i<n）

i=i*3;

習(xí)題二

一、填空題

1.在一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素（l<=i<=n）之前插入一個(gè)元素時(shí)，需向

后移動(dòng)個(gè)元素。

2.在一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素（l<=i<=n）時(shí)，需向前移動(dòng)個(gè)

元素。

3.單鏈表是的鏈接存儲(chǔ)表示。

4.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是在插入或刪除第一個(gè)結(jié)點(diǎn)時(shí)不必對(duì)

進(jìn)行處理。

5.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向，另一個(gè)指向

6.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行

s->next=和p->next的操作。

7.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足條件。

二、單選題

1.不帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是o

A.head=NULLB.head->next=NULL

C.head->next=headD.head!=NULL

2.帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是-

A.head=NULLB.head->next=NULL

C.head->next=headD.head!=NULL

3.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足o

A.p->next=NULLB.p=NULL

C.p->next=headD.p=head

4.在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是。

A.p-<next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B.p-<next=s;p->next->prior=s;s->prior=p;s->next=p->next;

C.s->prior=p;s->next=p->next;p-<next=s;p->next->prior=s;

D.s->prior=p;s->next=p->next;p->next->prior=s;p-<next=s;

5.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之

間插入S結(jié)點(diǎn)，則執(zhí)行O

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

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

6.一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則

執(zhí)行O

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

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

7.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行o

A.p->next=p->next->nextB.p=p->next;p->next=p->next->next

C.p->next=p->nextD.p=p->next->next

三、算法描述題

1.已知一個(gè)向量中的元素按元素值非遞減有序排列，編寫(xiě)一個(gè)函數(shù)刪除向量中

多余的值相同的元素。

2.編寫(xiě)一個(gè)函數(shù)將一個(gè)向量A（有"個(gè)元素，且任何元素均不為0）分拆成兩個(gè)

向量，使A中大于0的元素存放在B中，小于0的元素存放在C中。

3.已知在一維數(shù)組A[l,m+n]中依次存放著兩個(gè)向量（a的,..,am）和（也,

b2,……，ba）,編寫(xiě)一個(gè)函數(shù)將兩個(gè)向量的位置互換，即把（b”b2,……,ba）

放到（ai,a2,.......，am）的前面。

4.有一個(gè)單鏈表（不同結(jié)點(diǎn)的數(shù)據(jù)值域可能相同），其頭指針為head,編寫(xiě)一個(gè)

函數(shù)計(jì)算數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。

5.編寫(xiě)一個(gè)函數(shù)將不帶頭結(jié)點(diǎn)的單鏈表La復(fù)制成單鏈表Lbo

6.有一個(gè)單鏈表，其結(jié)點(diǎn)的元素值以非遞減有序排列，編寫(xiě)一個(gè)函數(shù)刪除該單

鏈表中多余的元素值相同的結(jié)點(diǎn)。

習(xí)題三

一、填空題

1.棧是限定僅在表尾進(jìn)行操作的線性表，表頭端稱(chēng)為，

表尾端稱(chēng)為，棧的操作特性是0

2.隊(duì)列是限定僅在表尾進(jìn)行和在表頭端進(jìn)行的線性

表，列隊(duì)的操作特性是O

3.以下定義了一個(gè)順序棧：

#defineMAXSTACK500

typedefstruct{

chardata[MAXSTACKl;

inttop;

Jsqstack;

sqstackss;

?？盏臈l件是：,棧滿的條件是：;

棧頂元素的表達(dá)式是:,棧底元素的表達(dá)式是:。

二、簡(jiǎn)答題

1.設(shè)將整數(shù)1,2,3,4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次

序插入在入棧操作之間，請(qǐng)回答下述問(wèn)題：

(1)若入出棧次序?yàn)镻ush(l),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),

PopO,則出棧的數(shù)字序列是什么(這里Push(i)表示進(jìn)棧，Pop()表示出棧)？

(2)能否得到出棧序列1423和1432?并說(shuō)明為什么不能得到或者如何得到。

(3)請(qǐng)分析1,2,3,4的24種排列中，哪些序列可以通過(guò)相應(yīng)的入、出棧操作

得到。

2.循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它的空和滿？

三、算法設(shè)計(jì)題

1.回文是指正讀反讀均相同的字符序列,如“abba"和“abdba”均是回文，

但“good”不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文。(提示：將

一半字符入棧。)

2.括號(hào)配對(duì)檢查，輸入一個(gè)只有左括號(hào)“(”和右括號(hào)“)”的序列，程序?qū)?/p>

括號(hào)配對(duì)的正確性進(jìn)行檢查并給出結(jié)果。提示：配對(duì)檢查算法中用到棧結(jié)構(gòu)。例

如括號(hào)序列“(()())”、“()()(())”為正確配對(duì)，括號(hào)序列“()())”、“)()(”為

不正確配對(duì)等。注意：輸入序列中只能出現(xiàn)左括號(hào)“(”和右括號(hào)“)”，序列的

語(yǔ)法正確性由用戶保證。

請(qǐng)給出完整的C程序描述。

習(xí)題四

一、填空題

1.已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)

單元，并且第一個(gè)元素的存儲(chǔ)地址是Loc(A[0][0]),則A[iJ[j]的地址是

2.二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單

元，并且A[0][0]的存儲(chǔ)地址是200,則A⑹⑵的地址是o

二、單選題

1.常對(duì)數(shù)組進(jìn)行的兩種基本操作是O

A.建立與刪除B.索引和修改C.查找和修改D.查找與索引

2.數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1

到10,存放該數(shù)組至少需要的單元數(shù)是o

A.80B.100C.240D.270

3.數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1

到10,從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]

的起始地址為o

A.SA+141B.SA+144C.SA+222D.SA+225

4.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即o

A.二維數(shù)組和三維數(shù)組B.三元組表和散列

C.三元組表和十字鏈表D.散列和十字鏈表

三、算法描述題

假設(shè)稀疏矩陣Am*n和Bm*n都采用三元組表，編寫(xiě)一個(gè)函數(shù)計(jì)算C=A+B,

要求C也采用三元組表表示。

習(xí)題五

一、簡(jiǎn)答題

1.設(shè)s="IAMASTUDENT”，

t="GOOD”，

q="WORKER”。

求：STRLEN(s),STRLEN(t),SUBSTR(s,8,7,),SUBSTR(t,2,1),

INDEX(s,"A"),INDEX(s,t),REPLACES,“STUDENT”，q)o

2.已知下列字串：

a="THIS"，f="ASMPLE"，c="GOOD"，d="NE”,b=""，g=“IS”

s=CONCAT(a,CONCAT(CONCAT(b,SUBSTR(a,3,2)),SUBSTR(f,2,

6)))

t=REPLACE(f,SUBSTR(f,3,5),c)

u=CONCAT(SUBSTR(c,3,1),d)

v=CONCAT(s,CONCAT(b,CONCAT(t,CONCAT(b,u))))

問(wèn)s,t,v,STRLEN(s),INDEX(v,g),INDEX(u,g)各是什么?

3、簡(jiǎn)述下列每對(duì)術(shù)語(yǔ)的區(qū)別：

空串和空格串；串變量和串常量；主串和子串。

4、兩個(gè)字符串相等的充要條件是什么？

5、設(shè)已知兩個(gè)串為：

Si="becadcabcadf”；

82="abc"。

試求兩個(gè)串長(zhǎng)度，并判讀斷S2串是否是與的子串。如果S2是否是S1的子

串，指出S2在$中的起始位置。

二、算法設(shè)計(jì)題

編寫(xiě)算法，在順序串上實(shí)現(xiàn)串的判等操作EQUAL(S,T)o設(shè)兩個(gè)串分別為

S="Beijing"，T="China”,調(diào)用函數(shù)EQUAL(S,T)判斷后,如果S=T,則返回

1,否則返回0.

習(xí)題六

一、判斷題

1、二叉樹(shù)是樹(shù)的特殊情形。（）

2、二叉樹(shù)的先序遍歷序列中，任意節(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)之前。（）

3、二叉鏈表是一種邏輯結(jié)構(gòu)。（）

4、由二叉樹(shù)的先序序列和后序序列可以唯一確定一棵二叉樹(shù)。（）

5、n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)不唯一。（）

6、樹(shù)的后續(xù)遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同。（）

7、完全二叉樹(shù)的某結(jié)點(diǎn)若無(wú)左孩子，則它必是葉子結(jié)點(diǎn)。（）

二、選擇題

1、將一棵樹(shù)t轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹(shù)h,則t的后序遍歷是卜的（）

A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷

2、對(duì)二叉樹(shù)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的

編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，則可采用

（）次序的遍歷實(shí)現(xiàn)編號(hào)。

A.先序B.中序C.后序D.從根開(kāi)始的層次遍歷

3、已知一?棵完全二叉樹(shù)中共有768個(gè)結(jié)點(diǎn)，則該樹(shù)中共有（）個(gè)葉子結(jié)點(diǎn)。

A.383B.384C.385D.386

4、先序遍歷和中序遍歷相同的二叉樹(shù)為（）

A.只有根結(jié)點(diǎn)的二叉樹(shù)B.根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù)

C.一般二叉樹(shù)D,只有根結(jié)點(diǎn)的二叉樹(shù)和所有結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)

三、簡(jiǎn)答題

1、一棵樹(shù)的邊集為｛（a,b）,（b,e）,（a,c）,（c,g）,（a,d）,（d,i）,（c,f）,（c,h）,（d,j）,

（i,k）｝,請(qǐng)畫(huà)出此棵樹(shù)的形態(tài)，并回答下列問(wèn)題：

（1）樹(shù)的根是哪個(gè)結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？哪些是分支結(jié)點(diǎn)？

（2）各結(jié)點(diǎn)的度分別是多少？樹(shù)的度是多少？

（3）各結(jié)點(diǎn)的層次分別是多少？樹(shù)的深度是多少？以d為根的子樹(shù)深度是

多少？

（4）結(jié)點(diǎn)i的雙親是哪個(gè)結(jié)點(diǎn)？祖先是哪個(gè)結(jié)點(diǎn)？孩子是哪些結(jié)點(diǎn)？兄弟

是哪些結(jié)點(diǎn)？

2、樹(shù)和二叉樹(shù)有哪些區(qū)別？

3、已知二叉樹(shù)的后序和中序序列如下，構(gòu)造出該二叉樹(shù)，寫(xiě)出它的前序遍歷

序列。

后序序歹U：ABCDEFG中序序歹U：ACBGDFE

4、假設(shè)用于通信的電文由字符集｛岫,斕?胴｝中的字母構(gòu)成，它們?cè)陔娢闹?/p>

出現(xiàn)的頻度分別為｛0.31,,0.16,0.10,0.08,0.11,0.20,0.04）

（1）為這7個(gè)字母設(shè)計(jì)哈弗曼編碼。

（2）對(duì)這7個(gè)字母進(jìn)行等長(zhǎng)編碼，至少需要幾位二進(jìn)制數(shù)？哈弗曼編碼與

等長(zhǎng)編碼相比，能使電文總長(zhǎng)壓縮多少？

四計(jì)算題

1、設(shè)計(jì)算法求二叉樹(shù)的高度。

2、按要求寫(xiě)出算法，功能為判斷一棵二叉樹(shù)（采用二叉鏈表存儲(chǔ)結(jié)構(gòu)）是否

為完全二叉樹(shù)。

習(xí)題七

-、單項(xiàng)選擇題

1、一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有條邊。

A.nB>n（n-l）C、n（n-l）/2D、2n

2、一個(gè)有4個(gè)頂點(diǎn)的無(wú)向完全圖有條邊。

A、6B、12C、16D、20

3、一個(gè)有5個(gè)頂點(diǎn)的連通圖至少有條邊

A、3B、4C、5D、6

的鄰接矩陣是對(duì)矩陣。

A、有向圖B、無(wú)向圖C、AOV網(wǎng)

5、鄰接表時(shí)圖的一種。

A、順序存儲(chǔ)結(jié)構(gòu)B、鏈接存儲(chǔ)結(jié)構(gòu)C、索引存儲(chǔ)結(jié)構(gòu)D、散列存儲(chǔ)結(jié)構(gòu)

6、采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的o

A、前序遍歷B、中序遍歷C、后序遍歷D、按層遍歷

7、采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的。

A、前序遍歷B、中序遍歷C、后序遍歷D、按層遍歷

8、任何一個(gè)無(wú)向連通圖最小生成樹(shù)。

A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在

9、一個(gè)圖的表示法師唯一的，而表示是不是唯一的。

A、三元組B、鄰接矩陣C、鄰接表D索引

二、簡(jiǎn)答題

1、對(duì)圖7.23所示有向圖，回答下列問(wèn)題

(1)該圖是強(qiáng)連通圖嗎?若不是，則給出其強(qiáng)連通分量。

(2)請(qǐng)給出從頂點(diǎn)1到頂點(diǎn)3的所有的簡(jiǎn)單路徑。

(3)請(qǐng)給出頂點(diǎn)1的度、入度和出度。

(4)請(qǐng)給出其鄰接矩陣，鄰接表及逆鄰接表。

2、對(duì)圖7.24所示無(wú)向圖，分別給出它從頂點(diǎn)1出發(fā)進(jìn)行深度和廣度遍歷得到的

頂點(diǎn)序列

圖7.23有向圖

3、對(duì)圖7.25所示無(wú)向圖，分別畫(huà)出按普里姆算法和克魯斯卡爾得到最小生成樹(shù)

的過(guò)程。

4、對(duì)圖7.26所示有向圖，利用辿杰斯特拉算法，求從頂點(diǎn)1到其余各項(xiàng)點(diǎn)的最

短路徑

5、對(duì)圖7.27所示有向圖,求拓?fù)湫蛄小?/p>

習(xí)題八

一、單選題

1、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須o

A、以順序方式存儲(chǔ)B、以鏈接方式存儲(chǔ)

C、以順序方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序排列

D、以鏈接方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序排列

2、采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度

為O

A、nB、n/2C、(n+l)/2D、(n-l)/2

3、采用二分查找長(zhǎng)度為n的線性時(shí)，每個(gè)元素的平均查找長(zhǎng)度為o

A>O(n2)B、O(nlong2n)C、O(n)D、O(long2n)

4、有一個(gè)序列表為(5,7,8,22,32,40,45,62,70,77,82,97,100),

當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)-，次比較后查找成功。

A、1B、3C、4D、8

5、從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈接表中查找其值等于x結(jié)點(diǎn)時(shí)，查找成功的情況

下，需平均比較個(gè)結(jié)點(diǎn)。

A、nB、n/2C、(n-l)/2D、(n+l)/2

二、填空題

1、假設(shè)有序線性表A[l],……，A[20]上進(jìn)行二分查找，則比較一次查找成功的

結(jié)點(diǎn)數(shù)為，則比較二次查找成功的結(jié)點(diǎn)數(shù)為,則比較三次查找成

功的結(jié)點(diǎn)數(shù)為，則比較四次查找成功的結(jié)點(diǎn)數(shù)為,則比較五次查

找成功的結(jié)點(diǎn)數(shù)為，平均查找長(zhǎng)度為o

2、在散列存儲(chǔ)中，裝填因子a的值越大，存取數(shù)據(jù)元素是發(fā)生沖突的可能

性;a的值越小，則發(fā)生沖突的可能性o

三.簡(jiǎn)答題、

設(shè)有一組關(guān)鍵字(19,01,23,14,55,20,84,27,68,11,10,77)采用哈

希函數(shù)

H(key)=key%13

1,、采用開(kāi)放地址的線性探測(cè)再散列方法解決沖突，試在[0…12]的散列地址

空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表

2、對(duì)上題中的關(guān)鍵字序列，采用鏈地址法，畫(huà)出相應(yīng)的哈希表

3、對(duì)有序表(5,8,27,35,45,48,57,72,89,95),采用二分查找，畫(huà)出

二分查找過(guò)程的二叉判定樹(shù)，并計(jì)算其平均查找長(zhǎng)度。

四.算法設(shè)計(jì)題

1.將折半查找算法改寫(xiě)為遞歸的形式。

2.以線性探測(cè)再散列為例，給出散列表的查找算法。

習(xí)題九

一、單選題

1、在所有排序方法中、關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的

是O

A、希爾排序B、冒泡排序C、直接插入排序D、直接選擇排序

2、沒(méi)有1000個(gè)無(wú)序的元素、希望用最快的速度挑選出其中前10個(gè)最大的元素,

最好的排序法。

A、冒泡排序B、堆排序C、快速排序D、基數(shù)排序

3、排序的元素序列基本有序的前提下，效率最高的排序方法是______」

A、直接插入排序B、直接選擇排序C、快速排序D、歸并排序

4、一組記錄的排序碼