數(shù)據(jù)結(jié)構(gòu)(I卷)

1、.數(shù)據(jù)結(jié)構(gòu)試卷(I卷)班級(jí):_學(xué)號(hào):_姓名:_得分:_題號(hào)一二三四五六七八九十成績復(fù)核得分閱卷題目部分，(卷面共有45題,100分,各大題標(biāo)有題量和總分)一、判斷正誤(11小題,共11分)1即使對(duì)不含相同元素的同意輸入序列進(jìn)行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序也一定相同。（ ）2棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。( )3任何一個(gè)非空廣義表，其表頭可能是單元素或廣義表，其表尾必定是廣義表。( ) 4己知二叉樹的前序遍歷序列和后序遍歷序列并不能唯一地確定這棵樹，因?yàn)椴恢罉涞母Y(jié)點(diǎn)是哪一個(gè)。( )5有n個(gè)數(shù)存放在伊維數(shù)組h1n中，在進(jìn)行順序查找時(shí)這n個(gè)數(shù)的排列有序或無序其平均查找長

2、度小同。( ) 6二叉樹中，具有兩個(gè)子女的結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)最多只能有一個(gè)子女。7用希爾(Shell)方法排序時(shí)，若關(guān)鍵字的初始排序雜亂無序，則排序效率就低。（ ）8外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進(jìn)行排序，因此排序所花的時(shí)間取決于內(nèi)部排序的時(shí)間。 （ ）9完全二叉樹就是滿二叉樹。（ ）10在散列法中，一個(gè)可用散列函數(shù)必須保證絕對(duì)不產(chǎn)生沖突。（ ）11快速排序是對(duì)起泡排序的一種改進(jìn)。( )二、單項(xiàng)選擇題(20小題,共42分)1在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)指針q所指向的新結(jié)點(diǎn)，其修改指針的操作是_A、 B、 C、 D、2雙向鏈表中有兩個(gè)指針域，llink和rl

3、ink分別指向前趨及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，現(xiàn)要求刪去p所指結(jié)點(diǎn)，則正確的刪除是（ ）（鏈中結(jié)點(diǎn)數(shù)大于2，p不是第一個(gè)結(jié)點(diǎn)）A、p.llink.rlink:=p.llink; p.llink.rlink:=p.rlink; dispose(p); B、dispose(p); p.llink.rlink:=p.llink; p.llink,rlink:=p.rlink; C、p.llink.rlink:=p.llink; dispose(p); p.llink.rlink:=p.rlink; D、以上A，B，C都不對(duì)。 3某堆棧的輸入序列為a, b，c ，d,下面的四個(gè)序列中，不可能是它

4、的輸出序列的是 A、 a，c，b，d B、 b, c，d，a C、 c, d，b, a D、 d, c，a，b4棧和隊(duì)都是A、順序存儲(chǔ)的線性結(jié)構(gòu) B、 鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu) C、 限制存取點(diǎn)的線性結(jié)構(gòu) D、 限制存取點(diǎn)的非線性結(jié)構(gòu)5數(shù)組的基本操作主要包括 。 A、 建立與刪除 B、 索引與修改 C、 訪問與修改 D、 訪問與索引 6下面說法不正確的是A、 廣義表的表頭總是一個(gè)廣義表 B、 廣義表的表尾總是一個(gè)廣義表 C、 廣義表難以用順序存儲(chǔ)結(jié)構(gòu) D、 廣義表可以是一個(gè)多層次的結(jié)構(gòu)7設(shè)有一表示算術(shù)表達(dá)式的二叉樹（見下圖），它所表示的算術(shù)表達(dá)式是A、 A*B+C/(D*E)+(F-G) B、 (

5、A*B+C)/(D*E)+(F-G) C、 (A*B+C)/(D*E+（F-G）) D、 A*B+C/D*E+F-G8深度為（根據(jù)的層次為）的二叉樹至多有( )個(gè)結(jié)點(diǎn)。A、 64 B、 63 C、 31 D、 32 9下面不正確的說法是 (1) 在AOE網(wǎng)中減小任一關(guān)鍵活動(dòng)上的權(quán)值后，整個(gè)工期也就相應(yīng)減小 (2)AOE一網(wǎng)工程工期為關(guān)鍵活動(dòng)上的權(quán)之和；(3)在關(guān)鍵活路徑上的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)也必在關(guān)鍵路徑上， A、(1) B、(2) C、(3) D、(1)、(2)10下列說法中不正確的是 A、無向圖中的極大連通子圖稱為連通分量 B、連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的

