大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試試題(有答案)

1、wordword數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題一、單選題(每小題 2 分，共 12 分)1在一個(gè)單鏈表HL 中，若要向表頭插入一個(gè)由指針p 指向的結(jié)點(diǎn)，則執(zhí)行( )。HLps pnextHLpnextHL；HLp3pnextHl；pHL；pnextHLnext;HLnextp；2n 個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含(。A.nl條有向邊B.n 條有向邊C.n(n1)2條有向邊D.n(n一1)條有向從一棵二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致(A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)由權(quán)值分別為3，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度(。A24B48C 72 53當(dāng)一個(gè)作為實(shí)

2、際傳遞的對(duì)象占用的存儲(chǔ)空間較大并可能需要修改時(shí)，應(yīng)最好把它說(shuō)明為()參數(shù)以節(jié)省參數(shù)值的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。A.整形B.引用型C.指針型常值引用型向一個(gè)長(zhǎng)度為n 的順序表中插人一個(gè)新元素的平均時(shí)間復(fù)雜度(AO(n)CO(n2)DO(10g2n)二、填空題(每空 1 分，共 28 分) 1數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為、和四種。在廣義表的存儲(chǔ)結(jié)構(gòu)中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個(gè)域?qū)?yīng)不同，各自分別為域和域。中綴表達(dá)式 3x*(2.456)所對(duì)應(yīng)的后綴表達(dá)式為。在一棵高度為h318，則它的最小深度為，最大深度為表示圖的三種存儲(chǔ)結(jié)構(gòu)為、和。n 個(gè)頂點(diǎn)和e表示的圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為。1043

3、和 56和假定對(duì)長(zhǎng)度n144 的線性表進(jìn)行索引順序查找，并假定每個(gè)子表的長(zhǎng)度均為，則進(jìn)行索引順序找的平均查找長(zhǎng)度為，時(shí)間復(fù)雜度為一棵B樹(shù)中的所有葉子結(jié)點(diǎn)均處在上。每次從無(wú)序表中順序取出一個(gè)元素，把這插入到有序表中的適當(dāng)位置，此種排序方法叫做排序； 624假定一棵二叉樹(shù)廣義表表示為歷的結(jié)果。先序： 中序； 后序：已知一個(gè)帶權(quán)圖的頂點(diǎn)集V 和邊集GV0，1，2，3，4，5；wordwordE=(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10，則求出該圖的最小生成樹(shù)的權(quán)。最小生成樹(shù)的權(quán)；3假定一組記錄的排序碼為(46，79，56，3

4、8，40，84，50，42)，則利用堆排序方法建立的初始堆為。4有 7 個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，求出該樹(shù)的帶權(quán)路徑長(zhǎng)度、高度、雙分支結(jié)點(diǎn)數(shù)。帶權(quán)路徑長(zhǎng)度： 高度： 雙分支結(jié)點(diǎn)數(shù)：。四、閱讀算法，回答問(wèn)題(每小題 8 分，共 16 分)1VOldAC(List&L)InitList(L)； InsertRear(L;25)； InsertFront(L，50)； IntaL45，8，12，15，36; for(inti0; i5; i+)if (ai20)InsertFront(L，ai)； elselnsertRear(L，a

5、i)；該算法被調(diào)用執(zhí)行后，得到的線性表L 為： 2void AG(Queue&Q)InitQueue(Q)； inta56，12，5，15，8；for(int i0;i5; QInsert(Q，QDelete(Q)； QInsert(Q，20)；QInsert(Q，QDelete(Q) 十 16)； while(!QueueEmpty(Q)coutQDelete(Q)該算法被調(diào)用后得到的輸出結(jié)果為：五、算法填空，在畫(huà)有橫線的地方填寫(xiě)合適的內(nèi)容(每小題 6 分，共 12 分)從一維數(shù)組 An)中二分查找關(guān)鍵字為 K1。IntBinsch(ElemTypeA，Intlow，int high，Key

6、TypeK)if(lowdataX)return 1; 根結(jié)點(diǎn)的層號(hào)為 1向子樹(shù)中查找x 結(jié)點(diǎn)elseint clNodeLevel(BTif(cl1)return cl+1;int if；若樹(shù)中不存在X 結(jié)點(diǎn)則返回o else return 0；六、編寫(xiě)算法(8 分)HL回，若單鏈表為空則中止運(yùn)行。EIemType MaxValue(LNOde*HL);“數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案一、單選題(每小題 2 分，共 12 分)評(píng)分標(biāo)準(zhǔn)；選對(duì)者得 2 分，否則不得分。1B4D1281順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)散列結(jié)(次序無(wú)先2值或data)子表指或sublist)33 x 24 56 一*十4(3h

7、 1)25 518小于大(或大于等)向上堆頂鄰接矩陣鄰接表邊集數(shù)(次序無(wú)先)9O(n2)O(e)10 131113O(12 同 一 層 13插人選擇14O(nlogn)O(n)22三、運(yùn)算題(每小題 6 分，共 24 分)先序：a，b，c，d，e，f，e2中序：c，b，d，a，f，8，e2 分后序：c，d，b，e，f，e，a2分最小生成樹(shù)的權(quán)6分3(84，79，56，42，40，46，50，38)64帶權(quán)路徑長(zhǎng)度3高度2分雙分支結(jié)點(diǎn)數(shù)1分四、閱讀算法，回答問(wèn)題(每小題 8 分，共 16 分)841(36，12，8，50，25，5，15)25 15 8 6 20 28五、算法填空，在畫(huà)有橫線的地

8、方填寫(xiě)合適的內(nèi)每小題6分，共12分1feturn mid2分returnBinsch(A，low，mid一1，K)2returnBmsch(A，mid+1，high，K)2分2NodeLevel(BTright，X)3(c2=1)returnc2十13分六、編寫(xiě)算法(8 分)評(píng)分標(biāo)準(zhǔn)：請(qǐng)參考語(yǔ)句后的注釋?zhuān)蚋鶕?jù)情況酌情給分。ElemType MaxValue(LNodeO* HL。)if (HL=NUlL)2exit(1)；ElemTypemax：HLdata；3LNOde*p=HI一next；4分while(P!：NULL)7 分if(maxdata)maxp 一 data； pp一next

9、；returnmax；數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料一、填空題數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)和運(yùn)算等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)被形式地定義D,其中D是數(shù)據(jù)元素的有限集合R是D上的關(guān)系有限集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算 這三個(gè)方面的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。多關(guān)系。在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒(méi)有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。在樹(shù)形結(jié)構(gòu)中樹(shù)根結(jié)點(diǎn)沒(méi)有 前驅(qū) 結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)葉子結(jié)點(diǎn)沒(méi)有 續(xù)結(jié)點(diǎn)，其余每個(gè)

