國家開放大學02272-數(shù)據(jù)結構（本）期末復習資料

單選題1、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）。參考答案：(n+1)/2(V)2、權值為{1，2，6，8}的四個結點構成的哈夫曼樹的帶權路徑長度是（）。參考答案：29(V)3、（）的一個重要應用是解決主機和打印機之間速度不匹配的問題。參考答案：隊列(V)4、（）的一個重要應用是在程序設計中實現(xiàn)遞歸調用。參考答案：棧(V)5、（）有兩個指針域，分別指向直接前驅和直接后繼，可以實現(xiàn)從前向后和從后向前查找。參考答案：雙向循環(huán)鏈表(V)6、（）不屬于線性表的基本操作。參考答案：求子表(V)7、8.對于一個鏈串s，查找第一個字符值為x的算法的時間復雜度為（）參考答案：O(n)(V)8、表達式a*(b+c)-d的后綴表達式是（）。參考答案：abc+*d-(V)9、采用折半查找方法查找長度為n的線性表時，其算法的時間復雜度為（）。參考答案：O(log2n)(V)10、串的長度是指（）。參考答案：串中所含字符的個數(shù)(V)11、串函數(shù)Strcat（a,b）的功能是進行串（）。參考答案：連接(V)12、串是（）。參考答案：有限個字符的序列(V)13、串與普通的線性表相比較，它的特殊性體現(xiàn)在（）。參考答案：數(shù)據(jù)元素是一個字符(V)14、從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（）。參考答案：插入排序(V)15、帶頭結點的單向鏈表L為空的判定條件是（）。參考答案：L->next==NULL(V)16、帶頭結點的雙向循環(huán)鏈表L為空表的條件是（）。參考答案：L->next==L(V)17、當利用大小為100的數(shù)組順序存儲一個隊列時，隊列的最大長度為（）。參考答案：99(V)18、當利用大小為N的數(shù)組順序存儲一個棧時，假定用top==-1表示?？?，則入棧應該執(zhí)行（）語句修改top指針。參考答案：top++(V)19、當利用大小為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？?，則入棧應該執(zhí)行（）語句修改top指針。參考答案：top--(V)20、當兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為（）。參考答案：交換排序(V)21、隊列是一種操作受限的線性表，其限制是（）。參考答案：僅允許在表的一端進行插入，而在另一端進行刪除操作(V)22、對二叉排序樹進行（）遍歷，可以使遍歷所得到的序列是有序序列。參考答案：中序(V)23、對具有n個元素的任意序列采用插入排序法進行排序，排序趟數(shù)為（）。參考答案：n-1(V)24、對線性表進行二分查找時，要求線性表必須（）。參考答案：以順序存儲方式，且數(shù)據(jù)元素有序(V)25、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接表中的結點總數(shù)為（）。參考答案：2e(V)26、對于一個線性表，若要求既能進行較快地插入和刪除，又要求存儲結構能夠反映數(shù)據(jù)元素之間的邏輯關系，則應該（）。參考答案：以鏈接存儲方式(V)27、二叉樹的按層遍歷算法需要使用（）參考答案：隊列(V)28、非空的單向循環(huán)鏈表的尾結點滿足（）（設頭指針為head，指針p指向尾結點）。參考答案：p->next==head(V)29、關于棧和隊列的說法中，錯誤的是（）。參考答案：棧是先進先出，隊列是后進先出(V)30、廣義表(f,h,(a,b,d,c),d,e,((i,j),k))的長度是()。參考答案：6(V)31、廣義表（a，a，b，d，e，（（i，j），k））的表頭是（）。參考答案：a(V)32、廣義表（a，d，e，（i，j），k）的表尾是（）。參考答案：（d，e，（i，j），k）(V)33、假定一棵二叉樹中，葉子結點數(shù)為10，單分支結點數(shù)為30，則雙分支結點數(shù)為（）。參考答案：9(V)34、假設鏈隊的隊首和隊尾指針是F和R，那么隊空的條件是（）。參考答案：R=NULL(V)35、就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關系是（）。參考答案：堆排序<

