數(shù)據(jù)結構考試題三

1、一、單選題（每題2分，共20分）1. 1.對一個算法的評價，不包括如下（B ）方面的內(nèi)容。A.健壯性和可讀性B.并行性 C.正確性 D.時空復雜度2. 2.在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，則 執(zhí)行（A ）。A. p-next=HL-next; HL-next=p;B. p-next=HL; HL=p;C.p-next=HL;p=HL;D. HL=p;p-next=HL;3. 3.對線性表，在下列哪種情況下應當采用鏈表表示？（ B）A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變4. 4.一個棧的

2、輸入序列為12 3,則下列序列中不可能是棧的輸出序列的是（C ）A.23 1B.32 1C.312D.1235. 5.AOV 網(wǎng)是一種（ D ）。A .有向圖 B .無向圖C.無向無環(huán)圖D .有向無環(huán)圖6. 6.采用開放定址法處理散列表的沖突時，其平均查找長度（ S ）。A .低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突相同D.高于二分查找7. 7.若需要利用形參直接訪問實參時，應將形參變量說明為（ D ）參數(shù)。A.值 B.函數(shù) C.指針D.引用8. 8.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同 的（A）。A.行號 B.列號 C.元素值 D.非零元素個

3、數(shù)9. 9.快速排序在最壞情況下的時間復雜度為（ D ）。2、A. O（log2n）B. O（nlog2n）C. 0（n）D. 0（n）10.10. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為（C）。一-一一-_ _ 2A. O（n）B. O（1）C. O（log2n）D. O（n ）一、 二、運算題（每題6分，共24分）1. 1.數(shù)據(jù)結構是指數(shù)據(jù)及其相互之間的 s當結點之間存在M對N （M: N）的聯(lián)系時，稱這種結構為 2. 2.隊列的插入操作是在隊列的 尾進行，刪除操彳是在隊列的 一首M行。3. 3.當用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示?？眨瑒t表示棧滿 的條件是

4、top=0（要超出才為滿）4. 4.對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為 ,在表尾插入元素的時間復雜度為 5. 5.設W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標i從0到7 ,列下標j從0到3 ,則二維數(shù)組 W的數(shù)據(jù)元素共占用 個字節(jié)。W中第6行的元素和第4列的元素共占用 個字節(jié)。若按行順序存放二維數(shù)組W,其起始地址為100,則二維數(shù)組元素 W6, 3的起始地址為。6. 6.廣義表A=(a,(a,b),(a,b),c),則它的深度為,它的長度為7. 7.二叉樹是指度為2的 Wo 一棵2點數(shù)為 N的二叉樹，其所有結點的度的總和是8. 8.對一棵二叉搜索樹進行中

5、序遍歷時，得到的結點序列是一個 對一棵由算術表達式組成的二叉語法樹進行后序遍歷得到的結點序列是該算術表 達式的9. 9.對于一棵具有n個結點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為 個，其中個用于指向孩子，個 指針是空閑的。10. 10.若對一棵完全二叉樹從0開始進行結點的編號，并按此編號把它順序存儲到一 維數(shù)組A中，即編號為0的結點存儲到A0中。其余類推，則Ai元素的左孩子 元素為 右孩子元素為 2雙親元素為。11. 11.在線性表的散列存儲中，處理沖突的常用方法有 和兩種。12. 12.當待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用排序；當待排序的記錄數(shù)較大，存儲空間允許且

6、要求排序是穩(wěn)定3. top=04.O (1)O (n)5. 128441086.337.7.有序n-16558. 8.有序序列后綴表達式(或逆波蘭式)9. 9.2nn-1n+110. 10.2i+12i+2(i-1)/211. 11.開放定址法鏈接法12. 12.快速歸并二、三、運算題(每題6分，共24分)1. 1.已知一個65稀疏矩陣如下所示，試：(1)(1)寫出它的三元組線性表；15132-145-2515637圖7時，宜采用排序。填空題(每空1分，共26分)1.1.聯(lián)系 圖(或圖結構)2.2.尾 首.(2) (2)給出三元組線性表的順序存儲表示。2. 2.設有一個輸入數(shù)據(jù)的

7、序列是 46, 25, 78, 62,12, 80,試畫出從空樹起，逐個輸 入各個數(shù)據(jù)而生成的二叉搜索樹。3. 3.對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，試寫出：(1)從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2)從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；4. 4.已知一個圖的頂點集V和邊集E分別為：V=1,2,3,4,5,6,7;E=, ,;若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序歹I.二、三、運算題(每題6分，共24分)1.1. (1)

