2、為主序，下三角表格的元素(i,j)對應到順序數(shù)組的元素下標為i*(i+l)+j—;若以列序為主序，則下三角表格的元素(i,j)對應到順序數(shù)組的元素下標o5、設圖G有n個頂點和e條邊，當用鄰接矩陣作圖的存儲結(jié)構(gòu)時，進行深度優(yōu)先搜索遍歷的時間復雜度為，6、哈希表的裝填因子定義為—哈希表的長度；直觀地看，裝填因子越—小發(fā)生沖突的可能性就越小。7、拓撲排序的方法為在有向圖中選一個同有前驅(qū)的頂點且輸岀之，從圖中刪除該頂點和所有以它為尾的弧，重復這兩個步驟，直到金部頂點均己輸岀。o8、設F是森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)
3、點，B中右指針域為空的結(jié)點有n+1個。9、已知一個有序表為(5,13,19,21,37,56,64,75,80,88,92),當折半查找值為21的元素時，若采用binary_search_l方法，需4次比較可查找成功。10、在Dijkstra算法中，S為已經(jīng)求得最短路徑的終點集合的集合，算法的時間復雜度為O(n2)—。11、快速排序的最壞情況是初始序列為已排好序或倒序,其時間復雜度為—O(n2)o二、應用題1、將隊列存儲在下標范圍0到(maxqueue.1)的數(shù)組中，隊列滿時數(shù)組留有一個空位，試寫出Queue類的定義，并給出隊空
4、和隊滿的條件(8分)Queue類的定義如下：constintmaxqueue=10;classQueue{public:Queue();boolempty()const;Error_codeserve();Error_codeappend(constQueue_entry&item);Error_coderetrieve(Queue_entry&item)const;protected:intcount;intfront,rear;Queue_entryentry[maxqueue];}；(5券)隊空條件為(rear+l)%ma
5、xqueue=front(1.5分)隊滿條件為(rear+2)%maxqueue=front(1.5分)2、設有關鍵字輸入序列：{haerbin,shanghai,cengdu,kunming,guangzhou,wuhan,changchun,beijing,jinan,fuzhou,changsha,xian,nanjing,tianjin},畫出生成的二叉排序樹，求出在等查找概率情況下查找成功時的平均查找長度，并畫出刪除haerbin之后所得的二叉排序樹。（12分）3、Prim算法求下圖的最小生成樹，請寫出求解過程。（8分
6、）4、將序列（100,85,40,75,80,60,65,95,82,10,20）分別調(diào)整為小頂堆（堆頂元素取最小值）和大頂堆（堆頂元素取最大值）。請給岀在初始大頂堆中將關鍵字最大的記錄與序列中最后一個記錄交換后，再進行調(diào)整建成的新大頂堆。分析堆排序方法最壞情況下的吋間性能和輔助存儲量。（10分）三、算法設計題1、編寫算法，在一個帶頭結(jié)點的非遞減有序單鏈表中插入一個元素，使其仍然是一個有序單鏈表。(10分)typedefstructLnode{ElemTypedata；StructLnode*next;}Lnode,*LinkL
7、ist;Error_codeListInsert(LinkList&L,ElemTypex);voidinsert(LinkListL,ElemTypex){q=L;p=L->next;while((p!=NULL)&&(p->datanext;q=q->next;}(5分)s=(ListList)malloc(sizeof(LNode));s->data=x;q->next=s;s->next=p;}2、編寫算法，將Stringoriginal中最多n個字符復制到Stringcopy中。(10分)voids
8、trncpy(String©,constString&original,intn);voidstrncpy(String©,constString&original,intn){constchar*temp二original.c_str();(1
