數(shù)據(jù)結(jié)構(gòu)模擬練習題+答案

數(shù)據(jù)結(jié)構(gòu)模擬練習題+答案一、單選題（共100題，每題1分，共100分）1.在對n個元素進行冒泡排序的過程中，最好情況下的時間復雜度為（）。A、O(n2)B、O(n)C、O(1)D、O(log2n)正確答案：B2.下列四種基本的邏輯結(jié)構(gòu)中，結(jié)構(gòu)結(jié)點間不存在任何邏輯聯(lián)系的是（）A、集合B、圖形結(jié)構(gòu)C、線性結(jié)構(gòu)D、樹形結(jié)構(gòu)正確答案：A3.在排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為()A、歸并排序B、希爾排序C、選擇排序D、插入排序正確答案：C4.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（）。A、算法B、存儲結(jié)構(gòu)C、邏輯結(jié)構(gòu)D、操作正確答案：C5.衡量查找算法效率的主要標準是（）。A、元素的個數(shù)B、所需的存儲量C、平均查找長度D、算法難易程度正確答案：C6.以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）。A、二叉樹B、有向圖C、線索二叉樹D、串正確答案：D7.下面程序的時間復雜為（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A、O(n4)B、O(n)C、O(n2)D、O(n3)正確答案：C8.已知一棵完全二叉樹有64個葉子結(jié)點，則該樹可能達到的最大深度為（）A、10B、7C、8D、9正確答案：C9.循環(huán)隊列是空隊列的條件是（）A、Q->front==0B、Q->rear==Q->frontC、Q->rear==0D、(Q->rear+1)%maxsize==Q->front正確答案：B10.假設有向圖含n個頂點及e條弧，則表示該圖的鄰接表中包含的弧結(jié)點個數(shù)為（）A、nB、n·eC、2eD、e正確答案：D11.對于一個線性表，若既要求能夠進行較快地插入和刪除，又要求存儲結(jié)構(gòu)能夠得出數(shù)據(jù)元素之間的關(guān)系，則應該以()。A、鏈式存儲B、索引方式存儲C、順序方式存儲D、散列方式存儲正確答案：A12.對于順序表來說，訪問任一節(jié)點的時間復雜度是（）A、O(1)B、O(log2n)C、O(n)D、O(n2)正確答案：A13.假設在構(gòu)建散列表時，采用線性探測解決沖突。若連續(xù)插入的n個關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時，所需進行的比較次數(shù)為()A、n-1B、n+2C、nD、n+l正確答案：C14.導致棧上溢的操作是()A、棧滿時執(zhí)行的出棧B、棧滿時執(zhí)行的入棧C、?？諘r執(zhí)行的入棧D、?？諘r執(zhí)行的出棧正確答案：B15.由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）A、48B、71C、53D、24正確答案：B16.假設一棵完全二叉樹按層次遍歷的順序依次存放在數(shù)組BT[m]中，其中根結(jié)點存放在BT[0]，若BT[i]中的結(jié)點有左孩子，則左孩子存放在()A、BT[i/2]B、BT[2*i-1]C、BT[2*i]D、BT[2*i+1]正確答案：D17.設森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為m1,m2和m3與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是()。A、m3B、m2C、m1+m2D、m2+m3正確答案：D18.在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為()。A、O(n)B、O(n／2)C、O(1)D、O(n2)正確答案：A19.在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為（）。A、front=rear->nextB、rear=front->nextC、front=front->nextD、rear=rear->next正確答案：C20.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為（）。A、（front+l）％n==rearB、(rear+l)％n==frontC、rear％n-1==frontD、rear％n==front正確答案：B21.有8個結(jié)點的無向連通圖最少有（）條邊。A、5B、8C、7D、6正確答案：C22.若對n個元素進行直接插入排序，則進行任一趟排序的過程中，為尋找插入位置而需要的時間復雜度為（）。A、O(n2)B、O(n)C、O(log2n)D、O(1)正確答案：B23.已知指針p和q分別指向某單鏈表中第一個結(jié)點和最后一個結(jié)點。假設指針s指向另一個單鏈表中某個結(jié)點，則在s所指結(jié)點之后插入上述鏈表應執(zhí)行的語句為()A、q->next=s->next；s->next=p；B、p->next=s->next；s->next=q;C、s->next=q；p->next=s->next；D、s->next=p；q->next=s->next；正確答案：A24.棧的數(shù)組表示中，top為棧頂指針，指向棧頂元素的下一個位置，?？盏臈l件是()。A、top=maxSizeB、top=-1C、top=maxSizeD、top=0正確答案：D25.棧和隊列()A、共同之處在于二者都是先進后出的特殊的線性表B、沒有共同之處C、共同之處在于二者都只允許在頂端執(zhí)行刪除操作D、共同之處在于二者都是先進先出的特殊的線性表正確答案：C26.?？梢栽?)中應用。A、遞歸調(diào)用B、子程序調(diào)用C、表達式求值D、A,B,C正確答案：D27.設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。A、2n-1B、nC、n-1D、2n正確答案：C28.設p指向單鏈表中的一個結(jié)點，s指向待插入的結(jié)點，則下述程序段的功能是（）s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A、在p所指結(jié)點的元素之后插入元素B、在p所指結(jié)點的元素之前插入元素C、結(jié)點*p與結(jié)點*s的數(shù)據(jù)域互換D、在結(jié)點*p之前插入結(jié)點*s正確答案：D29.若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現(xiàn)的出棧序列是()A、2，3，5，1，6，4B、4，3，2，1，5，6C、3，2，4，1，6，5D、2，4，3，1，5，6正確答案：A30.一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是()。A、abcdeB、edcbaC、decbaD、dceab正確答案：D31.對ｎ個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。（）A、元素基本有序B、從小到大排列好的C、從大到小排列好的D、元素無序正確答案：C32.從一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動的元素的個數(shù)是（）。A、n-i-1B、n-i+1C、n-iD、i正確答案：C33.若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點1開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為()。A、1,2,5,4,3B、1,4,3,2,5C、1,2,5,3,4D、1,2,3,4,5正確答案：A34.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（）A、冒泡排序B、插入排序C、希爾排序D、選擇排序正確答案：B35.從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（）A、線性結(jié)構(gòu)B、樹形結(jié)構(gòu)C、線性結(jié)構(gòu)和樹型結(jié)構(gòu)D、線性結(jié)構(gòu)和圖狀結(jié)構(gòu)正確答案：C36.設指針變量p指向單鏈表結(jié)點A，則刪除結(jié)點A的后繼結(jié)點B需要的操作為（）。A、p->next=p->next->nextB、p=p->nextC、p=p->next->nextD、p->next=p正確答案：A37.若最常用的操作是讀取線性表中元素的值，則采用()存儲方式最節(jié)省時間。A、帶尾指針的單鏈表B、順序表C、單鏈表D、帶尾指針的單循環(huán)鏈表正確答案：B38.含有10個結(jié)點的二叉樹中，度為0的結(jié)點數(shù)為4，則度為2的結(jié)點數(shù)為（）A、4B、5C、3D、6正確答案：C39.對一個滿二叉樹，m個樹葉，k個分枝結(jié)點，n個結(jié)點，則（）。A、m+1=2nB、m=k-1C、n=2k+1D、n=m+1正確答案：C40.鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是（）。A、刪除操作更加方便B、通常不會出現(xiàn)棧滿的情況C、不會出現(xiàn)棧空的情況D、插入操作更加方便正確答案：B41.在下列排序方法中，平均時間性能為O(nlogn)且空間性能最好的是()。A、歸并排序B、快速排序C、基數(shù)排序D、堆排序正確答案：D42.高度為h的完全二叉樹中，結(jié)點數(shù)最多為（）A、2^(h-1)B、2^h-1C、2^hD、2^h+1正確答案：B43.引起循環(huán)隊列隊頭位置發(fā)生變化的操作是()。A、出隊B、入隊C、取隊尾元素D、取隊頭元素正確答案：A44.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標依次為()A、1，2，3B、9，5，2，3C、9，5，3D、9，4，2，3正確答案：D45.數(shù)據(jù)的四種基本存儲結(jié)構(gòu)是指（）A、順序存儲結(jié)構(gòu)、非順序存儲結(jié)構(gòu)、指針存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)B、順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)C、順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、散列存儲結(jié)構(gòu)D、順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、直接存儲結(jié)構(gòu)、倒排存儲結(jié)構(gòu)正確答案：C46.鄰接矩陣為對稱矩陣的圖是()A、帶權(quán)有向圖B、無向圖C、有向圖D、有向圖或無向圖正確答案：D47.下面關(guān)于線性表的敘述錯誤的是（）。A、線性表采用順序存儲必須占用一片連續(xù)的存儲空間B、線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)C、線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間D、線性表采用順序存儲便于插入和刪除操作的實現(xiàn)正確答案：D48.深度為6（根的層次為1）的二叉樹至多有（）結(jié)點。A、64B、32C、63D、31正確答案：C49.設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。A、7B、1C、10D、25正確答案：C50.利用二叉鏈表存儲樹，則根結(jié)點的右指針是()。A、非空B、指向最左孩子C、空D、指向最右孩子正確答案：C51.在平均情況下速度最快的排序方法為（）。A、堆排序B、歸并排序C、快速排序D、簡單選擇排序正確答案：C52.若允許表達式內(nèi)多種括號混合嵌套，則為檢查表達式中括號是否正確配對的算法，通常選用的輔助結(jié)構(gòu)是（）。A、二叉排序樹B、隊列C、棧D、線性表正確答案：C53.隊列是一種（）的線性表。A、只能插入B、先進先出C、只能刪除D、先進后出正確答案：B54.在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為（）。A、2nB、2n+1C、2n-1D、不確定正確答案：C55.在順序表中，只要知道（），就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。A、結(jié)點大小B、向量大小C、基地址和結(jié)點大小D、基地址正確答案：C56.下面選項中，（）不是圖的存儲方法。A、孩子兄弟鏈表B、逆鄰接鏈表C、鄰接矩陣D、鄰接鏈表正確答案：A57.采用順序存儲結(jié)構(gòu)存儲的線性表，其首地址為100，每個元素的長度為2，則第5個元素的地址為()。A、120B、108C、110D、100正確答案：B58.某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A、空或只有一個結(jié)點B、高度等于其節(jié)點數(shù)C、任一結(jié)點無左孩子D、任一結(jié)點無右孩子正確答案：B59.數(shù)組的邏輯結(jié)構(gòu)不同于下列（）的邏輯結(jié)構(gòu)。A、線性表B、棧C、樹D、隊列正確答案：C60.下面程序段的時間復雜度為（）for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A、O(n2)B、O(m*n)C、O(m2)D、O(m+n)正確答案：B61.下列排序算法中，（）在某些特殊情況可能只需一趟排序即可完成。A、快速排序B、堆排序C、冒泡排序D、插入排序正確答案：C62.在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（）A、有序表B、棧C、線性表D、隊列正確答案：D63.深度為k的完全二叉樹中最少有（）個結(jié)點。A、2k-1-1B、2k-1+1C、2k-1D、2k-1正確答案：C64.若根據(jù)查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13計算哈希地址，則元素64的哈希地址為()。A、12B、4C、13D、8正確答案：A65.對于長度為n的順序表執(zhí)行刪除操作，則其結(jié)點的移動次數(shù)（）A、最少為0，最多為nB、最少為0，最多為n-1C、最少為1，最多為nD、最少為1，最多為n-1正確答案：B66.為了有效地利用散列查找技術(shù)，主要解決的問題是()。①找一個好的散列函數(shù)。②有效地解決沖突。③用整數(shù)表示關(guān)鍵值A、①和③B、②和③C、①②和③D、①和②正確答案：D67.對關(guān)鍵字序列(6，1，4，3，7，2，8，5)進行快速排序時，以第1個元素為基準的一次劃分的結(jié)果為（）A、(8，7，6，5，4，3，2，1)B、(5，1，4，3，6，2，8，7)C、(5，1，4，3，2，6，8，7)D、(5，1，4，3，2，6，7，8)正確答案：C68.下列程序段的漸進時間復雜度為（）for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)A[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、(m+n)正確答案：C69.已知一個順序存儲的線性表，設每個結(jié)點需占m個存儲單元，若第一個結(jié)點的地址為da1,則第I個結(jié)點的地址為（）。A、da1+(I-1)*mB、da1+(I+1)*mC、da1-I*mD、da1+I*m正確答案：A70.棧的插入和刪除操作在（）進行。A、任意位置B、棧頂C、指定位置D、棧底正確答案：B71.元素大小為1個單元，容量為n個單元的非空順序棧中，以地址高端為棧底，以top作為棧頂指針，則出棧處理后，top的值應修改為()A、top=top-1B、top=n-1C、top=top+1D、top=top正確答案：C72.數(shù)據(jù)在計算機內(nèi)有鏈式和順序兩種存儲方式，在存儲空間使用的靈活性上，鏈式存儲比順序存儲要（）。A、不好說B、相同C、低D、高正確答案：D73.對于二叉樹來說，第I層上至多有（）個節(jié)點。A、2^iB、2^(i-1)-1C、2^(i-1)D、2^i-1正確答案：C74.除第一層外，滿二叉樹中每一層結(jié)點個數(shù)是上一層結(jié)點個數(shù)的（）A、1倍B、1/2倍C、3倍D、2倍正確答案：D75.從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為（）。A、歸并排序B、插入排序C、希爾排序D、選擇排序正確答案：D76.for（i=0；i<m；i++）for（j=0；j<n；j++）A［i][j］=i*j；上面算法的時間復雜度為()A、O(m2)B、O(n2)C、O(m×n)D、O(m+n）正確答案：C77.含有n個結(jié)點的二叉樹采用二叉鏈表存儲時，空指針域的個數(shù)為（）A、n+2B、n-1C、nD、n+1正確答案：D78.對于有向圖，其鄰接矩陣表示相比鄰接表表示更易于進行的操作為（）A、求一個頂點的鄰接點B、廣度優(yōu)先遍歷C、求一個頂點的度D、深度優(yōu)先遍歷正確答案：A79.設某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（）。A、512B、1024C、256D、20正確答案：A80.設單鏈表中結(jié)點結(jié)構(gòu)為(data,link).已知指針q所指結(jié)點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s，則應執(zhí)行下列哪一個操作（）A、s->link=p->link;p->link=s;B、p->link=s->link;s->link=p;C、q->link=s;s->link=pD、p->link=s;s->link=q;正確答案：C81.在對n個元素進行直接插入排序的過程中，算法的空間復雜度為（）。A、O(nlog2n)B、O(1)C、O(n2)D、O(log2n)正確答案：B82.判定一個棧ST（最多元素為m0）為空的條件是A、ST->top<>m0B、ST->top=0C、ST->top=m0D、ST->top<>0正確答案：B83.在一個單鏈表中，若P所指結(jié)點不是最后結(jié)點，在P之后插入s所指結(jié)點，則執(zhí)行()。A、s->next=p->next;p=sB、s->next=p;p->next=sC、s->next=p->next;p->next=sD、p->next=s;s->next=p正確答案：C84.樹最適合用來表示（）。A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間無聯(lián)系的數(shù)據(jù)D、元素之間具有分支層次關(guān)系的數(shù)據(jù)正確答案：D85.3個結(jié)點可構(gòu)成（）棵不同形態(tài)的二叉樹。A、4B、5C、3D、2正確答案：B86.在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為144，它被均分為12子表，每個子表的長度均為12，則索引查找的平均查找長度為()。A、13B、79C、24D、12正確答案：A87.設一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（）A、a，b，d，cB、d，c，b，aC、c，d，a，bD、a，b，c，d正確答案：C88.在下面的程序段中，對x的賦值語句的頻度為（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(n)B、O(n^2)C、O(log2n)D、O(2^n)正確答案：B89.在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（）個。A、6B、4C、5D、7正確答案：A90.若要把n個頂點連接為一個連通圖，則至少需要()條邊。A、n+1B、nC、2nD、n-1正確