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

數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案一、單選題（共100題，每題1分，共100分）1、具有35個結(jié)點的完全二叉樹的深度為()A、6B、7C、8D、5正確答案：A2、在一個單鏈表中,若q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點,若在q與p之間插入一個s所指的結(jié)點,則執(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;正確答案：B3、采用線性鏈表表示一個向量時，要求占用的存儲空間地址（）。A、部分地址必須是連續(xù)的B、一定是不連續(xù)的C、必須是連續(xù)的D、可連續(xù)可不連續(xù)正確答案：D4、在以單鏈表為存儲結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用（）A、數(shù)據(jù)元素的值表示B、數(shù)據(jù)元素在表中的序號表示C、數(shù)據(jù)元素的相鄰地址表示D、指向后繼元素的指針表示正確答案：D5、在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為()A、i+1B、n-i+1C、ID、n-i正確答案：D6、在數(shù)組A中，每一個數(shù)組元素A[i][j]占用3個存儲字，行下標(biāo)i從1到8，列下標(biāo)j從1到10。所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放該數(shù)組至少需要的存儲字數(shù)是（）。A、80B、100C、240D、270正確答案：C7、設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為m1,m2和m3與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是()。A、m1+m2B、m2C、m2+m3D、m3正確答案：C8、利用二叉鏈表存儲樹，則根結(jié)點的右指針是()。A、非空B、空C、指向最右孩子D、指向最左孩子正確答案：B9、廣度優(yōu)先遍歷類似于二叉樹的（）。A、層次遍歷B、先序遍歷C、后序遍歷D、中序遍歷正確答案：A10、設(shè)有一個棧，按A、B、C、D的順序進棧，則可能為出棧序列的是()A、DCBAB、CDABC、DBACD、DCAB正確答案：A11、用鏈接方式存儲的隊列，在進行插入運算時()。A、僅修改尾指針B、頭、尾指針可能都要修改C、僅修改頭指針D、頭、尾指針都要修改正確答案：B12、在關(guān)鍵字序列(12，23，34，45，56，67，78，89，91)中二分查找關(guān)鍵字為45、89和12的結(jié)點時，所需進行的比較次數(shù)分別為()A、4，4，3B、4，3，3C、3，3，4D、3，4，4正確答案：B13、循環(huán)隊列A[0…m-1]存放其元素值，分別用front和rear表示隊頭和隊尾，則當(dāng)前隊列的元素個數(shù)是()。A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front正確答案：A14、含有10個結(jié)點的二叉樹中，度為0的結(jié)點數(shù)為4，則度為2的結(jié)點數(shù)為（）A、6B、5C、4D、3正確答案：D15、對包含n個元素的散列表進行搜索，平均搜索長度為（）A、不直接依賴于nB、O（log2n）C、上述都不對D、O（n）正確答案：A16、對于一組記錄的關(guān)鍵字值(25,38,63,74)，采用折半查找25時，()次查找成功。A、1B、2C、4D、3正確答案：B17、隊和棧的主要區(qū)別是()A、所包含的運算個數(shù)不同B、限定插入和刪除的位置不同C、存儲結(jié)構(gòu)不同D、邏輯結(jié)構(gòu)不同正確答案：B18、導(dǎo)致棧上溢的操作是()A、?？諘r執(zhí)行的入棧B、棧空時執(zhí)行的出棧C、棧滿時執(zhí)行的出棧D、棧滿時執(zhí)行的入棧正確答案：D19、數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指()A、線性結(jié)構(gòu)、鏈表、樹、圖形結(jié)構(gòu)B、集合、線性結(jié)構(gòu)、樹、圖形結(jié)構(gòu)C、數(shù)組、鏈表、樹、圖形結(jié)構(gòu)D、線性表、鏈表、棧隊列、數(shù)組廣義表正確答案：B20、隊列操作的原則是（）。A、后進先出B、只能進行插入C、只能進行刪除D、先進先出正確答案：D21、線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（）A、必須是不連續(xù)的B、連續(xù)與否均可C、必須是連續(xù)的D、和頭結(jié)點的存儲地址相連續(xù)正確答案：B22、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時，top變化為（）。A、top不變B、top=0C、top++D、top--正確答案：D23、設(shè)指針變量p指向單鏈表結(jié)點A，則刪除結(jié)點A的后繼結(jié)點B需要的操作為（）。A、p->next=p->next->nextB、p=p->nextC、p=p->next->nextD、p->next=p正確答案：A24、在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（）A、棧B、隊列C、有序表D、線性表正確答案：B25、假設(shè)以數(shù)組A[n]存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設(shè)定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當(dāng)前存于隊列中的元素個數(shù)為()A、(rear-front-1)％nB、(rear-front)％nC、(front-rear+1)％nD、(rear-front+n)％n正確答案：D26、向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點時，應(yīng)執(zhí)行（）。A、hs->next=s；B、s->next=hs；hs=s；C、s->next=hs；hs=hs->next；D、s->next=hs->next；hs->next=s；正確答案：B27、連通圖G中有n個頂點，G的生成樹是()的連通子圖。A、包含G的所有頂點B、不必包含G的所有頂點C、包含G的所有邊D、包含G的所有頂點和所有邊正確答案：A28、對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應(yīng)鄰接表中該頂點單鏈表中的邊結(jié)點數(shù)為()。A、k1+k2B、k2C、k1-k2D、k1正確答案：B29、與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（）。A、操作B、存儲結(jié)構(gòu)C、算法D、邏輯結(jié)構(gòu)正確答案：D30、以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？()A、線性表B、隊列C、棧D、二叉樹正確答案：D31、從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，需平均比較（）個元素結(jié)點。A、（n-1）/2B、（n+1）/2C、n/2D、n正確答案：B32、數(shù)據(jù)結(jié)構(gòu)的定義為(D，S)，其中D是()的集合。A、算法B、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯結(jié)構(gòu)正確答案：B33、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為（）。A、第i行非0元素的個數(shù)之和B、第i列非0元素的個數(shù)之和C、第i行0元素的個數(shù)之和D、第i列0元素的個數(shù)之和正確答案：B34、排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（）A、冒泡排序B、插入排序C、希爾排序D、選擇排序正確答案：B35、已知含10個結(jié)點的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于()A、3.4B、2.9C、1D、5.5正確答案：B36、若根據(jù)查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13計算哈希地址，則元素64的哈希地址為()。A、12B、8C、4D、13正確答案：A37、對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列進行同樣的排序操作，直到子序列為空或只剩下一個元素為止。這樣的排序方法是（）。A、直接選擇排序B、直接插入排序C、快速排序D、冒泡排序正確答案：C38、對于含n個頂點和e條邊的圖，采用鄰接矩陣表示的空間復(fù)雜度為（）A、O(e)B、O（n）C、O(n+e)D、O(n2)正確答案：D39、鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯的優(yōu)點是（）。A、刪除操作更加方便B、通常不會出現(xiàn)棧滿的情況C、插入操作更加方便D、不會出現(xiàn)棧空的情況正確答案：B40、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為（）。A、top=top-1;B、top=top->next;C、top->next=top;D、top=top+1;正確答案：B41、樹最適合用來表示（）。A、元素之間無聯(lián)系的數(shù)據(jù)B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、有序數(shù)據(jù)元素正確答案：C42、在一個具有n個頂點和e條邊的無向圖的鄰接表中，邊結(jié)點的個數(shù)為()。A、eB、neC、2eD、n正確答案：C43、設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（）A、R-FB、(R-F+M)％MC、(F-R+M)％MD、F-R正確答案：B44、假設(shè)在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為（）個。A、16B、15C、17D、47正確答案：A45、若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（）A、前序遍歷算法B、層次遍歷算法C、中序遍歷算法D、后序遍歷算法正確答案：C46、設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。A、log2n-1B、log2n+1C、log2(n+1)D、log2n正確答案：B47、在對n個元素進行冒泡排序的過程中，第一趟排序至多需要進行（）對相鄰元素之間的交換。A、nB、n/2C、n-1D、n+1正確答案：C48、以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）。A、線索二叉樹B、有向圖C、串D、二叉樹正確答案：C49、若進棧次序為a，b，c，且進棧和出?？梢源┎暹M行，則可能出現(xiàn)的含3個元素的出棧序列個數(shù)是（）A、3B、7C、5D、6正確答案：C50、設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為H(key)=keymod13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（）A、4B、1C、2D、3正確答案：B51、下列排序方法中，穩(wěn)定的排序方法為（）A、堆排序B、直接插入排序C、希爾排序D、快速排序正確答案：B52、下面程序段的時間復(fù)雜度為（）for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A、O(n2)B、O(m*n)C、O(m+n)D、O(m2)正確答案：B53、為了有效地利用散列查找技術(shù)，主要解決的問題是()。①找一個好的散列函數(shù)。②有效地解決沖突。③用整數(shù)表示關(guān)鍵值A(chǔ)、①和②B、①②和③C、①和③D、②和③正確答案：A54、用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的。A、圖B、隊列C、棧D、樹正確答案：B55、已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行,則可能出現(xiàn)的出棧序列為（）A、1，4，6，5，2，3B、5，4，3，2，1，6C、3，2，5，4，1，6D、2，3，5，6，1，4正確答案：C56、設(shè)n,m為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中n在m前的條件是（）。A、n在m右方B、n是m的祖先C、n是m的子孫D、n在m左方正確答案：D57、在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行()。A、p->link=s;s->link=p;B、s->link=p->link;p->link=s;C、s->link=p->link;p=s;D、s->link=p;p->link=s;正確答案：B58、設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)不能得到一種深度優(yōu)先遍歷的頂點序列為（）。A、abedfcB、aedfcbC、acfebdD、aebdfc正確答案：C59、（）二叉排序樹可以得到一個從小到大的有序序列。A、層次遍歷B、中序遍歷C、先序遍歷D、后序遍歷正確答案：B60、判定一個棧ST（最多元素為m0）為空的條件是A、ST->top=0B、ST->top<>m0C、ST->top<>0D、ST->top=m0正確答案：A61、在一個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動（）個元素。A、n-i+lB、n-i-1C、iD、n-i正確答案：D62、二叉樹的第k層的結(jié)點數(shù)最多為().A、2^(k-1)B、2k-1C、2^k-1D、2k+1正確答案：A63、下列排序算法中，（）在某些特殊情況可能只需一趟排序即可完成。A、冒泡排序B、堆排序C、插入排序D、快速排序正確答案：A64、設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（）。A、O(log2n)B、O(1)C、O(n)D、O(n^2)正確答案：C65、在含有n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）。A、2eB、n2-2eC、n2-eD、e正確答案：B66、設(shè)有一個遞歸算法如下：則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。intfact(intn){/*大于等于0*/if(n<=0)return1;elsereturnn*fact(n-1);}A、n+2B、n+1C、n-1D、n正確答案：B67、棧的數(shù)組表示中，top為棧頂指針，指向棧頂元素的下一個位置，?？盏臈l件是()。A、top=maxSizeB、top=-1C、top=0D、top=maxSize正確答案：C68、棧可以在()中應(yīng)用。A、遞歸調(diào)用B、子程序調(diào)用C、表達式求值D、A,B,C正確答案：D69、一個數(shù)組元素a[i]與（）的表示等價。A、a+IB、*（a+i）C、&a+iD、*a+I正確答案：B70、根據(jù)先序序列ABDC和中序序列DBAC確定對應(yīng)的二叉樹，該二叉樹（）。A、是完全二叉樹B、不是完全二叉樹C、是滿二叉樹D、是完全二叉樹且是滿二叉樹正確答案：A71、由m棵結(jié)點數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點的右子樹上具有的結(jié)點個數(shù)是（）A、mnB、mn-1C、m(n-1)D、n(m-1)正確答案：D72、設(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)正確答案：B73、如果在排序過程中，每次均將一個待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的子表中的適當(dāng)位置，則該排序方法稱為（）A、冒泡排序B、堆排序C、歸并排序D、插入排序正確答案：D74、在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為n，它被均分為k個子表，每個子表的長度均為n/k，則索引查找的平均查找長度為()。A、(k+n/k)/2+1B、n+kC、(k+n/k)/2D、k+n/k正確答案：A75、一個棧的輸入序列是12345，則下列序列中是棧的輸出序列的是（）。A、1,4,2,5,3B、5,4,1,3,2C、3,1,2,4,5D、2,3,4,1,5正確答案：D76、在一個單鏈表中，若p所指結(jié)點是q所指結(jié)點的前驅(qū)結(jié)點，則刪除結(jié)點q的正確操作是（）A、p=q->nextB、p->next=qC、p->next=q->next->nextD、p->next=q->next正確答案：D77、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是（）。A、物理結(jié)構(gòu)B、邏輯結(jié)構(gòu)C、存儲結(jié)構(gòu)D、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)正確答案：B78、棧和隊列的共同特點是()。A、沒有共同點B、都是先進后出C、都是先進先出D、只允許在端點處插入和刪除正確答案：D79、計算機算法必須具備輸入、輸出和（）等5個特性。A、可行性、確定性和有窮性B、易讀性、穩(wěn)定性和安全性C、可行性、可移植性和可擴充性D、確定性、有窮性和穩(wěn)定性正確答案：A80、數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點（）。A、正確B、前半句對，后半句錯C、前半句錯，后半句對D、錯誤正確答案：D81、在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為（）。A、2n-1B、2nC、2n+1D、不確定正確答案：A82、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）.A、線性結(jié)構(gòu)、非線性結(jié)構(gòu)B、初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)C、順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)D、動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)正確答案：A83、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）正確答案：C84、下面關(guān)于線性表的敘述錯誤的是（）。A、線性表采用順序存儲必須占用一片連續(xù)的存儲空間B、線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)C、線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間D、線性表采用順序存儲便于插入和刪除操作的實現(xiàn)正確答案：D85、數(shù)據(jù)的四種基本存儲結(jié)構(gòu)是指（）A、順序存儲結(jié)構(gòu)、非順序存儲結(jié)構(gòu)、指針存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)B、順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)C、順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、散列存儲結(jié)構(gòu)D、順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、直接存儲結(jié)構(gòu)、倒排存儲結(jié)構(gòu)正確答案：C86、設(shè)一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（）A、a，b，d，cB、a，b，c，dC、d，c，b，aD、c，d，a，b正確答案：D87、棧的兩種常用存儲結(jié)構(gòu)分別為()A、順序存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)B、鏈?zhǔn)酱鎯Y(jié)構(gòu)和散列存儲結(jié)構(gòu)C、鏈?zhǔn)酱鎯Y(jié)構(gòu)和索引存儲結(jié)構(gòu)D、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)正確答案：D88、棧上溢現(xiàn)象通常出現(xiàn)在（）A、鏈棧的出棧操作過程中B、鏈棧的入棧操作過程中C、順序棧的出棧操作過程中D、順序棧的入棧操作過程中正確答案：D89、假設(shè)一棵完全二叉樹按層次遍歷的順序依次存放在數(shù)組BT[m]中，其中根結(jié)點存放在BT[0]，若BT[i]中的結(jié)點有左孩子，則左孩子存放在()A、BT[i/2]B、BT[2*i-1]C、BT[2*i]D、BT[2*i+1]正確答案：D90、在平均情況下速度最快的排序方法為（）。A、歸并排序B、快速排序C、堆排序D、簡單選擇排序正確答案：B91、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）A、71B、53C、48D、24正確答案：A92、一組記錄的排序碼為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的第一次劃分結(jié)果為（）。A、40,38,46,79,56,84B、40,38,46,84,56,7