【正文】 (k1，k2，…，kn1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn1，x)調(diào)整為堆。 while (i=1) if (temp=r[i1])break。 j=i。} r[j1]=temp。 A．健壯性和可讀性 B．并行性 C．正確性 D．時(shí)空復(fù)雜度2. 2. 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 HLnext=p。 HL=p。 p=HL。 pnext=HL。 A．有向圖 B．無向圖 C．無向無環(huán)圖 D．有向無環(huán)圖6. 6. 采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（ ）。A．值 B．函數(shù) C．指針 D．引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( )。二、 二、 運(yùn)算題（每題 6 分，共24分）1. 1.當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_____________________。 隊(duì)列的插入操作是在隊(duì)列的___尾______進(jìn)行，刪除操作是在隊(duì)列的____首______進(jìn)行。 當(dāng)用長度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？眨瑒t表示棧滿的條件是___top==0___(要超出才為滿)_______________。 對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_________，在表尾插入元素的時(shí)間復(fù)雜度為____________。 設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié)，行下標(biāo)i從0到7 ，列下標(biāo)j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用＿_(dá)____＿個(gè)字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W[6，3]的起始地址為＿_(dá)_______＿。 廣義表A= (a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。 二叉樹是指度為2的____________________樹。8. 8.對(duì)一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的__________________。 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為_____________個(gè)，其中_______________個(gè)用于指向孩子，_________________個(gè)指針是空閑的。 若對(duì)一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A[0]中。11. 11.12. 12. 已知一個(gè)6180。試：（1） （1） 給出三元組線性表的順序存儲(chǔ)表示。 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。 對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫出：(1) 從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點(diǎn)②出發(fā)進(jìn)行廣度優(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}。 int x=(int) sqrt(n)。 if (ix) return 1。 } (1) (1) 指出該算法的功能；(2) (2) 該算法的時(shí)間復(fù)雜度是多少？2. 2. 寫出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q。 couti39。 visited[i]=true。 while(!QueueEmpty(Q)) { int k=QDelete(Q)。 while(p!=NULL) { int j=padjvex。 39。 QInsert(Q,j)。 } }}Int Binsch(ElemType A[ ],int n,KeyType K){int low=0。while (low=high){int mid=_______________________________；if (K==A[mid].key) return mid。 //在左子表上繼續(xù)查找 else __________________________________。 //查找失敗，返回1}ElemType DeleFront(LNode * amp。2. 2. 圖8如圖8所示。 閱讀算法（每題7分，共14分）1. 1. (1) 判斷n是否是素?cái)?shù)（或質(zhì)數(shù)） （2）O（）2. 2. 功能為：從初始點(diǎn)vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 算法填空（8 分） (low+high)/2 high=mid1 low=mid+1 六、 六、 HL){if (HL==NULL){ cerr空表endl。}LNode* p=HL。ElemType temp=pdata。return temp。 2. 2. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( ). A. 僅修改頭指針 　 B. 頭、尾指針都要修改 C. 僅修改尾指針 、尾指針可能都要修改3. 3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？( ) A. 隊(duì)列 　　 B. 棧 C. 線性表 　　 D. 二叉樹4. 4. 設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。 6. 6. 二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為( ). A．2k1 +1 　　　D. 2k17. 7. 若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，38. 8. 對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為 A. O（1） 　　B. O（n）　　 C. O（1og2n） D. O（n2）9. 9. 對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)， A．1 B．2 C．3 D．410. 10. 設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有( )條邊才能確保是一個(gè)連通圖。二、 二、 填空題（每空1分，共26分）1. 1.2. 2.3. 3.4. 4.中綴算式（3+4X）2Y/3對(duì)應(yīng)的后綴算式為_______________________________。 若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。6. 6.7. 7.8. 8.9. 9.10. 10.11. 11.12. 12. 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A [0].next，試寫出該線性表。605078903412. 2.3. 3. E={(1,2)3,(1,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.amp。2. 2. void ABC(BTNode * BT){ if BT { ABC (BTleft)。 coutBTdata39。 } } 該算法的功能是： item){ if (BST==NULL) return false。//查找成功 return ___________。 else return Find(_______________,item)。六、 六、 編寫算法（共8分）統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。 單選題（每題2分，共20分） 二、 二、 增加111. 11. 歸并三、 三、 閱讀算法（每題7分，共14分）1. 1. （1）查詢鏈表的尾結(jié)點(diǎn)（2）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）返回的線性表為（a2,a3,…,an,a1） 2. 2. 遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。 算法填空（每空2分，共8 分）true BSTleft BSTright 六、 六、 LNode* p=HL。 p=pnext。 }//CountX 單選題（每小題2分，共8分） 在一個(gè)長度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 ( )。 A s→link=p→link。 B p→link=s。 C p→link=s→link。 D q →link=s。 A 棧頂 B 棧底 C 任意位置 D 指定位置 填空題（每空1分，共32分） 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為__________、 ___________ 、________和________四種。 在下面的數(shù)組a中鏈接存儲(chǔ)著一個(gè)線性表，表頭指針為a[o].next，則該線性表為_________________________________________________。 60 56 42 38 4 3 7 6 2 0 1 在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為________________和____________________。 當(dāng)堆棧采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用———————表示；當(dāng)堆棧采用鏈接存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用_______________表示。 在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為____________，通常它包含三個(gè)域：一是_____________；二是___________；三是_____________。 1 11 1 運(yùn)算題（每小題6分，共24分） 已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對(duì)其進(jìn)行快速排序的每一次劃分結(jié)果。 一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。 已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序鏈接的。 閱讀算法，回答問題（每小題8分，共16分） include include conss