【正文】 。i++,j++) t[j]=s[i]。int lev=0。void level(bitree *bt,int x){ if (bt!=0){lev++。}}數(shù)據(jù)結構試卷（十二） 字符串的長度是指（ ）。 建立一個長度為n的有序單鏈表的時間復雜度為（ ） (A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)3. 3. (A) 兩個字符串的長度相等 (B) 兩個字符串中對應位置上的字符相等 (C) 同時具備(A)和(B)兩個條件 (D) 以上答案都不對4. 4. (A) 99 (B) 97 (C) 91 (D) 935. 5. (A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)6. 6. (A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4] (C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]7. 7. (A) 8 (B) 7 (C) 6 (D) 58. 8. (A) 5 (B) 6 (C) 7 (D) 89. 9. (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc10. 10. 隊列是一種（ ）的線性表。（ ）3. 3. 分塊查找的基本思想是首先在索引表中進行查找，以便確定給定的關鍵字可能存在的塊號，然后再在相應的塊內進行順序查找。（ ）7. 7. 非空的雙向循環(huán)鏈表中任何結點的前驅指針均不為空。（ ）2． 2．struct node *lchild。t,int k){if (t==0 ) {____________________________。else__________________________。 _________________。5． 5． 設有向圖中不存在有向邊Vi,Vj，則其對應的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。9． 9．四、算法設計題(20分)1. 1.2. 2.三、填空題1. 1. headrlink，pllink5. 5. (13，27，38，50，76，49，65，97)9. 9.四、算法設計題1. 1. 設計一個在鏈式存儲結構上統(tǒng)計二叉樹中結點個數(shù)的算法。 countnode(btrchild,count)。}gadjmatrix。}glinklistnode。void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){int i,j。i++) g2[i].firstarc=0。j=n1。 g[i].firstarc=p。 g[j].firstarc=p。 (A) ni (B) n+l i (C) n1i (D) i3．設F是由TT2和T3三棵樹組成的森林，與F對應的二叉樹為B，TT2和T3的結點數(shù)分別為NN2和N3，則二叉樹B的根結點的左子樹的結點數(shù)為（ ）。 (A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序7．設輸入序列…、n經過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（ ）。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) (n1)/2，則順序查找的平均比較次數(shù)為（ ）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為（ ）。 設某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環(huán)隊列中最多存儲_______隊列元素。5． 5． 設一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。9． 9．（ ） 設計計算二叉樹中所有結點值之和的算法。 設計將所有奇數(shù)移到所有偶數(shù)之前的算法。 設計判斷單鏈表中元素是否是遞增的算法。二、填空題1. 1. pnext，sdata2. 2. 503. 3. m14. 4. 6，85. 5. 快速，堆6. 6. 19/77. 7. CBDA8. 8. 69. 9. (24，65，33，80，70，56，48)10. 10. 8void sum(bitree *bt,int amp。} }2． 2． while(ij){ while (ij amp。i=i+1。 if (ij) {r[j]=r[i]。 p!=0。一、選擇題(24分)1．下列程序段的時間復雜度為（ ）。(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，35．設有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（ ）。 (A) 129 (B) 219 (C) 189 (D) 2299. 設有n個關鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關鍵字映射到HASH表中需要做（ ）次線性探測。(A) F，H，C，D，P，A，M，Q，R，S，Y，X(B) P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y(C) A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X(D) H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y3. 3. 設二叉排序樹的高度為h，則在該樹中查找關鍵字key最多需要比較_________次。8. 8. 設無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結構進行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復雜度為_________；用鄰接表作為圖的存儲結構進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復雜度為_________。12. 12. 設有向圖G中的有向邊的集合E={1，2，2，3，1，4，4，5，5，3，4，6，6，5}，則該圖的一個拓撲序列為_________________________。________________。ch)。else{ bt=(bitree*)malloc(sizeof(bitree))。}}14. 14. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內容。 void lklistcreate(_____________ *amp。scanf(“%d”,amp。else {qnext=p。數(shù)據(jù)結構試卷（14）參考答案void mergelklist(lklist *ha,lklist *hb,lklist *amp。 hb!=0) if(hadatahbdata){if(s==0) hc=s=ha。ha=hanext。}。}2. 2. 設計在二叉排序樹上查找結點X的算法。 else p=prchild。 while (i=1) if (temp=r[i1])break。} r[j1]=temp。 A．健壯性和可讀性 B．并行性 C．正確性 D．時空復雜度2. 2. 在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，則執(zhí)行( )。 HL=p。 pnext=HL。A．值 B．函數(shù) C．指針 D．引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同的（ ）。二、 二、若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W[6，3]的起始地址為＿________＿。 廣義表A= (a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。 二叉樹是指度為2的____________________樹。11. 11.12. 12. 給出三元組線性表的順序存儲表示。 設有一個輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，試寫出：(1) 從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點②出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4. 4.E={2,1,3,2,3,6,4,3,4,5,4,6,5,1,5,7,6,1,6,2,6,5}。 if (ix) return 1。 couti39。 while(!QueueEmpty(Q)) { int k=QDelete(Q)。 39。 } }}Int Binsch(ElemType A[ ],int n,KeyType K){int low=0。 //在左子表上繼續(xù)查找 else __________________________________。 閱讀算法（每題7分，共14分）1. 1. (1) 判斷n是否是素數(shù)（或質數(shù)） （2）O（）2. 2. 功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 HL){if (HL==NULL){ cerr空表endl。ElemType temp=pdata。 2. 2. 用鏈接方式存儲的隊列，在進行插入運算時( ). A. 僅修改頭指針 　 B. 頭、尾指針都要修改 C. 僅修改尾指針 、尾指針可能都要修改3. 3. 以下數(shù)據(jù)結構中哪一個是非線性結構？( ) A. 隊列 　　 B. 棧 C. 線性表 　　 D. 二叉樹4. 4. 設有一個二維數(shù)組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。二、 二、6. 6.7. 7.8. 8.9. 9.10. 10.11. 11.12. 12.60507890344. 4.amp。 coutBTdata39。//查找成功 return ___________。六、 六、 增加111. 11. 算法填空（每空2分，共8 分）true BSTleft BSTright 六、 六、 p=pnext。 單選題（每小題2分，共8分） 在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 ( )。 B p→link=s。 D q →link=s。A 棧頂 B 棧底 C 任意位置 D 指定位置 填空題（每空1分，共32分） 數(shù)據(jù)的邏輯結構被分為__________、 ___________ 、________和________四種。 60 56 42 38 在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為________________和____________________。 在圖的鄰接表中，每個結點被稱為____________，通常它包含三個域：一是_____________；二是___________；三是_____________。 一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設散列表為HT[0..12]，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。 include include conss