10、結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可任意多個(gè)。在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè)。 9數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別順序 、 鏈?zhǔn)?、 索引 和 散列 5一個(gè)算法的效率可分為 時(shí)間效率和空間效率。在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 元素，具體移動(dòng)的元素個(gè)數(shù)與 表中的位置 有關(guān)。線性表中結(jié)點(diǎn)的集合是 有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一的。向一個(gè)長(zhǎng)度為ni1in+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i+1 個(gè)元素。向一個(gè)長(zhǎng)度為ni1in)n-i 個(gè)元素。在順序表中訪問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O(1)，因此，順序表也稱(chēng)為 隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu)。順序表中邏輯上相鄰

11、的元素的物理位置 相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 18其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 指示。在n*，其時(shí)間復(fù)雜度為（n。向量棧和隊(duì)列都是 線性結(jié)構(gòu)可以在向量的 任何位置插入和刪除元素對(duì)于棧只能在頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。棧是一種特殊的線性表允許插入和刪除運(yùn)算的一端稱(chēng)為棧頂不允許插入和刪除運(yùn)算的一端稱(chēng)棧底。隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。不包含任何字（長(zhǎng)度為0）的串 稱(chēng)為空串；由一個(gè)或多個(gè)空（僅由空格符組成的串為空白串。子串的定位運(yùn)算稱(chēng)為串的模式匹配； 被匹配的主串稱(chēng)為目標(biāo)串， 子串稱(chēng)為模式。假設(shè)有二維數(shù)組A

