20236月數(shù)據(jù)結(jié)構(gòu)習(xí)題

本文格式為Word版，下載可任意編輯——20236月數(shù)據(jù)結(jié)構(gòu)習(xí)題1、一棵二叉樹沒有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，則該樹總共有____11____個(gè)結(jié)點(diǎn)。

2、數(shù)據(jù)結(jié)構(gòu)的實(shí)質(zhì)就是研究數(shù)據(jù)的、以及定義在規(guī)律結(jié)構(gòu)上所進(jìn)行的一組。

3、棧和隊(duì)列的操作特點(diǎn)分別是___后進(jìn)先出____和_____先進(jìn)先出___。4、設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10，該完全二叉樹一共有____21____個(gè)結(jié)點(diǎn)。

5、一個(gè)圖的_________表示法是唯一的，而___________表示法是不唯一的。6、已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹中有個(gè)葉子結(jié)點(diǎn)。

7、G為無向圖，假使從G的某個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次廣度優(yōu)先探尋，即可訪問圖的每個(gè)頂點(diǎn)，則該圖一定是。

8、結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_____圖狀（網(wǎng)狀）___結(jié)構(gòu)。9、依照二叉樹的遞歸定義，對(duì)二叉樹遍歷的常用算法有先序；中序；后序三種。10、在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有__________個(gè)元素。11、3個(gè)結(jié)點(diǎn)可構(gòu)成棵不同形態(tài)的樹。

12、一棵深度為h的滿二叉樹上的結(jié)點(diǎn)總數(shù)為，一棵深度為h的完全二叉樹上的結(jié)點(diǎn)總數(shù)的最小值為，最大值為。

13、在一棵完全二叉樹中有n個(gè)結(jié)點(diǎn)，對(duì)這些結(jié)點(diǎn)按層序編號(hào)，若一個(gè)結(jié)點(diǎn)編號(hào)為69，則其雙親編號(hào)為，有左孩子的條件是，其左孩子編號(hào)為。

14、根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，尋?？煞譃榧?、線性、樹形、圖狀四類基本結(jié)構(gòu)。

15、數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為__樹形_____結(jié)構(gòu)。

16、要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間繁雜度分別為__n-1和O(n)__。

17、順序存儲(chǔ)的棧中，在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否,在進(jìn)行出棧運(yùn)算時(shí)應(yīng)先判別棧是否。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說明該棧的最大容量

為。

18、在帶頭結(jié)點(diǎn)的循環(huán)鏈表h中，判斷表空的條件是。19、具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為_________。20、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為_________和_________。

21、設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，假使6個(gè)元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)當(dāng)是________。

22、在線性表的順序存儲(chǔ)中，元素之間的規(guī)律關(guān)系是通過決定的；在線性表的鏈?zhǔn)酱鎯?chǔ)中，元素之間的規(guī)律關(guān)系是通過_________決定的。

23、把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體表達(dá)數(shù)據(jù)之間的規(guī)律結(jié)構(gòu)稱為____物理（存儲(chǔ)）____結(jié)構(gòu)。

24、在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行___s->next=p->next____和p->next=s;的操作。25、3個(gè)結(jié)點(diǎn)可以構(gòu)成棵不同形態(tài)的二叉樹。

26、對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵二叉樹時(shí)具有最小高度，即為，當(dāng)它為一棵單支樹時(shí)具有高度，即為。

27、一個(gè)圖的_________表示法是唯一的，而___________表示法是不唯一的。28、在一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹中，對(duì)這些結(jié)點(diǎn)按層序編號(hào)，若一個(gè)結(jié)點(diǎn)編號(hào)為59，則其雙親編號(hào)為，若一個(gè)結(jié)點(diǎn)編號(hào)為23，則其有右孩子的條件是。29、一棵深度為h的完全二叉樹上的結(jié)點(diǎn)總數(shù)的最小值為，最大值為。30、查找法的平均查找長(zhǎng)度與元素個(gè)數(shù)n無關(guān)。31、在帶頭結(jié)點(diǎn)的循環(huán)鏈表h中，判斷表空的條件是。32、一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為。

33、數(shù)組M中每個(gè)元素的長(zhǎng)度是3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址EA開始連續(xù)存放在存儲(chǔ)器中。若按行優(yōu)先方式存放，元素M[8][5]的起始地址為_____________；若按列優(yōu)先方式存放，元素M[8][5]的起始地址為___________。

34、對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間繁雜度為__________；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間繁雜度為_____________。

35、數(shù)據(jù)結(jié)構(gòu)的實(shí)質(zhì)就是研究數(shù)據(jù)的、以及定義在規(guī)律結(jié)構(gòu)上所進(jìn)行的一組操作。

36、在線性表的順序存儲(chǔ)中，元素之間的規(guī)律關(guān)系是通過決定的；在線性表的鏈?zhǔn)酱鎯?chǔ)中，元素之間的規(guī)律關(guān)系是通過指針決定的。37、n個(gè)頂點(diǎn)的連通圖的生成樹有條邊。

