2005-2006學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)a卷含答案

《2005-2006學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)a卷含答案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、專業(yè)班級(jí)：姓名：學(xué)號(hào)：…………………………密………………………………封………………………………線…………………………黃淮學(xué)院2005-2006學(xué)年第2學(xué)期期末考試《數(shù)據(jù)結(jié)構(gòu)》（計(jì)算機(jī)科學(xué)系）A卷題號(hào)一二三四總分核分人得分得分評(píng)卷人一、單選題（本題的每一備選答案中，只有一個(gè)是正確的，請(qǐng)把你認(rèn)為正確的答案的題號(hào)填入題干的括號(hào)內(nèi)，每小題2分，共30分）1.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為()。(1≤i≤n+1)(1)O(0)(2)O(1)(3)O(n)(4)O(n2)2.在單鏈表中p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn),則下列語(yǔ)句正確的是

2、()(1)p→next=s;s→next=p;(2)s→next=p→next;p→next=s;(3)s→next=p;p→next=s;(4)p→next=s→next;s→next=p;3.設(shè)一個(gè)棧的輸入序列為A，B，C，D，則借助一個(gè)棧所得到的輸出序列不可能是()（1）A，B，C，D（2）D，C，B，A（3）A，C，D，B（4）D，A，B，C4.若由樹林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是（）（1）根結(jié)點(diǎn)無(wú)右子樹的二叉樹（2）根結(jié)點(diǎn)無(wú)左子樹的二叉樹（3）根結(jié)點(diǎn)可能有左二叉樹和右二叉樹（4）根結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)的二叉樹5．設(shè)二叉樹的根為第一層，則深度為i

3、的二叉樹結(jié)點(diǎn)數(shù)最多為（）（1）２i（2）２i+1（3）２i-１（4）２i-16.首先訪問結(jié)點(diǎn)的左子樹，然后訪問該結(jié)點(diǎn)，最后訪問結(jié)點(diǎn)的右子樹，這種遍歷稱為(　　　)（1）前序遍歷（2）后序遍歷（3）中序遍歷（4）層次遍歷7．給定下列有向圖，從頂點(diǎn)1出發(fā)，其廣度優(yōu)先搜索序列為（）（1）12534（2）12435（3）14325（4）123458．散列表中的沖突是指（）（1）??兩個(gè)元素具有相同的序號(hào)（2）兩個(gè)元素的關(guān)鍵字相同，而其他屬性相同（3）不同的關(guān)鍵字對(duì)應(yīng)相同的存儲(chǔ)地址（4）數(shù)據(jù)元素的地址相同9.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:（）（1）必須是

4、連續(xù)的（2）部分地址必須是連續(xù)的（3）一定是不連續(xù)的（4）連續(xù)或不連續(xù)都可以10．下面程序段的時(shí)間復(fù)雜度為（）for(inti=1;i

5、址（）（1）必須大于等于原散列地址（2）必須小于等于原散列地址（3）可以大于或小于但不等于原散列地址（4）對(duì)地址在何處沒有限制14．棧的插入和刪除操作在（）進(jìn)行。（1）棧頂（2）棧底（3）任意位置（4）指定位置15．在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，對(duì)頭指針指向隊(duì)列的（）位置。（1）前一個(gè)（2）后一個(gè)（3）當(dāng)前（4）后面得分評(píng)卷人二、填空題（每空1分，共20分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_____________，________________，_________________，________________。2.單鏈表與循環(huán)鏈表的區(qū)別是__________________

6、_____________。3.在一個(gè)循環(huán)隊(duì)列中，判斷對(duì)空的條件是串是____________________，判斷對(duì)滿的條件是串是_______________________________4.從有序表（12，18，30，43，56，78，82，95）中一次折半搜索43和56元素是，其比較次數(shù)分別為_______和_______。5.與哈西表的平均查找長(zhǎng)度有關(guān)的三個(gè)因素分別是_____________________________，____________________，_____________________?！稊?shù)據(jù)結(jié)構(gòu)》試卷第3頁(yè)（共3頁(yè)）6.對(duì)于一個(gè)具有n

7、個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)個(gè)邊數(shù)分別為_________和__________。7.在二叉排序樹中，左子樹所有結(jié)點(diǎn)的關(guān)鍵字值都________該結(jié)點(diǎn)的關(guān)鍵碼值，而右子樹中所有結(jié)點(diǎn)的關(guān)鍵字值都_________該結(jié)點(diǎn)的關(guān)鍵碼值。8.在一個(gè)小頂堆中，堆頂元素的值是所有結(jié)點(diǎn)中的______________，在一個(gè)大頂堆中，堆頂元素的值是所有結(jié)點(diǎn)中的______________。9.假定一組紀(jì)錄的關(guān)鍵字為（46，79，56，38，40，80），對(duì)其進(jìn)行快速排序的一次劃分的結(jié)果為_____________________