數(shù)據(jù)結構復習內容

數(shù)據(jù)結構》復習內容一．單選題鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是B插入操作更加方便通常不會出現(xiàn)棧滿的情況不會出現(xiàn)?？盏那闆r刪除操作更加方便從未排序序列中挑選元素，將其放在已排序序列的一端，這種排序方法稱為A選擇排序 B.插入排序 C.快速排序 D.冒泡排序若n個頂點的無向圖采用鄰接矩陣存儲方法，該鄰接矩陣是一個B一般矩陣 B.對稱矩陣 C.對角矩陣 D.稀疏矩陣一個n*n的對稱矩陣，如果以行或列為主序放入內存，則其容量為Cn*n B.n*n/2 C.(n+1)*n/2 D.(n+1)*(n+1)/2當棧中的元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為Bn-1 B.n C.n+1 D.n/2在單鏈表中，增加頭結點的目的是C使單鏈表至少有一結點標志表中首結點位置方便運算的實現(xiàn)說明單鏈表是線性表的鏈式存儲實現(xiàn)TOC\o"1-5"\h\z在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 倍。C1/2 B.1 C.2 D.4下列排序方法中，排序趟數(shù)與序列的原始狀態(tài)有關的方法是D選擇排序 B.希爾排序 C.堆排序 D.冒泡排序在一棵具有五層的滿二叉數(shù)中，結點總數(shù)為AA.31 B.32 C.33 D.16線性表是A一個有限序列，可以為空一個有限序列，不能為空一個無限序列，可以為空一個無限序列，不能為空下列排序算法中， 排序在每趟結束后不一定能選出一個元素放到其排好序的最終位置上。CA.選擇 B.冒泡 C.歸并 D.堆二維數(shù)組a的每個元素是由6個字符組成的串，行下標的范圍從0到8，列下標的范圍從1到10，則存放a至少需要 個字節(jié)。DA.90 B.180 C.270 D.540對有14個元素的有序表A[1..14]作二分查找，查找元素A[4]時的被比較元素依次為CA[1],A[2],A[3],A[4]A[1],A[14],A[7],A[4]A[7],A[3],A[5],A[4]A[7],A[5],A[3],A[4]以二叉鏈表作為二叉樹的存儲結構，在具有n個結點的二叉鏈表中(n>0)，空鏈域的個數(shù)為CA.2n-1 B.n-1 C.n+1 D.2n+1向順序棧中壓入元素時A先移動棧頂指針，后存人元素先存人元素，后移動后移動棧頂指針誰先誰后無關緊要同時進行下列存儲形式中，哪一個不是樹的存儲形式DA.雙親表示法B.孩子鏈表表示法 C.孩子兄弟表示法 D.順序存儲表示法對n個記錄的文件進行堆排序，最壞情況下的執(zhí)行時間為A.O(logn) B.O(n) C.O(nlogn) D.O(n2)19用鏈表表示線性表的優(yōu)點是C 2便于隨機存取花費的存儲空間比順序表少便于插入和刪除數(shù)據(jù)元素的物理順序與邏輯順序相同20?下列有關線性表的敘述中，正確的是A線性表中的元素之間是線性關系線性表中至少有一個元素線性表中任何一個元素有且僅有一個直接前驅線性表中任何一個元素有且僅有一個直接后繼線性表的順序存儲結構中，一般情況下，在第i(lWiWn)個元素之前插入一個元素時，需向后移動()個元素。1n-i+1 ②n-i ③i ④i+1若一個棧的進棧序列為1，2，3，4，則()不可能為一個出棧序列。4①1,2，3，4 ②4,3，2，1 ③3,2，1，4 ④4,2，3，1鏈隊列中，用于判斷隊列為“空”的條件是()。3①Q.next二Q.front ②Q.front二NIL ③Q.front二Q.rear ④Q.rear二NIL在線性表的存儲結構中，能從當前結點出發(fā)訪問任一點的存儲結構是()。4①單鏈表②雙向鏈表③循環(huán)鏈表④②和③空串是指()。3①由一個或多個空格組成的串 ②串中字符是若干個“空”的串③零個字符的串 ④只有結尾字符的串需要預分較大空間，刪除操作時需要移動元素的線性表的存儲結構是()。2①單鏈表 ②順序表 ③循環(huán)鏈表④靜態(tài)鏈表樹中結點的()稱為樹的深度。3①最小層次②平均層次③最大層次④子樹層次哈夫曼樹或最優(yōu)二叉樹是()最小的二叉樹。2①路徑長度②帶權路徑長度③深度④度若采用順序存儲結構存儲滿二叉樹的全部結點，設每一個結點占用2個存儲單元，則深度為K的滿二叉樹共占用()個存儲單元。4①2k ②2k+1 ③2k+1 ④2k+1-2下面二叉樹中一定是完全二叉樹的是()。2①平衡二叉樹②滿二叉樹③單枝二叉樹④二叉排序樹在n個頂點，e條邊的連通圖中，連通分量個數(shù)為()2①0 ②1 ③n ④e下列排序算法中，不穩(wěn)定的算法是()。1①快速排序②基數(shù)排序③直接插入排序④簡單選擇排序不需要進行關鍵字之間比較的排序方法是()。4①簡單排序②快速排序③歸并排序④基數(shù)排序()遍歷二叉排序樹可得到一個關鍵字的有序序列。2①前序 ②中序 ③后序 ④隨意在數(shù)據(jù)結構中，從邏輯關系上可以把數(shù)據(jù)結構分成()3①動態(tài)結構和靜態(tài)結構②緊湊結構和非緊湊結構③線性結構和非線性結構④內部結構和外部結構