38、尋常數(shù)組只有________和________兩種運(yùn)算，因此常采用_________來存儲(chǔ)數(shù)組。

39、具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為_________。

40、任何連通圖的連通分量有__________個(gè)，即________________。

41、結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為____線性___結(jié)構(gòu)。

42、在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，尋常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是值域左指針、右指針。

43、有44個(gè)結(jié)點(diǎn)的完全二叉樹，編號(hào)為22的結(jié)點(diǎn)的左孩子的編號(hào)為_________，其右孩子_________。

44、樹中元素之間的關(guān)系是一對(duì)多的，而圖中元素之間的關(guān)系為_________。1、在具有n個(gè)結(jié)點(diǎn)的二叉排序樹上插入一個(gè)新結(jié)點(diǎn)時(shí)，其時(shí)間繁雜度大致為（）。

A、O（n2）B、O(n)C、O(log2n)D、O(nlog2n)2、下面程序段的時(shí)間繁雜度為（）。

for(i=1;inext==NULLC、h->next==hD、h!=NULL4、單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（）。

A、便利運(yùn)算的實(shí)現(xiàn)B、標(biāo)識(shí)單鏈表

C、使單鏈表中至少有一個(gè)結(jié)點(diǎn)D、用于標(biāo)識(shí)起始結(jié)點(diǎn)的位置

5、某二叉樹的前序和后序序列正好一致，則該二叉樹一定是（）的二叉樹。

A．空或只有一個(gè)結(jié)點(diǎn)B．高度等于其結(jié)點(diǎn)數(shù)C．任一結(jié)點(diǎn)無左孩子D．任一結(jié)點(diǎn)無右孩子

6、一棵非空的二叉樹的前序遍歷與后序遍歷序列正好相反，則該二叉樹一定滿足（）。

A:所有的節(jié)點(diǎn)均無左孩子；B:所有的節(jié)點(diǎn)均無右孩子；C:只有一個(gè)葉子節(jié)點(diǎn)；D:是任意一棵二叉樹

7、在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，則當(dāng)作退棧處理時(shí)，top的變化為（）。

A、top不變B、top=0C、top＝top+1D、top=top-18、鏈棧與順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。

A、尋常不會(huì)出現(xiàn)棧滿的狀況B、尋常不會(huì)出現(xiàn)?？盏臓顩rC、插入操作更加便利D、刪除操作更加便利

9、若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。

A、單鏈表B、雙鏈表C、單向循環(huán)鏈表D、順序表

10、若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再插入兩個(gè)元素后，rear和front的值分別為（）。

A.1和5B.2和4C.4和2D.5和1

11、設(shè)有一個(gè)無向圖G＝（V，E）和G｀＝（V｀，E｀），假使G｀為G的生成樹，則下面不正確的說法是（）。

A、G｀為G的子圖B、G｀為G的連通分量C、G｀為G的微小連通子圖且V｀＝VD、G｀是G的一個(gè)無環(huán)子圖

12、以下說法錯(cuò)誤的是（）A．每個(gè)存儲(chǔ)結(jié)點(diǎn)只能存放一個(gè)數(shù)據(jù)元素

B．?dāng)?shù)據(jù)元素之間的關(guān)聯(lián)方式可由存儲(chǔ)結(jié)點(diǎn)之間的關(guān)聯(lián)方式直接表達(dá)C．一種存儲(chǔ)結(jié)構(gòu)可以在兩個(gè)級(jí)別上探討。其一是機(jī)器級(jí)，其二是語言級(jí)D．語言級(jí)描述可經(jīng)編譯自動(dòng)轉(zhuǎn)換成機(jī)器級(jí)，因此也可以看成是一種機(jī)內(nèi)表示13、設(shè)兩個(gè)串(S1和S2)，求S1在S2中首次出現(xiàn)的位置的運(yùn)算稱為_______。(A)聯(lián)接操作(B)定位操作(C)置換操作(D)賦值操作14、串的長(zhǎng)度是________。

(A)串中不同字母的個(gè)數(shù)(B)串中不同字符的個(gè)數(shù)(C)串中所含字符的個(gè)數(shù)，且大于0(D)串中所含字符的個(gè)數(shù)

15、設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是0—(n-1)，其頭尾指針分別為f和r，其中，f表示隊(duì)頭元素位置，r表示隊(duì)尾元素后面一個(gè)元素的位置，則其隊(duì)滿的條件為________。

(A)r+1==n(B)(r+1)%n==f(C)(r+1)%n==n(D)(f+1)%n==r16、設(shè)有一個(gè)無向圖G＝（V，E）和G｀＝（V｀，E｀），假使G｀為G的生成樹，則下面不正確的說法是（）。

用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)（）。A．僅修改頭指針B．頭、尾指針都要修改C．僅修改尾指針

D．頭、尾指針可能都要修改

17、設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)

V1

V2V5V6

V3

V4V8V7

最正確。

A、線性表的順序存儲(chǔ)結(jié)構(gòu)B、棧

C、隊(duì)列D、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)18、在具有n個(gè)葉子的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（）。

