非選擇題部分

　　注意事項(xiàng)：

　　用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。

　　二、填空題(本大題共13小題，每小題2分，共26分)

　　16.數(shù)據(jù)的基本單位是_________。

　　17.雙向循環(huán)鏈表中，在p所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t，需要修改四個(gè)指針，分別為

　　t->prior=P;t->next=p->next;_________;p->next=t;。

　　18.在帶有頭結(jié)點(diǎn)的循環(huán)鏈表中，尾指針為rear，判斷指針P所指結(jié)點(diǎn)為首結(jié)點(diǎn)的條件是_________。

　　19.若線性表中最常用的操作是求表長(zhǎng)和讀表元素，則順序表和鏈表這兩種存儲(chǔ)方式中，較節(jié)省時(shí)間的是_________。

　　20.不含任何數(shù)據(jù)元素的棧稱為_________。

　　21.稀疏矩陣一般采用的壓縮存儲(chǔ)方法是_________。

　　22.100個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)時(shí)，用來指向左、右孩子結(jié)點(diǎn)的指針域有_________個(gè)。

　　23.已知完全二叉樹的第5層有5個(gè)結(jié)點(diǎn)，則整個(gè)完全二叉樹有_________個(gè)結(jié)點(diǎn)。

　　24.n個(gè)頂點(diǎn)的有向圖G用鄰接矩陣A[1..n，1..n]存儲(chǔ)，其第i列的所有元素之和等于頂點(diǎn)

　　Vi的_________。

　　25.具有10個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為_________。

　　26.要完全避免散列所產(chǎn)生的“堆積’’現(xiàn)象，通常采用_________解決沖突。

　　27.在長(zhǎng)度為n的帶有崗哨的順序表中進(jìn)行順序查找，查找不成功時(shí)，與關(guān)鍵字的比較次數(shù)為_________。

　　28.歸并排序算法的時(shí)間復(fù)雜度是_________。

　　三、應(yīng)用題(本大題共5小題，每小題6分，共30分)

　　29.稀疏矩陣A如題29圖所示，寫出該稀疏矩陣A的三元組表示法。

　　30.設(shè)二叉樹的中序遍歷序列為BDCEAFHG，后序遍歷序列為DECBHGFA，試畫出該二叉樹。

　　31.寫出題31圖所示無向圖的鄰接矩陣，并寫出每個(gè)頂點(diǎn)的度。

　　題31圖

　　32.已知散列表的地址空間為0至13，散列函數(shù)H(k)=kmod11，(mod為求余運(yùn)算)，待散列序列為(26，61，38，84，49)，用二次探測(cè)法解決沖突，構(gòu)造該序列的散列表，要求寫出處理沖突的過程。

　　33.將一組鍵值(80，50，65，13，86，35，96，57，39，79，59，15)應(yīng)用二路歸并排序算法從小到大排序，試寫出各趟的結(jié)果。

　　四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)

　　34.設(shè)單鏈表及鏈棧S的結(jié)構(gòu)定義如下：

　　typedef struct node

　　{ Data Type data;

　　struct node*next;

　�。齦inkstack;

　　編寫一個(gè)算法void ReverseList(1inkstack *head)，借助于棧S將帶頭結(jié)點(diǎn)單鏈表head中序號(hào)為奇數(shù)的結(jié)點(diǎn)逆置，序號(hào)為偶數(shù)的結(jié)點(diǎn)保持不變。(例如：?jiǎn)捂湵淼倪壿嫿Y(jié)構(gòu)為(a1，a2，a3，a4，a5，a6)，逆置后變?yōu)?a5，a2，a3，a4，a1，a6))。

　　說明：棧的初始化運(yùn)算用InitStack(S);進(jìn)棧運(yùn)算用Push(S，x);判�？者\(yùn)算用EmptyStack(S);出棧運(yùn)算用Pop(S);取棧頂元素運(yùn)算用Gettop(S)。

　　35.以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試編寫遞歸算法實(shí)現(xiàn)求二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)。