【正文】 儲起始地址與當(dāng)A按列優(yōu)先存儲的起始地址相同。（）[A] 1[B] 2[C] 1/2[D] 不一定7．遞歸函數(shù)F(n)=F(n1)+n+1(n1)的遞歸體是_______。()[A] K1[B] K[C] K+1[D] K（K+1）/22二、填空題（每小題2分，共20分）1．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為______，在表尾插入元素的時間復(fù)雜度為________。，要連通所有頂點則至少需要_________條邊。9．快速排序在平均情況下的空間復(fù)雜度為_____，在最壞情況下的空間復(fù)雜度為_____。（），只要知道該元素的指針即可，因此單鏈表是隨機存取的存儲結(jié)構(gòu)。（），所以二叉樹是一種特殊的樹。（）四、簡答題（每題10分，共60分）1．說明數(shù)組和鏈表的區(qū)別，各有何優(yōu)缺點？2．回答下列關(guān)于堆的一些問題：（1）堆的定義是什么？（2）存儲表示是順序的，還是鏈?zhǔn)降?？?）設(shè)有一個最小堆，其具有最小值、最大值的元素分別可能在什么地方？3．完全二叉樹用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)最合適，為什么？、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排 序和歸并排序中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現(xiàn)？5．用下列三種表示法畫出下圖G的存儲結(jié)構(gòu)（1）相鄰矩陣（2）鄰接表（3）鄰接多重表6．已知序列（70，83，100，65，10，32，7），請給出采用插入排序法對該序列作升序排序時的每一趟結(jié)果。數(shù)據(jù)結(jié)構(gòu)試題6答案一、 二、1．O（n）O（1）2．163．2 h 一 h 一14．最小值 最大值5．n一16．O（n 2）O（n十e）、7．順序 有序8．開放定址法 鏈接法（次序無先后）9．O（1og2n）O（n）10．9三、2.√ 5.√8.√四、1．區(qū)別：數(shù)組占用連續(xù)的內(nèi)存空間，鏈表不要求結(jié)點的空間連續(xù)。（3）最小堆的最小值元素必在堆頂，最大值的元素只有在葉結(jié)點上。，只有直接插入排序、冒泡排序、直接選擇排序易于在鏈表上實現(xiàn)。（） G 的拓?fù)湫蛄形ㄒ唬瑒t其弧數(shù)必為 n1(其中 n為 G 的頂點數(shù))。（） 樹的任何子樹都是 AVL樹。2．若按層次順序?qū)⒁豢糜衝個結(jié)點的完全二叉樹的所有結(jié)點從1到n編號，那么當(dāng)i為_____且大于 1時，結(jié)點I 的左兄弟是結(jié)點___ _，否則結(jié)點 i 沒有左兄弟。6．在一個帶頭結(jié)點的單循環(huán)鏈表中，p 指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針 head可用 p 表示為 head=_______。（圖1）（圖2）2．將上圖 2所示的二叉樹轉(zhuǎn)換為樹或樹林（畫出連線刪線圖和結(jié)果圖）。5．從一棵空的 AVL 樹開始，將關(guān)鍵碼 xal,wan,wil,zol,yo,xum 逐個插入，畫出每插入一 個關(guān)鍵碼后得到的 AVL 樹。flag:0..1。FOR i:=1 TO n DO Begin flag:=0。Info :datatype END。BEGINLow:=1。END。數(shù)據(jù)結(jié)構(gòu)試題8答案一、ADBCBADCBB1B1B1B1A1A二、初等，組合存儲密度散列函數(shù)的選取，沖突（碰撞）的解決樹（森）林按關(guān)鍵碼排序 1/2Σdi生成樹林相對位置三、B C EB CA B C D四、快速排序是不穩(wěn)定的如對初始類排序碼：81 2 5 82 4 1經(jīng)第一趟快排后為：〔1 2 5 82 4〕81經(jīng)第二趟快排后為： 1 〔2 5 82 4〕81經(jīng)第三趟快排后為： 1 2 〔5 82 4〕81經(jīng)第四趟快排后為： 1 2 4 5 8281和 82 相對位置發(fā)生了變化由于有了線索的存在而使的周游樹形結(jié)構(gòu)和找結(jié)點在指定次序下的前驅(qū)、后繼的算法變得很簡單、直截了當(dāng)。X:node。R〔j〕← R〔j1〕。t↑.rchild←q。數(shù)據(jù)結(jié)構(gòu)試題9 (每小題 1 分,15 分):（） 個要素 個要素 個要素 個要素,刪除節(jié)點 P之后的節(jié)點 Q 需要修改的指針域的個數(shù)為:（） :（） 表 SUBSTR(‘ABCDEF’,2,3)的引用結(jié)果是:（）A． ‘BCD’ B.‘BC’ C.‘CDE’ D.‘CD’ SQ有 m 個單元,其滿隊條件是:（）= MOD M+1= +1= = MOD M+1 A 4 * 4 的上三角元素 A(3,2)的位置是第:（） 個 個 個 個 D=(a,D)的深度為:（）C.+D.– A,B,C 可以構(gòu)成多少種二叉樹:（） n 個節(jié)點的完全二叉樹,其深度為:（）:（） n 個結(jié)點,e 條邊,則它的鄰接表需要表節(jié)點數(shù)目為:（）+1(KRUSKAL)算法求最小生成樹,是針對那種圖的:（） ,使用輔助空間為 O（n）的算法是:（） ,同義詞是指:（）≠ 且 HASH()=HASH()== 且 HASH()=HASH()= 文件屬于:（） (錯選,多選, 1 分,共 5 分),涉及到棧運算的有:（） ,算法的時間復(fù)雜度是 O(n 2)的有:（） :（） ,可以將排序分為:() :（） (每空1 分,共10 分),________,_________, : :(對的打”√”,錯的打”╳”, 2 分,判斷和說明各得 1 分,判斷3 錯誤, 10分) 2 的樹.（）,其時間復(fù)雜度為 O(n log 2 n).（）,限制在于節(jié)點的位置相對固定.（）.（）,則一般唯一.（）(每小題 3 分,共 9 分) (共 31分),并畫出主要轉(zhuǎn)化過程圖示.(4 分) W={2,3,4,7,8},試構(gòu)造關(guān)于 W 的一棵哈夫曼樹,并求其加權(quán)路徑長度 WPL 的 值.(6 分),并從頂點 1 出發(fā)依據(jù)存儲結(jié)構(gòu)進(jìn)行廣度遍歷, ABCDEF,中序序列為 BCAEDF,畫出此二叉樹的示意圖,并給 出其后序序列的線索樹.(6 分){51,28,36,86,7},請建立一個堆,要求畫出堆形成的示意圖.(6 分),現(xiàn)在要在節(jié)點P之后插入一個節(jié)點Q,請寫出插入動作的具體語句.(4分)（共20 分） A[1..m]作為循環(huán)隊列的存儲區(qū)域,試編寫一個出隊的類 PASCAL 語言算法.(6 分)2．利用類 pascal 語言寫出統(tǒng)計二叉樹中節(jié)點個數(shù)的算法（6 分）.3．利用類 pascal 語言寫出快速排序中一趟塊排的算法（8 分）.數(shù)據(jù)結(jié)構(gòu)試題9答案一、CBDADBCDAD1A1D1B1A1C二、A C DA BA C D ED EB C三、順序,鏈接,索引,散列相對位置指令必須有確切含義,無歧義性開地址法,拉鏈法修改,檢索四、√五、三元組表 P244拓?fù)渑判?P229AVL樹 P180六、鄰接表存儲表示同 A 卷六、2 廣度遍歷結(jié)果:1, 2, 6, 3, 4, 7, 8, 5后序:C B E F D A q↑.llink←pq↑.rlink←p↑.rlink p↑.rlink↑.llink←q p↑.rlink←q七、算法設(shè)計(6+6+8=20′)R=Fthenprint(‘underflow’)elseF←F MOD m+1算法結(jié)束TYPEpointer=↑nodenode=RECORD info: datatype。VAR count: integer)。TYPE node=RECORD Key: integer。j:0..n。begini:=l。if i＜j thenR〔j〕:=R〔j〕。j:=j1〕 until i=j R〔i〕:=x end注:整個快速排序 Procedure quicksort(VAR R:list。quicksort(R,i+1,t)〕end。k:=k+1 UNTIL(k=n)A.(2n+3)次(n+1)次 次 A,B,C,D,E 順序入棧,不能獲得的序列是:（）:（） p 所指的結(jié)點后插入一個新結(jié)點q,要修改的指針域個數(shù)為:（） 個 個 個 個 A 4 * 4 的下三角元素 A(3,2)的位置是第:（） 個 個 個 個 個結(jié)點順序存儲的完全二叉樹, i(1,設(shè) n0,n1,n2 分別是度數(shù)為 0,1,2的結(jié)點數(shù),則有:（）=n2+1=n21=n1+1=n11(一)的二叉樹,其后續(xù)遍歷結(jié)果為:（）圖（一）:（） SUBSTR(‘ABCDEFGH’,4,5)的引用結(jié)果是:（）A.‘DE’B.‘DEFGH’C.‘EFGH’D.‘BCDE’,R2其健值分別是K1和K2,數(shù)據(jù)為D1和D2,稱R1和R2是同義詞的條件是（）=K2=K2且 H(K1)≠H(K2)=D2≠K2 且 H(K1)=H(K2):（） 數(shù)不平衡后要調(diào)整的情形有:（） 種 種 種 算法是求圖的:（）,使用輔助存儲空間為 O（n）的算法是:（） n 個結(jié)點,e 條邊,則它的鄰接表需要表節(jié)點數(shù)目為:（）+n+1+2n:（） 個二進(jìn)制位 個字節(jié) 個字 個結(jié)點單元 SQ有 m 個單元,其滿隊條件是:（）A.(+1)MOD M==m ==m 文件屬于:（）20．下列說法中錯誤的是：（） 個結(jié)點的有向圖最多有 n*(n1)條邊(錯選,多選,漏選均不得分,每小題 2 分,共 14 分)，可將算法分為：（）:（）,涉及到棧運算的有:（） :將元素均勻的分成塊,塊內(nèi)元素不排序,塊之間排序,則查找塊及塊內(nèi)某元素實施的方法是:（） 順序查元素 順序查元素 折半查元素 折半查元素:（）:（）,內(nèi)容有關(guān),內(nèi)容無關(guān):（）(對的打”√”,錯的打”╳”, 1 分,判斷錯誤, 10 分),新插入的結(jié)點只能插到隊頭.（） 的樹.（）,相同的關(guān)鍵字散列在不同的地址空間上的現(xiàn)象稱為沖突.（）,其時間復(fù)雜度為:O(n log2n).（）.（）(每小題 4 分,共 12分) 樹 (每小題 5 分,共 20 分)(二)(二)圖（三）(緊縮格式)? 他有哪些優(yōu)缺點?(三)所示,給出其鄰接表,并寫出從1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷的:xal,wan,wil,zdl,yo,xul,yum,(每小題 12 分,共 24 分) pascal pascal 一、CDABCACADC1B1D1B1B1C1B1B1B1A D二、B C DA B C DA C EA BB CB D EA C D E或 C D E三、 對尾 二叉數(shù)不是樹的特例 不同,相同√ 不含任何字符,空白字符四、AVL 樹稀疏矩陣哈夫曼樹五、盡可能將串中多個字符存入同一單元的存儲方式,其優(yōu)點是節(jié)省存儲空間,、深度優(yōu)先：1，2，4，5，3，6，7 廣度優(yōu)先：1，2，3，4，5，6，7六、TYPE pointer=↑node node=RECORDinfo: datatype。VAR Count: integer)。TYPE node=RECORDkey: integer。以下略第二篇：考試題目及答案意外門診：理賠申請書發(fā)票原件診斷證明書門診病歷、處方本人事故經(jīng)過（團(tuán)單：單位意外事故證明）身份證、銀行卡或存折、保單復(fù)印件疾病住院：理賠申請書發(fā)票原件診斷證明書病案一套總費用明細(xì)清單身份證、銀行卡或存折、保單復(fù)印件（津貼：體溫記錄）意外住院：理賠申請書發(fā)票原件診斷證明書病案一套總費用明細(xì)清單意外事故經(jīng)過（團(tuán)單：單位意外事故證明）身份證、銀行卡或存折、保單復(fù)印件（津貼：體溫記錄）意外身故：理賠申請書醫(yī)學(xué)死亡證明或派出所死亡證明戶口注銷證明火化證明或土葬證明醫(yī)院搶救記錄及相關(guān)材料身份證及戶口本復(fù)印件所有法定第一順序受益人戶口本、身份證復(fù)印件受益人確認(rèn)書受益人銀行卡或存折復(fù)印件意外事故經(jīng)過（團(tuán)單：單位意外事故證明）保單復(fù)印件（交通事故：交通事故認(rèn)定書、行駛證、駕駛證）疾病身故：理賠申請書醫(yī)學(xué)死亡證明或派出所死亡證明戶口注銷證明火化證明或土葬證明醫(yī)院搶救記錄及相關(guān)材料身份證及戶口本復(fù)印件所有法定第一順序受益人戶口本、身份證復(fù)印件受益人確認(rèn)書受益人銀行卡或存折復(fù)印件保單復(fù)印件非被保險人遞交材料：授權(quán)委托書（被保險人）、被授權(quán)人身份證復(fù)印件另外：理賠款打入單位賬戶的，需提供：理賠款支付聲明（單位出具）、個人委托聲明（被保險人）第三篇：考試題目及答案考試題目及答案一、單項選擇題 2013年11月9日到12日，中共十八屆三中全會在北京召開，這次全會的主題是（A）。A、為人民服務(wù)B