2023年數(shù)據(jù)結(jié)構(gòu)題庫

線性結(jié)構(gòu)題棧和隊(duì)列的共同特點(diǎn)是(A）。（A）只允許在端點(diǎn)處插入和刪除元素(Ｂ)都是先進(jìn)后出(C)都是先進(jìn)先出(Ｄ)沒有共同點(diǎn)以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)?(D)(A）隊(duì)列(B)棧(Ｃ）線性表(D)二叉樹設(shè)有一個(gè)二維數(shù)組A[m］［n］,假設(shè)Ａ［０][０]存放位置在64４(1０),Ａ［２］［2]存放位置在６76（10)，每個(gè)元素占一個(gè)空間，問A［３][3](１０）存放在(C)位置。腳注(10)表達(dá)用1０進(jìn)制表達(dá)。(Ａ)６88(B)6７８(C)６9２(Ｄ）６964.設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表達(dá)為A＝(D，R),D=｛01，0２，03，04，05，06，０７，０8，09｝，R={ｒ},r={＜０1,0２＞，＜01,03>，＜01,０4>，＜0２,05>,<０２,06>,<0３,０7＞,<０3，08>，<０3,０9>},則數(shù)據(jù)結(jié)構(gòu)A是(B）。?(A)線性結(jié)構(gòu)?(B)樹型結(jié)構(gòu)?(Ｃ)物理結(jié)構(gòu)?(D)圖型結(jié)構(gòu)5.下面程序的時(shí)間復(fù)雜為（B）for(i=１,ｓ＝０；i<=n;i+＋）{t=1；foｒ(ｊ=１；ｊ<＝i;ｊ+＋)t=t＊ｊ;s＝ｓ+t；}?（A)O（n) (Ｂ)O(n2) （C）Ｏ(n3)? (D）Ｏ(n４）６．下列程序段的時(shí)間復(fù)雜度為(Ａ)。i=0,s=0；ｗhｉle(ｓ＜ｎ){s=ｓ+i;i++;｝（A）Ｏ(n1/2)?(B)O（n１/3)?(C)O(n) (D）O(n2)7.為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配的問題,通常設(shè)立一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要打印輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)當(dāng)是(B） (A）棧?(B)隊(duì)列?(C)樹 (D)圖8.已知二級(jí)數(shù)組ａ［50][4０]按行序?yàn)橹餍虼娣?，每個(gè)元素占4個(gè)字節(jié)空間，若數(shù)組a的首元素a[１][１]地址為202３,計(jì)算a[2３］［２1］的內(nèi)存地址為（Ｂ)。 (A)５６0０ （B)5612 (C)2912 ?(Ｄ）3６009.設(shè)輸入序列為１、2、3、４、５、6，則通過棧的作用后可以得到的輸出序列為（B）。(A）5,3,4，６,１，2?(B）3,２,5,6,4,1(C)３，1，2，5，4,6?(D)1，５,4,６,2，3１0．設(shè)有一個(gè)10階的下三角矩陣A(涉及對(duì)角線），按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中,每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則Ａ［5]［4]地址與Ａ[０]［0］的地址之差為(Ｂ)。(A)１0 (B)19?(C）28 (D)5５１1．廣義表A=(a,b（c,d),(e,(f,g)))，則head(tail（hｅad(tａil(tａil(A)))))值為（D) （Ａ)（g) (B)(d)?（C)（c)?(D)(ｄ)1２.數(shù)據(jù)的最小單位是（Ａ）。 (A)數(shù)據(jù)項(xiàng)?（B）數(shù)據(jù)類型 (Ｃ）數(shù)據(jù)元素 (D）數(shù)據(jù)變量13.函數(shù)ｓｕbsｔr(“DＡTASＴRUＣＴUＲE”，５，９)的返回值為(A）。 (Ａ)“SＴＲＵCＴＵRE” (B)“DATA”?(C)“ASTRUＣTＵＲ” (Ｄ)“DATAＳＴRＵCTURE”1４.在線性表中,一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是１０0，每個(gè)元素的長(zhǎng)度為２,則第5個(gè)元素的地址是(A）。(A)11０ （Ｂ)108（C）100?(Ｄ）1２015.棧中元素的進(jìn)出原則是（Ｂ)。(Ａ)先進(jìn)先出（B）后進(jìn)先出（Ｃ)?？談t進(jìn)（D）棧滿則出１６.設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針ｐ指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針ｓ指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)X的操作序列為（B)。（A)s->next=p－>ｎext;ｐ->nexｔ=-ｓ;?(Ｂ）q->ｎeｘt=ｓ;ｓ-＞ｎｅxt=p;(C)p-＞ｎext=s->next；ｓ->ｎｅxt=p; (Ｄ）p->nexｔ=ｓ;s->nexｔ=q;

非線性結(jié)構(gòu)1.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為C。(Ａ)log2(n)（Ｂ)ｌoｇ2（n) （C)loｇ２(n)+１(D）lｏg2(n）＋12．樹最適合用來表達(dá)(C)。（A)有序數(shù)據(jù)元素（B）無序數(shù)據(jù)元素??(Ｃ)元素之間具有分支層次關(guān)系的數(shù)據(jù)（D)元素之間無聯(lián)系的數(shù)據(jù)3.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為（Ｄ).(A)2k-1(Ｂ）2K＋1(C)2K-1（D）2ｋ－14．設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有(D)個(gè)葉子結(jié)點(diǎn)。 (Ａ）２00?（B）250 （C)3００ (D）3505.若有18個(gè)元素的有序表存放在一維數(shù)組A［19］中,第一個(gè)元素放A［1］中，現(xiàn)進(jìn)行二分查找，則查找Ａ[3]的比較序列的下標(biāo)依次為(D)(A)1，２，3 ?? ??(B)9,5,2，3(C)9，5,3?? ? ? (D)9，4，2,36.對(duì)n個(gè)記錄的文獻(xiàn)進(jìn)行快速排序,所需要的輔助存儲(chǔ)空間大體為(C)(A)Ｏ（1)(B)Ｏ（n）(C)Ｏ(１og2n)(D)Ｏ(ｎ２)7.設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(2０，15，14，18,21,３6,4０，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為(A)。(A）10,１5，14,１８,2０，３6,4０,21?(Ｂ)1０，1５,１4，１8，20,4０,3６，21 （Ｃ)10,１5，1４,20,18，40，３6，2ｌ (D)15，1０,14,18,２0,36,40,2１8．設(shè)無向圖G中有ｎ個(gè)頂點(diǎn)e條邊,則其相應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為(D）。 (Ａ）n,e （B）e，ｎ (C）2n,e （D)n,2e９．設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，假如需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字,則用下列（B)方法可以達(dá)成此目的。?（A）快速排序?(Ｂ)堆排序?（C)歸并排序?(D)插入排序10.下列四種排序中（D）的空間復(fù)雜度最大。 (A)插入排序?（Ｂ）冒泡排序?(C)堆排序 （D）歸并排序１1.設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有(Ｄ）個(gè)結(jié)點(diǎn)。?(A)2k-1?(B）2k (C)2k-１ (D)2k-112.設(shè)一組初始記錄關(guān)鍵字序列為(2５，50,１5，35,8０，85，２0,4０，36，70)，其中具有５個(gè)長(zhǎng)度為２的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為(）。（A)15，２5，35,５0，20,4０,８０，85,36,70(B)15，２5，35,5０,80,2０，85,40,7０,36(Ｃ)１5,25，３5,５0,80,85，20,36,40,７０(D)15，２5，35,5０,8０，20，3６，4０，70,8513．設(shè)有序表中有10０0個(gè)元素，則用二分查找查找元素X最多需要比較(B)次。 (A)25?(B）1０ （C)7 ?(D)1１4．設(shè)某棵二叉樹的高度為10,則該二叉樹上葉子結(jié)點(diǎn)最多有（C)。?(A)20?（B）2５6?（C)５12?（D)10２４15．在一個(gè)具有ｎ個(gè)頂點(diǎn)的無向連通圖中,要連通所有頂點(diǎn)至少需要(C）條邊。(A)ｎ（B）n+1（C)n-1（D)n/21６.對(duì)于線性表（7，34,55，2５,64,4６,2０，10）進(jìn)行散列存儲(chǔ)時(shí),若選用H（K）=K%９作為散列函數(shù)，則散列地址為１的元素有(D）個(gè)，（A)1(B)2(C)3(D)41７.設(shè)有６個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（A)條邊才干保證是一個(gè)連通圖。(A)5(B)6(C)７(D)818．二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（A）根結(jié)點(diǎn)的值。(Ａ)< （B）＞?(C)= (D)!=１9.設(shè)一組權(quán)值集合W=(15，3,１4,2，6,９,１6，1７),規(guī)定根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹,則這棵哈夫曼樹的帶權(quán)途徑長(zhǎng)度為(Ｄ)。(A)1２９ （B）2１9 (C)1８９ (D)２292０．設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為０的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有(C）個(gè)結(jié)點(diǎn)。(Ａ)２n?(Ｂ)n＋l (C)2n-1 (D)2n+l21.設(shè)一組初始記錄關(guān)鍵字序列為(Ｑ,H，C,Y,Ｐ,A，M,S，R,Ｄ，Ｆ,X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（D）。(A)Ｆ，H,Ｃ，D，Ｐ,Ａ,M，Ｑ，R，S，Ｙ，X(B)P,A,C，S,Ｑ，D,Ｆ,X，R，H,M，Y(C)A，Ｄ，Ｃ,R,F,Ｑ,M，S,Y，P,H,X(D)Ｈ,Ｃ,Ｑ,P,A,M,S，R,Ｄ，Ｆ,Ｘ，Y2２．設(shè)用鄰接矩陣A表達(dá)有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（B)。 (Ａ)第i行非０元素的個(gè)數(shù)之和 (B)第ｉ列非０元素的個(gè)數(shù)之和?(Ｃ)第ｉ行0元素的個(gè)數(shù)之和??(D)第ｉ列0元素的個(gè)數(shù)之和填空題：設(shè)F和R分別表達(dá)順序循環(huán)隊(duì)列的頭指針和尾指針，該隊(duì)列最存儲(chǔ)空間為N個(gè)，則判斷該循環(huán)隊(duì)列為空的條件為＿_(dá)_F＝=A__＿_(dá)__＿_(dá),判斷隊(duì)列為滿時(shí)條件為(R+１)%N==F。一個(gè)線性表是n≧０個(gè)數(shù)據(jù)元素a1,a2,a3,……aｎ的有限序列,表中每個(gè)數(shù)據(jù)元素，除第一個(gè)和最后一個(gè)外，有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。不管是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧,其入棧和出棧操作的時(shí)間復(fù)雜度均為＿０（１)＿_(dá)_＿＿。設(shè)輸入序列為１、2、3，則通過棧的作用后可以得到_＿_(dá)5____＿種不同的輸出序列。若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外,尚有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中,n個(gè)結(jié)點(diǎn)的二叉樹共有____2n___個(gè)指針域,其中有＿_(dá)＿n-1__個(gè)指針域是存放了地址，有＿_(dá)_＿_(dá)ｎ＋1_＿_(dá)_個(gè)指針是空指針。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖,在其相應(yīng)的鄰接表中,所含邊結(jié)點(diǎn)分別有_＿＿_(dá)個(gè)和______個(gè)。在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中,包具有＿_(dá)____＿＿條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中,包具有_＿_(dá)_____條邊。在快速排序、堆排序、歸并排序中，___歸并__＿_(dá)__排序是穩(wěn)定的。___中序____＿_(dá)_遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列(填先序、中序或后序)。設(shè)查找表中有100個(gè)元素,假如用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較___＿7_＿＿_(dá)次就可以斷定數(shù)據(jù)元素X是否在查找表中。設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊,所有的頂點(diǎn)入度數(shù)之和為ｄ,則ｅ和d的關(guān)系為___e＝d＿_(dá)____。設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為ｎ和e,所有頂點(diǎn)的度數(shù)之和為d，則e=__d／2_＿_(dá)__。設(shè)一組初始記錄關(guān)鍵字序列為(55,6３,４４,38，7５,8０，31，5６)，則運(yùn)用篩選法建立的初始堆為___31,3８,44,56,7５,８0,5５,63_____。已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，深度優(yōu)先搜索(Dfs)的輸出序列是1，３,４,５,2,廣度優(yōu)先搜索（ＢFS）遍歷的輸出序列是1,3，2,4,5假定一個(gè)線性表為（12,２３,7４，55,63,4０),若給出哈希函數(shù)Ｈ(ｋey）=Kｅy％4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為_______＿_(dá)____＿_(dá)＿_(dá)＿_(dá)＿_(dá)____＿＿_(dá)、_____＿_(dá)＿＿_(dá)＿_(dá)______＿、＿_(dá)_______＿_(dá)________＿_(dá)__和____＿_(dá)_＿_(dá)_______＿＿_(dá)＿_(dá)___＿＿。設(shè)有ｎ個(gè)結(jié)點(diǎn)的完全二叉樹，假如按照從自上到下、從左到右從1開始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為__i／２_＿_(dá)＿＿_(dá)＿＿＿_(dá),右孩子結(jié)點(diǎn)的編號(hào)為_＿_(dá)2i＋1____＿。設(shè)一組初始記錄關(guān)鍵字為(７２,73，71,23,94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為__＿_(dá)_＿＿_(dá)__________＿_(dá)_____＿_(dá)。設(shè)有向圖G中有向邊的集合Ｅ＝{<1，2>,<2，3>，<1,４＞,<4，2>,＜4,3>},則該圖的一種拓?fù)湫蛄袨開___1，４,2,3_＿_(dá)。設(shè)哈夫曼樹中共有ｎ個(gè)結(jié)點(diǎn),則該哈夫曼樹中有___＿０＿_(dá)個(gè)度數(shù)為１的結(jié)點(diǎn)。設(shè)有向圖G用鄰接矩陣A[n]［ｎ]作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)ｉ的＿行為出度_，第i列上所有元素之和等于頂點(diǎn)i的＿行為入度_。為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題是_構(gòu)造好的hasｈ函數(shù)__和__＿擬定解決沖突方法__。中序遍歷二叉排序樹所得到的序列是___有序___序列(填有序或無序）。折半查找有序表（４，6，１2,2０,28，３8，50，70，８8，100),若查找表中元素20，它將依次與表中元素２８,6,１2，2０比較大小。線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系,樹形結(jié)構(gòu)中元素之間存在關(guān)系一對(duì)多，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。?問答題設(shè)某棵二叉樹的中序遍歷序列為ＤＢEＡC,前序遍歷序列為ABDEC，規(guī)定給出該二叉樹的的后序遍歷序列并畫出該二叉樹。２．已知待散列的線性表為(３6,15,40,63，2２)，散列用的一維地址空間為[０．．6]，假定選用的散列函數(shù)是H（K)＝Kmod7，若發(fā)生沖突采用線性探查法解決,試:計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表：`0123４5６設(shè)無向圖G(如右圖所示),畫出該圖的最小生成樹的結(jié)構(gòu)，并寫出該圖的最小生成樹邊的集合及計(jì)算最小生成樹各邊上的權(quán)值之和。４.已知序列(1０，１８，４,3,６，1２，１,9，１8*,8）請(qǐng)用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。5．設(shè)一組初始記錄關(guān)鍵字序列為(45,80，48,40，22,78),則分別給出第4趟直接選擇排序和第4趟直接插入排序后的結(jié)果。６．給定一組權(quán)值{2,8，5,4，3}，構(gòu)造相應(yīng)的哈夫曼樹。7.下圖所示的森林:(１)求樹（a)的先根序列和后根序列；（2)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹;8．設(shè)散列表的地址范圍是[0．.9]，散列函數(shù)為H（kｅｙ)＝（kｅy２+2)MOD9,并采用鏈表解決沖突，請(qǐng)畫出元素7、4、５、3、6、2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。四、算法填空題折半查找算法：IｎｔBinＳrch(ＲｅcｏrdL,keyTypek)／*在有序表L中折半查找其關(guān)鍵字等于K的元素,若找到，則函數(shù)值為該元素在表中的位置*/Loｗ=１Higｈ=L