?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2017年10月真題（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2017年10月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2017年10月真題及答案解析（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

一、單項(xiàng)選擇題：本大題共15小題，每小題2分，共30分。在每小題列出的備選項(xiàng)中只有一項(xiàng)是最符合題目要求的，請(qǐng)將其選出。

1.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的(　　)

A.存儲(chǔ)結(jié)構(gòu)
B.邏輯結(jié)構(gòu)
C.類型
D.運(yùn)算實(shí)現(xiàn)

2.時(shí)間復(fù)雜度的階數(shù)中，O(n)表示(　　)

A.常數(shù)階
B.線性階
C.多項(xiàng)式階
D.指數(shù)階

3.假設(shè)順序表的長(zhǎng)度為n，則在第i(1≤i≤n+1)個(gè)元素之前插入一個(gè)新元素x所需移動(dòng)元素的個(gè)數(shù)為(　　)

A.i
B.n-i
C.n-i+1
D.n

4.在雙向循環(huán)鏈表中，設(shè)p指向待刪結(jié)點(diǎn)，刪除*p的正確語句為(　　)

A.p->prior->next=p->next; p->next->prior=p->prior; free(p);
B.p->next= p->prior->next; p->prior= p->next->prior; free(p);
C.p->prior->next=p->next; p->next->prior=-p->prior;
D.p->next=p->prior->next; p->prior= p->next->prior;

5.關(guān)于棧和隊(duì)列，下面敘述正確的是(　　)

A.函數(shù)的嵌套調(diào)用用隊(duì)列來實(shí)現(xiàn)
B.操作系統(tǒng)中進(jìn)程調(diào)用用棧來實(shí)現(xiàn)
C.程序遞歸的處理用隊(duì)列來實(shí)現(xiàn)
D.棧和隊(duì)列是運(yùn)算受限的線性表

6.設(shè)兩個(gè)數(shù)據(jù)元素類型一致的棧共享一維數(shù)組空間data[max]成為雙棧，兩個(gè)棧的棧底分別設(shè)在數(shù)組兩端，這兩個(gè)棧的棧頂變量分別為top1和top2，且top2≥top1，則下列會(huì)發(fā)生“上溢”情況的是(　　)

A.top1+1=top2
B.top1=top2
C.top2+1-=top1
D.top1+top2=max

7.設(shè)有一循環(huán)隊(duì)列SQ，現(xiàn)將數(shù)據(jù)x進(jìn)行入隊(duì)操作，語句為(　　)

A.SQ. front=(SQ. front+1)%maxsize;
B.SQ. rear=(SQ. rear+1)%maxsize;
C.SQ. front=(SQ. front +1)%maxsize; SQ. data[SQ. front]=x;
D.SQ. rear=(SQ. rear+1)%maxsize; SQ. data[SQ.rear]=x;

8.關(guān)于樹的概念，下面敘述正確的是(　　)

A.樹可以沒有根結(jié)點(diǎn)
B.樹中結(jié)點(diǎn)個(gè)數(shù)不為0
C.樹中可以存在多個(gè)根節(jié)點(diǎn)
D.若樹中存在多個(gè)子樹，則子樹之間可以相交

9.關(guān)于滿二叉樹和完全二叉樹，下面敘述正確的是(　　)

A.完全二叉樹結(jié)點(diǎn)個(gè)數(shù)>滿二叉樹結(jié)點(diǎn)個(gè)數(shù)
B.滿二叉樹一定是完全二叉樹
C.完全二叉樹一定是滿二叉樹
D.含有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log₂n

10.與二叉鏈表結(jié)構(gòu)形式完全相同的是(　　)

A.孩子鏈表
B.孩子兄弟鏈表
C.帶雙親的孩子鏈表
D.雙親鏈表

11.一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為(　　)

A.n²/2
B.n²
C.n(n-1)/2
D.n(n-1)

12.鄰接表的存儲(chǔ)方法結(jié)合了(　　)

A.順序存儲(chǔ)與散列存儲(chǔ)
B.順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)
C.鏈?zhǔn)酱鎯?chǔ)與索引存儲(chǔ)
D.鏈?zhǔn)酱鎯?chǔ)與散列存儲(chǔ)

