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

1、數(shù)據(jù)結(jié)構(gòu)試卷(I卷)班級(jí):_學(xué)號(hào):_姓名:_得分:_題號(hào)一二三四五六七八九十成績(jī)復(fù)核得分            閱卷           題目部分，(卷面共有45題,100分,各大題標(biāo)有題量和總分)一、判斷正誤(11小題,共11分)1即使對(duì)不含相同元素的同意輸入序列進(jìn)行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序也一定相同。（   ）2棧和隊(duì)

2、列都是限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu)。(    )3任何一個(gè)非空廣義表，其表頭可能是單元素或廣義表，其表尾必定是廣義表。(    )     4己知二叉樹(shù)的前序遍歷序列和后序遍歷序列并不能唯一地確定這棵樹(shù)，因?yàn)椴恢罉?shù)的根結(jié)點(diǎn)是哪一個(gè)。(    )5有n個(gè)數(shù)存放在伊維數(shù)組h1n中，在進(jìn)行順序查找時(shí)這n個(gè)數(shù)的排列有序或無(wú)序其平均查找長(zhǎng)度小同。(    )  6二叉樹(shù)中，具有兩個(gè)子女的結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)最多只能有一個(gè)子女。7用希爾(Shel

3、l)方法排序時(shí)，若關(guān)鍵字的初始排序雜亂無(wú)序，則排序效率就低。（    ）8外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進(jìn)行排序，因此排序所花的時(shí)間取決于內(nèi)部排序的時(shí)間。  （    ）9完全二叉樹(shù)就是滿(mǎn)二叉樹(shù)。（    ）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)，其修改指針的操

4、作是_A、 B、 C、 D、2雙向鏈表中有兩個(gè)指針域，llink和rlink分別指向前趨及后繼，設(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;  d

5、ispose(p);  p.llink.rlink:=p.rlink; D、以上A，B，C都不對(duì)。  3某堆棧的輸入序列為a, b，c ，d,下面的四個(gè)序列中，不可能是它的輸出序列的是    A、 a，c，b，d         B、 b, c，d，a    C、 c, d，b, a         D、 d, c，a，b4棧和隊(duì)都是A、順序存儲(chǔ)的線(xiàn)性結(jié)構(gòu)&

6、#160;       B、 鏈?zhǔn)酱鎯?chǔ)的非線(xiàn)性結(jié)構(gòu) C、 限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu)     D、 限制存取點(diǎn)的非線(xiàn)性結(jié)構(gòu)5數(shù)組的基本操作主要包括 。  A、 建立與刪除     B、 索引與修改     C、 訪(fǎng)問(wèn)與修改    D、 訪(fǎng)問(wèn)與索引 6下面說(shuō)法不正確的是A、 廣義表的表頭總是一個(gè)廣義表       

7、B、 廣義表的表尾總是一個(gè)廣義表 C、 廣義表難以用順序存儲(chǔ)結(jié)構(gòu)          D、 廣義表可以是一個(gè)多層次的結(jié)構(gòu)7設(shè)有一表示算術(shù)表達(dá)式的二叉樹(shù)（見(jiàn)下圖），它所表示的算術(shù)表達(dá)式是A、 A*B+C/(D*E)+(F-G)                 B、 (A*B+C)/(D*E)+(F-G)  C、 (A*B+C)/(D*E+（F

8、-G）)           D、 A*B+C/D*E+F-G8深度為（根據(jù)的層次為）的二叉樹(shù)至多有(    )個(gè)結(jié)點(diǎn)。 A、 64       B、 63      C、 31       D、 32 9下面不正確的說(shuō)法是    (1) 在A(yíng)OE網(wǎng)中減小任一

9、關(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下列說(shuō)法中不正確的是   A、無(wú)向圖中的極大連通子圖稱(chēng)為連通分量   B、連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)   C、圖的

10、深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)   D、有向圖的遍歷不可采用廣度優(yōu)先搜索方法11設(shè)有一個(gè)按各元素的值排好序的線(xiàn)性表且長(zhǎng)度大于2，對(duì)給定的值K，分別用順序查找法和二分法查找一個(gè)與K相等的元素，比較次數(shù)分別s 和b；在查找不成功的情況下，正確的s 和b的數(shù)量關(guān)系是_    A、   總有s=b    B、總有s>b    C、總有s<b   D、與K大小有關(guān)12設(shè)散列表的長(zhǎng)m=14，散列函數(shù)為h(k)=k11，表中已有4個(gè)記錄(如圖

11、所示)，如果采用二次探測(cè)再散列來(lái)處理沖突，則關(guān)鍵字為49的記錄其存儲(chǔ)地址是     A、 8    B、 3    C、 5    D、 913歸并排序中，歸并的趟數(shù)是A、O（n）           B、O(logn)            C、O(nlogn)

