2009-20101考試試卷數(shù)據(jù)結(jié)構(gòu)數(shù)字081

1、。裝。訂。線。2009 年2010 年第一學(xué)期數(shù)據(jù)結(jié)構(gòu) 試卷 A 卷學(xué)院班級學(xué)號分?jǐn)?shù)時間共 120 分鐘一、單項(xiàng)選擇題( 102= 20)1、以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ ）？A、廣義表C、稀疏矩陣B、二叉樹D、串2、在一個以 h 為頭的單循環(huán)鏈中，pA、p-next=NULLC、p-next-next= NULL指針指向鏈尾的條件是（）。B、p-next =hD、p！=NULL3、設(shè) abcdef 以所給的次序進(jìn)棧，若在進(jìn)棧操作時，允許退棧操作,則下面得不到的序列為（ ）。A、fedcbaB、 bcafedC、dcefbaD、 cabdef4、串的長度是指（）A、串中所含不同字母的個數(shù)

2、C、串中所含不同字符的個數(shù)B、串中所含字符的個數(shù)D、串中所空格字符的個數(shù)5、順序表表示的循環(huán)隊(duì)列中，隊(duì)列滿的條件是（）A、front=rearC、(front+1) %MAXSIZE=rear 6、在二叉樹的第i 層上最多有（B、front=rear+1D、(rear+1)%MAXSIZE=front）個結(jié)點(diǎn)B、2i-1C、2i-1A、不確定D、2i）條邊。7、要連通具有n 個頂點(diǎn)的有向完全圖，需要（n2An(n-l)B1/2C1/2n(n-1)D2n得分閱卷人題號一二三四五六總分得分閱卷人8、從鍵盤依次輸入關(guān)鍵字的值：v、i、s、u、a、l、c。建立二叉排序樹，則其中序遍歷序列為（）A、ai

3、slcuvC、acilsuvB、slcuviaD、aclisuv9、用線性探測法查找散列表，可能要探測多個散列地址，這些位置上的鍵值（）A、一定都是同義詞C、都相同B、一定都不是同義詞D、不一定都是同義詞10、對序列15，9，7，8，20，-1，4進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)?，7，8，15，-1，4，20；則采用的是（）排序。A. 選擇B. 快速C.D. 冒泡二、填空題(102=20)1、數(shù)據(jù)元間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：（1）和（2）。2、若經(jīng)常需要對線性表進(jìn)行和刪除運(yùn)算，則最好采用 （3）結(jié)構(gòu)，若經(jīng)常需要對線性表進(jìn)行查找運(yùn)算，則最好采用 （4） 結(jié)構(gòu)。3、棧的修改是按（

4、5）原則進(jìn)行，隊(duì)列的修改是按（6）原則進(jìn)行。4、深度為 6（根的層次為 1）的二叉樹至多有 （7）個結(jié)點(diǎn)。5、將含 100 個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點(diǎn)，根結(jié)點(diǎn)的為 1，為 49 的結(jié)點(diǎn)X 的雙親為 （8）6、N 個頂點(diǎn)的連通圖的生成樹有 （9）條邊。7、一個有向圖 G中若有弧、和,則在圖 G 的拓?fù)湫蛄兄?，頂點(diǎn)vi,vj 和vk 的相對位置為_（10）_。得分題號12345題號678910得分閱卷人1、在循環(huán)隊(duì)列中，front 指向隊(duì)列中第一個元素的前一位置，rear 指向?qū)嶋H的隊(duì)尾元素，隊(duì)列為滿的條件是 front=rear。（）2、對鏈表進(jìn)行和刪除操作時，不

5、必移動結(jié)點(diǎn)。（）3、?？梢宰鳛閷?shí)現(xiàn)遞歸調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。（）4、在一個有向圖的拓?fù)湫蛄兄?，若頂點(diǎn) a 在頂點(diǎn) b 之前，則圖中必有一條弧。()5、對有向圖 G，如果從任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問每個頂點(diǎn)，則該圖一定是完全圖。()6、“順序查找法”是指在順序表上進(jìn)行查找的方法。（）7、向二叉排序樹一個新結(jié)點(diǎn)時，新結(jié)點(diǎn)一定會成為二叉排序樹的一個葉子結(jié)點(diǎn)。（）8、鍵值序列A，C，D，E，F(xiàn)，E，F(xiàn)是一個堆。9、算法就是程序（）（）10、完全二叉樹肯定是平衡二叉樹。（）四 應(yīng)用題 (45= 20)1、將下圖的森林轉(zhuǎn)換為二叉樹，畫出二叉樹。（5 分）AEIBCDFGJ得分閱卷人題

6、號12345678910閱卷人2、下圖表示一個地區(qū)的交通網(wǎng)，頂點(diǎn)表示城市，邊表示連結(jié)城市間的公路，邊上的權(quán)表示修建公路花費(fèi)的代價。怎樣選擇能夠溝通每個城市且總造價最省的 n-1 條公路，畫出所有可能的方案。（10 分）v16v3195v5v4183、已知一個無向圖的鄰接表如下圖所示。（本題 5 分）12345(1) 畫出這個圖。(2)以v1 為出發(fā)點(diǎn)，對圖進(jìn)行廣度優(yōu)先搜索，寫出一種序列。231235414542V1V2V3V4V5五、算法設(shè)計(jì)題( 310= 30)1、設(shè)二叉樹以二叉鏈表為結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)為。設(shè)計(jì)一個算法，查找在先根序列中處于第k 個位置的結(jié)點(diǎn)。2、分別編寫在順序表和結(jié)點(diǎn)的單鏈表上統(tǒng)計(jì)出值為 x 的元素個數(shù)的算法，統(tǒng)計(jì)結(jié)果由函數(shù)值返