12、 ，每個(gè)元素用相鄰的 6A（基68地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為288B；末尾元素A 的第一個(gè)字節(jié)地址為1282；57若按行存儲(chǔ)時(shí)，元素A 的第一個(gè)字節(jié)地址為 (8+4)6+1000=1072；若按列存儲(chǔ)時(shí)，元素A 的第一個(gè)字1447節(jié)地址為 (674)61000）1276。由個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有5 種形態(tài)。一棵深度為6的滿(mǎn)二叉樹(shù)有 n+n=0+ n= n-1=31個(gè)分支結(jié)點(diǎn)和 1220注：滿(mǎn)二叉樹(shù)沒(méi)有度為 1 的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為9。（ log(n) +1= 8.xx +1=92700350 個(gè)葉子結(jié)點(diǎn)。答：最快方法：用

13、葉子數(shù)n/2350=32 個(gè)葉子。設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)則此完全二叉樹(shù)有 500 個(gè)葉子結(jié)點(diǎn)有 499個(gè)度為2的結(jié)點(diǎn)有1個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有 0個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。答：最快方法：用葉子數(shù)n/2500 ，n =n -1=499。 另外，最后一結(jié)點(diǎn)為 2i 屬于左葉子，右葉子是空的，20所以有 1 個(gè)非空左子樹(shù)。完全二叉樹(shù)的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹(shù)數(shù)0.在數(shù)據(jù)的存放無(wú)規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是 順序查找（線性查找） 。線性有序表，aaa )是從小到大排列的，對(duì)一個(gè)給定的值kk123256元素，在查找不成功的情況下，最多需要檢索 8次。設(shè)有100

14、個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是7。假設(shè)在有序線性表a20上進(jìn)行折半查找則比較一次查找成功的結(jié)點(diǎn)數(shù)為比較兩次查找成功的結(jié)點(diǎn)為 2；比較四次查找成功的結(jié)點(diǎn)數(shù)為 8；平均查找長(zhǎng)度為3.7 。解：顯然，平均查找長(zhǎng)度O（logtop0ST-top=0ST-topm0ST-top=m0（ C ）18. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。A1/2B. 1C. 2D. （ B ）19. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍B. 1C. 2D. 4（B）20.有 8 個(gè)結(jié)點(diǎn)的無(wú)向圖最多有條邊。B. 28C.56D.112（C）21.有 8 個(gè)結(jié)點(diǎn)的有向完全圖有條邊。

15、B. 28C.56D.112n（ B ）22在表長(zhǎng)為的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度. ;. （）;n. ;. （）（ A ）2折半查找有序表4，1，1，2，30507088100。若查找表中元素5，則它將依次與表中比較大小，查找結(jié)果是失敗。A20，70，30，50B30，88，70，50C20，50（ C ）24對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。A36（ A ）25. 鏈表適用于查找A順序二分法C順序，也能二分法隨機(jī)數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、選擇題。在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為CA動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C線性結(jié)構(gòu)和非線性結(jié)構(gòu)

16、D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 2數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指 A。A數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu)D數(shù)據(jù)元素之間的關(guān)3在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)。A邏輯B存儲(chǔ)邏輯和存儲(chǔ)物 理 4在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)CA數(shù)據(jù)的處理方法數(shù)據(jù)元素的類(lèi)型C數(shù)據(jù)元素之間的關(guān)系數(shù)據(jù)的存儲(chǔ)方法 5在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮AA各結(jié)點(diǎn)的值如何結(jié)點(diǎn)個(gè)數(shù)的多少C對(duì)數(shù)據(jù)有哪些運(yùn)算所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便6以下說(shuō)法正確的是 D。A數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位 B數(shù)據(jù)元素是數(shù)據(jù)的最小單位 C數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合 D算法分析的目的是 C，算法分析的兩

