數(shù)據(jù)結(jié)構(gòu)相關(guān)試題

(1)簡(jiǎn)述數(shù)據(jù)與數(shù)據(jù)元素的關(guān)系與區(qū)別。

(2)說出數(shù)據(jù)結(jié)構(gòu)中的四類基本邏輯結(jié)構(gòu)，并說明哪種關(guān)系最簡(jiǎn)單、哪種關(guān)

系最復(fù)雜。

(3)畫出線性結(jié)構(gòu)的示意圖。

(4)畫出樹形結(jié)構(gòu)的示意圖。

(5)畫出圖狀結(jié)構(gòu)的示意圖。

(6)什么是邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)？有哪兒種存儲(chǔ)結(jié)構(gòu)？

(7)簡(jiǎn)述順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在表示數(shù)據(jù)元素之間關(guān)系上的主要區(qū)

別。

(8)簡(jiǎn)述邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系。

(9)通常從哪兒個(gè)方面評(píng)價(jià)算法的質(zhì)量？

(10)算法的時(shí)間復(fù)雜度主要有哪幾種？按從優(yōu)到劣的順序?qū)懗龈鞣N表示形

式。

(11)簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存

儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。

(12)下列算法的時(shí)間復(fù)雜度是()o

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

for(j=0；j<n；j++)c[i][j]=i+j

2

A.0(1)B.O(n)C.O(log2n)D.O(n)

(13)下列算法的時(shí)間復(fù)雜度是()o

for(i=0；i<n；i++)c[i][i]=i+i

2

A.0(1)B.0(n)C.O(log2n)D.0(n)

5

※〈習(xí)題二〉

(1)若某線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占四個(gè)存儲(chǔ)單元，首地址為100,

則下標(biāo)為11的(第12個(gè))元素的存儲(chǔ)地址為()。

(2)下列說法正確的是()。

A.線性表的邏輯順序與存儲(chǔ)順序總是一致的

B.線性報(bào)第鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，內(nèi)存中可用的存儲(chǔ)單元可以使連續(xù)的，也可以

不連續(xù)

C.線性表弟順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

D.每種數(shù)據(jù)結(jié)構(gòu)都具有插入、刪除和查找三種基本運(yùn)算

⑶L是線性表，已知ListLength(L)的值是5,運(yùn)算DeleteList(L,2)后ListLength

(L)的值是()o

A.5B.0C.4D.6

(4)線性表中哪些元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼()o

A.首元素B.尾元素C.中間元素D.所有的元素

(5)線性表(L)經(jīng)運(yùn)算InitList(L)后，函數(shù)lEmpty(L)的值是()。

A.0B.,falseC.1D.Null

(6)指針P指向循環(huán)鏈表L的首元素的條件是()0

A.P=LB.P->nest=LC.L->nest=PD.P->nest=null

⑺線性表中各元素之間的關(guān)系是()關(guān)系。

A.層次B.網(wǎng)狀C.有序D.集合

(8)在單鏈表的一個(gè)結(jié)點(diǎn)中有()個(gè)指針。

A.1B.2C.0D.3

⑼在雙向鏈表的一個(gè)結(jié)點(diǎn)中有()個(gè)指針。

A.1B.2C.0D.3

(10)設(shè)非空單鏈表的數(shù)據(jù)字段為data,指針字段為next,指針p指向單鏈表

中第i個(gè)結(jié)點(diǎn)，s指向已生成的新結(jié)點(diǎn)，現(xiàn)將s結(jié)點(diǎn)插入到單鏈表中，使其成

為第i+1個(gè)結(jié)點(diǎn)，下列算法段能正確完成上述要求的是()0

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

C.s->next=p->next；p->next=s；交換p->data和s->data；D.p=s；

s->next=p

(11)設(shè)雙鏈表中結(jié)點(diǎn)的前趨指針的字段分別為tl和rl,則刪除雙鏈表中指針s

所指結(jié)點(diǎn)的操作為()0

A.s->tl-rl=s->tl；s-rl=s->rl；B.s->tl-rl=s->rl；s->rl=s->tl；

C.s->rl=s->tl；s->tl=s->rl->tl；D.s->tl=s-tl->rl；s->rl=s->tl；

(12)假設(shè)left和right為雙向鏈表中指向直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的指針字

段，現(xiàn)要把一個(gè)指針s所指的新結(jié)點(diǎn)作為非空雙鏈表中q所指結(jié)點(diǎn)(中間結(jié)點(diǎn))

的直接后繼結(jié)點(diǎn)插入到該雙向鏈表中，則下列算法段能正確完成上述要求的是

0。

A.q->right=s；s-left=q；q-right->left=s；s-right=q->right；

B.s->left=q；q->right=s；q->right->left=s；s->right=q->right；

C.s->left=q;s-right=q->right;q->right-left=s;q-right=s;

D.以上都不對(duì)

5

※〈習(xí)題三〉

(1)棧是限定在處進(jìn)行插入或刪除操作的線性表()。

A、端點(diǎn)B、棧底C、棧頂D、中間

(2)在棧頂一端可進(jìn)行的全部操作時(shí)()o

A、插入B、刪除C、插入和刪除D、進(jìn)棧

(3)4個(gè)元素按A、B、C、D、順序連續(xù)進(jìn)Szhan棧，進(jìn)行Pop(S,x)元素后，

