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

-.z.專業(yè)班級：姓名：**：專業(yè)班級：姓名：**：…………密………………封………………線…………專業(yè)班級：姓名：**：…………密專業(yè)班級：姓名：**：…………密………………封………………線…………考試方式：閉卷本試卷考試分數(shù)占學生總評成績的80%總分題號一二三四核分人得分復查總分總復查人得分評卷人毋小省一、單項選擇題〔此題的每一備選答案中，只有一個是正確的，請把你認為正確的答案的題號填入題干的括號內(nèi)，每題2分，共30分〕1.假設(shè)長度為n的線性表采用順序存儲構(gòu)造，在其第i個位置插入一個新元素的算法的時間復雜度為()。(1≤i≤n+1)

(1)O(0)(2)O(1)(3)O(n)(4)O(n2)2.在單鏈表中p所指結(jié)點后插入s所指結(jié)點,則以下語句正確的選項是()(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è)一個棧的輸入序列為A，B，C，D，則借助一個棧所得到的輸出序列不可能是()

〔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é)點無右子樹的二叉樹〔2〕根結(jié)點無左子樹的二叉樹〔3〕根結(jié)點可能有左二叉樹和右二叉樹〔4〕根結(jié)點只有一個孩子結(jié)點的二叉樹5．設(shè)二叉樹的根為第一層，則深度為i的二叉樹結(jié)點數(shù)最多為〔〕〔1〕２i 〔2〕２i+1〔3〕２i-１ 〔4〕２i-16.首先訪問結(jié)點的左子樹，然后訪問該結(jié)點，最后訪問結(jié)點的右子樹，這種遍歷稱為()〔1〕前序遍歷〔2〕后序遍歷〔3〕中序遍歷〔4〕層次遍歷7．給定以下有向圖，從頂點1出發(fā)，其廣度優(yōu)先搜索序列為〔〕〔1〕12534〔2〕12435〔3〕14325〔4〕123458．散列表中的沖突是指〔〕〔1〕兩個元素具有一樣的序號〔2〕兩個元素的關(guān)鍵字一樣，而其他屬性一樣〔3〕不同的關(guān)鍵字對應一樣的存儲地址〔4〕數(shù)據(jù)元素的地址一樣9.線性表假設(shè)采用鏈式存儲構(gòu)造時，要求內(nèi)存中可用存儲單元的地址:〔〕〔1〕必須是連續(xù)的〔2〕局部地址必須是連續(xù)的〔3〕一定是不連續(xù)的〔4〕連續(xù)或不連續(xù)都可以10．下面程序段的時間復雜度為〔〕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．當利用大小位的數(shù)組順序存儲一個隊列時，該隊列的最大長度為〔〕〔1〕n-2(2)n-1(3)n(4)n+112．對線性表進展折半搜索時，要求線性表必須〔〕〔1〕順序存儲〔2〕順序存儲且結(jié)點按關(guān)鍵字有序〔3〕鏈式存儲〔4〕鏈式存儲且結(jié)點按關(guān)鍵字有序13．采用線性探查法解決沖突時所產(chǎn)生的一系列后續(xù)地址〔〕〔1〕必須大于等于原散列地址〔2〕必須小于等于原散列地址〔3〕可以大于或小于但不等于原散列地址〔4〕對地址在何處沒有限制14．棧的插入和刪除操作在〔〕進展?！?〕棧頂〔2〕棧底〔3〕任意位置〔4〕指定位置15．在一個順序存儲的循環(huán)隊列中，對頭指針指向隊列的〔〕位置。〔1〕前一個〔2〕后一個〔3〕當前〔4〕后面得分評卷人毋小省二、填空題〔每空1分，共20分〕1.數(shù)據(jù)的邏輯構(gòu)造被分為___0__________，________________，_________________，________________。2.單鏈表與循環(huán)鏈表的區(qū)別是_______________________________。3.在一個循環(huán)隊列中，判斷對空的條件是串是____________________，判斷對滿的條件是串是_______________________________4.從有序表〔12，18，30，43，56，78，82，95〕中一次折半搜索43和56元素是，其比擬次數(shù)分別為_______和_______。5.與哈西表的平均查找長度有關(guān)的三個因素分別是_____________________________，____________________，_____________________。6.對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)個邊數(shù)分別為_________和__________。7.在二叉排序樹中，左子樹所有結(jié)點的關(guān)鍵字值都________該結(jié)點的關(guān)鍵碼值，而右子樹中所有結(jié)點的關(guān)鍵字值都_________該結(jié)點的關(guān)鍵碼值。8.在一個小頂堆中，堆頂元素的值是所有結(jié)點中的______________，在一個大頂堆中，堆頂元素的值是所有結(jié)點中的______________。9.假定一組紀錄的關(guān)鍵字為〔46，79，56，38，40，80〕，對其進展快速排序的一次劃分的結(jié)果為__________________________________。10.在一個網(wǎng)絡(luò)的所有生成樹中，各邊權(quán)值之和最小的生成樹，稱為該網(wǎng)絡(luò)的______________。得分評卷人毋小省三、判斷題〔判斷以下各題是否正確，假設(shè)正確在〔〕內(nèi)打"√〞，否則"×〞。每題1分，共10分〕〔〕1.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式?！病?.順序表構(gòu)造適宜于進展順序存取，而鏈表適宜于進展隨機存取。〔〕3.二叉樹中任何一個結(jié)點的度都是2。〔〕4.有回路的有向圖不能完成拓撲排序。〔〕5.按先根次序遍歷森林等同于按先序法遍歷對應的二叉樹。〔〕6.n〔n>1〕個頂點的無向連通圖最少由n-1條邊。〔〕7.有向圖的鄰接表表示中邊表中結(jié)點的總數(shù)與有向圖中有向邊的條數(shù)相等。〔〕8.一個無向圖的鄰接矩陣中各元素之和與圖中邊的條數(shù)相等。〔〕9.歸并排序要求待排序文件已局部排序?！病?0.順序檢索時數(shù)據(jù)的存儲方式可以是順序的，也可以是鏈接的。得分評卷人毋小省四、綜合題〔共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è)計哈夫曼編碼。(7分)2．設(shè)待排序的記錄的關(guān)鍵字序列為{12，2，16，30，10，20，18}，寫出使用鏈式基數(shù)排序每趟的結(jié)果。(6分)3、拓撲排序的結(jié)果不是唯一的，對于以下圖的結(jié)點進展拓撲排序，試寫出其中的任意5個。(5分)VV1V3V4V6V5V7V8V9V2AA4．分別按前序、后序、對稱序列寫出以下圖二叉樹的結(jié)點，并轉(zhuǎn)化為樹林，分別按先根次序、后根次序列出其結(jié)點。(6分)IFDEABIFDEABCGH5.一組關(guān)鍵字為〔19，14，23，01，68，20，84，27，55，11，10，79〕，則按哈希函數(shù)H(key)=keyMOD13,表長為13，分別用線性探查法和鏈地址法處理沖突構(gòu)造哈希表，并計算各平均查找長度。(10分)6.程序填空(6分)對有序表R[0]至R[n-1]進展二分查找，成功時返回記錄在表中的位置，失敗時返回0.Structsqlist{keytypekey;};intbinsrch(sqlistR[],keytypek)//在表R