在線網(wǎng)課知道知慧《數(shù)據(jù)結(jié)構(gòu)(山建大)》單元測(cè)試答案

第一章單元測(cè)試第二章單元測(cè)試第三章單元測(cè)試第四章單元測(cè)試第五章單元測(cè)試第六章單元測(cè)試第七章單元測(cè)試第八章單元測(cè)試第九章單元測(cè)試第十章單元測(cè)試第一章單元測(cè)試1【單選題】(2分)方法f1的時(shí)間復(fù)雜度是（）publicintf1(intn){intx=0;while(n>=(x+1)*(x+1)){x=x+1;}returnx;}A.O(n<sup1/2</sup)B.O(n)C.O(logn)D.O(n<sup2</sup)2【單選題】(2分)方法f2的時(shí)間復(fù)雜度是（）publicintf2(intn){inti=0;intsum=0;while(sum<n){sum+=++i;}returni;}A.O(n<sup1/2</sup)B.O(logn)C.O(n)D.O(nlogn)3【單選題】(2分)方法f3的時(shí)間復(fù)雜度是（）publicintf3(intn){intx=2;while(x<n/2){x=2*x;}returnx;}A.O(nlogn)B.O(n)C.O(n<sup2</sup)D.O(logn)4【單選題】(2分)方法f4的時(shí)間復(fù)雜度是（）publicintf4(intn){intcount=0;for(intk=1;k<=n;k*=2){for(intj=1;j<=n;j++){count++;}}returncount;}A.O(logn)B.O(n)C.O(n<sup2</sup)D.O(nlogn)5【單選題】(2分)記問題的規(guī)模n=a.length，方法f5的時(shí)間復(fù)雜度是（）publicvoidf5(int[]a,intx){intj=a.length;for(inti=0;i<a.length;i++){if(x>a[i]){j=i;break;}}for(inti=a.length;i>j;i--){a[i]=a[i-1];}a[j]=x;}A.O(n<sup2</sup)B.O(n)C.O(logn)D.O(nlogn)第二章單元測(cè)試1【單選題】(2分)數(shù)據(jù)對(duì)象是指（）A.性質(zhì)相同的數(shù)據(jù)元素的集合B.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合C.描述客觀事物且由計(jì)算機(jī)處理的數(shù)值、字符等符號(hào)的總稱D.數(shù)據(jù)的基本單位2.【多選題】正確答案：BCD數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容涉及（）A.算法用什么語言描述B.數(shù)據(jù)如何組織C.數(shù)據(jù)的運(yùn)算如何實(shí)現(xiàn)D.數(shù)據(jù)如何存儲(chǔ)3【判斷題】數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（）A.對(duì)B.錯(cuò)4【判斷題】數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)的表示和數(shù)據(jù)之間關(guān)系的表示。（）A.對(duì)B.錯(cuò)5【判斷題】如果使用Java語言描述，鏈?zhǔn)酱鎯?chǔ)是利用引用變量來表示數(shù)據(jù)之間的關(guān)系。（）A.對(duì)B.錯(cuò)第三章單元測(cè)試1【單選題】(2分)以下不是順序表特點(diǎn)的是（）。A.儲(chǔ)密度高B.插入和刪除操作需要移動(dòng)數(shù)據(jù)元素C.便于隨機(jī)存取D.無需預(yù)分配空間2【單選題】(2分)刪除順序表（共有n個(gè)數(shù)據(jù)元素）中第i（0≤i≤n-1）個(gè)數(shù)據(jù)元素時(shí)需要移動(dòng)（）個(gè)數(shù)據(jù)元素。A.n-i-1B.iC.n-i+1D.n-i3【單選題】(2分)在線性表中若經(jīng)常要存取第i個(gè)數(shù)據(jù)元素及其前驅(qū)，則宜采用（）存儲(chǔ)方式。A.循環(huán)單鏈表B.不帶頭結(jié)點(diǎn)的單鏈表C.帶頭結(jié)點(diǎn)的單鏈表D.順序表4【單選題】(2分)在一個(gè)有序單鏈表（含有n個(gè)結(jié)點(diǎn)）中插入一個(gè)新結(jié)點(diǎn)，使單鏈表仍然保持有序的算法的時(shí)間復(fù)雜度是（）。A.O（n<sup2</sup）B.O（1）C.O（n）D.O（log<sub2</subn）5【單選題】(2分)在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中的p結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)s，其修改鏈的Java語句序列是（）A.p.next=s;s.prior=p;p.next.prior=s;s.next=p.prior;B.p.next=s;p.next.prior=s;s.prior=p;s.next=p.next;C.s.prior=p;s.next=p.next;p.next=s;p.next.prior=s;D.s.next=p.next;s.prior=p;p.next.prior=s;p.next=s;第四章單元測(cè)試1【單選題】(2分)有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？（）。A.346521B.453126C.543612D.2341562【單選題】(2分)若一個(gè)棧的輸入序列為1,2,3,…,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（）。A.i-jB.i-j-1C.不確定D.j-i+13【單選題】(2分)若已知一個(gè)棧的入棧序列是1,2,3,…,n，其輸出序列為p<sub1</sub,p<sub2</sub,p<sub3</sub，…，p<subN</sub,若p<subN</sub是n，則p<subi</sub是（）。A.不確定B.iC.n-i+1D.n-i4【單選題】(2分)設(shè)有三個(gè)元素X，Y，Z順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到的出棧排列是（）。A.ZYXB.YZXC.XYZD.ZXY5【單選題】(2分)遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A.多維數(shù)組B.棧C.線性表D.隊(duì)列第五章單元測(cè)試1【單選題】(2分)用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。A.頭、尾指針可能都要修改B.僅修改頭指針C.頭、尾指針都要修改D.僅修改尾指針2【單選題】(2分)用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（）。A.僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭、隊(duì)尾指針都可能要修改3【判斷題】棧與隊(duì)列是一種特殊操作的線性表。（）A.對(duì)B.錯(cuò)4【判斷題】隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（）A.錯(cuò)B.對(duì)5【判斷題】通常使用隊(duì)列來處理函數(shù)或過程的調(diào)用。（）A.對(duì)B.錯(cuò)第六章單元測(cè)試1【單選題】(2分)在有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中有（）個(gè)空的指針域。A.nB.n+1C.0D.n-12【單選題】(2分)若某棵二叉樹的先根遍歷序列為ABCDEF,中根遍歷序列為CBDAEF,則這棵二叉樹的后根遍歷序列為（）。A.FEDCBAB.CDBFEAC.CDBEFAD.DCBEFA3【單選題】(2分)具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有度為2的結(jié)點(diǎn)有（）個(gè)A.11B.9C.10D.84【單選題】(2分)一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的深度為（）A.10至1024之間B.11C.11至1025之間D.105【單選題】(2分)利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（）。A.非空B.指向最右孩子C.指向最左孩子D.空第七章單元測(cè)試1【單選題】(2分)對(duì)有n個(gè)頂點(diǎn)，e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先搜索，其算法時(shí)間復(fù)雜度是（）A.O(n×e)B.O(n+e)C.O(e)D.O(n).2【單選題】(2分)設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊A.n(n+1)/2B.n<sup2</supC.n–1D.n(n-1)/23【單選題】(2分)使用鄰接表存儲(chǔ)圖所用的空間大?。ǎ〢.與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)B.與邊數(shù)的平方有關(guān)C.只與圖的頂點(diǎn)數(shù)有關(guān)D.只與圖的邊數(shù)有關(guān)4【單選題】(2分)用鄰接表存儲(chǔ)圖時(shí)，拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是（）A.O(n+e)B.O(n<sup2</sup)C.O(n×e)D.O(n)5【判斷題】為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了需要一個(gè)數(shù)組標(biāo)志已經(jīng)訪問過的結(jié)點(diǎn)外，還需要隊(duì)列。（）A.對(duì)B.錯(cuò)第八章單元測(cè)試1【單選題】(2分)已知一個(gè)長(zhǎng)度為16的順序表L，其元素按關(guān)鍵字有序排列。若采用二分查找法查找一個(gè)L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多是（）。A.5B.6C.4D.72【單選題】(2分)二分查找從100個(gè)有序整數(shù)中查找某數(shù)，最壞情況下需要比較的次數(shù)是（）。A.99B.50C.7D.103【單選題】(2分)若二叉搜索樹是有N個(gè)結(jié)點(diǎn)的完全二叉樹，則不正確的說法是（）。A.中位值結(jié)點(diǎn)在根結(jié)點(diǎn)或根的左子樹上B.最小值一定在葉結(jié)點(diǎn)上C.所有結(jié)點(diǎn)的平均查找效率是O(logN)D.最大值一定在葉結(jié)點(diǎn)上4【單選題】(2分)將{32,2,15,65,28,10}依次插入初始為空的二叉搜索樹。則該樹的前序遍歷結(jié)果是（）。A.32,2,15,10,28,65B.32,2,10,15,28,65C.52,10,15,28,32,65D.10,28,15,2,65,325【單選題】(2分)對(duì)二叉搜索樹進(jìn)行什么遍歷可以得到從小到大的排序序列？（）。A.層次遍歷B.中序遍歷C.后序遍歷D.前序遍歷第九章單元測(cè)試1【單選題】(2分)從待排序的序列當(dāng)中選出關(guān)鍵字值最大的記錄放到有序序列中，該排序方法稱為（）。A.直接選擇排序B.快速排序C.冒泡排序D.希爾排序2【單選題】(2分)當(dāng)待排序序列基本有序時(shí)，以下排序序列當(dāng)中最不利于其優(yōu)勢(shì)的發(fā)揮（）。A.直接插入排序B.直接選擇排序C.快速排序D.冒泡排序3【單選題】(2分)下面給出的4種排序算法中（）是不穩(wěn)定的排序A.冒泡排序B.堆排序C.2路歸并排序D.插入排序4【單選題】(2分)下列排序方法中，（）所需要的輔助空間最大。A.快速排序B.歸并排序C.希爾排序D.選擇排序5【判斷題】執(zhí)行排序操作時(shí)，根據(jù)使用的存儲(chǔ)器，可將排序算法分為內(nèi)排序和外排序。（）A.錯(cuò)B.對(duì)6【判斷題】若不考慮基數(shù)排序，則在排序過程中主要進(jìn)行的兩種基本操作是比較，移動(dòng)。（）A.錯(cuò)B.對(duì)第十章單元測(cè)試1【單選題】(2分)已知8個(gè)數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉搜索樹后，最后兩層上的結(jié)點(diǎn)總數(shù)為（）。A.4B.1C.3D.22【單選題】(2分)最小生成樹是指該樹中（）。A.帶權(quán)路徑長(zhǎng)度之和為最小B.一棵滿二叉樹C.所有邊的權(quán)值之和為最小D.所含結(jié)點(diǎn)個(gè)數(shù)最小3【單選題】(2分)使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點(diǎn)1到其他各頂點(diǎn)的最短路徑，依次得到的各最短路徑的目標(biāo)頂點(diǎn)是（）。A.5,2,3,6,4B.5,2,6,3,4C.5,2,4,3,6D.5,2,3,4,64【單選題】(2分)用一個(gè)有向圖來表示航空公司所有航班的航線。下列哪種算法最適合解決找給定兩城市間最經(jīng)濟(jì)的飛行路線問題？（）。A.拓?fù)渑判蛩惴˙.Kruskal算法C.Dijkstra算法D.深度優(yōu)先搜索5【單選題】(2分)Dijkstra算法用來解決哪個(gè)問題？（）A.字符串匹配B.最短路徑C.拓?fù)渑判駾.關(guān)鍵路徑6【判斷題】在n個(gè)結(jié)點(diǎn)的無向圖中，若邊數(shù)>n-1，則該圖必是連通圖。（）A.對(duì)B.錯(cuò)7【判斷題】鄰接表法只能用于有向圖的存儲(chǔ)，而鄰接矩陣法對(duì)于有向圖和無向圖的存儲(chǔ)都適用。（