(0012)《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)思考題答案

1、（0012）數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)思考題答案1：論述題 1、算法的時(shí)間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎?2、下列程序段帶標(biāo)號語句的頻度和時(shí)間復(fù)雜度。( 1 ) I=0;    while (I<N)&&(AI!=K)      I+; /語句3    return(I);( 2 ) n為不小于1的整數(shù)（設(shè)k的初值等于1）void pp ( int k)       if (k=n) /語句1

2、    for (I=0; I語句2        printf(aI); /語句3    else      for (I=k-1;I語句4        aI=aI+I; /語句5        pp(k+1); /語句6 &

3、#160;      /pp3、常用的存儲(chǔ)表示方法有哪幾種?  參考答案： 1、不,事實(shí)上，算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的元素取值等相關(guān)，但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時(shí)間復(fù)雜度時(shí)，一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。2、（1）這個(gè)算法完成在一維數(shù)組an中查找給定值k的功能。語句三的頻度不僅與問題的規(guī)模n有關(guān)，還與輸入實(shí)例中a的各元素取值以及k的取值相關(guān)，即與輸入實(shí)例的初始狀態(tài)復(fù)雜有關(guān)。若a中沒有與k相等的元素，則語句三的頻度為n；若a中的第一個(gè)元

4、素a0等于k，則語句三的頻度是常數(shù)0。在這種情況下，可用最壞情況下的時(shí)間復(fù)雜度作為時(shí)間復(fù)雜度。在此例中即為O(n)。這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是在任何輸入實(shí)例上運(yùn)行時(shí)間的上界。有時(shí),也可能選擇將算法的平均(或期望)時(shí)間復(fù)雜度作為討論目標(biāo)。所謂的平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例以等概率出現(xiàn)的情況下算法的期望運(yùn)行時(shí)間與問題規(guī)模的數(shù)量級的關(guān)系。此例中，以k出現(xiàn)在任何位置的概率相同，都為1/n，則語句三的執(zhí)行頻度為0+1+2+(n-1)/n=(n-1)/2。它決定了此程序段的平均時(shí)間復(fù)雜度的數(shù)量級為f(n)=n,記作O(n)。 （2）在計(jì)算包含調(diào)用語句的算法的語句頻度時(shí)，需考慮到調(diào)用發(fā)

5、生時(shí)在被調(diào)用算法中各語句的執(zhí)行情況。本題所示的遞歸調(diào)用較之非遞歸調(diào)用的分析更為復(fù)雜。由于k等于n是算法的出口條件,不妨首先分析算法pp(n)的簡單情況,這時(shí)各語句的執(zhí)行頻度分別為:1,n+1,n,0,0,0; 而當(dāng)k=n-1,n-2,1時(shí),語句的執(zhí)行情況和調(diào)度情況,如下表所示。 K 值不考慮調(diào)用時(shí)各語句的執(zhí)行頻度調(diào)用情況語句1語句2語句3語句4語句5語句6n1n+1n000/n-1100321pp(n)n-2100431pp(n-1)1100n+1n1pp(2)對于k=1即pp(1)而言，各語句的執(zhí)行次數(shù)還須將調(diào)用pp(2)時(shí)的執(zhí)行次數(shù)累計(jì)到內(nèi)，pp(2)各語句的執(zhí)行次數(shù)又須將調(diào)用pp(3)時(shí)

6、執(zhí)行次數(shù)累計(jì)到內(nèi)，由此可的語句頻度如下：語句：1+1+1=n語句：0+0+0+(n+1)=n+1語句：0+0+0+n=n語句：(n+1)+n+3=(n-1)(n+4)/2語句：n+(n-1)+2=(n-1)(n+2)/2語句：1+1+.+1+0=n-1算法的時(shí)間復(fù)雜度可以基于頻度最大的語句，應(yīng)為O(n2)。4、常用的存儲(chǔ)表示方法有四種：順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。鏈接存儲(chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)

7、表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。 1：論述題 1、何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?2、為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?3、確定下列算法中輸出語句的執(zhí)行次數(shù)，并給出算法的時(shí)間復(fù)雜度。（1） void combi (int n)  int I,j,k;    for ( I=1; I<=n; I+)     

8、60;for ( j=I+1; j<=n; j+)        for ( k=j+1; k<=n; k+)          cout<<I,J,K;< st1:citation>(2) void binary ( int n)  while(n)    cout<<N;   

9、 n=n/2;          4、常用的存儲(chǔ)表示方法有哪幾種? 5.分析以下程序段的時(shí)間復(fù)雜度。 a=0；b=1；for（i=2；i=n；i+）s=a+b；b=a；a=S；6.對于一個(gè)棧，給出輸入項(xiàng)A，B，C。如果輸入項(xiàng)序列由A，B，C組成，試給出全部可能的輸出序列 7、已知一個(gè)順序表中的元素按元素值非遞減有序排列，編寫一個(gè)函數(shù)刪除表中多余的值相同的元素。  參考答案： 1、答：在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲(chǔ)

10、結(jié)構(gòu)，通常有以下幾方面的考慮：1.基于空間的考慮。當(dāng)要求存儲(chǔ)的線性表長度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之， 若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。2、答：尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，

11、其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next 和 rear, 查找時(shí)間都是O(1)。 若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。3、(1)I取值范圍從1n，j取值范圍從I+1n，k取值范圍從j+1n，情況如下表所示： I值j值k值輸出語句的執(zhí)行次數(shù)123, 4, ,nn-2n-1n1n/234,5,nn-3n-1n1n/n-2n-1n1n/n-1n/n/所以，輸出語句共執(zhí)行次數(shù)為(n-2)+(n-3)+1)+(n-3)+(n-4)+1)+1= (n-1)(n-2)/2+(n-2)(n-3)/2+1= (n-1)2+(n-2)2+

