2018年4月自考02331數(shù)據(jù)結(jié)構(gòu)試題及答案含解析

數(shù)據(jù)結(jié)構(gòu)年月真題

0233120184

1、【單選題】數(shù)據(jù)結(jié)構(gòu)不包含的內(nèi)容是

數(shù)據(jù)的元素來源

數(shù)據(jù)的邏輯結(jié)構(gòu)

A:

數(shù)據(jù)的存儲結(jié)構(gòu)

B:

對數(shù)據(jù)施加的操作

C:

答D:案：A

解析：數(shù)據(jù)結(jié)構(gòu)包含的內(nèi)容包括三方面內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系，數(shù)據(jù)元素的存儲方

式，數(shù)據(jù)的運算即對數(shù)據(jù)元素施加的操作。

2、【單選題】下列選項中，屬于邏輯結(jié)構(gòu)的是

循環(huán)隊列

二叉樹

A:

散列表

B:

鄰接表

C:

答D:案：B

解析：邏輯結(jié)構(gòu)是反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。邏輯結(jié)構(gòu)反應(yīng)數(shù)據(jù)之間的關(guān)

系，常見的邏輯結(jié)構(gòu)有：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)，其中樹形結(jié)構(gòu)常見的有

二叉樹；物理結(jié)構(gòu)是存儲結(jié)構(gòu)，如隊列、散列表、鄰接表等。

3、【單選題】下列選項中，屬于順序存儲結(jié)構(gòu)優(yōu)點的是

插入運算方便

刪除運算方便

A:

存儲密度大

B:

方便存儲各種邏輯結(jié)構(gòu)

C:

答D:案：C

解析：順序存儲時,相鄰數(shù)據(jù)元素的存放地址也相鄰(邏輯與物理統(tǒng)一);要求內(nèi)存中可用存

儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大，存儲空間利用率高。缺點：插入或刪除

元素時不方便。

4、【單選題】某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元

素，則下列存儲結(jié)構(gòu)中，最節(jié)省運算時間的是

單鏈表

僅有頭指針的單循環(huán)鏈表

A:

雙向鏈表

B:

僅有尾指針的單循環(huán)鏈表

C:

答D:案：D

解析：有尾指針的單鏈表，刪除最后一個元素與鏈表的長度無關(guān)，單循環(huán)鏈表有尾指針，

所以時間復(fù)雜度為O(1),其他的都要O(n)。

5、【單選題】用不帶頭結(jié)點的單鏈表存儲隊列，在進行刪除運算時

僅修改頭指針

僅修改尾指針

A:

頭、尾指針一定都要修改

B:

頭、尾指針可能都要修改

C:

答D:案：D

解析：因為當隊列中只有一個元素時，刪除此元素后要將隊列置空，此時要修改隊尾指

針，使尾指針與頭指針相等（即Q.rear=Q.front）。假設(shè)head是指向隊列的頭結(jié)點指

針，p為與head同類型的指針，那么head->next指向的是隊列的首結(jié)點，那么出隊的操

作為p=head->next;//指向欲出隊的結(jié)點；head->next=p->next;free(p);//銷毀隊首

節(jié)點

6、【單選題】二維數(shù)組M，行下標取值范圍為0～8，列下標取值范圍為1～10，若按行優(yōu)先

存儲時，元素M[8][5]的存儲地址為ar，則按列優(yōu)先存儲時，地址ar存儲的數(shù)組元素應(yīng)是

M[8][5]

M[5][8]

A:

M[3][10]

B:

M[0][9]

C:

答D:案：C

解析：按行優(yōu)先存儲時，元素M[8][5]的存儲地址ar為第85個存儲空間，則按列優(yōu)先存

儲時，第85個存儲空間的元素是M[3][10]。

7、【單選題】根據(jù)二叉樹的定義，3個結(jié)點構(gòu)成的二叉樹的樹型有

2種

3種

A:

4種

B:

C:

5種

答D:案：D

解析：

3個結(jié)點能構(gòu)成的二叉樹如圖：

8、【單選題】—棵有序樹可轉(zhuǎn)換為一棵二叉樹，樹的后序遍歷對應(yīng)二叉樹的

前序遍歷

中序遍歷

A:

后序遍歷

B:

以上都不對

C:

答D:案：B

解析：樹轉(zhuǎn)換成二叉樹：首先在所有兄弟結(jié)點之間加一道連線，然后再對每個結(jié)點保留長

子的連線，去掉該結(jié)點與其他孩子的連線。樹的后序遍歷是指先依次后序遍歷根的每棵子

