資源描述：
《計信DS復習題答案.doc》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、計信《數據結構》復習題答案一、選擇題1．如果某數據結構的數據元素的集合為S＝{A，B，C，D，E，F，G}，數據元素之間的關系為R＝{＜A，D＞，＜A，G＞，＜D，B＞，＜D，C＞，＜G，E＞，＜G，F＞}，則該數據結構是一種()。A．線性結構B．樹結構C．圖結構D．鏈表結構2．設有二維數組A[50][60]，其元素長度為1字節(jié)，按列優(yōu)先順序存儲，首元素A[0][0]的地址為200，則元素A[10][20]的存儲地址為()。A．820B．720C．1210D．14103．設棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6先后進
2、入棧S，一個元素出棧后即進入隊列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）都是先進后出B）都是先進先出C）只允許在端點處插入和刪除D）都采用順序方式存儲7．在線索二叉樹中，指針t所指結點沒有左子樹的充要條件是。A）t->lchi
3、ld==NULLB）t->ltag==1C）t->ltag==1且t->lchild==NULLD）t->ltag==08．對具有n個結點的完全二叉樹按自上而下、從左至右的順序，從1開始依次給結點編號，則編號最小的葉子結點的序號是。A）B）+1C）-1D）-19．下列算法中是用來構造無向連通圖的最小生成樹的。A）FloydB）KruskalC）HuffmanD）Dijkstra10．下列排序算法中是穩(wěn)定的。A）堆排序B）希爾排序C）快速排序D）歸并排序11．若要對一個線性表既能較快地查找，又能適應動態(tài)變化的要求，則可采用查找方法。A）分塊B）順
4、序C）折半D）哈希12．下面關于線性表的敘述中，錯誤的是。A）線性表采用順序方式存儲，必須占用一片連續(xù)的存儲單元B）線性表采用鏈式存儲，便于進行插入和刪除操作C）線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D）線性表采用順序方式存儲，便于進行插入和刪除操作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)單鏈表的頭結點，指針p指向該鏈表的尾結點的條件是。A）p->next=NULLB）p=NULLC）p->next=headD）p=head16．設電文中出現的字母為A、B、C、D和E，每個字母在電文中出現的次數分別為：6，23，3，5和12，按哈夫曼編碼（要求左子樹根結點的權小于等于右子樹根結點的權），則字母C的編碼應是。A．10B．110C．1110D．111117．下面關于二叉樹
6、的敘述中正確的是。A）二叉樹中，任何一個結點的左子樹和右子樹上的結點個數一樣B）二叉樹中的結點個數大于0C）二叉樹中葉子結點的個數等于度為2的結點個數加1D）二叉樹中任何一個結點要么是葉子，要么恰有兩個孩子18．具有n個頂點的連通無向圖的最小生成樹中包含條邊。A）nB）n-1C）n+1D）2n19．折半查找存儲結構。A）只適用于順序B）只適用于鏈式C）既適合于順序也適合于鏈式D）既不適合于順序也不適合于鏈式20．已知某算法的執(zhí)行時間為（n3+n2+n）log2(n+2)，n為問題規(guī)模，則該算法的時間復雜度是（）。A．O(n)B．O(n2)C．O
7、(log2n)D．O(n3log2n)1234567891011121314151617181920BCADDCBBBDADDDCCCBAD二、判斷題1．算法與程序沒有區(qū)別，所以在數據結構中兩者是通用的。2．串長度是指串中不同字符的個數。3．棧是一種后進先出表。4．由于二叉樹中每個結點的度最大為2，所以二叉樹是一種特殊的樹。5．根據線性表的鏈式存儲結構中每個結點所含指針的個數，鏈表分為單鏈表和雙鏈表。6．具有3個結點且高度也為3的有序樹只有1種形態(tài)。7．先序序列和中序序列相同的二叉樹是空二叉樹或任一結點均無右子樹的非空二叉樹。8．“AOV網”的
8、中文含義是邊表示活動的網。9．在棧滿的情況下不能作進棧的運算，否則產生“上溢”。10．在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此單鏈表
