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

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