樹，然后訪問根結(jié)點。二叉樹的中序遍歷1、中序遍歷左子樹2、訪問根節(jié)點3、中序遍

歷右子樹。

9、【單選題】若圖G的鄰接表中有奇數(shù)個表結(jié)點，則G是

含奇數(shù)個頂點的圖

無向圖

A:

含偶數(shù)個頂點的圖

B:

有向圖

C:

答D:案：D

解析：無向圖的鄰接表的表結(jié)點的個數(shù)一定是偶數(shù)，為邊數(shù)的2倍。若圖G的鄰接表中有

奇數(shù)個表結(jié)點，則圖G一定是有向圖。

10、【單選題】若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖

拓撲排序序列的結(jié)論是

存在，且唯一

存在，且不唯—

A:

存在，可能不唯一

B:

無法確定是否存在

C:

答D:案：C

解析：一個有向圖有拓撲序列的充要條件是該圖是有向無環(huán)圖。對角線以下元素均為零，

表明只有頂點i到頂點j（i<j）可能有邊，而頂點j到頂點i一定沒有邊，即有向圖是一

個無環(huán)圖，因此有向無環(huán)圖一定存在拓撲排序，但拓撲排序不一定唯一。

11、【單選題】如果無向圖G的最小生成樹中含有邊（a，b）和（a，c）,則下列選項

中，—定不在T中的邊是

(b，c)

(b，d)

A:

(c，d)

B:

(c，e)

C:

答D:案：A

解析：最小生成樹是：一個有n個結(jié)點的連通圖的生成樹是原圖的極小連通子圖，且包

含原圖中的所有n個結(jié)點，并且有保持圖連通的最少的邊。只有答案A（b，c）這條邊是

多余的。

12、【單選題】下列排序算法中，在每一趟都能選出一個元素放到其最終位罝上的是

插入排序

希爾排序

A:

歸并排序

B:

堆排序

C:

答D:案：D

解析：堆排序的思想：在排序過程中，將記錄數(shù)組看成一棵完全二叉樹的順序存儲結(jié)構(gòu)，

利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系，在當前無序區(qū)中選擇關(guān)鍵字最大

或最小記錄。

13、【單選題】若數(shù)據(jù)元素序列11，13,15,7,8,9,23,2,5是采用下列排序方法之一得到的

第二趟排序后的結(jié)果，則該排序算法是

冒泡排序

插入排序

A:

選擇排序

B:

歸并排序

C:

答D:案：B

解析：插入排序(InsertionSort)的基本思想是：每次將一個待排序的記錄，按其關(guān)鍵字

大小插入到前面已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入完成為止。

14、【單選題】線性表采用順序存儲或鏈式存儲，對其進行查找的方法應(yīng)是

順序查找

二分查找

A:

散列查找

B:

索引查找

C:

答D:案：A

解析：順序查找無論是順序存儲或鏈式存儲都同樣適用，缺點就是效率低。二分查找對象

是順序存儲結(jié)構(gòu)的有序表。

15、【單選題】設(shè)有序表為{1,3,9,12,32,41,45,62,75,77,82},采用二分查找法查找關(guān)鍵字

75,查找過程中關(guān)鍵字之間的比較次數(shù)是

1

2

A:

3

B:

4

C:

答D:案：B

解析：第一次比較時mid=6,第二次mid=9,正好是關(guān)鍵字75.

16、【問答題】兩個棧共享數(shù)組空間data[m]（定義如下），它們的棧底分別設(shè)在數(shù)組的

兩端（初始化后top1=-1，top2=m）。

答案：（1）判斷棧滿Intstackfull(SeqStack*s){returns->top1+1==s->top2;}

（2）進棧Voidpush(SeqStack*S,intsi,DataTypeX){if(stackfull(s))

printf(“satckoverflow”);else{if(si==0)s->data[++s->top1]=x;elses->data[--

s->top2]=x;}}

17、【問答題】已知二叉樹T中含有元素A，B，C，D，E，F(xiàn)，G，H，T的前序遍歷序

列、中序遍歷序列和后序遍歷序列如下，其中符號____表示未知元素.試寫出①到⑩所代

表的正確元素值.

答案：①C②H③D④E⑤H⑥D(zhuǎn)⑦B⑧E⑨G⑩A

解析：

根據(jù)題意可以畫出二叉樹：

18、【問答題】設(shè)圖G如題28圖所

示.回答下列問題。（1）圖

G是否是有向無環(huán)圖？（2）給出圖G所有的拓撲排序序列。

