2014考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)專項(xiàng)精講課程講義第二部分

(C/C++語言版(C/C++語言版Data基礎(chǔ)與理論環(huán)節(jié)——第一章第三章棧第六章圖及應(yīng)用第七章查找基礎(chǔ)基礎(chǔ)與理論環(huán)節(jié)——概念和算法思路解第一章緒基本概念和抽象數(shù)據(jù)類算法和算法A.效率B.復(fù)雜性C.現(xiàn)實(shí)性D問題的規(guī) B.待處理數(shù)據(jù)的初3.計(jì)算機(jī)算法指的是(1),它必須具備（2）A.計(jì)算方 B.排序方C.解決問題的步驟序列DA.A.程序B.問題求解步驟的描述C.要滿足五個(gè)基本特性D.A和從邏輯上可 分為() C.線性結(jié)構(gòu)非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu) 結(jié)構(gòu)無關(guān)的術(shù)語是()。 B.鏈表C.哈希 ()。FORi:=1TOnDOFORj:=1TOnDO8.FORi:=n-1DOWNTO1DOFORj:=1TOiDO8.FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFTHENA[j]與A[j+1]n為正整數(shù)，則最后一行的語句頻度在情況下是()。 系。()有關(guān)。()健壯的算法不會(huì) 的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)(66算法可以用不同語言描述，如果用C言等高級語言來描述，則算法實(shí)際上就是程序。()7.程序一定是算法。8.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí) 形式。( 的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。10.在順序 關(guān)系。()中 間儲 效率高。() 結(jié)構(gòu)的獨(dú)立。() 結(jié)構(gòu)。()三、填 包 的表示 的表示對于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有.（3）,（4）四種數(shù)據(jù)的邏輯結(jié)構(gòu)是 .個(gè).個(gè)4.在計(jì)算機(jī)4.在計(jì)算機(jī) 稱5.抽象數(shù)據(jù)類型的定義僅取決于它的一組 ,而 6中評價(jià)算法的兩個(gè)重要指標(biāo) ,而與(2),無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的(3),不變，都不影響其外部使用。7．在7．在下面的程序段中，對ｘ的賦值語句的頻度 （表示為n的函數(shù) i：＝１TOnDO j：＝１TOiDOFORk：＝1TOj8.計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s的執(zhí)行次數(shù) 8.8.計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s的執(zhí)行次數(shù) 答案：(n+3)(n-9.n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,,n!,n2+logn9.n,9.n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,,n!,n2+lognlogn,n1/2+logn,n,nlogn,n2+logn，n3,n-n3+7n5,2n/2,(3/2)n,n!,基礎(chǔ)與理論環(huán)節(jié)——第二章第三章棧第六章圖及應(yīng)用第七章查找—選擇—選擇3．線性表是具有n個(gè)A．表元 B．字）的有限序列（n>0）C．?dāng)?shù)據(jù)元 D．?dāng)?shù) E．信息4若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）省時(shí)間。A.順序結(jié)點(diǎn)的雙循環(huán)鏈 C．雙鏈D．僅有尾指針的單循環(huán)鏈6．設(shè)—個(gè)鏈表最常用的操作是入結(jié)點(diǎn)和刪除尾點(diǎn)，則選用 )最節(jié)省時(shí)間A.單鏈 B.單循環(huán)鏈C.帶尾指針的單循環(huán)鏈 結(jié)點(diǎn)的雙循環(huán)鏈7．7．若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用（ ）方式最節(jié)省運(yùn)算時(shí)間。A．單鏈 B．雙鏈C．單循環(huán)鏈 結(jié)點(diǎn)的雙循環(huán)鏈8.靜態(tài)鏈表中指針表示的是 A．內(nèi)存地 下面的敘述不正確的是 線性表在鏈 時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正線性表在鏈?zhǔn)綍r(shí)，查找第i個(gè)元素的時(shí)間同i的值無線性表在順序時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正線性表在順序時(shí)，查找第i個(gè)元素的時(shí)間同i的值無voidreverse(pointer{pointerp=h->next;h->next=NULL; {q=p;p=p->next;q->next=h->next; }}voidreverse(pointer{pointerp=h->next;h->next=NULL; {q=p;p=p->next;q->next=h->next; }}p!=null 31.下面是用c31.下面是用c語言編寫的對不 voidreverse（linklist{{ q->next=p；p=q；(2)} }voidreverse（linklist{p=null；q=L；{ >next=p；p=q；(2)} }L=L->next 3636typedefstruct{intdata;structnodevoidInsertsort(link {r=L;q=L- &&q->data<=p-{r=q;q=q-u=p->next; ; ;}}voidInsertsort(link {r=L;q=L- &&q->data<=p-{r=q;q=q-u=p->next; ; ;}}(1)L->next=null(2)p!=null(3)q!=null(4)p->next=r->next(5)r->next=p基礎(chǔ)與理論環(huán)節(jié)——基礎(chǔ)與理論環(huán)節(jié)——第六章圖及應(yīng)用第七章查找—選擇題一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第 B.n- C. D.n-4.若一個(gè)棧的輸入序列為1,2,3,,n，輸出序列的第一個(gè)元素是i，則A.i-j- B.i-）Cj-i+1D若已知一個(gè)棧的入棧序列是1,2,3,若已知一個(gè)棧的入棧序列是1,2,3,,n，其輸出序列為p1,p2,p3，，pN,若pN是n，則pi是( A. B.n- Cn- D有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪一個(gè)不是合法 A.54361 B.45312C.34652 D.234157.設(shè)棧的輸入序列是1，2，3，4,則（）A.1，2，4，3，B.C.1，4，3，2，D.4，3，1，2，E.8.一個(gè)棧的輸入序列為12345，則下列序列中不可能是棧的輸出序 A.2341C.2314B.5413D.15439.設(shè)一個(gè)棧的輸入序列是1，2，3，4，5,則下列序列中，是棧的合法 A.5123C.4312B.4513D.321510.10.某堆棧的輸入序列為a,b，c，d,下面的四個(gè)序列中，不可能是它 A. B.b,C.c,d，b, D.d,11.設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作,則 A．fedcbaB.bcafedC.dcefbaD.1 表達(dá)式exp的一個(gè)單詞 表達(dá)式exp的一個(gè)單詞③x是運(yùn)算符。若x‘）’，‘（’為止。。835+562/-*基礎(chǔ)基礎(chǔ)與理論環(huán)節(jié)——基本概念和算法思路第一章第三章棧第四章第五章樹與二叉第六章及應(yīng)用第七章查找第八章序第九章1用不 指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)()。A．僅修改隊(duì)頭指 B僅修改隊(duì)尾指C隊(duì)頭、隊(duì)尾指針都要修 D隊(duì)頭,隊(duì)尾指針都可能要修2遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（。A． 數(shù) C． D線性3假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。A．(rear-D．(rear-循環(huán)隊(duì)循環(huán)隊(duì) 在數(shù)組A[0m]中，則入隊(duì)時(shí)的操作為（）A Brear=(rear+1)mod(m-Crear=(rear+1)mod D若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rr和font的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，ar和on的值分別為多少？A1和 B2和 C4和 D5和已知輸入序列為abcd（）AdacbBcadbC DbdacE得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是()。A B C D件是（）。A(rear+1)MOD B D(rear-l)MOD9棧和隊(duì)列的共同點(diǎn)是（）A都是先進(jìn)先 B都是先進(jìn)后C只允許在端點(diǎn)處插入和刪除元 D沒有共同棧的特點(diǎn)是（）棧的特點(diǎn)是（）,隊(duì)列的特點(diǎn)是（）,棧和隊(duì)列都是（）。若進(jìn)棧序列為1,2,3,4則（④）不可能是一個(gè)出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為1,2,3,4則（⑤）是一個(gè)出①,②:A先進(jìn)先 B后進(jìn)先 C進(jìn)優(yōu)于出D出優(yōu)于③:A順序的線性結(jié)構(gòu)B鏈?zhǔn)降木€性結(jié)C限制存取點(diǎn)的線性結(jié)構(gòu)D④,⑤:A3,2,1,4B3,2,4,1C4,2,3,1D4,3,2,1F1,2,3,4G棧和隊(duì)都是（A．順序的線性結(jié) B鏈 的非線性結(jié)C限制存取點(diǎn)的線性結(jié)構(gòu)D設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素1，2，3，45和6依次通過棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2，4，3651則棧S的容量至少應(yīng)該是。 B C D用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（）鏈 B．鏈 C．鏈進(jìn)后出型結(jié)構(gòu)。（）通常使用隊(duì)列來處理函數(shù)或過程的調(diào)用。（隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。（循環(huán)隊(duì)列通常用指針來實(shí)現(xiàn)隊(duì)列的頭尾相接。（循環(huán)隊(duì)列也存在空間溢出問題。（隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。（棧和隊(duì)列 方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（三填空題循環(huán)隊(duì)列的引入，目的是為了克 隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是 。已知鏈隊(duì)列的頭尾指針分別是f和r，則將值x 區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們 6．設(shè)循環(huán)隊(duì)列用數(shù)組6．設(shè)循環(huán)隊(duì)列用數(shù)組A[1M]表示，隊(duì)首、隊(duì)尾指針分別是FRONT和 7設(shè)循環(huán)隊(duì)列存放在向量sqdata[0:M]中，則隊(duì)頭指針sqfront在循環(huán)意義 隊(duì)滿和隊(duì)空（設(shè)隊(duì)尾指針sqrear）,則隊(duì)滿的條件為 表達(dá)式求值 應(yīng)用的一個(gè)典型例子循環(huán)隊(duì)列用數(shù)組A[0m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是 設(shè)Q[0N-1]為循環(huán)隊(duì)列，其頭、尾指針分別為P和R，則隊(duì)Q中當(dāng)前 基礎(chǔ)與理論環(huán)節(jié)——基本概念和算法思路解第一章第三章棧第四章樹與二叉樹第六章圖及應(yīng)用第七章查找第八章序第九章2已知一棵二叉樹的前序遍歷為ABECDFGHIJ33(1)對此二叉樹進(jìn)行后序后繼線索化；(2)將此二叉樹變換為森林(3)用后根序遍歷該森林，；寫出遍歷后的結(jié)點(diǎn)序5、以數(shù)據(jù)集{3,4,5,8,12,18,20,30}5、以數(shù)據(jù)集{3,4,5,8,12,18,20,30}基礎(chǔ)與理論環(huán)節(jié)——第三章棧第六章圖及應(yīng)用第七章查找11．圖中有關(guān)路徑的定義是）2．設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）A．n- B．n(n- C． 3．—個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為（） B．n C．n+1 4．要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（）條邊。 5．n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目 Ｂ．n（n＋１））6．—個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（）個(gè)連通分量，最多有（）個(gè)連 C．n- 7．在—個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（7．在—個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（） 點(diǎn)，則輸出的頂點(diǎn)序列是()。A．逆拓?fù)溆?B．拓?fù)溆?C．無序9．下列哪—種圖的鄰接矩陣是對稱矩陣？（A．有向 B．無向 C．AOV D．AOE1．給出圖畫出G的鄰接表表示圖（2（2）以頂點(diǎn)①為根，畫出G的廣度優(yōu)先生成 2．已知一個(gè)無向圖如下圖所示，要求分別用Pi和Kuskl算法生成最小樹（假設(shè)以①為起點(diǎn)，試畫出構(gòu)造過程）假設(shè)開始頂點(diǎn)就選為頂點(diǎn)1，故首先有假設(shè)開始頂點(diǎn)就選為頂點(diǎn)1，故首先有66 15125 1255(d)u={1,3,6}134264(c)u={1,3}要求要求分別用Prim算法生成最小樹（假設(shè)以①為起點(diǎn)要求分別用Kruskal算法生成最小樹（假設(shè)以①為起點(diǎn)3．用最短路徑算法，求如下圖中3．用最短路徑算法，求如下圖中a到z4．請寫出應(yīng)填入下列敘述中（4．請寫出應(yīng)填入下列敘述中（） 完成此工程的關(guān)鍵路徑是（1）求出所有的最早開始時(shí)間ve[j]=若j=0（即vj為源點(diǎn)Maxve[idur(i,j|vviVe[0]=0(表示0最早發(fā)生時(shí)間是0)Ve[1]=Max{Ve[0]+dur(<0,1>)}=6(表示1最早發(fā)生時(shí)間是6)Ve[2]=Max{Ve[0]+dur(<0,2>)}=4(表示2最早發(fā)生時(shí)間是4)(表示（2（2）求出所 的最遲開始時(shí)vl[j]=ve(n-Min{vl[k]-dur(j,k)|<v,v>為網(wǎng)中jVl[8]=18(表示 Vl[7]=Min{Vl[8]-dur(<7,8>)}=18-4=14(表示 Vl[6]=Min{Vl[8]-dur(<6,8>)}=18-2=16(表示 Vl[5]=Min{Vl[7]-dur(<5,7>)}=14-4=10(表示 Vl[2]=Min{Vl[4]-dur(<2,4>)}=7-Vl[1]=Min{Vl[4]-dur(<1,4>)}=7-Vl[0]=Min{Vl[1]-dur(<0,1>),Vl[2]-dur(<0,1>,Vl[3]-dur(<0,3)}=Min{6-6,6-a<0,1>e[1]=Ve[0]=0a<0,2>e[2]=Ve[0]=0i=0a<0,3>e[3]=Ve[0]=0a<1,4>e[4]=Ve[1]=6i=1a<2,4>e[5]=Ve[2]=4i=2a<3,5>e[6]=Ve[3]=5i=3a<4,6>e[7]=Ve[4]=7i=4a<4,7>e[8]=Ve[4]=7i=4a<5,7>e[9]=Ve[5]=7a<6,8>e[10]=Ve[6]=16i=6a<7,8>e[11]=Ve[7]=14l[k]=Vl[j]-dur(<i,j>)a是活動(dòng)a<0,1>l[1]=Vl[1]-dur(<0,1>)=6-a<0,2>l[2]=Vl[2]-dur(<0,2>)=6-a<0,3>l[3]=Vl[3]-dur(<0,3>)=8-5=3a<1,4>l[4]=Vl[4]-dur(<1,4>)=7-=a<2,4>l[5]=Vl[4]-dur(<2,4>)=7-1=6a<3,5>l[6]=Vl[5]-dur(<3,5>)=10-a<4,6>l[7]=Vl[6]-dur(<4,6>)=16-a<4,7>l[8]=Vl[7]-dur(<4,7>)=14-a<5,7>l[9]=Vl[7]-dur(<5,7>)=14-l[1]-e[1]=0- l[4]-e[4]=6- l[7]-e[7]=7- l[11]-e[11]=14- （4（4）所以a1,a4,a7,a8,a10,a11是關(guān)鍵活動(dòng)，他們組成關(guān)鍵第i 最早開始時(shí)間活動(dòng)活動(dòng)ak的最早開始時(shí)間第i個(gè) 允許最遲開始時(shí)間松弛時(shí)間l[k]-基礎(chǔ)基礎(chǔ)與理論環(huán)節(jié)——基本概念和算法思路第一章第三章棧第四章第六章圖及應(yīng)用第七章查找第八章第九章—選擇題1.若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長度ASL為( )。A．(n- B. C. D.2N個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長度為() B.N/2 C.N D.[（1+N）*N]/2 數(shù)為（（1））,二分法查找只適用于查找順 的有序表，平比較次數(shù)為（（2））N為線性表中結(jié)點(diǎn)數(shù)，且每次查44下面關(guān)于二分查找的敘述正確的是()A表必須有序，表可以順序方式 C表必須B表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型 D表必須有序，5對線性表進(jìn)行二分查找時(shí)，要求線性表必須（A以順序方C 方B以順序方 D 方適用于折半查找的表 方式及元素排列要求為(方 ，元素?zé)o序 方 ，元素有C．順序方 ，元素?zé)o序D．順序方 ，元素有設(shè)哈希表長為14，哈希函數(shù)是Hkyky%1表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測再散列法解決，則放入的位置是() 列表中，至少要進(jìn)行多少次探測？()A．k-1次Bk次Ck+1次Dk（k+1）/2哈希查找中k個(gè)關(guān)鍵字具有同一哈希值，若用線性探測法將這k次探測。A． Bk+1Ck(k+1)/2D10散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以10散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以()A最大概率B最小概率C平均概率D11散列表的地址區(qū)間為0-17,散列函數(shù)為H(K)=Kmod17。采用線性探測法處理，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲（1）元素59存放在散列表中的地址是（）A． B C D（2）存放元素59需要搜索的次數(shù)是（）A． B C D12將個(gè)元素散列 個(gè)單元的哈希表中，則（）產(chǎn)生A一定會(huì)B一定不會(huì)C Hash表的平均查找長度與處理的方法無關(guān)(裝填因子)是散列表的一個(gè)重要參數(shù)，它反映散列表的裝滿7散列法的平均檢索長度不隨表中結(jié)點(diǎn)數(shù)目的增加而增加，而是隨負(fù)載若散列表的負(fù)載因子若散列表的負(fù)載因子α<1在索引順序表中，實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個(gè)數(shù)有關(guān)，而且與每塊中元素個(gè)數(shù)有關(guān)。順序查找法適用 結(jié)構(gòu)為順序或的線性表就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大。順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為 次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為_。 在順序表（81159252630332850）中，用二分（折半）法查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù)為3．在有序表A[112]中，采用二分查找算法查等于A[12]的元素，所比較 4在有序表A[120]中，按二分查找方法進(jìn)行查找，查找長度為5的元素 給定關(guān)鍵字序列給定關(guān)鍵字序列11，78，10，1，3，2，4，21，試分別用順序查找、二分查找、二叉排序樹查找、平衡二叉樹查找、散列查找(用線性探查法和拉鏈法)來實(shí)現(xiàn)查找，試畫出它們的對應(yīng)形式(順序查找的順序表，二分查找的判定樹，二叉排序樹查找的二叉排序樹及平衡二叉樹查找的平衡二叉樹，兩種散列查找的散列表)，并求出每一種查找的成功平均查找長度。散列函數(shù)H()=%1。01234567891324圖7-順序的順序表二分查找的判定樹（中序序列為從小到大排列的有序序列）7-20二分查找的判定樹（中序序列為從小到大排列的有序序列）7-20從圖7-20ASL=(1+2*2+3*4+4)/8=2二叉排序樹（關(guān)鍵字順序已確定，該二叉排序樹應(yīng)唯一）如圖7-21()所示，平衡二叉樹（關(guān)鍵字順序已確定，該平衡二叉樹也應(yīng)該是唯一的），如圖7-21(b)所示，ASL=(1+2*2+3*2+4+5*2)=3ASL=(1+2*2+3*3+4*2)/8=20101234567891324圖7-22線性探查的散列拉鏈法解決的散列表ASL=(1*6+2*2)/8=1.25基礎(chǔ)基礎(chǔ)與理論環(huán)節(jié)——基本概念和算法思路第一章第三章棧第四章第六章圖及應(yīng)用第七章查找第八章第九章—選擇題 C．平均時(shí)間為0（nlogn）2下面給出的四種排序法中 A.插 B.冒泡C.二路歸并 A.堆排序，冒泡排 B.快速排序，堆排C.直接選擇排序，歸并排 D.歸并排序，冒泡排4．穩(wěn)定的排序方法是 4．穩(wěn)定的排序方法是 C．簡單選擇排序和四路歸并排序D．樹形選擇排序和 排AB）B．歸并排序C．冒泡排序）。 則可選擇的排序方法是 ）AC A.起泡排序B.折半插入排序C.簡單選擇排序D.排序E.基數(shù)排序A．快速排序B.直接插入排序C.二路歸并排序D.簡單選擇排序EF（1）其比較次數(shù)與序列初態(tài)無關(guān)的算法是 在初始序列已基本有序（除去n個(gè)元素中的k個(gè)元素后即呈有序k<n）的情下，排序效率最的算法是（ ） A．插 B.選 C.冒 D.快 B.插入排序法 C.快速排序法 D.堆積排序法 B.二分法插入 C.快速排序 D.歸并排序在下列排序算法中,哪一個(gè)算法的時(shí)間復(fù)雜度與初始排序無關(guān)（）A．直接插入排序B.氣泡排 C.快速排 D.直接選擇排1616BCD B.C. ABC對一組數(shù)據(jù)（84，47，25，1521）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1）8447251521（2）1547258421（3）1521258447（4）212547則采用的排序是 )A.選 B.冒 C.快 D.插 ）排序。A.選 B.快 D A．選 B. C.直接插 D.冒A.快速排序B.s排序C.堆排序D下列排序算法中( )排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位上。A.選 B.冒 C.歸 D.下列序列中 A.[68，11，18，69] B.[68，11，69，23]C.[93，73][68，11，69，23，18] D.[68，11，69，23，18][93， ） B. D. )排 B.堆排 C.選擇排 D.歸并排 冒泡 C.快速D.下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上，并且其時(shí)間性能受數(shù)據(jù)初始特性影響的是：（ ）。A.直接插入排序B.快速排序C.直接選擇排 30.對初始狀態(tài)為遞增序列的表按遞增順序排序，最省時(shí)間的是（ A.堆排 B.快速排 C.插入排 D.歸并排31A.冒泡B.希爾插入C.交換D A．起泡排 B．快速排列排序D．堆排序E33法是 A．直接插入排序B．冒泡排序C34．下列排序算法中34．下列排序算法中）A.堆排序 B.冒泡排序 C.快速排序 D.插入排下列排序算法中，占用輔助空間最多的是： )A.歸并排B.快速排 排 D.堆排從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行AB37.在排序算法中，每次從未排序的記錄中挑出最?。ɑ蜃畲螅┳值挠涗?，加入到已排序記錄的末尾，該排序方法是 ）A.選 B.冒 C.插 D.38．用直接插入排序方法對下面四個(gè)序列進(jìn)行排序（由小到大），比較次數(shù)最少的是 ） CB．．D．39．直接插入排序在最好情況下的時(shí)間復(fù)雜度為A．D．B．）C．4010,14,26,29,41,524010,14,26,29,41,52進(jìn)行A.B.C.D. 41.采用簡單選擇排序，比較次數(shù)與移動(dòng)次數(shù)分別為 )A.D.B.C.42.對序列{15，9，7，8，20，-1，4，} A. B. C. D. ）A．{21,25,5,17,9,23,30}C．{21,9,17,30,25,23,5}Ｄ．44．對關(guān)鍵碼序列28，16，3212，60，2，572快速排序，從小到大一次劃分結(jié)果為（ ）。A.(2,5,12,16)26(60,32,72)B.C.(2,16,12,5)28(60,32,72)D. AB．每次分區(qū)后，先處理較長的部分C．與算法每次分區(qū)后的處理順序無關(guān)D．以上三者都不對46．當(dāng)n個(gè)整型數(shù)據(jù)是有序時(shí)，對這n46．當(dāng)n個(gè)整型數(shù)據(jù)是有序時(shí)，對這n間復(fù)雜度是(6)，當(dāng)用遞歸算法求n76)-(7)=（）A D. B.A．O(NlogN)B．O(N2)C．O(N3)D．堆排序E．冒泡排序F48.快速排序方法在 ）情況下最不利于發(fā)揮其長處A.要排序的數(shù)據(jù)量太 B.要排序的數(shù)據(jù)中含有多個(gè)相同C.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)D在含有n個(gè)關(guān)鍵字的小根堆（堆頂元素最?。┲?，關(guān)鍵字最大的記錄有可能 在（）位置上。 B．n/2- D．n/2 B.D.51．下列四個(gè)序列中，哪一個(gè)是堆 ）A. B.C. D.52.堆排序是52.堆排序是）加 空間復(fù)雜度分別是A.插入 B.交換F.O（n2）和HO（nlogn）和CD.基 G.O（nlogn）和O（n2）和 ）A.O(logn)B.O(1)C.O(n)D.對n個(gè)記錄的文件進(jìn)行堆排序 情況下的執(zhí)行時(shí)間是多少 A．O（logn）B．O（n）C．O（nlogn）法建立的初始堆為 A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不對。歸并排序中，歸并的趟數(shù)是 )A．O（nB．C． A．插入排序B．枚舉排序C．選擇排序D．交換排序就排序算法所用的輔助空間而言，堆排序，快速排序，歸并排序的關(guān)系是（ ）ABD已排序序列（初始時(shí)為空）中的元素作比較，將其放入已排序序列的正確位置上；（2）法從未排序的序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端；交換排序方法是對序列中的元素進(jìn)行一系列比較，當(dāng)被比較的兩元素逆序時(shí)，進(jìn)行交換；（3）和（4）（4）是比（3）效率更高的方法；（5）法是基于選擇排序的一種排序方法，是完全二（1）--B．快速排 C．插入排排序G當(dāng)待排序的元當(dāng)待排序的元素很大時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素。（ ）內(nèi)排序要求數(shù)據(jù)一定要以順序方 。 排序算法中的比較次數(shù)與初始元素序列的排列無關(guān)。排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（ ）在執(zhí)行某個(gè)排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動(dòng)，則該算法是不穩(wěn)定的。（）直接選擇排序算法在最好情況下的時(shí)間復(fù)雜度為O（N）。（8．在初始數(shù)據(jù)表已經(jīng)有序時(shí)，快速排序算法的時(shí)間復(fù)雜度為O(nlog8．在初始數(shù)據(jù)表已經(jīng)有序時(shí)，快速排序算法的時(shí)間復(fù)雜度為O(nlogn ）10序的執(zhí)行時(shí)間最省。 若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的 和記錄的 。外排序的基本操作過程 屬于不穩(wěn)定排序的 屬于不穩(wěn)定排序的 分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態(tài)為有序的表，則最省時(shí)間的是 算法，最費(fèi)時(shí)間的是 算法。 用鏈表表示的數(shù)據(jù)的簡單選擇排序，結(jié)點(diǎn)的域?yàn)閿?shù)據(jù)域data，指針域next；鏈表首指針為head，鏈表無頭結(jié)點(diǎn)。while {q=p; ){if )q=r; ;}tmp=q->data;q->data=p->data;p->data=tmp;p= ;}9．下面的9．下面的c函數(shù)實(shí)現(xiàn)對鏈表hed大#includetypedefstructnode{chardata;structnode*link;}node;node*select(node*head){node*p,*q,*r,*s;p=(node*)malloc(sizeof(node));p->link=head;head=p;{q=p->link;r=p;while((1){if(q->link->data<r->link->data)r=q;q=q->link;}if((2)){s=r->link;r->link=s->link;s->link=((3) );((4) ((5));}p=head;head=head->link;(p);}給出一組關(guān)鍵字：29，18，25，47，58，12，51，10，分別寫出按下列各種排序方法進(jìn)行排序時(shí)的變化過程：歸并排 每歸并一次書寫一個(gè)次序快速排 每劃分一次書寫一個(gè)次序堆排序 先建成一個(gè)堆，然后每從堆頂取下一個(gè)元素后，將堆調(diào)整一次基礎(chǔ)基礎(chǔ)與理論環(huán)節(jié)——基本概念和算法思路第一章第三章棧第四章第六章圖及應(yīng)用第七章查找第八章第九章—選擇題散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址，因?yàn)樯⒘泻瘮?shù)是一對一的關(guān)，則選擇好（ ）方法是散列文的關(guān)鍵。A.散列函數(shù)B.除余法中的質(zhì)數(shù)C.處理D.散列函數(shù)和處順序文件采用順序結(jié)構(gòu)實(shí)現(xiàn)文件的，對大型的順序文件的少量修改，要求重整個(gè)文件，價(jià)很高，采（ ）的方法可降低需的代價(jià)。A.附加文件B.按關(guān)鍵字大小排序C.按記錄輸入先后排序D 4．下述文件中適合于磁帶的是4．下述文件中適合于磁帶的是 ）A.順序文件B.索引文件C.散列文件D ）順序文 B.索引文6.ISAM文件和VASM文件屬于 ）A.索引非順序文件B.索引順序文件C.順序文 D.散列文 ）文件系統(tǒng)中 B. 文件 兩種文件 文件 兩種文件單關(guān)鍵字文 多關(guān)鍵字文3.從用戶的觀點(diǎn)看，文件的邏輯結(jié)構(gòu)通?？梢詤^(qū)分為兩類：一類是如dBASE中數(shù)據(jù)庫文件那樣的文件組織結(jié)構(gòu)，稱為(1文件；另一種是諸如用各種文字處理軟件編輯成的文本文件，稱為_2文件。從文件在器上的存放方式來看，文件的物理結(jié)構(gòu)往往可區(qū)分為三類，即(3)_，_(4和5)_。B適用于組織(6)_的索引結(jié)構(gòu)，mB_(7)_個(gè)兒子，除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)至少有(8(9個(gè)兒子，有k個(gè)兒子的結(jié)點(diǎn)必有(10)個(gè)關(guān)鍵碼。3.從用戶的觀點(diǎn)看，文件的邏輯結(jié)構(gòu)通?？梢詤^(qū)分為兩類：一類是如dBASE3.從用戶的觀點(diǎn)看，文件的邏輯結(jié)構(gòu)通常可以區(qū)分為兩類：一類是如dBASE中數(shù)據(jù)庫文件那樣的文件組織結(jié)構(gòu)，稱為(1)文件；另一種是諸如用各種文字處理軟件編輯成的文本文件，稱為_2文件。從文件在器上的存放方式來看，文件的物理結(jié)構(gòu)往往可區(qū)分為三類，即(3)_，_(4和5)_。B適用于組織(6)_的索引結(jié)構(gòu)，m階B+樹每個(gè)結(jié)點(diǎn)至多有_(7)_個(gè)兒子，除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)至少有(8(9個(gè)兒子，有k個(gè)兒子的結(jié)點(diǎn)必有(10)個(gè)關(guān)鍵碼。（1）數(shù)據(jù)庫（2）文本（3）順序組織（4）隨機(jī)組織（5）鏈組織（6）隨機(jī)組織（7）m （8）m/2（9）2（10）k文件 組成；記錄 組成 個(gè)記錄 存取 文件 文件 組成；記錄 組成記 數(shù)據(jù) 個(gè)記錄 存取 索引順序文件是最常用的文件組織之一，通常用 檢，也可以 檢索； 檢索又可以 檢索 檢索索引順序文件是最常用的文件組織之一，通常用索引順序文件是最常用的文件組織之一，通常用樹 檢 和 構(gòu)成的VSAM(虛擬存取方法)文件的優(yōu)點(diǎn)是：動(dòng)態(tài)地 和 構(gòu)成的VSAM(虛擬存取方法)文件的優(yōu)點(diǎn)是：動(dòng)態(tài)地 和 構(gòu)造散列函數(shù)解決的方 構(gòu)成的索引集順序集數(shù)據(jù)集VSAM(虛擬存取方法)文件的優(yōu)點(diǎn)是：動(dòng)態(tài) ，不需要文件進(jìn) ，分配和釋放空 重 順序結(jié)構(gòu)，相應(yīng)文件為順序文件，其記錄按存入文件的先后次序順序存放。順序文件本質(zhì)上就是順序表。若邏輯上相鄰的兩個(gè)記錄在位置上相鄰，則為連續(xù)文件；若記錄之間以指針相，則稱為串聯(lián)文件。順序文件只能順序存取，更新某個(gè)記錄，必須帶索引的結(jié)構(gòu)，相應(yīng)文件為索引文件。索引文件包括索引表和數(shù)據(jù)表，索引表中的索引項(xiàng)包括數(shù)據(jù)表中數(shù)據(jù)的關(guān)鍵字和相應(yīng)地址，索引表有序，其物理順序體現(xiàn)了文件的邏輯次序，實(shí)現(xiàn)了文件的線性結(jié)構(gòu)。索引文件只能是磁盤文件，既能順序存取，又能隋機(jī)存取。散列結(jié)構(gòu)，也稱計(jì)算尋址結(jié)構(gòu)，相應(yīng)文件稱為散列文件，其記錄是根據(jù)關(guān)鍵字值經(jīng)散列函數(shù)計(jì)算確定地址，