17、個(gè)主要方面是 A。（1）A找出數(shù)據(jù)結(jié)構(gòu)的合理性研究算法中的輸入和輸出的關(guān)C分析算法的效率以求改進(jìn)C分析算法的易讀性和文檔性（2）A空間復(fù)雜度和時(shí)間復(fù)雜度正確性和簡(jiǎn)明性 C可讀性和文檔性數(shù)據(jù)復(fù)雜性和程序復(fù)雜下面程序段的時(shí)間復(fù)雜度是 O(n2)s =0;for( I =0; in; i+) for(j=0;jn;j+) s +=Bij;sum = s ;下面程序段的時(shí)間復(fù)雜度是 O(n*m)for( i =0; in; i+)for(j=0;jm;j+) Aij 0;下面程序段的時(shí)間復(fù)雜度是 O(logn)。3i 0；while（inext =NULL Chead-next =headD head

18、!=NULL帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件是BAhead = NULLB head-next =NULL Chead-next =headD head!=NULL若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采D存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。單鏈表給出表頭指針的單循環(huán)鏈表雙鏈表D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是BA單鏈表靜態(tài)鏈表C線性鏈表順序存儲(chǔ)結(jié)構(gòu)非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿(mǎn)足 CAp-next = NULL= NULLCp-next =head= head在循環(huán)雙鏈表的p 所指的結(jié)點(diǎn)之前插

19、入s 所指結(jié)點(diǎn)的操作是D。Ap-prior = s；s-next = p；p-prior-next = s；s-prior = p-prior Bp-prior = s；p-prior-next = = p；s-prior = p-prior Cs-next = p；s-prior = p-prior；p-prior = s；p-prior-next = Ds-next = p；s-prior = p-prior；p-prior-next = s；p-prior = s如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用 D 存儲(chǔ)方式最節(jié)省時(shí)間A單鏈表雙鏈表單循環(huán)鏈表D順序表在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序

20、單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是 B AO（1）DO（nlog2n）在一個(gè)長(zhǎng)度為的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行B 操作與鏈表的長(zhǎng)度有關(guān)A刪除單鏈表中的第一個(gè)元素刪除單鏈表中的最后一個(gè)元素 C在單鏈表第一個(gè)元素前插入一個(gè)新元素D與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是 D 。A插入、刪除操作更簡(jiǎn)單 B可以進(jìn)行隨機(jī)訪問(wèn) C可以省略表頭指針或表尾指針 D順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活如果對(duì)線性表的操作只有兩種即刪除第一個(gè)元素在最后一個(gè)元素的后面插入新元素則最好使用BA只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表B只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表C非循環(huán)雙鏈表D循環(huán)雙鏈表在長(zhǎng)度為n的順序表的第i個(gè)

21、位置上插入一個(gè)元素1 in+1，元素的移動(dòng)次數(shù)為：A。An i + 1 i 1對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為CA順序表 用頭指針表示的循環(huán)單鏈表C用尾指針表示的循環(huán)單鏈表單鏈表下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？C。A插入運(yùn)算方便B 可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表C存儲(chǔ)密度大D刪除運(yùn)算方便下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？BA線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B 線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。CD線性表是具有n個(gè)B的有限序列。A字符B數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)表元素在n 個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O（1）的操作是AA訪問(wèn)第i

22、（1=i=n）個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)B在第i（1=i=n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C刪除第i（1=inext=s；s-next=p-next s-next=p-next ；p-next=s; Cp-next=s；p-next=s-next Dp-next=s-next；p-next=s36線性表的順序存儲(chǔ)結(jié)構(gòu)是一種A。A隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B順序存取的存儲(chǔ)結(jié)構(gòu)C索引存取的存儲(chǔ)結(jié)構(gòu)DHash 存取的存儲(chǔ)結(jié)構(gòu)棧的特點(diǎn)是B，隊(duì)列的特點(diǎn)是 AA先進(jìn)先出先進(jìn)后出棧和隊(duì)列的共同點(diǎn)是 C。A都是先進(jìn)后出都是先進(jìn)先C只允許在端點(diǎn)處插入和刪除元素沒(méi)有共同點(diǎn)一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的

