數(shù)據(jù)結(jié)構(gòu)(本科)武漢理工大學(xué)在線作業(yè)

1、-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-數(shù)據(jù)結(jié)構(gòu)（本科）武漢理工大學(xué)在線作業(yè)一、判斷(共計(jì)40分,每題2.5分)1、快速排序是排序算法中平均性能最好的一種排序。（）正確錯(cuò)誤答案:【A】2、調(diào)用一次深度優(yōu)先遍歷能夠接見(jiàn)到圖中的所有極點(diǎn)。（）正確錯(cuò)誤答案:【B】3、對(duì)連通圖進(jìn)行深度優(yōu)先遍歷能夠接見(jiàn)到該圖中的所有極點(diǎn)。（）正確錯(cuò)誤答案:【A】4、線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（）正確錯(cuò)誤答案:【B】5、設(shè)一棵二叉樹(shù)的先序序列和后序序列，則能夠唯一確定出該二叉樹(shù)的形狀。（）A.正確B.錯(cuò)誤答案:【B】6、先序遍歷一棵二叉排序樹(shù)獲取的結(jié)點(diǎn)序列不用然是有序的序列。（）A.正確B.錯(cuò)誤答案:【A】

2、7、不論線性表采用次序儲(chǔ)藏結(jié)構(gòu)還是鏈?zhǔn)絻?chǔ)藏結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。（）A.正確B.錯(cuò)誤答案:【A】8、滿(mǎn)二叉樹(shù)必然是完滿(mǎn)二叉樹(shù)，完滿(mǎn)二叉樹(shù)不用然是滿(mǎn)二叉樹(shù)。（）-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-正確錯(cuò)誤答案:【A】9、子串“ABC”在主串“AABCABCD”中的地址為2。()正確錯(cuò)誤答案:【A】10、非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（）正確錯(cuò)誤答案:【A】11、分塊查找的平均查找長(zhǎng)度不但與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。（）正確錯(cuò)誤答案:【A】12、線性表的次序儲(chǔ)藏結(jié)構(gòu)比鏈?zhǔn)絻?chǔ)藏結(jié)構(gòu)更好。（）正確錯(cuò)誤答案:【B】13、向二叉排序

3、樹(shù)中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹(shù)的高度。（）正確錯(cuò)誤答案:【B】14、層次遍歷初始堆能夠獲取一個(gè)有序的序列。（）正確錯(cuò)誤答案:【B】15、冒泡排序在初始要點(diǎn)字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）正確錯(cuò)誤答案:【A】16、設(shè)初始記錄要點(diǎn)字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。（）正確錯(cuò)誤-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-答案:【B】二、單項(xiàng)選擇(共計(jì)60分,每題2.5分)17、在二叉排序樹(shù)中插入一個(gè)要點(diǎn)字值的平均時(shí)間復(fù)雜度為（）。O(n)O(1og2n)O(nlog2n)O(n2)答案:【B】18、設(shè)有序次序表中有n個(gè)數(shù)據(jù)元素，則利用二

4、分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不高出（）。A.log2n+1B.log2n-1C.log2nD.log2(n+1)答案:【A】19、設(shè)用毗鄰矩陣A表示有向圖G的儲(chǔ)藏結(jié)構(gòu)，則有向圖G中極點(diǎn)i的入度為（）。A.第i行非0元素的個(gè)數(shù)之和B.第i列非0元素的個(gè)數(shù)之和C.第i行0元素的個(gè)數(shù)之和D.第i列0元素的個(gè)數(shù)之和答案:【B】20、對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助儲(chǔ)藏空間大體為()O（1）O（n）O（1og2n）O（n2）答案:【C】21、用鏈接方式儲(chǔ)藏的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)()-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-僅更正頭指針頭、尾指針都要更正僅更正尾指針頭、尾指

5、針可能都要更正答案:【D】22、設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A是（）。線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)物理結(jié)構(gòu)圖型結(jié)構(gòu)答案:【B】23、以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？()隊(duì)列棧線性表二叉樹(shù)答案:【D】24、以下排序算法中時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(n2)的是堆排序冒泡排序直接選擇排序快速排序答案:【C】25、設(shè)次序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要搬動(dòng)（）個(gè)元素。n-in+l-in-1-i-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-D.i答案:【A】26、設(shè)指針q指向單鏈

6、表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)X的操作序列為（）。A.s-next=p-next；p-next=-sB.q-next=s；s-next=pC.p-next=s-next；s-next=pD.p-next=s；s-next=q答案:【B】27、設(shè)一棵完滿(mǎn)二叉樹(shù)中有65個(gè)結(jié)點(diǎn)，則該完滿(mǎn)二叉樹(shù)的深度為（）。8765答案:【B】28、設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均查找長(zhǎng)度為（）。O(1)O(log2n)O(nlog2n)O(n2)答案:【B】29、設(shè)輸入序列1、2、3、n經(jīng)過(guò)棧作用后，輸出序列中的第一個(gè)元素是n，則

7、輸出序列中的第i個(gè)輸出元素是（）。A.n-iB.n-1-iC.n+l-iD.不能夠確定答案:【C】30、樹(shù)最適合用來(lái)表示()。-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-有序數(shù)據(jù)元素?zé)o序數(shù)據(jù)元素元素之間擁有分支層次關(guān)系的數(shù)據(jù)元素之間無(wú)聯(lián)系的數(shù)據(jù)答案:【C】31、以下各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（）?？焖倥判蚨雅判驓w并排序冒泡排序答案:【D】32、設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖最少應(yīng)有()條邊才能保證是一個(gè)連通圖。5678答案:【A】33、設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則采用以下（）儲(chǔ)藏方式最節(jié)約運(yùn)算時(shí)間。單向鏈表單向循環(huán)鏈表雙向鏈表雙向循環(huán)鏈表答案:【