X的值是（）。

A、AB、BC、CD、D

（4）棧的特點(diǎn)是（）-

A先進(jìn)先出B后進(jìn)先出C后進(jìn)后出D不進(jìn)不出

（5）棧結(jié)構(gòu)的元素個(gè)數(shù)是（）。

A不變的B可變的C任意的DO

（6）4個(gè)元素進(jìn)S棧的順序是A、B、C、D,進(jìn)行兩次Pop（S,x）操作后,

棧頂元素的值是（）。

A、AB、BC、CD、D

（7）同一個(gè)棧內(nèi)各元素的類型（）。

A必須一致B可以不一致C不能一致D不必不一致

（8）順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用（）。

A鏈表B數(shù)組C循環(huán)鏈表D變量

（9）一個(gè)順序棧一旦說明，其占用空間的大?。ǎ?。

A已固定B可以改變C不能固定D動(dòng)態(tài)變化

（10）棧是一個(gè)線性表結(jié)構(gòu)（）。

A不加限制的B加了限制的C推廣了的D非

（11）棧與一般線性表區(qū)別主要在方面（）o

A元素個(gè)數(shù)B元素類型C邏輯結(jié)構(gòu)D插入、刪除元素

的位置

（12）順序棧是空棧的條件是（）。

A.top==0B.top==lC.top==-1D.top=m

（13）元素A、B、C、D依次進(jìn)順序棧后，棧頂元素是（）。

A.AB.BC.CD.D

（14）經(jīng)過下列棧的運(yùn)算后GetTop（s）的值是（）。

InitStack（s）；Push（s,a）；Push（s,b）；Pop（s）；

A.aB.bC.lD.2

（15）經(jīng)過下列棧的運(yùn)算后EmptyStack（s）的值是（）。

InitStack（s）；Push（s,a）；Push（s,b）；Pop（s,x）；Pop（s,x）；

A.aB.bC.lD.O

（16）隊(duì)列是限定在處進(jìn)行插入操作的線性表（）o

A.端點(diǎn)B.隊(duì)頭C.隊(duì)尾D.中間

（17）隊(duì)列是限定在處進(jìn)行刪除操作的線性表（）o

A.端點(diǎn)B.隊(duì)頭C.隊(duì)尾D.中間

（18）隊(duì)列的特點(diǎn)是。

A.先進(jìn)先出B.后進(jìn)先出C.先進(jìn)后出D.不進(jìn)不出

（19）循環(huán)隊(duì)列Sq是空隊(duì)列的條件是（）。

ASq->read=Sq->frontB（Sq->read+l）%maxsize==Sq->front

CSq->read=ODSq->front==0

(20)循環(huán)隊(duì)列Sq是滿隊(duì)列的條件是()o

ASq->read=Sq->frontB(Sq->read+l)%maxsize=Sq->front

CSq->read=0DSq->front==0

(21)當(dāng)循環(huán)隊(duì)列Sq是滿隊(duì)列時(shí)，存放隊(duì)列元素的數(shù)組data有n個(gè)元素，則data

中存放個(gè)隊(duì)列元素()。

A.nB.n-1C.n-2D.0

(22)經(jīng)過下列運(yùn)算后GetHead(Q)的值是()。

InitQueue(Q)；EnQueue(Q,a)；EnQueue(Q,b)；OutQueue(Q,x)；

A.aB.bC.lD.2

(23)鏈棧Is是空棧的條件是()。

A.ls==nullB.ls->next=nullC.Ls=0D.ls->next==ls

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

任何次序夾入其中，請(qǐng)回答下述問題：

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

Push(4),Pop(),則出棧的數(shù)字序列為何(這里Push(i)表示進(jìn)棧，Pop()表示

出棧)？

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

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

得到的。

5

※〈習(xí)題四〉

(1)設(shè)S="IAMASTUDENT”，其長度是()。

(2)串是一種特殊的線性表，其特征體現(xiàn)在。

A可以順序存儲(chǔ)B數(shù)據(jù)元素是一個(gè)字符

C可以鏈接存儲(chǔ)D數(shù)據(jù)元素可以使多個(gè)字符

(3)設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作()。

A連接B模式匹配C求串長D求子串

(4)設(shè)字符串S1="ABCDEFG"，S2="PQRST”，則運(yùn)算：S=CONCAT(SUBSTR

(SI,2,LEN(S2))；SUBSTR(SI,LEN(S2),2))；后的串值為()。

A、BCDEFB、BCDEFGC、BCDPQRSTD、BCDEFER

(5)判斷題

①空格串和孔串的長度均為lo()

②串是一種特殊的線性表，其特殊性體現(xiàn)在數(shù)據(jù)元素可以使多個(gè)字符。()

③判斷兩個(gè)串是否相等，只需要判斷這兩個(gè)串是否包含相同的字符即可。()

④將一個(gè)nxn的對(duì)稱矩陣，以行為主序或以列為主序存入內(nèi)存，其容量至少

為n2o（）

⑤若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行標(biāo)和列標(biāo)互換,

就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算。（）

5

※〈習(xí)題五〉

（1）對(duì)于一個(gè)二維數(shù)組A[0..m][0..n],若按行序?yàn)橹餍虼鎯?chǔ)，則人…元素