快速排序<

歸并排序(V)36、空串與空格串（）。參考答案：不相同(V)37、利用2、4、5、10這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹的帶權路徑長度為（）。參考答案：38(V)38、鏈表不具有的特點是（）。參考答案：可隨機訪問任一元素(V)39、鏈表所具備的特點是（）。參考答案：插入刪除元素的操作不需要移動元素結點(V)40、鏈棧和順序棧相比，有一個比較明顯的優(yōu)點，即（）。參考答案：通常不會出現(xiàn)棧滿的情況(V)41、兩個字符串相等的條件是（）。參考答案：兩串的長度相等，并且對應位置上的字符相同(V)42、兩個字符串相等的條件是（）。參考答案：兩個串的長度相等且對應位置的字符相同(V)43、鄰接表是圖的一種（）。參考答案：鏈式存儲結構(V)44、每個存儲結點只存儲一個數(shù)據(jù)元素，各結點存儲在連續(xù)的存儲空間，該存儲方式是（）存儲方式。參考答案：順序(V)45、某串的長度小于一個常數(shù)，則采用（）存儲方式最節(jié)省空間。參考答案：順序(V)46、判斷向上增長型的順序?？盏臈l件是（）。參考答案：top=-1(V)47、判斷一個順序隊列sq（最多元素為m）為空的條件是（）。參考答案：sq->front==sq->rear(V)48、任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的（）。參考答案：相對次序不改變(V)49、如果進行串的比較，下列哪個串最大？（）參考答案：“BEIJING”(V)50、如果以鏈表作為棧的存儲結構，則退棧操作時（）。參考答案：必須判斷棧是否空(V)51、如圖所示二叉樹的中序遍歷序列是（）。參考答案：dgbaechf(V)52、若Head為一個帶表頭結點的單鏈表的表頭指針，則該表為空表的條件是（）。參考答案：Head->next==NULL(V)53、設a，b為一棵二叉樹的兩個結點，在后續(xù)遍歷中，a在b前的條件是（）。參考答案：a在b下方(V)54、設頭指針為head的非空的單向鏈表，指針p指向尾結點,則通過以下操作（)可使其成為單向循環(huán)鏈表。參考答案：p->next=head;(V)55、設有兩個長度為n的單向鏈表，結點類型相同，分別是循環(huán)鏈表和非循環(huán)鏈表，則（）。參考答案：對于兩個鏈表來說，刪除最后一個結點的操作，其時間復雜度都是O(n)(V)56、設有一個廣義表A(a)，其表尾為（）。參考答案：()(V)57、設有一個長度為n的順序表，要刪除第i個元素,則需移動元素的個數(shù)為（）。參考答案：n-i(V)58、樹的（）沒有前驅結點，其他結點有且僅有一個直接前驅結點。參考答案：根結點(V)59、樹形結構中數(shù)據(jù)元素之間的關系是（）參考答案：一對多(V)60、樹中所有結點的度等于所有結點數(shù)加（）。參考答案：-1(V)61、數(shù)據(jù)的存儲結構包括數(shù)據(jù)元素的表示和（）。參考答案：數(shù)據(jù)元素間的關系的表示(V)62、數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（）。參考答案：邏輯結構(V)63、數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（）。參考答案：邏輯結構(V)64、順序隊列中，隊首元素位置為5，則隊首指針位置為（）。參考答案：4(V)65、通常的使用順序棧或者鏈棧實現(xiàn)遞歸算法，下面哪個說法正確（）。參考答案：順序棧和鏈棧性能基本相同(V)66、圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。參考答案：先序(V)67、無向圖的鄰接矩陣是一個（）。參考答案：對稱矩陣(V)68、稀疏矩陣采用壓縮存儲的目的主要是（）。參考答案：減少不必要的存儲空間的開銷(V)69、下列的敘述中，不屬于算法特性的是（）。參考答案：可讀性(V)70、下列廣義表中的線性表是（）。參考答案：E(a,b)(V)71、下列是”abcd321ABCD”的子串的選項是（）。參考答案：”21ABC”(V)72、下列說法不正確的是（）。參考答案：串不是線性結構(V)73、下面程序段的時間復雜度是（）。for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}參考答案：O(n3)(V)74、下面的操作不是?；具\算的是（）。參考答案：排序操作(V)75、下面的應用中，不符合棧的后進先出特點的是（）。參考答案：算數(shù)運算、邏輯運算和關系運算(V)76、下面關于串的敘述中，正確的是（）。參考答案：模式匹配是串的一種重要運算(V)77、下面關于棧的基本運算算法中，復雜度最高的是（）。參考答案：鏈棧清空運算(V)78、線性結構中數(shù)據(jù)元素之間的關系是（）參考答案：一對一(V)79、向順序棧中壓入新元素時，應當（）。參考答案：先移動棧頂指針，再存入元素(V)80、向一個有127個元素的順序表中插入一個新元素，并保持原來的順序不變，平均要移動（）個元素。參考答案：63.5(V)81、序列狀態(tài)為（）時，快速排序達到最好的時間復雜度。參考答案：序列無序(V)82、一般情況下，將遞歸算法轉換成等價的非遞歸算法應該設置（）。參考答案：棧(V)83、一個具有n個頂點的有向完全圖包含（）條邊。參考答案：n（n-1）(V)84、一棵二叉樹采用鏈式存儲，n個結點的二叉樹共有（）個指針域為空。參考答案：n+1(V)85、一組記錄的關鍵字序列為（80，57，41，39，46，47），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（）。參考答案：39，46，41，57，80，47(V)86、依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）。參考答案：歸并排序(V)87、已知10個數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（）。參考答案：28，16，34，54，62，73，60，26，43，95(V)88、已知某二叉樹的后續(xù)遍歷序列是dabec，中序遍歷是debac，則它的先序遍歷序列是（）。參考答案：cedba(V)89、已知一個有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較（）次。參考答案：5(V)90、以下數(shù)據(jù)結構中（）是線性結構。參考答案：棧(V)91、以下四個串中最小的是（）。參考答案：”ABADF”(V)92、有關線性表的正確說法是（）。參考答案：除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅和一個直接后繼(V)93、有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。參考答案：29/10(V)94、有一個長度為12的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。參考答案：37/12(V)95、與順序表相比，鏈表的優(yōu)勢是（）。參考答案：插入數(shù)據(jù)元素較快(V)96、在二叉樹的第4層最多含有（）個結點。參考答案：8(V)97、在非空雙向循環(huán)鏈表的*p結點之前插入*q結點的操作是（）。參考答案：q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;(V)98、在雙向循環(huán)雙鏈表中，刪除*p結點需要（）。參考答案：p->prior->next=p->next;p->next->prior=p->prior;(V)99、在一非空二叉樹的中序遍歷序列中，根結點的右邊（）。參考答案：只有右子樹上的所有結點(V)100、在一個帶頭結點的單向鏈表中，若要在指針q所指結點后插入p指針所指結點，則執(zhí)行（）。參考答案：p->next=q->next;q->next=p;(V)101、在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。參考答案：2(V)102、在一個長度為n的順序表中為了刪除第5個元素，由第6個元素開始從后到前依次移動了15個元素。則原順序表的長度為（）。參考答案：20(V)103、在一棵度具有5層的滿二叉樹中結點總數(shù)為（）。參考答案：31(V)104、在有向圖的鄰接表中，每個頂點鄰接表鏈接著該頂點所有（）鄰接點。參考答案：出邊(V)105、在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86時，經(jīng)（）次比較后查找成功。參考答案：4(V)106、在長度為n（n>1）的（）上，刪除第一個元素，其算法的時間復雜度為O(n)。參考答案：只有首結點指針h的不帶頭結點的單向循環(huán)鏈表(V)107、棧的操作特性決定了它是一種（）的線性表。參考答案：先進后出(V)108、棧的基本運算包括（）參考答案：取棧頂元素(V)判斷題1、哈夫曼樹一定是完全二叉樹或滿二叉樹。參考答案：×(V)2、AOV網(wǎng)是一個帶權的有向圖。參考答案：×(V)3、按照一定規(guī)則，在二叉排序樹上插入、刪除結點，仍能保持二叉排序樹的性質。參考答案：√(V)4、采用分塊查找時，數(shù)據(jù)的組織方式是把數(shù)據(jù)分成若干塊，塊內數(shù)據(jù)不必有序，但塊間必需有序，每塊內最大（或最小）的數(shù)據(jù)組成索引表。參考答案：√(V)5、采用分塊查找時，數(shù)據(jù)的組織方式為把數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序，每塊內最大（或最小）的數(shù)據(jù)組成索引表。參考答案：×(V)6、采用順序查找法對長度為n（n為偶數(shù)）的線性表進行查找，采用從前向后的方向查找。在等概率條件下成功查找到前n/2個元素的平均查找長度為(n+2)/4。參考答案：√(V)7、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為n/2。參考答案：×(V)8、串的兩種最基本的存儲方式是順序和鏈接。參考答案：√(V)9、串中的元素只可能是字母。參考答案：×(V)10、串中字符的個數(shù)稱為串的長度。參考答案：√(V)11、存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關，而且與圖的邊數(shù)也有關。參考答案：×(V)12、待排序的序列為8,3,4,1,2,5,9，采用直接選擇排序算法，當進行了兩趟選擇后，結果序列為1,2,8,3,4,5,9。參考答案：×(V)13、遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。參考答案：×(V)14、遞歸算法可讀性差，但是效率高參考答案：×(V)15、遞歸算法執(zhí)行時，每次遞歸可將原問題的規(guī)?？s小。參考答案：√(V)16、隊列的特性是先進后出。參考答案：×(V)17、對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。參考答案：√(V)18、對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的行號、列號和元素值三項信息。參考答案：√(V)19、對于一個具有n個結點的單鏈表，在*p結點后插入一個新結點的時間復雜度是O(n)。參考答案：×(V)20、對于一個無向圖，每個頂點的入度等于出度。參考答案：√(V)21、對于一棵深度為4的滿三叉樹，其結點數(shù)為40。參考答案：√(V)22、對于一棵深度為h，度為3的樹最多有（3h-1）/2個結點。參考答案：×(V)23、二叉排序樹中某一結點的左兒子一定小于樹中任一個結點的右兒子。參考答案：×(V)24、二叉樹的遍歷就是按照一定次序訪問樹中所有結點，并且每個結點的值僅被訪問一次的過程。參考答案：√(V)25、二叉樹的根結點值大于其左子樹結點的值，小于右子樹結點的值，則它是一棵二叉排序樹。參考答案：×(V)26、二叉樹中任一結點的值均大于其左孩子的值，小于其右孩子的值，則它是一棵二叉排序樹。參考答案：×(V)27、二分查找是一種最簡單的查找方法。參考答案：×(V)28、分塊查找分為兩個步驟：第一步是要對索引表進行查找；第二步是在塊中查找。這兩步查找都可以采用折半查找或者順序查找方法。參考答案：×(V)29、父親李貴有兩個兒子李萬勝和李萬利，李萬勝又有三個兒子李建新、李建中和李建國，這個家庭可以用樹結構來描述。參考答案：√(V)30、各種鏈表只需定義有兩個域的結點。參考答案：×(V)31、根據(jù)圖的存儲結構進行某種次序的遍歷，得到的頂點序列是唯一的。參考答案：×(V)32、哈夫曼樹葉結點數(shù)比非葉結點數(shù)多1。參考答案：√(V)33、哈夫曼樹只存在著雙支結點，不存在單支結點。參考答案：√(V)34、計算機所處理的數(shù)據(jù)一般具有某種關系,這是指數(shù)據(jù)元素與數(shù)據(jù)元素之間存在的某種關系。參考答案：√(V)35、健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。參考答案：√(V)36、具有10個結點的完全二叉樹有5個葉子。參考答案：√(V)37、具有12個結點的完全二叉樹的深度為4。參考答案：√(V)38、具有n個結點的二叉樹，采用二叉鏈表存儲，共有n-1個空鏈域。參考答案：×(V)39、鏈接存儲表示中數(shù)據(jù)元素之間的邏輯關系是由指針表示的。參考答案：√(V)40、鏈棧通常不會出現(xiàn)棧滿的狀態(tài)參考答案：√(V)41、兩個字符串比較時，較長的串比較短的串大參考答案：×(V)42、鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。參考答案：×(V)43、滿二叉樹中沒有度為1的結點。參考答案：√(V)44、冒泡排序是一種比較簡單的插入排序方法。參考答案：×(V)45、冒泡排序是一種比較簡單的交換排序方法。參考答案：√(V)46、如果結點A有3個兄弟3個孩子，而且B是A的雙親，則A的度是3。參考答案：×(V)47、如果一個葉子結點是某二叉樹中序遍歷序列的最后一個結點，那么它也是該二叉樹的先序遍歷序列的最后一個結點。參考答案：√(V)48、若讓元素1,2,3依次進棧，則出棧次序1,3,2是不可能出現(xiàn)的情況。參考答案：×(V)49、若讓元素a,b,c依次進棧，則出棧次序c,a,b是不可能出現(xiàn)的情況。參考答案：√(V)50、若樹中各結點的子樹是按照一定的次序從左向右安排的，則稱之為有序樹。參考答案：√(V)51、若一個強連通圖有n個頂點，則該強連通圖中至少含有n條有向邊。參考答案：√(V)52、散列技術中的沖突指的是兩個元素具有相同的序號。參考答案：×(V)53、森林是m（m≥0）棵互不相交的樹的集合。參考答案：√(V)54、刪除順序表的最后一個元素，需要移動的元素最多。參考答案：×(V)55、設廣義表L=（（），（）），則其表頭是（（））。參考答案：×(V)56、設廣義表L=（（），（）），則其表尾是（）。參考答案：×(V)57、設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為BCDA。參考答案：×(V)58、設有6個結點的無向圖，該圖至少應有6條邊才能確保是一個連通圖。參考答案：×(V)59、設有一個不帶頭結點的單向循環(huán)鏈表，結點的指針域為next，指針p指向尾結點，現(xiàn)要使p指向第一個結點，可用語句p=p->next;。參考答案：√(V)60、設有一個單向鏈表，結點的指針域為next，頭指針為head，p指向尾結點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=head。參考答案：√(V)61、設有一個單向循環(huán)鏈表，結點的指針域為next，頭指針為head，指針p指向表中某結點，若邏輯表達式p->next==head;的結果為真，則p所指結點為尾結點。參考答案：√(V)62、設有一個長度為40的順序表，要刪除第8個元素需移動元素的個數(shù)為33。參考答案：×(V)63、深度為k的完全二叉樹至少有2k-1個結點。參考答案：×(V)64、使用鄰接矩陣存儲圖的時候，占用空間大小與圖的結點個數(shù)沒有關系。參考答案：×(V)65、使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲空間。參考答案：√(V)66、樹的所有結點有且只有一個前驅結點。參考答案：×(V)67、樹是一種線性結構。參考答案：×(V)68、樹是一種重要的非線性數(shù)據(jù)結構。參考答案：√(V)69、樹型結構的元素間存在多對多的關系。參考答案：×(V)70、樹最適合表示元素之間具有層次關系的數(shù)據(jù)。參考答案：√(V)71、數(shù)據(jù)的邏輯結構是與存儲該結構的計算機相關的。參考答案：×(V)72、數(shù)據(jù)的邏輯結構是指各數(shù)據(jù)元素之間的邏輯關系，是用戶根據(jù)應用需要建立的。參考答案：√(V)73、數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內的實際存儲形式。參考答案：√(V)74、數(shù)據(jù)結構中,元素之間存在多對多的關系稱為樹狀結構。參考答案：×(V)75、數(shù)據(jù)項是數(shù)據(jù)的最小單位。參考答案：√(V)76、數(shù)組通常具有的操作是順序存取。參考答案：×(V)77、順序查找是一種最簡單的查找方法。參考答案：√(V)78、順序隊列的入隊算法是先檢查隊列是否為滿，若不滿則將新元素值賦給隊頭指針所指向的數(shù)據(jù)單元，再將隊頭指針加1。參考答案：×(V)79、圖的廣度優(yōu)先搜索序列是惟一的。參考答案：×(V)80、圖的連通分量是無向圖的極大連通子圖。參考答案：√(V)81、圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。參考答案：√(V)82、圖的最小生成樹只有一棵。參考答案：×(V)83、完全二叉樹中沒有度為1的結點。參考答案：×(V)84、線性表的順序存儲是利用數(shù)組來實現(xiàn)的。參考答案：√(V)85、線性表是一個有限序列，不可以為空。參考答案：×(V)86、線性表用順序方式存儲可以隨機訪問。參考答案：√(V)87、向一個長度為n的順序表中的第i個元素（1≤i≤n）之前插入一個元素時，需向后移動n-i個元素。參考答案：×(V)88、序列15,13,16,14,19,17，采用冒泡排序算法(升序)，經(jīng)一趟冒泡后，結果序列是13,15,14,16,17,19。參考答案：√(V)89、序列3,1,7,18,6,9,13,12經(jīng)一趟歸并排序的結果為1,3,7,18,6,9,13,12。參考答案：×(V)90、循環(huán)隊列隊頭指針在隊尾指針后一個位置，隊列是“滿”狀態(tài)。參考答案：√(V)91、循環(huán)隊列是將隊列想象成一個首尾相接的圓環(huán)。參考答案：√(V)92、要在一個單向鏈表中刪除p所指向的結點，已知q指向p所指結點的直接前驅結點，若鏈表中結點的指針域為next，則可執(zhí)行q->next=p->next。參考答案：√(V)93、一個廣義表的表頭總是一個廣義表。參考答案：×(V)94、一個空格的串的長度是0。參考答案：×(V)95、一個有向圖的鄰接表和逆鄰接表中的節(jié)點個數(shù)一定相等。參考答案：√(V)96、一棵二叉樹每一層的結點數(shù)都達到最大值，則這個二叉樹是完全二叉樹。參考答案：×(V)97、已知一棵樹的先序序列和后序序列，一定能構造出該樹。參考答案：×(V)98、用鄰接矩陣存儲圖的時候，占用空間大小不但與圖的結點個數(shù)有關還與圖的邊數(shù)有關。參考答案：×(V)99、用數(shù)組實現(xiàn)順序棧，棧底可以是數(shù)組空間的任何一端參考答案：√(V)100、用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。參考答案：√(V)101、由一個具有n個頂點的連通圖生成的最小生成樹中，具有n-1條邊。參考答案：√(V)102、在單鏈表中，要刪除某一指定的結點，必須找到該結點的直接前驅結點。參考答案：√(V)103、在隊列的順序存儲結構中，當插入一個新的隊列元素時，尾指針后移，當刪除一個元素隊列時，頭指針后移。參考答案：√(V)104、在對10個記錄的序列(14,30,10,7,22,13,66,85,47,58)進行直接插入排序時，當把第6個記錄13插入到有序表時，為尋找插入位置，需比較3次。參考答案：×(V)105、在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是哈希表查找。參考答案：√(V)106、在歸并排序中，在第3趟歸并中，是把長度為4的有序表歸并為長度為8的有序表。參考答案：√(V)107、在雙向循環(huán)鏈表上，刪除最后一個結點，其算法的時間復雜度為0(1)。參考答案：√(V)108、在線性表的順序存儲中，元素之間的邏輯關系是通過物理存儲位置決定的；在線性表的鏈式存儲中，元素之間的邏輯關系是通過鏈域的指針值決定的。參考答案：√(V)109、在一個查找表中，能夠唯一地確定一個記錄的關鍵字稱為主關鍵字。參考答案：√(V)110、在一個順序存儲的循環(huán)隊列中,隊頭指針指向隊頭元素的后一個位置。參考答案：×(V)111、在有序表A[1…18]中，采用二分查找算法查找元素值等于A[17]的元素，所比較過的元素的下標依次是9、14、16、17。參考答案：√(V)112、在有序順序存儲的線性表中查找一個元素，用折半查找速度一定比順序查找快。參考答案：×(V)113、在長度為n的順序表L中查找指定元素值的元素，其時間復雜度為O(n)。參考答案：√(V)114、棧是限定在表的兩端進行插入和刪除操作的線性表，又稱為先進先出表。參考答案：×(V)115、長度為0的線性表稱為空表。參考答案：√(V)116、折半查找方法運用在升序序列比降序序列效率更高，所以降序序列最好先轉換為升序序列。參考答案：×(V)117、字符串a(chǎn)1=〝heijing〞,a2=〝hen〞,a3=〝heifang〞,a4=“heni〞，其中最小的是a2。參考答案：×(V)118、字符串屬于線性的數(shù)據(jù)結構參考答案：√(V)綜合題1、在下面空格處填寫一條語句，以使下面的順序隊列入隊算法完整。voidInQueue(structSeqQueue*sq,intx){if(sq->rear==MaxSize)

{printf(“隊列已滿！\n”);exit(1);}______________sq->rear++;}參考答案：sq->data[sq->rear]=x;(V)2、設有數(shù)據(jù)集合{50，39，17，83，91，14，65}，依次取集合中各數(shù)據(jù)構造一棵二叉排序樹，是如下的（）。參考答案：(V)3、以下為求二叉樹深度的算法，完成程序中空格部分。intBTreeDepth(BTreeNode*BT){

if(BT==NULL)

return0;

else

{intdep1=BTreeDepth(BT->left);/*計算左子樹的深度*/

intdep2=BTreeDepth(BT->right);/*計算右子樹的深度*/

if(________)

returndep1+1;

else

returndep2+!;

}}參考答案：dep1>dep2(V)4、設有一個頭指針為head的不帶頭結點單向鏈表中（結點類型為NODE），p為指向該鏈表中某個結點的指針。以下程序段為插入一個指針為s的結點，使它成為p結點的直接前驅，請把合適選項填寫到空行處。NODE*q;q=head;while(q->next!=p)q=q->next;s->next=p;________;參考答案：q->next=s(V)5、寫出下列程序段執(zhí)行后的結果SeqQueueQ;