12、(n-3)2+12)-(n-1)+(n-2)+(n-3)+.+1)/2=(n-1)n(2n-1)/6-n(n-1)/2)/2=(n(n-1)(2n-4)/12=n(n-1)(n-2)/6(2) ceil(log2n); 4、常用的存儲(chǔ)表示方法有四種：順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。鏈接存儲(chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的

13、地址。散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。1：論述題 1、已知L1和L2分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，且已知其長度分別為m和n。試寫一算法將這兩個(gè)鏈表連接在一起，請分析你的算法的時(shí)間復(fù)雜度。 2、假設(shè)某個(gè)單向循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表中某個(gè)結(jié)點(diǎn)指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。 3、指出以下算法中的錯(cuò)誤和低效之處，并把它改寫為一個(gè)既正確又高效的算法。Status DeleteK( SqList &a,int I, int k) /本過程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第I個(gè)元素起的k個(gè)

14、元素。if (I<1| k<0| I+k > a.length) return ERROR;else for (count=1;count刪除一個(gè)元素for (j=a.Length; j >=I+1;j-) a.elemj-1 = a.elemj;a.length-;rreturn OK;/DeleteK4、假設(shè)稀疏矩陣A采用三元組表示，編寫一個(gè)函數(shù)計(jì)算其轉(zhuǎn)置矩陣B，要求B也采用三元組表示5、設(shè)二維數(shù)組A5*6的每個(gè)元素占4個(gè)字節(jié)，已知Loc（a00）=1000，A共占多少個(gè)字節(jié)？A的終端結(jié)點(diǎn)a45的起始地址為多少？按行和按列優(yōu)先存儲(chǔ)時(shí)，a25的起始地址分別為多少？6、

15、編寫下列算法（假定下面所用的串均采用順序存儲(chǔ)方式，參數(shù)ch、ch1和ch2均為字符型）： · 將串r中所有其值為ch1的字符換成ch2的字符。 · 將串r中所有字符按照相反的次序仍存放在r中。 · 從串r中刪除其值等于ch的所有字符。 · 從串r1中第index個(gè)字符起求出首次與字符r2相同的子串的起始位置。 · 從串r中刪除所有與串r3相同的子串（允許調(diào)用第（4）小題的函數(shù)和第（3）小題的刪除子串的函數(shù)）。   參考答案： 1、參考答案LinkList Link( LinkList L1 , LinkList L2 )/將

16、兩個(gè)單鏈表連接在一起ListNode *p , *q ;p=L1;q=L2;while ( p->next ) p=p->next; /查找終端結(jié)點(diǎn)p->next = q->next ; /將L2的開始結(jié)點(diǎn)鏈接在L1之后return L1 ; 本算法的主要操作時(shí)間花費(fèi)在查找L1的終端結(jié)點(diǎn)上，與L2的長度無關(guān)，所以本算的法時(shí)間復(fù)雜度為： m+1=O(m)2、參考答案void Delprior ( Link s)p = q = s; while (p->next!=s) q = p;p = p->next;q->next = s;delete ( p);3

17、、參考答案更正：for (j = I+k; j <=a.Length; j+) a.elemj-k = a.elemj; a.Length = a.Length ? k;1：論述題 1、假設(shè)在二叉鏈表中增加兩個(gè)域：雙親域（parent)以指示其雙親結(jié)點(diǎn)；標(biāo)志域（mark取值0.2）以區(qū)分在遍歷過程中到達(dá)該結(jié)點(diǎn)時(shí)應(yīng)繼續(xù)向左或向右或訪問該結(jié)點(diǎn)。試以此存儲(chǔ)結(jié)構(gòu)編寫不用棧進(jìn)行后序遍歷的遞推形式的算法。2、設(shè)有三對角矩陣 An*n，將其三條對角線上的元素逐行地存儲(chǔ)到向量B03n-3中，使得Bk=aij,求： (1)用I , j 表示k的下標(biāo)變換公式。 (2)用 k 表示 I,j 的下標(biāo)變換公式。3

18、、 寫一算法void StrReplace(char *T, char *P, char *S),將T中首次出現(xiàn)的子串P替換為串S。注意：S和P的長度不一定相等。可以使用已有的串操作。4、 設(shè)兩個(gè)棧共享空間v0.m-1，兩棧的棧底分別設(shè)在向量的兩端，且每個(gè)元素占一個(gè)分量。試設(shè)計(jì)這兩個(gè)棧的插入和刪除算法。5、若以1234作為雙端隊(duì)列的輸入序列，試分別求出滿足以下條件的輸出序列：（1）能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列；（2）能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列；（3）既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端

19、隊(duì)列得到的輸出序列6、已知單鏈表L是一個(gè)遞增有序表，試寫一高效算法，刪除表中值大于min 且小于max的結(jié)點(diǎn)(若表中有這樣的結(jié)點(diǎn))，同時(shí)釋放被刪結(jié)點(diǎn)的空間，這里min 和 max是兩個(gè)給定的參數(shù)。請分析你的算法的時(shí)間復(fù)雜度。7、簡述以下算法的功能。(1) void Demo1(SeqStack *S)int I; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (I=0, I< n; I+) Push(S, arrI); /Demo1(2) SeqStack S1, S2, tmp;DataType x;/假設(shè)棧tmp和S2已做過初

20、始化while ( ! StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( ! StackEmpty (&tmp) ) x=Pop( &tmp);Push( &S1,x);Push( &S2, x);(3) void Demo2( SeqStack *S, int m) / 設(shè)DataType 為int 型SeqStack T; int I;InitStack (&T);while (! StackEmpty( S)if( I=Pop(S) !=m) Push( &T,I);w

21、hile (! StackEmpty( &T) I=Pop(&T); Push(S,I); (4)void Demo3( CirQueue *Q) / 設(shè)DataType 為int 型int x; SeqStack S;InitStack( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x );/ Demo3(5) CirQueue Q1, Q2; / 設(shè)DataType 為int 型int

22、 x, I , m = 0; / 設(shè)Q1已有內(nèi)容， Q2已初始化過while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); m+;for (I=0; I< n; I+) x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2, x);二、填空題1、在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為 。2、將下三角矩陣A18，18的下三角部分逐行地存儲(chǔ)到起始地址為1000的內(nèi)存單元中，已知每個(gè)元素占4個(gè)單元，則A7，5的地址為 。 3、高度

23、為5的三階B-樹至少有 個(gè)結(jié)點(diǎn)。4、具有100個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。 5、在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用_；若初始數(shù)據(jù)基本反序，則選用_。  參考答案： 1、void PostOrder( Bitree root) /設(shè)二叉樹的結(jié)點(diǎn)含有四個(gè)域：/mark , parent , lchild , rchild。p=root;while(p)swith(p->mark)case 0: p->mark=1;if (p->lchild) p->lchild;break;case 1: p->mark=2;if(p->rch

24、ild) p->rchild;break;case 2: p->mark=0;visit(*p);p=p->parent;break;default:;/PostOrder 2、(1) 解： 要求I,j 到k 的下標(biāo)變換公式，就是要知道在k之前已有幾個(gè)非零元素，這些非零元素的個(gè)數(shù)就是k的值，一個(gè)元素所在行為I,所在列為j,則在其前面已有的非零元素個(gè)數(shù)為： (I*3-1)+j-(I+1) 其中 (I*3-1)是這個(gè)元素前面所有行的非零元素個(gè)數(shù)，j-(I+1)是它所在列前面的非零元素個(gè)數(shù)化簡可得： k=2i+j; / c下標(biāo)是從0開始的。 (2) 解： 因?yàn)镵和I,j是一一對應(yīng)的

25、關(guān)系，因此這也不難算出： I=(k+1)/3 /k+1表示當(dāng)前元素前有幾個(gè)非零元素,被3整除就得到行號j=(k+1)%3+(k+1)/3-1 /k+1除以3的余數(shù)就是表示當(dāng)前行中第幾個(gè)非零元素，加上前面的0元素所點(diǎn)列數(shù)就是當(dāng)前列號3、 void StrReplace (char *T, char *P, char *S)/串替換int I , m;m=strlen (P);/取得子串長度I=StrMatch(T,P);/取得串匹配位置StrDelete( T,I,m);/刪除匹配處子串StrInsert( T, S,I);/將S串插入到匹配位置處4、答案：設(shè)用變量I表示棧的編號。類型定義：ty

26、pedef struct ElemType vm; /?？臻g向量int top2; /棧頂指針向量DuStack;棧空條件：s0棧：s->top0 = -1s1棧：s->top1 = m棧滿條件：s->top0+1=s->top1（此時(shí)向量空間全占滿）。（1）插入void push(DuStack * s, ElemType x, int I) /當(dāng)兩個(gè)棧共享空間時(shí)，再由I指定的棧中插入新元素x if (s->top0+1=s->top1) printf("OVERFLOW”); return;switch(I) case 0: s->top

27、0+;s->vs->top0=x;break;case 1: s->top1-;s->vs->top1=x;break; (2) 刪除ElemType pop( DuStack *s, int I) /當(dāng)兩棧共享空間時(shí)，在由I指定的棧中刪除棧頂元素，并返回該元素 switch (I) case 0 : if (s->top0=-1) printf("UNDERFLOW”); return; x=s->vs->top0;s->top0-;break;case 1: if (s->top1=m) printf("UND

28、ERFLOW”); return; x=s->vs->top1;s->top1+;break;return (x); 5、答：（1）4132；（2）4213；（3）4231。6、要解這樣的問題，我們首先想到的是拿鏈表中的元素一個(gè)個(gè)地與max和min比較，然后刪除這個(gè)結(jié)點(diǎn)，其實(shí)因?yàn)橐阎涫怯行蜴湵?，所以我們只要找到大于min的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)，再找到小于max的結(jié)點(diǎn)，然后一并把中間的全部摘掉就可以了。 算法如下：void DeleteList ( LinkList L, DataType min , DataType max )ListNode *p , *q ,*r;p=L

29、->next;while( p && p->data <=min ) /找比min大的前一個(gè)元素位置q=p;p=p->next; while( p && p->data < max ) /找比max小的最后一個(gè)元素位置r=p;p=p->next;free?;/釋放這個(gè)結(jié)點(diǎn)空間 q->next=p; /把斷點(diǎn)鏈上 7、答案：(1)程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個(gè)數(shù)限制在64個(gè)以內(nèi)。(2)程序段的功能是利用tmp棧將一個(gè)非空棧的所有元素按原樣復(fù)

30、制到一個(gè)空棧當(dāng)中去。(3)程序段的功能是將一個(gè)非空棧中值等于m的元素全部刪去。(4)程序段的功能是將一個(gè)循環(huán)隊(duì)列反向排列，原來的隊(duì)頭變成隊(duì)尾，原來的隊(duì)尾變成隊(duì)頭。(5)這段程序的功能是將隊(duì)列1的所有元素復(fù)制到隊(duì)列2中去，但其執(zhí)行過程是先把隊(duì)列1的元素全部出隊(duì)，進(jìn)入隊(duì)列2，然后再把隊(duì)列2的元素復(fù)制到隊(duì)列1中。二、填空題a)         2n-1b)        1208c)      