23、輸出序列是CAedcbaBdecbaCdceabDabcde設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳B、D、。下列C是不可能的出棧序列AA,B,C,D,EBB,C,D,E,ACE,A,B,C,DDE,D,C,B,A以下B不是隊(duì)列的基本運(yùn)算？ A從隊(duì)尾插入一個(gè)新元素從隊(duì)列中刪除第i個(gè)元C判斷一個(gè)隊(duì)列是否為空讀取隊(duì)頭元素的值若已知一個(gè)棧的進(jìn)棧序列是3其輸出序列為ppppn若pn則pi為C。AiBniD不確定判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是 BAst-top != -1= -1Cst-top != MaxSizest-top = MaxSize判定一個(gè)順序棧st（最多元素為Max

24、Size）為滿(mǎn)的條件是 DAst-top != -1= -1Cst-top != MaxSize= MaxSize一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是 BA4，3，2，1C1，4，3，2判定一個(gè)循環(huán)隊(duì)列最多元素為MaxSize）為空的條件是 C。Aqu-rear qu-front =MaxSize qu-front -1=MaxSize Cqu-rear =qu-frontqu-rear =qu-front -1在循環(huán)隊(duì)列中，若 front 與 rear 分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件C。Afront=rear+1Brear=front+1Cfron

25、t=rearDfront=0向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 D 操作Ah-next=s ;Bs-next=h ;Cs-next=h ;h =s ;Ds-next=h-next ;h-next=s ;輸入序列為ABC，可以變?yōu)镃BA 時(shí)，經(jīng)過(guò)的棧操作為B。Apush，pop，push，pop，push，popBpush，push，push，pop， pop， Cpush，push，pop， pop，push，popDpush，pop，push，push，pop， 若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1 top2分別代表第1和第2個(gè)棧的棧頂棧1的底在V1，

26、棧2的底在Vm，則棧滿(mǎn)的條件是B 。A|top2-top1|=0 top1+1=top2Ctop1+top2=mDtop1=top2設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用 D數(shù)據(jù)結(jié)構(gòu)最佳A線性表的順序存儲(chǔ)結(jié)構(gòu)B隊(duì)列C線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧允許對(duì)隊(duì)列進(jìn)行的操作有 D。 A對(duì)隊(duì)列中的元素排序取出最近進(jìn)隊(duì)的元C在隊(duì)頭元素之前插入元素D刪除隊(duì)頭元素對(duì)于循環(huán)隊(duì)列D。無(wú)法判斷隊(duì)列是否為空B無(wú)法判斷隊(duì)列是否為C隊(duì)列不可能滿(mǎn)以上說(shuō)法都不對(duì)若用一個(gè)大小為6的數(shù)值來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一元素，再加入兩個(gè)元素后和front的值分別為B 。A1和5和

27、4和2和1隊(duì)列的“先進(jìn)先出”特性是指D。 A最早插入隊(duì)列中的元素總是最后被刪除 B當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)C每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作 D每次從隊(duì)列中刪除的總是最早插入的元素和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是 A。 A通常不會(huì)出現(xiàn)棧滿(mǎn)的情況B 通常不會(huì)出現(xiàn)?？盏那镃插入操作更容易實(shí)現(xiàn)刪除操作更容易實(shí)現(xiàn)用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作C。僅修改隊(duì)頭指針僅修改隊(duì)尾指針 C隊(duì)頭、隊(duì)尾指針都可能要修改隊(duì)頭、隊(duì)尾指針都要修若串Ssoftwar，其子串的數(shù)目是B A8B37串的長(zhǎng)度是指 B。串中所含不同字母的個(gè)數(shù)

28、串中所含字符的個(gè)數(shù) C串中所含不同字符的個(gè)數(shù)串中所含非空格字符的個(gè)串是一種特殊的線性表，其特殊性體現(xiàn)在 BA可以順序存儲(chǔ)數(shù)據(jù)元素是一個(gè)字符 C可以鏈?zhǔn)酱鎯?chǔ)數(shù)據(jù)元素可以是多個(gè)字符設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為 BA連接 模式匹配C求子串D求串長(zhǎng)數(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ù)組按行存放，元素A85的起始地址為C 。ASA141 SA144CSA222DSA225數(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ù)組按行存放，元素A58的