13.假設(shè)順序表為(b1，b2，b3)，查找b1，b2，b3的概率分別為0.2，0.2，0.6，則順序查找法的平均查找長(zhǎng)度為(　　)

A.1
B.1.2
C.1.4
D.1.6

14.已知一個(gè)有序表為(13，18，24，35，47，50，62，83，90，115，134)，當(dāng)用二分查找方法查找值為90的元素時(shí)，查找成功時(shí)，鍵值比較的次數(shù)為(　　)

A.2
B.3
C.4
D.5

15.在插入排序方法中，類似圖書館中整理圖書的過程的是(　　)

A.希爾排序
B.表插入排序
C.折半插入排序
D.直接插入排序

二、填空題：本大題共13空，每空2分，共26分。

11.在估算算法空間復(fù)雜度時(shí)，一般只需要分析_________所占用的空間。

12.對(duì)于按位置查找運(yùn)算，順序表是隨機(jī)存取，其時(shí)間復(fù)雜度為_________。

13.設(shè)順序表A長(zhǎng)度為100，若下標(biāo)從1開始計(jì)數(shù)，則刪除元素A[10]需要移動(dòng)_________個(gè)元素。

14.循環(huán)隊(duì)列的隊(duì)頭指針為front，隊(duì)尾指針為rear，當(dāng)_________時(shí)表明隊(duì)列為空。

15.對(duì)于一棵包含n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為_________個(gè)。

16.若對(duì)一棵有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹從1開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為1的結(jié)點(diǎn)存儲(chǔ)到A[1]中，其余類推。若i>2，則A[i]的雙親結(jié)點(diǎn)為_________。

17.用于描述分類過程的二叉樹稱為_________。

18.在樹形結(jié)構(gòu)中，每一層結(jié)點(diǎn)只能和上一層中的至多一個(gè)結(jié)點(diǎn)相關(guān)，而在_________中，任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)。

19.Dijkstra算法的思想是按照最短路徑長(zhǎng)度_________的方法產(chǎn)生從一點(diǎn)到其他頂點(diǎn)的最短路徑。

110.遍歷圖的基本方法有深度優(yōu)先搜索和_________優(yōu)先搜索兩種。

111.作為一種數(shù)據(jù)結(jié)構(gòu)，查找表的邏輯結(jié)構(gòu)是_________。

112.對(duì)于具有n個(gè)元素的數(shù)據(jù)序列，采用二叉排序樹查找，平均查找長(zhǎng)度介于_________之間。

113.直接插入排序的空間復(fù)雜度為_________。

三、應(yīng)用題：本大題共5小題，每小題6分，共30分。

21.已知一個(gè)7×6的稀疏矩陣如題29圖所示，試寫出該稀疏矩陣的三元組表示。

22.已知一棵二叉樹如題30圖所示，試求該二叉樹的先序遍歷序列、后序遍歷序列和層次遍歷序列。

23.設(shè)有向圖的鄰接表表示如題31圖所示，請(qǐng)給出每個(gè)頂點(diǎn)的入度和出度。

24.已知散列表的地址空間為0~10，散列函數(shù)為H(key)= key mod11(mod表示求余運(yùn)算)，采用二次探測(cè)法解決沖突，試用鍵值序列20，38，16，27，5，23，56，29建立散列表，并計(jì)算出等概率情況下查找成功的平均查找長(zhǎng)度。

25.給出一組關(guān)鍵字(20，29，11，74，35，3，8，56)，寫出冒泡排序前兩趟的排序結(jié)果，并說明冒泡排序算法的穩(wěn)定性如何?

四、算法設(shè)計(jì)題：本大題共2小題，每小題7分，共14分。

31.設(shè)有一n階方陣A，設(shè)計(jì)算法實(shí)現(xiàn)對(duì)該矩陣的轉(zhuǎn)置。

32.已知二叉鏈表的類型定義如下：typedef struct btnode{  DataType data;   struct btnode *lchild, *rchild;}*BinTree;假定vsit(bt)是一個(gè)已定義的過程，其功能是訪問指針bt所指結(jié)點(diǎn)。設(shè)計(jì)遞歸算法preorder( BinTree bt)實(shí)現(xiàn)在二叉鏈表上的先序遍歷。