?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2017年4月真題(02142)
摘要:數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2017年4月真題及答案解析(02142),該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷,包含答案及詳細(xì)解析。
數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2017年4月真題及答案解析(02142)
數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2017年4月真題及答案解析(02142),該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷,包含答案及詳細(xì)解析。
一、單項(xiàng)選擇題(本大題共15小題。每小題2分,共30分)在每小題歹硅出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的請將其選躦并將“答題卡”的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無分。
1.任意兩個(gè)結(jié)點(diǎn)之間都沒有鄰接關(guān)系,組織形式松散,這種組織形式稱為( )
A.集合
B.線性結(jié)構(gòu)
C.樹形結(jié)構(gòu)
D.圖結(jié)構(gòu)
2.表示數(shù)據(jù)元素之間的關(guān)聯(lián)方式通常采用的存儲(chǔ)方式是( )
A.順序存儲(chǔ)方式和索引存儲(chǔ)方式
B.鏈?zhǔn)酱鎯?chǔ)方式和散列存儲(chǔ)方式
C.順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式
D.鏈?zhǔn)酱鎯?chǔ)方式和索引存儲(chǔ)方式
3.下面幾種算法時(shí)間復(fù)雜度階數(shù)中,最小的是( )
A.O(log2n)
B.O(n)
C.O(n2)
D.O(2n)
4.雙向循環(huán)鏈表中,在指針P所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t,正確的語句為( )
A.t->prior-P;
t->next=p->next;
p->next->prior=t;
p->next=t;
B.t->prior=p;
t->next=p->next;
p->next=t;
C.t->prior-P;
p->next->prior=t;
t->next=p->next;
P->next=t;
D.p->next-->prior=t;
p->next=t;
5.棧的修改原則是( )
A.先進(jìn)先出
B.后進(jìn)先出
C.??談t進(jìn)
D.棧滿則出
6.設(shè)有一順序隊(duì)列SQ,已知尾指針rear<隊(duì)列的最大長度-1,則數(shù)據(jù)x進(jìn)行入隊(duì)列操作的語句為( )
A.SQ.front=SQ.front+1;
B.SQ.front=SQ.rear+1;
C.SQ.front=SQ.front+1; SQ.dataF[Sq.front]=x;
D.SQ.rear=SQ.rear+1; SQ.datar[SQ.rear]=x;
7.一個(gè)數(shù)組的第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素占2存儲(chǔ)單元,則第5個(gè)元素的存儲(chǔ)地址是( )
A.105
B.108
C.115
D.118
8.樹中葉子的度是( )
A.0
B.1
C.2
D.3
9.將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào),若編號(hào)i所對應(yīng)的結(jié)點(diǎn)為A,且i>1,則A的雙親的編號(hào)為( )
A.i
B.i/2
C.
D.
10.含有100個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)時(shí),空指針域NULL的個(gè)數(shù)是( )
A.99個(gè)
B.100個(gè)
C.101個(gè)
D.200個(gè)
11.一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為( )
A.n(n-1)/2
B.n(n-1)
C.n2/2
D.n2
12.圖的深度優(yōu)先搜索遍歷類似于樹的( )
A.先序遍歷
B.中序遍歷
C.后序遍歷
D.層次遍歷
13.靜態(tài)查找表指對查找表只進(jìn)行兩項(xiàng)操作,即( )
A.插入和刪除一個(gè)數(shù)據(jù)元素
B.查找表中某一元素和插入一個(gè)數(shù)據(jù)元素
C.讀取表中“特定”數(shù)據(jù)元素和刪除一個(gè)數(shù)據(jù)元素
D.查找表中某一元素和讀取表中“特定”數(shù)據(jù)元素
14.若在線性表中采用二分查找法查找元素,該線性表應(yīng)該( )
A.元素按值有序,且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
B.元素按值無序,且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
C.元素按值有序,且采用順序存儲(chǔ)結(jié)構(gòu)
D.元素按值無序,且采用順序存儲(chǔ)結(jié)構(gòu)
15.下列排序方法中不穩(wěn)定的是( )
A.冒泡排序
B.二路歸并
C.堆排序
D.直接插入排序
二、填空題(本大題共13小題,每小題2分。共26分)
11.從宏觀上看,數(shù)據(jù)、數(shù)據(jù)元素和_________反映了數(shù)據(jù)組織的三個(gè)層次。
12.線性表、棧和隊(duì)列中的元素具有相同的邏輯結(jié)構(gòu),即_________。
13.一個(gè)算法的時(shí)空性是指該算法的時(shí)間性能和_________。
14.為了便于運(yùn)算的實(shí)現(xiàn),在單鏈表的第一個(gè)結(jié)點(diǎn)之前增設(shè)一個(gè)類型相同的結(jié)點(diǎn),稱之為_________。
15.假設(shè)一個(gè)8階的上三角矩陣A按照列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組8中,則B數(shù)組的大小應(yīng)為_________。
16.在棧中,允許進(jìn)行插入和刪除操作的一端稱為_________。
17.即使輸入非法數(shù)據(jù),算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理,不會(huì)產(chǎn)生預(yù)料不到的運(yùn)行結(jié)果, 這種評價(jià)算法好壞的因素稱為_________。
18.設(shè)棧S的初始狀態(tài)為空,若元素a,b,C,d依次進(jìn)棧,得到的出棧序列是c,d,b,a,則棧的容量至少是_________。
19.若一棵完全二叉樹有14個(gè)結(jié)點(diǎn),則它的深度為_________。
110.樹的雙親表示法由一個(gè)一維數(shù)組構(gòu)成,數(shù)組的每個(gè)分量包含_________和雙親域兩個(gè)域。
111.如果包含n個(gè)頂點(diǎn)的連通圖G的一個(gè)子圖G’的邊數(shù)大于n-1,則G’中一定有_________。
112.在含有9個(gè)元素的有序表(2,4,12,18,23,37,49,51,68)中二分查找關(guān)鍵字(關(guān)鍵字即為數(shù)據(jù)元素的值)為37的元素時(shí),所需進(jìn)行的比較次數(shù)為_________次。
113.從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較,然后將其放在已排序序列的合適位置,該排序方法稱為_________排序法。
三、應(yīng)用題(本大題共5小題。每小題6分,共30分)
21.設(shè)A、B、C、D、E五個(gè)元素依次進(jìn)棧(進(jìn)棧后可立即出棧),問能否得到下列序列:(1)A,B,C,D,E; (2)A,C,E,B,D若能得到,剛給出該序列的操作過程(用push(A)表示A進(jìn)棧,pop(A)表示A出棧);若不能,則說明理由。
22.已知一棵二叉樹的先序遍歷結(jié)果為ABDCEF,中序遍歷結(jié)果為DBAECF,試畫出這棵二叉樹,并寫出這棵二叉樹的后序遍歷序列。
23.畫出題31圖所示森林經(jīng)轉(zhuǎn)換后所對應(yīng)的二叉樹。
24.已知如題 32 圖所示的無向帶權(quán)圖,請從結(jié)點(diǎn) A 出發(fā),用普里姆(Prim)算法求其最小生成樹,并畫出過程示意圖。
25.將一組鍵值 {83,69,41,22,15,33,8,76} 應(yīng)用二路歸并排序算法從小到大排序,試寫出各趟排序的結(jié)果。
四、算法設(shè)計(jì)題(本大題共2小題,每小題7分。共14分)
31.設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)以下功能:在整型數(shù)組A[n]中查找值為k的元素,若找到,貝!1輸出其位置i(0≤i≤n-1),否則輸出-1作為標(biāo)志。
32.已知二叉鏈表的類型定義如下:typedef struct btnode{ DataType data; struct btnode *lchild, *rchild;}*BinTree;利用二叉樹遍歷的遞歸算法,設(shè)計(jì)求二叉樹的高度的算法Height(BinTree bt)。
延伸閱讀
- 2023年10月自考00257票據(jù)法真題
- 2023年10月自考00249國際私法真題
- 2023年10月自考00246國際經(jīng)濟(jì)法概論真題
- 2023年10月自考00245刑法學(xué)真題
- 2023年10月自考00186國際商務(wù)談判真題
- 2023年10月自考00185商品流通概論真題
自考微信公眾號(hào)
掃碼添加
自考備考資料免費(fèi)領(lǐng)取
去領(lǐng)取