的存儲(chǔ)地址為（）o

（2）設(shè)數(shù)組R[L.10,-2..6,2..8]以行序?yàn)橹餍虼鎯?chǔ)，設(shè)第一個(gè)元素的首地址為100,

每個(gè)元素占3個(gè)存儲(chǔ)單元，則元素A[5,0,7]的存儲(chǔ)地址為（）o

（3）設(shè)有一個(gè)10階對(duì)稱矩陣A采用壓縮存儲(chǔ)方式以行序?yàn)橹餍蛭淮鎯?chǔ)，a85的

存儲(chǔ)地址為（）o

（4）數(shù)組的基本操作主要包括（）。

A建立與刪除B索引與修改C訪問與修改D訪問與索引

（5）稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（）。

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

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

（6）設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省空間，將其下三角矩陣按行序存放在

一維數(shù)組B[l,n（n+1）⑵中，對(duì)下三角部分中任一元素aij（三j）,在一維數(shù)B

中下標(biāo)k的值是（）。

Ai（i-1）/2+j-lBi（i-l/2+jCi（i+1）/2+j-lDi（i+1）/2+j

※〈習(xí)題六〉

填空題

（1）假定--棵樹的嵌套括號(hào)表示法為A（B（E）,C（F,G）,D）,則該

樹的度為（），樹的深度為（），終端點(diǎn)的個(gè)數(shù)為（），分支結(jié)點(diǎn)的個(gè)數(shù)為（），

雙分支結(jié)點(diǎn)為（），三分支結(jié)點(diǎn)的個(gè)數(shù)為（），C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為（），

其孩子結(jié)點(diǎn)為（）和（）。

（2）設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則

B中右指針字段為空的結(jié)點(diǎn)有（）0

（3）對(duì)于…個(gè)具有n個(gè)結(jié)點(diǎn)的二叉樹;當(dāng)它儲(chǔ)存在二叉樹表中時(shí)，其指針字段

的總數(shù)為（）個(gè)，其中（）個(gè)用于鏈接孩子點(diǎn)，（）個(gè)空暇，

（4）一棵深度為K的滿二叉樹結(jié)點(diǎn)總數(shù)為（）,一棵深度為K的完全二叉樹的

結(jié)點(diǎn)總數(shù)的最小值為（），最大值為（）。

（5）如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的（）序是T2中結(jié)點(diǎn)

的（）=

（6）具有n個(gè)結(jié)點(diǎn)的完全二叉樹，若按層次從上到下、從左到右對(duì)其編號(hào)（根結(jié)

點(diǎn)為1號(hào)），則編號(hào)最大的分支結(jié)點(diǎn)序號(hào)為（），編號(hào)最小的分支結(jié)點(diǎn)序號(hào)為

（）,編號(hào)最大的葉子結(jié)點(diǎn)序號(hào)為（）＞編號(hào)最小的口r子結(jié)點(diǎn)序號(hào)為（）。

（7）有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)為（）。

（8）由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有（）種不同的結(jié)構(gòu)。

選擇題

（1）將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹，從根這一層開始，每一層從左到右依次

對(duì)結(jié)點(diǎn)編號(hào)，根據(jù)點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的雙親的編號(hào)為（）o

A.24B.25C.23D無法確定

（2）深度為6（根據(jù)的層次為1）的二叉樹至多有（）結(jié)點(diǎn)。

A64B63C31D32

（3）設(shè)二叉樹有n個(gè)結(jié)點(diǎn)，則其深度為。

An-1BnC跑2nD無法確定

（4）設(shè)森林T中有三棵樹，第一、第二、三棵數(shù)的活結(jié)點(diǎn)個(gè)數(shù)分別為nln2n3,

那么將森林轉(zhuǎn)換成二叉樹后，其根結(jié)點(diǎn)的右子樹上有（）個(gè)結(jié)點(diǎn)。

Anl-1Bn2+n3Cnl+n2+n3Dnl

（5）設(shè)森林T中有三棵樹，第一、二、三棵數(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為nln2n3,那么

將森林轉(zhuǎn)換成二叉樹后，其根結(jié)點(diǎn)的左子樹上有（）個(gè)結(jié)點(diǎn)。

A.nl-1B.n2+n3C.nl+n2+n3D.nl

（6）設(shè)深度為K的二叉樹上只有度為0或度為2的結(jié)點(diǎn)，則這類二叉樹上所含結(jié)

點(diǎn)總數(shù)至少（）o

A,K+1B.2KC2K—1D2K+1

（7）樹轉(zhuǎn)換成二叉樹后，以下結(jié)論正確的是（）o

A樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同

B樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同

C樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同

D以上都不對(duì)

（8）某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序?yàn)?，ABDGCDFH中序遍歷結(jié)點(diǎn)訪問順序

為DGBAECHE,則其后續(xù)遍歷結(jié)點(diǎn)訪問順序?yàn)椋ǎ?/p>

A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.

GDBDHFCA

（9）在一棵非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）。

A只有右子樹上的所有結(jié)點(diǎn)B只有右子樹砂鍋內(nèi)的部分結(jié)點(diǎn)

C只有左子樹上的所有結(jié)點(diǎn)D只有左子樹上的部分結(jié)點(diǎn)

