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ù)的存儲(chǔ)結(jié)構(gòu)

B:

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

C:

答D:案：A

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

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

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

循環(huán)隊(duì)列

二叉樹

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)是存儲(chǔ)結(jié)構(gòu)，如隊(duì)列、散列表、鄰接表等。

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

插入運(yùn)算方便

刪除運(yùn)算方便

A:

存儲(chǔ)密度大

B:

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

C:

答D:案：C

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

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

元素時(shí)不方便。

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

素，則下列存儲(chǔ)結(jié)構(gòu)中，最節(jié)省運(yùn)算時(shí)間的是

單鏈表

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

A:

雙向鏈表

B:

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

C:

答D:案：D

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

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

5、【單選題】用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)

僅修改頭指針

僅修改尾指針

A:

頭、尾指針一定都要修改

B:

頭、尾指針可能都要修改

C:

答D:案：D

解析：因?yàn)楫?dāng)隊(duì)列中只有一個(gè)元素時(shí)，刪除此元素后要將隊(duì)列置空，此時(shí)要修改隊(duì)尾指

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

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

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

節(jié)點(diǎn)

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

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

M[8][5]

M[5][8]

A:

M[3][10]

B:

M[0][9]

C:

答D:案：C

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

儲(chǔ)時(shí)，第85個(gè)存儲(chǔ)空間的元素是M[3][10]。

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

2種

3種

A:

4種

B:

C:

5種

答D:案：D

解析：

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

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

前序遍歷

中序遍歷

A:

后序遍歷

B:

以上都不對(duì)

C:

答D:案：B

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

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

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

歷右子樹。

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

含奇數(shù)個(gè)頂點(diǎn)的圖

無向圖

A:

含偶數(shù)個(gè)頂點(diǎn)的圖

B:

有向圖

C:

答D:案：D

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

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

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

拓?fù)渑判蛐蛄械慕Y(jié)論是

存在，且唯一

存在，且不唯—

A:

存在，可能不唯一

B:

無法確定是否存在

C:

答D:案：C

解析：一個(gè)有向圖有拓?fù)湫蛄械某湟獥l件是該圖是有向無環(huán)圖。對(duì)角線以下元素均為零，

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

個(gè)無環(huán)圖，因此有向無環(huán)圖一定存在拓?fù)渑判?，但拓?fù)渑判虿灰欢ㄎㄒ弧?/p>

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

中，—定不在T中的邊是

(b，c)

(b，d)

A:

(c，d)

B:

(c，e)

C:

答D:案：A

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

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

多余的。

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

插入排序

希爾排序

A:

歸并排序

B:

堆排序

C:

答D:案：D

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

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

或最小記錄。

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

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

冒泡排序

插入排序

A:

選擇排序

B:

歸并排序

C:

答D:案：B

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

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

14、【單選題】線性表采用順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，對(duì)其進(jìn)行查找的方法應(yīng)是

順序查找

二分查找

A:

散列查找

B:

索引查找

C:

答D:案：A

解析：順序查找無論是順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)都同樣適用，缺點(diǎn)就是效率低。二分查找對(duì)象

是順序存儲(chǔ)結(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

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

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

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

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

（2）進(jìn)棧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的前序遍歷序

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

表的正確元素值.

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

解析：

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

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

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

G是否是有向無環(huán)圖？（2）給出圖G所有的拓?fù)渑判蛐蛄小?/p>

答案：（1）是有向無環(huán)圖（2）該圖的拓?fù)渑判蛐蛄杏校海?，2，5，4，3，6）和（1，

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

解析：有向無環(huán)圖指的是一個(gè)無回路的有向圖，圖G沒有回路。拓?fù)湫蛄械耐負(fù)渑判蛩惴?/p>

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

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

的頂點(diǎn)數(shù)，則輸出“有回路”信息，否則輸出的頂點(diǎn)序列就是一種拓?fù)湫蛄小?/p>

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

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

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

答案：

解析：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個(gè)數(shù)，所以12除8=1.5是查找長(zhǎng)度。

20、【問答題】己知隊(duì)列的基本操作定義如下，請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)?shù)恼Z句，完成指定的

功能。

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

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

組b中.請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容將算法補(bǔ)充完整，

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

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

結(jié)果。

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

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

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

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

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

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

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

序序列了.

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

答案：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;}

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

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

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

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

點(diǎn)稱為。

答案：頭結(jié)點(diǎn)

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

存儲(chǔ)單元個(gè)數(shù)是。

答案：320

28、【填空題】對(duì)長(zhǎng)度為1的廣義表A，若有Head（A）=Tail（A），則A=。

答案：（（））

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

（）。

答案：2h-1

解析：

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

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