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

數(shù)據(jù)結(jié)構(gòu)練習(xí)題庫與答案一、單選題（共100題，每題1分，共100分）1.樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（）。A、多對(duì)多關(guān)系B、多對(duì)一關(guān)系C、一對(duì)多關(guān)系D、一對(duì)一關(guān)系正確答案：C2.設(shè)順序存儲(chǔ)的線性表共有123個(gè)元素，按分塊查找的要求等分成3塊。若對(duì)索引表采用順序查找來確定塊，并在確定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時(shí)的平均查找長度為（）。A、23B、62C、21D、41正確答案：A3.對(duì)于一個(gè)無向圖，下面()種說法是正確的。A、每個(gè)頂點(diǎn)的入度等于出度B、每個(gè)頂點(diǎn)的度等于其入度與出度之和C、每個(gè)頂點(diǎn)的入度為0D、每個(gè)頂點(diǎn)的出度為0正確答案：A4.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的存儲(chǔ)地址是()A、120B、100C、108D、110正確答案：C5.哈夫曼樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為()。A、1B、2C、0D、不確定正確答案：C6.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（）。A、2nB、不確定C、2n+1D、2n-1正確答案：D7.設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（）個(gè)葉子結(jié)點(diǎn)。A、101B、102C、99D、100正確答案：D8.設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（）。A、n-1-IB、n-IC、n+1-ID、不能確定正確答案：C9.設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為m1,m2和m3與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是()。A、m2B、m2+m3C、m3D、m1+m2正確答案：B10.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（）。A、s->next=hs；hs=s；B、s->next=hs；hs=hs->next；C、hs->next=s；D、s->next=hs->next；hs->next=s；正確答案：A11.在以單鏈表為存儲(chǔ)結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用（）A、數(shù)據(jù)元素的相鄰地址表示B、數(shù)據(jù)元素在表中的序號(hào)表示C、數(shù)據(jù)元素的值表示D、指向后繼元素的指針表示正確答案：D12.假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為f和r,則判斷隊(duì)空的條件為().A、f==0B、f+1==rC、f==rD、r+1==f正確答案：C13.對(duì)于含n個(gè)頂點(diǎn)和e條邊的圖，采用鄰接矩陣表示的空間復(fù)雜度為（）A、O(n+e)B、O(e)C、O（n）D、O(n2)正確答案：D14.排序算法中，不穩(wěn)定的排序是（）。A、冒泡排序B、直接插入排序C、選擇排序D、堆排序正確答案：D15.在下列排序方法中，平均時(shí)間性能為O(nlogn)且空間性能最好的是()。A、基數(shù)排序B、歸并排序C、快速排序D、堆排序正確答案：D16.對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，k個(gè)分枝結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，則（）。A、n=2k+1B、m+1=2nC、n=m+1D、m=k-1正確答案：A17.設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出對(duì)操作后其頭指針front值為（）。A、front=front+1B、front=(front+1)%mC、front=(front-1)%mD、front=(front+1)%(m-1)正確答案：B18.已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為（）A、FEDCBAB、ABCDEFC、FDECBAD、FBDCEA正確答案：A19.以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（）。A、二叉樹B、串C、線索二叉樹D、有向圖正確答案：B20.順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（）。A、O(n1/2)B、O(1og2n)C、O(n2)D、O(n)正確答案：D21.順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語句為（）。A、s.elem［top++］=e；s.top=s.top+1；B、s.top=s.top+1；s.elem［top+1］=e；C、s.elem［top］=e；s.top=s.top+1；D、s.top=s.top+1；s.elem［top］=e；正確答案：D22.一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為()A、3B、5C、4D、6正確答案：B23.高度為h的完全二叉樹中，結(jié)點(diǎn)數(shù)最多為（）A、2^h-1B、2^h+1C、2^hD、2^(h-1)正確答案：A24.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為（）。A、順序存儲(chǔ)結(jié)構(gòu)B、存儲(chǔ)結(jié)構(gòu)C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、邏輯結(jié)構(gòu)正確答案：C25.設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（）。A、45B、20C、40D、30正確答案：A26.具有n個(gè)結(jié)點(diǎn)的二叉樹，擁有指向孩子結(jié)點(diǎn)的分支數(shù)目是（）A、n-1B、2nC、n+1D、n正確答案：A27.在長度為n的線性表中刪除一個(gè)指針p所指結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）A、O(n)B、O(1)C、O(log2n)D、O(n2)正確答案：A28.棧和隊(duì)列共同具有的特點(diǎn)是（）A、都是先進(jìn)后出B、只允許在端點(diǎn)進(jìn)行操作運(yùn)算C、既能先進(jìn)先出，也能先進(jìn)后出D、都是先進(jìn)先出正確答案：B29.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為().A、2^(k-1)B、2k+1C、2k-1D、2^k-1正確答案：A30.對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為k1，出度為k2，則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為()。A、k1+k2B、k1-k2C、k1D、k2正確答案：D31.一個(gè)棧的輸入序列是12345，則下列序列中是棧的輸出序列的是（）。A、5,4,1,3,2B、2,3,4,1,5C、3,1,2,4,5D、1,4,2,5,3正確答案：B32.在一個(gè)單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個(gè)s所指的結(jié)點(diǎn),則執(zhí)行()。A、p→link=s→link;s→link=p;B、q→link=s;s→link=p;C、s→link=p→link;p→link=s;D、p→link=s;s→link=q;正確答案：B33.利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是()。A、空B、非空C、指向最左孩子D、指向最右孩子正確答案：A34.從未排序序列中挑選元素，并將其依次插入已排序序列（初始時(shí)為空）的一端的方法，稱為（）。A、選擇排序B、歸并排序C、希爾排序D、插入排序正確答案：A35.用二叉鏈表表示具有n個(gè)結(jié)點(diǎn)的二叉樹時(shí)，值為空的指針域的個(gè)數(shù)為()A、n+lB、nC、2nD、n-1正確答案：A36.由m棵結(jié)點(diǎn)數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點(diǎn)的右子樹上具有的結(jié)點(diǎn)個(gè)數(shù)是（）A、m(n-1)B、n(m-1)C、mnD、mn-1正確答案：B37.若進(jìn)棧次序?yàn)閍，b，c，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的含3個(gè)元素的出棧序列個(gè)數(shù)是（）A、7B、6C、3D、5正確答案：D38.對(duì)于二叉樹來說，第I層上至多有（）個(gè)節(jié)點(diǎn)。A、2^(i-1)B、2^(i-1)-1C、2^iD、2^i-1正確答案：A39.在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量的大小至少為()。A、nB、eC、2nD、2e正確答案：A40.下列排序算法中，在最好情況下，時(shí)間復(fù)雜度為O(n)的算法是()。A、歸并排序B、快速排序C、冒泡排序D、選擇排序正確答案：C41.若已知一個(gè)棧的入棧序列是1,2,3,4……n，其輸出序列為p1,p2,p3,……pn，若p1==n,則pi為（）。A、n-i+1B、iC、不確定D、n==i正確答案：A42.下列排序方法中，屬于不穩(wěn)定的排序方法是()A、希爾排序B、歸并排序法C、冒泡排序法D、直接插入排序法正確答案：A43.如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼，則該結(jié)構(gòu)是（）A、樹B、棧C、圖D、隊(duì)列正確答案：A44.在一個(gè)長度為n的順序表中，向第i個(gè)元素（1≤i≤n+1)位置插入一個(gè)新元素時(shí)需要從后向前移動(dòng)()個(gè)元素A、n-i-1B、n-i+1C、n-iD、i正確答案：B45.在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（）A、隊(duì)列B、棧C、有序表D、線性表正確答案：A46.鄰接矩陣為對(duì)稱矩陣的圖是()A、有向圖B、有向圖或無向圖C、帶權(quán)有向圖D、無向圖正確答案：B47.下面程序段的時(shí)間復(fù)雜度為（）intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A、O(n^2)B、O(1)C、O(n)D、O(n!)正確答案：C48.在一個(gè)非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）。A、只有右子樹上的所有結(jié)點(diǎn)B、只有右子樹上的部分結(jié)點(diǎn)C、只有左子樹的上的部分結(jié)點(diǎn)D、只有左子樹上的所有結(jié)點(diǎn)正確答案：A49.關(guān)于二叉樹性質(zhì)的描述，正確的是（）A、二叉樹至少含有一個(gè)根結(jié)點(diǎn)B、二叉樹若存在兩個(gè)結(jié)點(diǎn)，則必有一個(gè)為根，另一個(gè)為左孩子C、二叉樹若存在三個(gè)結(jié)點(diǎn)，則必有一個(gè)為根，另兩個(gè)分別為左、右孩子D、二叉樹結(jié)點(diǎn)的個(gè)數(shù)可以為0正確答案：D50.求單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前驅(qū)的時(shí)間復(fù)雜度分別是（）A、O（1）和O（1）B、O（1）和O（n）C、O（n）和O（1）D、O(n)和O（n）正確答案：B51.在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，指針域指向該結(jié)點(diǎn)的（）A、開始結(jié)點(diǎn)B、直接后繼C、直接前趨D、終端結(jié)點(diǎn)正確答案：B52.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（）。A、O(m)B、O(1)C、O(n)D、O(m+n)正確答案：A53.設(shè)數(shù)組A[m]為循環(huán)隊(duì)列Q的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則判定Q為空隊(duì)列的條件是()A、(rear-front)%m==1B、front==rearC、(rear-front)%m==m-1D、front==(rear+1)%m正確答案：B54.將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較（）次。A、8B、9C、10D、25正確答案：C55.有個(gè)頂點(diǎn)e條邊的無向圖G，它的鄰接表中的表結(jié)點(diǎn)總數(shù)是()。A、2nB、2eC、eD、n正確答案：B56.設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（）。A、O(nlog2n)B、O(n2)C、O(n)D、O(1)正確答案：D57.含有10個(gè)結(jié)點(diǎn)的二叉樹中，度為0的結(jié)點(diǎn)數(shù)為4，則度為2的結(jié)點(diǎn)數(shù)為（）A、3B、5C、6D、4正確答案：A58.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)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)；正確答案：A59.棧和隊(duì)列都是（）。A、順序存儲(chǔ)的線性結(jié)構(gòu)B、鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C、限制存取位置的線性結(jié)構(gòu)D、限制存取位置的非線性結(jié)構(gòu)正確答案：C60.若<vi,vj>是有向圖的一條邊，則稱（）A、vi與vj?不相鄰接B、vj鄰接于viC、vi鄰接于vjD、vi和vj相互鄰接正確答案：B61.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。A、索引存取B、隨機(jī)存取C、散列存取D、順序存取正確答案：B62.對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個(gè).A、4B、2C、1D、3正確答案：A63.設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不可能的出棧序列（）。A、A,B,C,D,EB、B,C,D,E,AC、E,A,B,C,DD、E,D,C,B,A正確答案：C64.棧和隊(duì)列的共同特點(diǎn)是()。A、只允許在端點(diǎn)處插入和刪除B、都是先進(jìn)后出C、沒有共同點(diǎn)D、都是先進(jìn)先出正確答案：A65.在排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為()A、冒泡排序B、快速排序C、希爾排序D、插入排序正確答案：D66.若一個(gè)圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點(diǎn)A開始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為()。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正確答案：D67.對(duì)包含n個(gè)元素的散列表進(jìn)行搜索，平均搜索長度為（）A、O（log2n）B、上述都不對(duì)C、不直接依賴于nD、O（n）正確答案：C68.衡量查找算法效率的主要標(biāo)準(zhǔn)是（）。A、元素的個(gè)數(shù)B、所需的存儲(chǔ)量C、平均查找長度D、算法難易程度正確答案：C69.若采用孩子兄弟鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（）A、前序遍歷算法B、中序遍歷算法C、后序遍歷算法D、層次遍歷算法正確答案：B70.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是（）。A、存儲(chǔ)結(jié)構(gòu)B、物理結(jié)構(gòu)C、邏輯結(jié)構(gòu)D、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)正確答案：C71.循環(huán)隊(duì)列A[0…m-1]存放其元素值，分別用front和rear表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是()。A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front正確答案：A72.在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則刪除結(jié)點(diǎn)q的正確操作是（）A、p=q->nextB、p->next=q->next->nextC、p->next=qD、p->next=q->next正確答案：D73.一組記錄的排序碼為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的第一次劃分結(jié)果為（）。A、38,40,46,56,79,84B、40,38,46,84,56,79C、40,38,46,56,79,84D、40,38,46,79,56,84正確答案：C74.在數(shù)組A中，每一個(gè)數(shù)組元素A[i][j]占用3個(gè)存儲(chǔ)字，行下標(biāo)i從1到8，列下標(biāo)j從1到10。所有數(shù)組元素相繼存放于一個(gè)連續(xù)的存儲(chǔ)空間中，則存放該數(shù)組至少需要的存儲(chǔ)字?jǐn)?shù)是（）。A、80B、100C、240D、270正確答案：C75.散列查找中散列函數(shù)的值()散列地址的范圍。A、在B、小于C、無關(guān)D、大于正確答案：A76.采用線性鏈表表示一個(gè)向量時(shí)，要求占用的存儲(chǔ)空間地址（）。A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、可連續(xù)可不連續(xù)D、一定是不連續(xù)的正確答案：C77.假設(shè)在構(gòu)建散列表時(shí)，采用線性探測(cè)解決沖突。若連續(xù)插入的n個(gè)關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時(shí)，所需進(jìn)行的比較次數(shù)為()A、n-1B、n+2C、nD、n+l正確答案：C78.設(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、aedfcbD、abedfc正確答案：A79.下列排序算法中，（）在某些特殊情況可能只需一趟排序即可完成。A、冒泡排序B、插入排序C、快速排序D、堆排序正確答案：A80.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。A、log2(n+1)B、log2nC、log2n+1D、log2n-1正確答案：C81.從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個(gè)或1個(gè)的數(shù)據(jù)結(jié)構(gòu)只能是（）A、線性結(jié)構(gòu)和樹型結(jié)構(gòu)B、線性結(jié)構(gòu)和圖狀結(jié)構(gòu)C、樹形結(jié)構(gòu)D、線性結(jié)構(gòu)正確答案：A82.設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為H(key)=keymod13，則它的開散列表中散列地址為1的鏈中的結(jié)點(diǎn)個(gè)數(shù)是（）A、4B、1C、2D、3正確答案：B83.為了有效地利用散列查找技術(shù)，主要解決的問題是()。①找一個(gè)好的散列函數(shù)。②有效地解決沖突。③用整數(shù)表示關(guān)鍵值A(chǔ)、①和②B、②和③C、①和③D、①②和③正確答案：A84.在關(guān)鍵字序列(12，23，34，45，56，67，78，89，91)中二分查找關(guān)鍵字為45、89和12的結(jié)點(diǎn)時(shí)，所需進(jìn)行的比較次數(shù)分別為()A、4，3，3B、3，3，4C、3，4，4D、4，4，3正確答案：A85.在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為144，它被均分為12子表，每個(gè)子表的長度均為12，則索引查找的平均查找長度為()。A、24B、12C、79D、13正確答案：D86.任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（）。A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對(duì)正確答案：A87.對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列進(jìn)行同樣的排序操作，直到子序列為空或只剩下一個(gè)元素為止。這樣的排序方法是（）。A、直接選擇排序B、冒泡排序C、快速排序D、直接插入排序正確答案：C88.設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（）個(gè)空指針域。A、2m-1B、2m+1C、4mD、2m正確答案：D89.在下面的程序段中，對(duì)x的賦值語句的頻度為（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(n^2)B、O(log2n)C、O(n)D、O(2^n)正確答案：A90.含有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)時(shí)，空指針域的個(gè)數(shù)為（）A、