31、;  31d)        7e)         插入排序選擇排序1：單選題下列排序算法中，( )算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。  A：堆排序B：冒泡排序C：快速排序D：SHELL排序參考答案：C2：論述題 1、采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)判別無向圖中任意給定的兩個(gè)頂點(diǎn)之間是否存在一條長度為k的簡單路徑的算法。2、編寫算法完成下列操作：無重復(fù)地輸出以孩子兄弟鏈表存儲(chǔ)的樹T中所有的邊。

32、輸出形式為（k1,k2)(ki,kj),其中ki,kj樹結(jié)點(diǎn)中結(jié)點(diǎn)的標(biāo)識。(提示：修改二叉樹遍歷的遞歸算法，使其參數(shù)表增加參數(shù)father,指向被訪問的當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)。)3、一個(gè)深度為h的滿k叉樹有如下性質(zhì)：第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹。如果按層次順序(同層自左至右)從1開始對全部結(jié)點(diǎn)編號，問： (1)各層的結(jié)點(diǎn)數(shù)目是多少? (2)編號為I的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號是多少? (3)編號為I的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)(若存在)的編號是多少? (4)編號為I的結(jié)點(diǎn)的有右兄弟的條件是什么? 其右兄弟的編號是多少?4、設(shè)哈希函數(shù)為 H（K）= K mod 7，哈