對一個滿二叉樹，m個樹葉，n個結點，深度為h,貝1」（）。4@n=h+m ②h+m=2n ③m=h-l ④n=2h-lL是帶表頭的單向鏈表的表頭指針，該表為空的條件是（ ）。CA、n==0 B、L==null C、L->next==null D、L->next=L設數(shù)組申bm-1］中有一循環(huán)隊列，F(xiàn),R是隊頭隊尾指針，空隊列的條件是（B）A、n=0BA、n=0B、F=RC、F=R-1D、F=R+140.棧上可進行的操作是（C40.棧上可進行的操作是（CA、訪問棧的第i個元素C、在棧頂后插入一個元素X）。B、在棧的第i個元素之后插入元素D、刪除棧底元素41具有n個頂點的強連通圖，其弧條數(shù)的最小值為（B）。A、n+1 B、n C、n-1 D、n-242.具有n個頂點的DAG圖（有向無環(huán)圖），其入度為0的的頂點個數(shù)至少有（D）。A、n B、n/2 C、n/4 D、143.一個三對角矩陣A 已按行壓縮存儲到一維數(shù)組B中，則B的長度至少是（D■43.一個三對角矩陣A 已按行壓縮存儲到一維數(shù)組B中，則B的長度至少是（D■nXB、3n）。A、3n+1 B、3n C、3n-1首先訪問結點的左子樹，然后訪問該結點①前序遍歷棧的特點是（1 ）①先進后出②先進先出在線性表L=（a1，a2，……①直接后繼 ②直接前驅雙重鏈表表示線表時，較之單鏈表更易進行（4①結點的插入 ②結點的刪除 ③線性表的擴充快速排序執(zhí)行一遍后，已經到位的元素個數(shù)至少是①1 ②2 ③n④2/n50.采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的（4）。②后序遍歷③中序遍歷D、3n-2最后訪問結點的右子樹，這種遍歷稱為（3）④層次遍歷③任意進出a）中，a稱為a.的n i+1 i③孩子④兩斷進出（1）。④兄弟）。④對結點的訪問）。①先根遍歷 ②中根遍歷③后根遍歷 ④按層遍歷帶頭結點的單鏈表head為空的判定條件是（2）。①head==NULL ②head->next==NULL③head->next==head ④head!==NULL一個棧的入棧序列是a,b,c,d,e貝棧的不可能的輸出序列是（3）。①edcba ②decba ③dceab ④abcde不是串a='ABCABDEABX'的子串是（4 ）。①串b=‘ABC'②串b=‘BX' ③串b=‘AB' ④串b=‘AC'數(shù)組通常具有的兩種基本操作是（C）A.建立與刪除 B.索引和修改 C.查找和修改 D.查找與索引55?設有一個足夠大的棧，入棧序列為x,y,z,u,v,下列哪一個出棧序列是不可能序列（A）A、x,v,u,y,z B、z,y,u,v,x C、z,y,u,x,v D、y,z,u,v,x中序遍歷和后序遍歷所得序列完全相同的二叉樹是（C）A、空二叉樹 B、所有左兒子域為空C、所有右兒子域均為空 D、兒子域中至少有一個為空對五個不同的數(shù)據(jù)進行排序，最多需要比較B次。A.8 B.10 C.15 D.25在線性表的存儲結構中，能從當前結點出發(fā)訪問任一點的存儲結構是（4）①單鏈表②雙向鏈表③循環(huán)鏈表④②和③空串是指（3）。①由一個或多個空格組成的串②串中字符是若干個“空”的串

