數(shù)據(jù)結(jié)構(gòu)期末考試客觀題及答案

一、單選題1、?有序數(shù)組a[18]進(jìn)行二分查找時(shí)，查找到a[5]的查找路徑（下標(biāo)序列）為_____。A.8，2，5B.1，3，5C.8，3，5D.8，4，5正確答案：C2、?對a[12]進(jìn)行二分查找，在等概率情況下，查找成功的平均查找長度為___。A.37/12B.43/12C.35/12D.39/12正確答案：A3、已知last指向單向簡單鏈表的尾結(jié)點(diǎn)，將s所指結(jié)點(diǎn)加在表尾，正確的操作是____。A.s->next=s,last=s,last->next=NULL;B.s->next=NULL,last->next=s,s=last;C.last->next=s,s->next=NULL,last=s;D.s->next=last,last->next=NULL,last=s;正確答案：C4、在長度為n的有序鏈表中插入結(jié)點(diǎn)并保持有序，最壞情況下和平均情況下，時(shí)間復(fù)雜性分別是_____。A.O(n)和O(logn)B.O(n)和O(1)C.O(logn)和O(n)D.O(n)和O(n)正確答案：D5、設(shè)進(jìn)棧序列是1，2，3，…，n，輸出序列為p1，p2，p3，…，pn。若p1=3，則p2為_____。A.可能是1B.不可能是2C.必是1D.可能是2正確答案：D6、高度為h的正則二叉樹至少有_____結(jié)點(diǎn)。A.2hB.2h-1C.2h+1D.2h+1正確答案：B7、正則二叉樹的先序序列為ABCDE，后序序列為BDECA，則其中序序列是__________。A.DBCAEB.BADCEC.ABCEDD.ABDCE正確答案：B8、若檢索樹中序序列是從小到大的序列，下列說法正確的是。A.檢索樹中，每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比其右子樹中所有結(jié)點(diǎn)關(guān)鍵字大或相等，比其左子樹中所有結(jié)點(diǎn)關(guān)鍵字小B.檢索樹中，每個(gè)結(jié)點(diǎn)的關(guān)鍵字都不比其左孩子關(guān)鍵字大或相等，不比其右孩子關(guān)鍵字小C.檢索樹中，每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比其左孩子關(guān)鍵字大或相等，比其右孩子關(guān)鍵字小D.檢索樹中，每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比其左子樹中所有結(jié)點(diǎn)關(guān)鍵字大或相等，比其右子樹中所有結(jié)點(diǎn)關(guān)鍵字小正確答案：D9、如圖所示檢索樹，其成功平均查找長度為____。A.2.9B.2.5C.3.2D.2.7正確答案：A10、?具有5層結(jié)點(diǎn)的AVL樹至少有____個(gè)結(jié)點(diǎn)。A.17B.13C.12D.15正確答案：C11、將結(jié)點(diǎn)13，24，37，90，53插入開始為空的平衡樹，其先序遍歷序列為____。A.24，13，53，37，90B.13，24，37，90，53C.24，13，37，90，53D.13，37，24，90，53正確答案：A12、設(shè)有13個(gè)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有____個(gè)結(jié)點(diǎn)。A.25B.12C.26D.13正確答案：A13、排序的時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlogn)的是（）。A.快速排序B.冒泡排序C.希爾排序D.堆排序正確答案：D14、一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（）。A.冒泡排序B.希爾排序C.快速排序D.堆排序正確答案：B15、執(zhí)行一趟快速排序能夠得到的序列是（）。A.[12，27，45，41]55[34，63，72]B.[41，12，34，45，27]55[72，63]C.[45，34，12，41]55[72，63，27]D.[63，12，34，45，27]55[41，72]正確答案：B16、?利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（）。A.O(nlogn)B.O(1ogn)C.O(n2D.O(n)正確答案：C17、?設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序排序的第一趟冒泡排序結(jié)束后的結(jié)果是（）。A.H，C，Q，P，A，M，S，R，D，F(xiàn)，X，YB.F，H，C，D，P，A，M，Q，R，S，Y，XC.A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，XD.P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y正確答案：A18、?在下列排序算法中,哪一個(gè)算法的時(shí)間復(fù)雜度與初始排序無關(guān)（）。A.改進(jìn)的冒泡排序B.直接插入排序C.快速排序D.簡單選擇排序正確答案：D19、?下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上，并且其時(shí)間性能受數(shù)據(jù)初始特性影響的是（）。A.簡單選擇排序B.直接插入排序C.快速排序D.堆排序正確答案：C20、以下代碼的復(fù)雜度是（）。x=0;for(i=1;i<n;i++)for(j=i;j<n;j++)x++;A.O(logn)B.O(nlogn)C.O(n)D.O(n*n)正確答案：D21、以下說法錯誤的是_____。A.裝填因子是散列法的一個(gè)重要參數(shù)，它反映了散列表的裝填程度B.散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針C.散列存儲的基本思想是由元素值決定其存儲地址D.散列表的查找效率主要取決于的散列函數(shù)和處理沖突的方法正確答案：B22、設(shè)散列表長m=14，散列函數(shù)Hash(x)=xmod11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址為空。若用平方探測法di=i*i處理沖突，插入元素49時(shí)，其地址是_____。A.5B.9C.8D.3正確答案：B23、在有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的____倍。A.1B.2C.4D.3正確答案：A24、對于下圖所存儲的有向圖，從頂點(diǎn)A開始進(jìn)行先廣搜索，不能得到的頂點(diǎn)序列是______。A.ABCEDB.ACBDEC.ADCEBD.ABCDE正確答案：C25、?非空的循環(huán)單鏈表L的尾結(jié)點(diǎn)(由p所指向)滿足____。A.p->next==NULLB.p==LC.p->next==LD.p==NULL正確答案：C26、?設(shè)有兩個(gè)長度為n的單鏈表，結(jié)點(diǎn)類型相同，若以hl為首結(jié)點(diǎn)的鏈表是非循環(huán)的，以h2為首結(jié)點(diǎn)指針的鏈表是循環(huán)的，則____。A.循環(huán)鏈表要比非循環(huán)鏈表占用更多的內(nèi)存空間B.hl和h2是不同類型的變量C.對于兩個(gè)鏈表來說，刪除最后一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(n)D.對于兩個(gè)鏈表來說，刪除第一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(1)正確答案：C27、?用二分法對數(shù)組a[13]進(jìn)行查找，若待查元素為x介于a[7]~a[8]之間，那么查找路徑為_______（用下標(biāo)序列表示）。A.6，10，7，8B.6，9，8，7C.6，9，7D.6，9，7，8正確答案：D28、?將如圖所示的單向鏈表中A段和B段交換位置（將B段調(diào)到A段的前面，其余結(jié)點(diǎn)次序不變），正確的程序段為_______。A.t=q->next;q->next=r->next;r->next=q;p->next=t；B.q->next=r->next;r->next=p->next;p->next=q->next；C.p->next=q->next；q->next=r->next;r->next=p->next;D.t=q->next;q->next=r->next;r->next=p->next;p->next=t；正確答案：D29、?帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是____。A.L->next==NULLB.L->next==LC.L!=NULLD.L==NULL正確答案：A30、?設(shè)進(jìn)棧序列是1，2，3，…，n，輸出序列為p1，p2，p3，…，pn。若p3=1，則p1為_____。A.不可能是3B.必是2C.必定是3D.可能是3正確答案：D31、?用二分法對數(shù)組a[13]進(jìn)行查找，在等概率的情況下，查找不成功的平均查找長度為____。A.27/7B.48/13C.49/14D.54/13正確答案：A32、?高為h的m元樹（m≥2，h≥1）中結(jié)點(diǎn)總數(shù)n_____。A.≥B.C.D.正確答案：C33、?若k元正則樹中共有m個(gè)非葉結(jié)點(diǎn)，則葉子數(shù)________。A.=(k-1)m+1B.=(k-1)m-1C.≤kmD.≥(k-1)m正確答案：A34、?已知二叉樹的先序序列是15，5，3，10，8，18，24；后序序列是3，8，10，5，24，18，15；樹中共有三片葉（3，8，24），而根結(jié)點(diǎn)和另外一個(gè)結(jié)點(diǎn)的度數(shù)為2。其余結(jié)點(diǎn)度數(shù)為1。請問結(jié)點(diǎn)24的父親結(jié)點(diǎn)是_______。A.18B.10C.5D.3正確答案：A35、?依次插入20，8，17，25，30，18來構(gòu)造開始為空的平衡二叉樹，則此平衡二叉樹的后序遍歷序列為_______。A.8，17，20，18，25，30B.8，17，18，30，25，20C.20，17，8，25，18，30D.20，8，17，25，30，18正確答案：B36、?在待排序的元素序列基本有序的前提下，效率最高的排序方法是_______。A.快速排序B.插入排序C.歸并排序D.選擇排序正確答案：D37、?用某種排序方法對線性表{25，84，21，47，15，27，68，35，20}進(jìn)行排序時(shí)，元素序列的變化情況如下：?（1）25，84，21，47，l5，27，68，35，20?（2）20，15，21，25，47，27，68，35，84?（3）15，20，21，25，35，27，47，68，84?（4）15，20，21，25，27，35，47，68，84?則采用的排序方法是_______。A.堆排序B.冒泡排序C.直接插入排序D.希爾排序正確答案：A38、?穩(wěn)定的排序方法是_______。A.直接插入排序B.快速排序C.堆排序D.簡單選擇排序正確答案：A39、?一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有_______條邊。A.n(n-1)B.nC.n(n-1)/2D.2n正確答案：C40、?已知一個(gè)圖如圖所示，若從頂點(diǎn)a出發(fā)按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_______。?A.a，b，c，e，d，fB.a，b，c，e，f，dC.a，c，f，d，e，bD.a，e，b，c，f，d正確答案：B41、?使用普里姆算法構(gòu)造出如圖所示的圖G的一棵最小生成樹，從頂點(diǎn)1出發(fā)依次得到的最小生成樹的序列為_______。A.(1,3)1,(3,6)4,(6,4)2,(3,2)5,(2,5)3B.(1,3)1,(6,4)2,(2,5)3,(3,6)4,(3,2)5C.(1,3)1,(3,6)4,(3,2)5,(6,4)2,(2,5)3D.(1,3)1,(3,2)5,(2,5)3,(3,6)4,(6,4)2正確答案：A42、?具有n個(gè)頂點(diǎn)，m條邊的無向圖，其鄰接表中，共有n個(gè)頂點(diǎn)結(jié)點(diǎn)和____個(gè)邊結(jié)點(diǎn)。A.mB.m/2C.2mD.n+m正確答案：C43、?下面敘述正確的是______。A.算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)B.以上三種描述都不對C.算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止D.算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)正確答案：C二、填空題1、?在一棵二叉樹中，度為2的結(jié)點(diǎn)有5個(gè)，度為1的結(jié)點(diǎn)有6個(gè)，則葉子結(jié)點(diǎn)數(shù)有_________個(gè)。正確答案：62、?G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有______個(gè)頂點(diǎn)。正確答案：83、對于下圖中的加權(quán)圖，其最小生成樹的邊長之和等于______。正確答案：154、?在對一組記錄{54，38，96，23，15，72，60，45，83}進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需