1、文檔供參考，可復制、編制，期待您的好評與關注！ 一、選擇題 1、 下列關于數據和邏輯結構的敘述中，哪一個是不正確的（ ）。 A ) 數據的邏輯結構是數據間關系的描述 B) 數據的邏輯結構抽象反映數據元素間的邏輯關系 C) 數據的邏輯結構具體反映數據在計算機中的存儲方式 D) 數據的邏輯結構分為線性結構和非線性結構2、 以下關于數據的存儲結構的敘述中哪一條是正確的（ ）。 A) 數據的存儲結構是數據間關系的抽象描述 B) 數據的存儲結構是邏輯結構在計算機存儲器中的實現 C) 數據的存儲結構分為線性結構和非線性結構 D) 數據的存儲結構對數據運算的具體實現沒有影響3、由于二叉樹中每個結點的度最大為

2、2，所以二叉樹是一種特殊的樹，這種說法 B . （A）正確 （B）錯誤4、某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是 (A)空或只有一個結點 (B) 完全二叉樹(C)二叉排序樹 (D) 高度等于其節點數5、深度為5的二叉樹至多有 C 多少個結點.(A)16 (B)32 (C)31 (D)106、根據使用頻率為5個字符設計的哈夫曼編碼不可能是 C（A）111，110，10，01，00 （B）000，001，010，011，1（C）100，11，10，1，0 （D）001，000，01，11，107、一個n個頂點的無向圖最多有條邊。(A) n (B) n(n-1) (C) n(

3、n-1)/2 (D) 2n8、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。（A）1/2 （B）1 （C）2 （D）49、關鍵路徑是事件結點網絡中 。（A）從源點到匯點的最長路徑 （B）最長的回路（C）從源點到匯點的最短路徑 (D）最短的回路10、下面不正確的說法是 。A、關鍵活動不按期完成就會影響整個工程的完成時間B、任何一個關鍵活動提前完成，將使整個工程提前完成C、所有關鍵活動都提前，則整個工程提前完成D、某些關鍵活動若提前完成，將使整個工程提前完成。11、采用順序查找法查找長度為n的線性表時，則查找成功時的平均查找長度為 C 。 (A) n (B) n/2 (C) (n+

4、1)/2 (D) (n-1)/212、在一個長度為12的有序表，按折半查找法對該表進行查找，在表內各元素等概率情況下查找成功所需的平均比較次數為 B 。（A）35/12 （B）37/12 （C）39/12 （D）43/1213、查找效率最高的二叉排序樹是 C 。 （A）所有結點的左子樹都為空的二叉排序樹 （B）所有結點的右子樹都為空的二叉排序樹 （C）平衡二叉樹 （D）沒有左子樹的二叉排序樹14、以下說法錯誤的是 B 。A、散列法存儲的基本思想是由關鍵碼值決定數據的存儲地址B、散列表的結點中只包含數據元素自身的信息，不包含任何指針C、裝填因子是散列法的一個重要參數，它反映了散列表的裝填程度D、

5、散列表的查找效率主要取決于散列表造表時選取的散列函數和處理沖突的方法15、散列表的平均查找長度 A 。A.與處理沖突方法有關與表長無關 B.與處理沖突方法無關與表的長度有關C.與處理沖突方法有關且與表的長度有關 D.與處理沖突方法無關且與表的長度無關二、填空題1、樹和二叉樹的主要差別是，。（1）每個結點最多有兩棵子樹； （2）子樹有左右之分2、深度為k的完全二叉樹至少有個結點，至多有個結點。2k-1, 2k-1,3、一棵二叉樹的第i(i³1)層最多有 個結點；一棵有n（n>0）個結點的滿二叉樹共有個葉子結點和個非葉子結點。 (n+1)/2,(n-1)/24、假設一棵二叉樹的結點

6、數為33個，則它的最小高度為（ ），最大高度為（ ）。 最小高度為：6，最大高度為：335、一個高度為h的滿m叉樹，第k層最多有（ ）個結點，整棵樹最多有（ ）個結點。第k層最多有 mk-1,整棵樹最多有(mk-1)/m-16、一個圖的表示法是唯一的，而表示法是不唯一的。7、在有n個頂點的有向圖中，每個頂點的度最大可達8、設線性表（a1，a2，a500）元素的值由小到大排列，對一個給定的k值用折半法查找線性表，在查找不成功的情況下至多需比較 （ ëlog2nû+1 ）次9、一個無序序列可以通過構造一棵 二叉排序樹 樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過

7、程。10、在散列存儲中，裝填因子的值越大，則；的值越小，則.。 發生沖突的可能性就越大；發生沖突的可能性就越小；二、簡答題 1 數據結構的存儲方式有哪幾種？ 常用的存儲表示方法有四種 : 1 、順序存儲方法：它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構，通常借助程序語言的數組描述。 2 、鏈接存儲方法：它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針字段表示。由此得到的存儲表示稱為鏈式存儲結構 , 通常借助于程序語言的指針類型描述。 3 、索引存儲方法：除建立存儲結點信息外，還建立

8、附加的索引表來標識結點的地址。組成索引表的索引項由結點的關鍵字和地址組成。若每個結點在索引表中都有一個索引項，則該索引表稱之為稠密索引（ Dense Index ）。若一組結點在索引表中只對應一個索引項，則該索引表稱為稀疏索引。 4 、散列存儲方法：就是根據結點的關鍵字直接計算出該結點的存儲地址。2 算法的時間復雜度僅與問題的規模相關嗎 ? 【解析】 算法的時間復雜度不僅與問題的規模相關，還與輸入實例中的初始狀態有關。但在最壞的情況下，其時間復雜度就是只與求解問題的規模相關的。我們在討論時間復雜度時，一般就是以最壞情況下的時間復雜度為準的。3、設n為正整數，利用大"O"記號

9、，將下列程序段的執行時間表示為n的函數。(1) i=1; k=0; while(i<n) k=k+10*i;i+; （1）分析：i=1; /1k=0; /1  while(i<n) /n k=k+10*i; /n-1i+; /n-1 由以上列出的各語句的頻度，可得該程序段的時間消耗：T(n)=1+1+n+(n-1)+(n-1)=3n可表示為T(n)=O(n)(2) i=0; k=0;dok=k+10*i; i+; while(i<n); （2）分析：i=0; /1k=0; /1do /nk=k+10*i; /ni+;

10、 /nwhile(i<n);/n 由以上列出的各語句的頻度，可得該程序段的時間消耗：T(n)=1+1+n+n+n+n=4n+2可表示為T(n)=O(n)(3) i=1; j=0; while(i+j<=n) if (i>j) j+;else i+;分析：通過分析以上程序段，可將i+j看成一個控制循環次數的變量，且每執行一次循環，i+j的值加1。該程序段的主要時間消耗是while循環，而while循環共做了n次，所以該程序段的執行時間為：T(n)=O(n)(4)x=n; / n>1 while (x>=(y+1)*(y+1)y

11、+;分析：由x=n且x的值在程序中不變，又while的循環條件(x>=(y+1)*(y+1)可知：當(y+1)*(y+1)剛超過n的值時退出循環。由(y+1)*(y+1)<n得：y<n0.5-1所以，該程序段的執行時間為：向下取整(n0.5-1)4、設三個函數f,g,h分別為 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 請判斷下列關系是否成立：(1) f(n)=O(g(n)  (2) g(n)=O(f(n)  (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 通俗地

12、說，就是當n時，f(n)的函數值增長速度與T（n)的增長速度同階。一般，一個函數的增長速度與該函數的最高次階同階。即：O(f(n)=n3 O(g(n)=n3 O(h(n)=n1.5答：（1）成立。 （2）成立。（3）成立。（4）不成立。5 何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜? 6在順序表中插入和刪除一個結點需平均移動多少個結點?具體的移動次數取決于哪兩個因素? 7為什么在單循環鏈表中設置尾指針比設置頭指針更好? 尾指針是指向終端結點的指針，用它來表示單循環鏈表可以使得查找鏈表的開始結點和終端結點都很方便，設一帶頭結點的單循環鏈表，其尾指針為rear，則開始結點和終端

13、結點的位置分別是rear->next->next 和 rear, 查找時間都是O(1)。 若用頭指針來表示該鏈表，則查找終端結點的時間為O(n)。8在單鏈表、雙鏈表和單循環鏈表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點*p從相應的鏈表中刪去?若可以，其時間復雜度各為多少?下面分別討論三種鏈表的情況。1. 單鏈表。若指針p指向某結點時，能夠根據該指針找到其直接后繼，能夠順后繼指針鏈找到*p結點后的結點。但是由于不知道其頭指針，所以無法訪問到p指針指向的結點的直接前趨。因此無法刪去該結點。2. 雙鏈表。由于這樣的鏈表提供雙向指針，根據*p結點的前趨指針和后繼指針可以查找到其

14、直接前趨和直接后繼，從而可以刪除該結點。其時間復雜度為O(1)。3. 單循環鏈表。根據已知結點位置，可以直接得到其后相鄰的結點位置(直接后繼)，又因為是循環鏈表，所以我們可以通過查找，得到p結點的直接前趨。因此可以刪去p所指結點。其時間復雜度應為O(n)。9、試描述頭指針、頭結點、開始結點的區別、并說明頭指針和頭結點的作用。開始結點是指鏈表中的第一個結點，也就是沒有直接前趨的那個結點。 鏈表的頭指針是一指向鏈表開始結點的指針(沒有頭結點時)，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。 頭結點是在鏈表的開始結點之前附加的一個結點。有了頭結點之后，頭指針指向頭結點，不論鏈表否為空

15、，頭指針總是非空。而且頭指針的設置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致(都是在某一結點之后)。10、已知一個順序表L，其中的元素遞增有序，設計一個算法插入一個元素x之后保持該順序表仍然遞增有序排列算法如下： void InsertIncreaseList( Seqlist *L , Datatype x ) if ( L->length>=ListSize)Error(“overflow"); for ( i=L -> length ; i>0 && L->data i-1 > x ; i-)L->data

16、 i =L->data i-1 ; / 比較并移動元素L->data i =x;L -> length+; 11、設計算法，從給定的順序表L中刪除元素值在min到max(min£max)之間的所有元素，要求以較高的效率實現。void DeleteList ( LinkList L, DataType min , DataType max )ListNode *p , *q , *s;p=L;while( p->next && p->next->data <=min ) /找比min大的前一個元素位置 p=p->next;

17、q=p->next;/p指向第一個不大于min結點的直接前趨，q指向第一個大于min的結while(q &&q->data<max) s=q;q=q->next; free(s);/刪除結點，釋放空間 p->next=q;/將*p結點的直接后繼指針指向*q結點12、下列函數的功能是，對以帶頭結點的單鏈表作為存儲結構的兩個遞增有序表（表中不存在值相同的數據元素）進行如下操作：將所有在Lb表中存在而La表中不存在的結點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入合適內容，使其成為一個完整的算法。13、已知一個線性表有n（n30）個

18、元素，其中每個元素的數據占8個字節。假設一個指針的大小為4個字節。如果采用有30個元素的數組存儲，那么當數組中有效元素個數n滿足什么條件時，數組的存儲效率比不帶頭結點的單鏈表更高。數組總的空間240個字節，數組的效率為8n/240；鏈表的總空間為12n，效率為8n/12n。故可得：n2013順序隊列一般應該組織成為循環隊列的形式，而且一般隊列頭或為隊列尾其中之一虛指一位，滿隊列時實際上數組中還有一個空閑位置。請分析這樣設置的理由。有利于判斷隊列是空還是滿。因為隊列有n+2種狀態：空，1個元素， 2個元素，, n個元素，滿。但實際上rear只有n種可能的取值，故必須尋求其他途徑解決隊空和隊滿。當

19、然也有其他方法。14隊列可以用循環單鏈表來實現，故可以只設置一個頭指針或者只設置一個尾指針。請分析對于循環單鏈表實現的隊列，用那種方案更合適設置尾指針。因為是循環單鏈表，設置尾指針，可以在O(1)的時間內找到頭；如果只設置頭指針，要在O(n)時間內找到尾。設置尾指針，入隊和出隊的時間復雜度均為O(1)，設置頭指針，出隊O(1)，入隊O(n)。15、假設一個單循環鏈表，其結點含有三個域pre,data和link。其中data為數據域;pre為指針域，它的值為空指針(NULL)；link為指針域，指向后繼結點。設計算法，將此表改為雙向循環鏈表設s為指向循環鏈表某一結點的指針，p,q中間結點；指針s

20、在搜索過程中保持不變，作為結束條件，每執行一次就將指針p賦給q所指節電的pre，并修改p,q，保持p在后，q在前。doulink(s:dLinkList) /非空表 p=s; do q=p->next; q->pre=p; p=q; while(p!=s); 16、假設循環隊列只設rear和quelen來分別指示隊尾元素的位置和隊中元素的個數，試給出判斷此循環隊列的隊滿條件，并寫出相應的入隊和出隊算法，要求出隊時需返回隊頭指針。隊滿條件： Q.quelen= MAX_QUEUE;入隊:設Q.rear指向隊尾元素if(Q.quelen!= MAX_QUEUE) Q.rear= (Q.

21、rear+1)% MAX_QUEUEQ.dataQ.rear=x;Q.quelen+;出隊：設Q.rear指向隊尾元素if(Q.quelen!=0) /隊列非空 front=(Q.rear+ MAX_QUEUE- Q.quelen)%MAX_MAXSIZE; Q.quelen-; return(front); 17、請說明一棵二叉樹進行先序、中序和后序遍歷，其葉結點的次序是否會發生變化？為什么？解答：二叉樹中葉結點必在某結點的左或右子樹中，三種遍歷方法對左右子樹的遍歷都是按先左后右的原則進行。所以在三種遍歷序列中葉結點的相對次序是不會發生變化的。18、給定14各字母，假設它們的權都相等。采用HUFFMAN編碼，則每個字母的平均代碼長度是多少？（12*4+2*3）/14=54/14=3.857 19、有7個帶權結點，其權值分別為4，7，8，2，5，16，30，以它們為葉子結點構造一顆哈夫曼樹（要求按每個結點的左子樹根結點的權值小于或等于右子樹根結點的權值的次序構造），并計算出其帶權路徑長度WPL。