33、希表的地址空間為 0， 6，開始時(shí)哈希表為空，用線性探測法解決沖突，請畫出依次插入鍵值23，14，9，6，30，12，18后的哈希表。二、填空題1、  二叉排序樹上，結(jié)點(diǎn)的平衡因子定義為該結(jié)點(diǎn)_子樹的高度減去該結(jié)點(diǎn)_子樹的高度。2、請列舉四種處理哈希沖突的方法： 、 、 、 。3、一個(gè)無向圖完全圖中，共有 條邊。4、對如何一顆二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則它們之間的關(guān)系應(yīng)為： 。5、下列排序算法中，穩(wěn)定的排序算法是 （選擇排序，堆排序，快速排序，直接插入排序）  參考答案： 1、Boolean visitedMAX;Boolean fin

34、dpath (ALGraph G, int k,int a, int b)for ( I=0; IvisitedI=FALSE;return DFSsearch ( G, k, a, b)Boolean DFSsearch ( ALGraph G, int k, int a, int b)visiteda=TRUE;for (w=FirstAdjVex(G,a); w; w=NextAdjVex(G,a,w) if (!visitedw)if (k=1)&&(w=b) return 1;else if (k=1) continue;else if (w=b) continue;

35、else if ( DFSsearch ( G,k-1,w,b) return 1;visiteda=FALSE; return 0; 2、status outTedge（CSNode* root, CSNode* father ) if ( root) printf(',father->mark, ,',root->mark, )' );if ( outTedge ( root->lchild , root)if( outTedge ( root->rchild , father)return OK;return ERROR;else retu

36、rn OK;3、 答：(1) 設(shè)層號為l的結(jié)點(diǎn)數(shù)目為m=k(l-1) (2) 編號為I的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號是：|_(I+k-2)/k_|(不大于(I+k-2)/k的最大整數(shù)。也就是(I+k-2)與k整除的結(jié)果.以下/表示整除。 (3) 編號為I的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)編號是：k*(I-1)+1+j; (4) 編號為I的結(jié)點(diǎn)有右兄弟的條件是(I+1)/k=(I+2)/k (整除) 并且I!=1 右兄弟的編號是I+1.4、0123456141823930126二、填空題1         左右2  

37、    開放定址法再哈希法鏈地址法建立一個(gè)公共溢出區(qū)3      1/（2*n*(n-1)）4        n0=n2+15、選擇排序 直接插入排序1：論述題 1、以單鏈表作為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)直接插入排序算法。2、以關(guān)鍵字序列(265，301，751，129，937，863，742，694，076，438)為例，分別寫出執(zhí)行以下排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。 (1) 直接插入排序 (2)希爾排序 (3)冒泡排序 (4)快速排序 (5)

38、 直接選擇排序 (6) 堆排序 (7) 歸并排序 (8)基數(shù)排序 上述方法中，哪些是穩(wěn)定的排序?哪些是非穩(wěn)定的排序?對不穩(wěn)定的排序試舉出一個(gè)不穩(wěn)定的實(shí)例。3、畫出對長度為18的有序的順序表進(jìn)行二分查找的判定樹，并指出在等概率時(shí)查找成功的平均查找長度，以及查找失敗時(shí)所需的最多的關(guān)鍵字比較次數(shù)4、某校學(xué)生學(xué)號由8位十進(jìn)制數(shù)字組成：c1c2c3c4c5c6c7c8。C1c2為入學(xué)時(shí)年份的后兩砬；c3c4為系別：0024分別代表該校的25個(gè)系：c5為0或1，0表示本科生，1表示研究生；C6c7c8為對某級某系某類學(xué)生的順序編號，對于本科生，它不超過199，對于研究生，它不超過049，共有4個(gè)年級，四年

39、級學(xué)生1996年入學(xué)。（1）當(dāng)在校生人數(shù)達(dá)極限情況時(shí)，將他們的學(xué)號散列到024999的地址空間，問裝載因子是多少?（2）求一個(gè)無沖突的哈希函數(shù)H1，它將在校生學(xué)號散列到024999的地址空間其簇聚性如何?（3）設(shè)在校生總數(shù)為15000人，散列地址空間為019999，你是否能找到一個(gè)(2)中要求的H1？若不能，試設(shè)計(jì)一個(gè)哈希函數(shù)H2及其解決沖突的方法，使得多數(shù)學(xué)號可只經(jīng)一次散列得到（可設(shè)各系各年級本科生平均人數(shù)為130，研究生平均人數(shù)為20）。（4）用算法描述語言表達(dá)H2,并寫出相應(yīng)的查找函數(shù)。5、 請描述數(shù)列（23，19，30，45，19，12）進(jìn)行升序快速排序的過程。  

40、參考答案： 1、答：#define int KeyType /且定義KeyType為int型 typedef struct nodeKeyType key; /關(guān)鍵字域OtherInfoType info; /其它信息域，只是意思意思struct node * next; /鏈表中指針域RecNode; /記錄結(jié)點(diǎn)類型 typedef RecNode * RecList ; /單鏈表用RecList表示 /下面就是排序算法 void InsertSort(RecList R) /鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的直接插入排序算法/R是帶頭結(jié)點(diǎn)的單鏈表RecNode *p,*q,*s,*t; /這四個(gè)指針用于保存排

41、序時(shí)的結(jié)點(diǎn)位置s=R->next; /s指向第一個(gè)結(jié)點(diǎn)t=R; /t指向頭結(jié)點(diǎn)p=R->next; /前一個(gè)記錄q=P->next; /下一個(gè)記錄 while( q ) /當(dāng)q為空時(shí)表示已經(jīng)訪問完畢所有結(jié)點(diǎn),排序結(jié)束if(p->key>q->key)/此時(shí)前一關(guān)鍵字大于后一關(guān)鍵字，因此要進(jìn)行插入操作while (s->key<=q->key&&s!=p) /從頭向右逐個(gè)比較直到p結(jié)點(diǎn)t=s; /記下s結(jié)點(diǎn)位置s=s->next; /指針向右移/比較結(jié)束，找到比q->key大的第一個(gè)結(jié)點(diǎn)(記錄)t->next

42、=q; /摘下q所指結(jié)點(diǎn)，插入到相應(yīng)位置P->next=q->next;q->next=s; q=p->next; /恢復(fù)指針順序S=R->next; t=R;/endif else /此時(shí)沒有插入操作，指針按序右移p=p->next; q=q->next;/endwhile/InsertSort 2、答：(1)直接插入排序:(方括號表示無序區(qū)) 初始態(tài): 265 301 751 129 937 863 742 694 076 438 第一趟：265 301 751 129 937 863 742 694 076 438 第二趟：265 301 751

43、 129 937 863 742 694 076 438 第三趟：129 265 301 751 937 863 742 694 076 438 第四趟：129 265 301 751 937 863 742 694 076 438 第五趟：129 265 301 751 863 937 742 694 076 438 第六趟：129 265 301 742 751 863 937 694 076 438 第七趟：129 265 301 694 742 751 863 937 076 438 第八趟：076 129 265 301 694 742 751 863 937 438 第九趟：076

44、 129 265 301 438 694 742 751 863 937 2：判斷題一棵樹中的葉子結(jié)點(diǎn)數(shù)一定等于與其對應(yīng)的二叉樹中的葉子結(jié)點(diǎn)數(shù)。  參考答案：錯(cuò)誤3：判斷題哈夫曼樹一定是滿二叉樹。  參考答案：錯(cuò)誤4：判斷題一個(gè)無環(huán)有向圖的拓?fù)湫蛄斜厝皇俏ㄒ坏摹?#160; 參考答案：錯(cuò)誤5：判斷題有向圖用鄰接矩陣表示后，頂點(diǎn)i的入度等于鄰接矩陣中第i列的元素個(gè)數(shù)。  參考答案：正確6：判斷題二路歸并排序的核心操作是將兩個(gè)有序序列歸并為一個(gè)有序序列。  參考答案：正確一、判斷題8：判斷題有向圖用鄰接矩陣表