6、頂點(diǎn) C、圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點(diǎn) D、有向圖的遍歷不可采用廣度優(yōu)先搜索方法11設(shè)有一個(gè)按各元素的值排好序的線性表且長度大于2，對(duì)給定的值K，分別用順序查找法和二分法查找一個(gè)與K相等的元素，比較次數(shù)分別s 和b；在查找不成功的情況下，正確的s 和b的數(shù)量關(guān)系是_ A、 總有s=b B、總有sb C、總有sb D、與K大小有關(guān)12設(shè)散列表的長m=14，散列函數(shù)為h(k)=k11，表中已有4個(gè)記錄(如圖所示)，如果采用二次探測再散列來處理沖突，則關(guān)鍵字為49的記錄其存儲(chǔ)地址是 A、 8 B、 3 C、 5 D、 913歸并排序中，歸并的趟數(shù)是A、O（n） B、O(logn

7、) C、O(nlogn) D、O(n*n) 14下列排序算法中，在待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的是( )排序。 A、 冒泡 B、 希爾 C、 快速 D、 堆 15快速排序在最壞情況下時(shí)間復(fù)雜度是，比（ ）的性能差。 A、堆排序 B、起泡排序 C、選擇排序16若對(duì)一個(gè)元素進(jìn)行直接選擇排序，則進(jìn)行任一趟排序的過程中，為尋找最小值元素所需要的時(shí)間復(fù)雜性為 A、O(l) B、 C、 D、17數(shù)據(jù)表示是指數(shù)據(jù)。 A、 書寫在紙上B、 從機(jī)外轉(zhuǎn)為機(jī)內(nèi)C、 磁盤中的數(shù)據(jù)D、 光盤中的數(shù)據(jù) 18以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)？ A、廣義表 B、 二叉樹 C、稀疏矩陣 D、 串19某二叉樹的前序和后序

8、序列正好相反，則該二叉樹一定是（）的二叉樹。A、空或只有一個(gè)結(jié)點(diǎn) B、高度等于其結(jié)點(diǎn)數(shù) C、任一結(jié)點(diǎn)無左孩子 D、任一結(jié)點(diǎn)無右孩子20在10階B-樹中根結(jié)點(diǎn)所包含的關(guān)鍵碼個(gè)數(shù)最多為（ ），最少為A、1 B、2 C、9 D、10三、填空題(14小題,共47分)1在一個(gè)不帶頭結(jié)點(diǎn)單鏈表中，在表頭插入或刪除與在其他位置插入或刪除其操作過程_。2根據(jù)需要，用適當(dāng)?shù)恼Z句填入下面算法的_中：問題：設(shè)有n件物品，重量分別為w1,w2,w3,wn和一個(gè)能裝載總重量為T的背包。能否從n件物品中選擇若干件恰好使它們的重量之和等于T。若能，則背包問題有解，否則無解。解此問題的算法如下： FUNCTION kanp_

9、stack(VAR stack,w:ARRAY1.n OF real; VAR top:integer; T:real):boolean; w1：n 存放n件物品的重量，依次從中取出物品放入背包中，檢查背包重量，若不超過T，則裝入，否則棄之，取下一個(gè)物品試之。若有解則返回函數(shù)值true,否則返回false BEGIN top:=0; i:=1; i指示待選物品 WHILE (1)_ AND(2)_DO IF (3)_ OR (4)_ AND (i0) THEN i:=(7)_;取出棧頂物品 top:= (8)_ ；T:= (9)_ ; 恢復(fù)T值 i:=i+1 準(zhǔn)備挑選下一件物品 ; ; RET

10、URN(10)_) 背包無解 END;3設(shè)有三對(duì)角矩陣如下圖所示，將帶狀區(qū)域中的元素（|i-j|=1)放在一維數(shù)組B中，則B的大小為_。元素在B 中的位置是_下標(biāo)從0開始計(jì))4二叉樹結(jié)點(diǎn)的對(duì)稱序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹結(jié)點(diǎn)的前序序列為 ,則該二叉樹對(duì)應(yīng)的樹林包括 棵樹。5對(duì)于前序遍歷和中序遍歷結(jié)果相同的二叉樹為_,對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹為_.A、一般二叉樹 B、只有根結(jié)點(diǎn)的二叉樹 C、根結(jié)點(diǎn)無左孩子的二叉樹 D、根結(jié)點(diǎn)無右孩子的二叉樹 E、所有結(jié)點(diǎn)只有左子樹的二叉樹 F、所有結(jié)點(diǎn)只有右子樹的二叉樹6設(shè)有N個(gè)結(jié)點(diǎn)的完全二叉樹順序存放在向量A1:N中，其下標(biāo)值最大的分支結(jié)點(diǎn)為_。7具有n個(gè)結(jié)點(diǎn)的滿二叉樹，其葉結(jié)點(diǎn)的個(gè)數(shù)是_。8n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有_個(gè)非零元崇。9對(duì)長度為n的查找表進(jìn)行查找時(shí)假定查找笫i個(gè)元素的概率為Pi，查找長度(即在查找過程中依次同有關(guān)元素比較的總次數(shù))為Ci，則在查找成功情況下的平均查找長度的計(jì)算公式為_。10對(duì)閉散列表來說，_的方法就是處理沖突的方法。11在一棵有n個(gè)結(jié)點(diǎn)的非平衡二叉樹中進(jìn)行查找，平均時(shí)間復(fù)雜度的上限(即最壞情況平均時(shí)間復(fù)雜度)為_。12在折半查