③零個字符的串④只有結尾字符的串在一般樹中，結點M、N分別為結點P的第i、第i+1個孩子，則該樹轉化為二叉樹后，結點N為結點M的(2)①左孩子②右孩子③兄弟④雙親順序存儲結構僅適合于(2)。①平衡二叉樹②完全二叉樹③二叉排序樹④單枝二叉樹具有n個頂點的強連通圖，其弧條數(shù)的最小值為(3)。①n(n-l) ①n(n-l) ②呼③n n-1)②活動持續(xù)時間最短的活動④源點到匯點路徑長度最長的路徑上的活動關鍵活動是(4)。②活動持續(xù)時間最短的活動④源點到匯點路徑長度最長的路徑上的活動(2)遍歷二叉排序樹可得到一個關鍵字的有序序列。①前序 ②中序 ③后序 ④隨意在堆排序過程中，當初始堆建成后(設堆頂為最小)，初始堆滿足(3)。①前序遍歷結果有序②中序遍歷結果有序③任一結點的關鍵字均小于等于它的兒子的關鍵字④任一結點的關鍵字均小于它左兒子的關鍵字，大于等于它右兒子的關鍵字在數(shù)據(jù)結構中，從邏輯關系上可以把數(shù)據(jù)結構分成(3)①動態(tài)結構和靜態(tài)結構②緊湊結構和非緊湊結構③線性結構和非線性結構④內部結構和外部結構對采用二分查找法進行查找運算的查找表，要求按(3)方式進行存儲①順序存儲鏈式存儲①順序存儲鏈式存儲順序存儲且結點按關鍵字有序④鏈式存儲且結點按關鍵字有序69．若要在一棵完全二叉村中尋找任意結點的雙親，則最佳存儲方案為(B)。A、A、帶有雙親信息的三叉鏈表B、順序存儲C、二叉鏈表DC、二叉鏈表70.在下面各種鏈表結構中，能在0(1)時間內完成在指定結點P之前搜入元素X的結構是(D)。A、單鏈表B、單向循環(huán)鏈表 C、帶表頭的單鏈表 D、雙向循環(huán)鏈表二判斷正誤題(正確的在題后的括號內劃“丿,錯誤的劃“X”)由于棧只能在棧頂進行插入或刪除操作，所以棧不是線性表。()Xn個結點有向圖，若它有n(n-1)條邊，則它一定是強連通的。()X鄰接矩陣存儲圖時所需存儲空間大小與圖的結點數(shù)有關，而與邊數(shù)無關。()n個結點的樹的各結點度數(shù)之和為n-1。()所謂沖突即是兩個關鍵字的值相同的元素，其哈希地址相同。()任何有向無環(huán)圖都存在一個唯一的拓撲序列。()X二叉樹是樹的一種特殊情況。()X在用線性探查法解決沖突所構造的散列表中，每組同義詞中至少有一個元的地址正好等于其散列地址。()X線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。()X二叉樹中任何一個結點的度都是2。()X用直接選擇排序方法分別對序列S1= (1，2,3, 4, 5, 6, 7)和序列S2=(