45、示后，頂點(diǎn)i的入度等于鄰接矩陣中第i列的元素個(gè)數(shù)。答案：正確9：判斷題二路歸并排序的核心操作是將兩個(gè)有序序列歸并為一個(gè)有序序列。答案：正確10：判斷題一個(gè)無環(huán)有向圖的拓?fù)湫蛄斜厝皇俏ㄒ坏摹?#160; 答案：錯(cuò)誤 11：判斷題哈夫曼樹一定是滿二叉樹。  答案：錯(cuò)誤 12：判斷題一棵樹中的葉子結(jié)點(diǎn)數(shù)一定等于與其對應(yīng)的二叉樹中的葉子結(jié)點(diǎn)數(shù)。  答案：錯(cuò)誤 二、論述題1.常用的存儲(chǔ)表示方法有哪幾種?答案：常用的存儲(chǔ)表示方法有四種：順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的

46、存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。鏈接存儲(chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。2.下列程序段帶標(biāo)號語句的頻度和時(shí)間復(fù)雜度。( 1 ) I=0;    while (I<n)&&(aI!=k)      I+; /語句3   

47、60;return(I);( 2 ) n為不小于1的整數(shù)（設(shè)k的初值等于1）void pp ( int k)       if (k=n) /語句1    for (I=0; I<n; I+) /語句2        printf(aI); /語句3    else      for (I=k-1;I<n;I+) /語句4&#

48、160;       aI=aI+I; /語句5        pp(k+1); /語句6        /pp答案：（1）這個(gè)算法完成在一維數(shù)組an中查找給定值k的功能。語句三的頻度不僅與問題的規(guī)模n有關(guān)，還與輸入實(shí)例中a的各元素取值以及k的取值相關(guān)，即與輸入實(shí)例的初始狀態(tài)復(fù)雜有關(guān)。若a中沒有與k相等的元素，則語句三的頻度為n；若a中的第一個(gè)元素a0等于k，則語句三

49、的頻度是常數(shù)0。在這種情況下，可用最壞情況下的時(shí)間復(fù)雜度作為時(shí)間復(fù)雜度。在此例中即為O(n)。這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是在任何輸入實(shí)例上運(yùn)行時(shí)間的上界。有時(shí),也可能選擇將算法的平均(或期望)時(shí)間復(fù)雜度作為討論目標(biāo)。所謂的平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例以等概率出現(xiàn)的情況下算法的期望運(yùn)行時(shí)間與問題規(guī)模的數(shù)量級的關(guān)系。此例中，以k出現(xiàn)在任何位置的概率相同，都為1/n，則語句三的執(zhí)行頻度為0+1+2+(n-1)/n=(n-1)/2。它決定了此程序段的平均時(shí)間復(fù)雜度的數(shù)量級為f(n)=n,記作O(n)。 （2）在計(jì)算包含調(diào)用語句的算法的語句頻度時(shí)，需考慮到調(diào)用發(fā)生時(shí)在被調(diào)用算法中各語

50、句的執(zhí)行情況。本題所示的遞歸調(diào)用較之非遞歸調(diào)用的分析更為復(fù)雜。由于k等于n是算法的出口條件,不妨首先分析算法pp(n)的簡單情況,這時(shí)各語句的執(zhí)行頻度分別為:1,n+1,n,0,0,0; 而當(dāng)k=n-1,n-2,1時(shí),語句的執(zhí)行情況和調(diào)度情況,如下表所示。 K 值不考慮調(diào)用時(shí)各語句的執(zhí)行頻度調(diào)用情況語句1語句2語句3語句4語句5語句6n1n+1n000/n-1100321pp(n)n-2100431pp(n-1)1100n+1n1pp(2)對于k=1即pp(1)而言，各語句的執(zhí)行次數(shù)還須將調(diào)用pp(2)時(shí)的執(zhí)行次數(shù)累計(jì)到內(nèi)，pp(2)各語句的執(zhí)行次數(shù)又須將調(diào)用pp(3)時(shí)執(zhí)行次數(shù)累計(jì)到內(nèi)，由此

51、可的語句頻度如下：語句：1+1+1=n語句：0+0+0+(n+1)=n+1語句：0+0+0+n=n語句：(n+1)+n+3=(n-1)(n+4)/2語句：n+(n-1)+2=(n-1)(n+2)/2語句：1+1+.+1+0=n-1算法的時(shí)間復(fù)雜度可以基于頻度最大的語句，應(yīng)為O(n2)。3.算法的時(shí)間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎?答案：不,事實(shí)上，算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的元素取值等相關(guān)，但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時(shí)間復(fù)雜度時(shí)，一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。4.常用的存儲(chǔ)表示方法有哪幾種?答案：常用的存儲(chǔ)表示方法有四

52、種：順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。鏈接存儲(chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。5.確定下列算法中輸出語句的執(zhí)行次數(shù)，并給出算法的時(shí)間復(fù)雜度。（1） void combi (int n)  int I,j,k;  &#

53、160; for ( I=1; I<=n; I+)      for ( j=I+1; j<=n; j+)        for ( k=j+1; k<=n; k+)          cout<<I,j,k;(2) void binary ( int n)  while(n)  

54、;  cout<<n;    n=n/2;          答案：(1)I取值范圍從1n，j取值范圍從I+1n，k取值范圍從j+1n，情況如下表所示： I值j值k值輸出語句的執(zhí)行次數(shù)123, 4, ,nn-2n-1n1n/234,5,nn-3n-1n1n/n-2n-1n1n/n-1n/n/所以，輸出語句共執(zhí)行次數(shù)為(n-2)+(n-3)+1)+(n-3)+(n-4)+1)+1= (n-1)(n-2)/2+(n-2)(n-3

55、)/2+1= (n-1)2+(n-2)2+(n-3)2+12)-(n-1)+(n-2)+(n-3)+.+1)/2=(n-1)n(2n-1)/6-n(n-1)/2)/2=(n(n-1)(2n-4)/12=n(n-1)(n-2)/6(2) ceil(log2n); 6.為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?答案：尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next 和 rear, 查找時(shí)間都是O(1)。 若用頭指針來表示該鏈表

56、，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。7.何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?答案：在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)，通常有以下幾方面的考慮：1.基于空間的考慮。當(dāng)要求存儲(chǔ)的線性表長度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之， 若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的

