智慧樹知道網(wǎng)課《數(shù)據(jù)結構(山東聯(lián)盟)》課后章節(jié)測試滿分答案

第一章測試1【單選題】(2分)數(shù)據(jù)在計算機內(nèi)存中的表示是指（）A.數(shù)據(jù)的邏輯結構B.數(shù)據(jù)的存儲結構C.數(shù)據(jù)元素之間的關系D.數(shù)據(jù)結構2【單選題】(2分)算法指的是（）A.計算機程序B.解決問題的有限運算序列C.排序算法D.解決問題的計算方法3【單選題】(2分)在數(shù)據(jù)結構中，與所使用的計算機無關的數(shù)據(jù)結構是（）A.邏輯結構和存儲結構B.邏輯結構C.存儲結構D.物理結構4【單選題】(2分)算法能正確地實現(xiàn)預定功能的特性稱為算法的（）。A.高效性B.可讀性C.健壯性D.正確性5【單選題】(4分)已知某算法的執(zhí)行時間為(n+n2)log2(n+2)，n為問題規(guī)模，則該算法的時間復雜度是（）。A.O((n+n2)logn)B.O(n2)C.O(n2logn)D.O(nlogn)6【單選題】(3分)下面算法將一維數(shù)組a中的數(shù)據(jù)逆序存放到原數(shù)組中，空間復雜度為（）。for(i=0;i<n;i++)b[i]=a[n-i-1];for(i=0;i<n;i++)a[i]=b[i];A.O(logn)B.O(1)C.O(n2)D.O(n)第二章測試1【單選題】(2分)鏈表不具備的特點是（）。A.所需空間與其長度成正比B.可隨機訪問任意一個結點C.插入和刪除不需要移動任何元素D.不必事先估計存儲空間2【判斷題】(2分)線性表的順序存儲表示優(yōu)于鏈式存儲表示。A.對B.錯3【判斷題】(2分)順序存儲結構的缺點是不便于修改,插入和刪除需要移動很多結點。A.錯B.對4【單選題】(2分)在設頭、尾指針的單鏈表中,與長度n有關的操作是()。A.在第一個結點之前插入一個結點B.刪除第一個結點C.在p結點之后插入一個結點D.刪除最后一個結點5【單選題】(2分)設指針q指向單鏈表中結點A,指針p指向單鏈表中結點A的后繼結點B,指針s指向被插入的結點X,則在結點A和結點B間插入結點X的操作序列為()。A.p->next=s;s->next=q;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.s->next=p->next;p->next=-s;6【單選題】(2分)對于只在表的首、尾兩端進行插入操作的線性表,宜采用的存儲結構為()。A.順序表B.用頭指針表示的循環(huán)單鏈表C.單鏈表D.用尾指針表示的循環(huán)單鏈表7【單選題】(2分)在一個單鏈表中,若p所指節(jié)點不是最后節(jié)點,在p之后插入s所指節(jié)點,則執(zhí)行()。A.s->link=p->link;p->link=s;B.s->link=p->link;p=s;C.p->link=s;s->link=p;D.s->link=p;p->link=s;8【單選題】(2分)在雙向鏈表存儲結構中,刪除p所指的結點時須修改指針()。A.p->prior->next=p;p->prior=p->prior->prior;B.p->next->prior=p->prior;p->prior->next=p->next;C.p->prior=p->next->next;p->next=p->prior->prior;D.p->next=p->next->next;p->next->prior=p;9【單選題】(2分)若事先不知道線性表的長度,則處理線性表時較好的存儲結構是()。A.順序表B.單鏈表C.靜態(tài)鏈表D.B和C10【單選題】(2分)向一個有127個元素的順序表中插入一個新元素并保存,原來順序不變,平均要移動()個元素。A.63.5B.7C.8D.6311【單選題】(2分)某線性表采用順序存儲結構,每個元素占4個存儲單元,首地址為100,則第12個元素的存儲地址為()。A.147B.144C.148D.14512【單選題】(2分)在一個以h為頭的單循環(huán)鏈表中,p指針指向鏈尾的條件是()。A.p->next==NULLB.p->next==hC.p->data==-1D.p->next->next==h13【單選題】(2分)在表頭指針為head且表長大于1的單向循環(huán)鏈表中,指針p指向表中的某個結點,若p->next->next=head,則()。A.*p的直接后繼是頭結點B.p指向頭結點C.*p的直接后繼是尾結點D.p指向尾結點14【單選題】(2分)線性表若采用鏈式存儲結構時,要求內(nèi)存中可用存儲單元的地址()。A.一定是不連續(xù)的B.必須是連續(xù)的C.部分地址必須是連續(xù)的D.連續(xù)不連續(xù)都可以15【單選題】(2分)在單鏈表中,指針p指向元素為x的結點,實現(xiàn)“刪除x的后繼”的語句是()。A.p=p->next->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next;16【單選題】(2分)可以用帶表頭結點的鏈表表示線性表,也可以用不帶表頭結點的鏈表表示線性表,前者最主要的好處是()。A.節(jié)省存儲空間B.可以加快對表的遍歷C.使空表和非空表的處理統(tǒng)一D.可以提高存取元素的速度17【單選題】(2分)與單鏈表相比,雙向鏈表的優(yōu)點之一是()。A.插入、刪除操作更加簡單B.可以隨機訪問C.可以省略表頭指針或表尾指針D.順序訪問相鄰結點更加靈活18【單選題】(2分)如果最常用的操作是取第i個結點及其前驅(qū),最節(jié)省時間的存儲方式()。A.單鏈表B.雙向鏈表C.順序表D.單循環(huán)鏈表19【單選題】(2分)線性鏈表不具有的特點是（）。A.插入與刪除時不必移動元素B.隨機訪問C.不必事先估計所需存儲空間大小D.所需空間與線性表長度成正比20【單選題】(2分)對順序存儲的線性表,設其長度為n,在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的()個元素。A.(n+1)/2B.nC.(n-1)/2D.n/221【判斷題】(2分)鏈表是采用鏈式存儲結構的線性表,進行插入、刪除操作時,在鏈表中比在順序存儲結構中效率高。A.錯B.對22【單選題】(2分)在一個帶頭結點的雙向循環(huán)鏈表中,若要在p所指向的結點之前插入一個新結點,則需要相繼修改()個指針域的值。A.2B.4C.5D.323【判斷題】(2分)具有線性關系的集合中，若a，b是集合中的任意兩個元素，則必有a<b的關系。<span=""></b的關系。<>A.錯B.對第三章測試1【單選題】(2分)設abcdef以所給次序進棧，若在進棧操作時允許退棧，則下列得不到的序列為（）A.fedcbaB.dcefbaC.cabdefD.bcafed2【單選題】(3分)若已知一個棧的進棧序列是1，2，3……n，其輸出序列是p1，p2，p3，pn，若p1=3，則p2為（）A.一定是2B.一定是1C.可能是2D.可能是13【單選題】(2分)假定循環(huán)隊列的隊首和隊尾指針分別為front和rear，則判斷隊滿的條件為（）。A.front+1==rearB.front==0C.(rear＋1)modMAXSIZE==frontD.front==rear4【判斷題】(2分)隊列和棧都是運算受限的線性表，只允許在表的兩端進行運算。A.錯B.對5【單選題】(2分)循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是()。A.rear-frontB.rear-front+1C.(rear-front+m)%mD.rear-front-16【判斷題】(3分)不論棧是用數(shù)組實現(xiàn)，還是用鏈表實現(xiàn)，入棧和出棧的時間復雜度均為O(n)。A.錯B.對7【單選題】(4分)若棧采用順序存儲方式存儲，兩棧共享空間A[1..m]，top[i]代表第i個棧（i=1,2）的棧頂，棧1的底在A[1]，棧2的底在A[m]，則棧滿的條件是（）。A.top[1]=top[2]B.top[1]+1=top[2]C.|top[2]-top[1]|=0D.top[1]+top[2]=m8【單選題】(4分)輸入序列為ABC，若出棧的順序為CBA時，經(jīng)過的棧操作為（）。A.push,push,push,pop,pop,popB.push,push,pop,pop,push,popC.push,pop,push,pop,push,popD.push,pop,push,push,pop,pop9【單選題】(2分)棧和隊都是（）。A.限制存取點的非線性結構B.順序存儲的線性結構C.鏈式存儲的非線性結構D.限制存取點的線性結構10【單選題】(4分)鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是（）。A.刪除操作更方便B.會出現(xiàn)?？盏那闆rC.插入操作更方便D.通常不會出現(xiàn)棧滿的情況11【單選題】(2分)設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結構最佳。A.線性表的順序存儲結構B.線性表的鏈式存儲結構C.隊列D.棧12【單選題】(4分)某隊列允許在其兩端進行入隊操作，但只允許在一端進行出隊操作，若有元素a,b,c,d,e依次入隊后再進行出隊操作，則不可能得到的出隊序列是（）。A.d,b,c,a,eB.d,b,a,c,eC.b,a,c,d,eD.e,c,b,a,d13【單選題】(4分)有如下遞歸算法：intfact(intn){//n大于等于0if(n<=0)return1;elsereturnn*fact(n-1);}則計算fact(n)需調(diào)用該函數(shù)的次數(shù)是（）。A.nB.n+2C.n-1D.n+114【單選題】(2分)棧在（）中有所應用。A.遞歸調(diào)用B.表達式求值C.前三個選項都有D.函數(shù)調(diào)用15【單選題】(2分)設有一個遞歸算法如下intfact(intn){//n大于等于0if(n<=0)return1;elsereturnn*fact(n-1);}則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。A.n-1B.n+2C.nD.n+116【單選題】(2分)（）的一個重要應用是在程序設計語言中實現(xiàn)遞歸。A.順序表B.數(shù)組C.隊列D.棧17【判斷題】(2分)只有那種使用了局部變量的遞歸過程在轉(zhuǎn)換成非遞歸過程時才必須使用棧。A.錯B.對18【判斷題】(2分)棧是實現(xiàn)過程和函數(shù)等子程序所必需的結構。A.錯B.對19【判斷題】(2分)通常使用隊列來處理函數(shù)或過程的調(diào)用。A.對B.錯20【判斷題】(2分)棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式A.對B.錯第四章測試1【單選題】(4分)設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第1個元素，其存儲地址為1，每個元素占用1個地址空間，則a85的地址為（）。A.13B.40C.18D.332【單選題】(3分)對于以行為主序的存儲結構來說．在數(shù)組A[c1..d1,c2..d2]中，c1和d1分別為數(shù)組A的第一維下標的下、上界，c2和d2分別為第二維下標的下、上界．每個數(shù)據(jù)元素占k個存儲單元，二維數(shù)組中任一元素a[i,j]的存儲位置可由（）確定。A.Loc[i,j]=[Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kB.Loc[i,j]=Loc[0,0]+[(d2-c2+1)(i-c1)+(j-c2)]×kC.Loc[i,j]=A[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kD.Loc[i,j]=[(d2-c2+1)(i-c1)+(j-c2)]×k3【單選題】(2分)A[N，N]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組T[N（N+1）/2]中，則對任一上三角元素a[i][j]對應T[k]的下標k是A.i（i-1）/2+jB.j（i-1）/2+1C.i（j-i）/2+1D.j（j-1）/2+i4【單選題】(2分)對矩陣壓縮存儲是為了（）A.提高運算速度B.方便存儲C.方便運算D.5【判斷題】(2分)操作取廣義表的表尾就是將廣義表中最后一個元素值返回。A.錯B.對6【判斷題】(2分)若廣義表S的表頭是空表，則S是一個空表。A.對B.錯7【單選題】(3分)下面說法不正確的是（）。A.廣義表的表尾總是一個廣義表B.廣義表難以用順序存儲結構實現(xiàn)C.廣義表可以看作是一個多層次結構D.廣義表的表頭總是一個廣義表第五章測試1【單選題】(2分)二叉樹是非線性數(shù)據(jù)結構，所以。A.它不能用順序存儲結構存儲B.順序存儲結構和鏈式存儲結構都不能使用C.順序存儲結構和鏈式存儲結構都能存儲D.它不能用鏈式存儲結構存儲2【判斷題】(2分)二叉樹中所有結點個數(shù)是2k-1-1，其中k是樹的深度。A.錯B.對3【判斷題】(2分)二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。A.錯B.對4【判斷題】(2分)在只有度為0和度為2的二叉樹中,設度為0的結點有n0個,度為2的結點有n2個,則有n0=n2+1。A.對B.錯5【判斷題】(2分)樹中所有結點的度之和等于所有結點數(shù)減1。A.錯B.對6【判斷題】(2分)設森林F中有4棵樹,第1、2、3、4棵樹的結點個數(shù)分別為n1、n2、n3、n4,當把森林F轉(zhuǎn)換成一棵二叉樹后,其根結點的左子樹中有n1個結點。A.對B.錯7【判斷題】(2分)設Huffman樹的葉子結點數(shù)為m,則結點總數(shù)為2m-1。A.錯B.對8【單選題】(2分)某二叉樹中序序列為BDAECF,后序序列為DBEFCA,則二叉樹對應的森林包括()棵樹。A.3B.1C.4D.29【單選題】(2分)若一棵二叉樹具有10個度為2的結點,5個度為1的結點,則度為0的結點的個數(shù)是()。A.不能確定B.9C.15D.1110【單選題】(2分)任何一棵二叉樹的葉子結點在前序、中序和后序遍歷序列中的相對次序()。A.不發(fā)生改變B.不能確定C.以上都不對D.發(fā)生改變11【單選題】(2分)設某棵二叉樹的高度為9,則該二叉樹上葉子結點最多有()。A.256B.511C.512D.102312【單選題】(2分)若完全二叉樹的結點個數(shù)為100,則第60個結點的度為()。A.不確定B.2C.1D.013【單選題】(2分)樹的基本遍歷策略分為先根遍歷和后根遍歷;二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里,我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應的二叉樹,其中結論()是正確的。A.樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同B.以上都不對C.樹的后根遍歷序列與其對應的二叉樹的后序遍歷序列相同D.樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同14【單選題】(2分)某二叉樹的先序和后序遍歷序列正好相反,則該二叉樹一定是()。A.深度等于其結點數(shù)B.完全二叉樹C.二叉排序樹D.空或只有一個結點15【單選題】(2分)一棵二叉樹的高度為h,所有結點的度或為0或為2,則這棵二叉樹最少有()個結點。A.2h+1B.2h-1C.h+1D.2h16【單選題】(2分)如果一棵二叉樹中所有結點的值都大于其左子樹中的所有結點的值,且小于其右子樹中所有結點的值,現(xiàn)欲得到各個結點的遞增序列,采用的方法是()。A.前序遍歷B.后序遍歷C.層次遍歷D.中序遍歷17【單選題】(2分)設n,m為一棵二叉樹上的兩個結點,在中序遍歷中,n在m前的條件是()。A.n是m的子孫B.n是m的祖先C.n在m右子樹上D.n在m的左子樹上18【單選題】(2分)深度為5的二叉樹至多有()個結點。A.32B.10C.16D.3119【單選題】(2分)由權值分別為11、8、6、2、5的葉子結點生成一棵哈夫曼樹,它的帶權路徑長度為()。A.24B.48C.53D.7120【單選題】(2分)如果一個完全二叉樹最底下一層為第六層(根為第一層)且該層共有8個葉結點,那么該完全二叉樹共有多少個結點?()A.71B.39C.31D.6321【單選題】(2分)某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF,則后序遍歷序列為（)。A.GDBEHFCAB.GDBECFHAC.BDGCEFHAD.BDGAECHF22【單選題】(2分)一個具有1025個結點的二叉樹的高h為()。A.11B.11至1025之間C.10D.10至1024之間23【單選題】(2分)設森林中有三棵樹,第一、二、三棵樹的結點個數(shù)分別為n1、n2、n3,那么將森林轉(zhuǎn)換成二叉樹后,其根結點的右子樹上有()個結點。A.n2+n3B.n1-1C.n1D.其他情況第六章測試1【單選題】(2分)任何一個無向連通圖的最小生成樹A.一棵或多棵B.可能不存在C.一定有多棵D.只有一棵2【單選題】(2分)用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用來實現(xiàn)算法的。A.圖B.樹C.隊列D.棧3【單選題】(2分)在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。A.1/2B.1C.2D.44【單選題】(4分)已知有向圖G=(V,E)，其中V={V1，V2，V3，V4，V5，V6，V7},E={<V1，V2>，<V1，V3>,<V1，V4>,<V2，V5>,<V3，V5>,<V3，V6>,<V4，V6>,<V5，V7>,<V6，V7>}，G的拓撲有序序列是（）。A.V1，V3，V4，V5，V2，V6，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V4，V6，V2，V5，V7D.V1，V2，V5，V3，V4，V6，V75【單選題】(4分)對于含有n個頂點的帶權連通圖，它的最小生成樹是指圖中任意一個（）。A.由n-1條權值之和最小的邊構成的子圖B.由n-1條權值之和最小的邊構成的連通子圖C.由n個頂點構成的邊的權值之和最小的連通子圖D.由n-1條權值最小的邊構成的子圖6【判斷題】(2分)用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間與圖中結點的個數(shù)有關，而與圖的邊數(shù)無關。A.錯B.對7【判斷題】(2分)如果有向圖的所有頂點可以構成一個拓撲排序，則說明該有向圖存在回路。A.錯B.對8【判斷題】(2分)一個非空圖可以沒有邊，但不能沒有頂點。A.錯B.對9【判斷題】(2分)有n-1條邊的圖肯定都是生成樹。A.錯B.對10【單選題】(2分)n個頂點的完全有向圖含有邊的數(shù)目是（）。A.n*nB.n(n-1)C.n(n+1)D.n/211【單選題】(4分)在有向圖的鄰接表存儲結構中，頂點v在鏈表中出現(xiàn)的次數(shù)是（）。A.頂點v的入度B.頂點v的出度C.依附于頂點v的邊數(shù)D.頂點v的度12【判斷題】(2分)對一個無向圖進行深度優(yōu)先搜索時，得到的搜索序列是唯一的。A.錯B.對13【單選題】(4分)G是一個非連通無向圖，有28條邊，則G至少有（）個頂點。A.8B.9C.7D.1014【單選題】(3分)對于一個有n個頂點，e條邊的有向圖，采用鄰接表存儲，對其進行廣度優(yōu)先搜索，算法的時間復雜度是（）。A.O(e)B.O(n+e)C.O(n)D.O(n*e)15【單選題】(3分)下列關于無向連通圖的敘述中，正確的是（）。所有頂點的度數(shù)之和是偶數(shù)邊數(shù)大于頂點數(shù)減1至少有一個頂點的度是1A.只有cB.a和cC.a和bD.只有a第七章測試1【單選題】(3分)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當用二分法查找值82的結點時，（）次比較后查找成功。A.4B.2C.8D.12【單選題】(2分)若根據(jù)查找表建立長度為m的哈希表，采用線性探測法處理沖突，假定對一個元素第一次計算的哈希地址為d，則下一次的哈希地址為()。A.dB.d+1C.(d+1)/mD.(d+1)%m3【單選題】(2分)若根據(jù)查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13計算哈希地址，則元素64的哈希地址為()。A.13B.4C.12D.84【單選題】(2分)從具有n個結點的二叉排序樹中查找一個元素時，在最壞情況下的時間復雜度為()。A.O(n2)B.O(log2n)C.O(1)D.O(n)5【單選題】(2分)對具有n個元素的有序表采用折半查找，則算法的時間復雜度為()。A.O(n)B.O(n2)C.O(1)D.O(logn)6【單選題】(2分)對于長度為18的順序存儲的有序表，若采用折半查找，則查找第15個元素的比較次數(shù)為()。A.4B.6C.3D.57【判斷題】(1分)二叉排序樹的左右子樹都是二叉排序樹。A.對B.錯8【單選題】(2分)若查找每個元素的概率相等，則在長度為n的順序表上查找任一元素的平均查找長度為()。A.(n-1)/2B.nC.n+1D.(n+1)/29【單選題】(2分)具有12個關鍵字的有序表，折半查找的平均查找長度是（）。A.2.5B.3.1C.5D.410【單選題】(3分)下面關于哈希查找的說法正確的是（）。A.若需要在一個哈希表中刪去一個元素，不管何種方法解決沖突都只要將該元素刪去即可B.哈希函數(shù)構造的越復雜越好，因為這樣隨機性好，沖突小C.除留余數(shù)法是所有哈希函數(shù)中最好的D.不存在特別好和特別壞的哈希函數(shù)，要視情況而定11【單選題】(2分)將10個元素散列到長度為100000的哈希表中，則（）產(chǎn)生沖突。A.一定會B.一定不會C.仍可能會12【判斷題】(2分)完全二叉樹肯定是平衡二叉樹。A.對B.錯13【單選題】(2分)查找n個元素的有序表時，最有效的查找方法是（）。A.折半查找B.順序查找C.二叉排序樹D.分塊查找14【單選題】(2分)當在一個有序順序存儲表中查找一個數(shù)據(jù)時，既可用折半查找，也可以用順序查找，但前者比后者的查找速度（）。A.一定快B.大部分情況下快C.取決于表遞增還是遞減D.一定慢15【判斷題】(2分)有n個數(shù)據(jù)存在在一維數(shù)組a中，進行順序查找時，這n個數(shù)據(jù)的排列有序或無序其平均查找長度不同。A.對B.錯16【判斷題】(2分)n個結點的二叉排序樹有多種形態(tài)，其中高度最小的二叉排序樹是最佳的。A.對B.錯17【單選題】(3分)假定有k個關鍵字互為同義詞，若用線性探測法把這k個關鍵字存入哈希表中，至少要進行（）次探測。A.kB.k+1C.k-1D.k(k+1)/2第八章測試1【單選題】(2分)如果對n個元素進行直接選擇排序，則進行任一趟排序的進程中，為尋找最小值元素所需要的時間復雜度為（）A.O(n)B.O(1)C.O(logn)D.O(n2)2【單選題】(3分)下列排序算法中，其中（）是穩(wěn)定的。A.快速排序，冒泡排序B.快速排序，堆排序C.簡單選擇排序，歸并排序D.歸并排序，冒泡排序3【單選題】(3分)下列序列中，（）是執(zhí)行第一趟快速排序后所得的序列。A.[93，38，18]49[27，73]B.[27，38，93]49[18，73]C.[27，38，73]49[93，18]D.[27，38，18]49[93，73]4【單選題】(3分)(15，9，7，8，20，-1，4)進行排序，第一趟排序后的序列變?yōu)?-1，9，7，8，20，15，4)，則采用的排序方法是（）。A.簡單選擇排序B.直接插入排序C.希爾排序D.快速排序5【單選題】(3分)從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的排序方法稱為（）。A.希爾排序B.選擇排序C.