數(shù)據(jù)結(jié)構(gòu)習題及答案.doc

此文檔收集于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系網(wǎng)站刪除數(shù)據(jù)結(jié)構(gòu)習題及答案第1章 數(shù)據(jù)結(jié)構(gòu)一、選擇題1.算法指的是（）。A計算機程序 B解決問題的計算方法C排序方法 D解決問題的有限運算序列2.在數(shù)據(jù)的樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間為（ ）的關(guān)系。A 0:0 B 1:1 C 1:n D m:n3.數(shù)據(jù)的存儲結(jié)構(gòu)包括順序、鏈接、散列和（ ）4種基本類型。A索引 B數(shù)組 C集合 D向量4.一個數(shù)組元素ai與（ ）的表示等價。A &a+i B *(a+i) C *a+i D a+i5.若只需要利用形參間接訪問實參指針所指向的對象，而形參本身具有相應(yīng)的存儲空間，則應(yīng)把形參變量說明為（ ）參數(shù)。A指針 B引用 C值 D指針引用6.若只需要利用形參實現(xiàn)對實參值的拷貝，函數(shù)體操作形參時與實參無關(guān)，則應(yīng)把形參變量說明為（ ）參數(shù)。A指針 B引用 C值 D指針引用7.下面程序的時間復雜性的量級為（）。int i=0，s1=，s2=0；while（i+n） if (i%2) s1+=i;else s2+=i;A.O(1) B.O(1bn) C.O（n） D.O(2n)8.下面程序段的時間復雜度為（ ）。 for(int i=0;im;i+) for(int j=0;jn;j+) aij=i*j;A.O(m2) B.O(n2) C.O(m+n) D.O(m*n)9.執(zhí)行下面程序段時，S語句的執(zhí)行次數(shù)為（）。 for(int i=1;i=n;i+) for(int j=1,jnext=ph; B. p-next=ph; ph=p;C. p-next=ph; p=ph; D. p-next=ph-next; ph-next=p;21.在一個表頭指針為ph的單鏈表中，若要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，則執(zhí)行（）操作。A. q-next=p-next; p-next=q; B. p-next=q-next; q=p;C. q-next=p-next; p-next=q; D. p-next=q-next; q-next=p;22.在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點（若存在的話），則執(zhí)行（）操作。A. p=q-next; p-next=q-next; B. p=q-next; q-next=p;C. p=q-next; q-next=p-next; D. q-next=q-next-next; q-next=q;23.在一個帶頭結(jié)點的循環(huán)雙向鏈表中，若要在指針p所指向的結(jié)點之后插入一個q指針所指向的結(jié)點，則需要對q-next賦值為（）。A. P-prior B. p-nextC. p-next-next D.p-prior-prior24.在一個帶頭結(jié)點的循環(huán)雙向鏈表中，若要在指針p所指向的結(jié)點之前插入一個q指針所指向的結(jié)點，則需要對p-prior-next賦值為（）。A. q B. p C. p-next D. p-prior25. 在一個帶頭結(jié)點的循環(huán)雙向鏈表中，若要刪除指針p所指向的結(jié)點則執(zhí)行（）操作。A. p-prior-next=p-next; p-next-prior=p-prior;B. p-next-prior=p; p-next=p-next-next;C. p-prior-next=p; p-next=p-next-prior;D. p=p-next; p-prior-next=p-prior;26.棧的插入和刪除操作在（）進行。A. 棧頂 B. 棧底C. 任意位置D. 指定位置27.當利用大小為N的數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則向這個棧插入一個元素時，首先應(yīng)執(zhí)行（）語句修改top指針。A.top+ B.top- C.top=0 D.top=N-128.假定利用數(shù)組aN順序存儲一個棧，用top表示棧頂指針，用top=N+1表示棧空，該數(shù)組所存儲的棧的最大長度為N，則表示棧滿的條件為（）。A.top=1 B.top=-1 C.top=0 D.top=N-129. 假定利用數(shù)組aN順序存儲一個棧，用top表示棧頂指針，用top=-1表示?？?，并已知棧未滿，當元素x進棧時所執(zhí)行的操作為（）。A.a-top=x B.atop-=x C.a+top=x D.atop+=x30. 假定利用數(shù)組aN順序存儲一個棧，用top表示棧頂指針，用top=-1表示棧空，并已知棧未空，當退棧并返回棧頂元素時所執(zhí)行的操作為（）。A return a-top B return atop- C return a+top D return atop+31.假定一個鏈式棧的棧頂指針用top表示，該鏈式棧為空的條件（）。A.top！=NULL; B. top=top-next; C. top= NULL; D. top！= top-next;32.假定一個鏈式棧的棧頂指針用top表示，每個結(jié)點結(jié)構(gòu)為,當p所指向的結(jié)點進棧時，執(zhí)行的操作為（）。A. p-next=top; top=top-next; B. top=p; p-next=top;C. p-next=top-next; top-next=p; D. p-next=top; top=p;33.假定一個鏈式棧的棧頂指針用top表示，每個結(jié)點結(jié)構(gòu)為,退棧時所執(zhí)行的操作為（）。A.top-next=top；B.top=top-data;C.top=top-next; D. top-next=top-next-next;34.若讓元素1，2，3，4依次進棧，則出棧次序不可能出現(xiàn)（ ）的情況。A.3，2，1，4 B.2，1，4，3 C.4，3，2，1 D.1，4，2，3.35.在一個順序循環(huán)隊列中，隊首指針指向隊首元素的（）位置。A前一個 B后一個 C當前 D最后36.當利用大小為N的數(shù)組循環(huán)存儲一個隊列時，該隊列的最大長度為（）。A.N-2 B.N-1 C.N D.N+137.從一個順序循環(huán)隊列中刪除元素時，首先需要（）。A.前移隊首指針 B.后移隊首指針C.取出隊首指針所指位置上的元素 D.取出隊尾指針所指位置上的元素38.假定一個順序循環(huán)隊列的隊首和隊尾指針分別用f和r表示，則判斷隊空的條件為（）。A.f+1=r B.r+1=f C.f=0 D.f=r39.假定一個順序循環(huán)隊列存儲于數(shù)組aN，其隊首和隊尾指針分別用f和r表示，則判斷隊滿的條件為（）。A.（r-1）%N=f B.（r+1）%N=f C.（f-1）%N=r D.（f+1）%N=r40.假定利用數(shù)組aN循環(huán)順序存儲一個隊列，其隊首和隊尾指針分別用f和r表示，并已知隊列未滿，當元素x入列時所執(zhí)行的操作為（）。A.a+r%N=x B.ar+%N=x C.a-r%N=x D.ar-%N=x41.假定利用數(shù)組aN循環(huán)順序存儲一個隊列，其隊首和隊尾指針分別用f和r表示，并已知隊列未空，當出列并返回隊首元素時所執(zhí)行的操作為（）。A.return a+r%N B.return a-r%N C.return a+f%N D.return af+%N42.假定一個鏈式隊列的隊首和隊尾指針分別為front和rear，則判斷隊空的條件為（）。A.front=rear B.front！=NULL C.rear！=NULL D.front=NULL43.假定一個鏈式隊列的隊首和隊尾指針分別為front和rear，每個結(jié)點結(jié)構(gòu)為,當出列時所進行的操作為（）。A.front=front-next B.rear=rear-nextC.front-next =rear；rear=rear-nextD.front=front-next；front-next =rear；44.假定一個帶頭結(jié)點的循環(huán)鏈式隊列的隊首和隊尾指針分別用front和rear表示，則判斷對空的條件為（）。A.front=rear-next B.rear=NULL C. front=NULL D. front =rear45.假定一個鏈式隊列的隊首和隊尾指針分別為front和rear，每個結(jié)點結(jié)構(gòu)為包含值域data和指針域next,則使p所指結(jié)點入列所執(zhí)行的操作為（）。A.p-next=NULL；rear=rear-next=p；B.p-next=rear-next；rear=rear-next=p；C.p-next=front；front=p；D.p-next=front-next；front-next=p；46.在一個長度為N的數(shù)組空間中，循環(huán)順序存儲著一個隊列，該隊列的隊首和隊尾指針分別用front和rear表示，則該隊列中數(shù)組元素個數(shù)為（）。A.（rear-front）%N B.（rear-front+N）%NC.（rear+N）%N D.（front+N）%N47.二維數(shù)組A12,10采用行優(yōu)先存儲，每個數(shù)據(jù)元素占用4個存儲單元，該數(shù)組的首地址（即A0，0的地址）為1200，則A6，5的地址為（）。A.1400 B.1404 C.1372 D.146048.有一個MN的矩陣A，若采用行優(yōu)先進行順序存儲，每個元素占用8個字節(jié)，則Aij(1iM,1jN)元素的相對字節(jié)地址（相對首元素地址而言）為（）。A.（i-1）N+j）8 B.（i-1）N+j-1）8C.（iN+j-1）8 D.（i-1）N+j+1）849.有一個NN的下三角矩陣A，若采用行優(yōu)先進行順序存儲，每個元素占用k個字節(jié)，則Aij(1iN,1ji)元素的相對字節(jié)地址（相對首元素地址而言）為（）。A.（i（i+1）/2+j-1）4 B.（ii/2+j）4C.（i（i-1）/2+j-1）4 D.（i（i-1）/2+j）450.樹中所有結(jié)點的度等于所有結(jié)點數(shù)加（）。A.0 B.1 C.-1 D.251.在一棵樹中，（）沒有前驅(qū)結(jié)點。A.樹枝結(jié)點 B.葉子結(jié)點 C.樹根結(jié)點 D.空結(jié)點52.在一棵樹中，每個結(jié)點最多有（）個前驅(qū)結(jié)點。A.0 B.1 C.2 D.任意多個53.在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（）。A.2 B.1 C.0 D.-154.在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于（）。A.n B.n-1 C.n+1 D.2n55.在一棵具有n個結(jié)點的二叉樹的第i層上，最多具有（）個結(jié)點。A.2i B.2i+1 C.2i-1 D.2n56.在一棵深度為h的完全二叉樹中，所含結(jié)點個數(shù)不小于（）。A.2h B.2h+1 C.2h-1 D.2h-157.在一棵深度為h的完全二叉樹中，所含結(jié)點個數(shù)不大于（）。A.2h B.2h+1 C.2h-1 D.2h-158.在一棵具有35個結(jié)點的完全二叉樹中，該樹的深度為（）。A.6 B.7 C.5 D.859.在一棵完全二叉樹中，若編號為i的結(jié)點存在左孩子，則左孩子結(jié)點編號為（）。A.2i B.2i-1 C.2i+1 D.2i+260.在一棵完全二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子結(jié)點編號為（）。A.2i B.2i-1 C.2i+1 D.2i+261.在一棵完全二叉樹中，對于編號為i（i1）的結(jié)點其雙親結(jié)點的編號為（）。A.（i+1）/2 B.（i-1）/2 C.i%2 D.i/262.有如圖1.1所示的一棵二叉樹，則該二叉樹所含單支結(jié)點數(shù)為（）。A.2 B.3 C.4 D.563.有如圖1.2所示的一棵二叉樹，則該二叉樹的中序遍歷序列為（）。A. ABCDEFG B. CDBGFEA C. CBDAEGF D. ABECDFG64.有如圖1.2所示的一棵二叉樹，則該二叉樹的先序遍歷序列為（）。A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG65.有如圖1.2所示的一棵二叉樹，則該二叉樹的后序便利序列為（）。A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG66.利用n個值生成的哈夫曼樹中共有（）個結(jié)點。A.n B.n+1 C.2n D.2n-167.利用3，6，8，12這4個值作為葉子結(jié)點的權(quán)，生成一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（）。A.55 B.29 C.58 D.3868.在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有的入度數(shù)之和為（）。A.s B.s-1 C.s+1 D.n69.在一個具有n個頂點的有向圖中，若所有頂點的出度數(shù)之和為s，則所有的度數(shù)之和為（）。A. s B. s -1 C. s +1 D.2s70.在一個具有n個頂點的無向圖中，若具有e條邊，則所有頂點的度數(shù)為（）。A.n B.e C.n+e D.2e71.在一個具有n個頂點的無向完全圖中，所含的邊數(shù)為（）。A.n B.n（n-1） C.n（n-1）/2 D.n（n+1）/2 72.在一個具有n個頂點的有向完全圖中，所含的邊數(shù)為（）。A.n B.n（n-1） C.n（n-1）/2 D.n（n+1）/273.在一個具有n個頂點的無向連通圖中，它包含的連通分量的個數(shù)為（）。A.0 B.1 C.n D.n+174.若有一個圖中包含k個連通分量，若按照深度優(yōu)先搜索的方法訪問所有頂點，則必須調(diào)用（）次深度優(yōu)先搜索遍歷的算法。A.k B.1 C.k-1 D.k+175.若要把n個頂點連接為一個連通圖，則至少需要（）條邊。A.n B.n+1 C.n-1 D.2n76.在一個具有n個頂點和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素（又稱為有效元素）的個數(shù)為（）。A.n B.ne C.e D.2e77.在一個具有n個頂點和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素的個數(shù)為（）。A.n B.ne C.e D.2e78.在一個具有n個頂點和e條邊的無向圖的鄰接矩陣中，邊結(jié)點的個數(shù)為（）。A.n B.ne C.e D.2e79.對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應(yīng)鄰接表中該頂點單鏈表的邊數(shù)結(jié)點為（）。A.k1 B.k2 C.k1-k2 D.k1+k280.對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應(yīng)逆鄰接表中該頂點單鏈表的邊數(shù)結(jié)點為（）。A.k1 B.k2 C.k1-k2 D.k1+k281.對于一個無向圖，下面（）的說法是正確的。A.每個頂點的入度等于出度 B.每個頂點的度等于入度和出度之和C.每個頂點的入度為0 D.每個頂點的出度為082.在一個有向圖的鄰接表中，每個頂點單鏈表中結(jié)點的個數(shù)等于該頂點的（）。A.出邊數(shù) B.入邊數(shù) C.度數(shù) D.度數(shù)減一83.若一個圖的邊集為（A，B）（A，C）（B，D）（C，F(xiàn)）（D，E）（D，F(xiàn)），則從頂點A開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為（）。A. ABCFDE B. ACFDEB C. ABDCFE D. ABDFEC84.若一個圖的邊集為（A，B）（A，C）（B，D）（C，F(xiàn)）（D，E）（D，F(xiàn)），則從頂點A開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為（）。A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE85.若一個圖的邊集（1，2）（1，4）（2，5）（3，1）（3，5）（4，3），則從頂點1開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為（）。A.1，2，5，4，3 B.1，2，3，4，5 C.1，2，5，3，4 D.1，4，3，2，586.若一個圖的邊集（1，2）（1，4）（2，5）（3，1）（3，5）（4，3），則從頂點1開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為（）。A. 1，2，3，4，5 B. 1，2，4，3，5 C. 1，2，4，5，3 D. 1，4，2，5，387.由一個具有n個頂點的連通圖生成的最小樹中有（）條邊。A.n B.n-1 C.n+1 D.2n88.若查找每一個元素的概率相等，則在長度為n的順序表上查找任一元素的平均查找長度為（）。A. n B. n+1 C. (n-1)/2 D. (n+1)/289.對長度為n的單鏈有序表，若查找每個元素的概率相等，則查找任一個元素的平均查找長度為（）。A. n/2 B.（n+1）/2 C. (n-1)/2 D.n/490.對于長度為9的順序存儲的有序表，若采用二分查找，在等概率情況下的平均查找長度為（）的值除以9。A.20 B.18 C.25 D.2291.對于長度為18的順序存儲的有序表，若采用二分查找，則查找第15個元素的查找長度為（）。A.2 B.3 C.4 D.692.對于順序存儲的有序表（5，12，20，26，37，42，46，50，64），若采用二分查找，則查找元素26的查找長度為（）。A.2 B.3 C.4 D.593.在分塊查找中，若用于保存數(shù)據(jù)元素的主表長度為n，它被分為k個子表，每個子表的長度均為n/k，若用順序查找確定塊，則分塊查找的平均查找長度為（）。A.n+k B.k+n/k C.（k+n/k）/2 D.（k+n/k）/2+194.在分塊查找中，若用于保存數(shù)據(jù)元素的主表長度為144，它被分為12個子表，每個子表的長度均為12，若用順序查找確定塊，則分塊查找的平均查找長度為（）。A.13 B.24 C.12 D.7995.在一棵深度為h的具有n個元素的二叉排序樹中，查找所有元素的最長查找長度為（）。A.n B.lbn C.（h+1）/2 D.h96.在一棵平衡二叉排序樹中，每個結(jié)點的平衡因子的取值范圍是（）。A.-11 B.-22 C.12 D.0197.若根據(jù)查找表（23，44，36，48，52，73，64，58）建立線性哈希表，采用H（K）=K%13計算哈希地址，則元素64的哈希地址為（）。A.4 B.8 C.12 D.1398.若根據(jù)查找表（23，44，36，48，52，73，64，58）建立線形哈希表，采用H（K）=K%13計算哈希地址，則哈希地址為3的元素個數(shù)為（）。A.1 B.2 C.3 D.499.若根據(jù)查找表建立長度為m的線性哈希表，采用線性探測再哈希法處理沖突，假定對一個元素第一次計算的哈希地址為d，則下一次的哈希地址為（）。A.d B.d+1 C.（d+1）/m D.（d+1）%m100.在采用線性探測再哈希法處理沖突的線性哈希表上，假定裝填因子a的值為0.5，則查找任一個元素的平均查找長度為（）。A.1 B.1.5 C.2 D.2.5101.在哈希查找中，平均查找長度主要與（）有關(guān)。A.哈希表長度 B.哈希元素個數(shù) C.裝填因子 D.處理沖突方法102.若對n個元素進行直接插入排序，則進行第i趟排序過程前，有序表中元素的個數(shù)為（）。A.i B.i+1 C.i-1 D.1103.若對n個元素進行直接插入排序，在進行第i趟排序時，為尋找插入位子最多需要進行（）次元素的比較，假定第0號元素放有待查的鍵值。A. i B.i-1 C.i+1 D.1104.若對n個元素進行直接插入排序，在進行第i趟排序時,假定元素ri+1的插入位置為rj，則需要移動元素的次數(shù)為（）。A.j-i B.i-j-1 C.i-j D.i-j+1105.若對n個元素進行直接插入排序，在進行任意一趟排序的過程中，為尋找插入位置而需要的時間復雜度為（）。A.O（1） B.O（n） C.O（n2） D. O（lbn）106.在對n個元素進行直接插入排序的過程中，共需要進行（）趟。A.n B.n+1 C.n-1 D.2n107.對n個元素進行直接插入排序的時間復雜度為（）。A.O（1） B.O（n） C.O（n2） D. O（lbn）108.在對n個元素進行冒泡排序的過程中，第一趟排序至多進行（）對相鄰元素之間的交換。A .n B.n-1 C.n+1 D.n/2109.在對n個元素進行冒泡排序的過程中，最壞情況下的時間復雜度為（）。A.O（1） B.O（lbn） C.O（n2） D.O（n）110.在對n個元素進行冒泡排序的過程中，至多需要（）趟完成。A .1 B.n C.n-1 D.n/2111.在對n個元素進行快速排序的過程中，最好情況下需要進行（）趟。A.n B.n/2 C.lbn D.2n112.在對n個元素進行快速排序的過程中，最壞情況下需要進行（）趟。A.n B.n-1 C.n/2 D.lbn113.對下列4個序列進行快速排序，各以第一個元素為基準進行第一次劃分，則在該次劃分過程中需要移動元素次數(shù)最多的序列為（）。A.1，3，5，7，9 B.9，7，5，3，1 C.5，3，1，7，9 D.5，7，9，1，3114.假定對元素序列（7，3，5，9，1，12，8，15）進行快速排序，則進行第一次劃分后，得到的左區(qū)間中元素的個數(shù)為（）。A.2 B.3 C.4 D.5115.在對n個元素進行簡單選擇排序的過程中，在第i趟需要從（）個元素中選擇出最小值元素。A.n-i+1 B.n-i C.i D.i+1116.若對n個元素進行簡單選擇排序，則進行任一趟排序的過程中，為尋找最小值元素所需要的時間復雜度為（）。A.O（1） B.O（lbn） C.O（n2） D. O（n）117.假定一個初始堆為（1，5，3，9，12，7，15，10），則進行第一趟堆排序后得到的結(jié)果為（）。A.3，5，7，9，12，10，15，1 B.3，5，9，7，12，10，15，1C.3，7，5，9，12，10，15，1 D.3，5，7，12，9，10，15，1118.若一個元素序列基本有序，則選用（）方法較快。A.直接插入排序 B.簡單選擇排序 C.堆排序 D.快速排序119.若要從1000個元素中得到10個最小元素，最好采用（）方法。A.直接插入排序 B.簡單選擇排序 C.堆排序 D.快速排序120.在平均情況下速度最快的排序方法為（）。A.簡單選擇排序 B.冒泡排序 C.堆排序 D.快速排序二填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)可分為_和_兩大類。2.數(shù)據(jù)的存儲結(jié)構(gòu)被分為_，_，_和_4種。3.在下面的程序段中，s=s+p語句被執(zhí)行次數(shù)為_，p*=j語句的執(zhí)行次數(shù)為_,該程序的復雜度為_。int i=0，s=0；while（+i=n） int p=1;for(int j=1;j=i;j+)p*=j;s=s+p;4.一種數(shù)據(jù)結(jié)構(gòu)的元素集合K和它的二元關(guān)系R為：K=a,b,c,d,e,f,g,h R=，則該數(shù)據(jù)結(jié)構(gòu)具有_結(jié)構(gòu)。5.線性表的兩種存儲結(jié)構(gòu)分別為_和_。6.線性表的順序存儲結(jié)構(gòu)稱為_，鏈式存儲結(jié)構(gòu)稱為_。7.若經(jīng)常需要對線性表進行插入和刪除運算，則最好采用_存儲結(jié)構(gòu)，若經(jīng)常需要對線性表進行查找運算，則最好采用_存儲結(jié)構(gòu)。8.對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為_。9.對于一個單鏈表存儲的線性表，在表頭插入結(jié)點的時間復雜度為_，在表尾插入結(jié)點的時間復雜度為_。10.在線性表的單鏈表存儲中，若一個元素所在結(jié)點的地址為p，則其后的斷結(jié)點的地址為_。11.在以HL為頭指針的帶頭結(jié)點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為_和_。12.在_鏈表中，既可以通過設(shè)定一個頭指針，也可以通過設(shè)定一個尾指針來確定它，即通過頭指針或尾指針可以訪問到該鏈表的每個結(jié)點。13.在一個單鏈表中刪除指針p所指向結(jié)點的后繼結(jié)點時，需要把_的值賦給p-next指針域。14.在一個單鏈表中指針p所指向結(jié)點的后面插入一個指針q所指向的節(jié)點時，首先把_的值賦給p-next，然后把_的值賦給p-next。15.假定指向單鏈表中第一個結(jié)點的頭指針為head，則像該單鏈表的表頭插入指針p所指向的新結(jié)點時，首先執(zhí)行_賦值操作，然后執(zhí)行_賦值操作。16.訪問一個順序表和一個單鏈表中第i個元素的時間復雜度分別為_和_。17.在一個帶頭結(jié)點的循環(huán)單鏈表中，在表頭插入或刪除與在其它位置插入和刪除，其操作過程是否相同？_。18.在雙向鏈表中每個結(jié)點包含有兩個指針域，一個指向其_結(jié)點，另一個指向其_結(jié)點。19.在一個雙向鏈表中指針p所指向的結(jié)點之后插入一個指針q所指向的結(jié)點時，需要對p-next-prior指針域賦值為_。20.在一個雙向鏈表中刪除指針p所指向的結(jié)點時，需要對p-next-prior指針域賦值為_。21.棧又稱為_表，隊列又稱為_表。22.在一個用一維數(shù)組aN表示的順序棧中，該棧所含元素的個數(shù)最少為_個，最多為_個。23.像一個順序棧插入一個元素時，首先使_后移一個位置，然后把新元素_到這個位子。24.從一個棧刪除元素時，首先取出_，然后再使_減一。25.一個順序棧存儲一個一維數(shù)組aM中，棧頂指針用top表示，當棧頂指針等于_時為空棧，棧頂指針為_時為滿棧。26.假定一個鏈棧的棧頂指針為top，每個結(jié)點包含值域data和指針域next，當p所指向的結(jié)點入棧時，則首先執(zhí)行_操作，然后執(zhí)行_操作。27. 假定一個鏈棧的棧頂指針為top，每個結(jié)點包含值域data和指針域next，當進行出棧運算時（假定棧非空），需要把棧頂指針修改為_的值。28.設(shè)元素1，2，3，4，5依次進棧，若要在輸出端得到序列34251，則應(yīng)進行的操作序列為Push(s,1),Push(s,2),_,Pop(s),Push(s,4),Pop(s),_,_,Pop(s),Pop(s)。29.設(shè)元素a，b，c，d依次進棧，若要在輸出端得到序列cbda，則應(yīng)進行的操作序列為push(s,a),push(s,b),push(s,c),_,_，_pop(s),pop(s)。30.隊列的插入操作在_進行，刪除操作在_進行。31.一個順序循環(huán)隊列存在于aM中,假定隊首和隊尾指針分別為front和rear，則判斷對空的條件為_，判斷對滿的條件為_。32.一個順序循環(huán)隊列存在于aM中,假定隊首和隊尾指針分別為front和rear，則求出隊首和隊尾指針的下一個位置的計算公式分別為_和_。33.在一個用一維數(shù)組aN存儲的順序循環(huán)隊列中，該隊列中的元素個數(shù)最少為_個，最多為_個。34.向一個順序循環(huán)隊列中插入元素時，需要首先移動_，然后再向它所指位置_新元素。35.在一個空鏈隊列中，假定隊首和隊尾指針分別為f和r，當向他插入一個新結(jié)點*p時，則首先執(zhí)行_操作，然后執(zhí)行_操作。36.在一個帶頭結(jié)點的循環(huán)鏈隊列中，假定隊首和隊尾指針分別為f和r，當向它插入一個新結(jié)點*p時，則首先執(zhí)行_操作，然后執(zhí)行_操作。37.假定front和rear分別為一個鏈隊列的對首和隊尾指針，則該鏈隊列中只有一個結(jié)點的條件為_。38.在一個鏈棧中，若棧頂指針等于NULL則為_；在一個鏈隊列中，若對首和隊尾的指針相同，則表示該隊列為_或該隊列_。39.一個二維數(shù)組A15，10采用行優(yōu)先方式存儲，每個數(shù)據(jù)元素占用4個存儲單元，以該數(shù)組第3列第0行的地址（即A3，0的地址）1000為首地址，則A12，9的地址為_。40.在二維數(shù)組a10,20中，每個元素占8個存儲單元，假定該數(shù)組的首地址為2000，則數(shù)組元素a6,15的字節(jié)地址為_。41.有一個88的下三角矩陣A，若將其進行順序存儲于一維數(shù)組aN中，則N的值為_。42.有一個1010的下三角矩陣A，若將其進行順序存儲于一維數(shù)組aN中，則Aij（1i10,1ji）存儲于a中的下標位置為_。43.有一個88的下三角矩陣A，若將其進行順序存儲，每個元素占用4個字節(jié)，則A5，4元素的相對字節(jié)地址為（相對首元素地址而言）_。44.一種數(shù)據(jù)結(jié)構(gòu)的元素集合K和它的二元關(guān)系R為：K=a,b,c,d,e,f,g,hR=，則該數(shù)據(jù)結(jié)構(gòu)具有_結(jié)構(gòu)。45.對于一棵具有n個結(jié)點的樹，則該樹中所有結(jié)點的度數(shù)之和為_。46.在一棵樹中，_結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有并且只有一個_，可以有人以多個_結(jié)點。47.如圖1.3所示為一棵樹，該樹的葉子結(jié)點數(shù)為_個，單支結(jié)點數(shù)為_個，雙分支結(jié)點數(shù)為_個，三分支結(jié)點數(shù)為_個。48.如圖1.3所示的一棵樹，結(jié)點K的所有祖先的結(jié)點數(shù)為_個，結(jié)點B的所有子孫結(jié)點數(shù)為_個。49.如圖1.3所示的一棵樹，結(jié)點D和X的層數(shù)分別為_和_。50.如圖1.4所示的一棵樹，則樹中所含的結(jié)點數(shù)為_個，樹的深度為_，樹的度為_。51.如圖1.4所示的一棵樹，則度為3，2，1，0的結(jié)點數(shù)分別為_，_，_。52.如圖1.4所示一棵樹，則結(jié)點H的雙親為_，孩子結(jié)點為_。53.在一棵二叉樹中，假定雙分支結(jié)點數(shù)為5個，單分支結(jié)點數(shù)為6個，則葉子結(jié)點數(shù)為_。54.對于一棵二叉樹，若一個結(jié)點的編號i，若它的左孩子結(jié)點存在，則其編號為_，若右孩子結(jié)點存在，則其編號為_，若雙親結(jié)點存在，則其編號為_。55.在一棵二叉樹中，第5層上的結(jié)點數(shù)最多為_。56.假定一棵二叉樹的結(jié)點數(shù)為18，則它的最小深度為_，最大深度為_。57.如圖1.5所示為一棵二叉樹，則E結(jié)點的雙親結(jié)點數(shù)為_，左孩子結(jié)點為_，右孩子結(jié)點為_。58.如圖1.5所示為一棵二叉樹，它含有雙支結(jié)點_個，單分支結(jié)點_個，葉子結(jié)點_個。59.假定一棵二叉樹順序存儲在一維數(shù)組a中，若a5元素的左孩子存在則對應(yīng)的元素為_，若右孩子存在則對應(yīng)的元素為_，雙親元素為_。60.若對一棵二叉樹從0開始進行結(jié)點編號，并按此編號把它存儲到一維數(shù)組a中，即編號為0的結(jié)點存儲到a0中，依次類推，則ai元素的左孩子為_，右孩子為_，雙親元素（i0）為_。61.對于一棵具有n個結(jié)點的二叉樹，對應(yīng)_二叉鏈表中指針總數(shù)為_個，其中_個用于指向孩子結(jié)點，_個指針空閑。62.在一棵深度為h的完全平衡二叉樹中，最少含有_個結(jié)點，最多含有_個結(jié)點。63.一棵深度為5的完全二叉樹中的結(jié)點數(shù)最少為_個，最多為_個。64.如圖1.6所示為一棵二叉樹，對它進行先序遍歷結(jié)果為_。65.若將如圖1.7所示為一棵樹轉(zhuǎn)換為二叉樹，該二叉樹中雙支結(jié)點的個數(shù)為_個，單支結(jié)點的個數(shù)為_個，葉子結(jié)點個數(shù)為_。66.一棵樹轉(zhuǎn)換為二叉樹后如圖1.8所示，則原樹中分支結(jié)點數(shù)為_，葉子結(jié)點數(shù)為_。67.一個樹林轉(zhuǎn)換成二叉樹后如圖1.9所示，則該素林中包含_棵樹。68.若由3，6，8，12，10作為葉子結(jié)點的值生成一棵哈夫曼樹，則該樹的深度為_，帶權(quán)路徑長度為_。69.一種數(shù)據(jù)結(jié)構(gòu)的元素集合K和它的二元關(guān)系R為：K=1，2，3，4，5，6R=（1，2）（2，3）（2，4）（3，4）（3，5）（3，6）（4，5）（4，6）則該數(shù)據(jù)結(jié)構(gòu)具有_數(shù)據(jù)結(jié)構(gòu)。70.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_倍。71.在一個具有n個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有向完全圖中，包含有_條邊。72.已知一個連通圖的邊集為（1，2），（1，3），（1，4），（2，3），（2，5），（3，5），（4，5），則度為3的頂點的個數(shù)有個。73.假定一個有向圖的頂點的集為a,b,c,d,e,f,邊集，,則出度為0的頂點個數(shù)為，入度為1的頂點個數(shù)為。74.在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要條邊。75.表示圖的兩種存儲結(jié)構(gòu)為和。76.在一個連通圖中存在著個連通分量。77.若一個圖的頂點集為a,b,c,d,e,f,邊集為（a,b），（a,c），（b,c），（d,e），則該圖含有個連通分量。78.若一個圖的邊集為，則從頂點V0到頂點V4共有條簡單路徑。79.如圖1.10所示為一個帶權(quán)有向圖，從頂點V0到頂點V4的最短路徑長度為。80.對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小至少為。81.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點的個數(shù)分別為和。82.在有向圖的鄰接表和逆鄰接表表示中，每個頂點鄰接表分別鏈接著該頂點的所有和。83.有一個圖的邊集為（a,c），（a,e），（b,e），（c,d），（d,e），從頂點a出發(fā)進行深度優(yōu)先搜索遍歷得到的頂點序列為，從頂點a出發(fā)進行廣度優(yōu)先搜索遍歷得到的頂點序列為。84.一個圖的邊集為（a,c），（a,e），（c,f），（d,c），（e,b），（e,d）,從頂點a出發(fā)出發(fā)進行深度優(yōu)先搜索遍歷得到的頂點序列為，從頂點a出發(fā)進行廣度優(yōu)先搜索遍歷得到的頂點序列為。85.圖的優(yōu)先搜索遍歷算法是一種遞歸算法，圖的優(yōu)先搜索遍歷算法需要使用隊列。86.若一個連通圖中每個邊上的權(quán)值均不同，則得到的最小生成樹是（唯一/不唯一）。87.以順序查找方法從長度為n的順序表或單鏈表中查找一個元素時，平均查找長度為。88.對長度為n的查找表進行查找時，假定查找第i個元素的概率為P，查找長度（即在查找過程中依次同有關(guān)元素比較的總次數(shù)）為C，則在查找成功的情況下的平均查找長度的計算公式為。89.假定一個順序表的長度為40，并假定查找每個元素的概率都相同，則在查找成功的情況下的平均查找長度，則在查找不成功的情況下的平均查找長度。90.以折半查找方法從長度為n的有序表中查找一個元素時，平均查找長度約等于減一。91.以折半查找方法從長度為50的有序表中查找一個元素時，其查找長度不超過。92.從有序表（12，18，30，43，56，78，82，95）中分別折半查找43和56元素時，其查找長度分別為和。93.假定對長度n=50的有序表進行折半查找，則對應(yīng)的判定樹深度為，最后一層的結(jié)點數(shù)為。94.在分塊查找中，假定查找表（即主表）的長度為96，被等分為8個子表，則進行分塊查找的平均查找長度為。95.假定對長度為n的有序表進行分塊查找，并假定每個子表的長度為，則進行分塊查找的平均查找長度為。96.在一棵二叉樹排序中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定該結(jié)點的值，右子樹上所有結(jié)點的值一定該結(jié)點的值。97.從一棵二叉排序樹中查找某個元素時，若元素的值等于根結(jié)點的值，則表明，若元素的值小于根結(jié)點的值，則繼續(xù)向查找，若元素的值大于根結(jié)點的值，則繼續(xù)向查找。98.向一棵二叉排序樹種插入一個元素時，若元素的值小于根結(jié)點的值，則接著向根結(jié)點的插入，若元素的值大于根結(jié)點的值，則接著向根結(jié)點的插入。99.在一棵平衡二叉排序樹中，每個結(jié)點的左子樹深度與右子樹深度之差的絕對值不超過。100.假定對線性表（38，25，74，52，48），進行散列存儲，采用H（K）=K%7作為哈希函數(shù)，采用線性探測再散列法處理沖突，則在建立哈希表過程中，將會碰到次沖突。101.假定對線性表（38，25，74，52，48）進行散列存儲，采用H（K）=K%7作為哈希函數(shù)，采用線性探測再散列法處理沖突，則平均查找長度為。102.在線性表的散列存儲中，裝填因子a又稱裝填系數(shù)，若用m表示散列表的長度，n表示散列存儲的元素個數(shù)，則a等于。103.對線性表（18，25，63，50，42，32，90）進行散列存儲時，若選用H（K）=K%9作為哈希函數(shù)，則散列地址為0的元素有個，則散列地址為5的元素有個。104.每次從無序子表中取出一個元素，把它插入到有序子表的適當位置，此種排序方法叫做排序；每次從無序子表中挑選出一個最小或最大元素，把它交換到有序表的一段，此種排序方法叫做排序。105.若對一組記錄（46，79，56，38，40，80，35，50，74）進行直接插入排序，當把第8個記錄插入到前面已排序的有序表時，為尋找插入位置需比較次。106.排序方法能夠每次使無序表中的第一個記錄插入到有序表中。107.對n個記錄進行冒泡排序時，最少的比較次數(shù)為，最少的趟數(shù)為。108.假定一組記錄為（46，79，56，38，40，84），在冒泡排序過程中進行第一趟排序后的結(jié)果為。109.假定一組記錄為（46，79，56，64，38，40，84，43），在冒泡排序過程中進行第一趟排序時，元素97將最終下沉到其后第位置。110.排序方法使鍵值達的記錄逐漸下沉，使鍵值小的記錄逐漸上浮。111.假定一組記錄為（46，79，56，38，40，80）對其進行快速排序的過程中，共需要趟。112.假定一組記錄為（46，79，56，25，76，38，40，80）對其進行快速排序的第一次劃分后，右區(qū)間內(nèi)元素個數(shù)為。113.假定一組記錄為（46，79，56，38，40，80），對其進行快速排序的第一次劃分后的結(jié)果為。114.在所有排序方法中，排序方法采用的是折半查找法的思想。115.在簡單選擇排序中，記錄比較次數(shù)的時間復雜度為，記錄移動次數(shù)的時間復雜度為。116.若對一組記錄（46，79，56，38，40，80，35，50，74）進行簡單選擇排序，用k表示最小值元素的下標，進行第一趟是可得初值為1，則在第一趟選擇最小值的過程中，k的值被修改次。117.在時間復雜度為O（n2）的所有排序方法中，排序方法使不穩(wěn)定的。118.假定一個堆為（38