8、D】34、設(shè)散列表中有m個(gè)儲(chǔ)藏單元，散列函數(shù)H(key)=key%p，則p最好選擇（）。小于等于小于等于小于等于小于等于答案:【B】的最大奇數(shù)的最大素?cái)?shù)的最大偶數(shù)的最大合數(shù)35、在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。O(1)O(n)-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-O(log2n)O(n2)答案:【C】36、（）是線性表。A.(1,2,3,)a,b,c,d,e(1,3,5,7)A,B,C答案:【C】37、設(shè)某完滿(mǎn)無(wú)向圖中有n個(gè)極點(diǎn)，則該完滿(mǎn)無(wú)向圖中有（）條邊。n(n-1)/2n(n-1)n2n2-1答案:【A】38、設(shè)某無(wú)向圖有n個(gè)極點(diǎn)，則該無(wú)向圖的毗鄰表中有（）個(gè)

9、表頭結(jié)點(diǎn)。2nnn/2n(n-1)答案:【B】39、設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（）次。251071答案:【B】40、設(shè)二叉排序樹(shù)上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（）。O(n)O(n2)O(nlog2n)O(1og2n)-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-答案:【D】41、設(shè)一組初始記錄要點(diǎn)字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個(gè)長(zhǎng)度為2的有序子表，則用歸并排序的方法對(duì)該記錄要點(diǎn)字序列進(jìn)行一趟歸并后的結(jié)果為（）。15，25，35，50，20，40，80，85，36，7015，

10、25，35，50，80，20，85，40，70，3615，25，35，50，80，85，20，36，40，7015，25，35，50，80，20，36，40，70，85答案:【A】42、設(shè)輸入序列是1、2、3、n，經(jīng)過(guò)棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（）。A.n-iB.n-1-iC.n+1-iD.不能夠確定答案:【C】43、設(shè)輸入序列為1、2、3、4、5、6，則經(jīng)過(guò)棧的作用后能夠獲取的輸出序列為（）。5，3，4，6，1，23，2，5，6，4，13，1，2，5，4，61，5，4，6，2，3答案:【B】44、設(shè)某哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有（）個(gè)葉子結(jié)

11、點(diǎn)。99100101102答案:【B】45、設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有（）個(gè)結(jié)點(diǎn)。2k-12k2k-12k-1答案:【D】-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-46、設(shè)一棵三叉樹(shù)中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉樹(shù)中有（）個(gè)度數(shù)為0的結(jié)點(diǎn)。A.5B.6C.7D.8答案:【C】47、設(shè)某強(qiáng)連通圖中有n個(gè)極點(diǎn)，則該強(qiáng)連通圖中最少有（）條邊。n(n-1)n+1nn(n+1)答案:【C】48、算法必定具備輸入、輸出和計(jì)算方法排序方法解決問(wèn)題的有限運(yùn)算步驟程序設(shè)計(jì)方法答案:【C】49、圖G的某一最小生成樹(shù)的代價(jià)必然小于其他生成樹(shù)的代價(jià)

12、必然是必然不是不用然是都不對(duì)答案:【C】50、設(shè)一棵為Nm，則m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為m的結(jié)點(diǎn)數(shù)N0=（）。Nl+N2+Nml+N2+2N3+3N4+(m-1)NmN2+2N3+3N4+(m-1)Nm2Nl+3N2+(m+1)Nm答案:【B】51、下面程序的時(shí)間復(fù)雜度為（）for（i=1，s=0；i=n；i+）t=1；for(j=1；jright=s；s-left=p；p-right-left=s；s-right=p-right；B.s-left=p；s-right=p-right；p-right=s；p-right-left=s；C.p-right=s；

13、p-right-left=s；s-left=p；s-right=p-right；D.s-left=p；s-right=p-right；p-right-left=s；p-right=s；答案:【A】63、設(shè)依照從上到下、從左到右的次序從1開(kāi)始對(duì)完滿(mǎn)二叉樹(shù)進(jìn)行次序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（）。A.2i+1B.2iC.i/2D.2i-1答案:【B】64、設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k%P，則P平時(shí)情況下最好選擇（）。99979193答案:【B】64、二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為()。2k-12K+12K-12k-1答案:【D】65、設(shè)次序表的長(zhǎng)度為n，則次序查找的平均

14、比較次數(shù)為（）。nn/2-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-(n+1)/2(n-1)/2答案:【C】66、利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（）。O(n)O(nlog2n)O(n2)O(1og2n)答案:【C】67、以下四種排序中（）的空間復(fù)雜度最大。插入排序冒泡排序堆排序歸并排序答案:【D】68、設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是（）。head=0head-next=0head-next=headhead!=0答案:【A】69、若線性表最常用的操作是存取第i個(gè)元素的值，則采用_儲(chǔ)藏方式節(jié)約時(shí)間。單鏈表雙鏈表單循環(huán)鏈表次序表答案:【D】70、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（）。top=top+1;top=top-1;top-next=top;top=top-next;-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-答案:【D】71、在一個(gè)單鏈表中，若P所指節(jié)點(diǎn)不是最后節(jié)點(diǎn)，在P此后插入S所指節(jié)點(diǎn)，則執(zhí)行A.Snext=Pnext;Pnext=S;B.Pnext=Snext;Snext=P;C.Snext=P;Pnext=S;D.Pnext=S;Snext=P;答案:【A】72、深度為k的完滿(mǎn)二叉樹(shù)中最稀有（）個(gè)結(jié)點(diǎn)。2k-1-1