2023春國家開放大學(xué)-02272數(shù)據(jù)結(jié)構(gòu)（本）-期末考試題帶答案

單選題1、采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（）。

正確選項(xiàng)1.(n+1)/2(V)

2、（）不屬于線性表的基本操作。

正確選項(xiàng)1.求子表(V)

3、8.對于一個(gè)鏈串s，查找第一個(gè)字符值為x的算法的時(shí)間復(fù)雜度為（）

正確選項(xiàng)1.O(n)(V)

4、表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。

正確選項(xiàng)1.abc+*d-(V)

5、采用折半查找方法查找長度為n的線性表時(shí)，其算法的時(shí)間復(fù)雜度為（）。

正確選項(xiàng)1.O(log2n)(V)

6、串函數(shù)Strcat（a,b）的功能是進(jìn)行串（）。

正確選項(xiàng)1.連接(V)

7、帶頭結(jié)點(diǎn)的單向鏈表L為空的判定條件是（）。

正確選項(xiàng)1.L->next==NULL(V)

8、帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空表的條件是（）。

正確選項(xiàng)1.L->next==L(V)

9、當(dāng)利用大小為100的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，隊(duì)列的最大長度為（）。

正確選項(xiàng)1.99(V)

10、當(dāng)利用大小為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==-1表示?？?，則入棧應(yīng)該執(zhí)行（）語句修改top指針。

正確選項(xiàng)1.top++(V)

11、當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱為（）。

正確選項(xiàng)1.交換排序(V)

12、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（）。

正確選項(xiàng)1.2e(V)

13、非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。

正確選項(xiàng)1.p->next==head(V)

14、關(guān)于棧和隊(duì)列的說法中，錯(cuò)誤的是（）。

正確選項(xiàng)1.棧是先進(jìn)先出，隊(duì)列是后進(jìn)先出(V)

15、廣義表(f,h,(a,b,d,c),d,e,((i,j),k))的長度是()。

正確選項(xiàng)1.6(V)

16、假定一棵二叉樹中，葉子結(jié)點(diǎn)數(shù)為10，單分支結(jié)點(diǎn)數(shù)為30，則雙分支結(jié)點(diǎn)數(shù)為（）。

正確選項(xiàng)1.9(V)

17、就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關(guān)系是（）。

正確選項(xiàng)1.堆排序<

快速排序<

歸并排序(V)

18、空串與空格串（）。

正確選項(xiàng)1.不相同(V)

19、鏈表所具備的特點(diǎn)是（）。

正確選項(xiàng)1.插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)(V)

20、每個(gè)存儲(chǔ)結(jié)點(diǎn)只存儲(chǔ)一個(gè)數(shù)據(jù)元素，各結(jié)點(diǎn)存儲(chǔ)在連續(xù)的存儲(chǔ)空間，該存儲(chǔ)方式是（）存儲(chǔ)方式。

正確選項(xiàng)1.順序(V)

21、某串的長度小于一個(gè)常數(shù)，則采用（）存儲(chǔ)方式最節(jié)省空間。

正確選項(xiàng)1.順序(V)

22、判斷向上增長型的順序?？盏臈l件是（）。

正確選項(xiàng)1.top=-1(V)

23、如果進(jìn)行串的比較，下列哪個(gè)串最大？（）

正確選項(xiàng)1.“BEIJING”(V)

24、如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（）。

正確選項(xiàng)1.必須判斷棧是否空(V)

25、如圖所示二叉樹的中序遍歷序列是（）。

正確選項(xiàng)1.dgbaechf(V)

26、設(shè)a，b為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在后續(xù)遍歷中，a在b前的條件是（）。

正確選項(xiàng)1.a在b下方(V)

27、設(shè)頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點(diǎn),則通過以下操作（)可使其成為單向循環(huán)鏈表。

正確選項(xiàng)1.p->next=head;(V)

28、設(shè)有兩個(gè)長度為n的單向鏈表，結(jié)點(diǎn)類型相同，分別是循環(huán)鏈表和非循環(huán)鏈表，則（）。

正確選項(xiàng)1.對于兩個(gè)鏈表來說，刪除最后一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(n)(V)

29、設(shè)有一個(gè)廣義表A(a)，其表尾為（）。

正確選項(xiàng)1.()(V)

30、樹的（）沒有前驅(qū)結(jié)點(diǎn)，其他結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)。

正確選項(xiàng)1.根結(jié)點(diǎn)(V)

31、樹形結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系是（）

正確選項(xiàng)1.一對多(V)

32、樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（）。

正確選項(xiàng)1.-1(V)

33、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。

正確選項(xiàng)1.數(shù)據(jù)元素間的關(guān)系的表示(V)

