數(shù)據(jù)結(jié)構(gòu)試卷A

-.z.專業(yè)班級(jí)：姓名：**：專業(yè)班級(jí)：姓名：**：…………密………………封………………線…………專業(yè)班級(jí)：姓名：**：…………密專業(yè)班級(jí)：姓名：**：…………密………………封………………線…………考試方式：閉卷本試卷考試分?jǐn)?shù)占學(xué)生總評(píng)成績(jī)的80%總分題號(hào)一二三四核分人得分復(fù)查總分總復(fù)查人得分評(píng)卷人毋小省一、單項(xiàng)選擇題〔此題的每一備選答案中，只有一個(gè)是正確的，請(qǐng)把你認(rèn)為正確的答案的題號(hào)填入題干的括號(hào)內(nèi)，每題2分，共30分〕1.假設(shè)長(zhǎng)度為n的線性表采用順序存儲(chǔ)構(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ǔ)句正確的選項(xiàng)是()(1)p→ne*t=s;s→ne*t=p;(2)s→ne*t=p→ne*t;p→ne*t=s;(3)s→ne*t=p;p→ne*t=s;(4)p→ne*t=s→ne*t;s→ne*t=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.假設(shè)由樹林轉(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的二叉樹結(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.線性表假設(shè)采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:〔〕〔1〕必須是連續(xù)的〔2〕局部地址必須是連續(xù)的〔3〕一定是不連續(xù)的〔4〕連續(xù)或不連續(xù)都可以10．下面程序段的時(shí)間復(fù)雜度為〔〕for(inti=1;i<m;i++)for(intj=1;j<n;j++)a[i][j]=i*j;(1)O(m2)(2)O(n2)(3)O(m*n)(4)O(m+n)11．當(dāng)利用大小位的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為〔〕〔1〕n-2(2)n-1(3)n(4)n+112．對(duì)線性表進(jìn)展折半搜索時(shí)，要求線性表必須〔〕〔1〕順序存儲(chǔ)〔2〕順序存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序〔3〕鏈?zhǔn)酱鎯?chǔ)〔4〕鏈?zhǔn)酱鎯?chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序13．采用線性探查法解決沖突時(shí)所產(chǎn)生的一系列后續(xù)地址〔〕〔1〕必須大于等于原散列地址〔2〕必須小于等于原散列地址〔3〕可以大于或小于但不等于原散列地址〔4〕對(duì)地址在何處沒有限制14．棧的插入和刪除操作在〔〕進(jìn)展?！?〕棧頂〔2〕棧底〔3〕任意位置〔4〕指定位置15．在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，對(duì)頭指針指向隊(duì)列的〔〕位置?！?〕前一個(gè)〔2〕后一個(gè)〔3〕當(dāng)前〔4〕后面得分評(píng)卷人毋小省二、填空題〔每空1分，共20分〕1.數(shù)據(jù)的邏輯構(gòu)造被分為___0__________，________________，_________________，________________。2.單鏈表與循環(huán)鏈表的區(qū)別是_______________________________。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è)因素分別是_____________________________，____________________，_____________________。6.對(duì)于一個(gè)具有n個(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é)果為__________________________________。10.在一個(gè)網(wǎng)絡(luò)的所有生成樹中，各邊權(quán)值之和最小的生成樹，稱為該網(wǎng)絡(luò)的______________。得分評(píng)卷人毋小省三、判斷題〔判斷以下各題是否正確，假設(shè)正確在〔〕內(nèi)打"√〞，否則"×〞。每題1分，共10分〕〔〕1.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式?！病?.順序表構(gòu)造適宜于進(jìn)展順序存取，而鏈表適宜于進(jìn)展隨機(jī)存取。〔〕3.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都是2。〔〕4.有回路的有向圖不能完成拓?fù)渑判??！病?.按先根次序遍歷森林等同于按先序法遍歷對(duì)應(yīng)的二叉樹?！病?.n〔n>1〕個(gè)頂點(diǎn)的無(wú)向連通圖最少由n-1條邊。〔〕7.有向圖的鄰接表表示中邊表中結(jié)點(diǎn)的總數(shù)與有向圖中有向邊的條數(shù)相等?！病?.一個(gè)無(wú)向圖的鄰接矩陣中各元素之和與圖中邊的條數(shù)相等。〔〕9.歸并排序要求待排序文件已局部排序?！病?0.順序檢索時(shí)數(shù)據(jù)的存儲(chǔ)方式可以是順序的，也可以是鏈接的。得分評(píng)卷人毋小省四、綜合題〔共40分〕1．*系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。(7分)2．設(shè)待排序的記錄的關(guān)鍵字序列為{12，2，16，30，10，20，18}，寫出使用鏈?zhǔn)交鶖?shù)排序每趟的結(jié)果。(6分)3、拓?fù)渑判虻慕Y(jié)果不是唯一的，對(duì)于以下圖的結(jié)點(diǎn)進(jìn)展拓?fù)渑判颍噷懗銎渲械娜我?個(gè)。(5分)VV1V3V4V6V5V7V8V9V2AA4．分別按前序、后序、對(duì)稱序列寫出以下圖二叉樹的結(jié)點(diǎn)，并轉(zhuǎn)化為樹林，分別按先根次序、后根次序列出其結(jié)點(diǎn)。(6分)IFDEABIFDEABCGH5.一組關(guān)鍵字為〔19，14，23，01，68，20，84，27，55，11，10，79〕，則按哈希函數(shù)H(key)=keyMOD13,表長(zhǎng)為13，分別用線性探查法和鏈地址法處理沖突構(gòu)造哈希表，并計(jì)算各平均查找長(zhǎng)度。(10分)6.程序填空(6分)對(duì)有序表R[0]至R[n-1]進(jìn)展二分查找，成功時(shí)返回記錄在表中的位置，失敗時(shí)返回0.Structsqlist{keytypekey;};intbinsrch(sqlistR[],keytypek)//在表R