數據結構題庫及參考答案

數據結構題庫及參考答案一、單選題（共100題，每題1分，共100分）1.設有n個結點的二叉樹上只有度為0和度為2的結點，則此二叉樹中葉子結點數()。A、n/2B、（n+1)/2C、不能確定D、(n-1)/2正確答案：B2.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（）。A、front->next=s；front=s；B、s->next=front；front=s；C、rear->next=s；rear=s；D、s->next=rear；rear=s；正確答案：C3.在一棵度為3的樹中，度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點數為（）個。A、7B、4C、6D、5正確答案：C4.采用順序存儲結構存儲的線性表，其首地址為100，每個元素的長度為2，則第5個元素的地址為()。A、120B、108C、110D、100正確答案：B5.下列關于線性表的敘述中，不正確的是()A、線性表的每一個結點有且僅有一個前趨和一個后繼B、線性表可以為空表C、線性表結點間的邏輯關系是1:1的聯系D、線性表是n個結點的有窮序列正確答案：A6.設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為（）。A、n，2eB、e，nC、n，eD、2n，e正確答案：A7.在一個單鏈表中,若q所指結點是p所指結點的前驅結點,若在q與p之間插入一個s所指的結點,則執(zhí)行()。A、p→link=s;s→link=q;B、s→link=p→link;p→link=s;C、p→link=s→link;s→link=p;D、q→link=s;s→link=p;正確答案：D8.圖的深度、廣度優(yōu)先遍歷算法分別類似于二叉樹的()。A、先序遍歷和層序遍歷B、后序遍歷和中序遍歷C、層序遍歷和先序遍歷D、先序遍歷和中序遍歷正確答案：A9.若對n個元素進行直接插入排序，則進行任一趟排序的過程中，為尋找插入位置而需要的時間復雜度為（）。A、O(n2)B、O(1)C、O(n)D、O(log2n)正確答案：C10.下面關于生成樹的描述中，不正確的是()A、生成樹是樹的一種表現形式B、生成樹一定是連通的C、生成樹一定不含有環(huán)D、若生成樹頂點個數為n，則其邊數一定為n-1正確答案：A11.連通圖G中有n個頂點，G的生成樹是()的連通子圖。A、包含G的所有頂點B、不必包含G的所有頂點C、包含G的所有邊D、包含G的所有頂點和所有邊正確答案：A12.如果在數據結構中每個數據元素只可能有一個直接前驅，但可以有多個直接后繼，則該結構是（）A、隊列B、圖C、樹D、棧正確答案：C13.在索引順序表中查找一個元素，可用的且最快的方法是（）。A、用順序查找方法確定元素所在塊，再用二分查找在相應塊中查找B、用順序查找方法確定元素所在塊，再用順序查找在相應塊中查找C、用二分查找方法確定元素所在塊，再用順序查找在相應塊中查找D、用二分查找方法確定元素所在塊，再用二分查找在相應塊中查找正確答案：C14.在一個具有n個頂點和e條邊的有向圖的鄰接表中，保存頂點單鏈表的表頭指針向量的大小至少為()。A、eB、nC、2nD、2e正確答案：B15.設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。A、2n-1B、n-1C、nD、2n正確答案：B16.具有4個頂點的無向完全圖有()條邊。A、16B、6C、20D、12正確答案：B17.設一組記錄的關鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數為H(key)=keymod13，則它的開散列表中散列地址為1的鏈中的結點個數是（）A、1B、2C、4D、3正確答案：A18.高度為h的完全二叉樹中，結點數最多為（）A、2^hB、2^h+1C、2^h-1D、2^(h-1)正確答案：C19.具有n個結點的二叉樹，擁有指向孩子結點的分支數目是（）A、n-1B、2nC、nD、n+1正確答案：A20.有8個結點的無向連通圖最少有（）條邊。A、8B、6C、5D、7正確答案：D21.在一個有向圖的鄰接表中，每個頂點單鏈表中結點的個數等于該頂點的()。A、入邊數B、出邊數C、度數減1D、度數正確答案：B22.棧和隊列共同具有的特點是（）A、都是先進后出B、都是先進先出C、只允許在端點進行操作運算D、既能先進先出，也能先進后出正確答案：C23.一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運行時間來看，通常遞歸過程比非遞歸過程（）。A、不定B、相同C、較快D、較慢正確答案：D24.在排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為()A、歸并排序B、希爾排序C、插入排序D、選擇排序正確答案：D25.在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執(zhí)行()。A、s->link=p->link;p=s;B、s->link=p->link;p->link=s;C、p->link=s;s->link=p;D、s->link=p;p->link=s;正確答案：B26.設棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應該是（）。A、6B、3C、2D、4正確答案：B27.若采用孩子兄弟鏈表作為樹的存儲結構，則樹的后序遍歷應采用二叉樹的（）A、中序遍歷算法B、后序遍歷算法C、前序遍歷算法D、層次遍歷算法正確答案：A28.長度為12的按關鍵字有序的查找表，采用順序組織方式。若采用折半查找方法，則在等概率情況下，查找失敗時的ASL值是()。A、Dec-37B、37/13C、Dec-49D、49/13正確答案：D29.深度為5的二叉樹至多有()個結點。A、31B、16C、10D、32正確答案：A30.隊和棧的主要區(qū)別是()A、限定插入和刪除的位置不同B、存儲結構不同C、所包含的運算個數不同D、邏輯結構不同正確答案：A31.設有一個遞歸算法如下：則計算fact(n)需要調用該函數的次數為（）。intfact(intn){/*大于等于0*/if(n<=0)return1;elsereturnn*fact(n-1);}A、n-1B、n+2C、nD、n+1正確答案：D32.數據的四種基本存儲結構是指（）A、順序存儲結構、非順序存儲結構、指針存儲結構、樹型存儲結構B、順序存儲結構、索引存儲結構、直接存儲結構、倒排存儲結構C、順序存儲結構、鏈式存儲結構、樹型存儲結構、圖型存儲結構D、順序存儲結構、索引存儲結構、鏈式存儲結構、散列存儲結構正確答案：D33.帶權有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（）。A、第i行非0的元素之和B、第i列非0的元素之和C、第i行非0的元素個數D、第i列非0的元素個數正確答案：D34.設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（）。A、1024B、256C、20D、512正確答案：D35.在一棵二叉樹上第4層的結點數最多為（）。A、8B、6C、4D、2正確答案：A36.深度為k的完全二叉樹中最少有（）個結點。A、2k-1B、2k-1C、2k-1+1D、2k-1-1正確答案：B37.在關鍵字序列(12，23，34，45，56，67，78，89，91)中二分查找關鍵字為45、89和12的結點時，所需進行的比較次數分別為()A、4，4，3B、3，3，4C、3，4，4D、4，3，3正確答案：D38.對于具有n個頂點的強連通圖，其弧條數的最小值為()。A、n-1B、nC、n-2D、n+1正確答案：B39.在對查找表的查找過程中，若被查找的數據元素不存在，則把該數據元素插入到集合中。這種方式主要適合于()A、靜態(tài)查找表或動態(tài)查找表B、靜態(tài)查找表C、靜態(tài)查找表與動態(tài)查找表D、動態(tài)查找表正確答案：D40.線性表的順序存儲結構是一種（）的存儲結構。A、隨機存取B、索引存取C、順序存取D、散列存取正確答案：A41.用散列函數求元素在散列表中的存儲位置時，可能會出現不同的關鍵字得到相同散列函數值的沖突現象?？捎糜诮鉀Q上述問題的是()A、線性探測法B、折疊法C、除留余數法D、平方取中法正確答案：A42.下列四種基本的邏輯結構中，結構結點間不存在任何邏輯聯系的是（）A、集合B、線性結構C、圖形結構D、樹形結構正確答案：A43.用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用（）來實現算法的。A、樹B、圖C、隊列D、棧正確答案：C44.若采用鄰接矩陣存儲一個n個頂點的無向圖，則該鄰接矩陣是一個（）。A、對稱矩陣B、稀疏矩陣C、上三角矩陣D、對角矩陣正確答案：A45.設p指向單鏈表中的一個結點，s指向待插入的結點，則下述程序段的功能是（）s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A、在p所指結點的元素之后插入元素B、在p所指結點的元素之前插入元素C、結點*p與結點*s的數據域互換D、在結點*p之前插入結點*s正確答案：D46.對一個滿二叉樹，m個樹葉，k個分枝結點，n個結點，則（）。A、n=m+1B、m=k-1C、m+1=2nD、n=2k+1正確答案：D47.若最常用的操作是讀取線性表中元素的值，則采用()存儲方式最節(jié)省時間。A、帶尾指針的單循環(huán)鏈表B、帶尾指針的單鏈表C、單鏈表D、順序表正確答案：D48.在一個具有n個頂點和e條邊的無向圖的鄰接表中，邊結點的個數為()。A、eB、2eC、neD、n正確答案：B49.若一個圖的邊集為{(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正確答案：D50.下面程序段的時間復雜度為（）intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(n!)B、O(n)C、O(n^2)D、O(1)正確答案：B51.散列查找是由鍵值（）確定散列表中的位置，進行存儲或查找。A、平方B、散列函數值C、相反數D、本身正確答案：B52.從邏輯上可以把數據結構分為（）.A、順序結構、鏈式結構B、動態(tài)結構、靜態(tài)結構C、線性結構、非線性結構D、初等結構、構造型結構正確答案：C53.棧的插入和刪除操作在（）進行。A、任意位置B、棧底C、棧頂D、指定位置正確答案：C54.對于二叉樹來說，第I層上至多有（）個節(jié)點。A、2^(i-1)-1B、2^(i-1)C、2^i-1D、2^i正確答案：B55.排序算法中，不穩(wěn)定的排序是（）。A、冒泡排序B、堆排序C、選擇排序D、直接插入排序正確答案：B56.在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間復雜度為()。A、O(n2)B、O(n+e)C、O(n)D、O(n3)正確答案：B57.n個頂點的連通圖至少中含有()邊。A、n+1B、0C、nD、n-1正確答案：D58.以下數據結構中，哪一個是線性結構（）。A、有向圖B、串C、二叉樹D、線索二叉樹正確答案：B59.與數據元素本身的形式、內容、相對位置、個數無關的是數據的（）。A、操作B、存儲結構C、邏輯結構D、算法正確答案：C60.若要把n個頂點連接為一個連通圖，則至少需要()條邊。A、n-1B、nC、2nD、n+1正確答案：A61.下面程序段的時間復雜度為()s=0；for(i=1；i<n；i++)for(j=1；j<i；j++)s+=i*j；A、O(n)B、O(n2)C、O(logn)D、O(1)正確答案：B62.含有10個結點的二叉樹中，度為0的結點數為4，則度為2的結點數為（）A、6B、3C、5D、4正確答案：B63.為了有效地利用散列查找技術，主要解決的問題是()。①找一個好的散列函數。②有效地解決沖突。③用整數表示關鍵值A、①和③B、②和③C、①②和③D、①和②正確答案：D64.對關鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為（）A、(2,5,12,16)28(60,32,72)B、(2,16,12,5)28(60,32,72)C、(5,16,2,12)28(32,60,72)D、(5,16,2,12)28(60,32,72)正確答案：D65.棧的兩種常用存儲結構分別為()A、順序存儲結構和散列存儲結構B、鏈式存儲結構和索引存儲結構C、順序存儲結構和鏈式存儲結構D、鏈式存儲結構和散列存儲結構正確答案：C66.設順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為（）。A、21B、41C、23D、62正確答案：C67.下面選項中，（）不是圖的存儲方法。A、孩子兄弟鏈表B、鄰接矩陣C、鄰接鏈表D、逆鄰接鏈表正確答案：A68.無向圖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)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（）。A、a,e,d,f,c,bB、a,b,e,c,d,fC、a,c,f,e,b,dD、a,e,b,c,f,d正確答案：A69.在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數，假定查找每個元素的概率都相等）為()。A、(n+1)/2B、nC、(n-1)/2D、n/2正確答案：A70.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）正確答案：C71.在順序表中，只要知道（），就可在相同時間內求出任一結點的存儲地址。A、向量大小B、基地址和結點大小C、基地址D、結點大小正確答案：B72.深度為k的二叉樹至多有()A、2^(k-1)個結點B、2^(k-1)-1個結點C、2^k個結點D、2^k-1個結點正確答案：D73.如果在排序過程中，每次均將一個待排序的記錄按關鍵字大小加入到前面已經有序的子表中的適當位置，則該排序方法稱為（）A、插入排序B、冒泡排序C、堆排序D、歸并排序正確答案：A74.圖的鄰接矩陣表示法適用于表示（）A、有向圖B、稠密圖C、無向圖D、稀疏圖正確答案：B75.已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針s指向另一個單鏈表中某個結點，則在s所指結點之后插入上述鏈表應執(zhí)行的語句為()A、s->next=p；q->next=s->next；B、q->next=s->next；s->next=p；C、p->next=s->next；s->next=q;D、s->next=q；p->next=s->next；正確答案：B76.設某無向圖有n個頂點，則該無向圖的鄰接表中有（）個表頭結點。A、n(n-1)B、2nC、nD、n/2正確答案：C77.衡量查找算法效率的主要標準是（）。A、元素的個數B、所需的存儲量C、平均查找長度D、算法難易程度正確答案：C78.對于具有n個頂點的連通無向圖，其邊的個數至少為()。A、n+1B、nC、n-1D、nlog2n正確答案：C79.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。A、top=top+1;B、top=top->next;C、top=top-1;D、top->next=top;正確答案：B80.設有一個棧，按A、B、C、D的順序進棧，則可能為出棧序列的是()A、DCBAB、CDABC、DBACD、DCAB正確答案：A81.假設一棵完全二叉樹按層次遍歷的順序依次存放在數組BT[m]中，其中根結點存放在BT[0]，若BT[i]中的結點有左孩子，則左孩子存放在()A、BT[i/2]B、BT[2*i-1]C、BT[2*i]D、BT[2*i+1]正確答案：D82.在排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為()A、快速排序B、插入排序C、冒泡排序D、希爾排序正確答案：B83.數據的基本單位是（）A、數據項B、數據類型C、數據變量D、數據元素正確答案：D84.設單鏈表中結點結構為(data,link).若想摘除結點*p的直接后繼，則應執(zhí)行下列哪一個操作（）A、p=p->link;p->link=p->link->link;B、p->link=p->link->link;C、p=p->link->link;D、p->link=p->link;正確答案：B85.設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（）。A、6B、7C、5D、8正確答案：B86.設指針變量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)；正確答案：A87.已知一個順序存儲的線性表，設每個結點需占m個存儲單元，若第一個結點的地址為da1,則第I個結點的地址為（）。A、da1+(I+1)*mB、da1-I*mC、da1+I*mD、da1+(I-1)*m正確答案：D88.3個結點可構成（）棵不同形態(tài)的二叉樹。A、4B、2C、5D、3正確答案：C89.在含有n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數為（）。A、n2-eB、n2-2eC、2eD、e正確答案：B90.有個頂點e條邊的無向圖G，它的鄰接表中的表結點總數是()。A、2eB、2nC、nD、e正確答案：A91.樹最適合用來表示（）。A、有序數據元素B、元素之間無聯系的數據C、元素之間具有分支層次關