34、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）。

正確選項(xiàng)1.邏輯結(jié)構(gòu)(V)

35、通常的使用順序?；蛘哝湕?shí)現(xiàn)遞歸算法，下面哪個(gè)說法正確（）。

正確選項(xiàng)1.順序棧和鏈棧性能基本相同(V)

36、圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。

正確選項(xiàng)1.先序(V)

37、下列廣義表中的線性表是（）。

正確選項(xiàng)1.E(a,b)(V)

38、下列說法不正確的是（）。

正確選項(xiàng)1.串不是線性結(jié)構(gòu)(V)

39、下面的操作不是棧基本運(yùn)算的是（）。

正確選項(xiàng)1.排序操作(V)

40、線性結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系是（）

正確選項(xiàng)1.一對一(V)

41、向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）。

正確選項(xiàng)1.先移動(dòng)棧頂指針，再存入元素(V)

42、已知某二叉樹的后續(xù)遍歷序列是dabec，中序遍歷是debac，則它的先序遍歷序列是（）。

正確選項(xiàng)1.cedba(V)

43、有關(guān)線性表的正確說法是（）。

正確選項(xiàng)1.除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼(V)

44、有一個(gè)長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。

正確選項(xiàng)1.29/10(V)

45、有一個(gè)長度為12的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。

正確選項(xiàng)1.37/12(V)

46、在二叉樹的第4層最多含有（）個(gè)結(jié)點(diǎn)。

正確選項(xiàng)1.8(V)

47、在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）。

正確選項(xiàng)1.只有右子樹上的所有結(jié)點(diǎn)(V)

48、在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。

正確選項(xiàng)1.2(V)

49、在一個(gè)長度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開始從后到前依次移動(dòng)了15個(gè)元素。則原順序表的長度為（）。

正確選項(xiàng)1.20(V)

50、在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（）鄰接點(diǎn)。

正確選項(xiàng)1.出邊(V)

51、棧的基本運(yùn)算包括（）

正確選項(xiàng)1.取棧頂元素(V)判斷題1、哈夫曼樹一定是完全二叉樹或滿二叉樹。

正確選項(xiàng)1.×(V)

2、AOV網(wǎng)是一個(gè)帶權(quán)的有向圖。

正確選項(xiàng)1.×(V)

3、采用分塊查找時(shí)，數(shù)據(jù)的組織方式是把數(shù)據(jù)分成若干塊，塊內(nèi)數(shù)據(jù)不必有序，但塊間必需有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引表。

正確選項(xiàng)1.√(V)

4、采用分塊查找時(shí)，數(shù)據(jù)的組織方式為把數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引表。

正確選項(xiàng)1.×(V)

5、串的兩種最基本的存儲(chǔ)方式是順序和鏈接。

正確選項(xiàng)1.√(V)

6、串中的元素只可能是字母。

正確選項(xiàng)1.×(V)

7、遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。

正確選項(xiàng)1.×(V)

8、遞歸算法可讀性差，但是效率高

正確選項(xiàng)1.×(V)

9、遞歸算法執(zhí)行時(shí)，每次遞歸可將原問題的規(guī)?？s小。

正確選項(xiàng)1.√(V)

10、隊(duì)列的特性是先進(jìn)后出。

正確選項(xiàng)1.×(V)

11、對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。

正確選項(xiàng)1.√(V)

12、對稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對應(yīng)的三元組包括該元素的行號、列號和元素值三項(xiàng)信息。

正確選項(xiàng)1.√(V)

13、對于一棵深度為h，度為3的樹最多有（3h-1）/2個(gè)結(jié)點(diǎn)。

正確選項(xiàng)1.×(V)

14、二叉樹的遍歷就是按照一定次序訪問樹中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)的值僅被訪問一次的過程。

正確選項(xiàng)1.√(V)

15、分塊查找分為兩個(gè)步驟：第一步是要對索引表進(jìn)行查找；第二步是在塊中查找。這兩步查找都可以采用折半查找或者順序查找方法。

正確選項(xiàng)1.×(V)

16、各種鏈表只需定義有兩個(gè)域的結(jié)點(diǎn)。

正確選項(xiàng)1.×(V)

17、根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列是唯一的。

正確選項(xiàng)1.×(V)

18、哈夫曼樹葉結(jié)點(diǎn)數(shù)比非葉結(jié)點(diǎn)數(shù)多1。

正確選項(xiàng)1.√(V)

19、鏈棧通常不會(huì)出現(xiàn)棧滿的狀態(tài)

正確選項(xiàng)1.√(V)

20、兩個(gè)字符串比較時(shí)，較長的串比較短的串大

