違法信息舉報(bào) 客服熱線:400-118-7898
廣告
?
專接本欄目測(cè)試廣告

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

自考 責(zé)任編輯:彭雅倩 2019-06-26

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

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

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

一、單項(xiàng)選擇題(本大題共15小題,每小題2分,共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的,請(qǐng)將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無(wú)分。

1.下列幾種算法時(shí)間復(fù)雜度中,最大的是(  )

A.O(1)
B.O(n)
C.O(log2n)
D.O(n2)

2.數(shù)據(jù)結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鏈”的結(jié)構(gòu)是(  )

A.集合
B.圖結(jié)構(gòu)
C.樹(shù)形結(jié)構(gòu)
D.線性結(jié)構(gòu)

3.在表長(zhǎng)為100的順序表中做插入運(yùn)算,平均移動(dòng)元素的次數(shù)為(  )

A.25
B.33
C.50
D.100

4.已知尾指針的單向循環(huán)鏈表中,在第一個(gè)結(jié)點(diǎn)后面插入一個(gè)新結(jié)點(diǎn),該算法的時(shí)間復(fù)雜度為(  )

A.O(1)
B.O(log2n)
C.O(n)
D.O(n2)

5.下列表述正確的是(  )

A.??諘r(shí)出棧產(chǎn)生“上溢”,棧滿時(shí)進(jìn)棧產(chǎn)生“下溢”
B.??諘r(shí)出棧產(chǎn)生“下溢”,棧滿時(shí)進(jìn)棧產(chǎn)生“上溢”
C.棧空時(shí)出棧和棧滿時(shí)進(jìn)棧均產(chǎn)生“上溢”
D.??諘r(shí)出棧和棧滿時(shí)進(jìn)棧均產(chǎn)生“下溢”

6.隊(duì)列操作的原則是(  )

A.先進(jìn)先出
B.后進(jìn)先出
C.先進(jìn)后出
D.只進(jìn)不出

7.一棵深度為6的滿二叉樹(shù)有(  )

A.63個(gè)結(jié)點(diǎn)
B.64個(gè)結(jié)點(diǎn)
C.127個(gè)結(jié)點(diǎn)
D.128個(gè)結(jié)點(diǎn)

8.在一棵度為3的樹(shù)中,度為3的結(jié)點(diǎn)有4個(gè),度為2的結(jié)點(diǎn)有2個(gè),度為1的結(jié)點(diǎn)有3個(gè),則度為0的結(jié)點(diǎn)有(  )

A.8個(gè)
B.10個(gè)
C.11個(gè)
D.12個(gè)

9.一棵二叉樹(shù)T,度為2的結(jié)點(diǎn)數(shù)為20個(gè),則葉子結(jié)點(diǎn)數(shù)為(  )

A.19個(gè)
B.20個(gè)
C.21個(gè)
D.22個(gè)

10.有10個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)中共有(  )

A.10個(gè)結(jié)點(diǎn)
B.11個(gè)結(jié)點(diǎn)
C.19個(gè)結(jié)點(diǎn)
D.21個(gè)結(jié)點(diǎn)

11.求圖中兩個(gè)結(jié)點(diǎn)之間的最短路徑采用的算法是(  )

A.廣度優(yōu)先搜索(BFS)算法
B.克魯斯卡爾(Kruskal)算法
C.普里姆(Prim)算法
D.迪杰斯特拉(Dijkstra)算法

12.順序查找算法的平均查找長(zhǎng)度為(  )

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

13.二叉排序樹(shù)中,根的(  )

A.左子樹(shù)是二叉排序樹(shù)、右子樹(shù)不一定是二叉排序樹(shù)
B.左子樹(shù)是二叉排序樹(shù)、右子樹(shù)也是二叉排序樹(shù)
C.左子樹(shù)不一定是二叉排序樹(shù)、右子樹(shù)是二叉排序樹(shù)
D.左子樹(shù)不一定是二叉排序樹(shù)、右子樹(shù)也不一定是二叉排序樹(shù)

14.冒泡排序的時(shí)間復(fù)雜度為(  )

A.O(n)
B.O(nlog2n)
C.O(n2)
D.O(log2n)

15.關(guān)于穩(wěn)定性的表述,正確的是(  )

A.穩(wěn)定性是排序方法本身的特性,與數(shù)據(jù)無(wú)關(guān)
B.穩(wěn)定性不是排序方法本身的特性,與數(shù)據(jù)有關(guān)
C.穩(wěn)定性是排序方法本身的特性,與數(shù)據(jù)有關(guān)
D.穩(wěn)定性不是排序方法本身的特性,與數(shù)據(jù)無(wú)關(guān)

二、填空題(本大題共13小題,每小題2分,共26分)

11.數(shù)據(jù)中不可分割的最小標(biāo)識(shí)單位是__________。