8、(1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)(3 分)E) (b)g(d)(t)算法進行排序，試給出得到的拓樸排序的序圖8(2) 三元組線性表的順序存儲表示如圖7示。2. 2.如圖8所示。3. 3. DFS:BFS:4.拓樸排序為：4 3 6 5 7 2 1三、 四、閱讀算法(每題7分，共14分)1. 1.intPrime(intn)int i=1;int x=(int) sqrt(n);while (+ix) return 1;else return 0;(1) (1)指出該算法的功能；(2) (2)該算法的時間復雜度是多少？2. 2.寫出下述算法的功能

9、：void AJ(adjlist GL, int i, int n) Queue Q;InitQueue(Q);coutiadjvex;if(!visitedj)coutjnext; 4、 五、算法填空(共8分)如下為二分查找的非遞歸算法，試將其填寫完整。Int Binsch(ElemType A ,int n,KeyType K) int low=0;int high=n-1;while (low=high) int mid=if (K=Amid.key) return mid;查找成功，返回元素的下標 else if (Kmid.key);/在左子表上繼續(xù)查 找else;/在右子表上繼續(xù)查

10、找return -1;/查找失敗，返回-15、 六、編寫算法(共8分)HL是單鏈表的頭指針，試寫出刪除頭結點的算法。ElemType DeleFront(LNode * & HL)參考答案四、閱讀算法(每題7分，共14分)1. 1.(1)判斷n是否是素數(shù)(或質(zhì)數(shù))(2) O ( 4n )2. 2.功能為：從初始點 vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。五、算法填空(8分)(low+high)/2high=mid-1low=mid+1六、編寫算法(8分)ElemType DeleFront(LNode * & HL)if (HL=NULL)cerr空表next;ElemType temp=

11、p-data;delete p;return temp;)(二)1、 一、單選題(每題2分，共20分)1. 1.棧和隊列的共同特點是(A )。A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點2. 2.用鏈接方式存儲的隊列，在進行插入運算時(D ).A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改3. 3.以下數(shù)據(jù)結構中哪一個是非線性結構？( C )A.隊列B.棧C.線性表D.二叉樹4. 4.設有一個二維數(shù)組Amn,假設A0存放位置在644(10), A22存放位置A33(10)存放在什么位置？腳注(10)表示用C. 692D. 69

12、6B.無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)c小-1D. 2A19中，第一個元素放A1中，現(xiàn)在676(10),每個元素占一個空間，問10進制表示。CA. 688B. 6785. 5.樹最適合用來表示( C)。A.有序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)6. 6.二叉樹的第k層的結點數(shù)最多為(D).A. 2k-1B.2K+1C.2K-17. 7.若有18個元素的有序表存放在一維數(shù)組進行二分查找，則查找 A 3的比較序列的下標依次為(D )A.1 , 2, 3B. 9, 5, 2, 3C.9, 5, 3D.9, 4, 2, 38. 8.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為C

