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

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

設有一個棧，元素的進棧次序為A,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向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點時，應執(zhí)行—B___。hs->next=s;s->next=hs;hs=s;s->next=hs->next;hs->next=s;s->next=hs;hs=hs->next;在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為—D。A.rear%n==front B.(front+l)%n==rearC.rear%n-1==frontD.(rear+l)%n==front在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為___C—。A.rear%n==front B.front+l=rearC.rear==front D.(rear+l)%n=front在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為A___。A.front=front->nextB.rear=rear->nextC.rear=front->nextD.front=rear->nextC.rear=front->nextD.front=rear->next18.設二維數(shù)組A[0???m-1][0???n-1]按行優(yōu)先順序存儲在內(nèi)存中，第一個元素的地址為p，每個元素占k個字節(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)先順序存儲，則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.*，按列順序壓縮存儲在數(shù)組Sa[0?"(n+1)n/2]中，則非零元素a..的地址為(B)。(設每個元素占d個字節(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.設有廣義表D=(a,b,D)，其長度為(B)，深度為(A)。A.無窮大 B.3 C.2 D.522.廣義表A=((x,(a,B)),(x,(a,B),y))，則運算head(head(tail(A)))的結(jié)果為(A)。A.x B.(a,B)稀疏矩陣一般的壓縮存儲方法有兩種,A.x B.(a,B)稀疏矩陣一般的壓縮存儲方法有兩種,A.二維數(shù)組和三維數(shù)組C.三元組和十字鏈表一個廣義表的表頭總是一個(D)。A.廣義表 B.元素一個廣義表的表尾總是一個(A)。A.廣義表 B.元素(x,(a,B)) D.A即(C九三元組和散列散列和十字鏈表空表 D.元素或廣義表C.空表 D.元素或廣義表在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為(C)個。TOC\o"1-5"\h\zA.4 B.5 C.6 D.7假設在一棵二叉樹中，雙分支結(jié)點數(shù)為15,單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為(B)個。A.15 B.16 C.17 D.47假定一棵三叉樹的結(jié)點數(shù)為50,則它的最小高度為(C九A.3 B.4 C.5 D.6用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中R[1..n]，結(jié)點R[i]若有左孩子，其左孩子的編號為結(jié)點(B)。A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為(D九A.24 B.48 C.72 D.53設n,m為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中n在m前的條件是(B九A.n在m右方 B.n在m左方C.n是m的祖先 D.n是m的子孫如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的前序就是F中結(jié)點的(B)。A.中序B.前序 C.后序 D.層次序在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有頂點的入度數(shù)之和為(A)。A. s B. s-1 C.s+1 D.n在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有頂點的度數(shù)之和為(D)。A. s B. s-1 C.s+1 D.2s在一個具有n個頂點的無向完全圖中，所含的邊數(shù)為(C)。A.n B.n(n-1)C.n(n-1)/2D.n(n+1)/2在一個具有n個頂點的有向完全圖中，所含的邊數(shù)為(B)。A.n B.n(n-1) C.n(n-1)/2D.n(n+1)/2若一個圖中包含有k個連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂點，則必須調(diào)用(A)次深度優(yōu)先搜索遍歷的算法。A. k B. 1 C. k-1 D.k+1若要把n個頂點連接為一個連通圖，則至少需要(C)條邊。A. n B. n+1 C. n-1 D.2n在一個具有n個頂點和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素(又稱為有效元素)的個數(shù)為(D)。A. n B. nxe C. e D.2xe在一個具有n個頂點和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個數(shù)為(C)。A. n B. nxe C. e D.2xe在一個具有n個頂點和e條邊的有向圖的鄰接表中，保存頂點單鏈表的表頭指針向量的大小至少為(A)。A.n B.2n C.e D.2e對于一個有向圖，若一個頂點的度為k1，出度為k2,則對應逆鄰接表中該頂點單鏈表中的邊結(jié)點數(shù)為(C)。A.k1 B.k2 C.k1-k2D.k1+k2若一個圖的邊集為｛(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)｝，則從頂點A開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為(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若一個圖的邊集為｛(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)｝，則從頂點A開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為( 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若一個圖的邊集為｛<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>｝,則從頂點1開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為(A)。A. 1,2, 5,4,3 B. 1,2,3,4,5C. 1,2, 5,3,4 D. 1,4,3,2,5若一個圖的邊集為｛<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>｝，則從頂點1開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為(C)。A. 1,2,3,4,5 B. 1,2,4,3,5C. 1,2,4,5,3 D. 1,4,2,5,3由一個具有n個頂點的連通圖生成的最小生成樹中，具有(B)條邊。A.n B. n-1 C. n+1 D. 2xn已知一個有向圖的邊集為｛<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>｝，則由該圖產(chǎn)生的一種可能的拓撲序列為(A)。A.a,b,c,d,e B.a,b,d,e,bC.a,c,b,e,dD.a,c,d,b,e若查找每個元素的概率相等，則在長度為n的順序表上查找任一元素的平均查找長度為(D)。A.n B.n+1 C.(n-1)/2 D.(n+1)/2對于長度為9的順序存儲的有序表，若采用折半查找，在等概率情況下的平均查找長度為(A )的9分之一。A.20 B.18 C.25 D.22對具有n個元素的有序表采用折半查找，則算法的時間復雜度為(D)。A.O(n) B.O(n2) C.0(1) D.O(logn)2在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為n，它被均分為k個子表，每個子表的長度均為n/k，則索引查找的平均查找長度為(D)。A.n+k B.k+n/kC.(k+n/k)/2D.(k+n/k)/2+1在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為144,它被均分為12子表，每個子表的長度均為12,則索引查找的平均查找長度為(A)。A.13 B.24 C.12 D.79從具有n個結(jié)點的二叉排序樹中查找一個元素時，在平均情況下的時間復雜度大致為(C)。A.0(n)B.0(1)C.0(logn)D.0(m)2在一棵平衡二叉排序樹中，每個結(jié)點的平衡因子的取值范圍是(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計算哈希地址，則哈希地址等于3的元素個數(shù)(B)。A.1 B.2 C.3 D.4若根據(jù)查找表建立長度為m的哈希表，采用線性探測法處理沖突，假定對一個元素第一次計算的哈希地址為d，則下一次的哈希地址為(D)。A.d B.d+1 C.(d+1)/m D.(d+1)%m在對n個元素進行冒泡排序的過程中，第一趟排序至多需要進行(B)對相鄰元素之間的交換。A.n B.n-1 C.n+1 D.n/2在對n個元素進行直接插入排序的過程中，算法的空間復雜度為(A九A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)在對n個元素進行堆排序的過程中，時間復雜度為(D九A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)假定一個初始堆為(1,5,3,9,12,7,15,10)，要求從大到小排序，則進行第一趟堆排序后得到的結(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若對n個元素進行歸并排序，則進行歸并的趟數(shù)為(D九A.n B.n-1 C.n/2 D.「log?]若要對1000個元素排序，要求既快又穩(wěn)定，則最好采用(B)方法。A.直接插入排序 B.歸并排序C.堆排序D.快速排序若要對1000個元素排序，要求既快又節(jié)省存儲空間，則最好采用(C)方法。A.直接插入排序 B.歸并排序C.堆排序D.快速排序在平均情況下速度最快的排序方法為(D九A.簡單選擇排序 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é)點間的邏輯關系是一對一的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關系是一對多或多對多_。一個算法的效率可分為時間效率和—空間—效率。線性結(jié)構(gòu)中元素之間存在一對一關系；樹型結(jié)構(gòu)中元素之間存―一對多—關系；圖型結(jié)構(gòu)中元素之間存在多對多關系。 M下面程序段的時間復雜度是一一。i=s=0;while(s<n){i++；s+=i;}下面程序段的時間復雜度是一O(log3n)。i=1；while(i<=n)i=i*3;算法時間復雜度的分析通常有兩種方法，即一事后統(tǒng)計一，和 一的方法，通常我們對算法求時間復雜度時，采用后一種方法。在一個長度為n的順序表的第i個元素之前插入一個元素，需要后移—一n-i+1——個元素。在線性表的順序存儲中，元素之間的邏輯關系是通過物理存儲位置_決定的;在線性表的鏈接存儲中，元素之間的邏輯關系是通過 一決定的。在雙向鏈表中，每個結(jié)點含有兩個指針域，一個指向 一結(jié)點，另一個指向 一結(jié)點。當對一個線性表經(jīng)常進行存取操作，而很少進行插入和刪除操作時，則采用土^，存儲結(jié)構(gòu)為宜。相反，當經(jīng)常進行的是插入和刪除操作時，則采用存儲結(jié)構(gòu)為宜。線性表、棧和隊列都是線性結(jié)構(gòu)，可以在線性表的任何位置插入和刪除元素；對于棧只能在一棧頂一位置插入和刪除元素；對于隊列只能在隊尾位置插入元素和在一 位置刪除元素。設有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push,push,pop,push,pop,push,push后，輸出序列是2、3。無論對于順序存儲還是鏈式存儲的棧和隊列來說，進行插入或刪除運算的時間復雜度均相同為0(1)。對于一個二維數(shù)組A[m][n]，若按行序為主序存儲，則任一元素A[i][j]相對于A[0][0]的地址為iXn+j個元素位置—。一個廣義表為(a,(a,b),d,e,((i,j),k))，則該廣義表的長度為3,深度為又。

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

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