（10）任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（）o

A不發(fā)生變化B發(fā)上變化C不能確定D以上都不對(duì)

判斷題

⑴一棵度為2的樹就是一棵二叉樹、()

⑵無序樹的子樹沒有順序之分，而二叉樹的子樹分為左子樹和右子樹。()

⑶給定二叉樹的先序遍歷序列和后序遍歷序列，就能惟一地確定一棵二叉樹。

()

⑷先根序列和中根序列相同的二叉樹中任意一個(gè)結(jié)點(diǎn)都無左孩子。()

解答題

(1)已知一棵樹邊的集合為｛(I,M),(I,N)(E,I),(B,E),(B,

D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,L),(C,

H),(A,C)｝,畫出這棵樹，并回答下列問題：

A、哪個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)？B、哪些結(jié)點(diǎn)是葉子結(jié)點(diǎn)？C、哪個(gè)結(jié)點(diǎn)是結(jié)點(diǎn)G的

雙親結(jié)點(diǎn)？D、哪些結(jié)點(diǎn)是結(jié)點(diǎn)G的祖先結(jié)點(diǎn)？E、哪些結(jié)點(diǎn)是結(jié)點(diǎn)G的孩

子結(jié)點(diǎn)？哪些結(jié)點(diǎn)是結(jié)點(diǎn)E的子孫結(jié)點(diǎn)？F、哪些結(jié)點(diǎn)是結(jié)點(diǎn)E的兄弟結(jié)

點(diǎn)？哪些是結(jié)點(diǎn)F的兄弟結(jié)點(diǎn)？G、結(jié)點(diǎn)B和N的層次分別是多少？H、樹

的深度是多少？I、以結(jié)點(diǎn)C為根的子樹的深度是多少？

(2)說明一棵度為2的樹與一棵二叉樹之間的區(qū)別。

(3)試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和具有3個(gè)結(jié)點(diǎn)的二叉樹的所有結(jié)構(gòu)圖。

(4)按照下列給定二叉樹的先序遍歷序列、中序遍歷和后序遍歷序列，分別構(gòu)

造出二叉樹。

①先序遍歷序列：EBADCFHGIKJ中序遍歷系列：ABCDEFGHIJK

②中序遍歷序列：ACBGEDF后序遍歷序列：ABCDEFG

(5)給定的權(quán)值｛2,3,4,7,8,9),構(gòu)造出相應(yīng)的赫夫曼樹

和赫夫曼編碼，并求出帶權(quán)路徑的長度WPL0

(6)對(duì)于圖6.1給出的樹，指出樹中的根結(jié)點(diǎn)、葉結(jié)點(diǎn)和分支結(jié)點(diǎn)。并指出各

個(gè)結(jié)點(diǎn)的度數(shù)和層數(shù)。

(7)對(duì)圖6.1所示的樹，采用先根次序、后根次序和中根次序遍歷。問得到怎

樣的結(jié)點(diǎn)序列？

(8)對(duì)圖6.1所示的樹，分別采用先根次序的父指針表示法、子表表示法、長

子-兄弟表示法，試畫出各種方法的圖示。

(9)已知一棵度為m的樹中有nl個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…，

nm個(gè)度為m的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？

(10)用三個(gè)結(jié)點(diǎn)A,B,C可以構(gòu)成多少種不同的二叉樹？請(qǐng)把它們畫出來。

(11)將圖6.1所示的樹轉(zhuǎn)換成對(duì)應(yīng)的二叉樹是什么樣子？請(qǐng)把它畫出來。

A

（12）請(qǐng)按先根、后根和對(duì)稱序遍歷圖6.2所示的二叉樹，列出遍歷所得的結(jié)

點(diǎn)序列。

（13）請(qǐng)將圖6.2所示的二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹林，并按先根次序和后根次序

遍歷樹林，將遍歷結(jié)果與上題結(jié)果對(duì)照比較。

（14）已知某二叉樹的先根遍歷序列為：A,B,D,E,G,C,F,H,I,J,對(duì)

稱次序遍歷序列為：D,B,G,E,A,H,F,I,J,C,試給出該二叉樹的后根次

序遍歷序列。

（15）試給出圖6.2所示的二叉樹的穿線樹表示（按對(duì)稱序穿線）。

（16）對(duì)下圖所示的森林：

1）求各樹的前序序列和后序序列；

2）求森林的前序序列和后序序列；

3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；

4）給出（a）所示樹的雙親鏈表表示、孩子鏈表表示、雙親孩子鏈表表示及孩

子兄弟鏈表表示等四種存儲(chǔ)結(jié)構(gòu)，并指出哪些存儲(chǔ)結(jié)構(gòu)易于求指定結(jié)點(diǎn)的祖先，

哪些易于求指定結(jié)點(diǎn)的后代？

（17）畫出下圖所示的各二叉樹所對(duì)應(yīng)的森林。

（18）假設(shè)用于通信的電文由字符集匕,1）”,46,￡&七中的字母構(gòu)成,這8個(gè)

字母在電文中出現(xiàn)的概率分別為

