2021年數(shù)據(jù)結構考試題庫

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