2021年數(shù)據(jù)結(jié)構(gòu)考試題庫

緒論一、填空題1.數(shù)據(jù)邏輯構(gòu)造被分為集合、(線性構(gòu)造)、(樹形構(gòu)造)和(圖狀構(gòu)造)四種。2.物理構(gòu)造是數(shù)據(jù)構(gòu)造在計(jì)算機(jī)中表達(dá)，又稱為(存儲(chǔ)構(gòu)造)。3.數(shù)據(jù)元素邏輯構(gòu)造涉及( 線性)、(樹)和圖狀構(gòu)造3種類型，樹形構(gòu)造和圖狀構(gòu)造合稱為(非線性構(gòu)造)。4.(數(shù)據(jù)元素)是數(shù)據(jù)基本單位，(數(shù)據(jù)項(xiàng))是數(shù)據(jù)不可分割最小單位。線性構(gòu)造中元素之間存在(一種對(duì)一種)關(guān)系，樹形構(gòu)造中元素之間存在(一種對(duì)各種)關(guān)系，圖狀構(gòu)造中元素之間存在(各種對(duì)各種)關(guān)系。？6.數(shù)據(jù)構(gòu)造是一門研究非數(shù)值計(jì)算程序設(shè)計(jì)問題中：計(jì)算機(jī)(數(shù)據(jù)元素)以及它們之間(關(guān)系)和(運(yùn)籌)等學(xué)科。7.算法五個(gè)重要特性為有窮性、擬定性、(輸入)、(輸出)和(可行性)。二、選取題1.數(shù)據(jù)不可分割基本單位是(D)。A.元素 B.結(jié)點(diǎn) C.數(shù)據(jù)類型 D.數(shù)據(jù)項(xiàng)*2.線性表邏輯順序與存儲(chǔ)順序總是一致，這種說法(B)。A.對(duì)的 B.不對(duì)的 C.不擬定 D.無法選取3.線性構(gòu)造是指數(shù)據(jù)元素之間存在一種(D)。A.一對(duì)多關(guān)系 B.多對(duì)多關(guān)系 C.多對(duì)一關(guān)系 D.一對(duì)一關(guān)系4.在數(shù)據(jù)構(gòu)造中，從邏輯上可以把數(shù)據(jù)構(gòu)造提成(A)。A.動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造 B.緊湊構(gòu)造和非緊湊構(gòu)造C.線性構(gòu)造和非線性構(gòu)造 D.內(nèi)部構(gòu)造和外部構(gòu)造5.線性表若采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)，規(guī)定內(nèi)存中可用存儲(chǔ)單元地址(D)。A.必要是持續(xù) B.某些地址必要是持續(xù)C.一定是不持續(xù) D.持續(xù)不持續(xù)都可以三、簡答題1.算法特性是什么。答：有窮性擬定性可行性有0或各種輸入有1或各種輸出線性構(gòu)造一、填空題1.在一種長度為n線性表中刪除第i個(gè)元素（1≤i≤n）時(shí)，需向前移動(dòng)(n-i)個(gè)元素。2.從循環(huán)隊(duì)列中刪除一種元素時(shí)，其操作是(先移動(dòng)隊(duì)首指針，后取出元素)。3.在線性表單鏈接存儲(chǔ)中，若一種元素所在結(jié)點(diǎn)地址為p，則其后繼結(jié)點(diǎn)地址為(p->next)。4.在一種單鏈表中指針p所指向結(jié)點(diǎn)背面插入一種指針q所指向結(jié)點(diǎn)時(shí)，一方面把(p->next)值賦給q->next，然后(q->date)值賦給p->next。5.從一種棧刪除元素時(shí)，一方面取出(棧頂元素)，然后再使(棧頂指針)減1。6.子串定位操作普通稱做串(模式匹配)。7.設(shè)目的T=‘a(chǎn)bccdcdccbaa’，模式P=‘cdcc’則第(六)次匹配成功。。8.順序棧S中，出棧操作時(shí)要執(zhí)行語句序列中有S->top(--)；進(jìn)棧操作時(shí)要執(zhí)行語句序列中有S->top(++)。9.順序表中邏輯上相鄰元素物理位置(一定)緊鄰；單鏈表中邏輯上相鄰元素物理位置(不一定)緊鄰。10.在(循環(huán))鏈表中，從任何一結(jié)點(diǎn)出發(fā)都能訪問到表中所有結(jié)點(diǎn)。11.棧和隊(duì)列均是(運(yùn)算受限)線性表，棧特點(diǎn)是(先進(jìn)后出后進(jìn)先出)；隊(duì)列特點(diǎn)是(先進(jìn)先出后進(jìn)后出)。12.普通，在程序中使用串可分為串常量和串變量；而串按存儲(chǔ)方式又可分為(定長順序存儲(chǔ))和(堆分派存儲(chǔ))。13.循環(huán)隊(duì)列頭指針front指向隊(duì)頭元素，隊(duì)尾指針rear指向隊(duì)尾元素后一種空閑元素，隊(duì)列最大空間為Queuelen。在循環(huán)隊(duì)列中，隊(duì)空標(biāo)志為(front==rear)，隊(duì)滿標(biāo)志為(（rear+1）%max==front)。當(dāng)rear>=front時(shí)，隊(duì)列長度為(rear-front)，當(dāng)rear<front時(shí)，隊(duì)列長度為(rear-front+max)。14.在一種長度為n線性表中第i個(gè)元素（1≤i≤n）之前插入一種元素時(shí)，需向后移動(dòng)(n-i+1)個(gè)元素。15.在具備n個(gè)單元循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有(n-1)個(gè)元素。16.帶有一種頭結(jié)點(diǎn)單鏈表Head為空條件是(Head->next==null)。17.在一種單鏈表中刪除指針p所指向結(jié)點(diǎn)后繼結(jié)點(diǎn)時(shí)，需要把(p->next->next)值賦給p->next指針域。18.一種順序循環(huán)隊(duì)列存于a[M]中，假定隊(duì)首和隊(duì)尾指針分別為front和rear，則判斷隊(duì)空條件為(a.front==a.rear)，判斷隊(duì)滿條件為(（a.rear+1）%M==a.front)。19.在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一種指向其(前驅(qū))結(jié)點(diǎn)，另一種指向其(后繼)結(jié)點(diǎn)，最后一種結(jié)點(diǎn)(后繼結(jié)點(diǎn))指針域?yàn)榭铡?20.若D=((a，(b，c))，e，a)，則Head(D)=( )，Tail(D)=( )，Head(Tail(D))=( )。（本人不會(huì)）21.在循環(huán)鏈表中，每個(gè)結(jié)點(diǎn)有(一種)個(gè)指針域，指向其(后繼)結(jié)點(diǎn)，最后一種結(jié)點(diǎn)指針域(為空)。*22.若S=(a，(b，c)，e，d)，則Head(S)=( )，Tail(S )=( )，Head(Tail(S ))=( )。（本人不會(huì)）二、選取題1.在一種單鏈表中，若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)，若在q與p之間插入一種s所指結(jié)點(diǎn)，則執(zhí)行(A)。s->link=p->link；p->link=s；B.p->link=s；s->link=q;C.p->link=s->link；s->link=p；D.q->link=s；s->link=p；2.對(duì)于順序存儲(chǔ)隊(duì)列，存儲(chǔ)空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一種環(huán)，則隊(duì)列中元素個(gè)數(shù)(A)。A.R-F B.n+R-F C.(R-F+1)modn D.(n+R-F)mod n3.如下陳述中對(duì)的是(A)。A.串是一種特殊線性表 B.串長度必要不不大于零C.串中元素只能是字母 D.空串就是空白串4.若讓元素1，2，3依次進(jìn)棧，則出棧順序不也許浮現(xiàn)(C)狀況。A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，2鑒定一種隊(duì)列QU（最多元素為m0）為空條件是(C)。A.QU->rear-QU->front==m0 B.QU->rear-QU->front-1==m0C.QU->front==QU->rear D.QU->front==QU->rear+16.設(shè)目的串S=‘a(chǎn)bcdef’，模式串p=‘de’，則第(C)次匹配成功。A.1 B.2 C.4 D.57.設(shè)字符串s1=‘ABCDEFG’，S2=‘PQRST’，T，sub1，sub2為空串。則運(yùn)算s=Concat(T，SubString(sub1，s1，2，SubLength(s2))，SubString(sub2，s1，SubLength(s2)，2))后串T值為(D)。A.‘BCDEF’B.‘BCDEFG’C.‘BCPQRST’D.‘BCDEFEF’8.一種順序線性表第一種元素存儲(chǔ)地址是100，每個(gè)元素長度為2，則第5個(gè)元素地址是(B)。A.100 B.108 C.110 D.1209.非空循環(huán)單鏈表head尾結(jié)點(diǎn)（由p所指向）滿足(C)。A.p->next==NULL B.p==NULLC.p->next==head D.p==head10.在一種鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則刪除一種結(jié)點(diǎn)運(yùn)算時(shí)(C)。A.r=f->next; B.r=r->next;C.f=f->next; D.f=r->next；11.在一種長度為n線性表中，刪除值為x元素時(shí)，需要比較元素和移動(dòng)元素總次數(shù)為(C)。A.(n+1)/2 B.n/2 C.n D.n+112.在一種單鏈表中，若要在p所指向結(jié)點(diǎn)之后插入一種新結(jié)點(diǎn)，則需要相繼修改(B)個(gè)指針域值。A.1 B.2 C.3 D.413.線性構(gòu)造中，每個(gè)結(jié)點(diǎn)(C)。A.無直接前驅(qū) B.只有一種直接前驅(qū)和個(gè)數(shù)不受限制直接后繼C.只有一種直接前驅(qū)和后繼 D.有個(gè)數(shù)不受限制直接前驅(qū)和后繼14.隊(duì)列是限定在(D)進(jìn)行操作線性表。A.中間 B.隊(duì)頭 C.隊(duì)尾 D.端點(diǎn)15.設(shè)串S1=“ABCDEFG”，S2=“PQRST”，函數(shù)StrCat(x,y)返回x和y串連接串，函數(shù)StrSub(S，i，j)返回串S從序號(hào)i字符開始j個(gè)字符構(gòu)成子串，StrLen(S)返回串S長度，則StrCat(StrSub(S1，2，StrLen(S2))，StrSub(S1，StrLen(S2)，2))成果串是(D)。A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF16.學(xué)生成績表是一種(C)構(gòu)造。A.圖形 B.樹形 C.線性 D.集合17.在一種鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)運(yùn)算時(shí)(C)。A.f->next=s; f=s; B.r->next=s; r=s；C.s->next=r; r=s; D.s->next=f; f=s;18.向順序表中i位置處插入元素，下面哪項(xiàng)可以精確表白i位置是合法。(D)A.i<=1||i>l->length+1 B.i>=1C.i>=l->length+1 D.1<=i<=l->length+119.設(shè)線性鏈表中結(jié)點(diǎn)構(gòu)造為（data，next），已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)直接后繼，若在*q和*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行(A)操作。A.s->next=p->next; p->next=s；B.q->next=s; s->next=p;C.p->next=s->next; s->next=p；D.p->next==s; s->next=q;20.一種棧入棧序列為a，b，c，d，e，則出棧序列不也許是(C)。A.edcba B.dcbae C.dceab D.abcde21.如果以鏈表作為棧存儲(chǔ)構(gòu)造，則出棧操作時(shí)(B)。A.必要鑒別棧與否滿 B.必要鑒別棧與否為空C.必要鑒別棧元素類型 D.可不做任何判斷22.設(shè)有兩個(gè)串p和q，求q在p中初次浮現(xiàn)位置運(yùn)算稱為(B)。A.連接 B.模式匹配 C.求子串 D.求串長23.p指向線性鏈表中某一結(jié)點(diǎn)，則在線性鏈表表尾插入結(jié)點(diǎn)S語句序列是(A)。A.while(p->next!=NULL)p=p->next；p->next=s；s->next=NULL;B.while(p!=NULL)p=p->next；p->next=s；s->next=NULL;C.while(p->next!=NULL)p=p->next；s->next=p;p->next=NULL;D.while(p!=NULL)p=p->next->next;->next;p->next=s;s->next=p24.向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)(A)。A.先移動(dòng)棧頂指針，再存入元素B.先存入元素，再移動(dòng)棧頂指針C.先后順序無關(guān)緊要D.同步進(jìn)行25.假定一種順序隊(duì)列隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空條件為(D)。f+1==r B.r+1==f C.f==0 D.f==r26.棧插入和刪除操作在(A)進(jìn)行。A.棧頂 B.棧底 C.任意位置 D.指定位置27.棧和隊(duì)列共同點(diǎn)是(C)。A.都是先進(jìn)后出 B.都是先進(jìn)先出C.只容許在端點(diǎn)處插入和刪除元素 D.沒有共同點(diǎn)28.若6行8列數(shù)組以列序?yàn)橹餍蝽樞虼鎯?chǔ)，基地址為1000，每個(gè)元素占2個(gè)存儲(chǔ)單元，則第5行第3列元素(假定無第0行第0列)地址是(B)。A.1086 B.1032 C.1068 D.答案A，B，C都不對(duì)29.設(shè)有50行二維數(shù)組A[50][60]，其元素長度為2字節(jié)，按行優(yōu)先順序存儲(chǔ)，基地址為100，則元素A[18][25]存儲(chǔ)地址為(D)。A.1850 B.2188 C.1950 D.2310三、闡述題1.寫出線性表插入算法、刪除算法。解：太麻煩略略略*2.畫出主串為‘a(chǎn)babcabcacbab’，子串為‘a(chǎn)bc’模式匹配過程。解：四、算法設(shè)計(jì)題1.在帶頭結(jié)點(diǎn)單鏈線性表L中第i個(gè)位置之前插入新元素e。略2.在帶頭結(jié)點(diǎn)單鏈線性表L中，刪除第i個(gè)元素，并由e返回其值。略樹形構(gòu)造一、填空題1.赫夫曼樹，又稱最優(yōu)樹，是一類(帶權(quán)途徑)長度最短樹。2.在一棵二叉樹中，第5層上結(jié)點(diǎn)數(shù)最多為(16)個(gè)。3.一棵高度為5二叉樹中至少具有(5)個(gè)結(jié)點(diǎn)，最多含有(31)個(gè)結(jié)點(diǎn)。4.若一棵二叉樹中有8個(gè)度為2結(jié)點(diǎn)，則它有(9)個(gè)葉子。5.一棵深度為6滿二叉樹有(31)個(gè)非終端結(jié)點(diǎn)。6.樹中結(jié)點(diǎn)A(子樹數(shù))稱為結(jié)點(diǎn)A度。7.對(duì)一棵二叉排序樹進(jìn)行中序遍歷時(shí)，得到結(jié)點(diǎn)序列是一種(升序序列)。8.在樹型構(gòu)造中，根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)有且僅有(一)個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)(沒有)后繼結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)都可以有(一或各種)個(gè)后繼結(jié)點(diǎn)。在最優(yōu)二叉樹中沒有度為1結(jié)點(diǎn)，則一棵有n個(gè)葉子結(jié)點(diǎn)最優(yōu)二叉樹中共有(2n-1)個(gè)結(jié)點(diǎn)。10.深度為4（設(shè)根層數(shù)為1）二叉樹至少有(4)個(gè)結(jié)點(diǎn)，至多有(15)個(gè)結(jié)點(diǎn)，第i層上至多有(2n-1)個(gè)結(jié)點(diǎn)。11.深度為6（設(shè)根層數(shù)為1）二叉樹至少有(6)個(gè)結(jié)點(diǎn)，至多有(63)個(gè)結(jié)點(diǎn)，第4層上至多有(8)個(gè)結(jié)點(diǎn)。A.nB.N+1C.n-1D.不擬定注：1:B2:D3:A4:B5.下面(A)是對(duì)。A.哈夫曼樹中結(jié)點(diǎn)度只也許是0和2。B.二叉樹順序存儲(chǔ)中，是以先序遍歷存儲(chǔ)結(jié)點(diǎn)。C.完全二叉樹事實(shí)上就是滿二叉樹。D.一棵二叉樹第i層最大結(jié)點(diǎn)數(shù)為2i-1。6.將含100個(gè)結(jié)點(diǎn)完全二叉樹從根這一層開始，每層上從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)編號(hào)為1。編號(hào)為49結(jié)點(diǎn)X右孩子編號(hào)為(B)。A.98 B.99 C.24 D.無法擬定7.先序?yàn)锳，B，C且后序?yàn)镃，B，A二叉樹共有(B)種。A.3 B.4 C.5 D.68.在一棵度為3樹中，度為3結(jié)點(diǎn)個(gè)數(shù)為2，度為2結(jié)點(diǎn)個(gè)數(shù)為1，則度為0結(jié)點(diǎn)個(gè)數(shù)為(C)。A.4 B.5 C.6 D.79.由權(quán)值分別為11，8，6，2，5葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它帶權(quán)途徑長度為(B)。A.24 B.71 C.48 D.5310.一種具備767個(gè)結(jié)點(diǎn)完全二叉樹，其葉子結(jié)點(diǎn)個(gè)數(shù)為(B)。A.382 B.384 C.385 D.38611.在一棵具備35個(gè)結(jié)點(diǎn)完全二叉樹中，該樹深度為(A)。A.6 B.7 C.5 D.812.由三個(gè)結(jié)點(diǎn)構(gòu)成二叉樹，共有(B)種不同構(gòu)造。A.3 B.4 C.5 D.613.深度為k二叉樹至多有(2K-1)個(gè)結(jié)點(diǎn)(k≥1)。A.2k B.2k-1 C.2k-1 D.2k三、簡答題1.已知一棵二叉樹先序遍歷和中序遍歷，則該二叉樹后序遍歷是什么？先序遍歷：A，B，C，D，E，F(xiàn)，G，H，I，J中序遍歷：C，B，A，E，F(xiàn)，D，I，H，J，G解：后序遍歷：C,B,F,E,I,J,H,G,D,A2.如下圖森林轉(zhuǎn)化為二叉樹。解：此題沒法寫略略略3.已知某二叉樹前序序列為EBADCFHGI，中序序列為ABCDEFGHI，請(qǐng)給出二叉樹且寫出二叉樹后序序列。解：二叉樹略后序序列:A,C,D,B,G,I,H,F,E試用權(quán)集合{6，4，8，3，7，5，10，8，2，1，11}，構(gòu)造哈夫曼(Huffman)樹。(1)畫出這棵哈夫曼樹；(2)分別計(jì)算該哈夫曼樹途徑長度和帶權(quán)途徑長度。解：(1)略(2)途徑長度為：1x2+2x4+3x8+4x3+5x2=60;帶權(quán)途徑長度為：3x(6+7+8+8+10+11)+4x(3+4+5)+5x(1+2)=2135.試按表(10，18，9，2，20，5，6，15，19，25)中元素排列順序，將所有元素插入一棵初始為空二叉排序樹中，使之仍是一棵二叉排序樹。(1)試畫出插入完畢之后二叉排序樹；(2)若查找元素2，它將依次與二叉排序樹中哪些元素比較大小?(3)對(duì)該樹進(jìn)行中序遍歷，試寫出中序遍歷序列。解：(1)略(2)10,9,2(3)2,5,6,9,10,15,18,19,20,256.已知一棵二叉樹順序存儲(chǔ)表達(dá)如下，其中0表達(dá)空，請(qǐng)分別寫出二叉先序、中序、后序遍歷序列。1234567891011121320846515300001018035解：先序序列：20,8,5,15,10,18,46,30,35中序序列：5,8,10,15,18,20,30,35,46后序序列：5,10,18,15,8,35,30,46,207.將如下圖普通樹轉(zhuǎn)化為二叉樹。8.將下圖中二叉樹轉(zhuǎn)換成森林。AAEBCGKFDHLIJ四、闡述題1.由分別帶權(quán)為3，12，9，2，5，7葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，并計(jì)算該樹帶權(quán)途徑長度。解:帶權(quán)途徑長度為:91圖狀構(gòu)造一、填空題1.若一種圖頂點(diǎn)集為{a，b，c，d，e，f}，邊集為{(a，b)，(a，c)，(b，c)，(d，e)},則該圖具有(3)個(gè)連通分量。2.具備10個(gè)頂點(diǎn)無向圖，邊總數(shù)最多為(45)。3.圖廣度優(yōu)先搜索遍歷類似于樹(按層次)遍歷過程。4.在無向圖G鄰接矩陣A中，若A[i][j]等于1，則A[j][i]等于(1)。5.圖(深度)優(yōu)先搜索遍歷算法是一種遞歸算法，圖(廣度)優(yōu)先搜索遍歷算法需要使用隊(duì)列二、選取題1.一種有n個(gè)頂點(diǎn)無向圖最多有(C)條邊。A.n B.n(n-1) C.n(n-1)/2 D.2n2.在一種無向圖中，所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)(B)倍。A.3 B.2 C.1 D.1/23.在一種具備n個(gè)頂點(diǎn)無向圖中，若具備e條邊，則所有頂點(diǎn)度數(shù)之為(D) 。A.n B.e C.n+e D.2e三、簡答題1.給出如下圖所示無向圖G鄰接矩陣存儲(chǔ)構(gòu)造。（答案略）2.畫出下圖鄰接表存儲(chǔ)構(gòu)造。（答案略）3.給出下圖從A點(diǎn)出發(fā)深度優(yōu)先遍歷和廣度優(yōu)先遍歷頂點(diǎn)序列。解：深度優(yōu)先遍歷：AECDB廣度優(yōu)先遍歷：AEBDC5.給出從V1點(diǎn)出發(fā)深度優(yōu)先遍歷和廣度優(yōu)先遍歷頂點(diǎn)序列。解：深度優(yōu)先遍歷;v1v2v3v4v5v6v7v8v9廣度優(yōu)先遍歷;v1v2v3v4v7v5v6v8v9四、闡述題1.寫出下面帶權(quán)有向圖核心途徑。解：(1)1->2->5->8->92.設(shè)將整數(shù)1、2、3、4依次進(jìn)棧，請(qǐng)回答下述問題：1）若入、出棧順序?yàn)镻ush(1)，Pop()，Push(2)，Push(3)，Pop()，Pop()，Push(4)，Pop()，則出棧數(shù)字序列是什么？2）能否得到出棧序列1432和1423？并闡明為什么不能得到或者如何得到？解：(1):1324(2):可以得到1432不能得到1423得到1432過程為：Push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop(),不能得到1423無法執(zhí)行此操作3.求出下圖最小生成樹。（答案略）4.求出下圖最小生成樹。（答案略）查找一、簡答題1.核心字集合{19，01，23，14，55，68，11，82，36}，哈希函數(shù)為：H(key)=key MOD 9構(gòu)建哈希表，采用開放定址法解決沖突。（答案略）2.核心字集