2023學年第一學期數(shù)據(jù)結(jié)構(gòu)試題(A卷)

22023~2023學年第一學期數(shù)據(jù)構(gòu)造期末考試試題考試時間 100分鐘 考試方式 閉卷筆試一、單項選擇題：〔每題2分，共40分〕在每題給出的四個選項中，請選出一項最符合題目要求的。從規(guī)律上可以把數(shù)據(jù)構(gòu)造分為〔 〕兩大類。動態(tài)構(gòu)造、靜態(tài)構(gòu)造 B.挨次構(gòu)造、鏈式構(gòu)造C.線性構(gòu)造、非線性構(gòu)造 D.根本構(gòu)造、構(gòu)造構(gòu)造以下術(shù)語中〔 〕與數(shù)據(jù)的存儲構(gòu)造無關(guān)。棧 B.哈希表 C.線索樹 D.雙向鏈表下面的程序段的時間簡單度為〔 。for〔i=1；i<=n；i++〕for〔j=1；j<=n；j++〕x=x+1；A.O(log2n) B.O(2n) C.O(n) D.O(n2)假設(shè)長度為n的線性表承受挨次存儲構(gòu)造在其第i(1<=i<=n+1)個位置插入一個元素的算法的時間簡單度為〔 〕。A.O(0) B.O(1) C.O(n) D.O(n2)為解決計算機主機與打印機之間速度不匹配問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機輯構(gòu)造應(yīng)當是〔〕。A.棧B.隊列C.樹D.圖假設(shè)元素a，b，c，d，e，f依次進棧，允許進棧、退棧操作交替進展。但不允許連續(xù)三次進展退棧工作，則不行能得到的出棧序列是〔 〕。dcebfa B.cbdaef C.bcaefd D.afedcb假設(shè)對n階對稱矩陣A以行序為主序方式將其下三角形的元〔包括主對角線上全部元素〕依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定A矩陣中的元素aij〔i<j〕的位置k的關(guān)系為( )。A.i*(i-1)/2+j B.j*(j-1)/2+I C.i*(i+1)/2+j D.j*(j+1)/2+i在一棵度為4的樹T中假設(shè)有20個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點，10個度為1的結(jié)點，則數(shù)T的葉節(jié)點個數(shù)是〔 。A.41 B.82 C.113 D.122給定二叉樹以下圖所示設(shè)N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。假設(shè)遍歷后的結(jié)點序列為〔3，1，7，5，6，2，4〕，則其遍歷方式是〔 〕。11234567A.LRN B.NRL C.RLN D.RNL將森林轉(zhuǎn)換為對應(yīng)的二叉樹假設(shè)在二叉樹中結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點則在原來的森林中，u和v可能具有的關(guān)系是〔 〕。I.父子關(guān)系 Ⅱ.兄弟關(guān)系 Ⅲ.u的父結(jié)點與v的父結(jié)點是兄弟關(guān)系A(chǔ).只有Ⅱ B.I和Ⅱ C.I和Ⅲ D.I、Ⅱ和Ⅲ以下編碼中〔 〕不是前綴碼。A.〔00，01，10，11〕 B.〔0，10，110，111〕C.〔0，1，00，11〕 D.〔1，01，000，001〕在以下圖所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵平衡二叉樹，在平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左、右子結(jié)點保存的關(guān)鍵字分別是〔 。242413533790A.13，48 B.24，48 C.24，53 D.24，90假設(shè)無向圖G=(V.E)中含7個頂點，則保證圖G在任何狀況下都是連通的，則需要的邊數(shù)最少是〔 。A.6 B.15 C.16 D.2114G=(VE)V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}，圖G的拓撲序列是〔 。A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V715.關(guān)鍵字序列351376，9102，用折半查找法查找66與6，要將給定值與關(guān)鍵字比較的次數(shù)分別為〔 。A.6，7 B.2，3C.2，4D.3，4以下表達中，不符合m階B樹定義要求的是〔 〕。根結(jié)點最多有m棵子樹 B.全部葉結(jié)點都在同一層上C.各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列 D.葉結(jié)點之間通過指針鏈接對一組數(shù)據(jù)〔2，12，16，88，5，10〕進展排序，假設(shè)前三趟排序結(jié)果如下：〔，1，1，，1，8〕則承受的排序方法可能是〔。起泡排序B.希爾排序C.歸并排序D.基數(shù)排序以下關(guān)鍵字序列中〔 〕是堆。A.〔75,65,30,15,25,45,20,10〕 B.〔75,65,45,10,30,25,20,15〕C.〔75,45,65,10,25,30,20,15〕 D.〔75,45,65,30,15,25,20,10〕19.對關(guān)鍵字序列〔05，46，13，55，94，17，42〕進展基數(shù)排序，一趟排序后的結(jié)果是〔。A.〔05，46，13，55，94，17，42〕 B.〔05，13，17，42，46，55，94〕C.〔42，13，94，05，55，46，17〕 D.〔05，13，46，55，17，42，94〕以下排序方法中〔 〕是穩(wěn)定的排序方法。A.折半插入排序 B.直接選擇排序 C.希爾排序 D.快速排序1~3題各10分，4、5題各15分，共60分。1.99請在圖中標出各結(jié)點的值。2．設(shè)無向圖G=〔V，E〕，其中V={1，2，3，4，5}，E={〔1，2，4〕，〔2，5，5〕，〔1，3，2〕，〔2，4，4〕，〔3，4，1〕，〔4，5，3〕，〔1，5，8〕}，每條邊由一個三元組G中從頂點1到其余各點的了短路徑的求解過程。要求列出最短路徑上的頂點，并計算路徑長度。0～9，哈希函數(shù)為：H〔Key〕＝KeyMOD7，用線性探測法再散列法處理沖突，依據(jù)關(guān)鍵字序列〔16，8，15，32，24，30〕哈希造表，試答復以下問題：畫出哈希表的示意圖；假設(shè)查找關(guān)鍵字24，需要依次與哪些關(guān)鍵字進展比較？假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。地址下標地址下標關(guān)鍵字0123456789兩個升序序列長度分別為mnab素歸并成一個非遞減的序列并存放到數(shù)組c描述算法的根本設(shè)計思想；描述算法的具體實現(xiàn)步驟；依據(jù)設(shè)計思想和實現(xiàn)步驟，承受程序設(shè)計語言描述算法〔使用C或C++或JAVA語言實現(xiàn)〕，關(guān)鍵之處請給出簡要注釋。用一個帶有表頭結(jié)點的循環(huán)鏈表表示隊列結(jié)點構(gòu)造為 假設(shè)該循環(huán)鏈表只設(shè)一個尾指針rear指向隊尾元素結(jié)點〔留意不設(shè)頭指針列和出隊列算法。要求：描述算法的根本設(shè)計思想；描述算法的具體實現(xiàn)步驟；依據(jù)設(shè)計思想和實現(xiàn)步驟，承受程序設(shè)計語言描述算法〔使用C或C++或JAVA語言實現(xiàn)〕，關(guān)鍵之處請給出簡要注釋。2023~2023學年第一學期數(shù)據(jù)構(gòu)造期末考試參考答案一、單項選擇題：〔240〕1.C2．A3.D4.C5.B6.D7.B8.B9.D10.B11.C12.C13.A14.A15.B16.D17.A18.D19.C 20.A1~3題各10分，4、5題各15分，共60分。1.55194627382．假設(shè)頂點數(shù)組為{V1，V2，V3，V4，V5}，則鄰接矩陣為：∞4 2 ∞84 ∞∞452 ∞∞1∞∞4 1 ∞38 5 ∞3∞V1頂點V1i=1∞i=2∞i=3∞i=4∞i=5∞無V24{V1，V2}4{V1，V2}4{V1，V2}V32{V1，V3}V4∞3{V1，V3，V4}V58{V1，V5}8{V1，V5}6{V1，V3，V4，V5}6{V1，V3，V4，V5}VjV3V4V2V5SS{V1，V3}{V1，V3，V4}{V1，V2，V3，V4}{V1，V2，V3，V4，V5}V1為起點到頂點V24，路徑為{V1，V2}；V1為起點到頂點V32，路徑為{V1，V3}；V1為起點到頂點V43，路徑為{V1，V3，V4}；V1為起點到頂點V56，路徑為{V1，V3，V4，V5}?！?〕哈希表的示意圖:地址下標0123456789關(guān)鍵字81615322430〔2〕24，15,32,243〔3〕查找成功時的平均查找長度：ASL=〔1+1+3+1+3+5〕/6=7/3?！?〕算法的根本設(shè)計思想：順次比較a，b兩個數(shù)組的元素，將較小的一個存放到c數(shù)組中去，并取下一個元素；當一個數(shù)組搜尋到終點的時候，將另一個數(shù)組的剩余元素依次存放到c算法的具體實現(xiàn)步驟：i，j分別表示a，b0；用kc0。①當i<mj<na[ib[jc1，c1，重復①；②當i<m時，將ac③當j<n時，將bc算法的CvoidMerge(inta[],intb[],intc[],intm,intn)//{inti,j,k；for(i=0,j=0,k=0；i<m&&j<n；++k)//a，b{if(a[i]<b[j])c[k]=a[i++]；//a[ic[k]中，取aelsec[k]=b[j++]； //b[j]存放到c[k]中，取b}while〔i<m)c[k++]=a[i++]； //當b中沒有元素時while〔j<n〕c[k++]=b[j++]； //當a中沒有元素時}〔1〕算法的根本設(shè)計思想：改寫尾指針。出隊列，推斷隊列是否為空，假設(shè)不為空，則刪除循環(huán)鏈表中第一個數(shù)據(jù)元素，假設(shè)原隊列只有一個元素，刪除后要改寫尾指針。算法的具體實現(xiàn)步驟：數(shù)據(jù)構(gòu)造為單鏈表，一個數(shù)據(jù)域data，一個指針域link。初始化：生成一個結(jié)點rear，假設(shè)安排成功，rear入隊列：給元素x安排結(jié)點空間s，假設(shè)安排成功，s數(shù)據(jù)域賦值為x，s指向頭結(jié)點，ss出隊列：推斷隊列是否為空；假設(shè)不為空，h指向鏈表的頭結(jié)點，刪除hhh。算法的C#defineOK1#defineERROR0typedefintStatus；typedefstrucNode{intdata；strucNode*link；}QNode,*QLink；StatusInitQueue(QLink&rear)//函數(shù)首部，初始化成功返回OK，否則返回ERROR{rear=〔QLink〕malloc〔sizeof〔QNode〕；//安排頭結(jié)點空間if〔rea〕retur〔ERRO； //動態(tài)存儲安排失敗，返回rear->link=rear； //循環(huán)鏈表retur〔O；}StatusEnQueue(QLink&rear,intx)//OKERROR{QLinks；s=〔QLink〕malloc〔sizeof〔QNode〕； //給xif〔sretur〔ERRO； //動態(tài)存儲安排失敗，返回ERRORs->data=x； //結(jié)點的數(shù)據(jù)域為xs->link=rear->link； //結(jié)點的指針域指向頭結(jié)點rear->link=s； //將結(jié)點連到鏈表尾部rear=s； //sretu