InitQueue(Q);inti,a[4]={5,8,12,15};for(i=0;i<4;i++)InQueue(Q,a[i]);InQueue(Q,OutQueue(Q));InQueue(Q,30);InQueue(Q,OutQueue(Q)+10);while(!QueueEmpty(Q))printf(“%d”,OutQueue(Q));參考答案：121553018(V)6、在下面空格處填寫一條語句，以使下面的出棧算法完整。ElemTypePop(structSeqStack*s,ElemTypex){if(StackEmpty(s))

{printf(“棧下溢錯誤！\n”);exit(1);}x=s->data[s->top];

________

returnx;}參考答案：s->top--;(V)7、設某二叉樹先序遍歷為abdec，中序遍歷為dbeac。該二叉樹的圖形是（）。參考答案：(V)8、二叉排序樹結點類型定義如下：typedefstructBnode{intkey;structBnode*left;structBnode*right;}Bnode;以下為二叉排序樹的查找算法，完成程序中空格部分。Bnode*BSearch(Bnode*bt,intk){

Bnode*p;

if(bt==NULL)

return(bt);

p=bt;while(________)

{if(kkey)

p=p->left;

else

p=p->right;if(p==NULL)break;

}return(p);}參考答案：p->key!=k(V)9、一組記錄的關鍵字序列為（6，9，7，4，5，8），利用堆排序（堆頂元素是最小元素）的方法建立初始堆是如下哪個圖？（）參考答案：(V)10、在下面空格處填寫一條語句，以使下面的循環(huán)隊列出隊算法完整。ElemTypeOutQueue(structSeqQueue*sq){if(sq->rear==sq->front)

{printf(“隊列已空，不能進行出隊操作！\n”);exit(1);}________sq->front=(sq->front+1)%MaxSize;

returnx;}參考答案：x=sq->data[sq->front];(V)11、設數(shù)據(jù)序列為：{53,30,37,12,45,24,96}，從空二叉樹開始逐個插入該數(shù)據(jù)序列來形成二叉排序樹，若希望高度最小，應該選擇的序列是（）。參考答案：37,24,12,30,53,45,96(V)12、以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結點）。voidPreorder(structBTreeNode*BT){if(BT!=NULL)

{_________________;Preorder(BT-->left);Preorder(BT-->right);}}參考答案：printf(“%c”,BT->data)(V)13、設查找表為：用折半查找在該查找表成功查找到元素55需要經(jīng)過（）次比較。參考答案：2(V)14、設線性表以不帶頭結點的單向鏈表存儲，鏈表頭指針為head。以下程序的功能是輸出鏈表中各結點中的數(shù)據(jù)域data，完成程序中空格部分。#defineNULL0voidmain(){NODE*head,*p;p=head;/*p為工作指針*/do{printf(“%d\n”,p->data);p=p->next;}while(________);}參考答案：p!=NULL(V)15、設關鍵字序列為：（36，69，46，28，30，74），將此序列用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結果為（）。參考答案：30，28，36，46，69，74(V)16、以1，2，3，6，7，8作為葉結點的權，構造一棵哈夫曼樹是如下哪個圖？（）參考答案：(V)17、在下面空格處填寫一條語句，以使下面的串連接算法完整。char*strcat(char*s1,char*s2){char*p=s1;while(*p!='\0')p++;while(*s2!='\0'){*p=*s2;p++;_____}*p='\0';