12.雙向循環(huán)鏈表中,在p所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t,需要修改四個(gè)指針,分別為:t->prior=p; __________; p->next->prior=t; p->next=t;。

13.在帶有頭結(jié)點(diǎn)的循環(huán)鏈表中,頭指針為head,判斷指針p所指結(jié)點(diǎn)為首結(jié)點(diǎn)的條件是__________。

14.元素的進(jìn)棧次序?yàn)?,2,3,…,n,出棧的第一個(gè)元素是n,則第k個(gè)出棧的元素是__________。

15.在棧結(jié)構(gòu)中,允許插入和刪除的一端稱為_(kāi)_________。

16.100個(gè)結(jié)點(diǎn)的二叉樹(shù)采用三叉鏈表存儲(chǔ)時(shí),空指針域NULL有__________個(gè)。

17.某二叉樹(shù)的先序遍歷序列為ABKLMNO,中序遍歷序列為BLKANMO,則該二叉樹(shù)中結(jié)點(diǎn)A的右孩子為結(jié)點(diǎn)__________。

18.一個(gè)二叉樹(shù)的最少結(jié)點(diǎn)個(gè)數(shù)為_(kāi)_________。

19.圖中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路。除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外,其余頂點(diǎn)不重復(fù)的回路,稱為_(kāi)_________。

110.設(shè)查找表有n個(gè)數(shù)據(jù)元素,則二分查找算法的平均查找長(zhǎng)度為_(kāi)_________。

111.用鍵值通過(guò)散列函數(shù)獲取存儲(chǔ)位置的這種存儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)稱為_(kāi)_________。

112.若在線性表中采用二分查找法查找元素,則該線性表必須按值有序,并且采用__________存儲(chǔ)結(jié)構(gòu)。

113.堆分為最小堆和最大堆,若鍵值序列{k1, k2, …, kn},滿足,則這n個(gè)鍵值序列{k1, k2,…, kn}是__________。

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

21.設(shè)一個(gè)鏈棧的輸入序列為X,Y,Z,試寫(xiě)出出棧的所有可能的輸出序列及其操作步驟。

22.設(shè)二叉樹(shù)的先序遍歷序列為DCBAHEIFG,中序遍歷序列為ABCHDIEFG,試畫(huà)出該二叉樹(shù)并寫(xiě)出后序遍歷序列。

23.已知連通帶權(quán)圖如題31圖所示,試?yán)闷绽锬?Prim)算法,從頂點(diǎn)A出發(fā),構(gòu)造它的最小生成樹(shù),畫(huà)出構(gòu)造過(guò)程。                      題31圖

24.給定表(28,15,55,3,71,75,10,22,56),試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹(shù),畫(huà)出插入完成后的二叉排序樹(shù)。

25.應(yīng)用直接選擇排序算法,對(duì)初始關(guān)鍵字序列為48,35,61,98,82,18,29,48的記錄進(jìn)行從小到大排序,寫(xiě)出排序過(guò)程和結(jié)果。

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

31.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義如下:typedef struct node{   int data;    struct node *next; }Node, *LinkList;試編寫(xiě)在帶頭結(jié)點(diǎn)的單鏈表head中查找第1個(gè)元素值小于x的結(jié)點(diǎn)的實(shí)現(xiàn)算法Node *GetLinklist( LinkList head, int x),若找到,則返回指向該結(jié)點(diǎn)的指針,否則返回NULL。

32.假設(shè)樹(shù)采用孩子兄弟鏈表表示法,其結(jié)構(gòu)定義如下:typedef struct tnode{  DataType data;   struct tnode *son, *brother;}*Tree;試編寫(xiě)算法void leveltree(Tree root)實(shí)現(xiàn)樹(shù)的按層次遍歷。

更多資料

00149《國(guó)際貿(mào)易理論與實(shí)務(wù)》【知識(shí)集錦】

00159《高級(jí)財(cái)務(wù)會(huì)計(jì)》【知識(shí)集錦】

00184《市場(chǎng)營(yíng)銷策劃》【知識(shí)集錦】

溫馨提示:因考試政策、內(nèi)容不斷變化與調(diào)整,本網(wǎng)站提供的以上信息僅供參考,如有異議,請(qǐng)考生以權(quán)威部門公布的內(nèi)容為準(zhǔn)!

自考備考資料免費(fèi)領(lǐng)取

去領(lǐng)取

資料下載
  • 00152《組織行為學(xué)》【知識(shí)集錦】

    下載
  • 00158《資產(chǎn)評(píng)估》【知識(shí)集錦】

    下載
  • 00148《國(guó)際企業(yè)管理》【知識(shí)集錦】

    下載
  • 00160《審計(jì)學(xué)》【知識(shí)集錦】

    下載