答案：（1）是有向無環(huán)圖（2）該圖的拓撲排序序列有：（1，2，5，4，3，6）和（1，

2，5，4，3，7，6）

解析：有向無環(huán)圖指的是一個無回路的有向圖，圖G沒有回路。拓撲序列的拓撲排序算法

主要是循環(huán)執(zhí)行以下兩步，直到不存在入度為0的頂點為止。(1)選擇一個入度為0的頂

點并輸出之；(2)從網(wǎng)中刪除此頂點及所有出邊。循環(huán)結(jié)束后，若輸出的頂點數(shù)小于網(wǎng)中

的頂點數(shù)，則輸出“有回路”信息，否則輸出的頂點序列就是一種拓撲序列。

19、【問答題】設(shè)關(guān)鍵字序列為：53,15,72,52,48,67,63,23。己知散列表地址空間為0?11,

散列函數(shù)為H（k）=kmod11，采用線性探查再散列法解決沖突。（1）將所給關(guān)鍵字數(shù)

據(jù)依次填入該散列表中；（2）計算等概率下查找成功的平均查找長度。

答案：

解析：53/11余9，15/11余4，72/11余6，53/11余8，48/11余4，沖突后重新分配，

（4+1）/11余5，67/11余1，63/11余8，沖突后重新分配，（8+1）/11余9，還是沖

突，（9+1）/11余10，23/11余1，處理沖突（1+1）/11余2。按余的值放到散列表的相

應(yīng)位置。一共查找了12次，共8個數(shù)，所以12除8=1.5是查找長度。

20、【問答題】己知隊列的基本操作定義如下，請在空白處填寫適當?shù)恼Z句，完成指定的

功能。

答案：(1)Q->rear==Q->front(2)(Q->rear+1)%QueueSize(3)(Q->front+1)%QueueSize

21、【問答題】程序G1是將輸入的m行n列的二維數(shù)組a變換為三元組表形式存儲在數(shù)

組b中.請在空白處填上適當內(nèi)容將算法補充完整，

答案：(1)*a；(2)k++；(3)k

22、【問答題】已知二叉樹7.如題32圖所示.閱讀程序f32,寫出執(zhí)行f32（T）的輸出

結(jié)果。

答案：7,3,9,6,1,5,2,8,4

解析：先輸出右子樹的值，再輸出根結(jié)點的值，再輸出左子樹的值，左右子樹分別遞歸。

23、【問答題】閱讀下列程序，寫出執(zhí)行結(jié)果。

答案：62,32,21,23,25,5,10,1,20,9

解析：堆排序的基本思想是：將待排序序列構(gòu)造成一個大頂堆，此時，整個序列的最大值

就是堆頂?shù)母?jié)點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余n-1個

元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復(fù)執(zhí)行，便能得到一個有

序序列了.

24、【問答題】己知帶有頭結(jié)點的單鏈表定義如下：

答案：intf34(LinkListh,charstring[]){LinkListp,q;Char

*pcintcount=0;Pc=string;While(*pc!=’\0’){P=h;While(p->next!=null){if(p-

>next->ch!=*pc)P=p->next;Elsebreak;}if(p-

>next==null){q=(LinkList)malloc(sizeof(ListNode));q->ch=*pc;q->next=p->next;p-

>next=q;count++;}Pc++;}Returncount;}

解析：就是新建一個ListNode，然后鏈到新鏈表上，如果遇到重復(fù)的字符就跳過去。

25、【填空題】在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和。

答案：非線性結(jié)構(gòu)

26、【填空題】為便于實現(xiàn)單鏈表的插入及刪除運算，需要在單鏈表中增加一個結(jié)點，該結(jié)

點稱為。

答案：頭結(jié)點

27、【填空題】在二維數(shù)組A[10][8]中，每個數(shù)組元素占用4個存儲單元，則數(shù)組A需要的

存儲單元個數(shù)是。

答案：320

28、【填空題】對長度為1的廣義表A，若有Head（A）=Tail（A），則A=。

答案：（（））

29、【填空題】設(shè)高為h的二叉樹T中只有度為0和2的結(jié)點，則T包含的結(jié)點數(shù)最多為

（）。

答案：2h-1

解析：

考慮按如下規(guī)則構(gòu)造一棵高度為H的二叉樹，可使得其節(jié)點數(shù)最少：1)構(gòu)造一個根結(jié)點2)

為根結(jié)點構(gòu)造2個兒子結(jié)點3)如果樹的高度已經(jīng)達到H，則結(jié)束；否則以上