returns1;}參考答案：s2++;(V)18、以下程序是快速排序的算法，完成程序中空格部分。設待排序的記錄序列存放在a[start],…a[end]中，按記錄的關鍵字進行快速排序，先進行一次劃分，再分別進行遞歸調用。

voidquicksort(NODEa[],intstart,intend){inti,j;NODEmid;if(start>=end)return;i=start;j=end;mid=a[i];while(i<J)a[j].key&&while(imid.key)j--;if(i<J)&&while(i<j)i++;a[i].key<="mid.key)"/>參考答案：quicksort(a,start,i-1);(V)19、在下面空格處填寫一條語句，以使下面的串比較算法完整。intstrcmp(char*s1,char*s2){inti;for(i=0;s1[i]!='\0'&&s2[i]!='\0';i++)if(s1[i]>s2[i])

return1;else

if(s1[i]<S2[I])}參考答案：return0;(V)20、設查找表為(16,15,20,53,64,7)，用冒泡法對該表進行排序，在排序后的有序表的基礎上進行折半查找，在等概率條件下,成功查找的平均查找長度為（）。參考答案：14/6(V)21、一組記錄的關鍵字序列為（36，69，46，28，30，84），對該序列進行直接選擇排序（每次選擇最小關鍵字），第二趟排序后的結果序列為（）。參考答案：28，30，46，36，69，84(V)22、已知某帶權圖的鄰接矩陣如下所示：從頂點1出發(fā)的廣度優(yōu)先搜索序列為（）。參考答案：1，2，3，4，5，6(V)23、在下面空格處填寫一條語句，以使下面的進棧算法完整。voidPush(structSeqStack*s,ElemTypex){if(s->top==MaxSize-1)

{printf(“棧滿溢出錯誤！\n”);exit(1);}________s->data[s->top]=x;}參考答案：s->top++;(V)24、以下是直接插入排序算法對存放在a[0],a[1],……,a[n-1]中，長度為n的記錄序列按關鍵字key由小到大排序，完成程序中空格部分。voiddisort(NODEa[],intn){inti,j;NODEtemp;for(i=1;i<N;I++)

{j(temp="a[i];

j=i-1;

while">=0&&temp.key<A[J].KEY)

{a[j+1]="a[j];

_______;

}">參考答案：j--(V)25、在下面空格處填寫一條語句，以使下面的順序隊列出隊算法完整。ElemTypeOutQueue(structSeqQueue*sq){if(sq->rear