數(shù)據(jù)結(jié)構(gòu)(同名4772)

1、數(shù)據(jù)結(jié)構(gòu)一、單項(xiàng)選擇題1 數(shù)據(jù)的最小單位是_A_。A 數(shù)據(jù)元素 B.記錄 C.數(shù)據(jù)對(duì)象 D.數(shù)據(jù)項(xiàng)2. 對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)和e條邊的無向圖，若采用鄰接表表 示，所有邊鏈表中邊結(jié)點(diǎn)的總數(shù)為 _C_。A. e/2 B.e C.2eD.n+e3. 數(shù)組a1.6,1.5 (無0行0列)以列序?yàn)橹餍蝽樞虼鎯?chǔ)，a11的地址為1000,每個(gè)元素占2個(gè)存儲(chǔ)單元，則a34的地址是A 0A.1026B.1040C.1042D.10464. 某線性表常發(fā)生的操作為刪除第一個(gè)數(shù)據(jù)元素和在最后一個(gè) 元素后添加新元素，采用 _D_的存儲(chǔ)結(jié)構(gòu)，能使其存儲(chǔ)效率 和時(shí)間效率最咼。A 單鏈表B 僅用頭指針的循環(huán)鏈表C.雙向循環(huán)

2、鏈表D 僅用尾指針的循環(huán)鏈表5. 在一個(gè)單鏈表中，已知q所指向的結(jié)點(diǎn)是p指向的結(jié)點(diǎn)的直接 前驅(qū)結(jié)點(diǎn)，若在q所指向的結(jié)點(diǎn)和p指向的結(jié)點(diǎn)間插入s所指 向的結(jié)點(diǎn)，則執(zhí)行 C _ _ 0A. s-n ext=p-n ext; p-n ext=s;B. p-n ext=s-n ext; s-n ext=p;C. q-n ext=s; s-n ext=p;D. p-n ext=s; s-n ext=q;6. 若循環(huán)隊(duì)列使用C數(shù)組Am存放其數(shù)據(jù)元素，已知頭指針front指向隊(duì)首元素，尾指針rear指向尾元素后的空單元，則 當(dāng)前隊(duì)列中的元素個(gè)數(shù)為_A_oA.(rear-fro nt+m)%mB. rear-f

3、r on t+1C. rear-fr ontD. rear-fr on t-17. 棧和隊(duì)列的共同點(diǎn)是C oA.先進(jìn)先出B.后進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.運(yùn)算受限的線性表8. 一棵深度為5的完全二叉樹，葉結(jié)點(diǎn)數(shù)最大值和最小值分別為_B_。A. 10，5 B. 16，8 C. 8，4 D. 32，169. 折半查找有序表(5,15,25,35,40,65,70,75,80,85,88,90), 若 查找元素75,需依次與表中元素 _A_進(jìn)行比較，。A.65,80,70,75 B.65,85,75 C.65,80,75D.70,85,7510. 算法suanfa的時(shí)間復(fù)雜度為_A_。

4、int sua nfa(i nt n) int i=1；while(pow(2,i)=n) /* pow(2,i)表示 2 */i=i+1；return i ；A.O(log n) B.O( .5) C.O(n2)D.O( n)二、簡(jiǎn)答題1. 簡(jiǎn)敘深度優(yōu)先遍歷算法與廣度優(yōu)先遍歷算法的區(qū)別，當(dāng)采用廣 度優(yōu)先遍歷時(shí)，如何記錄已被訪問的頂點(diǎn)？答：區(qū)別：可以看到兩種方法最大的區(qū)別在于前者從頂點(diǎn)的第一 個(gè)鄰接點(diǎn)一直訪問下去再訪問頂點(diǎn)的第二個(gè)鄰接點(diǎn)；后者從頂點(diǎn) 開始訪問該頂點(diǎn)的所有鄰接點(diǎn)再依次向下，一層一層的訪問?？梢杂藐?duì)列來儲(chǔ)存那些沒有訪問或者剛訪問過的結(jié)點(diǎn)，對(duì)每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)訪問標(biāo)志位。2. 設(shè)文件R共有1500條記錄，磁盤的讀、寫單位為 250條記錄， 內(nèi)存可提供750條記錄的空間，試簡(jiǎn)要說明對(duì)文件R的排序過程。答：第一步，每次將三個(gè)記錄塊即750個(gè)記錄有外存讀到內(nèi)存， 進(jìn)行內(nèi)