安徽理工大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提綱

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提綱一，選擇題數(shù)據(jù)結(jié)構(gòu)是指(A)。數(shù)據(jù)元素的組織形式 B.數(shù)據(jù)類型C.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu) D.數(shù)據(jù)定義數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為(C九存儲(chǔ)結(jié)構(gòu) B.邏輯結(jié)構(gòu)C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D.順序存儲(chǔ)結(jié)構(gòu)設(shè)語句x++的時(shí)間是單位時(shí)間，則以下語句的時(shí)間復(fù)雜度為(B九for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;O(1) B.O(n2) C.O(n) D.O(n3)計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是(C九數(shù)據(jù) B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.數(shù)據(jù)庫在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1<=i<=n)時(shí)，需向前移動(dòng)—A—個(gè)元素。n-i B.n-i+lC.n-i-1D.i線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址___D。A.必須是連續(xù)的 B.一定是不連續(xù)的C.部分地址必須是連續(xù)的 D?連續(xù)與否均可以從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較―C 個(gè)元素結(jié)點(diǎn)。A.n/2 B.n C.(n+1)/2D.(n-1)/2在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是—D__。p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)(若存在)，則需修改指針的操作為―A―。A.p->next=p->next->next; B.p=p->next;C.p=p->next->next; D.p->next=p;在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素(0<i<n+l)之前插入一個(gè)新元素時(shí)，需向后移動(dòng)_B__個(gè)元素。A.n-i B.n-i+l C.n-i-1 D.i在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行------B------s->next=p->next;p->next=sq->next=s;s->next=pp->next=s->next;s->next=pp->next=s;s->next=q在順序表中，只要知道__D___，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。

設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不可能的出棧序列C。A.A,B, C, D, E B. B,C,D, E, AC.E,A, B, C, D D. E,D,C, B, A向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行—B___。hs->next=s;s->next=hs;hs=s;s->next=hs->next;hs->next=s;s->next=hs;hs=hs->next;在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為—D。A.rear%n==front B.(front+l)%n==rearC.rear%n-1==frontD.(rear+l)%n==front在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為___C—。A.rear%n==front B.front+l=rearC.rear==front D.(rear+l)%n=front在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為A___。A.front=front->nextB.rear=rear->nextC.rear=front->nextD.front=rear->nextC.rear=front->nextD.front=rear->next18.設(shè)二維數(shù)組A[0???m-1][0???n-1]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，第一個(gè)元素的地址為p，每個(gè)元素占k個(gè)字節(jié)，則元素a..的地址為(A九A.p+[i*n+j-1]*k B.p+[(i-1)*n+j-1]*kC.p+[(jT)*n+iT]*kD.p+[j*n+i-1]*kC.p+[(jT)*n+iT]*kD.p+[j*n+i-1]*k若數(shù)組A[0?"m][0?"n]按列優(yōu)先順序存儲(chǔ)，則a..地址為(A九A.LOC(a)+[j*m+i] B.LOC(a)+[j*n+i]C.LOC(a00)+[(j-1)*n+i-1] D.LOC(a00)+[(j-1)*m+i-1]若下三角矩陣A.*，按列順序壓縮存儲(chǔ)在數(shù)組Sa[0?"(n+1)n/2]中，則非零元素a..的地址為(B)。(設(shè)每個(gè)元素占d個(gè)字節(jié))(j-2)(j-1)[(j-1)*n- 2 +i-1]*d(j—2)(j-1)[(j-1)*n- 少 +i]*d(j—2)(j—1)[(j-1)*n- 2 +i+1]*d(j—2)(j—1)[(j-1)*n- +i-2]*d21.設(shè)有廣義表D=(a,b,D)，其長(zhǎng)度為(B)，深度為(A)。A.無窮大 B.3 C.2 D.522.廣義表A=((x,(a,B)),(x,(a,B),y))，則運(yùn)算head(head(tail(A)))的結(jié)果為(A)。A.x B.(a,B)稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種,A.x B.(a,B)稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種,A.二維數(shù)組和三維數(shù)組C.三元組和十字鏈表一個(gè)廣義表的表頭總是一個(gè)(D)。A.廣義表 B.元素一個(gè)廣義表的表尾總是一個(gè)(A)。A.廣義表 B.元素(x,(a,B)) D.A即(C九三元組和散列散列和十字鏈表空表 D.元素或廣義表C.空表 D.元素或廣義表在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為(C)個(gè)。TOC\o"1-5"\h\zA.4 B.5 C.6 D.7假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為(B)個(gè)。A.15 B.16 C.17 D.47假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50,則它的最小高度為(C九A.3 B.4 C.5 D.6用順序存儲(chǔ)的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R[1..n]，結(jié)點(diǎn)R[i]若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)(B)。A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為(D九A.24 B.48 C.72 D.53設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是(B九A.n在m右方 B.n在m左方C.n是m的祖先 D.n是m的子孫如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是F中結(jié)點(diǎn)的(B)。A.中序B.前序 C.后序 D.層次序在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s，則所有頂點(diǎn)的入度數(shù)之和為(A)。A. s B. s-1 C.s+1 D.n在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s，則所有頂點(diǎn)的度數(shù)之和為(D)。A. s B. s-1 C.s+1 D.2s在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，所含的邊數(shù)為(C)。A.n B.n(n-1)C.n(n-1)/2D.n(n+1)/2在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，所含的邊數(shù)為(B)。A.n B.n(n-1) C.n(n-1)/2D.n(n+1)/2若一個(gè)圖中包含有k個(gè)連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂點(diǎn)，則必須調(diào)用(A)次深度優(yōu)先搜索遍歷的算法。A. k B. 1 C. k-1 D.k+1若要把n個(gè)頂點(diǎn)連接為一個(gè)連通圖，則至少需要(C)條邊。A. n B. n+1 C. n-1 D.2n在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素(又稱為有效元素)的個(gè)數(shù)為(D)。A. n B. nxe C. e D.2xe在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個(gè)數(shù)為(C)。A. n B. nxe C. e D.2xe在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量的大小至少為(A)。A.n B.2n C.e D.2e對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為k1，出度為k2,則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為(C)。A.k1 B.k2 C.k1-k2D.k1+k2若一個(gè)圖的邊集為｛(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)｝，則從頂點(diǎn)A開始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為(B)。A,B,C,F,D,E B.A,C,F,D,E,BC.A,B,D,C,F,E D.A,B,D,F,E,C若一個(gè)圖的邊集為｛(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)｝，則從頂點(diǎn)A開始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為( D)。A.A,B,C,D,E,F B.A,B,C,F,D,E

C.A,B,D,C,E,F D.A,C,B,F,D,E若一個(gè)圖的邊集為｛<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>｝,則從頂點(diǎn)1開始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為(A)。A. 1,2, 5,4,3 B. 1,2,3,4,5C. 1,2, 5,3,4 D. 1,4,3,2,5若一個(gè)圖的邊集為｛<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>｝，則從頂點(diǎn)1開始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為(C)。A. 1,2,3,4,5 B. 1,2,4,3,5C. 1,2,4,5,3 D. 1,4,2,5,3由一個(gè)具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有(B)條邊。A.n B. n-1 C. n+1 D. 2xn已知一個(gè)有向圖的邊集為｛<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>｝，則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨?A)。A.a,b,c,d,e B.a,b,d,e,bC.a,c,b,e,dD.a,c,d,b,e若查找每個(gè)元素的概率相等，則在長(zhǎng)度為n的順序表上查找任一元素的平均查找長(zhǎng)度為(D)。A.n B.n+1 C.(n-1)/2 D.(n+1)/2對(duì)于長(zhǎng)度為9的順序存儲(chǔ)的有序表，若采用折半查找，在等概率情況下的平均查找長(zhǎng)度為(A )的9分之一。A.20 B.18 C.25 D.22對(duì)具有n個(gè)元素的有序表采用折半查找，則算法的時(shí)間復(fù)雜度為(D)。A.O(n) B.O(n2) C.0(1) D.O(logn)2在索引查找中，若用于保存數(shù)據(jù)元素的主表的長(zhǎng)度為n，它被均分為k個(gè)子表，每個(gè)子表的長(zhǎng)度均為n/k，則索引查找的平均查找長(zhǎng)度為(D)。A.n+k B.k+n/kC.(k+n/k)/2D.(k+n/k)/2+1在索引查找中，若用于保存數(shù)據(jù)元素的主表的長(zhǎng)度為144,它被均分為12子表，每個(gè)子表的長(zhǎng)度均為12,則索引查找的平均查找長(zhǎng)度為(A)。A.13 B.24 C.12 D.79從具有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜度大致為(C)。A.0(n)B.0(1)C.0(logn)D.0(m)2在一棵平衡二叉排序樹中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是(A)。A.-1-1 B.-2-2 C.1~2 D.0~1若根據(jù)查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7計(jì)算哈希地址，則哈希地址等于3的元素個(gè)數(shù)(B)。A.1 B.2 C.3 D.4若根據(jù)查找表建立長(zhǎng)度為m的哈希表，采用線性探測(cè)法處理沖突，假定對(duì)一個(gè)元素第一次計(jì)算的哈希地址為d，則下一次的哈希地址為(D)。A.d B.d+1 C.(d+1)/m D.(d+1)%m在對(duì)n個(gè)元素進(jìn)行冒泡排序的過程中，第一趟排序至多需要進(jìn)行(B)對(duì)相鄰元素之間的交換。A.n B.n-1 C.n+1 D.n/2在對(duì)n個(gè)元素進(jìn)行直接插入排序的過程中，算法的空間復(fù)雜度為(A九A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)在對(duì)n個(gè)元素進(jìn)行堆排序的過程中，時(shí)間復(fù)雜度為(D九A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)假定一個(gè)初始堆為(1,5,3,9,12,7,15,10)，要求從大到小排序，則進(jìn)行第一趟堆排序后得到的結(jié)果為(A)。A.3,5,7,9,12,10,15,1A.3,5,7,9,12,10,15,13,5,9,7,12,10,15,13,7,5,9,12,10,15,1 D.3,5,7,12,9,10,15,1若對(duì)n個(gè)元素進(jìn)行歸并排序，則進(jìn)行歸并的趟數(shù)為(D九A.n B.n-1 C.n/2 D.「log?]若要對(duì)1000個(gè)元素排序，要求既快又穩(wěn)定，則最好采用(B)方法。A.直接插入排序 B.歸并排序C.堆排序D.快速排序若要對(duì)1000個(gè)元素排序，要求既快又節(jié)省存儲(chǔ)空間，則最好采用(C)方法。A.直接插入排序 B.歸并排序C.堆排序D.快速排序在平均情況下速度最快的排序方法為(D九A.簡(jiǎn)單選擇排序 B.歸并排序 C.堆排序D.快速排序二，填空題數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是隼合、樹 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)多或多對(duì)多_。一個(gè)算法的效率可分為時(shí)間效率和—空間—效率。線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系；樹型結(jié)構(gòu)中元素之間存―一對(duì)多—關(guān)系；圖型結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。 M下面程序段的時(shí)間復(fù)雜度是一一。i=s=0;while(s<n){i++；s+=i;}下面程序段的時(shí)間復(fù)雜度是一O(log3n)。i=1；while(i<=n)i=i*3;算法時(shí)間復(fù)雜度的分析通常有兩種方法，即一事后統(tǒng)計(jì)一，和 一的方法，通常我們對(duì)算法求時(shí)間復(fù)雜度時(shí)，采用后一種方法。在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移—一n-i+1——個(gè)元素。在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過物理存儲(chǔ)位置_決定的;在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過 一決定的。在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向 一結(jié)點(diǎn)，另一個(gè)指向 一結(jié)點(diǎn)。當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用土^，存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用存儲(chǔ)結(jié)構(gòu)為宜。線性表、棧和隊(duì)列都是線性結(jié)構(gòu)，可以在線性表的任何位置插入和刪除元素；對(duì)于棧只能在一棧頂一位置插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾位置插入元素和在一 位置刪除元素。設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push,push,pop,push,pop,push,push后，輸出序列是2、3。無論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來說，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為0(1)。對(duì)于一個(gè)二維數(shù)組A[m][n]，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素A[i][j]相對(duì)于A[0][0]的地址為iXn+j個(gè)元素位置—。一個(gè)廣義表為(a,(a,b),d,e,((i,j),k))，則該廣義表的長(zhǎng)度為3,深度為又。

18,一個(gè)稀疏矩陣為18,一個(gè)稀疏矩陣為，則對(duì)應(yīng)的三元組線性表為一(0，2，2)，(1，0，3)，(2，2，-1)，(2,3，5))_。已知廣義表A=((a,b,c),(d,e,f))，則運(yùn)算head(tail(tail(A)))=_e_。設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式以行序?yàn)橹餍虼鎯?chǔ)，a00為第一個(gè)元素，其存儲(chǔ)地址為0,每個(gè)元素占有1個(gè)存儲(chǔ)地址空間，則a85的地址為41。已知廣義表Ls=(a,(b,c,d),e)，運(yùn)用head和tail函數(shù)取出Ls中的原子b的運(yùn)算是head(head(tail(Ls)))。數(shù)組A[1???10,-2???6,2???8]以行優(yōu)先的順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是100,每個(gè)元素占3個(gè)存儲(chǔ)長(zhǎng)度的存儲(chǔ)空間，則元素A[5,0,7]的存儲(chǔ)地址為—。假定一棵樹的廣義表表示為A(B(E)，C(F(H，I，J)，G)，D)，則該樹的度為^^，樹的深度為」，終端結(jié)點(diǎn)的個(gè)數(shù)為一^，單分支結(jié)點(diǎn)的個(gè)數(shù)為^，雙分支結(jié)點(diǎn)的個(gè)數(shù)為^―，三分支結(jié)點(diǎn)的個(gè)數(shù)為，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為^^，其孩子結(jié)點(diǎn)為和結(jié)點(diǎn)。對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵 —二叉樹時(shí)具有最小高度，即為「log2(〃+1)1，當(dāng)它為一棵單支樹具有最大高度，即為n。由帶權(quán)為3,9,6,2,5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長(zhǎng)度為。在一棵二叉排序(搜索)樹上按中序遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為二^個(gè)，其中隊(duì)^_個(gè)用于鏈接孩子結(jié)點(diǎn)，n+1個(gè)空閑著。在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)個(gè)數(shù)為％，則％=—n2一。一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，單支樹形態(tài)達(dá)到最大深度， 完全一.叉樹形態(tài)達(dá)到最小深度。線索鏈表中的rtag域值為一時(shí)，表示該結(jié)點(diǎn)無右孩子，此時(shí)一RChild—域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的^倍。在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有n(n-1)/2條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_n(n-1)_條邊。假定一個(gè)有向圖的頂點(diǎn)集為｛a,b,c,d,e,f｝，邊集為｛<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>｝,則出度為0的頂點(diǎn)個(gè)數(shù)為__2-_,入度為1的頂點(diǎn)個(gè)數(shù)為_工_。在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要—n^條邊。表示圖的兩種存儲(chǔ)結(jié)構(gòu)為鄰接矩陣和鄰接表。若一個(gè)圖的頂點(diǎn)集為｛a,b,c,d,e,f｝,邊集為｛(a,b),(a,c),(b,c),(d,e)｝,則該圖含有個(gè)連通分量。對(duì)于具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在它們對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)的個(gè)數(shù)分別為—2e和―e—。在有向圖的鄰接表和逆鄰接表表示中，每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有 —和一入邊結(jié)點(diǎn)。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，當(dāng)分別采用鄰接矩陣和鄰接表表示時(shí)，求任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度分別為 ——和一O(e/n)——。假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣和鄰接表表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為一O(n2) 和—O(n+e) 。圖的深度優(yōu)先搜索遍歷算法是一種遞歸算法，圖的廣度優(yōu)先搜索遍歷算法需要使用隊(duì)列。對(duì)長(zhǎng)度為n的查找表進(jìn)行查找時(shí)，假定查找第i個(gè)元素的概率為？「,查找長(zhǎng)度(即在查找過程中依次同有關(guān)元素比較的總次數(shù))為匕，則在查找成功情況下的平均查找長(zhǎng)度的計(jì)算公式為YP.C,。_L=1 以折半查找方法在一個(gè)查找表上進(jìn)行查找時(shí)，該查找表必須組織成順序存儲(chǔ)的—。從有序表(12,18,30,43,56,78,82,95)中分別折半查找43和56元素時(shí)，其比較次數(shù)分別為_^和假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半查找，則對(duì)應(yīng)的判定樹高度為，最后一層的結(jié)點(diǎn)數(shù)為19。假定在索引查找中，查找表長(zhǎng)度為n，每個(gè)子表的長(zhǎng)度相等，設(shè)為s，則進(jìn)行成功查找的平均查找長(zhǎng)度為(n/s+s)/2+1。在索引查找中，假定查找表(即主表)的長(zhǎng)度為96，被等分為8個(gè)子表，則進(jìn)行索引查找的平均查找長(zhǎng)度為—11 。根據(jù)n個(gè)元素建立一棵二叉排序樹的時(shí)間復(fù)雜度大致為O(nlog^l)一。在一棵平衡二叉排序樹中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對(duì)值不超過_工_。假定對(duì)線性表(38,25,74,52,48)進(jìn)行哈希存儲(chǔ)，采用H(K)=K%7作為哈希函數(shù)，采用線性探測(cè)法處理沖突，則在建立哈希表的過程中，將會(huì)碰到5次存儲(chǔ)沖突。對(duì)線性表(18,25,63,50,42,32,90)進(jìn)行哈希存儲(chǔ)時(shí)，若選用H(K)=K%9作為哈希函數(shù)，則哈希地址為0的元素有—3—個(gè)，哈希地址為5的元素有—2—個(gè)。每次從無序子表中取出一個(gè)元素，把它插入到有序子表中的適當(dāng)位置，此種排序方法叫做』^排序；每次從無序子表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做盜『排序。每次直接或通過支點(diǎn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就交換它們的位置，此種排序方法叫做快速排序；每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法叫做歸并排序。對(duì)n個(gè)記錄進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)為n-1，最少的趟數(shù)為。假定一組記錄為(46,79,56,38,40,84)，則利用堆排序方法建立的初始小根堆為_。假定一組記錄為(46,79,56,38,40,84)，(往后冒泡)在冒泡排序的過程中進(jìn)行第一趟排序后的結(jié)果為。假定一組記錄為(46,79,56,38,40,80)，對(duì)其進(jìn)行快速排序的第一次劃分后的結(jié)果為[4038]46[567980_。假定一組記錄為(46,79,56,38,40,80,46,75,28,46)，對(duì)其進(jìn)行歸并排序的過程中，第三趟歸并后的第2個(gè)子表為—[2846]——。在所有排序方法中， 堆排序方法使數(shù)據(jù)的組織采用的是完全二叉樹的結(jié)構(gòu)。直接選擇排序方法能夠每次從無序表中順序查找出一個(gè)最小值。三，算法設(shè)計(jì)與應(yīng)用題1，設(shè)計(jì)將帶表頭的鏈表逆置算法。設(shè)單循環(huán)鏈表的頭指針為head，類型為L(zhǎng)inkList。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域作以修改，使其原前趨結(jié)點(diǎn)成為后繼。如要更改q結(jié)點(diǎn)的指針域時(shí)，設(shè)s指向其原前趨結(jié)點(diǎn)，p指向其原后繼結(jié)點(diǎn)，則只需進(jìn)行q->next=s;操作即可，算法描述如下：voidinvert(LinkList*head){〃逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist*p,*q,*s;q=head;p=head->next;while(p!=head)〃當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置{s=q;q=p;p=p->next;q->next=s;}p->next=q;

}已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA給出如圖A所示的森林的先根、后根遍