數據結構(C語言版)(第4版)習題

習題1選擇題。(1)計算機識別、存儲和加工處理的對象統(tǒng)稱為。A．數據B.數據元素C.數據結構D.數據類型(2)數據結構通常是研究數據的及它們之間的聯(lián)系。A．存儲和邏輯結構B.存儲和抽象C.理想和抽象D.理想和邏輯(3)下列不是數據的邏輯結構的是。A．散列結構B.線性結構C.樹形結構D.圖狀結構(4)數據結構被形式地定義<D,R>，其中D是的有限集，R是___的有限集。A．算法B.數據元素C.數據操作D.邏輯結構(5)組成數據的基本單位是。A．數據項B.數據類型C.數據元素D.數據變量(6)設數據結構A=(D,R),其中，D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},則數據結構A是。A．線性結構B.樹形結構C.圖狀結構D.集合(7)數據在計算機存儲器中表示時，若物理地址與邏輯地址相同并且是連續(xù)的，則稱為。A．存儲結構B.邏輯結構C．順序存儲結構D.鏈式存儲結構(8)在數據結構的討論中把數據結構從邏輯上分。A．內部結構與外部結構B.靜態(tài)結構與動態(tài)結構B．線性結構與非線性結構D.緊湊結構與非緊湊結構(9)對于一個算法的評價，不包括以下方面的內容。A.健壯性和可讀性B.并行性C.正確性D.時間空間復雜度(10)算法分析的兩個方面是。A．空間復雜性和時間復雜性B.正確性和簡明性C．可讀性和文檔性D.數據復雜性和程序復雜性1.2填空題(1)數據結構是一門研究非數值計算的程序設計問題中計算機的以及它們之間的和運算等的學科。(2)數據結構包括數據的結構和結構。(3)數據結構從邏輯上劃分為3種基本類型，即、和。(4)數據的物理結構被分為、、和種類型。(5)一種抽象數據結構類型包括和兩個部分。(6)數據的邏輯結構是指數據的存儲結構是指(7)數據結構是指指數數據及其相互之間的當結點之間存在M對N(M:N)的聯(lián)系時，稱這種結構為當結點之間存在1對N(1：N)的聯(lián)系時，稱這種結構為(8)對算法從時間和空間兩個方面進行衡量，分別稱為分析。(9)算法的效率可以分為效率和效率。(10)for(i=1,t=1,s=0;i<=n;i++){t=t*i;s=s+t;}的時間復雜度為1.3簡述下列術語：數據、數據項、數據元素、數據的邏輯結構、數據的物理結構、數據類型和算法。1.4分析下面語句段執(zhí)行的時間復雜度。(1)for(i=1;i<=n;i++)for(j=1;j<=n;j++)s++;(2)for(i=1;i<=n;i++)for(j=i;j<=n;j++)s++;(3)for(i=1;i<=n;i++)for(j=1;j<=i;j++)s++;(4)i=1;k=0;While(i<=n-1){k+=10*i;i++;}(5)for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;1.5試寫一個算法，自大至小依次輸出順序讀入的3個整數X、Y和Z。1.6編寫算法，求一元多項式Pn(x)=a0+a1x+習題22.1選擇題(1)線性表是具有n個的有限序列(n≠0)。A.表元素B.字符C.數據元素D.數據項(2)順序表的存儲結構是一種的存儲結構。A.隨機存取B.順序存取C.索取存取D.Hash存取(3)在一個長度為n的順序表中向第i個元素(1≤i≤n+1)之間插入一個新元素時需要向后移動個元素。A.n-iB.n-i+1C.n-i-1D.i(4)鏈表是一種采用存儲結構存儲的線性表。A．順序B.鏈式C.星型D.網狀(5)下面關于線性表的敘述錯誤的是A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C.線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)D．線性表采用順序存儲便于插入和刪除操作的實現(xiàn)(6)設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列存儲方式最節(jié)省運算時間。A.單向鏈表B.單向循環(huán)鏈表C.雙向鏈表D.雙向循環(huán)鏈表(7)設指針q指向單鏈表中的結點A，指針p指向單鏈表中的結點A的后繼結點B，指針s指向被插入的結點X，則在結點A和結點B之間插入結點X的操作序列為A.s->next=p->next;p->next=-s;B.q->next=s;s->next=p;C.p->next=s->next;s->next=p;D.p->next=s;s->next=q;(8)設指針變量p指向單鏈表結點A，則刪除結點A的后繼結點B需要的操作為A.p->next=p->next->nextB.p=p->nextC.p=->next->nextD.p->next=p(9)在一個以h為頭的單循環(huán)鏈表中，p指針指向鏈尾的條件是。A.p->next=hB.p->next=NULLC.p->next->next=hD.p->date=-1(10)對于只有首、尾兩端進行操作的線性表，宜采用的存儲結構為。A.順序表B.用頭指針表示的單循環(huán)鏈表C.單鏈表D.用尾指針表示的單循環(huán)鏈表2.2填空題(1)線性表是n個元素的________________。(2)線性表的存儲結構有________________。(3)設線性表中有n個數據元素，則在順序存儲結構上實現(xiàn)順序查找的平均時間復雜度為，在鏈式存儲結構上實現(xiàn)順序查找的平均時間復雜度為。(4)設順序線性表中有n個數據元素，則在第i個位置上插入一個數據元素需要移動表中的個數據元素，刪除第i個位置上數據元素需要移動表中的個元素。(5)若頻繁地對線性表進行插入與刪除操作，則該線性表應采用存儲結構。(6)鏈式存儲結構中的結點包含域和域。(7)在雙向鏈式表中每個結點有兩個指針域，一個指向另一個指向(8)對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為在表尾插入元素的時間復雜度為(9)設指針變量p指向單鏈式表中的結點A，指針變量s指向被插入的結點B，則在結點A的后面插入結點B的操作序列為________。(10)設指針變量p指向單鏈式表中的結點A，則刪除結點A的后繼結點（假設存在）的語句序列為“s=p->next;p->next=;free(s);”2.3將一順序表A中的元素逆置。例如原來順序表A中的元素是100,90,80,70,60,50,40，逆置以后為40,50,60,70,80,90,100。要求算法所用的輔助空間盡可能地少，用非形式算法描述，并編寫C語言程序。2.4寫一算法輸出已知順序表A中元素的最大值和最小值，并編寫C語言程序。2.5設一順序表中的元素值遞增有序，寫一算法，將元素x插入到表中的適當位置，并保持順序表的有序性。2.6設有兩個按元素遞增有序的順序表A和B（單鏈式表A和B），編一程序將A表和B表歸并成一個新的遞增有序的順序表C（單鏈式表C），值相同的元素均保留在C表中。2.7設有兩個線性表A和B都是單鏈表存儲結構。同一個表中的元素各不相同，且遞增有序，寫一算法，構成一個新的線性表C，使C為A和B的交集，且C中的元素也遞增有序。習題33.1選擇題(1)下列說法正確的是_____。A.堆棧是在兩端操作、先進后出的線性表B.堆棧是在一端操作、先進先出的線性表C.隊列是在一端操作、先進先出的線性表D.隊列是在兩端操作、先進先出的線性表(2)棧和隊列的共同點是_____。A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素D.沒有共同點(3)以下數據結構中是非線性結構的是_____。A.隊列B.棧C.線性表D.二叉樹(4)已知一個棧的入棧序列是1,2,3，…,n，輸出序列是p1，p2，p3?A.iB.n-iC.n-i+1D.不確定(5)當利用大小為N的一堆數組順序存儲一個棧時，假定用top==N表示棧空，則向這個棧插入一個元素時首先應執(zhí)行_____語句修改top指針。A.top++B.top--C.top=0D.top(6)4個元素進S棧的順序是A→B→C→D，經POP(S)運算后棧頂元素是_____。A.AB.BC.CD.D(7)一個棧的輸入序列是a,b,c,d,e,則棧不可能的輸出序列是____。A.e,d,c,b,aB.d,e,c,b,aC.d,c,e,a,bD.a,b,c,d,e(8)設輸入序列是1,2,3，…，n，經過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出的元素是_____。A.n-iB.n-i-1C.n+1-iD.不能確定(9)字符A,B,C,D依次進入一個棧，按出棧的先后順序組成不同的字符串，最多可以組成_____個不同的字符串。A.15B.14C.16D.21(10)遞歸函數f(n-1)=f(n-1)+n(n≥1)的遞歸出口是_____。A.f1=0B.f1=1C.(11)設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作為_____。A.top=top+1;B.top=top-1;C.top->next=top;D.top=top->next;(12)中綴表達式A-(B+C/D)*E的后綴形式是_____。A.ABC+D/*E-B.ABCD/+E*-C.AB-C+D/E*D.ABC-+D/E*(13)用front和rear分別表示順序循環(huán)隊列的隊首和隊尾指針，判斷隊空的條件為_____。A.front+==reearB.(rear+1)%maxSize==frontC.front==0D.front==rear(14)判定一個循環(huán)隊列QU（最多元素為m0）為滿隊列的條件為_____。A.QU->front==QU->rearB.QU->front!=QU->rearC.QU->front==(QU->rear+1)%mD.QU->front!=(QU->rear+1)%m(15)設棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，A.6B.4C.3D.2(16)用連接方式存儲的隊列，在進行插入運算時_____。A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改(17)若用一個大小為6的數組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3。當從隊列中刪除一個元素再加入兩個元素后，rear和front的值分別為_____。A.1和5B.2和4C.4和2D.5和1(18)設順序循環(huán)隊列Q[0：M=1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一個位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數為_____。A.R-FB.F-RC.(R-F=M)%MD.(F-R+M)%M(19)設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作為_____。A.front->next=s;front=s;B.s->next=front;rear=s;C.rear->next=s;rear=s;D.s->next=front;front=s;(20)當利用大小為n的數組順序存儲一個隊列時，該隊列的最大長度為_____。A.n-2B.n-1C.nD.n+13.2填空題（1）棧的插入和刪除只能在棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為_____表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為下劃表。（2）后綴算式923+-102/-的值為_____，中綴算式(3+4X)-2Y/3對應的后綴算式為_____。（3）下面程序段的功能是實現(xiàn)數據x的進棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==n-1)printf(“overfow”);else{__________；__________；}（4）設指針變量p指向雙向循環(huán)鏈表中的結點X，則刪除結點X需要執(zhí)行的語句序列為_____；_____；（設結點中的兩個指針域分別為llink和rlink）。（5）設一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲M-1個隊列元素，當前實際存儲_____個隊列元素（設頭指針F指向F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。（6）設有一個順序共享棧S[0:n-1],其中，第一個棧頂指針top1的處置為-1，第二個棧頂指著top2的初值為n，則判斷共享棧滿的條件是（7）設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為__________。（8）順序循環(huán)隊列判空的條件是（使用front、rear、n表示）__________。（9）順序循環(huán)隊列判滿的條件是（使用front、rear、n表示）__________。（10）順序循環(huán)隊列MAXSIZE=N,最多可以存儲_____個元素。3.3簡述棧和線性表的區(qū)別。3.4簡述棧和隊列這兩種數據結構的相同點和不同點。3.5如果進棧的元素序列為A,B,C,D,可能得到的出棧序列有多少種？寫出全部的可能序列。3.6如果進棧的元素序列為1,2,3,4,5,6，能否得到4,3,5,6,1,2和1,3,5,4,2,6的出棧序列？說明為什么不能得到或如何得到。3.7寫出下列程序段的運行結果（棧中的元素類型是char）:main(){SeqStacks,*p;charx,y;p=&s;Init_Queue(p);x=’c’;y=’k’;push(p,x);push(p,’a’);push(p,y);x=pop(p);push(p,’t’);push(p,x);x=pop(p);push(p,’s’);while(!Empty_SeqStack(p)){y=pop(p);printf(“%c”,y);}printf(“%c\n”,x);}3.8將一個非負十進制整數轉換成二進制數，用非遞歸算法和遞歸算法來實現(xiàn)。3.9寫一算法將一順序棧中的元素依次取出，并打印元素值。3.10寫出下列程序段的運行結果（隊列中的元素類型是char）:main(){SeqStacka,*q;charx,y;q=&a;x=’e’;y=’c’;Init_Queue(q);In_Quene(q,’h’);In_Quene(q,’r’);In_Quene(q,y);x=Out_Quene(q);Init_Queue(q,x);x=Out_Quene(q);Init_Queue(q,’a’);while(!Empty_SeqStack(q)){y=Out_Quene(q);printf(“%c”,y);}printf(“%c\n”,x);}3.11寫一算法將一鏈隊列中的元素依次取出，并打印這些元素值。習題44.1選擇題(1)下列敘述正確的是_____。A．串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串(2)下列關于串的敘述正確的是_____。A.串長度是指串中不同字符的個數B.串是n個字母的有限序列C.如果兩個串含有相同的字符，則它們相等D.只有當兩個串的長度相等并且各個對應位置的字符都相符時才相等(3)字符串的長度是指_____。A.串中不同字符的個數B.串中不同字母的個數C.串中所含字符的個數D.串中不同數字的個數(4)兩個字符串相等的充要條件是_____。A.兩個字符串的長度相等B.兩個字符串中對應位置上的字符相等C.同時具備A和B兩個條件D.以上答案都不對(5)串是一種特殊的線性表，其特殊性體現(xiàn)在_____。A.可以順序存儲B.數據元素是一個字符C.可以連接存儲D.數據元素可以是多個字符(6)設有兩個p和q,求q和p中首次出現(xiàn)的位置的位置的運算稱為_____。A.連接B.模式匹配C.求子串D.求串長(7)設串s1=“ADCDEFG”,s2==“PQRET”，函數con(x,y)返回x和y串的連接subs(s,i,j)返回串s從序列號為i的字符開始的j個字符組成的子串，len(s)返回串s的度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結果串是_____。A.BCDEFB.BCDEFGC.BCPQRETD.BCDEFEF(8)函數substr(“DATASTRUCTURE”),5,9)的返回值為_____。A.“STRUCTURE”B.“DATA”C.“ASTRUCTUR”D.“DATASTRUCTURE”(9)設有二維數組A[50][60],其元素長度為1B，按列優(yōu)先順序存儲，首先素A[0][0]的地址為200，則元素A[10][20]的存儲地址為_____。A.820B.720C.1210D.1410(10)設串s=“IAMATEACHER!”,其長度是_____。A.16B.11C.14D.154.2填空題（1）兩個串相等的充要條件是__________。（2）空串是_____，其長度為_____。（3）空格串是_____，其長度是_____。（4）s=“Iamaman”的長度為_____。（5）s1=“hello”,s2=“boy”,s1,s2連接后為_____。（6）s=“thisisthemainstring”，sub=“string”,strindex(s,sub)是_____。（7）inta[10][10],已知a=1000,sizeof(int)=2,a[3][3]的地址為_____。（8）設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為_____。（9）串的長度是指_____。（10）s=“xiaotech”所含子串的個數是_____。4.3設s=“IAMASTUDENT”,t=“GOOD”,q=“WORKER”,求StrLength(s)、StrLength(t)、SubStr(t,2,1)、SteeIndex(s,“A”)、StrIndex(s,t)、StrRep(s,“STUDENT”,q)。4.4已知s=“（XXZ）+*”,t=“（X+Z）*Y”,試利用連接、求字串和置換等基本運算將s轉化為t。4.5簡述下列每對術語的區(qū)別：空串和空格串；串變量和串常量；主串和字串；串變量的名字和串變量的值。4.6編一算法，在順序串上實現(xiàn)串的判等操作EQUAL(S,T).4.7設有二維數組A(6×8),每個元素占6B順序存放，A的起地址為1000，做以下計算：（1）數組A的體積（即存儲量）；（2）數組的最后一個元素A5,（3）按行優(yōu)先存放時，元素A1,（4）按列優(yōu)先存放時，元素A4,74.8已知稀疏矩陣如圖4.12所示，畫出它的三元組表的示意圖。A=圖4.12題4.8圖習題55.1單選題（1）樹最適合用來表示_____。A.有序數據元素B.無序數據元素C.元素間具有層次關系的數據D.元素間無聯(lián)系的數據（2）在m叉樹中，度為0的結點稱為_____。A.兄弟B.樹葉C.樹根D.1（3）如果樹的結點A有4個兄弟，而且B為A的雙親，則B的度為_____。（4）根據二叉樹的定義可知二叉樹共有_____種不同的形態(tài)。A.4B.5C.6D.7（5）由3個結點可以構造出_____種不同形態(tài)的二叉樹。A.3B.4C.5D.6(6)具有20個結點的二叉樹，其深度最多為_____。A.4B.5C.6D.20（7）高度為h的滿二叉樹的結點數是_____個。A.log2hB.2hC.2h-1（8）深度為5的二叉樹最多有_____個結點。A.16B.32C.31D.10（9）設一棵二叉樹共有50個葉子結點（終端結點），則共有_____個度為2的結點。A.25B.49C.50D.51（10）一顆完全二叉樹中根結點的編號為1，并且23號結點有左孩子但沒有右孩子，則完全二叉樹共有_____個結點。A.24B.45C.46D.47（11）二叉樹的第3層最少有_____個結點。A.4B.1C.2D.3（12）設n,m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m之前的條件是_____。A.n在m右方B.n是m的祖先C.n在m左方D.n是m的子孫（13）某二叉樹的先序序列和后序序列正好相同，該二叉樹可能是_____的二叉樹。A.高度大于1的左單支B.高度大于1的右單支C.最多只有一個結點D.既有左孩子又有右孩子（14）某二叉樹的先序序列和后序序列正好相反，該二叉樹一定是_____的二叉樹。A.空或只有一個結點B.高度等于其結點數C.任一結點無左孩子D.任一結點無右孩子（15）有n個結點的二叉樹鏈表共有_____個空指針域。A.n-1B.2n-1C.2n+1D.2(n-1)（16）一個有n個葉結點的哈夫曼樹具有的結點數為_____。A.2nB.2n-1C.2n+1D.2(n-1)5.2填空題（1）一顆深度為5的二叉樹，最少有_____個葉子結點。（２）一顆完全二叉樹采用順序存儲結構，每個結點占４個字節(jié)，設編號為５的元素的地址為１０１６，且它有左孩子和右孩子，則該左孩子和右孩子的地址分別為_____和_____。（３）一顆完全二叉樹采用順序存儲結構，若編號為ｉ的元素有有左孩子，則該左孩子的編號為_____。（４）一棵含有ｎ（ｎ＞１）個結點的ｋ叉樹，當ｋ＝_____時深度最大，此最大深度為_____；當ｋ＝_____時深度最小，此最小深度為_____。（５）深度為為ｋ的玩群二叉樹最少有_____個結點，最多有_____個結點。（６）已知一棵二叉樹的線序遍歷序列為ＥＢＡＤＣＦＨＧＩＫＪ，中序遍歷序列為ＡＢＣＤＥＦＧＦＩＪＫ，則該二叉樹的后序遍歷序列為_____。（７）如果指針ｐ指向一棵二叉樹的一個結點，則判斷ｐ沒有左孩子的邏輯表達式為_____。（８）在由ｎ個帶權葉子結點構造出的所有二叉樹中，帶權路徑長度最小的二叉樹稱為_____。（９）在樹的孩子兄弟表示法中，每個結點有兩個指針域，一個指向_____，另一個指向_____。（１０）樹的先根遍歷結果與其轉換的相應二叉樹的_____結果相同；樹的后跟遍歷與其轉換的相應二叉樹的_____結果相同。５.３寫出圖５.２４中樹的葉子結點、非終端結點、個結點的度和樹深。５．４分別畫出含３個結點的無序樹與二叉樹的所有不同形態(tài)。５．５分別畫出含３個結點的無序樹與二叉樹的所有不同形態(tài)。５.６分別寫出圖５.２５中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結點訪問序列。圖５.２４題５.３圖圖５.２５題５.５圖５.７試找出分別滿足下列條件的所有二叉樹：（１）先徐序列和中序序列相同；（２）后徐序列和中序序列相同；（３）先徐序列和后序序列相同。５.８已知一棵二叉樹的中序序列和后序序列分別為ＢＣＤＥＡＦＨＧ和ＤＥＣＢＨＧＦＡ，試畫出這棵二叉樹。５.９分別寫出圖５．２４中所示樹的先根遍歷、后根遍歷和層次遍歷的結點訪問序列。５.１０如果一棵樹有n1個度為1的結點，n2個為2的結點。……,nm個度為m的結點，則該樹共有多少個葉5.12編一算法求二叉樹中的結點的總數。5.13編一算法將二叉樹中所有結點的左、右子樹相互交換。5.14編一算法判別給定的二叉樹是否是完全二叉樹。5.15將圖5.26中所示的森林轉換為二叉樹。圖5.26題5.15圖5.16分別畫出圖5.27中所示二叉樹對應的森林。5.17在以雙親鏈表表示法存儲結構的樹中，寫出以下算法：（1）求樹中結點雙親的算法；（2）求樹中結點孩子的算法。5.18在以孩子鏈表表示法存儲結構的樹中，寫出以下算法：（1）求樹中結點雙親的算法；（2）求樹中結點孩子的算法。5.19在以孩子兄弟鏈表結構存儲的樹中，寫出求樹中結點孩子的算法。5.20（1）給定權值（4,3,16,9,22,10,5），構造相應的哈夫曼樹。（2）設上述權值分別代表7個字母出現(xiàn)的頻率，試為這7個字母設計哈夫曼編碼。習題66.1選擇題（1）一個有8個頂點的有向圖，所有頂點的入度之和與所有頂點的出度之和的差是_____。A.16B.4C.0D.2（2）一個有n個頂點的連通無向圖最少有_____條邊。A.n-1B.nC.n+1D.n+2（3）具有n個頂點的完全有向圖的弧數為_____。A.n(n-1)/2B.n(n-1)C.n2D.（4）一個n條邊的連通無向圖，其頂點的個數最多為_____。A.n-1B.nC.n+1D.nlogn（5）設無向圖的頂點個數為n，則該圖最多有_____條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.0（6）任何一個無向連通圖的最小生成樹_____A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在（7）在下列算法中，_____算法用來求圖中某頂點到其他所有頂點之間的最短路徑。A.DijkstraB.FloyedC.PrimD.Kruskal（8）在一個無向圖中，所有頂點的度數之和等于所有邊數的_____倍。A.2B.3C.1D.1.5（9）下面關于圖的存儲的敘述中正確的是_____。A.用鄰接表法存儲圖，占用的存儲空間大小只與圖中的邊數有關，而與頂點個數無關。B.用鄰接表法存儲圖，占用的存儲空間大小與圖中的邊數和頂點個數都有關。C.用鄰接矩陣表法存儲圖，占用的存儲空間大小與圖中的邊數和頂點個數都有關。D.用鄰接矩陣表法存儲圖，占用的存儲空間大小只與圖中的邊數有關，而與頂點個數無關。（10）設有向無環(huán)圖G中的有向邊集合E={<1，2>,<2，3>,<3，4>,<1，4>},則下列屬于該有向圖G的一種拓撲排序序列的是_____。A.1，2，3，4B.2，3，4，1C.1，4，2，3D.1，2，4，3(11)設無向圖G中的邊的集合E={(a,b),(a,e),(a,c)(b,e),(e,d),(d,f),(f,c)},則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為_____。A.aedfcbB.acfebdC.aebcfdD.aedfbc（12）連通圖G中有n個頂點，G的生成樹是_____連通子圖。A.包含G的所有頂點B.包含G的所有邊C.不必包含G的所有頂點D.包含G的所有頂點和所有邊（13）設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有_____中個表頭結點。A.n-1B.nC.n+1D.2n-1（14）設無向圖G中有n個頂點、e條邊，則其對應的鄰接表中的表頭結點和邊表結點的個數分別為_____。A.n,eB.e,nC.2n,eD.n,2e（15）用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為_____。A.第i行非0元素的個數之和B.第i列非0元素的個數之和C.第i行0元素的個數之和D.第i列0元素的個數之和（16）用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的出度為_____。A.第i行非0元素的個數之和B.第i列非0元素的個數之和C.第i行0元素的個數之和D.第i列0元素的個數之和（17）可以判斷一個有向圖中是否含有回路的方法為_____。A.廣度優(yōu)先遍歷B.深度優(yōu)先遍歷C.拓撲排序D.求最短路徑6.2填空題（1）一個連通無向圖有5個頂點、8條條邊，則其生成樹將要去掉_____條邊。（2）在樹結構和圖結構中，前驅和后繼結點之間分別存在著_____和_____的聯(lián)系。（3）有n個頂點的連通圖至少有_____條邊，有n個頂點的強連通圖至少有_____條邊。（4）一個具有n個頂點的有向圖至少有_____條弧。（5）如果不知道一個圖是有向圖還是無向圖，但是知道它的鄰接矩陣是非對稱的，那么這個圖必定是_____。（6）在無向圖G的鄰接矩陣A中，若A[I][J]=1，則A[J][I]為_____。（7）無向圖用鄰接矩陣存儲，其所有元素之和表示無向圖的邊數的_____。（8）無向圖用鄰接表存儲，其所有邊表結點之和表示無向圖的邊數的_____。（9）無向圖用鄰接表存儲，頂點vi的度為_____（10）有向圖用鄰接表存儲，頂點vi的度為_____（11）圖的遍歷方式一般有_____和_____兩種。（12）Prim算法的時間復雜度為_____，與邊數無關，因此適用于求邊稠密的網的最小生成樹。（13）如果某有向圖的所有頂點可以構成一個拓撲排序序列，則說明該有向圖_____。6.3畫出無向圖6.23的鄰接矩陣和鄰接鏈表示意圖，并寫出每個頂點的度。6.4畫出有向圖6.24的鄰接矩陣、鄰接鏈表和逆鄰接鏈表示意圖，并寫出每個頂點的入度、出度。圖6.23題6.3圖圖6.24題6.4圖6.5對應圖6.25，寫出從v1出發(fā)的深度優(yōu)先查找遍歷結果和廣度優(yōu)先查找遍歷結果各3個。6.6求圖6.26的連通分量。6.7分別用Prim算法按列表方式求出圖6,27的最小生成樹，并畫出最小生成樹的示意圖。圖6.25題6.5圖圖6.26題6.6圖圖6.27題6.7圖6.8寫出圖6.28的拓撲排序。6.9試寫出下列算法：（1）建立無向圖鄰接矩陣算法；（2）建立無向網鄰接矩陣算法；（3）建立有向圖鄰接矩陣算法。6.10試寫出下列算法：（1）建立無向圖鄰接鏈表結構算法；（2）建立無向網鄰接鏈表結構算法。6.11編寫算法，在無向圖的鄰接鏈表結構上生成無向圖的鄰接矩陣結構。6.12編寫算法，在無向圖的鄰接矩陣結構上生成無向圖的鄰接鏈表結構。6.13已知有m個頂點的無向圖，采用鄰接矩陣結構存儲，問：（1）圖中有多少條邊？（2）任意兩個頂點i和j之間是否有邊相連？（3）任意一個頂點的度是多少？6.14已知一個無向圖，采用鄰接鏈表結構存儲，問：（1）圖中有多少條邊？（2）任意兩個頂點i和j之間是否有邊相連？（3）任意一個頂點的度是多少？6.15以圖6.29所示的無向圖連通圖為例，按照深度優(yōu)先查找遍歷的算法編寫程序上機運行，并獲得正確的結果。圖6.28題6.8圖圖6.29題6.15圖習題77.1選擇題（1）對長度為n的無序線性表進行順序查找，查找成功、不成功時的平均數據比較次數分別為_____。A.n2、nB.n+12、n-1（2）指出順序表{2、5、7、10、14、15、18、23、35、41、52}中用二分法查找關鍵碼12需做_____次關鍵碼比較。A.2B.3C.4D.5（3）對線性表進行折半查找時，必須要求線性表_____。A.以順序方式存儲B.以鏈式方式存儲C.以順序方式存儲，且結點按關鍵字有序排列D.以鏈式方式存儲，且結點按關鍵字有序排列（4）設二叉樹中有n個結點，則在二叉排序樹的平均查找長度為_____。A.O(1)B.O(log2n)C.O(n)D.O(（5）在依次插入序列（50,72,43,85,75,20,35,45,65,30）后建立的二叉搜索樹中，查找元素35要進行_____元素間的比較。A.4次B.5次C.7次D.10次（6）在一棵高度為5的理想平衡樹中，最少含有16個結點，最多含有_____個結點。A.31B.32C.30D.33(7)對包含N個元素的散列表進行查找，平均查找長度_____。A.為O(log2N)C.不直接依賴于ND.上述三者都不是（8）設散列表中有m個存儲單元，散列函數H（key）=key%p,則p最好選擇_____。A.小于等于m的最大奇數B.小于等于m的最大素數C.小于等于m的最大偶數D.小于等于m的最大合數（9）_____是Hash查找的沖突處理方法。A.求余法B.平方取中法C.二分法D.開放地址法（10）當α的值較小時，散列存儲通常比其他存儲方式具有_____的查找速度。A.較慢B.較快C.相同D.不確定（11）對線性表進行折半查找最方面結構是_____。A.順序表B.有序的順序表C.鏈表D.有序的鏈表（12）對一個排好序的線性表用二分法檢索表中的元素，被檢索的表應當采用_____。A.順序存儲B.鏈接存儲C.散列法存儲D.存儲表示不受限制（13）若在線性表中采用折半查找法查找元素，該線性應該_____。A.元素按值有序B.采用順序存儲結構C.元素按值有序，且采用順序存儲結構D.元素按值有序，且采用鏈式存儲結構（14）用二分法查找一個長度為10的、排好序的線性表，查找不成功是，最多需要比較_____次。A.5B.2C.4D.1（15）采用分塊查找時，若線性表中共有625個元素，查找每個元素的概率相同，假設采用順序查找來確定結點所在的塊，每塊分_____個結點最佳。A.10B.25C.6D.625（16）如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，可以采用_____查找方法。A.分塊B.順序C.二分D.散列（17）散列函數有一個共同性質，即函數值應按_____取其值域的每一個值。A.最大概率B.最小概率C.同等概率D.平均概率（18）某順序存儲的表格中有90000個元素，以按關鍵字值額定升序排列，假定對每個元素進行查找的概率相同，且每個元素的關鍵字的值都不相同，在用順序查找法查找時，平均比較次數約為_____，最大比較次數為_____。A.25000B.30000C.45000D.90000（19）如果m階B_樹中具有n個關鍵字，則葉子結點（即查找不成功的結點）為_____。A.n-1B.n+1C.nD.n/2（20）m階B_樹中的所有非終端（除根之外）結點中的關鍵字個數必須大于或等于_____。A.m/2B.m/2-1C.m/2+1D.m7.2填空題（1）對于長度為n的線性表，若進行順序查找，則時間復雜度為_____；若采用折半法查找，則時間復雜度為_____。（2）假設上在有序線性表A[1..20]進行折半查找，則比較一次查找成功的結點數為_____，比較兩次查找成功的結點數為_____，比較三次查找成功的結點數為_____，比較四次查找成功的結點數為_____，比較五次查找成功的結點數為_____，平均查找長度為_____。（3）在一棵二叉樹搜索樹中，每個分支結點的左子樹上所有結點的值一定_____該結點的值，右子樹上所有結點的值一定_____該結點的值。（4）在對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個_____。（5）在一棵m階B_樹上，每個非樹根結點的關鍵字數目最少為_____個，最多為_____。（6）對于線性表（70,34,55,23,65,41,20）進行散列存儲時，若選用H(K)=K%7作為散列函數，則散列地址為0的元素有_____個，散列地址為6的元素有_____個。（7）在線性表的散列存儲中，裝填因子α又稱為裝填系數，若用m表示散列表的長度，用n表示待散列存儲的元素的個數，則α等于_____。（8）在散列表中解決沖突的兩種方法是_____和_____。（9）在散列存儲中，裝填因子α的值越大，_____；α的值越小，_____。（10）散列法存儲的基本思想是由_____決定數據的存儲地址。（11）最優(yōu)二叉樹（哈夫曼樹）、最優(yōu)查樹均為查找路徑長度i=1nwihi最小的樹，其中對于最優(yōu)二叉樹，n表示_____，對于最優(yōu)查找樹，n表示_____（12）在分塊檢索中，對于256個元素的線性表最好分成_____塊，每塊的最佳長度是_____；若每塊的長度為_____，其平均檢索長度為_____。（13）構造哈希函數的方法有_____。（14）哈希表處理沖突的方法有_____。（15）負載因子（裝填因子）是散列表的一個重要參數，它反映散列表的_____。（16）在分塊查找中首先查找_____，然后查找相應的_____。（17）散列表的查找效率主要取決與散列表造表時選擇的_____和_____。（18）當所有結點的權值都相等時，用這些結點構造的二叉排序樹，_____遍歷它們得到的序列的順序是一樣的。（19）對兩棵具有相同關鍵字集合但形狀不同的二叉排序樹，_____遍歷它們得到的序列的順序是一樣的。（20）m階B_樹每一個結點的子樹個數最多_____m。7.3何謂二叉排序樹？7.4簡述用二次探測法解決沖突的基本思路。7.5順序查找時間為O(n),二分查找時間為O(log2n)，散列查找時間為7.6簡述用多重散列法解決沖突的基本思路。7.7簡述用公共溢出區(qū)法解決沖突的基本思路。7.8在結點個數n(n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結點？多少個分支結點？高度最大的樹的高度是多少？它有多少個葉結點？多少個分支結點？7.9設單鏈表的結點是按關鍵字從小到大排列的，試寫出對詞鏈表的查找算法，并說明是否可以采用折半查找（二分查找）。7.10試寫一個判別給定二叉樹是否為二叉排序數的算法，設此二叉樹以二叉鏈表做存儲結構。7.11通過散列函數hashf(x)=xmod11把一個整數數值轉換成散列表下標，現(xiàn)要把數據1、13、12、34、38、33、27、22插入到散列表中。（1）使用線性探查再散列法來構造散列表。（2）使用鏈地址法來構造散列表。（3）針對這種情況，確定其裝填因子，查找成功所需的平均查找次數以及查找不成功所需的平均探查次數。7.12試寫出二分查找的遞歸算法。7.13假設線性表中的結點是按鍵值遞增的順序存放的，試寫一順序查找法，將崗哨設在高下標端，然后分別求出等概率情況下查找成功和不成功時的平均查找長度。7.14已知紀錄關鍵字集合為（53,17,19,61,98,75,79,63,46,49），要求散列到地址區(qū)間（100,101,102,103,104,105,106,107,108,109）內，若產生沖突則開型尋址法的線性探測法解決，要求寫出選用的散列函數、形成的散列表、計算出查找成功時的平均查找長度和查找不成功時的平均查找長度。習題88.1選擇題。（1）下述排序算法中，穩(wěn)定的是_____。A.直接選擇排序B.直接插入排序C.快速排序D.堆排法（2）下列排序算法中，_____需要的輔助存儲空間最大。A.快速排序B.插入排序C.希爾排序D.基數排序（3）下列排序算法中，平均時間復雜度為O(n2)是_____A.快速排序B.堆排法C.歸并排序D.冒泡排序（4）在基于關鍵碼比較的排序算法中，_____算法在最壞情況下關鍵的比較次數不高于O(logA.冒泡排序B.直接插入排序C.二路歸并排序D.快速排序（5）一組紀錄為{46,79,56,38,84,40}，則采用冒泡排序法按升序排列時第一趟的排序結果是_____。A.46，79，56，38，40，84B.46，56，38，79，40，84C.38，40，46，56，84，79D.38，46，79，56，40，84（6）每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法稱為_____排序。A.插入B.堆C.快速D.歸并（7）每次從無序表中挑選出一個最小或最大的元素，把它交換到有序表的一端，此種排序方法稱為_____排序。A.插入B.堆C.快速D.歸并（8）設有一組初始紀錄關鍵字序列（5,2,6,3,8），以第一個紀錄關鍵字5為基準進行一趟快速排序的結果為_____。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8（9）設有n個待排序的紀錄關鍵字，則在堆排序中需要_____個輔助紀錄單元。A.1B.nC.nlog2n（10）對于關鍵字序列（12,13,11,18,60,15,7,18,25,100），用篩選法建堆，必須從關鍵字值為_____的結點開始。A.100B.12C.60D.15（11）在下列排序方法中，比較次數與紀錄的初始排列狀態(tài)無關的方法是_____。A.直接插入排序B.冒泡排序C.快速排序D.直接選擇排序（12）設有關鍵碼初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X},新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用_____方法對初始序列進行第一趟掃描的結果。A.直接插入排序B.二路歸并排序C.以第一個元素為分界元素的快速排序D.基數排序（13）在待排序文件已基本有序的前提下，下述排序方法中效率最高的是_____。A.直接插入排序B.直接選擇排序C.快速排序D.歸并排序（14）排序的算法很多，若按排序的穩(wěn)定性和不穩(wěn)定性分類，則_____是不穩(wěn)定排序。A.冒泡排序B.歸并排序C.直接插入排序D.希爾（15）若需在On(log2n)的時間內完成對數組的排序，且要求排序A.快速排序B.堆排序C.歸并排序D.直接插入排序（16）將兩者各有n個元素的有序表歸并成一個有序表，其最少的比較次數是_____。A.nB.2n-1C.2nD.n-1（17）下列排序算法中，時間復雜度不受數據初始狀態(tài)的影響，恒為O(log2n)A.堆排序B.冒泡排序C.直接插入排序D.快速排序（18）下列排序算法中，_____算法可能會出現(xiàn)下面的情況：初始數據有序時，花費的時間反而最多。A.堆排序B.冒泡排序C.快速排序D.Shell排序（19）數據表A中有10000個元素，如果僅要求求出其中最大的10個元素，則采用_____算法最節(jié)省時間。A.堆排序B.希爾排序C.快速排序D.直接插入排序（20）如果只想得到1024個元素組成的序列中第5個最小袁術之前的部分排列的序，用_____方法最快。A.冒泡排序B.快速排序C.簡單選擇排序D.堆排序8.2填空題（1）當待排序的紀錄數較大，排序碼較隨機且對穩(wěn)定性不做要求時，宜采用_____排序；當待排序的紀錄數較大，存儲空間允許且要求排序穩(wěn)定時，宜采用____