數據結構習題（含參考答案）一、單選題（共100題，每題1分，共100分）1.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×n×t）B、O（m+n×t）C、O（m×t+n）D、O（m+n+t）正確答案：A2.在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結點的操作為（）。A、rear=rear->nextB、front=front->nextC、rear=front->nextD、front=rear->next正確答案：B3.設順序表有19個元素，第一個元素的地址為200，且每個元素占3個字節，則第14個元素的存儲地址為()A、236B、239C、245D、242正確答案：B4.有個頂點e條邊的無向圖G，它的鄰接表中的表結點總數是()。A、eB、2nC、nD、2e正確答案：D5.下列四種排序中（）的空間復雜度最大。A、快速排序B、冒泡排序C、堆D、希爾排序正確答案：A6.數據結構的定義為(D，S)，其中D是()的集合。A、算法B、數據元素C、數據操作D、邏輯結構正確答案：B7.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是()A、108B、100C、120D、110正確答案：A8.深度為k的二叉樹至多有()A、2^(k-1)-1個結點B、2^k-1個結點C、2^k個結點D、2^(k-1)個結點正確答案：B9.可以唯一地轉化成一棵一般樹的二叉樹的特點是（）A、根結點無左孩子B、根結點有兩個孩子C、根結點沒有孩子D、根結點無右孩子正確答案：D10.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（）。A、O(1)B、O(n)C、O(m+n)D、O(m)正確答案：D11.在下面的程序段中，對x的賦值語句的頻度為（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(log2n)B、O(n)C、O(2^n)D、O(n^2)正確答案：D12.假設以數組A[m]存放循環隊列的元素。已知隊列的長度為length，指針rear指向隊尾元素的下一個存儲位置，則隊頭元素所在的存儲位置為()A、(rear-length+m+1)％mB、(rear-length+m)％mC、(rear-length+m-1)％mD、(rear-length)％m正確答案：B13.在一棵二叉樹的二叉鏈表中，空指針域數等于非空指針域數加()。A、2B、1C、0D、-1正確答案：A14.若線性表最常用的操作是存取第i個元素及其前趨的值，那么最節省操作時間的存儲方式是（）A、順序表B、雙鏈表C、單鏈表D、單循環鏈表正確答案：A15.衡量查找算法效率的主要標準是（）。A、元素的個數B、所需的存儲量C、平均查找長度D、算法難易程度正確答案：C16.如果在數據結構中每個數據元素只可能有一個直接前驅，但可以有多個直接后繼，則該結構是（）A、棧B、圖C、隊列D、樹正確答案：D17.下列排序方法中，穩定的排序方法為（）A、希爾排序B、堆排序C、快速排序D、直接插入排序正確答案：D18.元素大小為1個單元，容量為n個單元的非空順序棧中，以地址高端為棧底，以top作為棧頂指針，則出棧處理后，top的值應修改為()A、top=topB、top=n-1C、top=top+1D、top=top-1正確答案：C19.由一個具有n個頂點的連通圖生成的最小生成樹中，具有()條邊。A、n-1B、nC、n+1D、2′n正確答案：A20.設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（）。A、2i+1B、2iC、i/2D、2i-1正確答案：B21.G是一個非連通無向圖，共有28條邊，則該圖至少有()個頂點。A、7B、8C、6D、9正確答案：D22.采用線性鏈表表示一個向量時，要求占用的存儲空間地址（）。A、部分地址必須是連續的B、一定是不連續的C、必須是連續的D、可連續可不連續正確答案：D23.在線性表的下列運算中，不改變數據元素之間結構關系的運算是（）A、刪除B、排序C、插入D、定位正確答案：D24.對關鍵字序列(6，1，4，3，7，2，8，5)進行快速排序時，以第1個元素為基準的一次劃分的結果為（）A、(5，1，4，3，6，2，8，7)B、(5，1，4，3，2，6，7，8)C、(8，7，6，5，4，3，2，1)D、(5，1，4，3，2，6，8，7)正確答案：D25.設單鏈表中結點結構為(data,link).已知指針q所指結點是指針p所指結點的直接前驅，若在*q與*p之間插入結點*s，則應執行下列哪一個操作（）A、q->link=s;s->link=pB、s->link=p->link;p->link=s;C、p->link=s->link;s->link=p;D、p->link=s;s->link=q;正確答案：A26.在一個有向圖的鄰接表中，每個頂點單鏈表中結點的個數等于該頂點的()。A、入邊數B、度數C、度數減1D、出邊數正確答案：D27.在一個非空二叉樹的中序遍歷序列中，根結點的右邊（）。A、只有右子樹上的所有結點B、只有右子樹上的部分結點C、只有左子樹的上的部分結點D、只有左子樹上的所有結點正確答案：A28.若采用鄰接矩陣存儲一個n個頂點的無向圖，則該鄰接矩陣是一個（）。A、上三角矩陣B、稀疏矩陣C、對角矩陣D、對稱矩陣正確答案：D29.在平均情況下速度最快的排序方法為（）。A、歸并排序B、快速排序C、堆排序D、簡單選擇排序正確答案：B30.在索引查找中，若用于保存數據元素的主表的長度為n，它被均分為k個子表，每個子表的長度均為n/k，則索引查找的平均查找長度為()。A、k+n/kB、n+kC、(k+n/k)/2D、(k+n/k)/2+1正確答案：D31.在一個單鏈表中,若q所指結點是p所指結點的前驅結點,若在q與p之間插入一個s所指的結點,則執行()。A、s→link=p→link;p→link=s;B、p→link=s→link;s→link=p;C、q→link=s;s→link=p;D、p→link=s;s→link=q;正確答案：C32.設一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現的是（）A、a，b，d，cB、a，b，c，dC、c，d，a，bD、d，c，b，a正確答案：C33.設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（）。A、20B、512C、1024D、256正確答案：B34.無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進行深度優先遍歷，得到的頂點序列正確的是（）。A、a,e,b,c,f,dB、a,b,e,c,d,fC、a,c,f,e,b,dD、a,e,d,f,c,b正確答案：D35.用散列函數求元素在散列表中的存儲位置時，可能會出現不同的關鍵字得到相同散列函數值的沖突現象。可用于解決上述問題的是()A、除留余數法B、折疊法C、平方取中法D、線性探測法正確答案：D36.用鄰接表表示圖進行深度優先遍歷時，通常是采用（）來實現算法的。A、樹B、圖C、棧D、隊列正確答案：C37.數據在計算機存儲器內表示時，物理地址與邏輯地址不相同的，稱之為（）。A、邏輯結構B、鏈式存儲結構C、存儲結構D、順序存儲結構正確答案：B38.在一個單鏈表中，若p所指結點不是最后結點，則刪除p所指結點的后繼結點的正確操作是()A、p->next=p->nextB、p->next=pC、p->next=p->next->nextD、p=p->next正確答案：C39.假設一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除預某個頂點vi相關的所有弧的時間復雜度是（）。A、O(e)B、O(n)C、O(n*e)D、O(n+e)正確答案：D40.在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執行()。A、p->link=s;s->link=p;B、s->link=p;p->link=s;C、s->link=p->link;p=s;D、s->link=p->link;p->link=s;正確答案：D41.具有n個結點的二叉樹，擁有指向孩子結點的分支數目是（）A、2nB、nC、n-1D、n+1正確答案：C42.在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（）。A、top--B、top=0C、top不變D、top++正確答案：A43.抽象數據類型的三個組成部分分別為（）A、數據元素、數據結構和數據類型B、數據對象、數據關系和基本操作C、數據項、數據元素和數據類型D、數據元素、邏輯結構和存儲結構正確答案：B44.在以單鏈表為存儲結構的線性表中，數據元素之間的邏輯關系用（）A、數據元素的值表示B、數據元素的相鄰地址表示C、指向后繼元素的指針表示D、數據元素在表中的序號表示正確答案：C45.3個結點可構成（）棵不同形態的二叉樹。A、4B、2C、3D、5正確答案：D46.對包含n個元素的散列表進行搜索，平均搜索長度為（）A、O（n）B、O（log2n）C、上述都不對D、不直接依賴于n正確答案：D47.如下陳述中正確的是（）A、串是一種特殊的線性表B、空串就是空白串C、串中元素只能是字母D、串的長度必須大于0正確答案：A48.在索引查找中，若用于保存數據元素的主表的長度為144，它被均分為12子表，每個子表的長度均為12，則索引查找的平均查找長度為()。A、12B、79C、24D、13正確答案：D49.循環隊列是空隊列的條件是（）A、Q->rear==0B、Q->rear==Q->frontC、(Q->rear+1)%maxsize==Q->frontD、Q->front==0正確答案：B50.在排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為()A、希爾排序B、歸并排序C、選擇排序D、插入排序正確答案：C51.某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A、空或只有一個結點B、高度等于其節點數C、任一結點無左孩子D、任一結點無右孩子正確答案：B52.導致棧上溢的操作是()A、棧空時執行的入棧B、棧空時執行的出棧C、棧滿時執行的出棧D、棧滿時執行的入棧正確答案：D53.設棧S和隊列Q的初始狀態為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應該是（）。A、3B、2C、6D、4正確答案：A54.對于任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點為n2.,則()A、n0=2n2+1B、n2=n0+1C、n0=n2+1D、n2=2n0+1正確答案：C55.除第一層外，滿二叉樹中每一層結點個數是上一層結點個數的（）A、2倍B、3倍C、1/2倍D、1倍正確答案：A56.用鏈接方式存儲的隊列，在進行插入運算時()。A、僅修改尾指針B、頭、尾指針可能都要修改C、頭、尾指針都要修改D、僅修改頭指針正確答案：B57.為了有效地利用散列查找技術，主要解決的問題是()。①找一個好的散列函數。②有效地解決沖突。③用整數表示關鍵值A、①和②B、①②和③C、①和③D、②和③正確答案：A58.設有n個結點的二叉樹上只有度為0和度為2的結點，則此二叉樹中葉子結點數()。A、不能確定B、（n+1)/2C、n/2D、(n-1)/2正確答案：B59.下面關于生成樹的描述中，不正確的是()A、生成樹是樹的一種表現形式B、生成樹一定是連通的C、生成樹一定不含有環D、若生成樹頂點個數為n，則其邊數一定為n-1正確答案：A60.棧上溢現象通常出現在（）A、順序棧的出棧操作過程中B、鏈棧的出棧操作過程中C、鏈棧的入棧操作過程中D、順序棧的入棧操作過程中正確答案：D61.下面程序段的時間復雜度為（）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)正確答案：C62.連通圖G中有n個頂點，G的生成樹是()的連通子圖。A、包含G的所有頂點B、不必包含G的所有頂點C、包含G的所有邊D、包含G的所有頂點和所有邊正確答案：A63.設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（）個空指針域。A、4mB、2m-1C、2m+1D、2m正確答案：D64.圖的深度、廣度優先遍歷算法分別類似于二叉樹的()。A、層序遍歷和先序遍歷B、先序遍歷和層序遍歷C、先序遍歷和中序遍歷D、后序遍歷和中序遍歷正確答案：B65.設以數組A[m]存放循環隊列的元素，其頭尾指針分別為front和rear，則當前隊列中的元素個數為（）。A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m正確答案：A66.對關鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為（）A、(5,16,2,12)28(32,60,72)B、(2,5,12,16)28(60,32,72)C、(5,16,2,12)28(60,32,72)D、(2,16,12,5)28(60,32,72)正確答案：C67.一個棧的輸入序列為1，2，3，…，n，設若輸出序列的第1個元素為n，輸出第i（1≤i≤n)個元素是()。A、n-i+1B、n-iC、iD、不確定正確答案：A68.算法分析的兩個主要方面是：A、數據復雜性和程序復雜性B、可讀性和文檔性C、空間復雜性和時間復雜性D、正確性和簡明性正確答案：C69.（）二叉排序樹可以得到一個從小到大的有序序列。A、后序遍歷B、層次遍歷C、先序遍歷D、中序遍歷正確答案：D70.數據的四種基本邏輯結構是指()A、數組、鏈表、樹、圖形結構B、線性表、鏈表、棧隊列、數組廣義表C、線性結構、鏈表、樹、圖形結構D、集合、線性結構、樹、圖形結構正確答案：D71.設一組記錄的關鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數為H(key)=keymod13，則它的開散列表中散列地址為1的鏈中的結點個數是（）A、3B、4C、1D、2正確答案：C72.若最常用的操作是讀取線性表中元素的值，則采用()存儲方式最節省時間。A、順序表B、帶尾指針的單循環鏈表C、單鏈表D、帶尾指針的單鏈表正確答案：A73.設單鏈表中指針p指向結點A，要刪除A之后的結點（若存在），則修改指針的操作為（）A、p->next=p->next->nextB、p=p->nextC、p=p->next->nextD、p->next=p正確答案：A74.某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF，則后序遍歷序列為（）A、BDGCEFHAB、GDBECFHAC、BDGAECHFD、GDBEHFCA正確答案：D75.數據的基本單位是（）A、數據項B、數據變量C、數據元素D、數據類型正確答案：C76.設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。A、nB、2nC、2n-1D、n-1正確答案：D77.若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點1開始對該圖進行深度優先搜索，得到的頂點序列可能為()。A、1,2,3,4,5B、1,2,5,4,3C、1,2,5,3,4D、1,4,3,2,5正確答案：B78.在一個長度為n的順序表中，向第i個元素（1≤i≤n+1)位置插入一個新元素時需要從后向前移動()個元素A、iB、n-i+1C、n-iD、n-i-1正確答案：B79.鏈式棧與順序棧相比，一個比較明顯的優點是（）。A、刪除操作更加方便B、不會出現棧空的情況C、通常不會出現棧滿的情況D、插入操作更加方便正確答案：C80.在按層次遍歷二叉樹的算法中，需要借助的輔助數據結構是（）A、有序表B、棧C、隊列D、線性表正確答案：C81.n個頂點的連通圖至少中含有()邊。A、0B、n-1C、nD、n+1正確答案：B82.以下數據結構中哪一個是非線性結構？()A、棧B、隊列C、二叉樹D、線性表正確答案：C83.設數組data[m]作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執行出對操作后其頭指針front值為（）。A、front=front+1B、front=(front-1)%mC、front=(front+1)%mD、front=(front+1)%(m-1)正確答案：C84.設數組A[m]為循環隊列Q的存儲空間，front為隊頭指針，rear為隊尾指針，則判定Q為空隊列的條件是()A、(rear-front)%m==1B、front==rearC、(rear-front)%m==m-1D、front==(rear+1)%m正確答案：B85.對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應鄰接表中該頂點單鏈表中的邊結點數為()。A、k1B、k2C、k1+k2D、k1-k2正確答案：B86.在待排關鍵字序列基本有序的前提下，效率最高的排序方法是()A、歸并排序B、直接選擇排序C、快速排序D、直接插入排序正確答案：D87.若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點A開始對該圖進行深度優先搜索，得到的頂點序列可能為()。A、A,B,C,F,D,EB、A,C,F,D,E,BC、A,B,D,C,F,ED、A,B,D,F,E,C正確答案：B88.在長度為32的有序表中進行二分查找時，所需進行的關鍵字比較次數最多為()A、6B、5C、7D、4正確答案：A89.一個數組元素a[i]與（）的表示等價。A、&a+iB、*（a+i）C、*a+ID、a+I正確答案：B90.下列關于線性表的敘述中，不正確的是()A、線性表的每一個結點有且僅有一個前趨和一個后繼B、線性表結點間的邏輯關系是1:1的聯系C、線性表可以為空表D、線性表是n個結點的有窮序列正確答案：A91.