吉大《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)二答卷

1、吉大18春學(xué)期數(shù)據(jù)結(jié)構(gòu)在線作業(yè)二-0005試卷總分:100 得分:100一、單選題 (共 10 道試題,共 40 分)1.在單鏈表中，刪除p所指結(jié)點(diǎn)的直接后繼的操作是( )A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p-next=p-next;D.p=p-next-next;答案:A2.深度為6的二叉樹最多有( )個(gè)結(jié)點(diǎn)。A.64B.63C.32D.31答案:B3.帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是()。A.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL答案:B4.P

2、USH和POP命令常用于（ ）操作A.隊(duì)列B.數(shù)組C.棧D.記錄答案:C5.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由指針p所指)滿足( )。A.p-next=NULLB.p=NULLC.p-next=headD.p=head答案:C6.設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則這類二叉樹上所含結(jié)點(diǎn)總數(shù)最少( )個(gè)。A.k+1B.2kC.2k-1D.2k+1答案:C7.在 一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前趨，若在p,q之間插入s結(jié)點(diǎn)，這執(zhí)行（ ）操作。A.s-next=p-next;p-next=sB.q-next=s;s-next=pC.p-next=s-next;s-nex

3、t=p;D.p-next=s;s-next=q;答案:B8.在數(shù)據(jù)結(jié)構(gòu)中，邏輯上數(shù)據(jù)結(jié)構(gòu)可分為：（ ）A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.線性結(jié)構(gòu)和非線性結(jié)構(gòu)C.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)答案:B9.在圖的鄰接表存儲(chǔ)結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類似于二叉樹上的( )。A.先根遍歷B.中根遍歷C.后根遍歷D.按層次遍歷答案:A10.通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ ）A.數(shù)據(jù)元素具有同一特點(diǎn)B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C.每個(gè)數(shù)據(jù)元素都一樣D.數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等答案:B二、多選題 (共 5 道試題,共 2

4、0 分)11.二叉樹的遍歷方式有（）A.先根遍歷B.中根遍歷C.后根遍歷D.深度遍歷答案:ABC12.對(duì)有序表的查找方式有以下幾種（）A.折半查找B.斐波那契查找C.插值查找D.二叉樹查找答案:ABC13.一個(gè)好的算法應(yīng)具備以下性質(zhì)（ ）A.正確性B.可讀性C.穩(wěn)健性D.有窮性答案:ABCD14.對(duì)線性表，可進(jìn)行如下基本操作（ ）A.隨機(jī)存取B.插入C.刪除D.查找答案:ABCD15.類string中包含的串運(yùn)算有（ ）A.Find()B.Substr()C.Insert()D.Length()答案:ABCD三、判斷題 (共 10 道試題,共 40 分)16.設(shè)棧的輸入序列是1,2,3,4，則

5、1,4,3,2不可能是其出棧序列答案:錯(cuò)誤17.具有n（n0）個(gè)頂點(diǎn)的無(wú)向圖最多含有n(n-1)/2條邊答案:正確18.單鏈表中的頭結(jié)點(diǎn)就是單鏈表的第一個(gè)結(jié)點(diǎn)。( )答案:錯(cuò)誤19.字符串是一種線性表，其特殊性表現(xiàn)在它的數(shù)據(jù)元素是一個(gè)字符答案:正確20.對(duì)于前序遍歷和中序遍歷結(jié)果相同的二叉樹為所有結(jié)點(diǎn)只有右孩子的二叉樹答案:正確21.若需在O(nlog2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是歸并排序答案:正確22.快速排序的速度在所有排序方法中為最快，而且所需附加空間也最少答案:錯(cuò)誤23.判斷一個(gè)表達(dá)式中左右括號(hào)是否匹配，采用棧實(shí)現(xiàn)較為方便答案:正確24.在最好和最壞情況下的時(shí)