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

-.z線性構(gòu)造題棧和隊(duì)列的共同特點(diǎn)是(A)。(A)只允許在端點(diǎn)處插入和刪除元素(B)都是先進(jìn)后出(C)都是先進(jìn)先出(D)沒有共同點(diǎn)以下數(shù)據(jù)構(gòu)造中哪一個(gè)是非線性構(gòu)造？(D)(A)隊(duì)列(B)棧(C)線性表(D)二叉樹設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問A[3][3](10)存放在(C)位置。腳注(10)表示用10進(jìn)制表示。(A)688(B)678(C)692(D)6964．設(shè)*數(shù)據(jù)構(gòu)造的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)構(gòu)造A是〔B〕。(A)線性構(gòu)造 (B)樹型構(gòu)造 (C)物理構(gòu)造 (D)圖型構(gòu)造5．下面程序的時(shí)間復(fù)雜為〔B〕for〔i=1，s=0；i<=n；i++〕{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n) (B)O(n2) (C)O(n3)(D)O(n4)6.以下程序段的時(shí)間復(fù)雜度為〔A〕。i=0，s=0；while(s<n){s=s+i；i++；}(A)O(n1/2)(B)O(n1/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ū)的邏輯構(gòu)造應(yīng)該是〔B〕 (A)棧 (B)隊(duì)列 (C)樹 (D)圖8．二級數(shù)組a[50][40]按行序?yàn)橹餍虼娣?，每個(gè)元素占4個(gè)字節(jié)空間，假設(shè)數(shù)組a的首元素a[1][1]地址為2012，計(jì)算a[23][21]的存地址為〔B〕。 (A)5600 (B)5612 (C)2912 (D)36009．設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為〔B〕。(A)5，3，4，6，1，2 (B)3，2，5，6，4，1(C)3，1，2，5，4，6 (D)1，5，4，6，2，310．設(shè)有一個(gè)10階的下三角矩陣A〔包括對角線〕，按照從上到下、從左到右的順序存儲到連續(xù)的55個(gè)存儲單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為〔B〕。(A)10 (B)19 (C)28 (D)5511．廣義表A=〔a,b〔c,d〕,(e,(f,g))〕，則head(tail(head(tail(tail(A)))))值為〔D〕(A)〔g〕 (B)(d) (C)(c) (D)(d)12．?dāng)?shù)據(jù)的最小單位是〔A〕。 (A)數(shù)據(jù)項(xiàng) (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量13．函數(shù)substr("DATASTRUCTURE〞，5，9)的返回值為〔A〕。 (A)"STRUCTURE〞(B)"DATA〞 (C)"ASTRUCTUR〞 (D)"DATASTRUCTURE〞14．在線性表中，一個(gè)向量第一個(gè)元素的存儲地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是〔A〕?！睞〕110 〔B〕108〔C〕100 〔D〕12015．棧中元素的進(jìn)出原則是〔B〕。〔Ａ〕先進(jìn)先出〔B〕后進(jìn)先出〔Ｃ〕?？談t進(jìn)〔Ｄ〕棧滿則出16．設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針s指向被插入的結(jié)點(diǎn)*，則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)*的操作序列為〔B〕。(A)s->ne*t=p->ne*t；p->ne*t=-s； (B)q->ne*t=s；s->ne*t=p；(C)p->ne*t=s->ne*t；s->ne*t=p； (D)p->ne*t=s；s->ne*t=q；非線性構(gòu)造1.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為C。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+12.樹最適合用來表示(C)。(A)有序數(shù)據(jù)元素(B)無序數(shù)據(jù)元素(C)元素之間具有分支層次關(guān)系的數(shù)據(jù)(D)元素之間無聯(lián)系的數(shù)據(jù)3.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為(D).(A)2k-1(B)2K+1(C)2K-1(D)2k-14．設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有(D)個(gè)葉子結(jié)點(diǎn)。 〔A〕200 〔B〕250 〔C〕300 〔D〕3505.假設(shè)有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)展二分查找，則查找A［3］的比擬序列的下標(biāo)依次為(D)(A)1，2，3 (B)9，5，2，3(C)9，5，3 (D)9，4，2，36.對n個(gè)記錄的文件進(jìn)展快速排序，所需要的輔助存儲空間大致為(C)(A)O〔1〕(B)O〔n〕(C)O〔1og2n〕(D)O〔n2〕7．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序完畢后的結(jié)果為(A)。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21 (C)10，15，14，20，18，40，36，2l (D)15，10，14，18，20，36，40，218．設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為〔D〕。 (A)n，e (B)e，n (C)2n，e (D)n，2e9．設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用以下〔B〕方法可以到達(dá)此目的。(A)快速排序 (B)堆排序 (C)歸并排序 (D)插入排序10.以下四種排序中〔D〕的空間復(fù)雜度最大。(A)插入排序 (B)冒泡排序 (C)堆排序 (D)歸并排序11．設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有〔D〕個(gè)結(jié)點(diǎn)。 (A)2k-1 (B)2k (C)2k-1 (D)2k-112．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個(gè)長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)展一趟歸并后的結(jié)果為〔〕。(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，8513．設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素*最多需要比擬〔B〕次。 (A)25 (B)10(C)7 (D)114．設(shè)*棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有〔C〕。 (A)20 (B)256 (C)512 (D)102415．在一個(gè)具有n個(gè)頂點(diǎn)的無向連通圖中,要連通全部頂點(diǎn)至少需要〔C〕條邊。〔A〕n〔B〕n+1〔C〕n-1〔D〕n/216.對于線性表〔7，34，55，25，64，46，20，10〕進(jìn)展散列存儲時(shí)，假設(shè)選用H〔K〕=K%9作為散列函數(shù)，則散列地址為1的元素有〔D〕個(gè)，(A)1(B)2(C)3(D)417.設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有(A)條邊才能確保是一個(gè)連通圖。(A)5(B)6(C)7(D)818.二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均〔A〕根結(jié)點(diǎn)的值。(A)< (B)> (C)= (D)!=19.設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為〔D〕。(A)129 (B)219 (C)189 (D)22920.設(shè)*棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有〔C〕個(gè)結(jié)點(diǎn)。(A)2n (B)n+l (C)2n-1 (D)2n+l21.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，*)，則按字母升序的第一趟冒泡排序完畢后的結(jié)果是〔D〕。(A)F，H，C，D，P，A，M，Q，R，S，Y，*(B)P，A，C，S，Q，D，F(xiàn)，*，R，H，M，Y(C)A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，*(D)H，C，Q，P，A，M，S，R，D，F(xiàn)，*，Y22.設(shè)用鄰接矩陣A表示有向圖G的存儲構(gòu)造，則有向圖G中頂點(diǎn)i的入度為〔B〕。 (A)第i行非0元素的個(gè)數(shù)之和 (B)第i列非0元素的個(gè)數(shù)之和 (C)第i行0元素的個(gè)數(shù)之和 (D)第i列0元素的個(gè)數(shù)之和填空題：設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，該隊(duì)列最存儲空間為N個(gè)，則判斷該循環(huán)隊(duì)列為空的條件為___F==A________，判斷隊(duì)列為滿時(shí)條件為(R+1)%N==F。一個(gè)線性表是n≧0個(gè)數(shù)據(jù)元素a1,a2,a3,……an的有限序列，表中每個(gè)數(shù)據(jù)元素，除第一個(gè)和最后一個(gè)外，有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。不管是順序存儲構(gòu)造的棧還是鏈?zhǔn)酱鎯?gòu)造的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為_0(1)_____。設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___5_____種不同的輸出序列。假設(shè)用鏈表存儲一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲構(gòu)造中，n個(gè)結(jié)點(diǎn)的二叉樹共有____2n___個(gè)指針域，其中有___n-1__個(gè)指針域是存放了地址，有_____n+1____個(gè)指針是空指針。對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有____個(gè)和______個(gè)。在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有________條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。在快速排序、堆排序、歸并排序中，___歸并______排序是穩(wěn)定的。___中序_______遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列〔填先序、中序或后序〕。設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素*，則最多需要比擬____7____次就可以斷定數(shù)據(jù)元素*是否在查找表中。設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為___e=d______。設(shè)*無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=__d/2_____。設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___31,38,44,56,75,80,55,63_____。一有向圖的鄰接表存儲構(gòu)造如下：從頂點(diǎn)1出發(fā)，深度優(yōu)先搜索〔Dfs〕的輸出序列是1,3,4,5,2，廣度優(yōu)先搜索〔BFS〕遍歷的輸出序列是1,3,2,4,5假定一個(gè)線性表為(12,23,74,55,63,40)，假設(shè)給出哈希函數(shù)H〔key〕=Key%4條件進(jìn)展劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為____________________________、___________________、_______________________和__________________________。設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開場順序編號，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為__i/2__________，右孩子結(jié)點(diǎn)的編號為___2i+1_____。設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為___________________________。設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓?fù)湫蛄袨開___1,4,2,3___。設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有____0__個(gè)度數(shù)為1的結(jié)點(diǎn)。設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲構(gòu)造，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的_行為出度_，第i列上所有元素之和等于頂點(diǎn)i的_行為入度_。為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題是_構(gòu)造好的hash函數(shù)__和___確定解決沖突方法__。中序遍歷二叉排序樹所得到的序列是___有序___序列〔填有序或無序〕。折半查找有序表〔4，6，12，20，28，38，50，70，88，100〕，假設(shè)查找表中元素20，它將依次與表中元素28,6,12,20比擬大小。線性構(gòu)造中元素之間存在一對一關(guān)系，樹形構(gòu)造中元素之間存在關(guān)系一對多，圖形構(gòu)造中元素之間存在多對多關(guān)系。問答題設(shè)*棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列并畫出該二叉樹。2．待散列的線性表為〔36，15，40，63，22〕，散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H〔K〕=Kmod7，假設(shè)發(fā)生沖突采用線性探查法處理，試：計(jì)算出每一個(gè)元素的散列地址并在以下圖中填寫出散列表：`0123456設(shè)無向圖G〔如右圖所示〕，畫出該圖的最小生成樹的構(gòu)造，并寫出該圖的最小生成樹邊的集合及計(jì)算最小生成樹各邊上的權(quán)值之和。4．序列〔10，18，4，3，6，12，1，9，18*，8〕請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。5．設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟直接選擇排序和第4趟直接插入排序后的結(jié)果。6．給定一組權(quán)值{2，8，5，4，3}，構(gòu)造相應(yīng)的哈夫曼樹。7．以下圖所示的森林：(1)求樹〔a〕的先根序列和后根序列；〔2〕將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；8．設(shè)散列表的地址圍是[0..9]，散列函數(shù)為H〔key〕=〔key2+2〕MOD9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲構(gòu)造。四、算法填空題折半查找算法：IntBinSrch(RecordL,keyTypek)/*在有序表L中折半查找其關(guān)鍵字等于K的元素，假設(shè)找到，則