數(shù)據(jù)結構練習題庫與答案_第1頁
數(shù)據(jù)結構練習題庫與答案_第2頁
數(shù)據(jù)結構練習題庫與答案_第3頁
數(shù)據(jù)結構練習題庫與答案_第4頁
數(shù)據(jù)結構練習題庫與答案_第5頁
已閱讀5頁,還剩22頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

數(shù)據(jù)結構練習題庫與答案一、單選題(共100題,每題1分,共100分)1.樹形結構是數(shù)據(jù)元素之間存在一種()。A、多對多關系B、多對一關系C、一對多關系D、一對一關系正確答案:C2.設順序存儲的線性表共有123個元素,按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊,并在確定的塊中進行順序查找,則在查找概率相等的情況下,分塊查找成功時的平均查找長度為()。A、23B、62C、21D、41正確答案:A3.對于一個無向圖,下面()種說法是正確的。A、每個頂點的入度等于出度B、每個頂點的度等于其入度與出度之和C、每個頂點的入度為0D、每個頂點的出度為0正確答案:A4.一個向量第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的存儲地址是()A、120B、100C、108D、110正確答案:C5.哈夫曼樹中度為1的結點個數(shù)為()。A、1B、2C、0D、不確定正確答案:C6.在有n個葉子結點的哈夫曼樹中,其結點總數(shù)為()。A、2nB、不確定C、2n+1D、2n-1正確答案:D7.設某哈夫曼樹中有199個結點,則該哈夫曼樹中有()個葉子結點。A、101B、102C、99D、100正確答案:D8.設輸入序列是1、2、3、……、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序列中第i個輸出元素是()。A、n-1-IB、n-IC、n+1-ID、不能確定正確答案:C9.設森林F中有三棵樹,第一、第二和第三棵樹的結點個數(shù)分別為m1,m2和m3與森林F對應的二叉樹根結點的右子樹上的結點個數(shù)是()。A、m2B、m2+m3C、m3D、m1+m2正確答案:B10.向一個棧頂指針為hs的鏈棧中插入一個s結點時,應執(zhí)行()。A、s->next=hs;hs=s;B、s->next=hs;hs=hs->next;C、hs->next=s;D、s->next=hs->next;hs->next=s;正確答案:A11.在以單鏈表為存儲結構的線性表中,數(shù)據(jù)元素之間的邏輯關系用()A、數(shù)據(jù)元素的相鄰地址表示B、數(shù)據(jù)元素在表中的序號表示C、數(shù)據(jù)元素的值表示D、指向后繼元素的指針表示正確答案:D12.假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為f和r,則判斷隊空的條件為().A、f==0B、f+1==rC、f==rD、r+1==f正確答案:C13.對于含n個頂點和e條邊的圖,采用鄰接矩陣表示的空間復雜度為()A、O(n+e)B、O(e)C、O(n)D、O(n2)正確答案:D14.排序算法中,不穩(wěn)定的排序是()。A、冒泡排序B、直接插入排序C、選擇排序D、堆排序正確答案:D15.在下列排序方法中,平均時間性能為O(nlogn)且空間性能最好的是()。A、基數(shù)排序B、歸并排序C、快速排序D、堆排序正確答案:D16.對一個滿二叉樹,m個樹葉,k個分枝結點,n個結點,則()。A、n=2k+1B、m+1=2nC、n=m+1D、m=k-1正確答案:A17.設數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間,front為隊頭指針,rear為隊尾指針,則執(zhí)行出對操作后其頭指針front值為()。A、front=front+1B、front=(front+1)%mC、front=(front-1)%mD、front=(front+1)%(m-1)正確答案:B18.已知二叉樹的中序序列和后序序列均為ABCDEF,則該二叉樹的先序序列為()A、FEDCBAB、ABCDEFC、FDECBAD、FBDCEA正確答案:A19.以下數(shù)據(jù)結構中,哪一個是線性結構()。A、二叉樹B、串C、線索二叉樹D、有向圖正確答案:B20.順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為()。A、O(n1/2)B、O(1og2n)C、O(n2)D、O(n)正確答案:D21.順序棧S中top為棧頂指針,指向棧頂元素所在的位置,elem為存放棧的數(shù)組,則元素e進棧操作的主要語句為()。A、s.elem[top++]=e;s.top=s.top+1;B、s.top=s.top+1;s.elem[top+1]=e;C、s.elem[top]=e;s.top=s.top+1;D、s.top=s.top+1;s.elem[top]=e;正確答案:D22.一棵含18個結點的二叉樹的高度至少為()A、3B、5C、4D、6正確答案:B23.高度為h的完全二叉樹中,結點數(shù)最多為()A、2^h-1B、2^h+1C、2^hD、2^(h-1)正確答案:A24.數(shù)據(jù)在計算機存儲器內表示時,物理地址與邏輯地址不相同的,稱之為()。A、順序存儲結構B、存儲結構C、鏈式存儲結構D、邏輯結構正確答案:C25.設一組權值集合W={2,3,4,5,6},則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為()。A、45B、20C、40D、30正確答案:A26.具有n個結點的二叉樹,擁有指向孩子結點的分支數(shù)目是()A、n-1B、2nC、n+1D、n正確答案:A27.在長度為n的線性表中刪除一個指針p所指結點的時間復雜度是()A、O(n)B、O(1)C、O(log2n)D、O(n2)正確答案:A28.棧和隊列共同具有的特點是()A、都是先進后出B、只允許在端點進行操作運算C、既能先進先出,也能先進后出D、都是先進先出正確答案:B29.二叉樹的第k層的結點數(shù)最多為().A、2^(k-1)B、2k+1C、2k-1D、2^k-1正確答案:A30.對于一個有向圖,若一個頂點的度為k1,出度為k2,則對應鄰接表中該頂點單鏈表中的邊結點數(shù)為()。A、k1+k2B、k1-k2C、k1D、k2正確答案:D31.一個棧的輸入序列是12345,則下列序列中是棧的輸出序列的是()。A、5,4,1,3,2B、2,3,4,1,5C、3,1,2,4,5D、1,4,2,5,3正確答案:B32.在一個單鏈表中,若q所指結點是p所指結點的前驅結點,若在q與p之間插入一個s所指的結點,則執(zhí)行()。A、p→link=s→link;s→link=p;B、q→link=s;s→link=p;C、s→link=p→link;p→link=s;D、p→link=s;s→link=q;正確答案:B33.利用二叉鏈表存儲樹,則根結點的右指針是()。A、空B、非空C、指向最左孩子D、指向最右孩子正確答案:A34.從未排序序列中挑選元素,并將其依次插入已排序序列(初始時為空)的一端的方法,稱為()。A、選擇排序B、歸并排序C、希爾排序D、插入排序正確答案:A35.用二叉鏈表表示具有n個結點的二叉樹時,值為空的指針域的個數(shù)為()A、n+lB、nC、2nD、n-1正確答案:A36.由m棵結點數(shù)為n的樹組成的森林,將其轉化為一棵二叉樹,則該二叉樹中根結點的右子樹上具有的結點個數(shù)是()A、m(n-1)B、n(m-1)C、mnD、mn-1正確答案:B37.若進棧次序為a,b,c,且進棧和出??梢源┎暹M行,則可能出現(xiàn)的含3個元素的出棧序列個數(shù)是()A、7B、6C、3D、5正確答案:D38.對于二叉樹來說,第I層上至多有()個節(jié)點。A、2^(i-1)B、2^(i-1)-1C、2^iD、2^i-1正確答案:A39.在一個具有n個頂點和e條邊的有向圖的鄰接表中,保存頂點單鏈表的表頭指針向量的大小至少為()。A、nB、eC、2nD、2e正確答案:A40.下列排序算法中,在最好情況下,時間復雜度為O(n)的算法是()。A、歸并排序B、快速排序C、冒泡排序D、選擇排序正確答案:C41.若已知一個棧的入棧序列是1,2,3,4……n,其輸出序列為p1,p2,p3,……pn,若p1==n,則pi為()。A、n-i+1B、iC、不確定D、n==i正確答案:A42.下列排序方法中,屬于不穩(wěn)定的排序方法是()A、希爾排序B、歸并排序法C、冒泡排序法D、直接插入排序法正確答案:A43.如果在數(shù)據(jù)結構中每個數(shù)據(jù)元素只可能有一個直接前驅,但可以有多個直接后繼,則該結構是()A、樹B、棧C、圖D、隊列正確答案:A44.在一個長度為n的順序表中,向第i個元素(1≤i≤n+1)位置插入一個新元素時需要從后向前移動()個元素A、n-i-1B、n-i+1C、n-iD、i正確答案:B45.在按層次遍歷二叉樹的算法中,需要借助的輔助數(shù)據(jù)結構是()A、隊列B、棧C、有序表D、線性表正確答案:A46.鄰接矩陣為對稱矩陣的圖是()A、有向圖B、有向圖或無向圖C、帶權有向圖D、無向圖正確答案:B47.下面程序段的時間復雜度為()intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(n^2)B、O(1)C、O(n)D、O(n!)正確答案:C48.在一個非空二叉樹的中序遍歷序列中,根結點的右邊()。A、只有右子樹上的所有結點B、只有右子樹上的部分結點C、只有左子樹的上的部分結點D、只有左子樹上的所有結點正確答案:A49.關于二叉樹性質的描述,正確的是()A、二叉樹至少含有一個根結點B、二叉樹若存在兩個結點,則必有一個為根,另一個為左孩子C、二叉樹若存在三個結點,則必有一個為根,另兩個分別為左、右孩子D、二叉樹結點的個數(shù)可以為0正確答案:D50.求單鏈表中當前結點的后繼和前驅的時間復雜度分別是()A、O(1)和O(1)B、O(1)和O(n)C、O(n)和O(1)D、O(n)和O(n)正確答案:B51.在單鏈表中,存儲每個結點需要有兩個域,一個是數(shù)據(jù)域,另一個是指針域,指針域指向該結點的()A、開始結點B、直接后繼C、直接前趨D、終端結點正確答案:B52.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為()。A、O(m)B、O(1)C、O(n)D、O(m+n)正確答案:A53.設數(shù)組A[m]為循環(huán)隊列Q的存儲空間,front為隊頭指針,rear為隊尾指針,則判定Q為空隊列的條件是()A、(rear-front)%m==1B、front==rearC、(rear-front)%m==m-1D、front==(rear+1)%m正確答案:B54.將5個不同的數(shù)據(jù)進行排序,至多需要比較()次。A、8B、9C、10D、25正確答案:C55.有個頂點e條邊的無向圖G,它的鄰接表中的表結點總數(shù)是()。A、2nB、2eC、eD、n正確答案:B56.設一維數(shù)組中有n個數(shù)組元素,則讀取第i個數(shù)組元素的平均時間復雜度為()。A、O(nlog2n)B、O(n2)C、O(n)D、O(1)正確答案:D57.含有10個結點的二叉樹中,度為0的結點數(shù)為4,則度為2的結點數(shù)為()A、3B、5C、6D、4正確答案:A58.設指針變量p指向單鏈表中結點A,若刪除單鏈表中結點A,則需要修改指針的操作序列為()。A、q=p->next;p->data=q->data;p->next=q->next;free(q);B、q=p->next;q->data=p->data;p->next=q->next;free(q);C、q=p->next;p->next=q->next;free(q);D、q=p->next;p->data=q->data;free(q);正確答案:A59.棧和隊列都是()。A、順序存儲的線性結構B、鏈式存儲的線性結構C、限制存取位置的線性結構D、限制存取位置的非線性結構正確答案:C60.若<vi,vj>是有向圖的一條邊,則稱()A、vi與vj?不相鄰接B、vj鄰接于viC、vi鄰接于vjD、vi和vj相互鄰接正確答案:B61.線性表的順序存儲結構是一種()的存儲結構。A、索引存取B、隨機存取C、散列存取D、順序存取正確答案:B62.對于線性表(7,34,55,25,64,46,20,10)進行散列存儲時,若選用H(K)=K%9作為散列函數(shù),則散列地址為1的元素有()個.A、4B、2C、1D、3正確答案:A63.設有一個棧,元素的進棧次序為A,B,C,D,E,下列是不可能的出棧序列()。A、A,B,C,D,EB、B,C,D,E,AC、E,A,B,C,DD、E,D,C,B,A正確答案:C64.棧和隊列的共同特點是()。A、只允許在端點處插入和刪除B、都是先進后出C、沒有共同點D、都是先進先出正確答案:A65.在排序方法中,從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素進行比較,將其放入已排序序列的正確位置上的方法,稱為()A、冒泡排序B、快速排序C、希爾排序D、插入排序正確答案:D66.若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},則從頂點A開始對該圖進行廣度優(yōu)先搜索,得到的頂點序列可能為()。A、A,B,C,D,E,FB、A,B,C,F,D,EC、A,B,D,C,E,FD、A,C,B,F,D,E正確答案:D67.對包含n個元素的散列表進行搜索,平均搜索長度為()A、O(log2n)B、上述都不對C、不直接依賴于nD、O(n)正確答案:C68.衡量查找算法效率的主要標準是()。A、元素的個數(shù)B、所需的存儲量C、平均查找長度D、算法難易程度正確答案:C69.若采用孩子兄弟鏈表作為樹的存儲結構,則樹的后序遍歷應采用二叉樹的()A、前序遍歷算法B、中序遍歷算法C、后序遍歷算法D、層次遍歷算法正確答案:B70.在數(shù)據(jù)結構中,與所使用的計算機無關的是()。A、存儲結構B、物理結構C、邏輯結構D、邏輯結構和物理結構正確答案:C71.循環(huán)隊列A[0…m-1]存放其元素值,分別用front和rear表示隊頭和隊尾,則當前隊列的元素個數(shù)是()。A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front正確答案:A72.在一個單鏈表中,若p所指結點是q所指結點的前驅結點,則刪除結點q的正確操作是()A、p=q->nextB、p->next=q->next->nextC、p->next=qD、p->next=q->next正確答案:D73.一組記錄的排序碼為(46,79,56,38,40,84),則利用快速排序的方法,以第一個記錄為基準得到的第一次劃分結果為()。A、38,40,46,56,79,84B、40,38,46,84,56,79C、40,38,46,56,79,84D、40,38,46,79,56,84正確答案:C74.在數(shù)組A中,每一個數(shù)組元素A[i][j]占用3個存儲字,行下標i從1到8,列下標j從1到10。所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中,則存放該數(shù)組至少需要的存儲字數(shù)是()。A、80B、100C、240D、270正確答案:C75.散列查找中散列函數(shù)的值()散列地址的范圍。A、在B、小于C、無關D、大于正確答案:A76.采用線性鏈表表示一個向量時,要求占用的存儲空間地址()。A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、可連續(xù)可不連續(xù)D、一定是不連續(xù)的正確答案:C77.假設在構建散列表時,采用線性探測解決沖突。若連續(xù)插入的n個關鍵字都是同義詞,則查找其中最后插入的關鍵字時,所需進行的比較次數(shù)為()A、n-1B、n+2C、nD、n+l正確答案:C78.設連通圖G中的邊集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},則從頂點a出發(fā)不能得到一種深度優(yōu)先遍歷的頂點序列為()。A、acfebdB、aebdfcC、aedfcbD、abedfc正確答案:A79.下列排序算法中,()在某些特殊情況可能只需一趟排序即可完成。A、冒泡排序B、插入排序C、快速排序D、堆排序正確答案:A80.設有序順序表中有n個數(shù)據(jù)元素,則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過()。A、log2(n+1)B、log2nC、log2n+1D、log2n-1正確答案:C81.從邏輯關系來看,數(shù)據(jù)元素的直接前驅為0個或1個的數(shù)據(jù)結構只能是()A、線性結構和樹型結構B、線性結構和圖狀結構C、樹形結構D、線性結構正確答案:A82.設一組記錄的關鍵字key值為{62,50,14,28,19,35,47,56,83},散列函數(shù)為H(key)=keymod13,則它的開散列表中散列地址為1的鏈中的結點個數(shù)是()A、4B、1C、2D、3正確答案:B83.為了有效地利用散列查找技術,主要解決的問題是()。①找一個好的散列函數(shù)。②有效地解決沖突。③用整數(shù)表示關鍵值A、①和②B、②和③C、①和③D、①②和③正確答案:A84.在關鍵字序列(12,23,34,45,56,67,78,89,91)中二分查找關鍵字為45、89和12的結點時,所需進行的比較次數(shù)分別為()A、4,3,3B、3,3,4C、3,4,4D、4,4,3正確答案:A85.在索引查找中,若用于保存數(shù)據(jù)元素的主表的長度為144,它被均分為12子表,每個子表的長度均為12,則索引查找的平均查找長度為()。A、24B、12C、79D、13正確答案:D86.任何一棵二叉樹的葉子結點在先序、中序和后序遍歷序列中的相對次序()。A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對正確答案:A87.對待排序的元素序列進行劃分,將其分為左、右兩個子序列,再對兩個子序列進行同樣的排序操作,直到子序列為空或只剩下一個元素為止。這樣的排序方法是()。A、直接選擇排序B、冒泡排序C、快速排序D、直接插入排序正確答案:C88.設哈夫曼樹中的葉子結點總數(shù)為m,若用二叉鏈表作為存儲結構,則該哈夫曼樹中總共有()個空指針域。A、2m-1B、2m+1C、4mD、2m正確答案:D89.在下面的程序段中,對x的賦值語句的頻度為()。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(n^2)B、O(log2n)C、O(n)D、O(2^n)正確答案:A90.含有n個結點的二叉樹采用二叉鏈表存儲時,空指針域的個數(shù)為()A、

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論