數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題-wenkub.com
2025-04-14 01:46 本頁(yè)面
【正文】 （ ） 40．具有 n 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)有多種，其中樹(shù)高最小的二叉排序樹(shù)是最佳的。( ) 36．冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)。（ √ ） 32．對(duì)于任意一個(gè)圖，從它的某個(gè)結(jié)點(diǎn)進(jìn)行一次深度或廣度優(yōu)先遍歷可以訪問(wèn)到該圖的每個(gè)頂點(diǎn)。（ √ ） 28．用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。（ √ ） 24．廣義表((( a ), b), c ) 的表頭是(( a ), b)，表尾是( c )。（） 20．?dāng)?shù)組元素的下標(biāo)值越大，存取時(shí)間越長(zhǎng)。 ( ) 16．隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出的結(jié)構(gòu)。（ ） 13．鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序表中效率高。（ ） 9．線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。（ ） 5．線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。 1．在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮各結(jié)點(diǎn)的值如何。一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集，它由若干索引項(xiàng)組成，索引項(xiàng)的結(jié)構(gòu)為 關(guān)鍵字 和 關(guān)鍵字對(duì)應(yīng)記錄的地址 。 35．一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵 二叉排序 樹(shù)而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。 31．某二叉樹(shù)的前序遍歷序列是 abdgcefh，中序序列是 dgbaechf，其后序序列為 gdbehfca 。 27．在有 n 個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為_(kāi)_n+1__。 23．二維數(shù)組 M 的每個(gè)元素是 6 個(gè)字符組成的串，行下標(biāo) i 的范圍從 0 到 8，列下標(biāo) j 的范圍從 1 到 10，則存放 M 至少需要 540 個(gè)字節(jié)；M 的第 8 列和第 5 行共占 108 個(gè)字節(jié)。空白串是由一個(gè)或多個(gè)空格字符組成的串，其長(zhǎng)度等于其包含的空格個(gè)數(shù)。 16．順序存儲(chǔ)結(jié)構(gòu)是通過(guò) 下標(biāo) 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò) 指針 表示元素之間的關(guān)系的。 12．在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 前驅(qū) 結(jié)點(diǎn)，另一個(gè)指向 后繼結(jié)點(diǎn) 。 8．評(píng)估一個(gè)算法的優(yōu)劣，通常從 時(shí)間復(fù)雜度 和 空間復(fù)雜度 兩個(gè)方面考察。 4．線性結(jié)構(gòu)中元素之間存在 一對(duì)一 關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在 一對(duì)多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對(duì)多 關(guān)系。（n 為元素個(gè)數(shù)） A．O（n) B．O(log2n) C．O(nlog2n) D． O(n2) 二、填空題。下列關(guān)鍵碼序列 D 是一個(gè)堆。 A．希爾排序 B。 B．所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)。 C．負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度。這種說(shuō)法 B 。 A 散列存儲(chǔ) B 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) C 壓縮存儲(chǔ) D 索引存儲(chǔ) 91．對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 B 。 A．先序遍歷 B．中序遍歷 C．后序遍歷 D．按層遍歷 87．具有 n 個(gè)結(jié)點(diǎn)的連通圖至少有 A 條邊。 A．1/2 B 1 C 2 D 4 81．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 B 倍。 A．①②③ B．②③④ C．②④ D．①④ 77．設(shè)森林 F 對(duì)應(yīng)的二叉樹(shù)為 B，它有 m 個(gè)結(jié)點(diǎn)，B 的根為 p，p 的右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為 n，森林 F 中第一棵樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)是 A 。 A．n = h+m B h+m = 2n C m = h1 D n = 2h1 74．任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序 A 。 A．13 B． 33 C．18 D．40 70．稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即 C 。 A．n*(i1)+j B． n*(i1)+j1 C．i*(j1) D．j*m+i1 66．有一個(gè) 10090 的稀疏矩陣，非 0 元素有 10，設(shè)每個(gè)整型數(shù)占 2 個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是 B 。 A．SA＋141 B． SA＋144 C．SA＋222 D．SA＋225 63．?dāng)?shù)組 A 中，每個(gè)元素的長(zhǎng)度為 3 個(gè)字節(jié)，行下標(biāo) i 從 1 到 8，列下標(biāo) j 從 1 到 10，從首地址 SA 開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素 A[5][8]的起始地址為 C 。 A．8 B．37 C．36 D．9 59．串的長(zhǎng)度是指 B 。 A．1 和 5 B．2 和 4 C．4 和 2 D．5 和 1 55．隊(duì)列的“先進(jìn)先出”特性是指 D 。 A．|top[2]top[1]|=0 B． top[1]+1=top[2] C．top[1]+top[2]=m D．top[1]=top[2] 51．設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用 D 數(shù)據(jù)結(jié)構(gòu)最佳。 D．snext=hnext 。 A．hnext=s 。 A．sttop != 1 B．sttop == 1 C．sttop != MaxSize D．sttop == MaxSize 45．一個(gè)隊(duì)列的入隊(duì)序列是 1，2，3，4，則隊(duì)列的輸出序列是 B 。下列 C 是不可能的出棧序列。 A．隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) B．順序存取的存儲(chǔ)結(jié)構(gòu) C．索引存取的存儲(chǔ)結(jié)構(gòu) D．Hash 存取的存儲(chǔ)結(jié)構(gòu) 37．棧的特點(diǎn)是 B ，隊(duì)列的特點(diǎn)是 A 。 A．O(0) B．O(1) C．O(n) D．O(n2) 34．單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了 C 。 A．字符 B．?dāng)?shù)據(jù)元素 C．?dāng)?shù)據(jù)項(xiàng) D．表元素 30．在 n 個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是 O（1）的操作是 A 。 A 插入運(yùn)算方便 B 可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示 C 存儲(chǔ)密度大 D 刪除運(yùn)算方便 28．下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？ B 。 A．插入、刪除操作更簡(jiǎn)單 B．可以進(jìn)行隨機(jī)訪問(wèn) C．可以省略表頭指針或表尾指針 D．順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活 24．如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用 B 。 A．pprior = s；snext = p；ppriornext = s；sprior = pprior B．pprior = s；ppriornext = s；snext = p；sprior = pprior C．snext = p；sprior = pprior；pprior = s；ppriornext = s D
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1