《2021國開大學電大本科《數(shù)據(jù)結(jié)構(gòu)》期末試題及答案(試卷號:1252)》由會員分享,可在線閱讀,更多相關(guān)《2021國開大學電大本科《數(shù)據(jù)結(jié)構(gòu)》期末試題及答案(試卷號:1252)(6頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、國家開放大學電大本科《數(shù)據(jù)結(jié)構(gòu)》期末試題及答案(試卷號:1252)
2022盜傳必究
用分|評卷人| 工.
— —— 一、單項選擇腰(把合適的選項Ml號填寫在括號內(nèi)。符小分.共
45 分)
】?在數(shù)據(jù)結(jié)構(gòu)中.從謨捌上可以把數(shù)據(jù)結(jié)枸分為《
A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)
C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)
2.下面程序段的時間復雜度是( J.
H.緊密籍構(gòu)和非緊漠結(jié)構(gòu)
D.找性結(jié)構(gòu)和非線性結(jié)構(gòu)
for(i=l i!<- nii4-4 )
fcr(i=頃 V = n$ j + 十”
for(k=l ik< = nilc-f- +)
cCiWAcEE+MiNk]"住1口\
2(XD
2、
& 0( logj n >
C. O(n)
D.()3)
3.在一個單堡表中p指向結(jié)點a?q疳向結(jié)點a的宜接后撰結(jié)點b.要刪除結(jié)點b.可執(zhí) 行()?
A. p~ >ncxt ~q >nrxt
C. p —>next = q
B. pq ->next
D? p—>next = q
4.訛0 ?個氏世為■的響序戊?要在.第,個兀素之UU(也就是柚人無素作為新&的t
元蒙)?!?人一個兀索?網(wǎng)椎劫元泰個散為(
A> n—1
B. n-i^ 1
C n—i+l
D?i
5.一個隊刊的入隊序州站L2.LL南隊列的知出序列愜(
A. 4.3,2J
C L4.3
3、.2
K 1.2.3.4
11 3,2.1.1
6. 在一個tUKM*l為mp的燃蝕中.將一卜pIMf所桁的M點入校?應(yīng)執(zhí)
Ae top—>next*p
K p—>nrx< - top :>nrxt i lop- >nrxt p
(\ p >next*tupi 1叫尸"P
fh p >next top >nrxti top lt)p->nexi
7. n|Wr-個棚環(huán)隊州Q(JB 8幾?素為m)為滿的條fllH )?
A. Q->front - - Q -: -rear
K Q- > front I Q— >gr
(*. Q —Xronl 《Q—Arsr+1)% n\
4、
D. Q —>froni! IQ—>fr"+1〉X m
8. OR個甲p和加4中地p的子巾?求Q在p中H次出現(xiàn)的位置的算Ifc林為( )?
A.求子申 H.
C模式西ft! 口,求中長
9. -個N空廣義&的AK ).
A.不可能是障于 H.RfiB暴于取
C HIBftUK-f D?可以址于去或瞬*
10. 料中的留點散等于所礎(chǔ)點的度數(shù)如( )?
A. I B. 0
C 2 D.一1
it a m h.5/2的靖儀故皺參為( ).
A- M H. 15
c 16
12. 在一個圖G中,所有頂點的度數(shù)之和等于所有邊數(shù)之和的()倍。
A. 1/2 B. 1
C.
5、 2 D. 4
13. 對于一個具有n個頂點和e條邊的無向圖,若采用鄰接表表示,則所有頂點鄰接表中的結(jié)點總數(shù) 為()。
A. n B. e
C. 2n D. 2e
14. 有一個長度為12的有序表,按折半查找對該表進行查找,在等概率情況下查找成功的平均比較次 數(shù)為()。
A. 37/12 B. 39/12
C. 41/12 D. 35/12
15. 從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確 的位置上,此方法稱為()o
A.插入排序 B.交換排序
C.選擇排序 D.歸并排序
二、判斷題(根據(jù)敘述正確與否在其后面的括號內(nèi)打?qū)μ枴?J
6、”或打叉 號“ X ”。每小題2分,共 30分)
";?數(shù)據(jù)的邏利結(jié)構(gòu)是指作牧擋元索之間的謖輯關(guān)系,爛用戶根姑應(yīng)用需要建?立的.《
1禮牧據(jù)結(jié)構(gòu)中?元素之間存在多對多的關(guān)系稱為圖狀結(jié)構(gòu)( )
1X設(shè)” 個單向鈉占?姑點的指n城為next ■頭■■為head. p指向尾財.為T使■草 向做農(nóng)政為單向糊界晝表,可用帽句p->nexthend.( )
19.世勾 個單向糖―栽.結(jié)點的拊針域為.決指計為hmd?指供p指向&中■靖
點,若謖殂發(fā)iS式I, >nE?一hM 的站果為IK.IMp所指站戍為旭結(jié)也.《 )
2。.枚和隊列郴足牯殘的成性表.但它們對。取位置的限制小同.( )
21.
7、 枚足限定在&的倆湖迎行插入和解除操作的線作.役,乂稱為先迎先出發(fā)?( )
22. 諼舊定義的數(shù)據(jù)靖構(gòu)通常川述歸算法來尖現(xiàn)時它的旋作.《 )
23. 一個空格的小的長度是0"《 )
24. 對稀疏矩陣進行壓縮存儲,矩陣中每個非零元素對應(yīng)的三元組包括該元素的行號、列號和元素值
三項信息。()
25. 深度為k的完全二叉樹至少有2k_l個結(jié)點。()
26. 完全二叉樹中沒有度為1的結(jié)點。()
27. 圖的生成樹是惟一的。()
28. 對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。()
29. 在順序查找、折半查找、哈希表查找3種方法中,平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法
8、是
折半查找。()
30. n個元素進行冒泡法排序,通常需要進行n-1趟冒泡。()
三、綜合應(yīng)用及程序設(shè)計題(每小題5分,共25分)
31. 在下面空格處填寫-?條語句,以使下面的鏈式隊列全部元素出隊的算法完整.
int write(LinkQueue ? q)
(QueucNocie ? pi
if (q—Xront^ >rear) 隊空. /
(printf(o隊空!無元素可取”)*
rxit(O) s
)
while < q — >front —>*next ! = NULL)
| p=q —>froni —>rwxt $
q—>front—>nexi=p—>n
9、cxtt / ,出隊, <
/?祥放巳出隊結(jié)點?/
pnntf(M %4dwp~>dBta)(
frec(p):
B. q-q—>ncxt
IX pwp—>nrxi
/ ?怯空時.尖尾指向頭帽點??/
A- q ?>(rontcq->rear
C. <|->rcnr - q—Xront
32. 以I?程序R先序遍步*帆的通依的?完成程序中辛格部分(付靖村中劣. 成分JW為Mt和rinht.ttMMchu為字符微.町衍向輸點).
void Prnirdrr (ntruci HTrrrNodr ? BT)
(.((BTI NULL)
PrcorderCBT- >lelt))
10、
Preurdrr( BT— > right) <
A. pnntn"HrH>BT->|rh)
仁 print-Hc%H|->liT >riKht)
D. prmtf(-
(D將此序列川快速描序的方法.以箱 卜蛆量為棉到的_靖混分的姑果為(
(本小分)
A. 30.28t46f3Gt69.7d K 28.30.36.069.74
11、
(.2K.30.46.36.69,71 D. 30.2H.36.46.69,74
(2)用官泡法對匕述序列排序,經(jīng)過兩垣目泡的結(jié)果序列為( >.《本小題2分)
A. 36.28,3O.46.69.74
8 36.46,28.2O.69,74
C. 38.36.30.46.69.74
以 28?36?30,46,69,74
⑴從空.:乂列開始逐個抽人嫉數(shù)出序外躲形成二又拷序樹?苗希0!高成最小.應(yīng)徵逸抒
的序列站( ).(本小H3分)
A. 45.2L63.I2.37.96.3O
K 87.24J幻30,53.45.96
Q I2.2L30.37.45.53
12、.96
D. M.24.I2.37.15.96.53
⑵用槌糧地址序列內(nèi)迎哈希&?哈希函數(shù)為H(kry) key mod 13.JM散列地
址為】的飼中4( >個k!戒■(本小M2分)
試題答案及評分標準:
-.*amwn(a小島:分.共i分)
1.1>
3. A
3. B
6. C
l:k II
2L X
2:t <
25- X
10. A
ILA
二.判■(小???分,共:“)分)
20-V
2H-7
三.嫌合應(yīng)用fif Jifti+B(W小18分.共二分)
3!? (\ 戒 q rvnr i( (runt
,。成 |11 1111(( n(HeBI dnln)
3L(l)lh |ft :iOe28t3tteltfe6{U74 ( A 小 5 分)
<2>A>成:懷.即<木小H2分)
3fia (|)H.戒 37.:l .I2.M.5L iSeDA ( “小曲:l 分)
⑵&威I (木小的2分)