計信DS復(fù)習(xí)題答案.doc

《計信DS復(fù)習(xí)題答案.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、計信《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題答案一、選擇題1．如果某數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素的集合為S＝{A，B，C，D，E，F(xiàn)，G}，數(shù)據(jù)元素之間的關(guān)系為R＝{＜A，D＞，＜A，G＞，＜D，B＞，＜D，C＞，＜G，E＞，＜G，F(xiàn)＞}，則該數(shù)據(jù)結(jié)構(gòu)是一種()。A．線性結(jié)構(gòu)B．樹結(jié)構(gòu)C．圖結(jié)構(gòu)D．鏈表結(jié)構(gòu)2．設(shè)有二維數(shù)組A[50][60]，其元素長度為1字節(jié)，按列優(yōu)先順序存儲，首元素A[0][0]的地址為200，則元素A[10][20]的存儲地址為()。A．820B．720C．1210D．14103．設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6先后進(jìn)

2、入棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素的出隊順序是e2,e4,e3,e6,e5,e1，則棧S至少可以容納（）個元素。A．3B．4C．5D．64．串是。A）不少于一個字母的序列B）任意個字母的序列C）不少于一個字符的序列D）有限個字符的序列5．A，B，C，D依次入棧，則不可能的出棧序列是。A）A，B，C，DC）D，C，B，AB）A，C，D，BD）D，A，B，C6．棧和隊列的共同點是。A）都是先進(jìn)后出B）都是先進(jìn)先出C）只允許在端點處插入和刪除D）都采用順序方式存儲7．在線索二叉樹中，指針t所指結(jié)點沒有左子樹的充要條件是。A）t->lchi

3、ld==NULLB）t->ltag==1C）t->ltag==1且t->lchild==NULLD）t->ltag==08．對具有n個結(jié)點的完全二叉樹按自上而下、從左至右的順序，從1開始依次給結(jié)點編號，則編號最小的葉子結(jié)點的序號是。A）B）+1C）-1D）-19．下列算法中是用來構(gòu)造無向連通圖的最小生成樹的。A）FloydB）KruskalC）HuffmanD）Dijkstra10．下列排序算法中是穩(wěn)定的。A）堆排序B）希爾排序C）快速排序D）歸并排序11．若要對一個線性表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，則可采用查找方法。A）分塊B）順

4、序C）折半D）哈希12．下面關(guān)于線性表的敘述中，錯誤的是。A）線性表采用順序方式存儲，必須占用一片連續(xù)的存儲單元B）線性表采用鏈?zhǔn)酱鎯?，便于進(jìn)行插入和刪除操作C）線性表采用鏈?zhǔn)酱鎯Γ槐卣加靡黄B續(xù)的存儲單元D）線性表采用順序方式存儲，便于進(jìn)行插入和刪除操作13．廣義表A=（（a,b,c），（d,e,f）），從A中取出原子e的運算是。A）tail(head(A))B）head(tail(tail(head(A))))C）head(tail(A))D）head(tail(head(tail(A))))14．判定一個指針ST指向的順序棧（棧中最多元

5、素為M個）為棧滿的條件是。A）ST->top!=0B）ST->top==0C）ST->top!=M-1D）ST->top==M-115．指針head指向一個非空循環(huán)單鏈表的頭結(jié)點，指針p指向該鏈表的尾結(jié)點的條件是。A）p->next=NULLB）p=NULLC）p->next=headD）p=head16．設(shè)電文中出現(xiàn)的字母為A、B、C、D和E，每個字母在電文中出現(xiàn)的次數(shù)分別為：6，23，3，5和12，按哈夫曼編碼（要求左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)），則字母C的編碼應(yīng)是。A．10B．110C．1110D．111117．下面關(guān)于二叉樹

6、的敘述中正確的是。A）二叉樹中，任何一個結(jié)點的左子樹和右子樹上的結(jié)點個數(shù)一樣B）二叉樹中的結(jié)點個數(shù)大于0C）二叉樹中葉子結(jié)點的個數(shù)等于度為2的結(jié)點個數(shù)加1D）二叉樹中任何一個結(jié)點要么是葉子，要么恰有兩個孩子18．具有n個頂點的連通無向圖的最小生成樹中包含條邊。A）nB）n-1C）n+1D）2n19．折半查找存儲結(jié)構(gòu)。A）只適用于順序B）只適用于鏈?zhǔn)紺）既適合于順序也適合于鏈?zhǔn)紻）既不適合于順序也不適合于鏈?zhǔn)?0．已知某算法的執(zhí)行時間為（n3+n2+n）log2(n+2)，n為問題規(guī)模，則該算法的時間復(fù)雜度是（）。A．O(n)B．O(n2)C．O

7、(log2n)D．O(n3log2n)1234567891011121314151617181920BCADDCBBBDADDDCCCBAD二、判斷題1．算法與程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中兩者是通用的。2．串長度是指串中不同字符的個數(shù)。3．棧是一種后進(jìn)先出表。4．由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹。5．根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表分為單鏈表和雙鏈表。6．具有3個結(jié)點且高度也為3的有序樹只有1種形態(tài)。7．先序序列和中序序列相同的二叉樹是空二叉樹或任一結(jié)點均無右子樹的非空二叉樹。8．“AOV網(wǎng)”的

8、中文含義是邊表示活動的網(wǎng)。9．在棧滿的情況下不能作進(jìn)棧的運算，否則產(chǎn)生“上溢”。10．在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此單鏈表