12、60;       D、O(n*n) 14下列排序算法中，在待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的是(     )排序。     A、 冒泡  B、 希爾  C、 快速  D、 堆  15快速排序在最壞情況下時(shí)間復(fù)雜度是，比（   ）的性能差。    A、堆排序    B、起泡排序    C、選擇排序16若對(duì)

13、一個(gè)元素進(jìn)行直接選擇排序，則進(jìn)行任一趟排序的過(guò)程中，為尋找最小值元素所需要的時(shí)間復(fù)雜性為    A、O(l)      B、       C、      D、17數(shù)據(jù)表示是指數(shù)據(jù)。  A、 書(shū)寫(xiě)在紙上 B、 從機(jī)外轉(zhuǎn)為機(jī)內(nèi) C、 磁盤(pán)中的數(shù)據(jù) D、 光盤(pán)中的數(shù)據(jù) 18以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線(xiàn)性結(jié)構(gòu)？ A、廣義表    

14、0;    B、 二叉樹(shù)      C、稀疏矩陣         D、 串19某二叉樹(shù)的前序和后序序列正好相反，則該二叉樹(shù)一定是（）的二叉樹(shù)。A、空或只有一個(gè)結(jié)點(diǎn)     B、高度等于其結(jié)點(diǎn)數(shù)   C、任一結(jié)點(diǎn)無(wú)左孩子     D、任一結(jié)點(diǎn)無(wú)右孩子20在10階B-樹(shù)中根結(jié)點(diǎn)所包含的關(guān)鍵碼個(gè)數(shù)最多為（  ），最少為A、1 

15、;                 B、2               C、9                   D、10三、填空題(14小題,共47分)1在一個(gè)不帶頭

16、結(jié)點(diǎn)單鏈表中，在表頭插入或刪除與在其他位置插入或刪除其操作過(guò)程_。2根據(jù)需要，用適當(dāng)?shù)恼Z(yǔ)句填入下面算法的_中：?jiǎn)栴}：設(shè)有n件物品，重量分別為w1,w2,w3,wn和一個(gè)能裝載總重量為T(mén)的背包。能否從n件物品中選擇若干件恰好使它們的重量之和等于T。若能，則背包問(wèn)題有解，否則無(wú)解。解此問(wèn)題的算法如下：      FUNCTION kanp_stack(VAR stack,w:ARRAY1.n OF real; VAR top:integer; T:real):boolean;     w1：n 存放n件物品的重量，依次

17、從中取出物品放入背包中，檢查背包重量，若不超過(guò)T，則裝入，否則棄之，取下一個(gè)物品試之。若有解則返回函數(shù)值true,否則返回false BEGIN    top:=0;  i:=1;               i指示待選物品    WHILE (1)_ AND(2)_DO       IF (3)_ OR (4)_ AND (i

18、<n)          THEN  top := (5)_ ;stacktop :=i;第i件物品裝入背包                 T:=T-wi;        IF T=0 THEN RETURN (6)_)  背包問(wèn)題有解 &#

19、160;             ELSE  IF  (i=n )  AND  (top>0)                      THEN  i:=(7)_;取出棧頂物品   

20、                          top:= (8)_ ；T:= (9)_ ;  恢復(fù)T值                    &

21、#160;   i:=i+1        準(zhǔn)備挑選下一件物品                     ;        ;    RETURN(10)_) 背包無(wú)解 END;3設(shè)有三對(duì)角矩陣如下圖所示，將帶狀區(qū)域中的元素（|i-j|<=1)放在一維數(shù)組B中，則B的大小為_(kāi)。元素在B 中的位置是_下標(biāo)從0開(kāi)始計(jì))4二叉樹(shù)結(jié)點(diǎn)的對(duì)稱(chēng)序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹(shù)結(jié)點(diǎn)的前序序列為        ,則該二叉樹(shù)對(duì)應(yīng)的樹(shù)林包括        棵樹(shù)。5對(duì)于前序遍歷和中序遍歷結(jié)果相同的二叉樹(shù)為_(kāi),對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹(shù)為_(kāi).