數(shù)據(jù)結構期末復習

1、數(shù)據(jù)結構期末復習1.一個棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是（）。 單選題 *A. edcbaB. decbaC. dceab(正確答案)D. abcde2.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1.m，topi代表第i 個棧( i =1,2)棧頂，棧1 的底在v1，棧2 的底在Vm，則棧滿的條件是（）。 單選題 *A. top2-top1|=0B. top1+1=top2(正確答案)C. top1+top2=mD. top1=top23.若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為（）。 單選題 *A. iB. n=

2、iC. n-i+1(正確答案)D. 不確定4.棧結構通常采用的兩種存儲結構是（）。 單選題 *A. 順序存儲結構和鏈式存儲結構(正確答案)B. 散列方式和索引方式C. 鏈表存儲結構和數(shù)組D. 線性存儲結構和非線性存儲結構5.判定一個棧ST(最多元素為m0)為空的條件是（）。 單選題 *A. ST.top != -1B. ST.top = = -1(正確答案)C. ST.top != m0-1D. ST.top = = m0-16.判定一個棧ST(最多元素為m0)為棧滿的條件是（）。 單選題 *A. ST.top != -1B. ST.top = = -1C. ST.top != m0-1D.

3、ST.top = = m0-1(正確答案)7.棧的特點是（），隊列的特點是（）。 *A. 先進先出(正確答案)B.先進后出(正確答案)8.一個隊列的入列序列是1，2，3，4，則隊列的輸出序列是（）。 單選題 *A. 4，3，2，1B. 1，2，3，4(正確答案)C. 1，4，3，2D. 3，2，4，19.判定一個循環(huán)隊列QU(最多元素為m0)為空的條件是（）。 單選題 *A. front= =rear(正確答案)B. front！=rearC. front= =(rear+1)%m0D. front！=(rear+1)%m010.判定一個循環(huán)隊列QU(最多元素為m0)為滿隊列的條件是（）。 單

4、選題 *A. front= = rearB. front！= rearC. front= =(rear+1)%m0(正確答案)D. front！=(rear+1)%m011.循環(huán)隊列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是（）。 單選題 *A. (rear-front+m)%m(正確答案)B. rear-front+1C. rear-front-1D. rear-front12.棧和隊列的共同點是（）。 單選題 *A. 都是先進后出B. 都是先進先出C. 只允許在端點處插入和刪除元素D. 沒有共同點(正確答案)13.在一棵度為3的樹中，

5、度為3的結點數(shù)為2個，度為2的結點數(shù)為1個，度為1的結點數(shù)為2個，則度為0的結點數(shù)為（）個。 單選題 *A. 4B. 5C. 6(正確答案)D. 714.假設在一棵二叉樹中，雙分支結點數(shù)為15，單分支結點數(shù)為30個，則葉子結點數(shù)為（）個。 單選題 *A. 15B. 16(正確答案)C. 17D. 4715.假定一棵三叉樹的結點數(shù)為50，則它的最小高度為（）。 單選題 *A. 3B. 4C. 5(正確答案)D. 616.在一棵二叉樹上第4層的結點數(shù)最多為（）。 單選題 *A. 2B. 4C. 6D. 8(正確答案)17.用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數(shù)組中R1.n，結點Ri若

6、有左孩子，其左孩子的編號為結點（）。 單選題 *A. R2i+1B. R2i(正確答案)C. Ri/2D. R2i-118.由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）。 單選題 *A. 24B. 48C. 72D. 53(正確答案)19.線性結構是數(shù)據(jù)元素之間存在一種（）。 單選題 *A一對多關系B多對多關系C多對一關系D一對一關系(正確答案)20.數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（）結構。 單選題 *A存儲B物理C邏輯(正確答案)D物理和存儲21.算法分析的目的是（）。 單選題 *A找出數(shù)據(jù)結構的合理性B分析算法的效率以求改進(正確答案)C研究

7、算法中的輸入和輸出的關系D分析算法的易懂性和文檔性22.算法分析的兩個主要方面是（）。 單選題 *A空間復雜性和時間復雜性(正確答案)B正確性和簡明性C可讀性和文檔性D數(shù)據(jù)復雜性和程序復雜性23.計算機算法指的是（）。 單選題 *A計算方法B排序方法C解決問題的有限運算序列(正確答案)D調度方法24.從邏輯上可以把數(shù)據(jù)結構分為（）。 單選題 *A線性結構和非線性結構(正確答案)B緊湊結構和非緊湊結構C動態(tài)結構和靜態(tài)結構D內部結構和外部結構25.線性表是（）。 單選題 *A一個有限序列，可以為空(正確答案)B一個有限序列，不能為空C一個無限序列，可以為空D一個無限序列，不能為空26.帶頭結點的單

8、鏈表L為空的判定條件是（）。 單選題 *Ahead=nullBhead .next=null(正確答案)Chead .next=LDhead!=null27.在表長為n的單鏈表中，算法時間復雜度為O(n)的操作為（）。 單選題 *A刪除p結點的直接后繼結點B在p結點之后插入一個結點C刪除表中第一個結點D查找單鏈表中第i個結點(正確答案)28.在表長為n的順序表中，算法時間復雜度為O(1)的操作為（）。 單選題 *A在第i個元素前插入一個元素B刪除第i個元素C在表尾插入一個元素(正確答案)D查找其值與給定值相等的一個元素29.設單鏈表中指針p指向結點ai，若要刪除ai結點，則需修改指針的操作為（

9、）。 單選題 *Ap=p.nextBp.next=p.next.next(正確答案)Cp=p.next.nextDnext=p單選題1.數(shù)據(jù)的物理結構包括_ 的表示和存儲和 _的表示和存儲。 填空題_(答案：順序結構、鏈式結構)2.對于給定的n個元素,可以構造出的邏輯結構有（ ）,( )，( )，( )四種。 填空題_(答案：集合結構、線性結構、樹形結構、圖狀結構)3.一個算法具有5個特性：( )、（ ）、（ ），有零個或多個輸入、有一個或多個輸出。 填空題_(答案：有窮性、確定性、可行性)4.抽象數(shù)據(jù)類型被形式地定義為（ ），其中D是（ ）的有限集合，S是D上的（ ）有限集合， P是對D的（

10、 ）集合。 填空題_(答案：D,S,P、數(shù)據(jù)元素、關系、基本操作)5.數(shù)據(jù)結構主要包括數(shù)據(jù)的（ ）、數(shù)據(jù)的（ ）和數(shù)據(jù)的（ ）這三個方面的內容。 填空題_(答案：邏輯結構、存儲結構、操作)6.一個算法的效率可分為（ ）效率和（ ）效率。 填空題_(答案：時間、空間)7.線性表的兩種存儲結構分別為（ ）和（ ）。 填空題_(答案：順序存儲結構、鏈式存儲結構)8.順序表中，邏輯上相鄰的元素，其物理位置（ ）相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置（ ）相鄰。 填空題_(答案：不一定、一定)9.若經(jīng)常需要對線性表進行插入和刪除操作，則最好采用（ ）存儲結構，若線性表的元素總數(shù)基本穩(wěn)定，且很少進行