57、首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。8.指出以下算法中的錯(cuò)誤和低效之處，并把它改寫為一個(gè)既正確又高效的算法。Status DeleteK( SqList &a,int I, int k) /本過程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第I個(gè)元素起的k個(gè)元素。if (I<1| k<0| I+k > a.length) return ERROR;else for (count=1;count<k;count+) /刪除一個(gè)元素for (j=a.Length; j >=I+1;j-) a.elemj-1 = a.elemj;a.length-;rreturn O

58、K;/DeleteK答案：更正：for (j = I+k; j <=a.Length; j+) a.elemj-k = a.elemj; a.Length = a.Length k;9.假設(shè)某個(gè)單向循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表中某個(gè)結(jié)點(diǎn)指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。答案：void Delprior ( Link s)p = q = s; while (p->next!=s) q = p;p = p->next;q->next = s;delete ( p);10.假設(shè)某個(gè)單向循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表中某個(gè)結(jié)點(diǎn)指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。答案：void Delprior ( Link s)p = q = s; while (p->next!=s) q = p;p = p->next;q->next = s;delete ( p);11.已知L1和L2分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，且已知其長度分別為m和n。試寫一算法將這兩個(gè)鏈表連接在一起，請分析你的算法的時(shí)間復(fù)雜度算法如下: LinkList Link( Link