?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2015年4月真題(02142)
摘要:數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2015年4月真題及答案解析(02142),該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷,包含答案及詳細(xì)解析。
數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2015年4月真題及答案解析(02142)
數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2015年4月真題及答案解析(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è)某個(gè)算法的計(jì)算量是問(wèn)題規(guī)模n的函數(shù):T(n)=anc+blog2n+cn+d,則該算法的時(shí)間復(fù)度可表示成( )
A.O(nC)
B.O(log2 n)
C.O(n)
D.O(1)
2.將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法時(shí)間復(fù)雜度為( )
A.O(n)
B.O(m)
C.O(n+m)
D.O(n×m)
3.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問(wèn)題,通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是( )
A.棧
B.隊(duì)列
C.樹(shù)
D.圖
4.對(duì)于n(n≥0)個(gè)元素構(gòu)成的線(xiàn)性表L,適合采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的操作是( )
A.需要頻繁修改L中元素的值
B.需要頻繁地對(duì)L進(jìn)行隨機(jī)查找
C.需要頻繁地對(duì)L進(jìn)行插入和刪除操作
D.要求L存儲(chǔ)密度高
5.判斷一個(gè)帶有頭結(jié)點(diǎn)的鏈隊(duì)列為空隊(duì)列Q的條件是( )
A.Q.front==NULL
B.Q.front==Q.rear
C.Q.front!=Q.rear
D.Q.rear==NULL
6.在一個(gè)單鏈表中,已知指針q指向指針p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),則刪除* p結(jié)點(diǎn)的操作語(yǔ)句是( )
A.q=p;
B.q=p->next;
C.q->next=p;
D.q->next=p->next;
7.把特殊矩陣A[10][10]的下三角矩陣壓縮存儲(chǔ)到一個(gè)一維數(shù)組M中,則A中元素a[4][3]在M中所對(duì)應(yīng)的下標(biāo)位置是( )
A.8
B.12
C.13
D.55
8.若一棵具有n(n>0)個(gè)結(jié)點(diǎn)的二叉樹(shù)的先序序列與后序序列正好相反,則該二叉樹(shù)一定是( )
A.結(jié)點(diǎn)均無(wú)左孩子的二叉樹(shù)
B.結(jié)點(diǎn)均無(wú)右孩子的二叉樹(shù)
C.存在度為2的結(jié)點(diǎn)的二叉樹(shù)
D.高度為n的二叉樹(shù)
9.對(duì)關(guān)鍵字序列{0,2,4,8,16,32,64,128}進(jìn)行二分查找,則第一個(gè)被查找到的關(guān)鍵字是( )
A.0
B.8
C.16
D.128
10.已知一個(gè)圖如題10圖所示,若從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷,則可能得到的廣度優(yōu)先搜索( )
A.acefbd
B.acbdfe
C.acbdef
D.acdbfe
11.若某二叉樹(shù)按后序遍歷得到的結(jié)果為c、b、a,則可以得到該結(jié)果的二叉樹(shù)有( )
A.1種
B.2種
C.3種
D.5種
12.下列有關(guān)哈夫曼(Huffman)樹(shù)的描述,不正確的是( )
A.哈夫曼樹(shù)的樹(shù)形唯一,且其WPL值最小
B.哈夫曼樹(shù)的樹(shù)形不一定唯一,但其WPL值最小且相等
C.哈夫曼字符編碼不一定唯一,但總碼長(zhǎng)最短
D.哈夫曼樹(shù)沒(méi)有嚴(yán)格要求區(qū)別左右子樹(shù)權(quán)重次序
13.能夠使用二分查找算法進(jìn)行查找的條件是必須以( )
A.順序方式存儲(chǔ),且元素按關(guān)鍵字有序
B.鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字有序
C.順序方式存儲(chǔ),且元素按關(guān)鍵字無(wú)序
D.鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字無(wú)序
14.下列排序方法中不穩(wěn)定的是( )
A.直接插入排序
B.堆排序
C.冒泡排序
D.二路歸并排序
15.對(duì)于n個(gè)元素的關(guān)鍵字序列{k1,k2….,kn),當(dāng)且僅當(dāng)滿(mǎn)足關(guān)系ki≤k2i且ki≤k2i+1(2i≤n,2i+1≤n)稱(chēng)其為最小堆,反之則為最大堆。以下序列中不符合最小堆或最大堆定義的是( )
A.{4,10,15,72,39,23,18}
B.{58,27,36,12,8,23,9}
C.{4,10,18,72,39,23,15}
D.{58,36,27,12,8,23,9}
二、填空題(本大題共13小題,每小題2分。共26分)
11.數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、______、以及對(duì)數(shù)據(jù)及其關(guān)系的操作運(yùn)算。
12.根據(jù)數(shù)據(jù)元素之間的關(guān)系,通常有四類(lèi)基本的邏輯結(jié)構(gòu):集合、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、______.
13.在表長(zhǎng)為n的順序表中插入一個(gè)數(shù)據(jù)元素,平均需要移動(dòng)約______個(gè)數(shù)據(jù)元素。
14.設(shè)有二維數(shù)組A[8][ 10],按行序優(yōu)先存儲(chǔ),且每個(gè)元素占用2個(gè)存儲(chǔ)單元,若第一個(gè)元素的存儲(chǔ)起始位置為b,則存儲(chǔ)位置為b+20處的元素為_(kāi)_____。
15.棧的特點(diǎn)是先進(jìn)后出或后進(jìn)先出,隊(duì)列的特點(diǎn)是______。
16.若一棵二叉樹(shù)中度為1和度為2的結(jié)點(diǎn)個(gè)數(shù)均是3,則該二叉樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)是_____.
17.高度(深度)為h的完全二叉樹(shù)最少的結(jié)點(diǎn)個(gè)數(shù)是______。
18.根據(jù)圖的定義,圖中頂點(diǎn)的最少數(shù)目是______。
19.高度為3、含有5個(gè)結(jié)點(diǎn)(編號(hào)1~5)的二叉樹(shù),其順序存儲(chǔ)結(jié)構(gòu)為,則編號(hào)為4的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為_(kāi)_____。
110.對(duì)如題25圖所示的含有3棵樹(shù)的森林進(jìn)行先序遍歷,得到的結(jié)果序列是______。
111.按關(guān)鍵字的輸入序列{30,22,42,7,25}所生成的二又排序樹(shù)中,其左子樹(shù)上的關(guān)鍵字有______。
112.插入、選擇、冒泡及堆等四種排序方法在各自排序過(guò)程中其鍵值比較的次數(shù)與數(shù)據(jù)元素的初始排列次序無(wú)關(guān)的有______和堆排序。
113.用冒泡排序算法對(duì)n個(gè)帶有鍵值的數(shù)據(jù)元素進(jìn)行排序,排序結(jié)束后所可能歷經(jīng)的最少趟數(shù)為_(kāi)_____。
三、應(yīng)用題(本大題共5小題,每小題6分,共30分)
21.字符a.b、c、d依次通過(guò)一個(gè)棧,按出棧的先后次序組成字符串,至多可以組成多少個(gè)不同的字符串?并分別寫(xiě)出它們。
22.已知某棵二叉樹(shù)的先序遍歷和中序遍歷的結(jié)果序列分別為ABCDEFGHI和BCAEDGHFI。試構(gòu)造出該二叉樹(shù),并給出該二叉樹(shù)的后序遍歷結(jié)果序列。
23.帶權(quán)圖(權(quán)值非負(fù),表示邊連接的兩頂點(diǎn)間的距離)的最短路徑問(wèn)題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑,現(xiàn)有一種解決該問(wèn)題的方法:①設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn),令當(dāng)前頂點(diǎn)u為初始頂點(diǎn);②選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v,加入到最短路徑中,修改當(dāng)前頂點(diǎn)u=v;③重復(fù)步驟②,直到u是目標(biāo)頂點(diǎn)時(shí)為止。現(xiàn)問(wèn)上述方法能否求得最短路徑?若該方法可行,試證明之;否則,舉例說(shuō)明。
24.將關(guān)鍵字序列{7,8,30,11,18,9,14}散列存儲(chǔ)到一個(gè)散列表中,設(shè)該散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開(kāi)始、大小(HashSize)為10的一維數(shù)組,散列函數(shù)為H(key)=(key×3)MOD HashSize,處理沖突采用線(xiàn)性探測(cè)法?,F(xiàn)要求:(1)畫(huà)出所構(gòu)造的散列表;(2)計(jì)算出等概率情況下查找成功的平均查找長(zhǎng)度。
25.若采用冒泡排序方法對(duì)關(guān)鍵字序列{265,301,751,129,937,863,742,694,076,438}進(jìn)行升序排序,寫(xiě)出其每趟排序結(jié)束后的關(guān)鍵字序列。
四、算法設(shè)計(jì)題(本大題共2小題,每小題7分,共14分)
31.寫(xiě)出一個(gè)將線(xiàn)性表的順序表存儲(chǔ)方式(數(shù)組a、表長(zhǎng)為n)改成單鏈表存儲(chǔ)方式(其頭結(jié)點(diǎn)由頭指針head指向)的算法。設(shè)函數(shù)頭為:Node * CreateLinkedList(DataType a[], int n)
32.統(tǒng)計(jì)出一棵二叉樹(shù)中結(jié)點(diǎn)數(shù)據(jù)域的值不小于m的所有結(jié)點(diǎn)個(gè)數(shù)。設(shè)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為:typedef struct btnode{ int data; struct btnode *lchild, *rchile;}BTNode, *BTree;
延伸閱讀
- 2023年10月自考00257票據(jù)法真題
- 2023年10月自考00249國(guó)際私法真題
- 2023年10月自考00246國(guó)際經(jīng)濟(jì)法概論真題
- 2023年10月自考00245刑法學(xué)真題
- 2023年10月自考00186國(guó)際商務(wù)談判真題
- 2023年10月自考00185商品流通概論真題
自考微信公眾號(hào)
掃碼添加
自考備考資料免費(fèi)領(lǐng)取
去領(lǐng)取