{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。

①為這8個(gè)字母設(shè)計(jì)Huffman編碼。

②若用三位二進(jìn)制數(shù)（0-7）對(duì)這8個(gè)字母進(jìn)行等長編碼，則Huffman編碼的平均碼長是等

長編碼的百分之幾？它使電文總長平均壓縮多少？

5

※〈習(xí)題七〉

填空題

⑴一個(gè)具有n個(gè)頂點(diǎn)的完全圖的邊數(shù)為（）。

⑵無向圖中的連通分量定義為無向圖的（）。

⑶設(shè)無向圖G的頂點(diǎn)數(shù)為n,則G最少有（）條邊。

⑷一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為（）。

⑸有向圖中的強(qiáng)連通分量定義為有向圖的（）。

單項(xiàng)選擇題

（1）連通分量是（）極大連通子圖。

A.無向圖B.有向圖C樹D圖

（2）強(qiáng)連通分量是（）極大連通子圖。

A.無向圖B.有向圖C.樹D,圖

（3）有n個(gè)頂點(diǎn)的無向圖的鄰接矩陣是用（）組存儲(chǔ)。

A.n行n列B.一維C.任意行n列D.n行任意列

（4）有n條邊的無向圖的鄰接表存儲(chǔ)法中，鏈邊中結(jié)點(diǎn)的個(gè)數(shù)是（）個(gè)。

A.nB.2nC.n/2D.n*n

（5）一個(gè)加權(quán)的無向連通圖的最小生成樹（）。

A.有一棵或多棵B.只有一棵C.一定有多棵D.可能

不存在

（6）下列有關(guān)圖遍歷的說法中不正確的是（）。

A.連通圖的深度優(yōu)先搜索是個(gè)遞增過程

B.圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征

C.非連通圖不能用深度優(yōu)先搜索法

D.圖的遍歷要求每個(gè)頂點(diǎn)僅被訪問一次

（7）無向圖的鄰接矩陣是一個(gè)（）。

A.對(duì)稱矩陣B零矩陣C.上三角矩陣D.對(duì)角矩陣

（8）下列說法中正確的是（）。

A.一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為n（n-l）

B.連通圖的生成樹是該圖的一個(gè)極大連通子圖

C.圖的廣度優(yōu)先搜索是一個(gè)遞歸過程

D.在非連通圖的遍歷過程中，每調(diào)用一次深度優(yōu)先搜索算法都得到該圖的…

個(gè)連通分量

（9）如果從無向的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則

該圖一定是（）。

A.完全圖B.連通圖C.有回路D.一棵樹

問答題

（1）假設(shè)一棵完全圖包含A、B,…，G七個(gè)結(jié)點(diǎn)，寫出其鄰接矩陣。

（2）假設(shè)一棵完全圖包含A,B,C,D四個(gè)結(jié)點(diǎn)，畫出其鄰接表。

（3）設(shè)有一有向圖為G=（V,E）o其中,V={vO,vl,v2,v3},E={<vl,vO>,<v2,

vl>,<v3,v2>,<v3,vl>,<vO,v3>}o請(qǐng)畫出該有向圖。

（5）對(duì)于下圖，從頂點(diǎn)vO出發(fā)分別畫出其深度優(yōu)先生成樹和廣度優(yōu)先生成樹。

(6)對(duì)于圖所示的網(wǎng)絡(luò)，請(qǐng)分別用Prim算法和Kruskal算法構(gòu)造該網(wǎng)絡(luò)的最小

生成樹。

(7)畫出以頂點(diǎn)VI為初始源點(diǎn)遍歷所示的有向圖所得到的深度優(yōu)先遍歷和廣度

優(yōu)先遍歷生成森林。

(8)試寫出下圖所示有向圖的利用無前趨頂點(diǎn)優(yōu)先算法求得的拓?fù)湫蛄?，設(shè)鄰接

表的邊表結(jié)點(diǎn)中的鄰接點(diǎn)序號(hào)是遞增有序的。

5

※〈習(xí)題八〉

略

5

※〈習(xí)題九〉

填空題

(1)采用二分法進(jìn)行查找的查找表，應(yīng)選擇方式的存儲(chǔ)

結(jié)構(gòu)。

(2)在各種查找法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是

(3)在分塊查找法中，首先查找,然后再查找相應(yīng)的

(4)假設(shè)在有序表A[0……9]中進(jìn)行二分查找，比較一次查找成功的結(jié)點(diǎn)數(shù)為

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

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

，平均查找長度為?

(5)查找有序表R[0……11]中每個(gè)數(shù)據(jù)元素，假設(shè)查找在等概率情況下進(jìn)行，則進(jìn)行順序

查找的平均查找長度為,進(jìn)行二次查找的平均查找長度為。

(6)假設(shè)在線性表R[0……59]中進(jìn)行分塊查找，共分10塊，每塊長度為6,若利用順序查

找法對(duì)索引表和子塊進(jìn)行查找，則查找每個(gè)元素的平均查找長度為。

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

裝填因子a的值越小，存取數(shù)據(jù)元素時(shí)發(fā)生沖突的可能性就o

(8)在一個(gè)10階B-樹中，每個(gè)根結(jié)點(diǎn)所含關(guān)鍵字的數(shù)目最多允許為,最少

允許為?

(9)一棵深度為h的B-樹上，任一個(gè)葉子結(jié)點(diǎn)所處的層數(shù)為，當(dāng)向該B-樹

