2023年專升本試題數(shù)據(jù)結(jié)構(gòu)

《數(shù)據(jù)結(jié)構(gòu)》專升本考試試題（２0２3年３月）一、單項選擇題（本大題共2０小題，每小題2分,共40分)１.對于一個算法,當(dāng)輸入非法數(shù)據(jù)時,也要能作出相應(yīng)的解決，這種規(guī)定稱為()。(A)對的性（B)可行性(C)健壯性(D)輸入性２．設(shè)Ｓ為C語言的語句,計算機(jī)執(zhí)行下面算法時,算法的時間復(fù)雜度為(）。ｆor(i＝ｎ－１;i＞=０；ｉ--)fｏr(j=０；ｊ＜i;j++)Ｓ；(A)n2(B)O(nlgｎ）（Ｃ)O(ｎ)(D）O(n2)3.折半查找法合用于(）。(A）有序順序表（B)有序單鏈表（C）有序順序表和有序單鏈表都可以(D）無限制４.順序存儲結(jié)構(gòu)的優(yōu)勢是()。（A）利于插入操作(Ｂ)利于刪除操作（C）利于順序訪問(D)利于隨機(jī)訪問5．深度為k的完全二叉樹，其葉子結(jié)點必在第（）層上。（A)ｋ-1(Ｂ）ｋ(C)k－１和k(Ｄ)1至k6.具有6０個結(jié)點的二叉樹，其葉子結(jié)點有１2個，則度為1的結(jié)點數(shù)為(）。(A)１1(B）13（C)4８(D)377．圖的Deptｈ-FｉrstSｅaｒcｈ(DFS）遍歷思想事實上是二叉樹（)遍歷方法的推廣。(A)先序(Ｂ）中序（C)后序(D）層序8．在下列鏈隊列Q中,元素a出隊的操作序列為（)。bbcd∧afrontrearＱ(A)p＝Ｑ．front->next；ｐ->next=Q.front－>ｎｅｘt;（B)p=Q．ｆronｔ->next；Ｑ.ｆroｎｔ－>nｅxt=p->ｎexｔ;(C)p＝Q.ｒeａr->ｎext;p->next＝Ｑ.rear->nｅxｔ;(D）p＝Ｑ->ｎext;Q->ｎｅxt=ｐ->next；9.Huffmaｎ樹的帶權(quán)途徑長度WPL等于（)（A)除根結(jié)點之外的所有結(jié)點權(quán)值之和(Ｂ）所有結(jié)點權(quán)值之和（C）各葉子結(jié)點的帶權(quán)途徑長度之和(Ｄ)根結(jié)點的值10.線索二叉鏈表是運用（）域存儲后繼結(jié)點的地址。(A）ｌcｈilｄ(Ｂ）dａt(yī)ａ（C）ｒchｉld(Ｄ)roｏt11.研究數(shù)據(jù)結(jié)構(gòu)就是研究()。（A）數(shù)據(jù)的邏輯結(jié)構(gòu)?? (Ｂ）數(shù)據(jù)的存儲結(jié)構(gòu)(C)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)(D）數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本操作12.算法分析的兩個重要方面是()。(A)空間復(fù)雜度和時間復(fù)雜度?(Ｂ）對的性和簡樸性（Ｃ)可讀性和文檔性（D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性１３.若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素,則采用(）存儲方式最節(jié)省時間。（A)順序表(Ｂ）單鏈表 （C)雙鏈表(D)單循環(huán)鏈表1４.在一個長度為n的順序表中，在第i個元素之前插入一個新元素時,需向后移動（)個元素。（A)n－i? （Ｂ）n-ｉ+1 (C）n-i－1 （D)i15．非空的循環(huán)單鏈表heａd的尾結(jié)點p滿足(）。(Ａ)p->neｘt=＝heaｄ??（B)ｐ-＞nｅxt＝＝NULＬ??（C）ｐ＝=ＮULＬ? ? （D)p==head16．一個棧的輸入序列為:a，b，ｃ,d,e，則棧的不也許輸出的序列是（）。（A）ａ，b，c，d,e(Ｂ）ｄ,e,c,b,a? （C)d，c，e，a，b?(Ｄ)e,d,c,b,a17.設(shè)SUＢＳTR(S,i，ｋ)是求Ｓ中從第i個字符開始的連續(xù)k個字符組成的子串的操作,則對于Ｓ＝‘Beｉjiｎg&Ｎanjｉｎg’，ＳUBＳＴR（Ｓ,4,５)=()。（A）‘ijiｎg’(B)‘jing&’ （Ｃ)‘ｉngＮａ’?（D）‘ing&N’18．廣義表(（a),a)的表尾是（)。（A)a?? (B）（a) ??（Ｃ）()? （D)（(a)）１9．在一棵具有5層的滿二叉樹中結(jié)點總數(shù)為（）。（A）31 (B)32? (C）33 (D）２0．假如從無向圖的任一頂點出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點,則該圖一定是（）。(A)完全圖 （B）連通圖? (C)有回路 ?(Ｄ)一棵樹二、填空題（本大題共２0個空,每空2分,共40分）邏輯結(jié)構(gòu)決定了算法的,而存儲結(jié)構(gòu)決定了算法的。棧和隊列都是一種的線性表,棧的插入和刪除只能在進(jìn)行。線性表（a1,a2,…,an）的順序存儲結(jié)構(gòu)中,設(shè)每個單元的長度為Ｌ，元素ａi的存儲地址LOC(ａi)為已知一雙向鏈表如下(指針域名為ｎexｔ和ｐrｉor):yyxeep現(xiàn)將p所指的結(jié)點插入到x和y結(jié)點之間，其操作環(huán)節(jié)為：；;;；5.ｎ個結(jié)點無向完全圖的的邊數(shù)為，n個結(jié)點的生成樹的邊數(shù)為。6.已知一有向無環(huán)圖如下：EBEBACDFG任意寫出二種拓?fù)渑判蛐蛄?、。7.已知二叉樹的中序遍歷序列為ＢCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為，層序遍歷序列為。8.數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表達(dá)，它們分別是。9.在圖形結(jié)構(gòu)中,每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以。10.寫出帶頭結(jié)點的雙向循環(huán)鏈表L為空表的條件。11．哈夫曼樹是其樹的帶權(quán)途徑長度的二叉樹。12.n個頂點的連通圖至少有條邊。三、應(yīng)用題（本大題共6小題，共40分）1.設(shè)散列函數(shù)H(k)=k%13,設(shè)關(guān)鍵字系列為{22,1２，24,6，４5,7，8，13,２１}，規(guī)定用線性探測法解決沖突。(8分)（1）構(gòu)造HASＨ表。(2）分別求查找成功和不成功時的平均查找長度。給定表（19,１4，22,15,20,2１,56，１0）。(６分）按元素在表中的順序，建立一棵二叉排序樹。對(1)中所建立的二叉排序樹進(jìn)行中序遍歷，寫出遍歷序列。已知一維數(shù)組中的數(shù)據(jù)為（18，１2，25,53,18），試寫出插入排序（升序)過程。并指出具有ｎ個元素的插入排序的時間復(fù)雜度是多少？(6分)已知二叉樹的先序遍歷序列為ＡBCDEFGH，中序遍歷序列為ＣＢＥDFAＧＨ,畫出該二叉樹。（５分)已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點Ａ開始的最小生成樹。（6分)ABＣDEF6．已知數(shù)據(jù)六個字母及在通信中出現(xiàn)頻率如下表:ABＣＤEＦ0.15０.15０.10．1０.20.3把這些字母和頻率作為葉子結(jié)點及權(quán)值，完畢如下工作（9分，要有過程）。（1)畫出相應(yīng)的Huffman樹。（2)計算帶權(quán)途徑長度ＷPL。(3）求Ａ、Ｂ、C、Ｄ、E、Ｆ的Hｕｆfｍａn編碼。四、程序分析填空題(本大題共2小題,每小題５分，共１0分)1．函數(shù)GｅtElem實現(xiàn)返回單鏈表的第ｉ個元素,請在空格處將算法補充完整。 intGeｔEleｍ(LinｋLisｔL,ｉnti,Ｅlemtｙpｅ*e）｛ ?LiｎkListp；inｔj；p=L->ｎext;j＝1; ?whｉle(ｐ＆&j＜i){ (1);++j;}iｆ(!p|｜j＞ｉ）reｔｕrｎERROR；*e=（2);rｅturnOＫ;}2．函數(shù)ListDｅlete_sq實現(xiàn)順序表刪除算法,請在空格處將算法補充完整。iｎtListDeｌetｅ＿ｓq(Ｓqlｉsｔ*L，inti){intｋ;ｉf（i<1||i>L－>lｅngｔh)ｒeturnERRＯＲ；for(k=i－1;ｋ<L-