數據結構考試題.doc

一 判斷題 10*1分1調用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（ ）2分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（ ）3冒泡排序在初始關鍵字序列為逆序的情況下執(zhí)行的交換次數最多。（ ）4滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ ）5設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ ）6層次遍歷初始堆可以得到一個有序的序列。（ ）7設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8線性表的順序存儲結構比鏈式存儲結構更好。（ ）9中序遍歷二叉排序樹可以得到一個有序的序列。（ ）10.快速排序是排序算法中平均性能最好的一種排序。（ ）1不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。（ ）2當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。（）3設某堆中有n個結點，則在該堆中插入一個新結點的時間復雜度為O(log2n)。（ ）4完全二叉樹中的葉子結點只可能在最后兩層中出現。（）5哈夫曼樹中沒有度數為1的結點。（ ）6對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（ ）7先序遍歷一棵二叉排序樹得到的結點序列不一定是有序的序列。（ ）8由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（ ）9線性表中的所有元素都有一個前驅元素和后繼元素。（ ）10.帶權無向圖的最小生成樹是唯一的。（ ）1. 如果兩個關鍵字的值不等但哈希函數值相等，則稱這兩個關鍵字為同義詞。（ ）2. 設初始記錄關鍵字基本有序，則快速排序算法的時間復雜度為O(nlog2n)。（ ）3. 分塊查找的基本思想是首先在索引表中進行查找，以便確定給定的關鍵字可能存在的塊號，然后再在相應的塊內進行順序查找。（ ）4. 二維數組和多維數組均不是特殊的線性結構。（ ）5. 向二叉排序樹中插入一個結點需要比較的次數可能大于該二叉樹的高度。（ ）6. 如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。（ ）7. 非空的雙向循環(huán)鏈表中任何結點的前驅指針均不為空。（ ）8. 不論線性表采用順序存儲結構還是鏈式存儲結構，刪除值為X的結點的時間復雜度均為O(n)。（ ）9. 圖的深度優(yōu)先遍歷算法中需要設置一個標志數組，以便區(qū)分圖中的每個頂點是否被訪問過。（ ）10. 稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（ ）1 有向圖的鄰接表和逆鄰接表中表結點的個數不一定相等。( )2 對鏈表進行插入和刪除操作時不必移動鏈表中結點。( )3 子串“ABC”在主串“AABCABCD”中的位置為2。( )4 若一個葉子結點是某二叉樹的中序遍歷序列的最后一個結點，則它必是該二叉樹的先序遍歷序列中的最后一個結點。( )5 希爾排序算法的時間復雜度為O(n2)。( )6 用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數無關而與圖中邊數有關。( )7 中序遍歷一棵二叉排序樹可以得到一個有序的序列。( )8 入棧操作和入隊列操作在鏈式存儲結構上實現時不需要考慮棧溢出的情況。( )9 順序表查找指的是在順序存儲結構上進行查找。（ ）10 堆是完全二叉樹，完全二叉樹不一定是堆。（ ）二選擇題15*2分：1 以下數據結構中哪一個是非線性結構？( D ) A. 隊列 B. 棧 C. 線性表 D. 二叉樹2 樹最適合用來表示( A )。 A.有序數據元素 B.無序數據元素 C.元素之間具有分支層次關系的數據 D.元素之間無聯系的數據3二叉樹的第k層的結點數最多為( D ). A2k-1 B.2K+1 C.2K-1 D. 2k-14若有18個元素的有序表存放在一維數組A19中，第一個元素放A1中，現進行二分查找，則查找A3的比較序列的下標依次為( C ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，35對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K %9作為散列函數，則散列地址為1的元素有（ D ）個， A1 B2 C3 D46下面關于線性表的敘述錯誤的是（ D ）。(A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B) 線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C) 線性表采用鏈式存儲便于插入和刪除操作的實現(D) 線性表采用順序存儲便于插入和刪除操作的實現.7設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA8數據的最小單位是（A ）。(A) 數據項(B) 數據類型(C) 數據元素(D) 數據變量9設一個有序的單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（ D ）。(A) O(log2n)(B) O(1)(C) O(n2)(D) O(n)10設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（B ）次。(A) 25(B) 10(C) 7(D) 111執(zhí)行一趟快速排序能夠得到的序列是（A ）。(A) 41，12，34，45，27 55 72，63(B) 45，34，12，41 55 72，63，27(C) 63，12，34，45，27 55 41，72(D) 12，27，45，41 55 34，63，7212設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（A ）。(A) head=0(B) head-next=0(C) head-next=head(D) head!=013時間復雜度不受數據初始狀態(tài)影響而恒為O(nlog2n)的是（A ）。(A) 堆排序(B) 冒泡排序(C) 希爾排序(D) 快速排序14程序段s=i=0；do i=i+1； s=s+i；while(i=n)；的時間復雜度為（A ）。(A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(n3/2)15下列程序段的時間復雜度為（ A）。for(i=0； im； i+) for(j=0； jt； j+) cij=0；for(i=0； im； i+) for(j=0； jt； j+) for(k=0； kright=s； s-left=p； p-right-left=s； s-right=p-right；(B) s-left=p；s-right=p-right；p-right=s； p-right-left=s；(C) p-right=s； p-right-left=s； s-left=p； s-right=p-right；(D) s-left=p；s-right=p-right；p-right-left=s； p-right=s；18設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（ D ）存儲方式最節(jié)省運算時間。(A) 單向鏈表(B) 單向循環(huán)鏈表(C) 雙向鏈表(D) 雙向循環(huán)鏈表19設輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（ B ）。(A) 5，3，4，6，1，2(B) 3，2，5，6，4，1(C) 3，1，2，5，4，6(D) 1，5，4，6，2，320設一組權值集合W=(15，3，14，2，6，9，16，17)，要求根據這些權值集合構造一棵哈夫曼樹，則這棵哈夫曼樹的帶權路徑長度為（D ）。(A) 129(B) 219(C) 189(D) 22921設一組初始記錄關鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F，X)，則按字母升序的第一趟冒泡排序結束后的結果是（ ）。(A) F，H，C，D，P，A，M，Q，R，S，Y，X(B) P，A，C，S，Q，D，F，X，R，H，M，Y(C) A，D，C，R，F，Q，M，S，Y，P，H，X(D) H，C，Q，P，A，M，S，R，D，F，X，Y1 數據結構的三個層次：邏輯結構、存儲結構、操作。數據結構的基本結構關系圖：線性結構、樹形結構、圖狀結構。2 算法的時間復雜度的求解3 線性表4 單鏈表三簡答題和應用題45分：1算法的五個特征：有窮性、確定性、可行性、輸入、輸出2線性表順序存儲和鏈式存儲的比較（優(yōu)缺點）鏈式存儲結構: (1)占用額外的空間以存儲指針(浪費空間) (2)存取某個元素速度慢 (3)插入元素和刪除元素速度快 (4)沒有空間限制,存儲元素的個數無上限,基本只與內存空間大小有關.順序存儲結構: (1)空間利用率高 (2)存取某個元素速度快 (3)插入元素和刪除元素存在元素移動,速度慢,耗時 (4)有空間限制,當需要存取的元素個數可能多于順序表的元素個數時,會出現溢出問題.當元素個數遠少于預先分配的空間時,空間浪費巨大. 在存取元素頻繁,但刪除或插入操作較少的情況宜用順序表.堆排序,二分查找適宜用順序表.3棧和隊列的特點：棧的特點：后進先出，只能在棧頂插入和刪除；隊列的特點：先進先出，只允許在隊尾插入和隊首刪除。5 AOV網的定義：用頂點表示活動，用弧表示活動間的優(yōu)先關系的有向圖稱為頂點表示活動的網，簡稱AOV網。應