插入一個(gè)新結(jié)點(diǎn)時(shí)，為了檢索插入位置需讀取個(gè)結(jié)點(diǎn)。

(10)當(dāng)向B-樹中插入關(guān)鍵字時(shí)，可能引起結(jié)點(diǎn),最終可能導(dǎo)致該B-樹的高度

,當(dāng)從B-樹中刪除關(guān)鍵字時(shí)，可能引起結(jié)點(diǎn),最終可能導(dǎo)致該B-

樹的高度?

選擇題

(1)采用順序查找法檢索長度為n的線性表，則檢索每個(gè)元素的平均比較次數(shù)

為O

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

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

A.有序表B.分塊有序表C.二叉排序樹

D.線性鏈表

(3)如果要求一個(gè)線性表既能快速查找，又能適應(yīng)動(dòng)態(tài)變化的要求，則宜采用

的檢索方法是。

A.分塊檢索B.順序檢索C.二分檢索D.基于屬

性檢索

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

A.鍵值有序的鏈接表B.鍵值有序的順序表

C.鏈接表但鍵值不一定有序D.順序但鍵值不一定有序

(5)有一個(gè)有序表{1,4,6,10,18,35,42,53,67,71,78,84,92,99},

當(dāng)用二分查找法查找鍵值為84的結(jié)點(diǎn)時(shí)，經(jīng)比較后查找成功。

A.2B.3C.4D.12

(6)順序檢索一個(gè)具有n個(gè)數(shù)據(jù)元素的線性表，其時(shí)間復(fù)雜度為,二分檢

索一個(gè)具有n個(gè)數(shù)據(jù)元素的線性表，其時(shí)間復(fù)雜度為o

A.O(n)B.O(log2n)C.O(n2)

D.O(nlog2n)

(7)在一棵3階B-樹上，每個(gè)結(jié)點(diǎn)包括的子樹相同，最多為，最少為o

A.1B.2C.3D.4

(8)設(shè)散列表長度為m,散列函數(shù)為H(key)=key%p,為了減少發(fā)生沖突的

可能性，p應(yīng)取。

A.小于m的最大奇數(shù)B.小于m的最大素?cái)?shù)

C.小于m的最大偶數(shù)D.小于m的最大合數(shù)

判斷題

(1)在等概率情況下實(shí)現(xiàn)分塊查找，其平均查找長度不僅與表的個(gè)數(shù)有關(guān)，而

且與每一塊中的元素個(gè)數(shù)有關(guān)。()

(2)刪除一個(gè)排序二叉樹中的一個(gè)結(jié)點(diǎn)，在重新插入上去，一定能得到原來的

二叉排序樹;()

(3)只要采用順序存儲(chǔ)結(jié)構(gòu)存放的數(shù)據(jù)元素，都可以利用折半查找法進(jìn)行查找。

()

(4)二叉平衡樹要求任意結(jié)點(diǎn)的左右子樹的高度必須相等。()

5

※〈習(xí)題十〉

填空題

(1)排序是將一組任意排列的數(shù)據(jù)元素按的值從小到大或從

大到小重新排列成有序的序列。

(2)在排序前，關(guān)鍵字值相等的不同記錄間的前后相對(duì)位置保持

的排序方法稱為穩(wěn)定的排序方法。

(3)在排序前，關(guān)鍵字值相等的不同記錄間的前后相對(duì)位置

的排序方法稱為不穩(wěn)定的排序方法。

(5)當(dāng)數(shù)據(jù)已經(jīng)有序時(shí)，不再進(jìn)行排序的方法是排序方法。

（6）在堆排序中，首先要使數(shù)據(jù)成堆，在堆中所有的都不比其孩子結(jié)

點(diǎn)?。ɑ虼螅?/p>

（7）在直接插入排序的方法中，當(dāng)需要將第i個(gè)數(shù)據(jù)插入時(shí)，此時(shí)前i-l個(gè)數(shù)據(jù)

是的。

（8）對(duì)一個(gè)基本有序的數(shù)據(jù)進(jìn)行排序排序方法運(yùn)算次數(shù)最

少。

選擇題

（1）排序是根據(jù)的大小重新安排各元素的順序。

A.數(shù)組B.關(guān)鍵字C.元素D.結(jié)點(diǎn)

（2）內(nèi)部排序是根據(jù)關(guān)鍵字的大小重新安排各的順序。

A.關(guān)鍵字B.數(shù)據(jù)項(xiàng)C.文件D.數(shù)據(jù)元素

（3）穩(wěn)定的排序方法是指在排序中，關(guān)鍵字相等的不同記錄間的前后相對(duì)位置

A.保持不變B.保持相反C.不定D.無關(guān)

（4）不穩(wěn)定的排序方法是指在排序中，關(guān)鍵字相等的不同記錄間的前后相對(duì)位

置o

A.保持不變一步B.保持相反C.不定D.無關(guān)

（5）內(nèi)部排序是指在排序的整個(gè)過程中，全部數(shù)據(jù)都在計(jì)算機(jī)的

A.內(nèi)存儲(chǔ)器B.外存儲(chǔ)器C.內(nèi)存儲(chǔ)器和外存儲(chǔ)器D.寄

存器

（6）直接插入排序的方法是的排序方法。

A.穩(wěn)定B.不穩(wěn)定C.外部D.選擇

