數(shù)據(jù)結(jié)構(gòu)習(xí)題集與參考答案(重要)

.26/26第一章緒論一、填空題數(shù)據(jù)是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)且能夠被計(jì)算機(jī)程序加工處理的符號(hào)集合。_________是數(shù)據(jù)的基本單位；___________是數(shù)據(jù)的最小單位。通常被計(jì)算機(jī)加工處理的數(shù)據(jù)不是孤立無(wú)關(guān)的,而是彼此之間存在著某種聯(lián)系,將這種數(shù)據(jù)間的聯(lián)系稱為________。數(shù)據(jù)結(jié)構(gòu)進(jìn)行形式化定義時(shí),可以從邏輯上認(rèn)為數(shù)據(jù)結(jié)構(gòu)DS是_________的集合D和D上_________的集合R所構(gòu)成的二元組：DS=〔D,R。已知某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為：A=<D,R>,D={01,02,03,04,05,06,07,08,09},R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}。則此數(shù)據(jù)結(jié)構(gòu)屬于_____________結(jié)構(gòu)。一個(gè)算法的時(shí)間復(fù)雜度通常用問(wèn)題規(guī)模大小的函數(shù)來(lái)表示,當(dāng)一個(gè)算法的時(shí)間復(fù)雜度與問(wèn)題規(guī)模n大小無(wú)關(guān)時(shí),則表示為__________；成正比關(guān)系時(shí),則表示為___________；成對(duì)數(shù)關(guān)系時(shí),則表示為___________；成平方關(guān)系時(shí),則表示為__________。數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)包括_____________、樹型結(jié)構(gòu)和圖型結(jié)構(gòu)三種類型,其中樹型結(jié)構(gòu)和圖型結(jié)構(gòu)合稱為_____________；數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)主要包括____________和____________兩種類型。線性結(jié)構(gòu)的特點(diǎn)是：第一個(gè)結(jié)點(diǎn)_______前驅(qū)結(jié)點(diǎn),其余結(jié)點(diǎn)有且僅有_______個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)_______后繼結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且僅有_______個(gè)后繼結(jié)點(diǎn)。樹型結(jié)構(gòu)的特點(diǎn)是：根結(jié)點(diǎn)沒有________結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且僅有________個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)_________后繼結(jié)點(diǎn),其余結(jié)點(diǎn)可以有_________個(gè)后繼結(jié)點(diǎn)。圖型結(jié)構(gòu)的特點(diǎn)是：每個(gè)結(jié)點(diǎn)可以有_________個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。程序段for〔i=1,s=0；s<n；i++s=s+i；的時(shí)間復(fù)雜度為___________。常見的時(shí)間復(fù)雜度有常數(shù)階O<1>、對(duì)數(shù)階O<log2n>、線性階O<n>、平方階O<n2>、線性對(duì)數(shù)階O<nlog2n>、立方階O<n3>、指數(shù)階O<2n>等等,這些數(shù)量階之間的大小關(guān)系為__________________________。二、分析下列用二元組形式表示的數(shù)據(jù)結(jié)構(gòu),指出他們分別屬于何種類型的數(shù)據(jù)結(jié)構(gòu)。A=〔K,R,其中：K={a,b,c,d,e,f,g,h},R={r},r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}。B=〔K,R,其中：K={a,b,c,d,e,f,g,h},R={r},r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}。C=〔K,R,其中：K={a,b,c,d,e},R={r},r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<a,d>,<c,f>}。D=〔K,R,其中：K={48,25,64,57,82,36,75},R={r1,r2},r1={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>}；r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<25,75>}。E=〔K,R,其中：K={1,2,3,4,5,6,7},R={r},r={<1,2>,<2,1>,<1,4>,<4,1>,<2,3>,<3,2>,<3,4>,<4,3>,<1,3>,<3,1>}。三、指出下列各函數(shù)的功能并求出其時(shí)間復(fù)雜度。voidprime<intn>{inti;for<i=2;i<=sqrt<n>;i++>if<n%i==0>break;if<i>sqrt<n>>printf<"yes">;elseprintf<"no">;}longsum1<intn>{ longsum,w,i;for<sum=0,i=1;i<=n;i++>{w=1;for<j=1;j<=i;j++>w=w×i;sum=sum+w;}return<sum>;}longsum2<intn>{ longsum,w,i;for<sum=0,w=1,i=1;i<=n;i++>{w=w×i;sum=sum+w;}return<sum>;}voidsort<intr[],intn>{inti,j;for<i=1;i<n;i++>for<j=0;j<n-i;j++>if<r[j]>r[j+1]>{temp=r[j];r[j]=r[j+1];r[j+1]=temp;}}第一章參考答案一、填空題數(shù)據(jù)元素,數(shù)據(jù)項(xiàng),結(jié)構(gòu)數(shù)據(jù),關(guān)系樹型O<1>,O<n>,O<log2n>,O<n2>線性結(jié)構(gòu),非線性結(jié)構(gòu),順序結(jié)構(gòu),鏈?zhǔn)浇Y(jié)構(gòu)無(wú),一,無(wú),一前驅(qū),一,無(wú),任意任意O<n1/2>分析：設(shè)程序段中的循環(huán)體執(zhí)行k次,則有不等式成立,解此不等式得到不等式,因此。O<1><O<log2n><O<n><O<nlog2n><O<n2><O<n3><O<2n>二、分析下列用二元組形式表示的數(shù)據(jù)結(jié)構(gòu),指出他們分別屬于何種類型的數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)樹型結(jié)構(gòu)圖型結(jié)構(gòu)圖型結(jié)構(gòu)分析：數(shù)據(jù)結(jié)構(gòu)D中的關(guān)系集合R有兩個(gè)關(guān)系r1和r2。如果只考慮關(guān)系r1,則為線性結(jié)構(gòu)；如果只考慮關(guān)系r2,則為樹型結(jié)構(gòu)；如果把關(guān)系r1和r2聯(lián)合起來(lái)考慮,則為圖型結(jié)構(gòu)。圖型結(jié)構(gòu)分析：若用圖形來(lái)表示則可以看出r是E上的對(duì)稱關(guān)系,為了簡(jiǎn)化起見,我們通常把<x,y>和<y,x>這兩個(gè)有序偶對(duì)用一個(gè)無(wú)序偶對(duì)<x,y>或<y,x>來(lái)代替。在用圖形表示時(shí),我們把x結(jié)點(diǎn)和y結(jié)點(diǎn)之間兩條相反的弧用一條無(wú)向邊來(lái)代替。三、指出下列各函數(shù)的功能并求出其時(shí)間復(fù)雜度。函數(shù)的功能是判斷n是否是一個(gè)素?cái)?shù),其時(shí)間復(fù)雜度為O<n1/2>。分析：函數(shù)prime中出現(xiàn)的庫(kù)函數(shù)sqrt為平方根函數(shù),因此。函數(shù)的計(jì)算的值,其時(shí)間復(fù)雜度為O<n2>。函數(shù)的計(jì)算的值,其時(shí)間復(fù)雜度為O<n>。函數(shù)的功能是對(duì)數(shù)組r中的n個(gè)元素進(jìn)行冒泡排序,其時(shí)間復(fù)雜度為O<n2>。分析：。第二章線性表一、填空題設(shè)長(zhǎng)度為n的順序線性表在任何位置上插入或刪除操作都是等概率的,則插入一個(gè)元素時(shí)平均需要移動(dòng)_______個(gè)元素,刪除一個(gè)元素時(shí)平均需要移動(dòng)______個(gè)元素。在順序線性表中插入一個(gè)元素時(shí),插入位置開始后的所有元素均需要________移動(dòng)一個(gè)位置。在順序線性表中刪除一個(gè)元素時(shí),被刪除元素后的所有元素均需要__________移動(dòng)一個(gè)位置。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,元素之間的線性關(guān)系是通過(guò)結(jié)點(diǎn)中的________來(lái)實(shí)現(xiàn)的。線性表的順序存儲(chǔ)結(jié)構(gòu)中邏輯上相鄰的元素,物理位置__________相鄰；線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中邏輯上相鄰的元素,物理位置____________相鄰。已知單鏈表的長(zhǎng)度為n,則在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為__________。已知單鏈表的長(zhǎng)度為n,則刪除給定值為x的結(jié)點(diǎn)的時(shí)間復(fù)雜度為__________。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是________________________________。雙向鏈表中每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域,其中一個(gè)指針域指向_______結(jié)點(diǎn),另一個(gè)指針域指向______結(jié)點(diǎn)。在長(zhǎng)度為n的線性表中順序查找某個(gè)結(jié)點(diǎn)值為X的時(shí)間復(fù)雜度為______________。二、選擇題1．在長(zhǎng)度為n的順序線性表中刪除第i個(gè)元素<1<=i<=n>,則需要向前移動(dòng)的元素個(gè)數(shù)為〔。⑴n-i ⑵n+1-i ⑶n-1-i ⑷i2．建立一個(gè)長(zhǎng)度為n的單鏈表的時(shí)間復(fù)雜度為〔。⑴O<n> ⑵O<1> ⑶O<n2> ⑷<<log2n>3．設(shè)指針p指向單鏈表中的結(jié)點(diǎn)A,結(jié)點(diǎn)A的后繼結(jié)點(diǎn)是結(jié)點(diǎn)B,則刪除結(jié)點(diǎn)B的操作為〔。⑴p->next=p ⑵p=p->next⑶p=p->next->next ⑷p->next=p->next->next4．設(shè)指針p指向單鏈表中結(jié)點(diǎn)A,指針q指向單鏈表中結(jié)點(diǎn)A的前驅(qū)結(jié)點(diǎn)B,指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A和結(jié)點(diǎn)B之間插入結(jié)點(diǎn)X的操作為〔。⑴s->next=p->next；p->next=s；⑵q->next=s；s->next=p；⑶p->next=s->next；s->next=p；⑷p->next=s；s->next=q；5．在長(zhǎng)度為n的順序線性表中的第i個(gè)元素<1<=i<=n+1>之前插入一個(gè)新元素時(shí),則需要向后移動(dòng)的元素個(gè)數(shù)為〔。⑴n-i ⑵n+1-i ⑶n-1-i ⑷i6．在長(zhǎng)度為n的有序線性表中插入一個(gè)元素后仍然保持有序的平均時(shí)間復(fù)雜度為〔。⑴O<log2n>⑵O<1> ⑶O<n2> ⑷O<n>7．設(shè)指針p指向雙向鏈表中的結(jié)點(diǎn)A,指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A之后插入結(jié)點(diǎn)X的操作為〔。⑴p->rlink=s；s->llink=p；p->rlink->llink=s；s->rlink=p->rlink；⑵s->llink=p；s->rlink=p->rlink；p->rlink=s；p->rlink->llink=s；⑶p->rlink=s；p->rlink->llink=s；s->llink=p；s->rlink->p->rlink；⑷s->llink=p；s->rlink=p->rlink；p->rlink->llink=s；p->rlink=s；8．指針p指向雙向鏈表中的結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的操作是〔。⑴p->llink->rlink=p->rlink；p->rlink->llink=p->llink；⑵p->rlink->llink=p->rlink；p->llink->llink=p->llink；⑶p->llink->rlink=p->llink；p->rlink->llink=p->rlink；⑷p->rlink->rlink=p->rlink；p->rlink->rlink=p->rlink；9．線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),要求存儲(chǔ)單元的地址〔。⑴必須是連續(xù)的⑵部分地址必須是連續(xù)的⑶一定是不連續(xù)的 ⑷連續(xù)不連續(xù)都可以10．設(shè)head為單鏈表的頭指針,則不帶頭結(jié)點(diǎn)的單鏈表為空的判定條件是〔。⑴head==NULL ⑵head->next==NULL⑶head->next==head ⑷head!=NULL11．設(shè)head為單鏈表的頭指針,則帶頭結(jié)點(diǎn)的單鏈表為空的判定條件是〔。⑴head==NULL ⑵head->next==NULL⑶head->next==head ⑷head!=NULL12．設(shè)head和tail分別為單向循環(huán)鏈表的頭指針和尾指針,則下列等式成立的是〔。⑴head==tail ⑵head->next==tail⑶tail->next==head ⑷head->next==tail->next三、算法設(shè)計(jì)題順序存儲(chǔ)結(jié)構(gòu)的類型定義：typedefstruct{inta[m];intn;}sqlist;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的類型定義：typedefstructnode{intdata;structnode*next;}lklist;建立一個(gè)有n個(gè)結(jié)點(diǎn)的單鏈表,要求從尾部進(jìn)行插入。建立一個(gè)有n個(gè)結(jié)點(diǎn)的單鏈表,要求從頭部進(jìn)行插入。用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表就地逆置算法,即在原表的存儲(chǔ)空間內(nèi)將線性表〔a1,a2,……,an逆置為<an,an-1,……,a1>。用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表就地逆置算法,即在原表的存儲(chǔ)空間內(nèi)將線性表〔a1,a2,……,an逆置為<an,an-1,……,a1>。已知集合A、B,求集合C=A∩B算法,要求集合A、B和C均用采用順序存儲(chǔ)結(jié)構(gòu)表示。已知集合A、B,求集合C=A∩B算法,要求集合A、B和C均用采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。設(shè)計(jì)在帶有頭結(jié)點(diǎn)的單向鏈表中刪除值為X的結(jié)點(diǎn)算法。第二章參考答案一、填空題n/2,<n-1>/2分析：當(dāng)在順序線性表中的第i〔1<=i<=n+1個(gè)位置之前插入一個(gè)新元素時(shí),從第i個(gè)元素起向后的n+1-i個(gè)元素均要向后移動(dòng)一個(gè)位置。因此在等概率情況下,插入操作中元素的平均移動(dòng)次數(shù)為；當(dāng)在順序線性表中刪除第i〔1<=i<=n個(gè)位置上的元素,從第i+1個(gè)元素起向后的n-i個(gè)元素均要向前移動(dòng)一個(gè)位置。因此在等概率情況下,刪除操作中元素的平均移動(dòng)次數(shù)為。向后向前指針域一定,不一定O<n>O<n>消除空表的特殊性,統(tǒng)一表示和處理空表和非空表的情形,從而簡(jiǎn)化插入和刪除等操作的某些細(xì)節(jié)。前驅(qū),后繼O<n>二、填空題<1><1>分析：建立一個(gè)單鏈表的過(guò)程實(shí)際上就是在空鏈表的基礎(chǔ)之上從單鏈表的頭部或從單鏈表的尾部不斷插入新結(jié)點(diǎn)的過(guò)程,因此建立單鏈表的時(shí)間復(fù)雜度為O<n>。<4><2><2><4>分析：在有序的線性表中插入一個(gè)元素后仍然保持有序的過(guò)程分為兩步：第一步查找插入位置,第二步插入新元素。在線性表中查找插入位置的平均時(shí)間復(fù)雜度為f1<n>=O<n>,在順序線性表中插入新元素的平均時(shí)間復(fù)雜度為f2<n>=O<n>,而在鏈?zhǔn)骄€性表中插入新元素的平均時(shí)間復(fù)雜度為f2<n>=O<1>,因此本題中的平均時(shí)間復(fù)雜度f(wàn)<n>=O<n>+O<1>=O<n>或f<n>=O<n>+O<n>=O<n>。<4>分析：在雙向鏈表或雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)的操作比較繁瑣,通常需要修改4個(gè)指針域,根據(jù)排列公式可知共有4!=24種方案。在這24種方案中,有些方案是可行的,有些方案是不可行的。我們的通常做法是先連接哪些不破壞有用信息的指針域,然后再根據(jù)需要連接其余的指針域,在操作過(guò)程中注意修改有關(guān)結(jié)點(diǎn)指針域的操作順序,以免丟失鏈域信息而造成鏈表中斷的錯(cuò)誤。<1>分析：在雙向鏈表或雙向循環(huán)鏈表中刪除一個(gè)結(jié)點(diǎn)的操作比較相對(duì)插入一個(gè)新結(jié)點(diǎn)而言稍微簡(jiǎn)單一些,只需要修改兩個(gè)指針域。首先找到指向前驅(qū)結(jié)點(diǎn)的指針〔p->left和指向后繼結(jié)點(diǎn)的指針〔p->right,然后再分別表示出前驅(qū)結(jié)點(diǎn)中的右指針域〔p->left->right和后繼結(jié)點(diǎn)的左指針域〔p->right->left,最后分別修改前驅(qū)結(jié)點(diǎn)中的右指針域和后繼結(jié)點(diǎn)的左指針域。<4><1><2><3>三、算法設(shè)計(jì)題建立一個(gè)有n個(gè)結(jié)點(diǎn)的單鏈表,要求從尾部進(jìn)行插入。分析：本題的算法思想是設(shè)置指針變量q始終指向當(dāng)前鏈表中的最后一個(gè)結(jié)點(diǎn),新生成的結(jié)點(diǎn)直接在尾部進(jìn)行插入。這種設(shè)置指針變量q的方法使得操作比較簡(jiǎn)單,否則每次在尾部插入新結(jié)點(diǎn)時(shí)需要用一個(gè)臨時(shí)指針變量從鏈表頭部移到鏈表尾部。voidcreatelklistfromtail<lklist*&head>{inti;lklist*p,*q;for<i=1,head=0;i<=n;i++>{p=<lklist*>malloc<sizeof<lklist>>;scanf<"%d",&<p->data>>;p->next=0;if<i==1>head=q=p;else{q->next=p;q=p;}}}提示：以下形式參數(shù)表中出現(xiàn)在形式參數(shù)名前加符號(hào)"&"的現(xiàn)象,這種現(xiàn)象在我們常見的TurboC2.0版本中不能使用,但在BorlandC3.1及其以后版本中可以使用,它的作用是使得對(duì)形式參數(shù)的修改可以影響到對(duì)應(yīng)的實(shí)在參數(shù)。以后算法設(shè)計(jì)題中經(jīng)常用到。建立一個(gè)有n個(gè)結(jié)點(diǎn)的單鏈表,要求從頭部進(jìn)行插入。voidcreatelklistfromhead<lklist*&head>{inti;lklist*p,*q;for<i=1,q=head=0;i<=n;i++>{p=<lklist*>malloc<sizeof<lklist>>;scanf<"%d",&<p->data>>;p->next=head;head=p;}}提示：不斷從頭部插入新結(jié)點(diǎn)的方法來(lái)構(gòu)造單向鏈表比不斷從尾部插入新結(jié)點(diǎn)的方法來(lái)構(gòu)造單向鏈表稍微操作簡(jiǎn)單一些。但順序打印從尾部插入建立的單向鏈表所得到的序列與建立單向鏈表輸入的序列一樣,而順序打印從頭部插入建立的單向鏈表所得到的序列與建立單向鏈表輸入的序列正好相反。用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表就地逆置算法,即在原表的存儲(chǔ)空間內(nèi)將線性表〔a1,a2,……,an逆置為<an,an-1,……,a1>。voidinvertsqlist<sqlist&list>{inti,temp,n=list.n;for<i=1;i<=n/2;i++>{temp=list.a[i-1];list.a[i-1]=list.a[n-i];list.a[n-i]=temp;}}提示：本題中的循環(huán)次數(shù)只能是順序線性表的長(zhǎng)度一半,如果循環(huán)次數(shù)是順序線性表的長(zhǎng)度,則經(jīng)過(guò)逆置后再逆置而還原到初始狀態(tài)。用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表就地逆置算法,即在原表的存儲(chǔ)空間內(nèi)將線性表〔a1,a2,……,an逆置為<an,an-1,……,a1>。分析：本題的算法思想是依次將單鏈表中的結(jié)點(diǎn)取出來(lái)并用指針q指向它,然后再用從頭部插入的方法建立一個(gè)新的單鏈表。voidinvertlklist<lklist*&head>{lklist*p=head,*q;head=0;while<p!=0>{q=p;p=p->next;q->next=head;head=q;}}已知集合A、B,求集合C=A∩B算法,要求集合A、B和C均用采用順序存儲(chǔ)結(jié)構(gòu)表示。分析：本題的算法思想是順序取出集合A中的元素A[i],然后再在集合B中從前向后進(jìn)行順序查找,如果找到等于該元素的結(jié)點(diǎn)則將其放入集合C中,否則什么也不做。本題算法思想同樣適用于其后的第6題。voidintersectionsqlist<sqlistlista,sqlistlistb,sqlist&listc>{inti,j;for<listc.n=0,i=0;i<=lista.n-1;i++>{for<j=0;j<=listb.n-1;j++>if<listb.a[j]==lista.a[i]>break;if<j<=listb.n-1>{listc.a[listc.n]=lista.a[i];listc.n++;}}}已知集合A、B,求集合C=A∩B算法,要求集合A、B和C均用采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。voidintersectionlklist<lklist*lista,lklist*listb,lklist*&listc>{lklist*p,*q,*s;for<listc=0,p=lista;p!=0;p=p->next>{for<q=listb;q!=0;q=q->next>if<p->data==q->data>break;if<q!=0>{s=<lklist*>malloc<sizeof<lklist>>;s->data=p->data;s->next=listc;listc=s;}}}設(shè)計(jì)在帶有頭結(jié)點(diǎn)的單向鏈表中刪除值為X的結(jié)點(diǎn)算法。分析：本題的算法思想是首先在單鏈表中查找值為x的結(jié)點(diǎn),如果單鏈表為空或在單鏈表中找不到值為x的結(jié)點(diǎn)則給出相應(yīng)的提示信息,否則進(jìn)行刪除操作。為了便于刪除操作的實(shí)現(xiàn)而設(shè)置指針變量p指向被刪除的結(jié)點(diǎn),指針變量q始終指向其前驅(qū)結(jié)點(diǎn)。voiddeletelklist<lklist*&head,intx>{lklist*q,*p;if<head->next==0>printf<"Thislinklistisempty\n">;elsefor<q=head,p=head->next;p!=0;q=p,p=p->next>if<p->data==x>break;if<p==0>printf<"Notfound%dinthislinklist\n",x>;else{q->next=p->next;free<p>;}}提示：在鏈表中引入頭結(jié)點(diǎn)后可以消除空表的特殊性,統(tǒng)一表示和處理空表和非空表的情形,從而簡(jiǎn)化插入和刪除等操作的某些細(xì)節(jié)。具體涉及到本題中,如果沒有引入頭結(jié)點(diǎn),則在找到值為x的結(jié)點(diǎn)后要區(qū)分該結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)還是其它結(jié)點(diǎn),而引入頭結(jié)點(diǎn)后,則這兩種情況就可以統(tǒng)一處理。如果本題中的單鏈表沒有帶頭結(jié)點(diǎn),則需要將上述黑體中的代碼改為代碼if<p==head>head=p->next;elseq->next=p->next;。第三章棧和隊(duì)列一、填空題線性表、棧和隊(duì)列從邏輯上來(lái)說(shuō)都是____________結(jié)構(gòu)?？梢栽诰€性表的_______位置插入和刪除元素；對(duì)于棧只能在__________插入和刪除元素；對(duì)于隊(duì)列只能在___________插入元素和在_________刪除元素。棧的插入和刪除只能在棧的棧頂進(jìn)行,后進(jìn)棧的元素必定先出棧,所以又把棧稱為__________表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行,進(jìn)行插入的一端叫做__________,進(jìn)行刪除的一端叫做___________,先進(jìn)隊(duì)的元素必定先出隊(duì),所以又把隊(duì)列稱為____________表。假設(shè)用向量S[1：m]來(lái)存儲(chǔ)順序棧,指針top指向當(dāng)前棧頂?shù)奈恢谩t當(dāng)棧為空時(shí)滿足的條件是____________；當(dāng)棧為滿時(shí)滿足的條件是_____________。設(shè)有一個(gè)空棧,現(xiàn)有輸入序列1、2、3、4、5,經(jīng)過(guò)push、push、pop、push、pop、push、push、pop、pop、pop后,輸出序列為__________________。在一個(gè)順序循環(huán)隊(duì)列中為了方便入隊(duì)列和出隊(duì)列的操作通常約定頭指針front指向?qū)嶋H隊(duì)頭元素的____________,尾指針rear指向當(dāng)前實(shí)際隊(duì)尾元素的____________。若該順序循環(huán)隊(duì)列有m個(gè)存儲(chǔ)單元,則隊(duì)列滿時(shí)共有__________個(gè)元素。設(shè)有一個(gè)順序循環(huán)隊(duì)列如上題中的約定,則該隊(duì)列滿的條件是_________,隊(duì)列空的條件是_________。不論是順序棧〔隊(duì)列還是鏈?zhǔn)綏！碴?duì)列,插入〔刪除運(yùn)算的時(shí)間復(fù)雜度均為________。系統(tǒng)在函數(shù)調(diào)用前自動(dòng)把調(diào)用后的____________壓入堆棧；當(dāng)函數(shù)調(diào)用結(jié)束后,系統(tǒng)又自動(dòng)作退棧處理,并將程序執(zhí)行流程無(wú)條件轉(zhuǎn)移到所保存的_____________處繼續(xù)執(zhí)行。二、選擇題1．設(shè)棧的輸入序列是1、2、3、…、n,輸出序列的第一個(gè)元素是n,則第i個(gè)輸出元素是〔。①n-i ②n-i-1 ③n-i+1 ④不確定2．設(shè)元素進(jìn)棧次序?yàn)锳、B、C、D、E,則下列不可能的出棧序列是〔。①ABCDE ②BCDEA ③EABCD ④EDCBA3．設(shè)用一維數(shù)組s[m]表示棧的存儲(chǔ)空間,用top指向當(dāng)前棧頂元素〔其初始值為-1,則進(jìn)行出棧時(shí)的操作序列是〔。①x=s[op]； ②x=s[top]；top=0；③x=s[top]；top==top-1；④x=s[top]；top==top+1；4．設(shè)指針hs指向棧頂,指針s指向插入的結(jié)點(diǎn)A,則插入結(jié)點(diǎn)A時(shí)的操作為〔。①hs->next=s；②s->next=hs；hs=s；③s->next=hs->next；hs->next=s；④s->next=hs；hs=hs->next；5．設(shè)用一維數(shù)組s[m]表示棧的存儲(chǔ)空間,用top指向當(dāng)前棧頂元素〔其初始值為-1,則進(jìn)行入棧時(shí)的操作序列是〔。①s[top]=x； ②top=top+1；s[top]=x；③top==top-1；s[top]=x；④s[top]=x；top==top+1；6．設(shè)front是鏈?zhǔn)疥?duì)列的頭指針,rear是鏈?zhǔn)疥?duì)列的尾指針,s指向插入的結(jié)點(diǎn)A,則插入結(jié)點(diǎn)A的操作為〔。①front->next=s；front=s；②s->next=rear；rear=s；③rear->next=s；rear=s；④s->next=front；front=s；7．設(shè)front是鏈?zhǔn)疥?duì)列的頭指針,rear是鏈?zhǔn)疥?duì)列的尾指針,則刪除隊(duì)頭元素的操作為〔。①front=front->next；②rear=rear->next ；③rear=front->next ；④front=rear->next；8．對(duì)于一個(gè)具有m個(gè)存儲(chǔ)單元的順序循環(huán)隊(duì)列,設(shè)front為隊(duì)頭指針,rear為隊(duì)尾指針,則該隊(duì)列中隊(duì)列元素的個(gè)數(shù)計(jì)算公式為〔。①rear-front ②front-rear③<rear-front>%m ④<rear-front+m>%m設(shè)用一維數(shù)組q[m]作為順序循環(huán)隊(duì)列的存儲(chǔ)空間,front指向隊(duì)頭元素的前一個(gè)位置,rear指向隊(duì)尾元素的當(dāng)前位置,則入隊(duì)列的操作序列為〔。①q[rear]=x；rear=rear+1；②q[rear]=x；rear=rear-1；③rear=<rear+1>%m；q[rear]=x； ④rear=<rear-1>%m；q[rear]=x；設(shè)用一維數(shù)組q[m]作為順序循環(huán)隊(duì)列的存儲(chǔ)空間,front指向隊(duì)頭元素的前一個(gè)位置,rear指向隊(duì)尾元素的當(dāng)前位置,則出隊(duì)列的操作序列為〔。①x=q[front]；front=front+1；②x=q[front]；front=<front+1>%m；③x=q[front]；front=front-1； ④x=q[front]；front=<front-1>%m；三、算法設(shè)計(jì)題設(shè)有兩個(gè)順序棧S1和S2共享一個(gè)存儲(chǔ)區(qū)S[0：m-1],為了盡量利用存儲(chǔ)空間減少溢出的可能性,采用棧頂相向、迎面增長(zhǎng)的存儲(chǔ)方式,要求分別設(shè)計(jì)兩個(gè)棧的入棧和出棧操作。設(shè)計(jì)算法判斷表達(dá)式中的圓括號(hào)是否配對(duì)出現(xiàn)。設(shè)用一個(gè)單向循環(huán)鏈表來(lái)表示隊(duì)列〔也稱循環(huán)隊(duì)列,該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針rear,不設(shè)隊(duì)頭指針front,要求設(shè)計(jì)出該隊(duì)列的入隊(duì)列和出隊(duì)列操作。假設(shè)以一個(gè)一維向量q[0：m-1]作為順序循環(huán)隊(duì)列的存儲(chǔ)空間,同時(shí)設(shè)變量rear和len分別指示順序循環(huán)隊(duì)列中的隊(duì)尾元素的位置和實(shí)際隊(duì)列中的元素個(gè)數(shù),要求設(shè)計(jì)出該隊(duì)列的入隊(duì)列和出隊(duì)列操作。將數(shù)字1、2、……、n按順時(shí)針?lè)较蚺帕谐森h(huán)形,按順時(shí)針?lè)较驈?開始計(jì)數(shù),計(jì)滿時(shí)則輸出該位置上的數(shù)字并從環(huán)中刪除該數(shù)字,然后從下一個(gè)數(shù)字開始繼續(xù)計(jì)數(shù),直到環(huán)中所有數(shù)字均被輸出為止,要求設(shè)計(jì)一個(gè)算法完成此功能。第三章參考答案一、填空題線性,任何,棧頂,隊(duì)尾,隊(duì)頭先進(jìn)后出〔FILO,隊(duì)尾,隊(duì)頭,先進(jìn)先出〔FIFOtop==0,top==m23541前一個(gè)位置,所在位置,m-1分析：在順序循環(huán)隊(duì)列中約定頭指針front和尾指針rear所指向的位置,是犧牲掉一個(gè)存儲(chǔ)單元而方便表示隊(duì)列空和隊(duì)列滿的條件,因此順序循環(huán)隊(duì)列中實(shí)際可用的存儲(chǔ)單元只有m-1個(gè)。<rear+1>%m==front,rear==frontO<1>返回地址,返回地址二、選擇題<3>分析：設(shè)棧的輸入序列是1、2、3、……、n,輸出序列的第一個(gè)元素是n,則輸出序列必定是n、n-1、n-2、……、1,因此第i個(gè)輸出元素是n+1-i。<3><3><2><2><3><1><4>分析：順序循環(huán)隊(duì)列中的元素個(gè)數(shù)=,整理合并可寫成<rear-front+m>%m。<3><2>三、算法設(shè)計(jì)題設(shè)有兩個(gè)順序棧S1和S2共享一個(gè)存儲(chǔ)區(qū)S[0：m-1],為了盡量利用存儲(chǔ)空間減少溢出的可能性,采用棧頂相向、迎面增長(zhǎng)的存儲(chǔ)方式,要求分別設(shè)計(jì)兩個(gè)棧的入棧和出棧操作。分析：本題算法思想是引入形式參數(shù)flag,當(dāng)形式參數(shù)flag的值為1時(shí)表示對(duì)棧1進(jìn)行操作,flag的值為2時(shí)表示對(duì)棧2進(jìn)行操作。typedefstruct{ints[m];inttop1;inttop2;}sqstack;voidpush<sqstack&stack,intx,intflag>{if<stack.top1+1==stack.top2>printf<"stackisfull\n">;else{if<flag==1>{stack.top1++;stack.s[stack.top1]=x;}elseif<flag==2>{stack.top2--;stack.s[stack.top2]=x;}elseprintf<"inputerror\n">;}}voidpop<sqstack&stack,int&y,intflag>{if<flag==1>if<stack.top1<0>printf<"empty\n">;else{y=stack.s[stack.top1];stack.top1--;}elseif<flag==2>if<stack.top2>=m>printf<"empty\n">;else{y=stack.s[stack.top2];stack.top2--;}elseprintf<"inputerror\n">;}設(shè)計(jì)算法判斷表達(dá)式中的圓括號(hào)是否配對(duì)出現(xiàn)。分析：本題的算法思想是順序掃描表達(dá)式,當(dāng)掃描到左圓括號(hào)時(shí)進(jìn)棧而掃描到右圓括號(hào)時(shí)出棧,如果掃描到右圓括號(hào)時(shí)不能出棧或掃描表達(dá)式結(jié)束時(shí)棧中仍有左圓括號(hào)則意味表達(dá)式中圓括號(hào)不匹配,否則表達(dá)式中圓括號(hào)匹配。typedefstruct{ints[m];inttop;}sqstack;intmatchbracket<>{charch;sqstackstack;stack.top=-1;do{ch=getchar<>;if<ch==‘<’>{stack.top=stack.top+1;stack.s[stack.top]=ch;}elseif<ch==‘>’>if<stack.top<0>return<0>;elsestack.top=stack.top-1;}while<ch!=‘#’>;if<stack.top<0>return<1>;elsereturn<0>;}設(shè)用一個(gè)單向循環(huán)鏈表來(lái)表示隊(duì)列〔也稱鏈?zhǔn)窖h(huán)隊(duì)列,該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針rear,不設(shè)隊(duì)頭指針front,要求設(shè)計(jì)出該隊(duì)列的入隊(duì)列和出隊(duì)列操作。typedefstructnode{intdata;structnode*next;}lklist;voidinlkqueue<lklist*&rear,intx>{lklist*p;p=<lklist*>malloc<sizeof<lklist>>;p->data=x;if<rear==0>{rear=p;rear->next=rear;}else{p->next=rear->next;rear->next=p;rear=p;}}voidoutlkqueue<lklist*&rear,int&y>{lklist*p;if<rear==0>printf<"queueisempty\n">;elseif{rear->next==rear}{y=rear->data;rear=0;}else{p=rear->next;y=p->data;rear->next=p->next;free<p>;}}假設(shè)以一個(gè)一維向量q[0：m-1]作為順序循環(huán)隊(duì)列的存儲(chǔ)空間,同時(shí)設(shè)變量rear和len分別指示順序循環(huán)隊(duì)列中的隊(duì)尾元素的位置和實(shí)際隊(duì)列中的元素個(gè)數(shù),要求設(shè)計(jì)出該隊(duì)列的入隊(duì)列和出隊(duì)列操作。分析：本題中出隊(duì)列的算法思路是設(shè)置一個(gè)臨時(shí)變量front指向當(dāng)前隊(duì)列中隊(duì)頭元素的實(shí)際位置,考慮到表達(dá)式queue.rear+1-queue.len的值可能為負(fù),因此設(shè)置front的值為<queue.rear+1-queue.len+m>%m。typedefstruct{intq[m];intrear;intlen;}sqqueue;voidinsqqueue<sqqueue&queue,intx>{if<queue.len==m>printf<"queueisfull\n">;else{queue.rear=<queue.rear+1>%m;queue.q[queue.rear]=x;queue.len++;}}voidoutsqqueue<sqqueue&queue,int*y>{intfront;if<queue.len==0>printf<"queueisemptyl\n">;else{front=queue.rear+1-queue.len+m}%m;y=queue.q[queue.front];queue.len--;}}編寫一個(gè)算法解決約瑟夫〔Josephus環(huán)問(wèn)題。其問(wèn)題是：設(shè)有n個(gè)人圍坐在一張圓桌周圍,現(xiàn)從第一個(gè)人開始從1報(bào)數(shù),報(bào)到k的人出離開圓桌,接著從下一個(gè)人從1開始重新報(bào)數(shù),……,以此類推,直到他們都離開圓桌,求出他們離開圓桌的先后順序。分析：本題的算法思路是設(shè)置變量sum和num,其中變量sum表示當(dāng)前已經(jīng)離開圓桌的人數(shù)個(gè)數(shù),變量num表示當(dāng)前的報(bào)數(shù)。voidJosephus<intn,intk>{inti,num,sum,r[100];for<i=0;i<n;i++>r[i]=i;for<sum=num=i=0;sum<n;i=<i+1>%n>if<r[i]!=-1>{num++;if<num%k==0>{printf<"%d\t",i>;num=0;sum++;r[i]=-1;}}}第四章字符串和數(shù)組一、填空題設(shè)字符串S1="ABCDEF",S2="PQRS",則運(yùn)算S=CONCAT<SUB<S1,2,LEN<S2>>,SUB<S1,LEN<S2>,2>的結(jié)果為S=_________________。判斷兩個(gè)字符串相等的充要條件是____________________________。下列程序段實(shí)現(xiàn)子串t在主串s中位置的算法,要求在下劃線處填上正確語(yǔ)句。intindex<chars[],chart[]>{i=j=0;while<i<strlen<s>&&j<strlen<t>>/*函數(shù)strlen的功能是求字符串的長(zhǎng)度*/if<s[i]==t[j]>{i=i+l;j=j+l;}else{i=_______;j=______;}if<j==strlen<t>>return<i-strlen<t>>;elsereturn<-1>;}設(shè)二維數(shù)組A有m行n列,每個(gè)數(shù)組元素占L個(gè)字節(jié)的存儲(chǔ)單元,按行的順序存放在m*n個(gè)連續(xù)的存儲(chǔ)單元中。已知A[0][0]的地址為1000,則A[i][j]的地址為______________________________________。設(shè)三維數(shù)組A[3][4][5]中的每個(gè)元素占10個(gè)字節(jié)的存儲(chǔ)單元,按行的順序存放在一組連續(xù)的存儲(chǔ)空間中。已知A[0][0][0]的首地址為1000,則數(shù)組元素A[1][2][3]的首地址為___________________________。設(shè)對(duì)稱矩陣A有n行n列,每個(gè)數(shù)組元素占L個(gè)字節(jié)的存儲(chǔ)單元,按行的順序?qū)⑾氯蔷仃囍械脑亍舶▽?duì)角線上的元素存放在n*<n+1>/2個(gè)存儲(chǔ)單元中,已知A[0][0]的地址為1000,則A[i][j]〔i>=j的地址為___________________________。設(shè)有n行n列的三對(duì)角矩陣A,每個(gè)數(shù)組元素占L個(gè)字節(jié)的存儲(chǔ)單元,按照從上到下從左到右的順序?qū)⑷龡l對(duì)角線上的元素存放在3n-2個(gè)連續(xù)的存儲(chǔ)單元中,已知A[0][0]的地址為1000,則三對(duì)角線上元素A[i][j]的地址為_________________。已知稀疏矩陣A=,則A的三元組表為__________________。二、算法設(shè)計(jì)題設(shè)用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)字符串S1和S2,要求設(shè)計(jì)一個(gè)函數(shù)完成對(duì)兩個(gè)字符串的比較。若S1>S2時(shí)則返回正數(shù)；若S1=S2時(shí)則返回0；若S1<S2時(shí)則返回負(fù)數(shù)。用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)在字符串S中刪除所有其值等于ch的字符的算法。設(shè)單鏈表中存放n個(gè)字符,試設(shè)計(jì)算法判斷字符串是否關(guān)于中心對(duì)稱。第四章參考答案一、填空題"ABCDDE"字符串的長(zhǎng)度相等且對(duì)應(yīng)位置上的字符相等i-j+1,0分析：在查找子串位置的過(guò)程中,當(dāng)發(fā)現(xiàn)s[i]!=t[j]時(shí)需要重新調(diào)整指針i和j的值后繼續(xù)查找。指針j的值肯定調(diào)整到子串的開始位置0,而指針i的值則相應(yīng)調(diào)整到i-j的后一個(gè)位置i-j+1。1000+<i*n+j>*L1330分析：A[1][2][3]的首地址=1000+<1*4*5+2*5+3>*10=1330。1000+<i*<i+1>/2+j>*L分析：A[i][j]的首地址=1000+<1+2+……+i+j>*L=1000+<i*<i+1>/2+j>*L。<2*i+j>*L分析：A[i][j]的首地址=,經(jīng)合并整理可得A[i][j]的首地址=<2*i+j>*L。二、算法設(shè)計(jì)題設(shè)用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)字符串S1和S2,要求設(shè)計(jì)一個(gè)函數(shù)完成對(duì)兩個(gè)字符串的比較。若S1>S2時(shí)則返回正數(shù)；若S1=S2時(shí)則返回0；若S1<S2時(shí)則返回負(fù)數(shù)。intcomparestring<chars1[],chars2[]>{inti;for<i=0;s1[i]!=0;i++>if<s1[i]!=s2[i]>break;return<s1[i]-s2[i]>;}用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)在字符串S中刪除所有其值等于ch的字符的算法。voiddeletestring<chars[],charch>{inti=0,j;while<s[i]!=0>if<s[i]==ch>{for<j=i+1;s[j]!=0;j++>s[j-1]=s[j];s[j-1]=0;}elsei++;}設(shè)計(jì)一個(gè)算法判斷字符串S中的字符是否關(guān)于中心對(duì)稱。typedefstruct{chars[m];inttop;}sqstack;intstringsymmetry<chars[]>{inti;sqstackstack;stack.top=-1;for<i=0;s[i]!=0;i++>{stack.top++;stack.s[stack.top]=s[i];}for<i=0;s[i]!=0;i++>if<s[i]==stack.s[stack.top]>stack.top=stack.top-1;elsereturn<0>;return<1>;}第五章樹一、填空題設(shè)一棵樹的二元組形式表示為T=〔D,R,其中D={A,B,C,D,E,F,G},R={<A,B>,<A,C>,<A,D>,<B,E>,<C,F>,<C,G>},則該樹的度數(shù)為________,樹的深度為________,葉子結(jié)點(diǎn)的個(gè)數(shù)為_________,分支結(jié)點(diǎn)的個(gè)數(shù)為_________,C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為__________,C結(jié)點(diǎn)的孩子結(jié)點(diǎn)為__________。二叉樹有_________種不同形態(tài)。對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹,當(dāng)它為一棵__________二叉樹時(shí)具有最小高度,其最小高度為_______________。一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為___________；一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)最少有___________個(gè),最多有____________個(gè)。已知一棵二叉樹中度數(shù)為0的結(jié)點(diǎn)個(gè)數(shù)為n0,度數(shù)為1的結(jié)點(diǎn)數(shù)為n1,則該樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為n2,則n0=___________。一棵樹中度數(shù)為1的結(jié)點(diǎn)數(shù)為n1,度數(shù)為2的結(jié)點(diǎn)數(shù)為n2,……,度數(shù)為m的結(jié)點(diǎn)度為nm,則該樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為____________個(gè)。已知一棵二叉樹的順序存儲(chǔ)結(jié)構(gòu)表示為ABCDEF〔其中字符表示空結(jié)點(diǎn),則其前序序列為_____________,中序序列為___________,后序序列為_____________。按照從上到下、從左到右的順序?qū)τ衝個(gè)結(jié)點(diǎn)的完全二叉樹從1開始順序編號(hào),則編號(hào)為i〔i!=1且2i+1<=n的結(jié)點(diǎn)其雙親結(jié)點(diǎn)的編號(hào)為________,其左孩子結(jié)點(diǎn)的編號(hào)為________,其右孩子結(jié)點(diǎn)的編號(hào)為________。對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹,當(dāng)用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí),其二叉鏈表中的指針域的總數(shù)為______個(gè),其中______個(gè)用于鏈接孩子結(jié)點(diǎn),_______個(gè)為空指針域。設(shè)某棵二叉樹的前序遍歷序列為ABCDEFGH,中序遍歷序列為BCAEDGHF,則該二叉樹的后序遍歷序列為____________________。如果按中序遍歷某二叉樹的遍歷序列為abc,問(wèn)有________種不同的二叉樹可以得到這一遍歷序列。設(shè)哈夫曼樹中有n個(gè)葉子結(jié)點(diǎn),則該哈夫曼樹中總共有___________結(jié)點(diǎn)。二、選擇題1．假設(shè)一棵二叉樹中,雙分支結(jié)點(diǎn)數(shù)為15個(gè),單分支結(jié)點(diǎn)數(shù)為30個(gè),則終端結(jié)點(diǎn)數(shù)為〔。①15 ②16 ③17 ④472．假設(shè)一棵三叉樹的結(jié)點(diǎn)數(shù)為50,則它的最小高度為〔。①3 ②4 ③5 ④63．一棵二叉樹上第5層的結(jié)點(diǎn)數(shù)最多為〔。①15 ②16 ③8 ④324．將完全二叉樹中的所有結(jié)點(diǎn)按照從上到下、從左到右的順序存放在n個(gè)連續(xù)的存儲(chǔ)單元中,若結(jié)點(diǎn)R[i]有左孩子,則左孩子的結(jié)點(diǎn)是〔。①R[2i+1]②R[2i] ③R[i/2] ④R[2i-1]5.設(shè)一棵具有n個(gè)結(jié)點(diǎn)的滿二叉樹有m個(gè)葉子結(jié)點(diǎn)和k個(gè)分枝結(jié)點(diǎn),則下列等成立的是〔。①n=2k+1 ②m+k=2n③n=2m+1④n=2k-16．設(shè)森林F中有三棵樹,第一、第二和第三棵樹的結(jié)點(diǎn)樹分別為m1、m2和m3,則與森林F對(duì)應(yīng)的二叉樹的根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是〔。①m1②m1+m2③m3④m2+m37．設(shè)A、B為一棵二叉樹上的兩個(gè)結(jié)點(diǎn),中序遍歷時(shí)A在B前的條件是〔。①A在B的右方 ②A在B的左方 ③A是B的祖先 ④A是B的子孫8．一棵具有k層的滿三叉樹中共有〔個(gè)結(jié)點(diǎn)數(shù)。①<3k-1>/2②3k-1③<3k-1>/3④3k9．設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn),則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少有〔個(gè)。①2h②2h-1③2h+1④h+110．若采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)深度為h且有n個(gè)結(jié)點(diǎn)的二叉樹,則最多將浪費(fèi)〔個(gè)存儲(chǔ)單元。①0 ②2h-1-n③2h+1-n④2h-n11．已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的前序遍歷序列是〔。①acbed②decab③deabc④cedba12．在一棵非空二叉樹的中序遍歷序列中,根結(jié)點(diǎn)的右邊〔。①只有右子樹上的所有結(jié)點(diǎn) ②只有右子樹上的部分結(jié)點(diǎn)③只有左子樹上的部分結(jié)點(diǎn) ④只有左子樹上的所有結(jié)點(diǎn)三、應(yīng)用題設(shè)一棵樹的二元組形式表示為{<A,B>,<A,C>,<A,D>,<B,E>,<C,F>,<C,G>},要求用孩子兄弟表示法表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化為對(duì)應(yīng)的二叉樹。根據(jù)5個(gè)葉子結(jié)點(diǎn)的權(quán)值集合{3、6、9、2、5}構(gòu)成一棵哈夫曼樹并計(jì)算這棵哈夫曼樹的帶權(quán)路徑長(zhǎng)度。四、算法設(shè)計(jì)題typedefstructnode{intdata;structnode*lchild;structnode*rchild;}bitree;設(shè)計(jì)復(fù)制一棵二叉樹的算法。設(shè)計(jì)判斷兩個(gè)二叉樹是否等價(jià)的算法。設(shè)計(jì)層次遍歷二叉樹中所有結(jié)點(diǎn)的算法。設(shè)計(jì)統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)總數(shù)的算法。設(shè)計(jì)交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。建立一棵二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的算法。第五章參考答案一、填空題3,3,4,4,A,F和G5完全,2k-1,2k-1,2k-1n0=1+n2n0=1+n2+2n3+…+<m-1>nm分析：設(shè)m叉樹中的結(jié)點(diǎn)總數(shù)為n,則下面兩個(gè)等式同時(shí)成立,經(jīng)兩式相減得到等式n0=1+n2+2n3+…+<m-1>nm。n=n0+n1+n2+n3+…+nm〔如果從結(jié)點(diǎn)數(shù)的角度考慮n-1=n1+2n2+3n3+…+mnm〔如果從分支數(shù)的角度考慮ABDECF,DBEACF,DEBFCAi/2,2i,2i+12n,n-1,n+1分析：用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)時(shí),第個(gè)結(jié)點(diǎn)有兩個(gè)指針域,則有n個(gè)結(jié)點(diǎn)的二叉鏈表中共有2n個(gè)指針域,其中有n-1個(gè)指針域指向非根結(jié)點(diǎn),因此整個(gè)二叉鏈表中還有n+1個(gè)指針域。線索二叉樹的線索就是利用這多余的n+1個(gè)指針域來(lái)作為線索而方便查找某個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。CBEHGFDA分析：由前序遍歷序列可知,根結(jié)點(diǎn)最先被訪問(wèn),這就可以確定A是根結(jié)點(diǎn),而又由中序遍歷序列可知二叉樹的根結(jié)點(diǎn)是其左右子樹的分隔點(diǎn),從而可以確定以A為根結(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)為BC,右子樹上的結(jié)點(diǎn)為DEFGH。以此類推,直到將這棵二叉樹構(gòu)造出來(lái)。實(shí)際上,只要給定某棵二叉樹的前序遍歷序列和中序遍歷序列〔或中序遍歷序列和后序遍歷序列可以唯一地確定這棵二叉樹。但如果給定的是某棵二叉樹的前序遍歷序列和后序遍歷序列則不能唯一確定這棵二叉樹。5分析：三個(gè)結(jié)點(diǎn)的二叉樹形狀共有5種,如果再考慮到三個(gè)結(jié)點(diǎn)的排列順序則每種情況又分為6種子情況,但中序遍歷序列是abc的只能是1種子情況。因此中序遍歷序列是abc的共有5種二叉樹可以得到這一結(jié)果。2n-1由構(gòu)造哈夫曼樹的過(guò)程可知,哈夫曼樹中不存在度數(shù)為1的結(jié)點(diǎn),只有度數(shù)為0的結(jié)點(diǎn)和度數(shù)為2的結(jié)點(diǎn)。二、選擇題<2><3>用歸納法可以證明三叉樹中的第i層上最多有3i-1個(gè)結(jié)點(diǎn)。本題中的三叉樹的結(jié)點(diǎn)樹為50個(gè),因此該三叉樹的最小高度為5。<2><2><1>分析：根據(jù)滿二叉樹的定義可知滿二叉樹中沒有度數(shù)為1的結(jié)點(diǎn),因此有等式n=m+k和等式m=k+1成立,從而得到等式n=2k+1和等式n=2m-1成立。<4>森林轉(zhuǎn)化為二叉樹的規(guī)則是首先將森林中的各棵樹的根結(jié)點(diǎn)看成是兄弟結(jié)點(diǎn),然后再按照樹轉(zhuǎn)化為二叉樹的規(guī)則進(jìn)行轉(zhuǎn)化。因此,本題中經(jīng)轉(zhuǎn)化而得到的二叉樹的根結(jié)點(diǎn)的右子樹上結(jié)點(diǎn)數(shù)等于第二、第三棵樹上的結(jié)點(diǎn)數(shù)之和。<2>設(shè)結(jié)點(diǎn)C為結(jié)點(diǎn)A和B的最近的公共祖先,則根據(jù)中序遍歷時(shí)A在B的之前知：如果C就是A,則B一定在A的右子樹上,如果C就是B,則A一定在B的左子樹上,如果C不是A也不是B,則A一定在C的左子樹上而B一定在C的右子樹上。<1>分析：用歸納法可以證明三叉樹中的第i層上最多有3i-1個(gè)結(jié)點(diǎn),因此根據(jù)等比數(shù)列求和分式可知具有k層的三叉樹最多有<3k-1>/2個(gè)結(jié)點(diǎn)。<3><2>分析：順序存儲(chǔ)結(jié)構(gòu)比較適合于完全二叉樹,如果是一般二叉樹則要將其擴(kuò)充成完全二叉樹以后才能夠用順序存儲(chǔ)結(jié)構(gòu)。深度為h的二叉樹擴(kuò)充成完全二叉樹最多需要2h-1個(gè)存儲(chǔ)單元,而實(shí)際利用的只是其中的n個(gè)存儲(chǔ)單元,因此最多浪費(fèi)2h-1-n個(gè)存儲(chǔ)單元。<4><1>三、應(yīng)用題略哈夫曼樹略,帶樹路徑等于55四、算法設(shè)計(jì)題設(shè)計(jì)復(fù)制一棵二叉樹的算法。voidcopybitree<bitree*bt1,bitree*&bt2>{if<bt1==0>{bt2=0;return;}bt2=<bitree*>malloc<sizeof<bitree>>;bt2->data=bt1->data;copybitree<bt1->lchild,bt2->lchild>;copybitree<bt1->rchild,bt2->rchild>;}設(shè)計(jì)判斷兩個(gè)二叉樹是否等價(jià)的算法。intjudgebitree<bitree*bt1,bitree*bt2>{if<bt1==0&&bt2==0>return<1>;elseif<bt1==0&&bt2!=0||bt1!=0&&bt2==0||bt1->data!=bt2->data>return<0>;elsereturn<judgebitree<bt1->lchild,bt2->lchild>*judgebitree<bt1->rchild,bt2->rchild>>;}設(shè)計(jì)層次遍歷二叉樹中所有結(jié)點(diǎn)的算法。分析：本題的算法思想是設(shè)置一個(gè)順序循環(huán)隊(duì)列,隊(duì)列中的單元用來(lái)存儲(chǔ)二叉樹上結(jié)點(diǎn)的指針。先將二叉樹上的根指針入隊(duì)列,在隊(duì)列非空的情況下取出隊(duì)頭元素訪問(wèn)所指向的結(jié)點(diǎn)且將該結(jié)點(diǎn)中的左右指針域入隊(duì)列。voidlevelorder<bitree*bt>{struct{intfront,rear;bitree*q[m];}queue;bitree*p=bt;queue.rear=queue.front=0;if<bt!=0>{queue.rear=<queue.rear+1>%m;queue.q[queue.rear]=p;}while<!<queue.front==queue.rear>>{queue.front=<queue.front+1>%m;p=queue.q[queue.front];visitnode<p>;if<p->lchild!=0>{queue.rear=<queue.rear+1>%m;queue.q[queue.rear]=p->lchild;};if<p->rchild!=0>{queue.rear=<queue.rear+1>%m;queue.q[queue.rear]=p->rchild;};}}設(shè)計(jì)統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)總數(shù)的算法。voidcountleaf<bitree*bt,int&count>{if<bt==0>return;if<bt->lchild==0&&bt->rchild==0>count++;if<bt->lchild!=0>countleaf<bt->lchild,count>;if<bt->rchild!=0>countleaf<bt->rchild,count>;}設(shè)計(jì)交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。voidswapbitree<bitree*bt>{bitree*p;if<bt==0>return;swapbitree<bt->lchild>;swapbitree<bt->rchild>;p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}建立一棵二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的算法。voidcreatebitree<threadbitree*&bt>{charch;scanf<"%c",&ch>;if<ch=='#'>{bt=0;return;}bt=<threadbitree*>malloc<sizeof<threadbitree>>;bt->data=ch;createbitree<bt->lchild>;createbitree<bt->rchild>;}提示：遍歷是二叉樹各種操作的基礎(chǔ),可在在遍歷過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行各種操作,如求已知結(jié)點(diǎn)的孩子結(jié)點(diǎn)、判定結(jié)點(diǎn)所在的層次、求二叉樹的深度、統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)總數(shù)、復(fù)制二叉樹等操作,也可以在遍歷過(guò)程中生成結(jié)點(diǎn),如建立二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第六章圖一、填空題設(shè)無(wú)向圖G中的頂點(diǎn)數(shù)為n,則圖G中最少有________條邊,最多有________條邊；設(shè)有向圖G中的頂點(diǎn)數(shù)為n,則圖G中最少有________條邊,最多有________條邊。設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)和e條邊,用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)時(shí),則訪問(wèn)任何一個(gè)頂點(diǎn)的所有鄰接點(diǎn)的時(shí)間復(fù)雜度為__________；用鄰接表作為存儲(chǔ)結(jié)構(gòu)時(shí),則訪問(wèn)任何一個(gè)頂點(diǎn)的所有鄰接點(diǎn)的平均時(shí)間復(fù)雜度為__________。設(shè)有向圖G有n個(gè)頂點(diǎn),采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu),則該矩陣中含有_______個(gè)數(shù)組元素。設(shè)無(wú)向圖G中有e條邊且所有頂點(diǎn)的度數(shù)之和為m,則m與e之間的關(guān)系為_____。設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)和e條邊,則用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先遍歷或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為_________；用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先遍歷或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為_________；圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜度為____________。設(shè)有向圖G有n個(gè)頂點(diǎn)和e條邊且用鄰接表作為存儲(chǔ)結(jié)構(gòu),則進(jìn)行拓補(bǔ)排序時(shí)的時(shí)間復(fù)雜度為__________。在一個(gè)有向圖G中若有弧<i,j>、<j,k>和<i,k>,則在圖G的拓?fù)湫蛄兄?頂點(diǎn)i,j,k的相對(duì)次序?yàn)開___________。在有向圖的鄰接矩陣中,第i行上非零元素個(gè)數(shù)之和等于頂點(diǎn)i的_________,第i列上非零元素個(gè)數(shù)之和等于頂點(diǎn)i的_________。設(shè)有向圖G的鄰接表中第1條單鏈表中有結(jié)點(diǎn)2、5、4,第2條單鏈表中有結(jié)點(diǎn)3、5,第3條單鏈表中有結(jié)點(diǎn)5,第4條單鏈表為空,第5條單鏈表中有結(jié)點(diǎn)4、3,則從該圖中頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷序列為__________________,廣度優(yōu)先遍歷序列為____________________。設(shè)用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu),則用普里姆算法求連通圖的最小生成樹的時(shí)間復(fù)雜度為_____________。二、選擇題1．無(wú)向圖的深度優(yōu)先遍歷算法類似于二叉樹的〔。①中序遍歷②先序遍歷③后序遍歷 ④層次遍歷2．圖的廣度優(yōu)先遍歷算法類似于二叉樹的〔。①中序遍歷②先序遍歷 ③后序遍歷 ④層次遍歷3．設(shè)無(wú)向圖G的二元組形式表示為G=〔D,R,其中D={a,b,c,d,e,f},R={<a,b>,<a,e>,<a,c>,<b,e>,<e,d>,<d,f>,<f,c>},從頂點(diǎn)a出發(fā)按深度優(yōu)先遍歷該圖,則可以得到的一種頂點(diǎn)序列為〔。①abecdf ②acfebd ③aebcfd ④aedfcb4．設(shè)無(wú)向圖G中有e條邊且采用鄰接表作為存儲(chǔ)結(jié)構(gòu),則鄰接表中有〔表結(jié)點(diǎn)。①e/2②e ③2e④n+e5．連通具有n個(gè)頂點(diǎn)的無(wú)向圖至少需要〔條邊。①n②n+1 ③n/2④n-16．已知有向圖G的二元組形式表示為G=〔D,R,其中D={1,2,3,4,5,6},R={<1,2>,<2,3>,<1,4>,<4,5>,<4,6>,<6,5>,<5,3>},,則由圖G1得到的一種拓?fù)渑判蛐蛄袨椤?。①v1,v4,v6,v2,v5,v3②v1,v2,v3,v4,v5,v6③v1,v4,v2,v3,v6,v5④v1,v2,v4,v6,v3,v57．設(shè)強(qiáng)連通圖G有n個(gè)頂點(diǎn),則該圖至少有〔條邊。①n ②n+1③n<n-1>④n-18．關(guān)鍵路徑是AOE網(wǎng)中的〔。①?gòu)脑袋c(diǎn)到匯點(diǎn)的最長(zhǎng)路徑②最長(zhǎng)的回路③從源點(diǎn)到匯點(diǎn)的最短路徑 ④最短的回路三、已知無(wú)向圖G的鄰接矩陣,按要求完成下列各題。給出無(wú)向圖G中各頂點(diǎn)的度數(shù)；給出無(wú)向圖G的鄰接表；分別給出應(yīng)用Kruskal和Prim算法構(gòu)造最小生成樹的過(guò)程。四、算法設(shè)計(jì)題設(shè)計(jì)圖的深度優(yōu)先遍歷算法〔用鄰接表作為存儲(chǔ)結(jié)構(gòu)。設(shè)計(jì)圖的廣度優(yōu)先遍歷算法〔用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)。設(shè)計(jì)將無(wú)向圖的鄰接矩陣轉(zhuǎn)化成無(wú)向圖的鄰接表的算法。第六章參考答案一、填空題0,n<n-1>/2,0,n<n-1>O<n>,O<e/n>分析：如果在鄰接矩陣中訪問(wèn)無(wú)向圖中第i個(gè)元素的所有鄰接點(diǎn),則需要對(duì)該鄰接矩陣中的第i行或第i列進(jìn)行一趟掃描,因此時(shí)間復(fù)雜度為O<n>。如果在鄰接表中訪問(wèn)無(wú)向圖中第i個(gè)元素的所有鄰接點(diǎn),則需要訪問(wèn)鄰接表中第i條單鏈表,因?yàn)閚條單鏈表的長(zhǎng)度之和為2e,所以每條單鏈表的平均長(zhǎng)度為2e/n,因此平均時(shí)間復(fù)雜度為O<e/n>。n2m=2eO<n2>,O<n+e>,O<n>分析：圖的遍歷過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程,其耗費(fèi)的時(shí)間取決于所采用的存儲(chǔ)結(jié)構(gòu)。當(dāng)用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí),時(shí)間復(fù)雜度為O<n2>,而當(dāng)用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí),時(shí)間復(fù)雜度為O<n+e>。在圖的遍歷過(guò)程中為了避免同一個(gè)頂點(diǎn)被訪問(wèn)多次,在遍歷圖的過(guò)程中必須記錄已被訪問(wèn)過(guò)的頂點(diǎn),因此需要設(shè)置一個(gè)長(zhǎng)度為n的標(biāo)志數(shù)組用來(lái)記錄哪些已被訪問(wèn)過(guò)。O<n+e>分析：初始化棧的時(shí)間復(fù)雜度為O<n>；建立求各頂點(diǎn)入度并將入度為0的頂點(diǎn)入棧的時(shí)間復(fù)雜度為O<n+e>；在拓?fù)渑判蜻^(guò)程中每一個(gè)頂點(diǎn)進(jìn)一次棧和出一次棧,入度減1的操作在循環(huán)語(yǔ)句中共執(zhí)行e次,總的時(shí)間復(fù)雜度為O<n+e>。<i,j,k>出度,入度1、2、3、5、4,1、2、5、4、3分析：圖的深度優(yōu)先遍歷是一個(gè)遞歸的過(guò)程,當(dāng)訪問(wèn)過(guò)某個(gè)頂點(diǎn)之后要在其鄰接點(diǎn)中查找未被訪問(wèn)過(guò)的頂點(diǎn)進(jìn)行深度優(yōu)先遍歷,否則要依次回退到最近被訪問(wèn)過(guò)的尚有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)并從該頂點(diǎn)出度進(jìn)行深度優(yōu)先遍歷。圖的廣度遍歷是當(dāng)訪問(wèn)過(guò)某個(gè)頂點(diǎn)之后訪問(wèn)其未被訪問(wèn)過(guò)的鄰接點(diǎn),然后再依次從這些頂點(diǎn)出度分別訪問(wèn)它們未被訪問(wèn)過(guò)的鄰接點(diǎn)。O<n2>分析：利用普里姆算法求最小生成樹的時(shí)間主要耗費(fèi)在一個(gè)雙重循環(huán)語(yǔ)句中,外循環(huán)執(zhí)行n-1次,而內(nèi)循環(huán)的功能是求最小值和重新選擇具有最小代價(jià)的邊各執(zhí)行n次,因此總的時(shí)間復(fù)雜度為O<n2>。二、選擇題<2><4><4><3><4><1><1><1>三、應(yīng)用題TD<1>=TD<2>=TD<3>=TD<4>=3,TD<5>=4v1->2->4->5；v2->1->3->5；v3->2->4->5；v4->1->3->5；v5->1->2->3->4Prim算法：<1,2>,<2,3>,<2,5>,<5,4>Kruskal算法：<2,5>,<2,3>,<2,1>,<5,4>四、算法設(shè)計(jì)題設(shè)計(jì)圖的深度優(yōu)先遍歷算法。intvisited[m];typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidcreateadjlist<glinkheadnodeg[]>{inti,j,k;glinklistnode*p;for<i=0;i<n;i++>{g[i].vertexinfo=i;g[i].firstarc=0;}for<k=0;k<e;k++>{scanf<"%d,%d",&i,&j>;p=<glinklistnode*>malloc<sizeof<glinklistnode>>;p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=<glinklistnode*>malloc<sizeof<glinklistnode>>;p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}}voiddfs<glinkheadnodeg[],intv0>{glinklistnode*p;printf<"%d\t",v0>;visited[v0]=1;p=g[v0].firstarc;while<p!=0>{if<visited[p->adjvertex]==0>dfs<g,p->adjvertex>;p=p->nextarc;}}設(shè)計(jì)圖的廣度優(yōu)先遍歷算法〔用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)。intvisited[m];typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;voidcreateadjmatrix<gadjmatrix&g>{inti,j,k;for<i=0;i<n;i++>g.vertex[i]=i;for<i=0;i<n;i++>for<j=0;j<n;j++>g.edge[i][j]=0;for<k=0;k<e;k++>{scanf<"%d,%d",&i,&j>;g.edge[i][j]=g.edge[j][i]=1;}}voidbfs<gadjmatrixg,intv0>{struct{intfront;intrear;intq[m];}queue;inti,j;printf<"%d\t",v0>;visited[v0]=1;queue.front=queue.rear=0;queue.rear=<queue.rear+1>%m;queue.q[queue.rear]=v0;while<queue.front!=queue.rear>{queue.front=<queue.front+1>%m;i=queue.q[queue.front];for<j=0;j<n;j++>if<g.edge[i][j]==1&&visited[j]==0>{printf<"%d\t",j>;visited[j]=1;queue.rear=<queue.rear+1>%m;queue.q[queue.rear]=j;}}}設(shè)計(jì)將無(wú)向圖的鄰接矩陣轉(zhuǎn)化成無(wú)向圖的鄰接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist<gadjmatrixg1[],glinkheadnodeg2[]>{inti,j;glinklistnode*p;for<i=0;i<=n-1;i++>g2[i].firstarc=0;for<i=0;i<=n-1;i++>for<j=0;j<=n-1;j++>if<g1.edge[i][j]==1>{p=<glinklistnode*>malloc<sizeof<glinklistnode>>;p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=<glinklistnode*>malloc<sizeof<glinklistnode>>;p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}}第七章排序一、填空題對(duì)一組記錄關(guān)鍵字〔50,40,95,20,15,70,60,45,80進(jìn)行直接插入排序時(shí),當(dāng)把第7個(gè)記錄60插入到有序表時(shí),從后向前為尋找插入位置需要比較_______次。在對(duì)一組記錄關(guān)鍵字〔50,40,95,20,15,70,60,45,80進(jìn)行希爾排序時(shí),假定取d1=4,d2=2,則第二趟排序后的結(jié)果為____________________________。在對(duì)一組記錄關(guān)鍵字〔50,40,95,20,80,70,60,45,15進(jìn)行冒泡排序時(shí),第一趟需要進(jìn)行相鄰記錄的交換次數(shù)為___________,在整個(gè)排序過(guò)程中需要進(jìn)行__________趟才能完成。在對(duì)一組記錄關(guān)鍵字〔50,40,95,20,15,70,60,45,80進(jìn)行快速排序時(shí),若以第一個(gè)關(guān)鍵字50作為基準(zhǔn)記錄,則第一趟排序后的結(jié)果為___________________。在對(duì)一組記錄關(guān)鍵字〔50,40,95,20,15,70,60,45,80進(jìn)行簡(jiǎn)單選擇排序時(shí),第4趟排序后的結(jié)果為_________________________。在直接插入和簡(jiǎn)單選擇排序中,若初始記錄關(guān)鍵字基本有序,則選用___________排序,若初始記錄關(guān)鍵字基本反序,則選用____________排序。在對(duì)一組記錄關(guān)鍵字〔50,40,95,20,15,70,60,45,80進(jìn)行堆排序時(shí),則根據(jù)這組記錄關(guān)鍵字構(gòu)成的初始堆為_________________________。在堆排序過(guò)程中,由n個(gè)待排序的記錄關(guān)鍵字建成初始堆需要進(jìn)行___________次篩選；由初始堆到堆排序結(jié)束需要進(jìn)行___________次篩選,每次篩選時(shí)對(duì)記錄關(guān)鍵字進(jìn)行比較的數(shù)量級(jí)為__________；堆排序算法的時(shí)間復(fù)雜度為__________。在堆排序和快速排序中,若原始記錄關(guān)鍵字接近正序或反序,則最好選用________排序,若原始記錄關(guān)鍵字無(wú)序,則最好選用_________排序。在歸并排序中,若待排序的記錄關(guān)鍵字個(gè)數(shù)為20,則需要進(jìn)行__________趟歸并,在第三趟歸并中是把長(zhǎng)度為__________的有序表歸并成長(zhǎng)度為__________的有序表。在堆排序、快速排序和歸并排序中,若從節(jié)省存儲(chǔ)空間的角度考慮