正確選項(xiàng)1.×(V)

21、鄰接表只能用于存儲(chǔ)有向圖，而鄰接矩陣則可存儲(chǔ)有向圖和無向圖。

正確選項(xiàng)1.×(V)

22、滿二叉樹中沒有度為1的結(jié)點(diǎn)。

正確選項(xiàng)1.√(V)

23、如果結(jié)點(diǎn)A有3個(gè)兄弟3個(gè)孩子，而且B是A的雙親，則A的度是3。

正確選項(xiàng)1.×(V)

24、散列技術(shù)中的沖突指的是兩個(gè)元素具有相同的序號。

正確選項(xiàng)1.×(V)

25、刪除順序表的最后一個(gè)元素，需要移動(dòng)的元素最多。

正確選項(xiàng)1.×(V)

26、設(shè)廣義表L=（（），（）），則其表頭是（（））。

正確選項(xiàng)1.×(V)

27、設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為BCDA。

正確選項(xiàng)1.×(V)

28、設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，指針p指向尾結(jié)點(diǎn)，現(xiàn)要使p指向第一個(gè)結(jié)點(diǎn)，可用語句p=p->next;。

正確選項(xiàng)1.√(V)

29、設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，指針p指向表中某結(jié)點(diǎn)，若邏輯表達(dá)式p->next==head;的結(jié)果為真，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。

正確選項(xiàng)1.√(V)

30、深度為k的完全二叉樹至少有2k-1個(gè)結(jié)點(diǎn)。

正確選項(xiàng)1.×(V)

31、使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲(chǔ)空間。

正確選項(xiàng)1.√(V)

32、樹是一種線性結(jié)構(gòu)。

正確選項(xiàng)1.×(V)

33、樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)。

正確選項(xiàng)1.√(V)

34、樹最適合表示元素之間具有層次關(guān)系的數(shù)據(jù)。

正確選項(xiàng)1.√(V)

35、數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲(chǔ)該結(jié)構(gòu)的計(jì)算機(jī)相關(guān)的。

正確選項(xiàng)1.×(V)

36、數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。

正確選項(xiàng)1.√(V)

37、數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對多的關(guān)系稱為樹狀結(jié)構(gòu)。

正確選項(xiàng)1.×(V)

38、數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。

正確選項(xiàng)1.√(V)

39、順序查找是一種最簡單的查找方法。

正確選項(xiàng)1.√(V)

40、順序隊(duì)列的入隊(duì)算法是先檢查隊(duì)列是否為滿，若不滿則將新元素值賦給隊(duì)頭指針?biāo)赶虻臄?shù)據(jù)單元，再將隊(duì)頭指針加1。

正確選項(xiàng)1.×(V)

41、線性表的順序存儲(chǔ)是利用數(shù)組來實(shí)現(xiàn)的。

正確選項(xiàng)1.√(V)

42、線性表用順序方式存儲(chǔ)可以隨機(jī)訪問。

正確選項(xiàng)1.√(V)

43、序列15,13,16,14,19,17，采用冒泡排序算法(升序)，經(jīng)一趟冒泡后，結(jié)果序列是13,15,14,16,17,19。

正確選項(xiàng)1.√(V)

44、一個(gè)有向圖的鄰接表和逆鄰接表中的節(jié)點(diǎn)個(gè)數(shù)一定相等。

正確選項(xiàng)1.√(V)

45、已知一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹。

正確選項(xiàng)1.×(V)

46、用鄰接矩陣存儲(chǔ)圖的時(shí)候，占用空間大小不但與圖的結(jié)點(diǎn)個(gè)數(shù)有關(guān)還與圖的邊數(shù)有關(guān)。

正確選項(xiàng)1.×(V)

47、用數(shù)組實(shí)現(xiàn)順序棧，棧底可以是數(shù)組空間的任何一端

正確選項(xiàng)1.√(V)

48、由一個(gè)具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有n-1條邊。

正確選項(xiàng)1.√(V)

49、在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針后移，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，頭指針后移。

正確選項(xiàng)1.√(V)

50、在對10個(gè)記錄的序列(14,30,10,7,22,13,66,85,47,58)進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄13插入到有序表時(shí)，為尋找插入位置，需比較3次。

正確選項(xiàng)1.×(V)

51、在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是哈希表查找。

正確選項(xiàng)1.√(V)

52、在歸并排序中，在第3趟歸并中，是把長度為4的有序表歸并為長度為8的有序表。

正確選項(xiàng)1.√(V)

53、在雙向循環(huán)鏈表上，刪除最后一個(gè)結(jié)點(diǎn)，其算法的時(shí)間復(fù)雜度為0(1)。