（7）直接插入排序的方法是從第個(gè)元素開始，插入前邊適當(dāng)位置的

排序方法。

A.1B.2C.3D.n

（8）冒泡排序的方法是的排序方法。

A.穩(wěn)定B.不穩(wěn)定C.外部D.選擇

（9）用冒泡排序的方法對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，第一趟共比較對(duì)元

素。

A.1B.2C.n-1D.n

（10）快速排序的方法是的排序方法。

A.穩(wěn)定B.不穩(wěn)定C.外部D.選擇

（11）用快速排序的方法對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，首先將第一個(gè)元素移到在排

序后的位置。

A.1B.2C.n-1D.n

（12）直接選擇排序的方法是的排序方法。

A.穩(wěn)定B.不穩(wěn)定C.外部D.選擇

（13）使用直接選擇排序的方法對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，首先將選擇的元素放在

第個(gè)元素的位置。

A.1B.2C.n-1D.n

（14）堆排序的方法是的排序方法。

A.穩(wěn)定B.不穩(wěn)定C.外部D.選擇

（15）用堆排序的方法堆n個(gè)數(shù)據(jù)進(jìn)行排序，首先從堆的根選擇出最大（或最

?。┑脑匾频轿恢胦

A.1B.2C.n-1D.n

（16）基數(shù)排序的方法是的排序方法。

A.穩(wěn)定B.不穩(wěn)定C.外部D.選擇

（17）用基數(shù)排序的方法對(duì)n個(gè)十進(jìn)制數(shù)據(jù)進(jìn)行排序，對(duì)n個(gè)元素進(jìn)行一趟分

配時(shí)，最多被分成組，兩兩歸并。

A.10B.2C.n-1D.n

（18）直接插入排序的方法要求被排序的數(shù)據(jù)存儲(chǔ)。

A.必須是順序B.必須是鏈表C.順序或鏈表D.二叉樹

（19）冒泡排序的方法要求被排序的數(shù)據(jù)存儲(chǔ)。

A.必須是順序B.必須是鏈表C.順序或鏈表D.二叉樹

（20）快速排序的方法要求被排序的數(shù)據(jù)存儲(chǔ)。

A.必須是順序B.必須是鏈表C.順序或鏈表D.二叉樹

（21）直接選擇排序的方法要求被排序的數(shù)據(jù)存儲(chǔ)。

A.必須是順序B.必須是鏈表C.順序或鏈表D.二叉樹

（22）基數(shù)排序的方法要求被排序的數(shù)據(jù)存儲(chǔ)。

A.必須是順序B.必須是鏈表C.順序或鏈表D.二叉樹

（23）在下列排序方法中，是不穩(wěn)定的排序方法。

A,直接插入排序B.直接選擇排序C.冒泡D.基數(shù)排序

簡(jiǎn)答題

（1）簡(jiǎn)述什么是穩(wěn)定的排序，什么是不穩(wěn)定的排序。

（2）寫出使用直接插入排序法、冒泡排序法、快速排序法、直接選擇排序法、

堆排序法、歸并排序法對(duì)下列數(shù)據(jù)進(jìn)行從小到大排序的中間過程和最后結(jié)果。

[83,40,63,13,84,35,96,57,39,79,61,15]

（3）下列程序是按關(guān)鍵字的值從大到小進(jìn)行直接選擇排序的算法，將算法補(bǔ)充

o

Select（listr,intn）

{for（i=1;;i++）

{k=i；

for（j=i+1；；j++）

if（r[k].key<r[j].key）;

if（）swap（r[k],r[i]）;/*i■的與明交換*/

}

)

(4)將下列程序按關(guān)鍵字值從小到大直接插入排序的算法補(bǔ)充完整。

Straightsort(listr)

{for(；i++)

{=r[i]；

j=i-1；

while(r[O].key<r[j].key){=r[j];

j——；

)

__________=r[0];

)

)

(5)將下列按關(guān)鍵字值從小到大進(jìn)行冒泡排序的算法補(bǔ)充完整。

Bubblesort(intn.listr)

{flag=；

m=n-1;

while(m>0&&flag)

{flag=O;

for(i=1;i<=m;i++)

if(r[i].keyr[i+1].key){flag=;

swap(r[i],r[i+1];/*r[i]r[i+1]*/

}

m-;

)

)

(6)若快速排序算法中完成一趟快速排序的算法是Quickpass(listr,inth,int

i),將完整的快速排序遞歸算法補(bǔ)充完整。

Quicksort(listr,ints,intt)

{if(s<t){Quickpass(r,s,t,i);

Quicksort(r,);

Quicksort(r,);

}

}

(7)若進(jìn)行一趟二路歸并的算法是MpassQistajistb,intn,inth),其中a和b

是數(shù)組，該算法是將a中相鄰的、長度為h的兩個(gè)有序的子序列合并成一個(gè)長

度為2h的一個(gè)有序子序列，n是a中記錄的個(gè)數(shù)。將下列二路歸并算法補(bǔ)充完

整。

Msort(lista,intn)

{h=;

while(h<n){Mpass(a,b,);

h*=2;

Mpass(,n,h);

h*=2;

)

)

5

※〈習(xí)題H>

(1)外部排序是指在排序的整個(gè)過程中，全部數(shù)據(jù)在計(jì)算機(jī)的中完