13、A.O (1)B.O (n)C.O (1og2n)D.O (n2)9. 9.對于線性表(7, 34, 55, 25, 64, 46, 20, 10)進行散列存儲時，若選用 H (K) =K%9作為散列函數(shù)，則散列地址為1的元素有(D )個，A. 1B. 2C. 3D. 410.10. 設有6個結點的無向圖，該圖至少應有(A)條邊才能確保是一個連通圖。A.5B.6C.7D.82、 二、填空題(每空1分，共26分) 1. 1.通常從四個方面評價算法的質(zhì)量： 、2. 2.一個算法的時間復雜度為(n3+n2log2n+14n)/n2,其數(shù)量級表示為 3. 3.假定一棵樹的廣義表表示為 A (C, D

14、(E, F, G) , H (I, J),則樹中所含 的結點數(shù)為個，樹的深度為,樹的度為 04. 4.后綴算式923+- 102/-的值為 o中綴算式(3+4X) -2Y/3對應的后綴算式為5. 5.若用鏈表存儲一棵二叉樹時，每個結點除數(shù)據(jù)域外，還有指向左孩子和右孩子 的兩個指針。在這種存儲結構中，n個結點的二叉樹共有 個指針域，其中有 個指針域是存放了地址，有 個指針是空指針。6. 6.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含 邊結點分別有個和個。7. 7.AOV網(wǎng)是一種的圖。8. 8.在一個具有n個頂點的無向完全圖中，包含有 條邊,在一個具有n個頂點的有向完全

15、圖中，包含有條邊。9. 9.假定一個線性表為(12,23,74,55,63,40),若按Key % 4條件進行劃分，使得同一 余數(shù)的元素成為一個子表，則得到的四個子表分別為 口10. 10.向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹 的高度11. 11.在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為 ,整 個堆排序過程的時間復雜度為 。12. 12.在快速排序、堆排序、歸并排序中， 排序是穩(wěn)定的。填空題(每空1分，共26分)1. 1.正確性 易讀性 強壯性 高效率2. 2. O(n)3. 3.9334. 4.-13 4 X * + 2 Y * 3 / -5.

16、 5.2nn-1n+16. 6. e2e7. 7.有向無回路8. 8. n(n-1)/2n(n-1)9. 9. ( 12, 40)( ) (74) (23,55, 63)10. 10.增加 111. 11. O(log 2n)O(nlog2n)12. 12.歸并三、運算題(每題6分，共24分)1. 1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A 0.next,試寫出該線性表。A data next605078903440357204101234562. 2.請畫出圖10的鄰接矩陣和鄰接表。3. 3.已知一個圖的頂點集V和邊集E分別為：V=1,2,3,4,5,6,7;E=(1,2)3,(1

17、,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊4. 4.畫出向小根堆中加入數(shù)據(jù)四、 四、閱讀算法(每題4. 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化 7分，共14分)1. 1. LinkList mynote(LinkList L)/L是不帶頭結點的單鏈表的頭指針 if(L&L-next)q=L; L=L next; p=L;S1:S2:while(p next) p=p next；p next=q；

18、q next=NULL ;return L；請回答下列問題：(1)說明語句S1的功能；(2)說明語句組S2的功能；(3)設鏈表表示的線性表為(ai,a2,an),寫出算法執(zhí)行后的返回值所表示 的線性表。2. 2.void ABC(BTNode * BT)if BT ABC (BT-left);ABC (BT-right);coutdatadata)計em=BST-data;/查找成功return ;else if(itemdata)return Find(,item);else return Find(,item);/if6、 六、編寫算法(共8分)統(tǒng)計出單鏈表HL中結點的值等于給定值X的結點

19、數(shù)。int CountX(LNode* HL,ElemType x)參考答案三、運算題(每題6分，共24分)1. 1.線性表為：(78, 50, 40, 60, 34, 90)0 1110 10 10 1 110 11 10 10 12. 2.鄰接矩陣：J 1 1 1 0鄰接表如圖11所示：圖113. 3.用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4, (1,3)5,(1,4)8,(2,5)10,(4,7)204. 4.見圖122458324580 總圖12照閱讀算法(闡7分第14港1、 1. (1)條丸表的尾結點UU(2)將第一個結點鏈接到鏈表的尾部，作為新的尾結(3)返回

20、的線性表為(a2,a3r2an,a1)2、 2.遞歸地后序遍歷鏈式存儲的入2、 五、空3， 邊 共8分)true BST-left. BST-right3、 六、編寫算硒int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計數(shù)器while(p!=NULL) if (P-data=x) i+;p=p-next;/while,出循環(huán)時i中的值即為x結點個數(shù) return i;/CountX(三)單選題(每小題2分，共8分)1、1、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度(即x與元素的平均比較次數(shù)，假定

21、查找每個元素的概率都相等)為(C)。A nB n/2 C (n+1)/2 D (n-1)/22、2、在一個單鏈表中，若q所指結點是p所指結點的前驅(qū)結點，若在q與p之間插入一個s所指的結點，則執(zhí)行(D )。A s- link=pTink;pf link=s;B pTink=s;s- link=q;C pf link=sTink;s- link=p;D q -link=s;s- link =p;3、 3、棧的插入和刪除操作在(A)進行。A棧頂 B棧底 C任意位置D指定位置4、 4、由權值分別為11, 8, 6, 2, 5的葉子結點生成一棵哈夫曼樹，它的帶權路徑 長度為(B)A 24B 71C 48

22、D 53二、填空題(每空1分，共32分)1、1、數(shù)據(jù)的邏輯結構被分為 :?口四種。2、2、一種抽象數(shù)據(jù)類型包括?口網(wǎng)個部分。3、3、在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為 ao.next,則該線性表為二a 0123456786056423874254376201datanext4、4、在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件 分別為 口5、5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的,該循環(huán)隊列白最大長度為 6、6、當堆棧采用順序存儲結構時，棧頂元素的值可用 表示；當堆棧采用鏈接存儲結構時,棧頂元素的值可用 表示。7

23、、7、一棵高度為5的二叉樹中最少含有 個結點，最多含有 個結點；一棵高度為5的理想平衡樹中，最少含有 個結點，最多含有個結點。8、8、在圖的鄰接表中，每個結點被稱為 ,通常它包含三個域：一9、9、在一個索引文件的索引表中，每個索引項包含對應記錄的 和兩項數(shù)據(jù)。10、 10、假定一棵樹的廣義表表示為 A (B (C, D (E, F, G) , H (I, J),則樹中所含的結點數(shù)為個，樹的深度為 樹的度為，結點H的雙親結點為 孩子結點為。11、 11、在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為整個堆排序過程白時間復雜度為 o12、 12、在對m階的B_W插入元素的過程中，每向一個

24、結點插入一個索引項(葉子結點中的索引項為關鍵字和空指針)后，若該結點的索引項數(shù)等于個，則必須把它分裂為 個結點。、填空題(每空 1分，共32分)1:集合、線性、樹、圖；2:數(shù)據(jù)描述、操作聲名；3: (38, 56, 25, 60, 42, 74);4: HL-next =NULL ； HL=HL -next；5: 前一個位置；n-1 ；6： S.stack S.top;HS - data;7: 5318: 邊結點、鄰接點域、權域、鏈域；9: 索引值域、開始位置域；10: 10、3、3、B、I 和 J;11: O (log2n)、O(nlog 2n);12： m、 m - 12、 三、運算題(每

25、小題6分，共24分)1、1、已知一組記錄的排序碼為(46, 79, 56, 38, 40, 80, 95, 24),寫出對 其進行快速排序的每一次劃分結果。2、2、一個線性表為 B= (12, 23, 45, 57, 20, 03, 78, 31, 15, 36),設散歹U 表為HT0.12,散列函數(shù)為H (key) = key % 13并用線性探查法解決沖突，請 畫出散列表，并計算等概率情況下查找成功的平均查找長度。3、3、已知一棵二叉樹的前序遍歷的結果序列是ABECKFGHIJ ,中序遍歷的結果是EBCDAFHIGJ ,試寫出這棵二叉樹的后序遍歷結果。4、4、已知一個圖的頂點集 V各邊集G

26、如下：V =0,1, 2, 3,4, 5, 6,7,8, 9;E = (0, 1), (0, 4) ,(1, 2) ,(1, 7),(2,8),(3,4),(3,8),(5, 6), (5, 8) ,(5, 9) ,(6, 7),(7,8),(8,9)當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V。出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時鄰接表表示時3、 四、閱讀算法，回答問題(每小題 8分，共16分)1、假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 3

27、0 91 34 - 1,請寫出 輸出結果。# include # include consst int stackmaxsize = 30;typedef int elemtype;struct stack elemtype stack stackmaxsize;int top;；# include “stack.hVoid main ()stack a;initstack(a);int x;cin x;while (x! = -1) push (a, x ); cin x;while (!stackempty (a) cout pop (a) ” cout end1;該算法的輸出結果為：2、

28、閱讀以下二叉樹操作算法，指出該算法的功能。Template void BinTree : unknown (BinTreeNode*t) BinTreeNode *p =t, *temp; if (p!=NULL) temp = 尸 leftchild; pf leftchild = pfrightchild; pf rightchild = temp; unknown(pTeftchild); undnown(pfrightchild); 該算法的功能是：4、 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分) 對順序存儲的有序表進行二分查找的遞歸算法。int Binsch( ElemT

29、ype A ,int low ,int high,KeyType K )if (low = high)int mid = 1if ( K= = A mid .key ) return mid;else if ( K S2請在空白處填入適當?shù)膬?nèi)容。int comstr(LinkString s1,LinkString s2)/s1和s2為兩個鏈用的頭指針while(s1&s2)if(s1 datedate)return 1;if(s1 dates2 date)return1；if( )return 1 ；if()return1 ；31 .閱讀下面的算法LinkList mynote(LinkLi

30、st L)/L是不帶頭結點的單鏈表的頭指針if(L&L-next)q=L; L=L next; p=L;51: while(p next) p=p next；52: p next=q； q next=NULL ;return L；請回答下列問題：(1)說明語句S1的功能；(2)說明語句組S2的功能；(3)設鏈表表示的線性表為(a1,a2,an),寫出算法執(zhí)行后的返回值所表示 的線性表。,32.假設兩個隊列共享一個循環(huán)向量空間(參見右下入_夫q其類型Queue2定義如下：typedef structDateType dataMaxSize；int front2,rear2；Queue2；對于i=

31、0或1, fronti和reari分別為第i個隊列的頭指針和尾指針。請對以下算法 填空，實現(xiàn)第i個隊列的入隊操作。int EnQueue (Queue2*Q,int i,DateType x)/若第i個隊列不滿，則元素x入隊列，并返回1；否則返回0if(i1)return 0 ；if(Q reari=Q front return0；Q data =x ；Q reari=;returnl；33 .已知二叉樹的存儲結構為二叉鏈表，閱讀下面算法。typedef struct node DateType dataStruct node * next；ListNode;typedef ListNode

32、* LinkList ；LinkList Leafhead=NULL ；Void Inorder (BinTree T)LinkList s ；If(T)Inorder(T lchild);If (!T lchild)&(!T rchild) s=(ListNode*)malloczeof(ListNode); s data=T data； s next=Leafhead;Leafhead=Inorder(T rchild);對于如下所示的二叉樹(1)畫出執(zhí)行上述算法后所建立的結構；(2)說明該算法的功能。五、算法設計題(本題共10分)34 .閱讀下列函數(shù) arrange

33、(int a,int 1,int h,int x)/1和h分別為數(shù)據(jù)區(qū)的下界和上界int i,j,t ；i=1 ； j=h ；while(ij)while(i=x)j-； while(i=x)i+ ； if(ij) t=aj ； aj=ai ； ai=t ； if(ai 31.2 1 1 2ASL（2 ）平均查找長度 一 517.p next next19. 1221. 38425.多關鍵字共20分）95四、算法閱讀題（本大題共4小題，每小題5分，共20分）30. S1=S1 next s2=s2 nexts2(或 s2!=NULL 或 s2&!s1)si(或 s1!=NULL 或 s1&!s

34、2) return 031. (1)查詢鏈表的尾結點(2)將第一個結點鏈接到鏈表的尾部，作為新的尾結點(3)返回的線性表為(的電,an,ai)32. (i + 1)%2(或 1 i) Q reari (Q reari + )%Maxsize33. (1)Leafhead, F | H | D | ALeafhead(2)中序遍歷二叉樹，按遍歷序列中葉子結點數(shù)據(jù)域的值構建一個以為頭指針的逆序單鏈表(或按二叉樹中葉子結點數(shù)據(jù)自右至左鏈接成一個鏈表)。五、算法設計題(本題共10分)34. (1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組 a中的元素并返回分界值i,使所有x 的元素均落在a1.i上，使所有方x的元素

35、均落在ai + 1.h上。int f(int b口,int n)int p,q；p=arrange(b,0,n1,1)；q= arrange(b,0,p,0)；(2) int f(int b口,int n) 或 int p,q；p=arrange(b,0,n- 1,0)；q= arrange(b,p+1,n-1,1)；return q p ；return p q ；(五)一、選擇題(20分)1 .組成數(shù)據(jù)的基本單位是()。(A)數(shù)據(jù)項 (B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量2 .設數(shù)據(jù)結構 A=(D, R),其中 D=1 , 2, 3, 4, R=r , r=, , ,則數(shù)據(jù)結構 人是()

36、。(A)線性結構(B)樹型結構(C)圖型結構(D)集合3 .數(shù)組的邏輯結構不同于下列()的邏輯結構。(A)線性表(B)棧(C)隊列(D)樹4 .二叉在t中第i(i2曷比的結點數(shù)最多有()個。(A) 2i(B) 2i(C) 2i-1(D) 2i-15 .設指車+變量p指向單鏈表結點A,則刪除結點A的后繼結點B需要的操作為()(A) p-next=p-next-next(B) p=p-next(C) p=p-next-next(D) p-next=p6 .設棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S, 一個元素出棧后即進入隊列 Q,若6個元素出列的順序為E2、E

37、4、E3、E6、E5和 E1,則棧S的容量至少應該是()。(A) 6(B) 4(C) 3(D) 27 .將10階對稱矩陣壓縮存儲到一維數(shù)組 A中，則數(shù)組A的長度最少為()。(A) 100(B) 40(C) 55(D) 808 .設結點A有3個兄弟結點且結點B為結點A的雙親結點，則結點B的度數(shù)數(shù)為 ()。(A) 3(B) 4(C)5(D)19 .根據(jù)二叉樹的定義可知二叉樹共有()種不同的形態(tài)。(A) 4(B) 5(C)6(D)710.10.設有以下四種排序方法，則()的空間復雜度最大。(A)冒泡排序(B)快速排序(C)堆排序(D)希爾排序二、填空題(30分)1. 1.設順序循環(huán)隊列Q0: m-1的隊頭指針和隊尾指針分別為F和R,其中隊頭指針 F指向當前隊頭元素的前一個位置，隊尾指針R指向當前隊尾元素所在的位置，則出隊列的語句為F =；。2. 2.設線性表中有n個數(shù)據(jù)元素，則在順序存儲結構上實現(xiàn)順序查找的平均時間復 雜度為,在鏈式存儲結構上實現(xiàn)順序查找的平均時間復雜度為3.