數(shù)據(jù)結(jié)構(gòu)?？荚囶}及答案

數(shù)據(jù)結(jié)構(gòu)模考試題及答案一、單選題（共100題，每題1分，共100分）1、下面關(guān)于生成樹的描述中，不正確的是()A、生成樹是樹的一種表現(xiàn)形式B、生成樹一定是連通的C、生成樹一定不含有環(huán)D、若生成樹頂點(diǎn)個數(shù)為n，則其邊數(shù)一定為n-1正確答案：A2、用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用（）來實(shí)現(xiàn)算法的。A、圖B、棧C、隊列D、樹正確答案：C3、下列四種基本的邏輯結(jié)構(gòu)中，結(jié)構(gòu)結(jié)點(diǎn)間不存在任何邏輯聯(lián)系的是（）A、集合B、樹形結(jié)構(gòu)C、圖形結(jié)構(gòu)D、線性結(jié)構(gòu)正確答案：A4、以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）。A、線索二叉樹B、二叉樹C、有向圖D、串正確答案：D5、n個頂點(diǎn)的連通圖至少中含有()邊。A、n-1B、n+1C、nD、0正確答案：A6、G是一個非連通無向圖，共有28條邊，則該圖至少有()個頂點(diǎn)。A、7B、8C、6D、9正確答案：D7、在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點(diǎn)的操作為（）。A、rear=front->nextB、front=rear->nextC、front=front->nextD、rear=rear->next正確答案：C8、一個棧的輸入序列是12345，則下列序列中是棧的輸出序列的是（）。A、1,4,2,5,3B、3,1,2,4,5C、2,3,4,1,5D、5,4,1,3,2正確答案：C9、假設(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正確答案：B10、與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（）。A、存儲結(jié)構(gòu)B、操作C、邏輯結(jié)構(gòu)D、算法正確答案：C11、深度為k的完全二叉樹中最少有（）個結(jié)點(diǎn)。A、2k-1B、2k-1C、2k-1+1D、2k-1-1正確答案：A12、邏輯上通?？梢詫?shù)據(jù)結(jié)構(gòu)分為（）A、順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)B、初等結(jié)構(gòu)和組合結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)正確答案：C13、排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（）。A、快速排序B、冒泡排序C、插入排序D、選擇排序正確答案：C14、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（）。A、第i行非0元素的個數(shù)之和B、第i列非0元素的個數(shù)之和C、第i行0元素的個數(shù)之和D、第i列0元素的個數(shù)之和正確答案：B15、由一個具有n個頂點(diǎn)的連通圖生成的最小生成樹中，具有()條邊。A、n+1B、nC、2′nD、n-1正確答案：D16、循環(huán)隊列是空隊列的條件是（）A、(Q->rear+1)%maxsize==Q->frontB、Q->rear==0C、Q->front==0D、Q->rear==Q->front正確答案：D17、數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指()A、線性結(jié)構(gòu)、鏈表、樹、圖形結(jié)構(gòu)B、線性表、鏈表、棧隊列、數(shù)組廣義表C、數(shù)組、鏈表、樹、圖形結(jié)構(gòu)D、集合、線性結(jié)構(gòu)、樹、圖形結(jié)構(gòu)正確答案：D18、設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個數(shù)分別為m1,m2和m3與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是()。A、m2B、m2+m3C、m1+m2D、m3正確答案：B19、數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址不相同的，稱之為（）。A、順序存儲結(jié)構(gòu)B、存儲結(jié)構(gòu)C、邏輯結(jié)構(gòu)D、鏈?zhǔn)酱鎯Y(jié)構(gòu)正確答案：D20、為了有效地利用散列查找技術(shù)，主要解決的問題是()。①找一個好的散列函數(shù)。②有效地解決沖突。③用整數(shù)表示關(guān)鍵值A(chǔ)、①和②B、②和③C、①和③D、①②和③正確答案：A21、樹的先根序列等同于與該樹對應(yīng)的二叉樹的（）A、中序序列B、層序序列C、后序序列D、先序序列正確答案：D22、圖的鄰接矩陣表示法適用于表示（）A、有向圖B、稀疏圖C、無向圖D、稠密圖正確答案：D23、設(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、集合正確答案：C24、隊列是一種（）的線性表。A、先進(jìn)先出B、只能插入C、先進(jìn)后出D、只能刪除正確答案：A25、若允許表達(dá)式內(nèi)多種括號混合嵌套，則為檢查表達(dá)式中括號是否正確配對的算法，通常選用的輔助結(jié)構(gòu)是（）。A、二叉排序樹B、隊列C、棧D、線性表正確答案：C26、若進(jìn)棧次序?yàn)閍，b，c，且進(jìn)棧和出棧可以穿插進(jìn)行，則可能出現(xiàn)的含3個元素的出棧序列個數(shù)是（）A、6B、7C、5D、3正確答案：C27、任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序（）。A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對正確答案：A28、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為()。A、(n-1)/2B、n/2C、(n+1)/2D、n正確答案：C29、在一個具有n個結(jié)點(diǎn)的有序單鏈表插入一個新結(jié)點(diǎn)并仍然有序的時間復(fù)雜度是()。A、O(1)B、O(n2)C、O(n)D、O(nlog2n)正確答案：C30、在一個具有n個頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量的大小至少為()。A、eB、2nC、nD、2e正確答案：C31、高度為h的完全二叉樹中，結(jié)點(diǎn)數(shù)最多為（）A、2^(h-1)B、2^hC、2^h+1D、2^h-1正確答案：D32、設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。A、n+1-IB、不能確定C、n-1-ID、n-I正確答案：A33、一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是()。A、edcbaB、abcdeC、decbaD、dceab正確答案：D34、在一個具有n個頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個數(shù)為()。A、eB、2eC、nD、ne正確答案：A35、下列查找算法中，平均查找長度與元素個數(shù)n不直接相關(guān)的查找方法是（）A、二分查找B、順序查找C、分塊查找D、散列查找正確答案：D36、在一個具有n個頂點(diǎn)和e條邊的無向圖的鄰接表中，邊結(jié)點(diǎn)的個數(shù)為()。A、neB、nC、2eD、e正確答案：C37、采用順序存儲結(jié)構(gòu)存儲的線性表，其首地址為100，每個元素的長度為2，則第5個元素的地址為()。A、120B、110C、100D、108正確答案：D38、循環(huán)隊列A[0…m-1]存放其元素值，分別用front和rear表示隊頭和隊尾，則當(dāng)前隊列的元素個數(shù)是()。A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front正確答案：A39、元素大小為1個單元，容量為n個單元的非空順序棧中，以地址高端為棧底，以top作為棧頂指針，則出棧處理后，top的值應(yīng)修改為()A、top=topB、top=top-1C、top=n-1D、top=top+1正確答案：D40、設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。A、BADCB、BCDAC、CDABD、CBDA正確答案：A41、對于一個無向圖，下面()種說法是正確的。A、每個頂點(diǎn)的入度等于出度B、每個頂點(diǎn)的度等于其入度與出度之和C、每個頂點(diǎn)的入度為0D、每個頂點(diǎn)的出度為0正確答案：A42、對包含n個元素的散列表進(jìn)行搜索，平均搜索長度為（）A、不直接依賴于nB、上述都不對C、O（n）D、O（log2n）正確答案：A43、順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（）。A、O(n1/2)B、O(1og2n)C、O(n)D、O(n2)正確答案：C44、棧的數(shù)組表示中，top為棧頂指針，指向棧頂元素的下一個位置，?？盏臈l件是()。A、top=-1B、top=maxSizeC、top=maxSizeD、top=0正確答案：D45、下面程序的時間復(fù)雜為（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A、O(n3)B、O(n2)C、O(n)D、O(n4)正確答案：B46、若采用鄰接矩陣存儲一個n個頂點(diǎn)的無向圖，則該鄰接矩陣是一個（）。A、對角矩陣B、對稱矩陣C、上三角矩陣D、稀疏矩陣正確答案：B47、關(guān)于棧和隊列的說法中正確的是（）A、棧和隊列都是線性結(jié)構(gòu)B、棧和隊列都不是線性結(jié)構(gòu)C、棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu)D、棧是線性結(jié)構(gòu)，隊列不是線性結(jié)構(gòu)正確答案：A48、下列四種排序中（）的空間復(fù)雜度最大。A、希爾排序B、快速排序C、冒泡排序D、堆正確答案：B49、排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（）A、希爾排序B、選擇排序C、冒泡排序D、插入排序正確答案：D50、數(shù)組的邏輯結(jié)構(gòu)不同于下列（）的邏輯結(jié)構(gòu)。A、線性表B、樹C、棧D、隊列正確答案：B51、在一棵二叉樹上第4層的結(jié)點(diǎn)數(shù)最多為（）。A、2B、6C、4D、8正確答案：D52、在對n個元素進(jìn)行直接插入排序的過程中，共需要進(jìn)行（）趟。A、2nB、n+1C、nD、n-1正確答案：D53、設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點(diǎn)，B的根為p，p的右子樹結(jié)點(diǎn)個數(shù)為n,森林F中第一棵子樹的結(jié)點(diǎn)個數(shù)是（）。A、m-nB、m-n-1C、n+1D、條件不足，無法確定正確答案：A54、在下列對順序表進(jìn)行的操作中，算法時間復(fù)雜度為O(1)的是（）A、對順序表中元素進(jìn)行排序B、訪問第i個元素的前驅(qū)（1<i<=n)C、在第i個元素之后插入一個新元素(1<=i<=n)D、刪除第i個元素(1<=i<=n)正確答案：B55、設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（）。A、20B、45C、30D、40正確答案：B56、某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A、空或只有一個結(jié)點(diǎn)B、高度等于其節(jié)點(diǎn)數(shù)C、任一結(jié)點(diǎn)無左孩子D、任一結(jié)點(diǎn)無右孩子正確答案：B57、連通圖G中有n個頂點(diǎn)，G的生成樹是()的連通子圖。A、包含G的所有頂點(diǎn)B、不必包含G的所有頂點(diǎn)C、包含G的所有邊D、包含G的所有頂點(diǎn)和所有邊正確答案：A58、計算機(jī)識別、存儲和加工處理的對象被統(tǒng)稱為()A、數(shù)據(jù)元素B、數(shù)據(jù)C、數(shù)據(jù)結(jié)構(gòu)D、數(shù)據(jù)類型正確答案：B59、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］；上列程序的時間復(fù)雜度為（）A、O（m+n×t）B、O（m×t+n）C、O（m+n+t）D、O（m×n×t）正確答案：D60、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）A、48B、53C、71D、24正確答案：C61、設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（data,link）,且top是指向棧頂?shù)闹羔?。若想摘除鏈?zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)，并將被摘除結(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行下列（）操作。A、x=top->data;B、top=top->link;x=top->data;C、x=top->data;top=top->link;D、x=top;top=top->link;正確答案：C62、已知含10個結(jié)點(diǎn)的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于()A、3.4B、1C、5.5D、2.9正確答案：D63、如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是（）A、圖B、隊列C、樹D、棧正確答案：C64、在()運(yùn)算中，使用順序表比鏈表好。A、刪除B、根據(jù)元素值查找C、插入D、根據(jù)序號查找正確答案：D65、在數(shù)組A中，每一個數(shù)組元素A[i][j]占用3個存儲字，行下標(biāo)i從1到8，列下標(biāo)j從1到10。所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放該數(shù)組至少需要的存儲字?jǐn)?shù)是（）。A、80B、100C、240D、270正確答案：C66、下列排序方法中，屬于不穩(wěn)定的排序方法是()A、希爾排序B、冒泡排序法C、歸并排序法D、直接插入排序法正確答案：A67、在一個單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個s所指的結(jié)點(diǎn),則執(zhí)行()。A、p→link=s;s→link=q;B、p→link=s→link;s→link=p;C、s→link=p→link;p→link=s;D、q→link=s;s→link=p;正確答案：D68、已知一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為9個，則最后一層的結(jié)點(diǎn)數(shù)為（）。A、4B、3C、2D、1正確答案：C69、假設(shè)在構(gòu)建散列表時，采用線性探測解決沖突。若連續(xù)插入的n個關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時，所需進(jìn)行的比較次數(shù)為()A、n+2B、nC、n-1D、n+l正確答案：B70、若<vi,vj>是有向圖的一條邊，則稱（）A、vi與vj?不相鄰接B、vi和vj相互鄰接C、vj鄰接于viD、vi鄰接于vj正確答案：C71、若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點(diǎn)A開始對該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為()。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正確答案：B72、設(shè)無向圖G中有n個頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為（）。A、n，eB、e，nC、n，2eD、2n，e正確答案：C73、設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有()條邊才能確保是一個連通圖。A、6B、5C、7D、8正確答案：B74、由m棵結(jié)點(diǎn)數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點(diǎn)的右子樹上具有的結(jié)點(diǎn)個數(shù)是（）A、n(m-1)B、mnC、mn-1D、m(n-1)正確答案：A75、一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是（）。A、4,3,2,1B、1,2,3,4C、3,2,4,1D、1,4,3,2正確答案：B76、在計算機(jī)內(nèi)實(shí)現(xiàn)遞歸算法時所需的輔助數(shù)據(jù)結(jié)構(gòu)是()A、圖B、隊列C、棧D、樹正確答案：C77、如果在排序過程中，每次均將一個待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的子表中的適當(dāng)位置，則該排序方法稱為（）A、堆排序B、冒泡排序C、歸并排序D、插入排序正確答案：D78、下面選項(xiàng)中，（）不是圖的存儲方法。A、鄰接矩陣B、鄰接鏈表C、孩子兄弟鏈表D、逆鄰接鏈表正確答案：C79、棧和隊列都是（）。A、鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)B、限制存取位置的線性結(jié)構(gòu)C、順序存儲的線性結(jié)構(gòu)D、限制存取位置的非線性結(jié)構(gòu)正確答案：B80、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時，top變化為（）。A、top++B、top=0C、top不變D、top--正確答案：D81、已知棧的最大容量為4。若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行,則可能出現(xiàn)的出棧序列為（）A、3，2，5，4，1，6B、5，4，3，2，1，6C、1，4，6，5，2，3D、2，3，5，6，1，4正確答案：A82、在一個單鏈表中，若P所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在P之后插入s所指結(jié)點(diǎn)，則執(zhí)行()。A、s->next=p->next;p->next=sB、s->next=p;p->next=sC、p->next=s;s->next=pD、s->next=p->next;p=s正確答案：A83、在排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為()A、快速排序B、希爾排序C、冒泡排序D、插入排序正確答案：D84、設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。A、線性結(jié)構(gòu)B、樹型結(jié)構(gòu)C、物理結(jié)構(gòu)D、圖型結(jié)構(gòu)正確答案：B85、根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計算出該元素存儲地址的存儲方法是（）A、鏈?zhǔn)酱鎯Ψ椒˙、索引存儲方法C、散列存儲方法D、順序存儲方法正確答案：C86、一組記錄的排序碼為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的第一次劃分結(jié)果為（）。A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38,46,84,56,79D、40,38,46,56,79,84正確答案：D87、設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)不能得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。A、acfebdB、aebdfcC、abedfcD、aedfcb正確答案：A88、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（）。A、top=top->next;B、top->next=top;C、top=top-1;D、top=top+1;正確答案：A89、下面程序段的時間復(fù)雜度為（）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!)正確答案：B90、在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為（）。A、(rear+l)％n==frontB、rear％n==frontC、（front+l）％n==rearD、rear％n-1==front正確答案：A91、在對查找表的查找過程中，若被查找的數(shù)據(jù)元素不存