成的排序。

A.內(nèi)存儲(chǔ)器B,外存儲(chǔ)器C,內(nèi)存儲(chǔ)器和外存儲(chǔ)器D.寄

存器

(2)簡(jiǎn)述什么是外部排序。

(3)外部排序是指在排序前被排序的全部數(shù)據(jù)都存儲(chǔ)在計(jì)算機(jī)的

儲(chǔ)器中。

一、單選題(每題2分，共20分)

1.1.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下(B)方面的內(nèi)容。

A.健壯性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度

2.2.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)

點(diǎn)，則執(zhí)行()。

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

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

3.3.對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？()

A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作

C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變

4.4.一個(gè)棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是

(C)

A.231B.321

C.312D.123

5.5.AOV網(wǎng)是一種()□

A.有向圖B.無向圖C.無向無環(huán)圖D.有向無環(huán)圖

6.6.采用開放定址法處理散列表的沖突時(shí)，其平均查找長度()。

A.低于鏈接法處理沖突B.高于鏈接法處理沖突

C.與鏈接法處理沖突相同D.高于二分查找

7.7.若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為()參數(shù)。

A.值B.函數(shù)C.指針D.引用

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

有相同的()□

A.行號(hào)B.列號(hào)C.元素值D.非零元素個(gè)數(shù)

9.9.快速排序在最壞情況下的時(shí)間復(fù)雜度為()o

A.O(log2n)B.O(nlog2n)C.0(n)D.0(n2)

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

2

A.O(n)B.0(1)C.O(log2n)D.O(n)

二、二、運(yùn)算題(每題6分，共24分)

1.1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的。當(dāng)結(jié)點(diǎn)之間存在M

對(duì)N(M：N)的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為o

2.2.隊(duì)列的插入操作是在隊(duì)列的—尾進(jìn)行，刪除操作是在隊(duì)列的

—首進(jìn)行。

3.3.當(dāng)用長度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示?？?，則

表示棧滿的條件是—top=0—(要超出才為滿)一o

4.4.對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度

為，在表尾插入元素的時(shí)間復(fù)雜度為o

5.5.設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié)，行下標(biāo)i從0

到7,列下標(biāo)j從0到3,則二維數(shù)組W的數(shù)據(jù)元素共占用一一個(gè)字

節(jié)。W中第6行的元素和第4列的元素共占用個(gè)字節(jié)。若按行

順序存放二維數(shù)組W,其起始地址為100,則二維數(shù)組元素W[6,3]的起始

地址為o

6.6.廣義表A=(a,(a,b),((a,b),c)),則它的深度為,它的長度為

7.7.二叉樹是指度為2的樹。一棵結(jié)點(diǎn)數(shù)為N的二叉

樹.，其所有結(jié)點(diǎn)的度的總和是o

8.8.對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)

0對(duì)一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到

的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的。

9.9.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為

個(gè)，其中個(gè)用于指向孩子，

_________________個(gè)指針是空閑的O

10.10.若對(duì)一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存

儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A⑼中。其余類推，則A[i]

元素的左孩子元素為，右孩子元素為，雙親元素為

11.11.在線性表的散列存儲(chǔ)中，處理沖突的常用方法有

和兩種O

12.12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用

排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序

是穩(wěn)定時(shí)，宜采用排序。

三、三、運(yùn)算題(每題6分，共24分)

1.1.已知一個(gè)6x5稀疏矩陣如下所示，

00001

00000

0-1000

0000-2

50000

00700

試：

(1)(1)寫出它的三元組線性表；

(2)(2)給出三元組線性表的順序存儲(chǔ)表示。

2.2.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起,

逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。

3.3.對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的

邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫出：

(1)從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹.；

(2)從頂點(diǎn)②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；

4.4.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：

V={1,2,3,4,5,6,7};

/E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>

(2^—______\,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>}

若存儲(chǔ)它采用鄰接表，并且每個(gè)頂

點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序

圖6號(hào)從小到大的次序鏈接的，按主教材

中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。

四、四、閱讀算法(每題7分，共14分)

1.1.intPrime(intn)

(

inti=l;

intx=(int)sqrt(n);

while(-H-i<=x)

if(n%i=O)break;

if(i>x)return1;

elsereturn0;

)

(1)(1)指出該算法的功能；

(2)(2)該算法的時(shí)間復(fù)雜度是多少？

2.2.寫出下述算法的功能：

voidAJ(adjlistGL,inti,intn)

{

QueueQ;

InitQueue(Q);

cout?i?**;

visited[i]=true;

QInsert(Q,i);

while(!QueueEmpty(Q)){

intk=QDelete(Q);

edgenode*p=GL[k];

while(p!=NULL)

{

intj=p->adjvex;

if(!visited[j])

{

cout<<j?'

visited[j]=true;

QInsert(Q,j);

p=p->next;

)

五、五、算法填空(共8分)

如下為二分查找的非遞歸算法，試將其填寫完整。

IntBinsch(ElemTypeA[],intn,KeyTypeK)

(

intlow=0;

inthigh=n-l;

while(low<=high)

(

intmid=；

if(K==A[mid].key)returnmid;〃查找成功，返回元素的下標(biāo)

elseif(K<[mid].key)

__________________________________；