1、黃石理工學(xué)院2009 一 2010學(xué)年度(第一學(xué)期)2008級(jí) 計(jì)算機(jī)應(yīng)用、網(wǎng)絡(luò)、信息、科教號(hào)業(yè)數(shù)據(jù)結(jié)構(gòu)專(zhuān)科 期末試卷(C)* *班級(jí)：*學(xué)號(hào)：*姓名：*個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)考試方 式閉卷制卷份數(shù)式V題號(hào)一二三四五總分得分核分人一、單項(xiàng)選擇題(本大題共10小題，每小題3分，共30分)得分閱卷人1.研究數(shù)據(jù)結(jié)構(gòu)就是研究()A.B.C.D.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其數(shù)據(jù)在運(yùn)算上的實(shí)現(xiàn) 下列程序的時(shí)間復(fù)雜度為()for(i=0;im;i+) for(j=0;jdata=x; ; q- next =p;無(wú)論對(duì)順序存儲(chǔ)還是鏈接存儲(chǔ)的棧和隊(duì)列來(lái)說(shuō)，

2、進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為隊(duì)列結(jié)構(gòu)允許進(jìn)行刪除操作的一端稱(chēng)隊(duì)列的對(duì)于一個(gè)二維數(shù)組Amn,若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素Aij相對(duì)于A11的地址為 可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)對(duì)線性表用二分法查找時(shí)要求線性表必須8.對(duì)一組整數(shù)60，40，90，20，10，70，50，80進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)整數(shù)50插入到有序表中時(shí)，為尋找插入位置需比 次。9.一棵深度為k的滿二叉樹(shù)的葉子有 個(gè)。結(jié)點(diǎn)，另一個(gè)指向D. i)B. 一定是不連續(xù)的D.連續(xù)與否均可以得分閱卷人三、判斷題(本大題共10小題，每題1分，共10分)B.都是先進(jìn)先出D.沒(méi)有共同點(diǎn)1.(2.(后序遍歷 D.層次遍歷

3、則查找每個(gè)元素的平均比較次數(shù)為()D. (n-1)/23.(4.(5.(6.(7.(8.(9.(10.()數(shù)組通常具有的兩種基本操作是插入與刪除。)空串是由空白字符組成的串。)在鏈表中，邏輯上相鄰的數(shù)據(jù)元素，其物理存儲(chǔ)位置一定緊鄰。)鏈?zhǔn)酱鎯?chǔ)的棧與順序存儲(chǔ)的棧是兩種不同的數(shù)據(jù)結(jié)構(gòu)。)在無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和是所有邊數(shù)的2倍。一棵滿二叉樹(shù)一定是完全二叉樹(shù)。圖是一種結(jié)點(diǎn)之間無(wú)層次關(guān)系的線性結(jié)構(gòu)。順序隊(duì)和循環(huán)隊(duì)的隊(duì)空和隊(duì)滿判斷條件一樣。在棧中插入或刪除一個(gè)數(shù)據(jù)元素應(yīng)遵守后進(jìn)先出的原則。)希爾排序法是一種不穩(wěn)定的排序方法。個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)得分閱卷人個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)

4、個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)班級(jí):個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)學(xué)號(hào):個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)姓名:個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)

5、個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)黃石理工學(xué)院2009 2010學(xué)年度（第一學(xué)期）2008級(jí)計(jì)算機(jī)應(yīng)用、網(wǎng)絡(luò)、信息、科教專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)專(zhuān)科期末試卷（C）四、解答題（本大題共5小題，每題6分，共30分）1.在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)任一結(jié)點(diǎn)?2.設(shè)循環(huán)隊(duì)列的容量為30 （序號(hào)從0到29），現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)操作后，有 front=11，rear=19front=19，rear=11；問(wèn)在這兩種情況下，循環(huán)隊(duì)列的長(zhǎng)度各是多 少？3.設(shè)某密碼電文由6個(gè)字母A,B, C, D, E組成，每個(gè)字母在電文中的出現(xiàn)頻率分別是 0.12，0.4，0.15，0.08，0.25，試為這6個(gè)字母設(shè)計(jì)相應(yīng)的哈夫曼編碼。4.畫(huà)出下列網(wǎng)絡(luò)的最小生成樹(shù)l