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