29、起始地址為C。ASA141 SA180CSA222DSA225froat average=new float30;假設(shè)該數(shù)組的內(nèi)存起始位置為200， average15的內(nèi)存地址是 CA214設(shè)二維數(shù)組A1 m,1 n按行存儲(chǔ)在數(shù)組B中則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為AAn*(i-1)+j n*(i-1)+j-1Ci*(j-1)Dj*m+i-110090010，設(shè)每個(gè)整型數(shù)占2的字節(jié)數(shù)是B。A20B 66C18 000D3367數(shù)組A0 4，-1 -3，57中含有的元素個(gè)數(shù)是A。A55 45C36D16對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了D。A方便運(yùn)算 B 方便存儲(chǔ)C提高運(yùn)算速度減少存儲(chǔ)空間設(shè)

30、有一個(gè)10 階的對(duì)稱(chēng)矩陣A1，1，1每個(gè)元素占 1 個(gè)地址空間，則a 的地址為 B 。8，5A13 B 33C18稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即 CA二維數(shù)組和三維數(shù)組 三元組和散列C三元組和十字鏈表 散列和十字鏈表樹(shù)最適合用來(lái)表示C 。A有序數(shù)據(jù)元素?zé)o序數(shù)據(jù)元素 C元素之間具有分支層次關(guān)系的數(shù)據(jù)元素之間無(wú)聯(lián)系的數(shù)深度為5的二叉樹(shù)至多有C個(gè)結(jié)點(diǎn)A16 32 3110對(duì)一個(gè)滿(mǎn)二叉樹(shù)個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h，則 D。An = h+mB h+m = 2nC m = h-1D n = 任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序AA不發(fā)生改變發(fā)生改變不能確定D以上都不對(duì)在線索

31、化樹(shù)中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右鏈指向的是樹(shù)結(jié)構(gòu)信息，還是線索化信息若0標(biāo)識(shí)樹(shù)結(jié)構(gòu)信息標(biāo)識(shí)線索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)D。A00在下述論述中，正確的是D。只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為 0；二叉樹(shù)的度為 2；二叉樹(shù)的左右子樹(shù)可任意交換；深度為K 的順序二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿(mǎn)二叉樹(shù)ABCDF 對(duì)應(yīng)的二叉樹(shù)為Bmp，pnF的結(jié)點(diǎn)的個(gè)數(shù)是A。Am-nBm-n-1Cn+1D不能確定10210B 。A9B11具有10個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有B個(gè)度為2的結(jié)點(diǎn)A8C10在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 C倍A1/2B 1C 2D 4在一個(gè)有向圖中，所有頂點(diǎn)的入

32、度之和等于所有頂點(diǎn)的出度之和的 B 倍A1/2B 1C 2D 4某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：CA383已知一算術(shù)表達(dá)式的中綴形式為AB *CD/E，后綴形式為ABC*+DE/，其前綴形式為D。AA+B*C/DEBA+B*CD/EC +*ABC/DED+A*BC/DEabecdf已知一個(gè)圖，如圖所示，若從頂點(diǎn)abecdf到的一種頂點(diǎn)序列D；按廣度搜索法進(jìn)行遍歷，則可能得到的一種點(diǎn)序列A；Aa，b，e，c，d，fCa，e，b，c，f，d，Aa，b，c，e，d，fCa，e，b，c，f，d，采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)A

33、A先序遍歷中序遍歷后序遍歷按層遍歷采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)DA先序遍歷中序遍歷后序遍歷按層遍歷具有n 個(gè)結(jié)點(diǎn)的連通圖至少有A條邊。A n-1 n n(n-1)/2 2n88廣義表（，）的表頭是C，表尾是C 。AaB （）C （a）D （ a）廣義表（）的表頭是C ，表尾是B 。AaB （）C （a）D （a）順序查找法適合于存儲(chǔ)結(jié)構(gòu)為B 的線性表。A 散列存儲(chǔ)B 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C 壓縮存儲(chǔ)D 索引存儲(chǔ)對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 B。A以順序方式存儲(chǔ)B以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯?chǔ)D以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列采用折半查找

