數(shù)據(jù)結(jié)構(gòu)(本科)期末綜合練習(xí)二(填空與判斷題)

...wd......wd......wd...數(shù)據(jù)構(gòu)造〔本科〕期末綜合練習(xí)二〔填空與判斷題〕填空題1.數(shù)據(jù)是__信息__的載體，它能夠被計算機程序識別、存儲和加工處理。2.數(shù)據(jù)構(gòu)造包括邏輯構(gòu)造、__存儲構(gòu)造__和數(shù)據(jù)的運算三個方面。3.數(shù)據(jù)構(gòu)造的邏輯構(gòu)造包括線性構(gòu)造和__非線性__構(gòu)造兩大類。4.數(shù)據(jù)構(gòu)造的存儲構(gòu)造包括順序、__鏈接___、索引和散列等四種。5.基本數(shù)據(jù)類型是計算機已經(jīng)實現(xiàn)了的_數(shù)據(jù)構(gòu)造__。6.抽象數(shù)據(jù)類型的特點是__數(shù)據(jù)封裝__、信息隱蔽、使用與實現(xiàn)別離。7.算法的一個特性是__有窮性__，即算法必須執(zhí)行有限步就完畢。8.面向?qū)ο蟮奶卣鲬?yīng)包括對象、類、__繼承__、消息通信。9.屬性與服務(wù)一樣的對象構(gòu)成類，類中的每個對象稱為該類的__實例__。10.對象的私有狀態(tài)只能通過該對象的__操作〔或服務(wù)〕_才能改變。11.模板類是一種數(shù)據(jù)抽象，它把__數(shù)據(jù)類型_當(dāng)作參數(shù)，可以實現(xiàn)類的復(fù)用。12.在類的繼承構(gòu)造中，位于上層的類叫做基類，其下層的類那么叫做__派生〔或子〕__類。13.一維數(shù)組所占用的空間是連續(xù)的。但數(shù)組元素不一定順序存取，通常是按元素的__下標(biāo)〔或順序號〕__存取的。14.在程序運行過程中不能擴(kuò)大的數(shù)組是__靜態(tài)__分配的數(shù)組。這種數(shù)組在聲明它時必須指定它的大小。15.在程序運行過程中可以擴(kuò)大的數(shù)組是__動態(tài)___分配的數(shù)組。這種數(shù)組在聲明它時需要使用數(shù)組指針。16.二維數(shù)組是一種非線性構(gòu)造，其中的每一個數(shù)組元素最多有__兩個__個直接前驅(qū)〔或直接后繼〕。17.假設(shè)設(shè)一個nn的矩陣A的開場存儲地址LOC(0,0)及元素所占存儲單元數(shù)d，按行存儲時其任意一個矩陣元素a[i][j]的存儲地址為__LOC(0,0)+(i*n+j)*d__。18.對稱矩陣的行數(shù)與列數(shù)__相等_且以主對角線為對稱軸，aij=aji，因此只存儲它的上三角局部或下三角局部即可。19.將一個n階對稱矩陣的上三角局部或下三角局部壓縮存放于一個一維數(shù)組中，那么一維數(shù)組需要存儲__n(n+1)/2_個矩陣元素。20.將一個n階對稱矩陣A的上三角局部按行壓縮存放于一個一維數(shù)組B中，A[0][0]存放于B[0]中，那么A[I][J]在I≤J時將存放于數(shù)組B的__(2n-I-1)*I/2+J__位置。21.利用三元組表存放稀疏矩陣中的非零元素，那么在三元組表中每個三元組元素對應(yīng)一個非零元素的行號、列號和__值__。22.線性表是由n〔n≥0〕個__數(shù)據(jù)元素__組成的有限序列。23.假設(shè)設(shè)串S=“documentHash.doc\0〞，那么該字符串S的長度為___16____。24.鏈表是一種采用鏈?zhǔn)健不蜴溄印炒鎯?gòu)造存儲的線性表。25.鏈表只適用于順序查找。26.在鏈表中進(jìn)展插入和刪除操作的效率比在順序存儲構(gòu)造中進(jìn)展一樣操作的效率高。27.鏈表對于數(shù)據(jù)元素的插入和刪除不需要移動結(jié)點，只需要改變相應(yīng)結(jié)點的__指針域_的值。28.鏈接存儲表示的結(jié)點存儲空間一般在程序的運行過程中進(jìn)展動態(tài)地__分配__和釋放。29.單鏈表中邏輯上相鄰的結(jié)點而在物理位置上_不一定_相鄰。30.在單鏈表中,除了表頭結(jié)點外,任意結(jié)點的存儲位置由其直接_前驅(qū)_結(jié)點的指針域的值所指示。31.在單鏈表設(shè)置表頭結(jié)點的作用是插入和刪除表中第一個元素時不必對__表頭指針_進(jìn)展特殊處理。32.假設(shè)設(shè)L是指向帶表頭的單鏈表,語句L->link=L->link->link的作用是__刪除_單鏈表中的第一個結(jié)點。33.在雙向鏈表中,每個結(jié)點除了數(shù)據(jù)域外,還有兩個指針域,它們分別指向__前趨結(jié)點和后繼結(jié)點__。34.線性表的鏈接存儲只能通過_鏈接指針_順序訪問。35.鏈表與順序表、索引表、散列表等都是數(shù)據(jù)邏輯構(gòu)造的__存儲__表示。36.設(shè)雙向循環(huán)鏈表每個結(jié)點構(gòu)造為(data,llink,rlink),那么結(jié)點*p的前驅(qū)結(jié)點的地址為__p->llink__。37.棧是一種限定在表的一端進(jìn)展插入和刪除的線性表，又被稱為__后出先進(jìn)__表。38.隊列是一種限定在表的一端插入，在另一端刪除的線性表，它又被稱為__先進(jìn)先出__表。39.向一個鏈?zhǔn)綏２迦胍粋€新結(jié)點時，首先把棧頂指針的值賦給新結(jié)點的指針域，然后把新結(jié)點的存儲位置賦給__棧頂指針__。40.隊列的刪除操作在_隊頭〔或隊首〕_進(jìn)展。41.向一個順序棧插入一個元素時，首先使__棧頂指針_后移一個位置，然后把待插入元素寫入到這個位置上。42.假設(shè)設(shè)順序棧的最大容量為MaxSize，top==-1表示?？眨敲磁袛鄺M的條件是__top==MaxSize-1__。43.當(dāng)用長度為MaxSize的數(shù)組順序存儲一個棧時，假設(shè)用top==MaxSize表示?？?，那么表示棧滿的條件為__top==0__。44.向一個循環(huán)隊列中插入元素時，需要首先移動__隊尾__指針，然后再向所指位置寫入新元素。45.向一個棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€新結(jié)點*p時，應(yīng)執(zhí)行__p->link=top_和top=p操作。46.在一個鏈?zhǔn)疥犃兄?，假設(shè)隊頭指針與隊尾指針的值一樣，那么表示該隊列至多有__1__個結(jié)點。47.在一個鏈?zhǔn)疥犃兄?，假設(shè)隊頭指針與隊尾指針的值一樣，那么表示該隊列至多有___一__個結(jié)點。48.如果一個對象局部地包含自己，或自己定義自己，那么稱這個對象是__遞歸_的對象。49.如果一個過程直接或間接地調(diào)用自己，那么稱這個過程是一個__遞歸_的過程。50.遞歸工作棧起到兩個作用，其一是將遞歸調(diào)用時的實際參數(shù)和返回地址傳遞給下一層遞歸；其二是保存本層的形式參數(shù)和_局部變量_。51.函數(shù)內(nèi)部的局部變量是在進(jìn)入函數(shù)過程后才分配存儲空間，在函數(shù)過程執(zhí)行完畢后就__釋放___局部變量所占用的存儲空間。52.迷宮問題是一個回溯控制的問題，最好使用__遞歸___的方法來解決。53.非空廣義表的除第一個元素外其他元素組成的表稱為廣義表的__表尾__。54.廣義表A((a,b,c),(d,e,f))的表尾為_((d,e,f))_。55.廣義表是一種遞歸的數(shù)據(jù)構(gòu)造，子表結(jié)點那么指示下一層廣義表的__表頭結(jié)點__。56.廣義表的深度定義為廣義表括號的__重數(shù)__。57.對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為_n-1_。58.一棵樹的廣義表表示為a(b(c,d(e,f),g(h)),i(j,k(x,y)))，結(jié)點k的所有祖先的結(jié)點數(shù)為___2__個。59.一棵樹的廣義表表示為a(b(c,d(e,f),g(h)),i(j,k(x,y)))，結(jié)點f的層數(shù)為___3___。假定樹根結(jié)點的層數(shù)為0。60.假定一棵三叉樹〔即度為3的樹〕的結(jié)點個數(shù)為50，那么它的最小高度為__4_。假定樹根結(jié)點的深度為0。61.在一棵高度為3的四叉樹中，最多含有__85__個結(jié)點，假定樹根結(jié)點的高度為0。62.在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有__6__個。63.一棵高度為5的完全二叉樹中，最多包含有__63__個結(jié)點。假定樹根結(jié)點的高度為0。64.假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，那么該樹的高度為__3__。假定樹根結(jié)點的高度為0。65.在一棵二叉樹中，假定雙分支結(jié)點數(shù)為5個，單分支結(jié)點數(shù)為6個，那么葉子結(jié)點數(shù)為_6_個。66.假定一棵二叉樹的結(jié)點數(shù)為18，那么它的最小高度為__4__。假定樹根結(jié)點的高度為0。67.在一棵高度為h的理想平衡二叉樹中，最少含有__2h__個結(jié)點。假定樹根結(jié)點的高度為0。68.在一棵高度為h的理想平衡二叉樹中，最多含有__2h+1-1_個結(jié)點。假定樹根結(jié)點的高度為0。69.假設(shè)將一棵樹A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法轉(zhuǎn)換為二叉樹，該二叉樹中度為2的結(jié)點的個數(shù)為__2__個。70.將一棵樹按照左子女-右兄弟表示法轉(zhuǎn)換成對應(yīng)的二叉樹，那么該二叉樹中樹根結(jié)點肯定沒有__右__子女。71.在一個堆的順序存儲中，假設(shè)一個元素的下標(biāo)為i(0≤i≤n-1)，那么它的左子女元素的下標(biāo)為__2i+1_。72.在一個堆的順序存儲中，假設(shè)一個元素的下標(biāo)為i(0≤i≤n-1)，那么它的右子女元素的下標(biāo)為__2i+2__。73.在一個最小堆中，堆頂結(jié)點的值是所有結(jié)點中的__最小值_。74.在一個最大堆中，堆頂結(jié)點的值是所有結(jié)點中的_最大值_。75.以順序搜索方法從長度為n的順序表或單鏈表中搜索一個元素的漸進(jìn)時間復(fù)雜度為__O(n)_。76.對長度為n的搜索表進(jìn)展搜索時，假定搜索第i個元素的概率為pi,搜索長度〔即在搜索過程中依次同有關(guān)元素比較的總次數(shù)〕為ci，那么在搜索成功情況下的平均搜索長度的計算公式為____。77.假定一個順序表的長度為40，并假定順序搜索每個元素的概率都一樣，那么在搜索成功情況下的平均搜索長度為_20.5_。78.從有序表(12,18,30,43,56,78,82,95)中折半搜索元素56時，其搜索長度為__3__。79.假定對長度n=50的有序表進(jìn)展折半搜索，那么對應(yīng)的判定樹中最底下一層的結(jié)點數(shù)為__19__個。80.從一棵二叉搜索樹中搜索一個元素時，假設(shè)給定值大于根結(jié)點的值，那么需要向_右子樹_繼續(xù)搜索。81.向一棵二叉搜索樹中插入一個元素時，假設(shè)元素的值小于根結(jié)點的值，那么應(yīng)把它插入到根結(jié)點的_左子樹_上。82.根據(jù)n個元素建設(shè)一棵二叉搜索樹的漸進(jìn)時間復(fù)雜度大致為__O(nlog2n)__。83.在一棵AVL樹中，每個結(jié)點的左子樹高度與右子樹高度之差的絕對值不超過__1___。84.根據(jù)一組記錄(56,42,50,64,48)依次插入結(jié)點生成一棵AVL樹時，當(dāng)插入到值為_50_的結(jié)點時需要進(jìn)展旋轉(zhuǎn)調(diào)整。85.根據(jù)一組記錄(56,74,63,64,48)依次插入結(jié)點生成一棵AVL樹時，當(dāng)插入到值為63的結(jié)點時需要進(jìn)展__先右后左雙旋轉(zhuǎn)_調(diào)整。86.根據(jù)一組記錄(56,42,38,64,48)依次插入結(jié)點生成一棵AVL樹時，當(dāng)插入到值為38的結(jié)點時需要進(jìn)展_右單旋轉(zhuǎn)_調(diào)整。87.根據(jù)一組記錄(56,42,73,50,64,48,22)依次插入結(jié)點生成一棵AVL樹時，當(dāng)插入到值為__64_的結(jié)點時才出現(xiàn)不平衡，需要進(jìn)展旋轉(zhuǎn)調(diào)整。88.在一棵具有n個結(jié)點的AVL樹上進(jìn)展插入或刪除元素的漸進(jìn)時間復(fù)雜度大致為_O(log2n)_。89.n(n﹥0)個頂點的連通無向圖各頂點的度之和最少為__2(n-1)__。90.用鄰接矩陣存儲圖，占用的存儲空間與圖中的_頂點_數(shù)有關(guān)。91.設(shè)圖G=(V,E)，V={V0,V1,V2,V3},E={(V0,V1),(V0,V2),(V0,V3),(V1,V3)}，那么從頂點V0開場的圖G的不同深度優(yōu)先序列有__4__種。92.設(shè)圖G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，從頂點1出發(fā)，對圖G進(jìn)展廣度優(yōu)先搜索的序列有__2__種。93.n(n﹥0)個頂點的無向圖中頂點的度的最大值為__n-1_。94.在重連通圖中每個頂點的度至少為__2__。95.n個頂點的連通無向圖的生成樹含有__n-1__條邊。96.11個頂點的連通網(wǎng)絡(luò)N有10條邊，其中權(quán)值為1,2,3,4,5的邊各2條，那么網(wǎng)絡(luò)N的最小生成樹各邊的權(quán)值之和為__30__。97.在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹時，只有當(dāng)一條候選邊的兩個端點不在同一個_連通分量_上，才會被參加到生成樹中。98.一般來說,深度優(yōu)先生成樹的高度比廣度優(yōu)先生成樹的高度要__高_(dá)_。99.求解帶權(quán)連通圖最小生成樹的Prim算法使用圖的__鄰接矩陣_作為存儲構(gòu)造。100.設(shè)圖的頂點數(shù)為n，那么求解最短路徑的Dijkstra算法的時間復(fù)雜度為_O(n2)__。101.第i(i=1,2,…,n-1)趟從參加排序的序列中取出第i個元素，把它插入到由第0個至第i-1個元素組成的有序表中適當(dāng)?shù)奈恢?，此種排序方法叫做_直接插入_排序。102.第i(i=0,1,...,n-2)趟從參加排序的序列中第i個至第n-1個元素中挑選出一個最小元素，把它交換到第i個位置，此種排序方法叫做_直接選擇_排序。103.每次直接或通過基準(zhǔn)元素間接比較兩個元素，假設(shè)出現(xiàn)逆序排列就交換它們的位置，這種排序方法叫做__交換_排序。104.每次使兩個相鄰的有序表合并成一個有序表，這種排序方法叫做__二路歸并__排序。105.在直接選擇排序中，記錄比較次數(shù)的時間復(fù)雜度為__O(n2)__。106.在直接選擇排序中，記錄移動次數(shù)的時間復(fù)雜度為___O(n)__。107.在堆排序中，對n個記錄建設(shè)初始堆需要調(diào)用__n/2__次調(diào)整算法。108.在堆排序中，如果n個對象的初始堆已經(jīng)建好，那么到排序完畢，還需要從堆頂結(jié)點出發(fā)調(diào)用__n-1_次調(diào)整算法。109.在堆排序中，對任意一個分支結(jié)點進(jìn)展調(diào)整運算的時間復(fù)雜度為__O(log2n)__。110.對n個數(shù)據(jù)對象進(jìn)展堆排序，總的時間復(fù)雜度為___O(nlog2n)___。111.給定一組數(shù)據(jù)對象的關(guān)鍵碼為{46,79,56,38,40,84}，那么利用堆排序方法建設(shè)的初始堆〔最大堆〕為__84，79，56，38，40，46__。112.快速排序在平均情況下的時間復(fù)雜度為_O(nlog2n)_。113.快速排序在最壞情況下的時間復(fù)雜度為___O(n2)__。114.快速排序在平均情況下的空間復(fù)雜度為___O(log2n)___。115.快速排序在最壞情況下的空間復(fù)雜度為___O(n)___。116.給定一組數(shù)據(jù)對象的關(guān)鍵碼為{46，79，56，38，40，84}，對其進(jìn)展一趟快速排序處理，得到的右子表中有__3__個對象。117.在對n個數(shù)據(jù)對象的二路歸并排序中，每趟歸并的時間復(fù)雜度為___O(n)___。118.在對n個數(shù)據(jù)對象進(jìn)展的二路歸并排序中，整個歸并過程的時間復(fù)雜度為__O(nlog2n)__。119.在索引表中，每個索引項至少包含有__關(guān)鍵碼_域和地址域這兩項。120.假定一個線性表為{12,23,74,55,63,40,82,36}，假設(shè)按key%3條件進(jìn)展劃分，使得同一余數(shù)的元素成為一個子表，那么包含74的子表長度為__2__。121.假定一個線性表為(〞abcd〞,〞baabd〞,〞bcef〞,〞cfg〞,〞ahij〞,〞bkwte〞,〞ccdt〞,〞aayb〞)，假設(shè)按照字符串的第一個字母進(jìn)展劃分，使得同一個字母被劃分在一個子表中，那么得到的以a為第一個字母的子表長度為__3__。122.在索引表中，假設(shè)一個索引項對應(yīng)數(shù)據(jù)對象表中的一個表項，那么稱此索引為稠密索引，假設(shè)對應(yīng)數(shù)據(jù)對象表中的假設(shè)干表項，那么稱此索引為__稀疏_索引。 123.假定對長度n=100的線性表進(jìn)展索引順序搜索，并假定每個子表的長度均為，那么進(jìn)展索引順序搜索的時間復(fù)雜度為_O(Eq\r(n))_。124.假定對長度n=100的線性表進(jìn)展索引順序搜索，并假定每個子表的長度均為，那么進(jìn)展索引順序搜索的平均搜索長度為__11__。125.假設(shè)對長度n=10000的線性表進(jìn)展二級索引存儲，每級索引表中的索引項是下一級20個表項的索引，那么一級索引表的長度為__500_。126.假設(shè)對長度n=10000的線性表進(jìn)展二級索引存儲，每級索引表中的索引項是下一級20個表項的索引，那么二級索引表的長度為__25__。127.假定要對長度n=100的線性表進(jìn)展散列存儲，并采用開散列法處理沖突，那么對于長度m=20的散列表，每個散列地址的同義詞子表〔單鏈表〕的長度平均為_5__。128.在線性表的散列存儲中，裝載因子又稱為裝載系數(shù)，假設(shè)用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，那么等于_n/m_。129.對于包含n個關(guān)鍵碼的m階B樹，其最小高度為__logm(n+1)__。130.一棵3階B樹中含有50個關(guān)鍵碼，那么該樹的最小高度為___4___。131.一棵3階B樹中含有50個關(guān)鍵碼，那么該樹的最大高度為___5____。132.在一棵m階B樹上，每個非根結(jié)點的關(guān)鍵碼數(shù)最少為__m/2-1__個。133.在一棵m階B樹上，每個非根結(jié)點的子樹最少為__m/2__棵。134.在一棵m階B樹上，每個非根結(jié)點的關(guān)鍵碼數(shù)最多為__m-1__個。135.在對m階B樹插入元素的過程中，每向一個結(jié)點插入一個關(guān)鍵碼后，假設(shè)該結(jié)點的關(guān)鍵碼個數(shù)等于__m__個，那么必須把它分裂為2個結(jié)點。136.在從m階B樹刪除關(guān)鍵碼的過程中，當(dāng)從一個結(jié)點中刪除掉一個關(guān)鍵碼后，所含關(guān)鍵碼個數(shù)等于m/2-2個，并且它的左、右兄弟結(jié)點中的關(guān)鍵碼個數(shù)均等于_m/2-1_，那么必須進(jìn)展結(jié)點合并。判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。錯2.數(shù)據(jù)的邏輯構(gòu)造是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建設(shè)的。對3.算法和程序原那么上沒有區(qū)別，在討論數(shù)據(jù)構(gòu)造時二者是通用的。錯4.數(shù)據(jù)的邏輯構(gòu)造與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。對5.算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。錯6.只有用面向?qū)ο蟮挠嬎銠C語言才能描述數(shù)據(jù)構(gòu)造算法。錯7.如果采用如下方式定義一維字符數(shù)組：constintmaxSize=30;chara[maxSize];那么這種數(shù)組在程序執(zhí)行過程中不能擴(kuò)大。對8.如果采用如下方法定義一維字符數(shù)組：intmaxSize=30;char*a=newchar[maxSize];那么這種數(shù)組在程序執(zhí)行過程中不能擴(kuò)大。錯9.數(shù)組是一種靜態(tài)的存儲空間分配，就是說，在程序設(shè)計時必須預(yù)先定義數(shù)組的數(shù)據(jù)類型和存儲空間大小，由編譯程序在編譯時進(jìn)展分配。錯10.多維數(shù)組是一種復(fù)雜的數(shù)據(jù)構(gòu)造，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。對11.在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰。錯12.順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機〔或直接〕訪問。對13.插入與刪除操作是數(shù)據(jù)構(gòu)造中最基本的兩種操作，因此這兩種操作在數(shù)組中也經(jīng)常被使用。錯14.使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲空間。對15.用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。對16.線性表假設(shè)采用鏈?zhǔn)酱鎯Ρ硎緯r，其存儲結(jié)點的地址可連續(xù)也可不連續(xù)。對17.線性表假設(shè)采用鏈?zhǔn)酱鎯Ρ硎?在刪除時不需要移動元素。對18.在線性鏈表中刪除中間的結(jié)點時，只需將被刪結(jié)點釋放。錯19.在對雙向循環(huán)鏈表做刪除一個結(jié)點操作時，應(yīng)先將被刪除結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點鏈接好再執(zhí)行刪除結(jié)點操作。對20.每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素,這種隊列就是優(yōu)先級隊列。對21.鏈?zhǔn)綏Ｅc順序棧相比,一個明顯的優(yōu)點是通常不會出現(xiàn)棧滿的情況。對22.在一個順序存儲的循環(huán)隊列中,隊頭指針指向隊頭元素的后一個位置。錯23.棧和隊列都是順序存取的線性表,但它們對存取位置的限制不同。對24.在使用后綴表示實現(xiàn)計算器類時用到一個棧的實例,它的作用是暫存運算器對象。對25.在用循環(huán)單鏈表表示的鏈?zhǔn)疥犃兄?，可以不設(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針。對26.假設(shè)讓元素1,2,3依次進(jìn)棧，那么出棧次序1,3,2是不可能出現(xiàn)的情況。錯27.在用單鏈表表示的鏈?zhǔn)疥犃蠶中，隊頭指針為Q->front，隊尾指針為Q->rear，那么隊空條件為Q->front==Q->rear。錯28.遞歸定義的數(shù)據(jù)構(gòu)造通常用遞歸算法來實現(xiàn)對它的操作。對29.遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。錯30.遞歸調(diào)用算法與一樣功能的非遞歸算法相比，主要問題在于重復(fù)計算太多，而且調(diào)用本身需要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時間與空間開銷通常都比較大。對31.遞歸方法和遞推方法本質(zhì)上是一回事，例如求n!時既可用遞推的方法，也可用遞歸的方法。錯32.用非遞歸方法實現(xiàn)遞歸算法時一定要使用遞歸工作棧。錯33.將f=1+1/2+1/3+…+1/n轉(zhuǎn)化為遞歸函數(shù)時，遞歸局部為f(n)=f(n-1)+1/n，遞歸完畢條件為f(1)=1。對34.一個廣義表的表頭總是一個廣義表。錯35.一個廣義表的表尾總是一個表。對36.一個廣義表((a),((b),c),(((d))))的長度為3，深度為4。對37.一個廣義表((a),((b),c),(((d))))的表尾是((b),c),(((d)))。錯38.當(dāng)向一個最小堆插入一個具有最小值的元素時，該元素需要逐層向上調(diào)整，直到被調(diào)整到堆頂位置為止。對39.當(dāng)從一個最小堆中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到適宜位置為止。對40.二叉樹是一棵無序樹。錯41.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進(jìn)展前序遍歷和后序遍歷，那么具有一樣的結(jié)果。錯42.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進(jìn)展中序遍歷和后序遍歷，那么具有一樣的結(jié)果。對43.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進(jìn)展前序遍歷和中根遍歷，那么具有一樣的結(jié)果。錯44.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進(jìn)展前序遍歷和按層遍歷，那么具有一樣的結(jié)果。對45.在樹的存儲中，假設(shè)使每個結(jié)點帶有指向雙親結(jié)點的指針，這為在算法中尋找雙親結(jié)點帶來方便。對46.對于一棵具有n個結(jié)點，其高度為h的二叉樹，進(jìn)展任一種次序遍歷的時間復(fù)雜度為O(n)。對47.對于一棵具有n個結(jié)點，其高度為h的任何二叉樹，進(jìn)展任一種次序遍歷的時間復(fù)雜度均為O(h)。錯48.對于一棵具有n個結(jié)點的任何二叉樹，進(jìn)展前序、中序或后序的任一種次序遍歷的空間復(fù)雜度為O(log2n)。錯49.在一棵具有n個結(jié)點的線索二叉樹中，每個結(jié)點的指針域可能指向子女結(jié)點，也可能作為線索，使之指向某一種遍歷次序的前驅(qū)或后繼結(jié)點，所有結(jié)點中作為線索使用的指針域共有n個。錯50.線索二叉樹中的每個結(jié)點通常包含有5個數(shù)據(jù)成員。對51.對具有n個結(jié)點的堆進(jìn)展插入一個元素運算的時間復(fù)雜度為O(n)。錯52.在順序表中進(jìn)展順序搜索時，假設(shè)各元素的搜索概率不等，那么各元素應(yīng)按照搜索概率的降序排列存放，那么可得到最小的平均搜索長度。對53.進(jìn)展折半搜索的表必須是順序存儲的有序表。對54.能夠在鏈接存儲的有序表上進(jìn)展折半搜索，其時間復(fù)雜度與在順序存儲的有序表上一樣。錯55.假定有兩個用單鏈有序表表示的集合，那么這兩個集合的交運算可得到一個新的集合單鏈表，其長度小于等于參加運算的任意一個集合單鏈表的長度。對56.假定有兩個用單鏈有序表表示的集合，那么這兩個集合的差運算可得到一個新的集合單鏈表，其長度小于參加運算的任意一個集合單鏈表的長度。錯57.折半搜索所對應(yīng)的判定樹，既是一棵二叉搜索樹，又是一棵理想平衡二叉樹。對58.對于同一組關(guān)鍵碼互不一樣的記錄，假設(shè)生成二叉搜索樹時插入記錄的次序不同那么得到不同形態(tài)的二叉搜索樹。對59.對于同一組記錄，生成二叉搜索樹的形態(tài)與插入記錄的次序無關(guān)。錯60.對于兩棵具有一樣記錄集合而具有不同形態(tài)的二叉搜索樹，按中序遍歷得到的結(jié)點序列是一樣的。對61.在二叉搜索樹中，假設(shè)各結(jié)點的搜索概率不等，使得搜索概率越大的結(jié)點離樹根越近，那么得到的是最優(yōu)二叉搜索樹。對62.在二叉搜索樹中，假設(shè)各結(jié)點的搜索概率不等，使得搜索概率越小的結(jié)點離樹根越近，那么得到的是最優(yōu)二叉搜索樹。錯63.用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。對64.鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。錯65.鄰接矩陣適用于稠密圖〔邊數(shù)接近于頂點數(shù)的平方〕，鄰接表適用于稀疏圖〔邊數(shù)遠(yuǎn)小于頂點數(shù)的平方〕。對66.存儲無向圖的鄰接矩陣是對稱的，因此可以只存儲鄰接矩陣的下〔上〕三角局部。對67.強連通分量是有向圖中的極大強連通子圖。對68.對任何用頂點表示活動的網(wǎng)絡(luò)〔AOV網(wǎng)〕進(jìn)展拓?fù)渑判虻慕Y(jié)果都是唯一的。錯69.有回路的有向圖不能完成拓?fù)渑判?。?0.在AOE網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。錯71.用邊表示活動的網(wǎng)絡(luò)〔AOE網(wǎng)〕的關(guān)鍵路徑是指從源點到終點的路徑長度最長的路徑。對72.對于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動就能使整個工程提前完成。錯73.對于AOE網(wǎng)絡(luò)，任一關(guān)鍵活動延遲將導(dǎo)致整個工程延遲完成。對74.在AOE網(wǎng)絡(luò)中，可能同時存在幾條關(guān)鍵路徑，稱所有關(guān)鍵路徑都需通過的有向邊為橋。如果加速這樣的橋上的關(guān)鍵活動就