數(shù)據(jù)結(jié)構(gòu)期末試題及答案

E卷一、單項(xiàng)選擇題1、線性表若采用鏈?zhǔn)浇Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址()。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以2、判定一個(gè)棧ST(最多元素為m0)為空的條件是()。A.ST->top!=0B.ST->top==0C.ST->top!=m0D.ST->top==m03、數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列j下標(biāo)從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為()。A.SA+141B.SA+144C.SA+222D.SA+2254、設(shè)哈希表長m=14，哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是()。A.8B.3C.5D.95、在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是()。A.t->left==NULLB.t->ltag==1C.t->ltag==1且t->left==NULLD.以上都不對(duì)6、將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用()。A.棧B.隊(duì)列C.鏈表D.樹7、有一個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，()次比較后查找成功。A.1B.2C.4D.88、對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則()。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-19、如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用_____查找方法。A.分塊B.順序C.二分D.散列10、快速排序方法在()情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個(gè)相同值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)11、在含有n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為________.A.eB.2eC.-eD.-2e12.假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)相關(guān)的所有弧的時(shí)間復(fù)雜度是_________.A.O(n)B.O(e)C.O(n+e)D.O(n*e)13.用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是_________.A.選擇排序B.希爾排序C.歸并排序D.快速排序14.適宜于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是_____.A.有序表B.分塊有序表C.三叉排序表D.線性鏈表15.不定長文件是指__________.A.文件的長度不固定B.記錄的長度不固定C.字段的長度不固定D.關(guān)鍵字項(xiàng)的長度不固定二、填空題16、對(duì)數(shù)據(jù)間關(guān)系的描述是數(shù)據(jù)的邏輯結(jié)構(gòu)，形式地可以用一個(gè)二元組B=（D，R）來表示，其中D表示________；R表示___________。17、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)一有兩種，分為_______和________.18、評(píng)價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)，基本來說有兩條，一條是_______，二是_______。19、棧的類型說明為：typedefstrucstack{datatypes(maxlen);intlen;}stack;則：POP（stackst）;算法是：ifst.len=0printf(“underflow”)else__________;20、二叉樹的第i層上至多有______結(jié)點(diǎn)，深度為k的二叉樹至多有________結(jié)點(diǎn)。21、圖的遍歷主要有________和_________兩種.22、在hq的鏈隊(duì)中，判定只有一個(gè)結(jié)點(diǎn)的條件是____________。23、在散列函數(shù)H(key)=key%p中，p應(yīng)取_________。24、對(duì)于長度為n的線性表，若采用二分法查找，則時(shí)間復(fù)雜度為_____；若采用分塊查找(假定總塊數(shù)和每塊長度均接近n的平方根)，則時(shí)間復(fù)雜度為_________。三、解答操作題（每小題5分，共20分）25、已知一個(gè)無向圖的頂點(diǎn)集為{a,b,c,d,e},其鄰接矩陣如下所示：（1）畫出該圖的圖形。（2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，并寫出遍歷序列。26、把下列二叉樹換成二森林，畫出圖形27、已知一個(gè)散列表如下表示：35203348590123456789101112其散列函數(shù)h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為：=(h(key))+i*h(key)%mi=0,1,…,m-1其中h(key)=key%11+1回答以下問題：（1）對(duì)表中關(guān)鍵字35，20，33和48進(jìn)行查找時(shí)，所需要進(jìn)行的比較次數(shù)各為多少？（2）該散列表在等概率查找時(shí)查找成功的平均查找長度為多少？28、已知序列{17,18,60,40,7,32,73,65,85},請(qǐng)給出采用起泡排序法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。四、算法閱讀題(每小題6分，共12分)29、面給出了起泡排序算法，請(qǐng)?zhí)顚懰惴ㄖ械目湛?，使算法正確。structnode{intkey;

datatypeinfo;}node,*lnode；

inti，j;intflag;nodeX;nodeR[n];①[每循環(huán)一次作一次起泡]循環(huán)i以1為步長，從1到n－1，執(zhí)行下列語句(1)()(2)循環(huán)j以1為步長，()，執(zhí)行若()＜R[j].key則flag←1；X←R[j]；()；R[j＋1]←X(3)若()則跳出循環(huán)②算法結(jié)束30、下面給出了在對(duì)稱序穿線樹中找指定結(jié)點(diǎn)在后序下的前驅(qū)算法，請(qǐng)?zhí)顚懰惴ㄖ械目湛?，使算法正確。structnode{datatypeinfo;node*llink，*rlink;}*lnode；lnodep;[p指向指定結(jié)點(diǎn)]lnodeq;[q指向指定結(jié)點(diǎn)在后序下的前驅(qū)]①若p->rlink＞0則()，算法結(jié)束否則q←p②(1)循環(huán)當(dāng)()時(shí)，反復(fù)執(zhí)行()(2)()③算法結(jié)束五、算法設(shè)計(jì)題（共8分）31.設(shè)有一個(gè)循環(huán)雙鏈表，其中有一結(jié)點(diǎn)的指針為p,編寫一個(gè)函數(shù)p與其右邊的一個(gè)結(jié)點(diǎn)進(jìn)行交換。結(jié)點(diǎn)結(jié)構(gòu)為E卷一、單項(xiàng)選擇題1.D2.B3.C4.D5.B6.A7.C8.D9.A10.C11.D12.C13.D14.C15.B二、填空題16．?dāng)?shù)據(jù)集合數(shù)據(jù)間的關(guān)系17．順序非順序18．時(shí)間復(fù)雜度空間復(fù)雜度19．st.len=st.len-120．2i-12k-121．深度廣度22．hq->front=hq->rear23．素?cái)?shù)24．O(log2n)O(n)三、解答操作題（每小題5分，共20分）25、深度優(yōu)先遍歷序列為：abdce;廣度優(yōu)先遍歷序列為：abedc26、27、答：（1）比較次數(shù)分別為3、2、1、1。（2）平均查找長度ASL=(3+2+1+1+2)/5=1.828、初始：17，18，60，40，7，32，73，65，85第1趟：17，18，40，7，32，60，65，73，85第2趟：17，18，7，32，40，60，65，73，85第3趟：17，7，18，32，40，60，65，73，85第4趟：7，17，18，32，40，60，65，73，85第5趟：7，17，18，32，40，60，65，73，85四、算法閱讀題（每小題6分，共12分）29．(1)flag=0；(2)1到n-1；(3)R[j＋1].key；(4)R[j]=R[j＋1]；(5)flag＝030．q=p->.rlinkq->link＜0q=(－1)*(q->llink)q=q->.llink五、算法設(shè)計(jì)題（共8分）參考答案voidswap(dnode*p){