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

數(shù)據(jù)結(jié)構(gòu)練習題與答案一、單選題（共100題，每題1分，共100分）1、順序查找法適用于存儲結(jié)構(gòu)為()的線性表。A、壓縮存儲B、順序存儲或鏈式存儲C、散列存儲D、索引存儲正確答案：B2、在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為144，它被均分為12子表，每個子表的長度均為12，則索引查找的平均查找長度為()。A、79B、24C、13D、12正確答案：C3、設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。A、2mB、2m-1C、4mD、2m+1正確答案：A4、設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。A、2nB、n-1C、2n-1D、n正確答案：B5、在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒有()A、左孩子結(jié)點B、右孩子結(jié)點C、左孩子結(jié)點和右孩子結(jié)點D、左孩子結(jié)點，右孩子結(jié)點和兄弟結(jié)點正確答案：C6、設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。A、線性結(jié)構(gòu)B、樹型結(jié)構(gòu)C、圖型結(jié)構(gòu)D、集合正確答案：C7、下列排序算法中，第一趟排序結(jié)束后其最大或最小元素一定在其最終位置上的算法是()。A、冒泡排序B、直接插入排序C、快速排序D、歸并排序正確答案：A8、假設(shè)以數(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正確答案：B9、在下面的程序段中，對x的賦值語句的頻度為（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(log2n)B、O(2^n)C、O(n^2)D、O(n)正確答案：C10、具有4個頂點的無向完全圖有()條邊。A、12B、20C、6D、16正確答案：C11、下面關(guān)于生成樹的描述中，不正確的是()A、生成樹是樹的一種表現(xiàn)形式B、生成樹一定是連通的C、生成樹一定不含有環(huán)D、若生成樹頂點個數(shù)為n，則其邊數(shù)一定為n-1正確答案：A12、樹中所有結(jié)點的度之和等于所有結(jié)點數(shù)加（）。A、2B、-1C、0D、1正確答案：B13、高度為5的完全二叉樹中含有的結(jié)點數(shù)至少為()A、32B、17C、16D、31正確答案：C14、對關(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，2，6，7，8)C、(5，1，4，3，2，6，8，7)D、(5，1，4，3，6，2，8，7)正確答案：C15、在下列對順序表進行的操作中，算法時間復雜度為O(1)的是（）A、訪問第i個元素的前驅(qū)（1<i<=n)B、刪除第i個元素(1<=i<=n)C、在第i個元素之后插入一個新元素(1<=i<=n)D、對順序表中元素進行排序正確答案：A16、已知一個順序存儲的線性表，設(shè)每個結(jié)點需占m個存儲單元，若第一個結(jié)點的地址為da1,則第I個結(jié)點的地址為（）。A、da1-I*mB、da1+(I-1)*mC、da1+I*mD、da1+(I+1)*m正確答案：B17、圖的鄰接矩陣表示法適用于表示（）A、稀疏圖B、稠密圖C、有向圖D、無向圖正確答案：B18、下面程序的時間復雜為（）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)正確答案：C19、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)；A、物理B、物理和存儲C、邏輯D、存儲正確答案：C20、已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為（）A、FEDCBAB、ABCDEFC、FDECBAD、FBDCEA正確答案：A21、散列查找是由鍵值（）確定散列表中的位置，進行存儲或查找。A、相反數(shù)B、散列函數(shù)值C、本身D、平方正確答案：B22、執(zhí)行一趟快速排序能夠得到的序列是（）。A、[12，27，45，41]55[34，63，72]B、[45，34，12，41]55[72，63，27]C、[41，12，34，45，27]55[72，63]D、[63，12，34，45，27]55[41，72]正確答案：C23、設(shè)有n個結(jié)點的二叉樹上只有度為0和度為2的結(jié)點，則此二叉樹中葉子結(jié)點數(shù)()。A、(n-1)/2B、（n+1)/2C、不能確定D、n/2正確答案：B24、設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。A、必須判別棧是否為滿B、必須判別棧是否為空C、判別棧元素的類型D、對棧不作任何判別正確答案：B25、散列查找中散列函數(shù)的值()散列地址的范圍。A、無關(guān)B、小于C、大于D、在正確答案：D26、設(shè)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正確答案：D27、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）正確答案：C28、數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址不相同的，稱之為（）。A、順序存儲結(jié)構(gòu)B、邏輯結(jié)構(gòu)C、鏈式存儲結(jié)構(gòu)D、存儲結(jié)構(gòu)正確答案：C29、設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（）。A、i/2B、2i+1C、2i-1D、2i正確答案：D30、對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是()A、35和41B、23和39C、25和51D、15和44正確答案：C31、計算機識別、存儲和加工處理的對象被統(tǒng)稱為()A、數(shù)據(jù)類型B、數(shù)據(jù)結(jié)構(gòu)C、數(shù)據(jù)D、數(shù)據(jù)元素正確答案：C32、在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為（）。A、(rear+l)％n==frontB、rear％n==frontC、rear％n-1==frontD、（front+l）％n==rear正確答案：A33、若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點1開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為()。A、1,4,2,5,3B、1,2,3,4,5C、1,2,4,3,5D、1,2,4,5,3正確答案：D34、在排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為()A、歸并排序B、選擇排序C、希爾排序D、插入排序正確答案：B35、設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹結(jié)點個數(shù)為n,森林F中第一棵子樹的結(jié)點個數(shù)是（）。A、m-nB、m-n-1C、n+1D、條件不足，無法確定正確答案：A36、對關(guān)鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結(jié)果為（）A、(2,5,12,16)28(60,32,72)B、(5,16,2,12)28(60,32,72)C、(5,16,2,12)28(32,60,72)D、(2,16,12,5)28(60,32,72)正確答案：B37、若線性表最常用的操作是存取第i個元素及其前趨的值，那么最節(jié)省操作時間的存儲方式是（）A、單循環(huán)鏈表B、順序表C、雙鏈表D、單鏈表正確答案：B38、順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進棧操作的主要語句為（）。A、s.top=s.top+1；s.elem［top+1］=e；B、s.top=s.top+1；s.elem［top］=e；C、s.elem［top++］=e；s.top=s.top+1；D、s.elem［top］=e；s.top=s.top+1；正確答案：B39、對于二叉樹來說，第I層上至多有（）個節(jié)點。A、2^iB、2^(i-1)C、2^i-1D、2^(i-1)-1正確答案：B40、下列查找算法中，平均查找長度與元素個數(shù)n不直接相關(guān)的查找方法是（）A、二分查找B、順序查找C、散列查找D、分塊查找正確答案：C41、一棵含18個結(jié)點的二叉樹的高度至少為()A、6B、3C、5D、4正確答案：C42、在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為()。A、O(n)B、O(n2)C、O(n／2)D、O(1)正確答案：A43、以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）。A、鏈表B、循環(huán)隊列C、哈希表D、棧正確答案：D44、具有n個結(jié)點的二叉樹，擁有指向孩子結(jié)點的分支數(shù)目是（）A、2nB、n-1C、n+1D、n正確答案：B45、一個棧的輸入序列為1，2，3，…，n，設(shè)若輸出序列的第1個元素為n，輸出第i（1≤i≤n)個元素是()。A、n-iB、n-i+1C、iD、不確定正確答案：B46、排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（）A、希爾排序B、歸并排序C、插入排序D、選擇排序正確答案：D47、若采用鄰接矩陣存儲一個n個頂點的無向圖，則該鄰接矩陣是一個（）。A、對角矩陣B、上三角矩陣C、稀疏矩陣D、對稱矩陣正確答案：D48、設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為（）。A、6B、7C、5D、8正確答案：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、從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為（）。A、選擇排序B、希爾排序C、歸并排序D、插入排序正確答案：A51、用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的。A、隊列B、樹C、圖D、棧正確答案：D52、無向圖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,e,b,c,f,dC、a,b,e,c,d,fD、a,c,f,e,b,d正確答案：A53、若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點1開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為()。A、1,2,5,4,3B、1,2,3,4,5C、1,2,5,3,4D、1,4,3,2,5正確答案：A54、帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（）。A、第i行非0的元素之和B、第i列非0的元素之和C、第i行非0的元素個數(shù)D、第i列非0的元素個數(shù)正確答案：D55、在對n個元素進行冒泡排序的過程中，最好情況下的時間復雜度為（）。A、O(1)B、O(n)C、O(log2n)D、O(n2)正確答案：B56、在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是()A、直接插入排序B、歸并排序C、快速排序D、直接選擇排序正確答案：A57、對于具有n個頂點的連通無向圖，其邊的個數(shù)至少為()。A、n+1B、nlog2nC、n-1D、n正確答案：C58、在等概率情況下，順序表的插入操作要移動（）結(jié)點。A、全部B、一半C、三分之一D、四分之一正確答案：B59、若允許表達式內(nèi)多種括號混合嵌套，則為檢查表達式中括號是否正確配對的算法，通常選用的輔助結(jié)構(gòu)是（）。A、棧B、隊列C、二叉排序樹D、線性表正確答案：A60、下列排序算法中，在最好情況下，時間復雜度為O(n)的算法是()。A、歸并排序B、快速排序C、冒泡排序D、選擇排序正確答案：C61、已知某二叉樹的后序遍歷序列是DABEC，中序遍歷序列是DEBAC，則其先序遍歷的結(jié)點訪問序列是()。A、ACBEDB、DECABC、DEABCD、CEDBA正確答案：D62、棧和隊列()A、共同之處在于二者都是先進先出的特殊的線性表B、共同之處在于二者都是先進后出的特殊的線性表C、沒有共同之處D、共同之處在于二者都只允許在頂端執(zhí)行刪除操作正確答案：D63、算法分析的兩個主要方面是：A、數(shù)據(jù)復雜性和程序復雜性B、可讀性和文檔性C、正確性和簡明性D、空間復雜性和時間復雜性正確答案：D64、鄰接矩陣為對稱矩陣的圖是()A、帶權(quán)有向圖B、有向圖C、無向圖D、有向圖或無向圖正確答案：D65、循環(huán)隊列是空隊列的條件是（）A、(Q->rear+1)%maxsize==Q->frontB、Q->front==0C、Q->rear==0D、Q->rear==Q->front正確答案：D66、若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則不可能出現(xiàn)的出棧序列是()A、3，2，4，1，6，5B、2，4，3，1，5，6C、2，3，5，1，6，4D、4，3，2，1，5，6正確答案：C67、對ｎ個不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。（）A、元素無序B、從大到小排列好的C、元素基本有序D、從小到大排列好的正確答案：B68、高度為h的完全二叉樹中，結(jié)點數(shù)最多為（）A、2^(h-1)B、2^h-1C、2^h+1D、2^h正確答案：B69、對于一個線性表，若既要求能夠進行較快地插入和刪除，又要求存儲結(jié)構(gòu)能夠得出數(shù)據(jù)元素之間的關(guān)系，則應(yīng)該以()。A、散列方式存儲B、順序方式存儲C、鏈式存儲D、索引方式存儲正確答案：C70、在一個具有n個結(jié)點的有序單鏈表插入一個新結(jié)點并仍然有序的時間復雜度是()。A、O(nlog2n)B、O(n)C、O(n2)D、O(1)正確答案：B71、下面程序段的時間復雜度為（）intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(1)B、O(n)C、O(n^2)D、O(n!)正確答案：B72、設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（）。A、1024B、256C、512D、20正確答案：C73、圖的深度、廣度優(yōu)先遍歷算法分別類似于二叉樹的()。A、先序遍歷和中序遍歷B、先序遍歷和層序遍歷C、層序遍歷和先序遍歷D、后序遍歷和中序遍歷正確答案：B74、邏輯上通?？梢詫?shù)據(jù)結(jié)構(gòu)分為（）A、順序結(jié)構(gòu)和鏈式結(jié)構(gòu)B、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C、初等結(jié)構(gòu)和組合結(jié)構(gòu)D、線性結(jié)構(gòu)和非線性結(jié)構(gòu)正確答案：D75、在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（）個。A、6B、5C、4D、7正確答案：A76、用二叉鏈表表示具有n個結(jié)點的二叉樹時，值為空的指針域的個數(shù)為()A、n+lB、2nC、n-1D、n正確答案：A77、設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（）。A、O(n2)B、O(nlog2n)C、O(1)D、O(n)正確答案：C78、在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為（）。A、front+l=rearB、rear==frontC、(rear+l)％n=frontD、rear％n==front正確答案：B79、可以唯一地轉(zhuǎn)化成一棵一般樹的二叉樹的特點是（）A、根結(jié)點無左孩子B、根結(jié)點沒有孩子C、根結(jié)點有兩個孩子D、根結(jié)點無右孩子正確答案：D80、當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（）A、n-1B、n+1C、nD、n-2正確答案：A81、設(shè)指針變量p指向單鏈表中結(jié)點A，若刪除單鏈表中結(jié)點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)；正確答案：A82、將5個不同的數(shù)據(jù)進行排序，至多需要比較（）次。A、10B、9C、8D、25正確答案：A83、對n個元素進行直接插入排序時間復雜度為（）。A、O(log2n)B、O(n2)C、O(n)D、O(1)正確答案：B84、有個頂點e條邊的無向圖G，它的鄰接表中的表結(jié)點總數(shù)是()。A、2nB、nC、2eD、e正確答案：C85、根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計算出該元素存儲地址的存儲方法是（）A、順序存儲方法B、鏈式存儲方法C、散列存儲方法D、索引存儲方法正確答案：C86、設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出對操作后其頭指針front值為（）。A、front=(front-1)%mB、front=(front+1)%(m-1)C、front=front+1D、front=(front+1)%m正確答案：D87、設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（）。A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m正確答案：A88、樹的先根序列等同于與該樹對應(yīng)的二叉樹的（）A、后序序列B、先序序列C、中序序列D、層序序列正確答案：B89、除根結(jié)點外，樹上每個結(jié)點()A、可有任意多個孩子、一個雙親B、可有一個孩子、任意多個雙親C、可有任意多個孩子、任意多個雙親D、只有一個孩子、一個雙親正確答案：A90、數(shù)據(jù)結(jié)構(gòu)中所定義的數(shù)據(jù)元素，是用于表示數(shù)據(jù)的（）A、最小單位B、不可分割的單位C、基本單位D、最大單位正確答案：C91、在一個長度為n的順序表中，向第i個元素（1≤i≤n+1)位置插入一個新元素時需要從后向前移動()個元素A、iB、n-i+1C、n-iD、n-i