數(shù)據(jù)結(jié)構(gòu)考試題.doc

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