數(shù)據(jù)結構考試模擬題與參考答案一、單選題（共100題，每題1分，共100分）1.具有35個結點的完全二叉樹的深度為()A、6B、8C、7D、5正確答案：A2.在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為()A、n-iB、IC、i+1D、n-i+1正確答案：A3.在一個有向圖的鄰接表中，每個頂點單鏈表中結點的個數(shù)等于該頂點的()。A、入邊數(shù)B、度數(shù)減1C、出邊數(shù)D、度數(shù)正確答案：C4.對于任何一棵二叉樹T，如果其終端結點數(shù)為n0，度為2的結點為n2.,則()A、n0=2n2+1B、n2=2n0+1C、n0=n2+1D、n2=n0+1正確答案：C5.關于二叉樹性質的描述，正確的是（）A、二叉樹若存在兩個結點，則必有一個為根，另一個為左孩子B、二叉樹至少含有一個根結點C、二叉樹結點的個數(shù)可以為0D、二叉樹若存在三個結點，則必有一個為根，另兩個分別為左、右孩子正確答案：C6.設結點A有3個兄弟結點且結點B為結點A的雙親結點，則結點B的度數(shù)數(shù)為（）。A、3B、4C、5D、1正確答案：B7.已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為（）A、FEDCBAB、ABCDEFC、FDECBAD、FBDCEA正確答案：A8.若根據(jù)查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7計算哈希地址，則哈希地址等于3的元素個數(shù)()。A、3B、1C、4D、2正確答案：D9.對n個元素進行直接插入排序時間復雜度為（）。A、O(log2n)B、O(n)C、O(n2)D、O(1)正確答案：C10.計算機識別、存儲和加工處理的對象被統(tǒng)稱為()A、數(shù)據(jù)結構B、數(shù)據(jù)元素C、數(shù)據(jù)類型D、數(shù)據(jù)正確答案：D11.下面程序段的時間復雜度為（）intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(1)B、O(n!)C、O(n)D、O(n^2)正確答案：C12.數(shù)據(jù)在計算機內有鏈式和順序兩種存儲方式，在存儲空間使用的靈活性上，鏈式存儲比順序存儲要（）。A、低B、不好說C、高D、相同正確答案：C13.設單鏈表中結點結構為(data,link).已知指針q所指結點是指針p所指結點的直接前驅，若在*q與*p之間插入結點*s，則應執(zhí)行下列哪一個操作（）A、s->link=p->link;p->link=s;B、p->link=s;s->link=q;C、p->link=s->link;s->link=p;D、q->link=s;s->link=p正確答案：D14.一個棧的輸入序列是12345，則下列序列中是棧的輸出序列的是（）。A、5,4,1,3,2B、2,3,4,1,5C、1,4,2,5,3D、3,1,2,4,5正確答案：B15.下面關于線性表的敘述錯誤的是（）。A、線性表采用順序存儲便于插入和刪除操作的實現(xiàn)B、線性表采用順序存儲必須占用一片連續(xù)的存儲空間C、線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間D、線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)正確答案：A16.對一個滿二叉樹，m個樹葉，k個分枝結點，n個結點，則（）。A、m+1=2nB、n=2k+1C、m=k-1D、n=m+1正確答案：B17.為使平均查找長度達到最小,當由關鍵字集合{05,11,21,25,37,40,41,62,84}構建二叉排序樹時,第一個插入的關鍵字應為（）A、62B、37C、41D、5正確答案：B18.如果F是由有序樹T轉換而來的二叉樹，那么T中結點的前序就是F中結點的（）。A、層次序B、前序C、后序D、中序正確答案：B19.在含有n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）。A、2eB、n2-2eC、eD、n2-e正確答案：B20.設一組記錄的關鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為H(key)=keymod13，則它的開散列表中散列地址為1的鏈中的結點個數(shù)是（）A、1B、2C、3D、4正確答案：A21.為了有效地利用散列查找技術，主要解決的問題是()。①找一個好的散列函數(shù)。②有效地解決沖突。③用整數(shù)表示關鍵值A、①和③B、②和③C、①②和③D、①和②正確答案：D22.將5個不同的數(shù)據(jù)進行排序，至多需要比較（）次。A、25B、9C、8D、10正確答案：D23.用二叉鏈表表示具有n個結點的二叉樹時，值為空的指針域的個數(shù)為()A、2nB、nC、n+lD、n-1正確答案：C24.在對n個元素進行冒泡排序的過程中，第一趟排序至多需要進行（）對相鄰元素之間的交換。A、nB、n-1C、n+1D、n/2正確答案：B25.長度為12的按關鍵字有序的查找表，采用順序組織方式。若采用折半查找方法，則在等概率情況下，查找失敗時的ASL值是()。A、Dec-37B、37/13C、Dec-49D、49/13正確答案：D26.某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF，則后序遍歷序列為（）A、BDGCEFHAB、GDBECFHAC、BDGAECHFD、GDBEHFCA正確答案：D27.在一個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動（）個元素。A、n-i-1B、iC、n-iD、n-i+l正確答案：C28.假設有向圖含n個頂點及e條弧，則表示該圖的鄰接表中包含的弧結點個數(shù)為（）A、eB、nC、2eD、n·e正確答案：A29.對于一組記錄的關鍵字值(25,38,63,74)，采用折半查找25時，()次查找成功。A、1B、2C、3D、4正確答案：B30.鄰接矩陣為對稱矩陣的圖是()A、有向圖或無向圖B、無向圖C、有向圖D、帶權有向圖正確答案：A31.在索引順序表中查找一個元素，可用的且最快的方法是（）。A、用順序查找方法確定元素所在塊，再用順序查找在相應塊中查找B、用二分查找方法確定元素所在塊，再用二分查找在相應塊中查找C、用二分查找方法確定元素所在塊，再用順序查找在相應塊中查找D、用順序查找方法確定元素所在塊，再用二分查找在相應塊中查找正確答案：C32.下列排序算法中，（）在某些特殊情況可能只需一趟排序即可完成。A、堆排序B、插入排序C、快速排序D、冒泡排序正確答案：D33.廣度優(yōu)先遍歷類似于二叉樹的（）。A、層次遍歷B、后序遍歷C、先序遍歷D、中序遍歷正確答案：A34.用鏈接方式存儲的隊列，在進行插入運算時()。A、僅修改頭指針B、僅修改尾指針C、頭、尾指針可能都要修改D、頭、尾指針都要修改正確答案：C35.在下面的程序段中，對x的賦值語句的頻度為（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(2^n)B、O(log2n)C、O(n^2)D、O(n)正確答案：C36.對于含n個頂點和e條邊的圖，采用鄰接矩陣表示的空間復雜度為（）A、O（n）B、O(e)C、O(n2)D、O(n+e)正確答案：C37.設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（）。A、O(nlog2n)B、O(n)C、O(1)D、O(n2)正確答案：C38.設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（）。A、1024B、256C、512D、20正確答案：C39.若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現(xiàn)的出棧序列是()A、2，3，5，1，6，4B、3，2，4，1，6，5C、4，3，2，1，5，6D、2，4，3，1，5，6正確答案：A40.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（）。A、O(m+n)B、O(n)C、O(1)D、O(m)正確答案：D41.判定一個棧ST（最多元素為m0）為空的條件是A、ST->top=0B、ST->top=m0C、ST->top<>m0D、ST->top<>0正確答案：A42.有個頂點e條邊的無向圖G，它的鄰接表中的表結點總數(shù)是()。A、2eB、nC、eD、2n正確答案：A43.下列四種排序中（）的空間復雜度最大。A、快速排序B、冒泡排序C、堆D、希爾排序正確答案：A44.若采用鄰接表存儲結構，則圖的深度優(yōu)先搜索類似于二叉樹的（）A、層次遍歷B、先根遍歷C、后根遍歷D、中根遍歷正確答案：B45.對于二叉樹來說，第I層上至多有（）個節(jié)點。A、2^i-1B、2^(i-1)C、2^iD、2^(i-1)-1正確答案：B46.從一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動的元素的個數(shù)是（）。A、n-i+1B、n-i-1C、iD、n-i正確答案：D47.假設以數(shù)組A[n]存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當前存于隊列中的元素個數(shù)為()A、(rear-front-1)％nB、(rear-front)％nC、(front-rear+1)％nD、(rear-front+n)％n正確答案：D48.一棵完全二叉樹上有1001個結點，其中葉子結點的個數(shù)是()。A、505B、501C、500D、254正確答案：B49.在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為()。A、nB、(n+1)/2C、(n-1)/2D、n/2正確答案：B50.與數(shù)據(jù)元素本身的形式、內容、相對位置、個數(shù)無關的是數(shù)據(jù)的（）。A、算法B、操作C、邏輯結構D、存儲結構正確答案：C51.在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為144，它被均分為12子表，每個子表的長度均為12，則索引查找的平均查找長度為()。A、24B、13C、79D、12正確答案：B52.若線性表最常用的操作是存取第i個元素及其前趨的值，那么最節(jié)省操作時間的存儲方式是（）A、單鏈表B、順序表C、雙鏈表D、單循環(huán)鏈表正確答案：B53.在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（）。A、top--B、top不變C、top++D、top=0正確答案：A54.下列查找算法中，平均查找長度與元素個數(shù)n不直接相關的查找方法是（）A、順序查找B、散列查找C、二分查找D、分塊查找正確答案：B55.設以數(shù)組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（）。A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m正確答案：A56.假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為f和r,則判斷隊空的條件為().A、f+1==rB、f==0C、r+1==fD、f==r正確答案：D57.求單鏈表中當前結點的后繼和前驅的時間復雜度分別是（）A、O(n)和O（n）B、O（1）和O（n）C、O（n）和O（1）D、O（1）和O（1）正確答案：B58.若允許表達式內多種括號混合嵌套，則為檢查表達式中括號是否正確配對的算法，通常選用的輔助結構是（）。A、棧B、線性表C、二叉排序樹D、隊列正確答案：A59.鏈表不具有的特點是（）。A、可隨機訪問任一元素B、所需空間與線性長度成正比C、不必事先估計存儲空間D、插入、刪除不需要移動元素正確答案：A60.for（i=0；i<m；i++）for（j=0；j<t；j++）c［i][j］=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；k++）c［i][j］=c［i][j］+a［i][k］*b［k][j］；上列程序的時間復雜度為（）A、O（m×t+n）B、O（m+n×t）C、O（m+n+t）D、O（m×n×t）正確答案：D61.已知一個順序存儲的線性表，設每個結點需占m個存儲單元，若第一個結點的地址為da1,則第I個結點的地址為（）。A、da1+(I-1)*mB、da1-I*mC、da1+(I+1)*mD、da1+I*m正確答案：A62.若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點1開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為()。A、1,2,4,3,5B、1,4,2,5,3C、1,2,4,5,3D、1,2,3,4,5正確答案：C63.設森林F中有三棵樹，第一、第二和第三棵樹的結點個數(shù)分別為m1,m2和m3與森林F對應的二叉樹根結點的右子樹上的結點個數(shù)是()。A、m1+m2B、m2C、m3D、m2+m3正確答案：D64.下面選項中，（）不是圖的存儲方法。A、鄰接矩陣B、逆鄰接鏈表C、孩子兄弟鏈表D、鄰接鏈表正確答案：C65.設數(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正確答案：B66.有關棧的描述，正確的是（）A、棧是一種先進先出的特殊的線性表B、只能從棧頂執(zhí)行插入、刪除操作C、只能從棧頂執(zhí)行插入、棧底執(zhí)行刪除D、棧頂和棧底均可執(zhí)行插入、刪除操作正確答案：B67.棧上溢現(xiàn)象通常出現(xiàn)在（）A、順序棧的入棧操作過程中B、鏈棧的入棧操作過程中C、鏈棧的出棧操作過程中D、順序棧的出棧操作過程中正確答案：A68.在一棵二叉樹上第4層的結點數(shù)最多為（）。A、4B、2C、8D、6正確答案：C69.（）二叉排序樹可以得到一個從小到大的有序序列。A、中序遍歷B、后序遍歷C、先序遍歷D、層次遍歷正確答案：A70.從一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功的情況下，需平均比較（）個元素結點。A、n/2B、（n+1）/2C、（n-1）/2D、n正確答案：B71.下面程序的時間復雜為（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A、O(n2)B、O(n4)C、O(n)D、O(n3)正確答案：A72.設指針變量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)；正確答案：A73.在下列對順序表進行的操作中，算法時間復雜度為O(1)的是（）A、在第i個元素之后插入一個新元素(1<=i<=n)B、刪除第i個元素(1<=i<=n)C、對順序表中元素進行排序D、訪問第i個元素的前驅（1<i<=n)正確答案：D74.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（）A、希爾排序B、歸并排序C、選擇排序D、插入排序正確答案：C75.數(shù)據(jù)的基本單位是（）A、數(shù)據(jù)變量B、數(shù)據(jù)項C、數(shù)據(jù)元素D、數(shù)據(jù)類型正確答案：C76.假設以數(shù)組A[m]存放循環(huán)隊列的元素。已知隊列的長度為length，指針rear指向隊尾元素的下一個存儲位置，則隊頭元素所在的存儲位置為()A、(rear-length+m+1)％mB、(rear-length+m)％mC、(rear-length+m-1)％mD、(rear-length)％m正確答案：B77.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。A、top=top-1;B、top=top+1;C、top->next=top;D、top=top->next;正確答案：D78.設順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為（）。A、62B、21C、41D、23正確答案：D79.對關鍵字序列(6，1，4，3，7，2，8，5)進行快速排序時，以第1個元素為基準的一次劃分的結果為（）A、(8，7，6，5，4，3，2，1)B、(5，1，4，3，2，6，8，7)C、(5，1，4，3，2，6，7，8)D、(5，1，4，3，6，2，8，7)正確答案：B80.已知一棵完全二叉樹的結點總數(shù)為9個，則最后一層的結點數(shù)為（）。A、3B、1C、4D、2正確答案：D81.采用順序存儲結構存儲的線性表，其首地址為100，每個元素的長度為2，則第5個元素的地址為()。A、108B、120C、110D、100正確答案：A82.對于順序表來說，訪問任一節(jié)點的時間復雜度是（）A、O(n)B、O(log2n)C、O(n2)D、O(1)正確答案：D83.判定一個隊列QU（最多元素為m0）為滿隊列的條件是()A、QU->front==QU->rearQU->front==(QU->rear+1)%m0B、QU->front==QU->rear+1C、QU->rear－QU->front－1==m0D、QU->rear－QU->front==m0正確答案：D84.下列關于線性表的敘述中，不正確的是()A、線性表結點間的邏輯關系是1:1的聯(lián)系B、線性表的每一個結點有且僅有一個前趨和一個后繼C、線性表可以為空表D、線性表是n個結點的有窮序列正確答案：B85.在一個具有n個頂點和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個數(shù)為()。A、2eB、nC、eD、ne正確答案：C86.對ｎ個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。（）A、從大到小排列好的B、元素基本有序C、從小到大排列好的D、元素無序正確答案：A87.線性表的順序存儲結構是一種（）的存儲結構。A、隨機存取B、順序存取C、散列存取D、索引存取正確答案：A88.已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行,則可能出現(xiàn)的出棧序列為（）A、2，3，5，6，1，4B、5，4，3，2，1，6C、3，2，5，4，1，6D、1，4，6，5，2，3正確答案：C89.具有n個頂點的無向圖，若要連通全部頂點，至少需要（）A、n(n-1)/2條邊B、（n-1）條邊C、n(n-1)條邊D、n條邊正確答案：B90.衡量查找算