A、不確定B、2nC、2n+1D、2n-119、循環(huán)隊(duì)列的出隊(duì)操作為（）A．sq.front=(sq.ftont+1)%maxsizeB．sq.front=sq.front+1

C．sq.rear=(sq.rear+1)%maxsizeD．sq.rear=sq.rear+1

20、設(shè)數(shù)組Data[0..m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作的語句為（）A．front=front+1B．front=(front+1)%mC．rear=(rear+1)%mD．front=(front+1)%(m+1)

21、在具有n個(gè)結(jié)點(diǎn)的二叉排序樹上插入一個(gè)新結(jié)點(diǎn)時(shí)，其時(shí)間繁雜度大致為（）。

A、O（n2）B、O(n)C、O(log2n)D、O(nlog2n)22、下面程序段的時(shí)間繁雜度為（）。

for(i=1;inext==NULLC、h->next==hD、h!=NULL4、單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（）。A、便利運(yùn)算的實(shí)現(xiàn)B、標(biāo)識(shí)單鏈表

C、使單鏈表中至少有一個(gè)結(jié)點(diǎn)D、用于標(biāo)識(shí)起始結(jié)點(diǎn)的位置

24、一棵非空的二叉樹的前序遍歷與后序遍歷序列正好相反，則該二叉樹一定滿足（）。

A:所有的節(jié)點(diǎn)均無左孩子；B:所有的節(jié)點(diǎn)均無右孩子；C:只有一個(gè)葉子節(jié)點(diǎn)；D:是任意一棵二叉樹

25、在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，則當(dāng)作退棧處理時(shí)，top的變化為（）。

A、top不變B、top=0C、top＝top+1D、top=top-17、鏈棧與順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。A、尋常不會(huì)出現(xiàn)棧滿的狀況B、尋常不會(huì)出現(xiàn)?？盏臓顩rC、插入操作更加便利D、刪除操作更加便利

26、設(shè)有一個(gè)無向圖G＝（V，E）和G｀＝（V｀，E｀），假使G｀為G的生成樹，則下面不正確的說法是（）。

A、G｀為G的子圖B、G｀為G的連通分量C、G｀為G的微小連通子圖且V｀＝VD、G｀是G的一個(gè)無環(huán)子圖27、以下說法錯(cuò)誤的是（）

A．樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨B．線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C．樹形結(jié)構(gòu)可以表達(dá)(組織)更繁雜的數(shù)據(jù)D．樹(及一切樹形結(jié)構(gòu))是一種\分支層次\結(jié)構(gòu)

28、中序遍歷二叉排序樹可以得到一個(gè)有序的序列（）A正確B錯(cuò)誤

29、用非遞歸方法實(shí)現(xiàn)遞歸算法時(shí)一定要使用遞歸工作棧。（）A正確B錯(cuò)誤

30、將f=1+1/2+1/3+…+1/n轉(zhuǎn)化為遞歸函數(shù)時(shí)，遞歸部分為f(n)=f(n-1)+1/n，遞歸終止條件為f(1)=1。（）A正確

B錯(cuò)誤

31、線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示。（）A正確B錯(cuò)誤

32、一個(gè)廣義表((a),((b),c),(((d))))的表尾是((b),c),(((d)))。（）A正確B錯(cuò)誤

33、假使結(jié)點(diǎn)A是結(jié)點(diǎn)B的雙親，而且結(jié)點(diǎn)B有4個(gè)兄弟，則結(jié)點(diǎn)A的度是_______。(A)3(B)4(C)5(D)6

34、設(shè)有一棵樹的度為4，其中度為1、2、3、4結(jié)點(diǎn)的個(gè)數(shù)分別為4、2、1、1，則這棵樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為_______。

(A)5(B)6(C)7(D)835、下面關(guān)于圖的存儲(chǔ)的表達(dá)中正確的是_______。

(A)用鄰接矩陣存儲(chǔ)圖占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無關(guān)(B)用鄰接矩陣存儲(chǔ)圖占用的存儲(chǔ)空間大小只與圖的邊數(shù)有關(guān)，與頂點(diǎn)個(gè)數(shù)無關(guān)(C)用鄰接表存儲(chǔ)圖占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無關(guān)(D)用鄰接表存儲(chǔ)圖占用的存儲(chǔ)空間大小只與圖的邊數(shù)有關(guān)，與頂點(diǎn)個(gè)數(shù)無關(guān)36、深度為6的滿二叉樹上有_______個(gè)結(jié)點(diǎn)。

（A）32（B）64（C）31（D）63

37、設(shè)森林T中有三棵樹，第一、二、三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別是n1，n2，n3，那么當(dāng)把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點(diǎn)的左子樹上有（）個(gè)結(jié)點(diǎn)，右子樹上有（）個(gè)結(jié)點(diǎn)。

A、n1-1B、n1C、n1+n2D、n2+n3

38、設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)

V1

V2V5V6

V3

V4V8V7

最正確。

A、線性表的順序存儲(chǔ)結(jié)構(gòu)B、棧

C