【正文】 （一）一、 單選題（每題 2 分，共20分）1. 1. 對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（B ）方面的內(nèi)容。 A．健壯性和可讀性 B．并行性 C．正確性 D．時(shí)空復(fù)雜度2. 2. 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( A )。 A. pnext=HLnext。 HLnext=p。 B. pnext=HL。 HL=p。 C. pnext=HL。 p=HL。 D. HL=p。 pnext=HL。3. 3. 對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( B ) 4. 4. 一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. AOV網(wǎng)是一種（ D ）。 A．有向圖 B．無(wú)向圖 C．無(wú)向無(wú)環(huán)圖 D．有向無(wú)環(huán)圖6. 6. 采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（ S ）。A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. 若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（ D ）參數(shù)。A．值 B．函數(shù) C．指針 D．引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ A）。A．行號(hào) B．列號(hào) C．元素值 D．非零元素個(gè)數(shù)9. 9. 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ D ）。A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)二、 二、 運(yùn)算題（每題 6 分，共24分）1. 1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱(chēng)這種結(jié)構(gòu)為_(kāi)____________________。2. 2. 隊(duì)列的插入操作是在隊(duì)列的___尾______進(jìn)行，刪除操作是在隊(duì)列的____首______進(jìn)行。3. 3. 當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？眨瑒t表示棧滿(mǎn)的條件是___top==0___(要超出才為滿(mǎn))_______________。4. 4. 對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_(kāi)________，在表尾插入元素的時(shí)間復(fù)雜度為_(kāi)___________。5. 5. 設(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é)。W中第6 行的元素和第4 列的元素共占用＿_(dá)______＿個(gè)字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W[6，3]的起始地址為＿_(dá)_______＿。6. 6. 廣義表A= (a,(a,b),((a,b),c)),則它的深度為_(kāi)___________，它的長(zhǎng)度為_(kāi)___________。7. 7. 二叉樹(shù)是指度為2的____________________樹(shù)。一棵結(jié)點(diǎn)數(shù)為N的二叉樹(shù)，其所有結(jié)點(diǎn)的度的總和是_____________。8. 8. 對(duì)一棵二叉搜索樹(shù)進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)______________。對(duì)一棵由算術(shù)表達(dá)式組成的二叉語(yǔ)法樹(shù)進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的__________________。9. 9. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為_(kāi)____________個(gè)，其中_______________個(gè)用于指向孩子，_________________個(gè)指針是空閑的。10. 10. 若對(duì)一棵完全二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A[0]中。其余類(lèi)推，則A[ i ]元素的左孩子元素為_(kāi)_______,右孩子元素為_(kāi)______________，雙親元素為_(kāi)___________。11. 11. 在線性表的散列存儲(chǔ)中，處理沖突的常用方法有________________________和_____________________________兩種。12. 12. 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用________________________排序。一、 填空題（每空1分，共26分）1. 1. 聯(lián)系 圖（或圖結(jié)構(gòu)）2. 2. 尾 首3. 3. top==04. 4. O（1） O（n）5. 5. 128 44 1086. 6. 3 3 7. 7. 655151321452515637 圖7有序 n18. 8. 有序序列 后綴表達(dá)式（或逆波蘭式）9. 9. 2n n1 n+110. 10. 2i+1 2i+2 (i1)/211. 11. 開(kāi)放定址法 鏈接法12. 12. 快速 歸并三、 三、 運(yùn)算題（每題6分，共24分）1. 1. 已知一個(gè)6180。5稀疏矩陣如下所示，試：（1） （1） 寫(xiě)出它的三元組線性表；（2） （2） 給出三元組線性表的順序存儲(chǔ)表示。2. 2. 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。3. 3. 對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫(xiě)出：(1) 從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù)；(2) 從頂點(diǎn)②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù)； 4. 4. 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為： 圖6 V={1,2,3,4,5,6,7}。E={2,1,3,2,3,6,4,3,4,5,4,6,5,1,5,7,6,1,6,2,6,5}。若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列.二、 三、 運(yùn)算題（每題6分，共24分）1. 1. （1） ((1,5,1),(3,2,1),(4,5,2),(5,1,5),(6,3,7)) (3分)（2） 三元組線性表的順序存儲(chǔ)表示如圖7示。2. 2. 圖8如圖8所示。3. 3. DFS：????… BFS：???…? 4. 拓樸排序?yàn)椋?4 3 6 5 7 2 1 四、 四、 閱讀算法（每題7分，共14分）1. 1. int Prime(int n){ int i=1。 int x=(int) sqrt(n)。 while (++i=x) if (n%i==0) break。 if (ix) return 1。 else return 0。 } (1) (1) 指出該算法的功能；(2) (2) 該算法的時(shí)間復(fù)雜度是多少？2. 2. 寫(xiě)出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q。 InitQueue(Q)。 couti39。 39。 visited[i]=true。 QInsert(Q,i)。 while(!QueueEmpty(Q)) { int k=QDelete(Q)。 edgenode* p=GL[k]。 while(p!=NULL) { int j=padjvex。 if(!visited[j]) { coutj39。 39。 visited[j]=true。 QInsert(Q,j)。 } p=pnext。 } }}五、 五、 算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫(xiě)完整。Int Binsch(ElemType A[ ],int n,KeyType K){int low=0。int high=n1。while (low=high){int mid=_______________________________；if (K==A[mid].key) return mid。 //查找成功，返回元素的下標(biāo) else if (K[mid].key) ______________________________________。 //在左子表上繼續(xù)查找 else __________________________________。 //在右子表上繼續(xù)查找}return 1。 //查找失敗，返回1}六、 六、 編寫(xiě)算法（共8分）HL是單鏈表的頭指針，試寫(xiě)出刪除頭結(jié)點(diǎn)的算法。ElemType DeleFront(LNode * amp。 HL)參考答案四、 閱讀算法（每題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 六、 編寫(xiě)算法（8分）ElemType DeleFront(LNode * amp。 HL){if (HL==NULL){ cerr空表endl。exit(1)。