34、法查找長(zhǎng)度為n 的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為DA O(n2)B O(nlogn)C O(n)D O(logn)2293有一個(gè)有序表為1391344677895100，當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)， C次比較后查找成功。A 11B 5C4D8二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法B。A正確B錯(cuò)誤下面關(guān)于B 樹(shù)和B+樹(shù)的敘述中，不正確的結(jié)論是A。A B 樹(shù)和 B+樹(shù)都能有效的支持順序查找BB 樹(shù)和B+樹(shù)都能有效的支持隨機(jī)查找C B 樹(shù)和 B+樹(shù)都是平衡的多叉樹(shù)DB 樹(shù)和B+樹(shù)都可用于文件索引結(jié)構(gòu)以下說(shuō)法錯(cuò)誤的是B。 A散列法存儲(chǔ)的思想是

35、由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址 B散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。 C負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿(mǎn)程度。 D散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法查找效率最高的二叉排序樹(shù)是 C。A所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)B所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)C平衡二叉樹(shù)。 D沒(méi)有左子樹(shù)的二叉排序樹(shù)。排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正位置上的方法，稱(chēng)為C。A希爾排序。冒泡排序C插入排序。選擇排序在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是 DA希爾排序冒泡排

36、序直接插入排序D直接選擇排序堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個(gè)堆A94,31,53,23,16,72B94,53,31,72,16,23C16,53,23,94,31,72D16,31,23,94,53,72堆排序是一種B排序。A插入選擇交換歸并D在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高A順序查找B折半查找分塊查找插入直接選擇排序的時(shí)間復(fù)雜度為D（n 為元素個(gè)數(shù)AO（n)BO(logn)CO(nlogn) O(n2)22二、填空題。數(shù)據(jù)邏輯結(jié)構(gòu)包括 線性結(jié)構(gòu)、 樹(shù)形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 三種類(lèi)型樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱(chēng) 非性結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、 樹(shù)形結(jié)構(gòu) 和 圖狀

37、結(jié)構(gòu) 4種。1 個(gè)前驅(qū)結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)后續(xù)結(jié)點(diǎn)。1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以 任意多個(gè) 。數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是順序 、 鏈?zhǔn)?、索引和散列 存儲(chǔ) 。評(píng)估一個(gè)算法的優(yōu)劣，通常從 時(shí)間復(fù)雜度和 空間復(fù)雜度兩個(gè)方面考察。5在一個(gè)長(zhǎng)度為nin-i-1 個(gè)元素。在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的 前驅(qū) 結(jié)點(diǎn)。n當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元素是應(yīng)采用 順序存儲(chǔ)結(jié)構(gòu)。根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成單鏈表雙鏈表 。順序存儲(chǔ)結(jié)構(gòu)是通過(guò)

38、下標(biāo)表示元素之間的關(guān)系的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò) 指針 表示元素之間的關(guān)系的。帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是 L-next-next=L。棧 是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算遵循 后進(jìn)先出 的原則。的空格個(gè)數(shù)。一個(gè)字符串中 任意個(gè)連續(xù)字符構(gòu)成的部分 稱(chēng)為該串的子串。22子串 ”str” 在主串 ”datastructure” 中的位置是523二維數(shù)組M6i08，列下標(biāo)j110，放 M 至少需要 540 個(gè)字節(jié)； 的第 8 列和第 5 行共占 108 個(gè)字節(jié)。 24稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即 三元組表 和 十字鏈表 。25廣義表（bc（d）的長(zhǎng)度是3，深度是 4 。在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n02 的結(jié)點(diǎn)的個(gè)數(shù)為，則有n2+1 。在有n 個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)n+1。一棵有n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共2n-1_個(gè)結(jié)點(diǎn)。深度為5的二叉樹(shù)至多有 31個(gè)結(jié)點(diǎn)。若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為6931某二叉樹(shù)的前序遍歷序列是abdgcefh，中序序列是dgb