正確選項(xiàng)1.√(V)

54、在一個(gè)查找表中，能夠唯一地確定一個(gè)記錄的關(guān)鍵字稱為主關(guān)鍵字。

正確選項(xiàng)1.√(V)

55、在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中,隊(duì)頭指針指向隊(duì)頭元素的后一個(gè)位置。

正確選項(xiàng)1.×(V)

56、在有序順序存儲(chǔ)的線性表中查找一個(gè)元素，用折半查找速度一定比順序查找快。

正確選項(xiàng)1.×(V)

57、長度為0的線性表稱為空表。

正確選項(xiàng)1.√(V)

58、字符串屬于線性的數(shù)據(jù)結(jié)構(gòu)

正確選項(xiàng)1.√(V)綜合題1、在下面空格處填寫一條語句，以使下面的順序隊(duì)列入隊(duì)算法完整。voidInQueue(structSeqQueue*sq,intx){if(sq->rear==MaxSize)

{printf(“隊(duì)列已滿！\n”);exit(1);}______________sq->rear++;}

正確選項(xiàng)1.sq->data[sq->rear]=x;(V)

2、設(shè)有數(shù)據(jù)集合{50，39，17，83，91，14，65}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹，是如下的（）。

正確選項(xiàng)1.(V)

3、以下為求二叉樹深度的算法，完成程序中空格部分。intBTreeDepth(BTreeNode*BT){

if(BT==NULL)

return0;

else

{intdep1=BTreeDepth(BT->left);/*計(jì)算左子樹的深度*/

intdep2=BTreeDepth(BT->right);/*計(jì)算右子樹的深度*/

if(________)

returndep1+1;

else

returndep2+!;

}}

正確選項(xiàng)1.dep1>dep2(V)

4、設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表中（結(jié)點(diǎn)類型為NODE），p為指向該鏈表中某個(gè)結(jié)點(diǎn)的指針。以下程序段為插入一個(gè)指針為s的結(jié)點(diǎn)，使它成為p結(jié)點(diǎn)的直接前驅(qū)，請把合適選項(xiàng)填寫到空行處。NODE*q;q=head;while(q->next!=p)q=q->next;s->next=p;________;

正確選項(xiàng)1.q->next=s(V)

5、寫出下列程序段執(zhí)行后的結(jié)果SeqQueueQ;

InitQueue(Q);inti,a[4]={5,8,12,15};for(i=0;i<4;i++)InQueue(Q,a[i]);InQueue(Q,OutQueue(Q));InQueue(Q,30);InQueue(Q,OutQueue(Q)+10);while(!QueueEmpty(Q))printf(“%d”,OutQueue(Q));

正確選項(xiàng)1.121553018(V)

6、設(shè)數(shù)據(jù)序列為：{53,30,37,12,45,24,96}，從空二叉樹開始逐個(gè)插入該數(shù)據(jù)序列來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（）。

正確選項(xiàng)1.37,24,12,30,53,45,96(V)

7、以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。voidPreorder(structBTreeNode*BT){if(BT!=NULL)

{_________________;Preorder(BT-->left);Preorder(BT-->right);}}

正確選項(xiàng)1.printf(“%c”,BT->data)(V)

8、設(shè)查找表為：用折半查找在該查找表成功查找到元素55需要經(jīng)過（）次比較。

正確選項(xiàng)1.2(V)

9、設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head。以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data，完成程序中空格部分。#defineNULL0voidmain(){NODE*head,*p;p=head;/*p為工作指針*/do{printf(“%d\n”,p->data);p=p->next;}while(________);}

正確選項(xiàng)1.p!=NULL(V)

10、設(shè)關(guān)鍵字序列為：（36，69，46，28，30，74），將此序列用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果為（）。

正確選項(xiàng)1.30，28，36，46，69，74(V)

11、以1，2，3，6，7，8作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹是如下哪個(gè)圖？（）

正確選項(xiàng)1.(V)

12、在下面空格處填寫一條語句，以使下面的串連接算法完整。char*strcat(char*s1,char*s2){char*p=s1;while(*p!='\0')p++;while(*s2!='\0'){*p=*s2;p++;_____}*p='\0';

returns1;}

正確選項(xiàng)1.s2++;(V)

13、以下程序是快速排序的算法，完成程序中空格部分。設(shè)待排序的記錄序列存放在a[start],…a[end]中，按記錄的關(guān)鍵字進(jìn)行快速排序，先進(jìn)行一次劃分，再分別進(jìn)行遞歸調(diào)用。

voidquicksort(NODEa[],intstart,intend){inti,j;NODEmid;if(start>=