數(shù)據(jù)結(jié)構(gòu)歷年試題及答案匯編

1、數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)歷年試題匯編一、2006年上半年 在以下情形中，_(35)_適合于采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)。(35)A監(jiān)視一個火車票售票窗口等待服務(wù)的客戶D描述一個組織中的管理機(jī)構(gòu)C統(tǒng)計(jì)一個商場中的顧客數(shù)D監(jiān)視進(jìn)入某住宅樓的訪客 元素3、1、2依次全部進(jìn)入一個棧后，陸續(xù)執(zhí)行出棧操作，得到的出棧序列為_(36)_。(36)A3、2、1 B3、1、2C1、2、3 D2、1、3 一棵二叉樹如下圖所示，若采用順序存儲結(jié)構(gòu)，即用一維數(shù)組元素存儲該二叉樹中的結(jié)點(diǎn)(根結(jié)點(diǎn)的下標(biāo)為1，若某結(jié)點(diǎn)的下標(biāo)為i，則其左孩子位于下標(biāo)2i處、右孩子位于下標(biāo)2i+1處)，則該數(shù)組的大小至少為_(37)_；若采用二叉鏈表存儲該二叉樹(各

2、 個結(jié)點(diǎn)包括結(jié)點(diǎn)的數(shù)據(jù)、左孩子指針、右孩子指針)，則該鏈表中空指針的數(shù)目為_(38)_。(37)A6B10C12D15(38)A6B7 C12D14 以下各圖用樹結(jié)構(gòu)描述了7個元素之間的邏輯關(guān)系，其中_(39)_適合采用二分法查找元素。 對于二維數(shù)組a04,15，設(shè)每個元素占1個存儲單元，且以行為主序存儲，則元素a2,1相對于數(shù)組空間起始地址的偏移量是_(40)_。(40)A5 B10C15D25 若n表示問題的規(guī)模、O(f(n)表示算法的時間復(fù)雜度隨n變化的增長趨勢，則算法時間復(fù)雜度最小的是_(59)_。(59)AO(n2)BO(n)C O(log n)DO(nlog n) 二、2006年下

3、半年  在鏈表結(jié)構(gòu)中，采用 （35） 可以用最少的空間代價和最高的時間效率實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)。 （35）A.  僅設(shè)置尾指針的單向循環(huán)鏈表      B.  僅設(shè)置頭指針的單向循環(huán)鏈表 C.  僅設(shè)置尾指針的雙向鏈表          D.  僅設(shè)置頭指針的雙向鏈表   若需將一個棧 S 中的元素逆置，則以下處理方式中正確的是 （36） 。 （36）A.  將棧 S 中元素依次出棧并

4、入棧 T，然后棧 T 中元素依次出棧并進(jìn)入棧 S B.  將棧 S 中元素依次出棧并入隊(duì)，然后使該隊(duì)列元素依次出隊(duì)并進(jìn)入棧 S C.  直接交換棧頂元素和棧底元素 D.  直接交換棧頂指針和棧底指針   已知 N 個數(shù)已存入數(shù)組 A1.M的前 N 個元素中（N<M），為在 Ai（1iN）之前插入一個新數(shù)，應(yīng)先 （37） ，以挪出一個空閑位置插入該數(shù)。 （37）A.  從 Ai開始直到 A1，每個數(shù)向后移動一個位置 B.  從 A1開始直到 Ai，每個數(shù)向后移動一個位置 C.  從 Ai開始直到 AN，每個數(shù)向前移動一個

5、位置 D.  從 AN開始直到 Ai，每個數(shù)向后移動一個位置   若某二叉樹的先序遍歷序列和中序遍歷序列分別為 PBECD、BEPCD，則該二叉 樹的后序遍歷序列為 （38） 。 （38）A. PBCDE            B. DECBP       C. EBDCP        D. EBPDC   無向圖的鄰接矩陣一

6、定是 （39） 。 （39）A.  對角矩陣       B.  稀疏矩陣    C.  三角矩陣    D.  對稱矩陣   對具有 n 個元素的有序序列進(jìn)行二分查找時， （40） 。 （40）A.  查找元素所需的比較次數(shù)與元素的位置無關(guān) B.  查找序列中任何一個元素所需要的比較次數(shù)不超過log2(n+1) C.  元素位置越靠近序列后端，查找該元素所需的比較次數(shù)越少 D.  元素

7、位置越靠近序列前端，查找該元素所需的比較次數(shù)越少 三、2007年上半年 若將下圖(a)所示的無向圖改為完全圖，則還需要增加 （36） 條邊；下圖(b)的鄰接矩陣表示為 （37） （行列均以A、B、C、D、E為序）。（36）A. 1 B. 2 C. 5 D. 15 （37） 若線性表（23, 14, 45, 12, 8, 19, 7）采用散列法進(jìn)行存儲和查找。設(shè)散列函數(shù)為H(Key)=Key mod 7并采用線性探查法（順序地探查可用存儲單元）解決沖突，則構(gòu)造的散列表為 （38） ，其中，mod表示整除取余運(yùn)算。 （38） 在執(zhí)行遞歸過程時，通常使用的數(shù)據(jù)結(jié)構(gòu)是 （39） 。 （39）A. 堆棧

8、(stack) B.隊(duì)列(queue) C.圖 (graph) D. 樹(tree) 用二分法來檢索數(shù)據(jù)，最確切的說法是 （40） 。 （40）A. 僅當(dāng)數(shù)據(jù)隨機(jī)排列時，才能正確地檢索數(shù)據(jù) B. 僅當(dāng)數(shù)據(jù)有序排列時，才能正確地檢索數(shù)據(jù) C. 僅當(dāng)數(shù)據(jù)量較大時，才能有效地檢索數(shù)據(jù) D. 僅當(dāng)數(shù)據(jù)量較小時，才能有效地檢索數(shù)據(jù) 若原始數(shù)據(jù)序列（23,4,45,67,12,8,19,7）采用直接插入排序法（順序地將每個元素插入到它之前的適當(dāng)位置）排序，則進(jìn)行完第4趟后的排序結(jié)果是 （41） 。 （41）A. 4, 8,45, 23,67,12, 19,7 B. 4,7,8,12,23, 45,67,1

9、9 C. 4,12,8,19,7,23, 45,67 D. 4,12,23,45,67,8,19,7 對下圖所示的二叉樹進(jìn)行后序遍歷（左子樹、右子樹、根結(jié)點(diǎn)）的結(jié)果是 （42） 。 （42）A. 5 2 3 4 6 1 B. 5 2 3 4 1 6 C. 2 6 4 1 3 5 D. 2 5 6 4 3 1 數(shù)組A-5.5, 0.8按列存儲。若第一個元素的首地址為100，且每個元素占用4個存儲單元，則元素A2,3的存儲地址為 （43） 。 （43）A. 244 B. 260 C. 364 D. 300 四、2007年下半年 n個元素依次全部進(jìn)入棧后，再陸續(xù)出棧并經(jīng)過一個隊(duì)列輸出。那么， （36

10、） 。（36）A. 元素的出隊(duì)次序與進(jìn)棧次序相同 B. 元素的出隊(duì)次序與進(jìn)棧次序相反 C. 元素的進(jìn)棧次序與進(jìn)隊(duì)次序相同 D. 元素的出棧次序與出隊(duì)次序相反 若一個棧以向量V1.n存儲，且空棧的棧頂指針top為n+1，則將元素x入棧的正確操作是 （37） 。（37）A. top = top+1; Vtop = x; B. Vtop = x; top = top+1; C. top = top-1; Vtop = x; D. Vtop = x; top = top-1; 廣度優(yōu)先遍歷的含義是：從圖中某個頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個未被訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問

11、它們的鄰接點(diǎn)，且“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。 （38） 是下圖的廣度優(yōu)先遍歷序列。（38）A. 1 2 6 3 4 5B. 1 2 3 4 5 6 C. 1 6 5 2 3 4 D. 1 6 4 5 2 3 對于長度為11的順序存儲的有序表，若采用折半查找（向下取整），則找到第5個元素需要與表中的 （39） 個元素進(jìn)行比較操作（包括與第5個元素的比較）。（39）A. 5 B. 4C. 3 D. 2 與單向鏈表相比，雙向鏈表 （40） 。（40）A. 需要較少的存儲空間 B. 遍歷元素需要的時間較短 C. 較易于訪

12、問相鄰結(jié)點(diǎn) D. 較易于插入和刪除元素 如果待排序序列中兩個元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。 （41） 是穩(wěn)定的排序方法，因?yàn)檫@種方法在比較相鄰元素時，值相同的元素并不進(jìn)行交換。（41）A. 冒泡排序 B. 希爾排序 C. 快速排序 D. 簡單選擇排序 對下圖所示的二叉樹進(jìn)行中序遍歷（左子樹、根、右子樹）的結(jié)果是 （42） 。（42）A. 2 5 3 4 6 1 B. 2 5 3 4 1 6 C. 2 6 5 4 1 3 D. 2 6 4 5 3 1 采用一維數(shù)組S存儲一個n階對稱矩陣A的下三角部分（按行存放，包括主對角線），設(shè)元素Aij存放在Sk

13、 中（i、j、k均從1開始取值），且S1=A11，則k與i、j的對應(yīng)關(guān)系是 （43） 。例如，元素A32存在S5中。（43）A. B. C. D. 五、2008年上半年 若二維數(shù)組 P1.5, 0.8的首地址為 base，數(shù)組元素按行存儲，且每個元素占用 1個存儲單元，則元素 P3, 3在該數(shù)組空間的地址為（32）。（32）A. base+13 B. base+16 C. base+18 D. base+21設(shè)初始棧為空，s 表示入棧操作，x 表示出棧操作，則（33） 是合法的操作序列。（33）A. sxxsssxxx B. xxssxxss C. sxsxssxx D. xssssxxx 滿

14、二叉樹的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，因此對于高度為 h(h>1)的滿二叉樹，其結(jié)點(diǎn)總數(shù)為 （36） 。對非空滿二叉樹，由根結(jié)點(diǎn)開始，按照先根后子樹、先左子樹后右子樹的次序，從 1、2、3、依次編號，則對于樹中編號為 i 的非葉子結(jié)點(diǎn)，其右子樹的編號為 （37） （高度為 3 的滿二叉樹如下圖所示）。（36）A. 2 B. 2h-1 C. 2h 1 D. 2h-1+1（37）A. 2i B. 2i-1 C. 2i+1 D. 2i+2 在數(shù)據(jù)結(jié)構(gòu)中，結(jié)點(diǎn)（數(shù)據(jù)元素）及結(jié)點(diǎn)間的相互關(guān)系組成數(shù)據(jù)的邏輯結(jié)構(gòu)。按邏輯結(jié)構(gòu)的不同，數(shù)據(jù)結(jié)構(gòu)通?？煞譃椋?8） 兩類。（38）A.線性結(jié)構(gòu)和非線性結(jié)構(gòu)

15、 B.緊湊結(jié)構(gòu)和稀疏結(jié)構(gòu) C.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)采用哈希（或散列）技術(shù)構(gòu)造查找表時，需要考慮沖突（碰撞）的處理，沖突是指（39）。（39）A.關(guān)鍵字相同的記錄被映射到不同的哈希地址 B.關(guān)鍵字依次被映射到編號連續(xù)的哈希地址C.關(guān)鍵字不同的記錄被映射到同一個哈希地址D.關(guān)鍵字的數(shù)目超過哈希地址的數(shù)目數(shù)據(jù)結(jié)構(gòu)中的樹最適合用來表示（40）的情況。（40）A.數(shù)據(jù)元素有序 B.數(shù)據(jù)元素之間具有多對多關(guān)系 C.數(shù)據(jù)元素?zé)o序 D.數(shù)據(jù)元素之間具有一對多關(guān)系某循環(huán)隊(duì)列的容量為M，隊(duì)頭指針指向隊(duì)頭元素，隊(duì)尾指針指向隊(duì)尾元素之后，如下圖所示（M=8），則隊(duì)列中的元素數(shù)目為（41）（MOD

16、 表示整除取余運(yùn)算）。（41）A. rear front B. front rear C. (rear front + M) MOD M D. (front rear + M) MOD M二叉排序樹或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：若其左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若其右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；其左、右子樹本身就是兩棵二叉排序樹。根據(jù)該定義，對一棵非空的二叉排序樹進(jìn)行 （42）遍歷，可得到一個結(jié)點(diǎn)元素的遞增序列。（42）A.先序（根、左、右） B.中序（左、根、右）C.后序（左、右、根） D.層序（從樹根開始，按層次） 對于 n 個元素

17、的關(guān)鍵字序列k1,k2,kn，若將其按次序?qū)?yīng)到一棵具有 n 個結(jié)點(diǎn)的完全二叉樹上，使得任意結(jié)點(diǎn)都不大于其孩子結(jié)點(diǎn)(若存在孩子結(jié)點(diǎn))，則稱其為小頂堆。根據(jù)以上定義，（43）是小頂堆。六、2008年下半年設(shè)數(shù)組 a1.6,0.9的元素以行為主序存放，每個元素占用一個存儲單元，則數(shù)組元素 a3,3的地址為 （34） 。（34）A. a+23 B. a+27 C. a+39 D. a+35若字符串 s 的長度為 n（n >1）且其中的字符互不相同，則 s 的長度為 2 的子串有（35）個。（35）A. n B. n-1 C. n-2 D. 2若線性表（24, 13, 31, 6, 15, 18

18、, 8）采用散列（Hash）法進(jìn)行存儲和查找，設(shè)散列函數(shù)為 H(Key)=Key mod 11，則構(gòu)造散列表時發(fā)生沖突的元素為（36）。（其中的 mod表示整除取余運(yùn)算）（36）A. 24 和 13 B. 6和 15 C. 6和24 D. 18 和 8線性表采用順序存儲結(jié)構(gòu)，若表長為m，且在任何一個合法插入位置上進(jìn)行插入操作的概率相同，則插入一個元素平均移動（37）個元素。若二叉樹的先序遍歷序列與中序遍歷序列相同且樹中結(jié)點(diǎn)數(shù)大于 1，則該二叉樹的（38）。（38）A.只有根結(jié)點(diǎn)無左子樹 B.只有根結(jié)點(diǎn)無右子樹C.非葉子結(jié)點(diǎn)只有左子樹 D.非葉子結(jié)點(diǎn)只有右子樹由關(guān)鍵字序列（12，7，36，25，

19、18，2）構(gòu)造一棵二叉排序樹（初始為空，第一個關(guān)鍵字作為根結(jié)點(diǎn)插入，此后對于任意關(guān)鍵字，若小于根結(jié)點(diǎn)的關(guān)鍵字，則插入左子樹中，若大于根結(jié)點(diǎn)的關(guān)鍵字，則插入右子樹中，且左、右子樹均為二叉排序樹），該二叉排序樹的高度（層數(shù)）為（39）。（39）A. 6 B. 5 C. 4 D. 3對連通圖進(jìn)行遍歷前設(shè)置所有頂點(diǎn)的訪問標(biāo)志為 false（未被訪問），遍歷圖后得到一個遍歷序列，初始狀態(tài)為空。深度優(yōu)先遍歷的含義是：從圖中某個未被訪問的頂點(diǎn) v 出發(fā)開始遍歷，先訪問 v 并設(shè)置其訪問標(biāo)志為 true（已訪問），同時將 v 加入遍歷序列，再從 v 的未被訪問的鄰接頂點(diǎn)中選一個頂點(diǎn)，進(jìn)行深度優(yōu)先遍歷；若 v

20、的所有鄰接點(diǎn)都已訪問，則回到 v 在遍歷序列的直接前驅(qū)頂點(diǎn)，再進(jìn)行深度優(yōu)先遍歷，直至圖中所有頂點(diǎn)被訪問過。 （40）是下圖的深度優(yōu)先遍歷序列。（40）A. 1 2 3 4 6 5 B. 1 2 6 3 4 5 C. 1 6 2 5 4 3 D. 1 2 3 4 5 6 棧的運(yùn)算特點(diǎn)是后進(jìn)先出。元素 a、b、c、d 依次入棧，則不能得到的出棧序列是 （41）。（41）A. a b c d B. c a b d C. d c b a D. b c d a兩個遞增序列 A 和 B 的長度分別為 m 和 n（m<n），將二者歸并為一個長度為 m+n的遞增序列時，（42），歸并過程中元素的比較次數(shù)

21、最少。（42）A.當(dāng) A 的最大元素大于 B 的最大元素時B.當(dāng) A 的最大元素小于 B 的最小元素時C.當(dāng) A 的最小元素大于 B 的最小元素時D.當(dāng) A 的最小元素小于 B 的最大元素時 在任意一棵非空的二叉樹中，終端結(jié)點(diǎn)（葉子）的數(shù)目總是比具有兩個孩子的非終端結(jié)點(diǎn)的數(shù)目（43） 。（43）A. 多 0 個 B. 多 1 個 C. 多 2 個 D. 多 3 個七、2009年上半年以下關(guān)于排序算法的敘述中，正確的是 （36）。 （36）A.冒泡排序法中，元素的交換次數(shù)與元素的比較次數(shù)一定相同 B.冒泡排序法中，元素的交換次數(shù)不少于元素的比較次數(shù)C.簡單選擇排序中，關(guān)鍵字相同的兩個記錄在排序前

22、后的相對位置一定不變 D.簡單選擇排序中，關(guān)鍵字相同的兩個記錄在排序前后的相對位置可能交換設(shè)有一個初始為空的棧，若輸入序列為1、2、3、n（n>3），且輸出序列的第一個元素是 n-1，則輸入序列中所有元素都出棧后， （37）。 （37）A.元素 n-2 一定比 n-3 先出棧B.元素 1n-2 在輸出序列中的排列是不確定的C.輸出序列末尾的元素一定為 1D. 輸出序列末尾的元素一定為 n某二叉樹的先序遍歷序列為 ABFCDE、中序遍歷序列為 BFADCE，則該二叉樹根的左孩子和右孩子結(jié)點(diǎn)分別是 （38）。（38）A. B 和 F B. F 和 B C. B 和 C D. C 和 B調(diào)用遞

23、歸過程或函數(shù)時，處理參數(shù)及返回地址需要用一種稱為 （39） 的數(shù)據(jù)結(jié)構(gòu)。（39）A.隊(duì)列 B.棧 C.多維數(shù)組 D.順序表已知對稱矩陣 An*n（Ai,j=Aj,i）的主對角線元素全部為 0，若用一維數(shù)組 B 僅存儲矩陣 A 的下三角區(qū)域的所有元素（不包括主對角線元素），則數(shù)組 B 的大小為 （40） 。（40）A. n(n-1) B. n2/2 C. n(n-1)/2 D. n(n+1)/2設(shè) S 是一個長度為 5 的字符串，其中的字符各不相同，則計(jì)算 S 中互異的非平凡子串（非空且不同于 S 本身）數(shù)目的算式為（41）。（41）A. 5+4+3+2+1 B. 5+4+3+2 C. 4+3+

24、2+1 D. 4+3+2折半（二分）查找方法對查找表的要求是 （42）。（42）A.鏈表存儲結(jié)構(gòu)，元素有序排列 B.鏈表存儲結(jié)構(gòu)，元素?zé)o序排列 C.順序存儲結(jié)構(gòu)，元素有序排列 D.順序存儲結(jié)構(gòu)，元素?zé)o序排列若無向連通圖 G 具有 n 個頂點(diǎn)，則以下關(guān)于圖 G 的敘述中，錯誤的是 （43） 。A. G 的邊數(shù)一定多于頂點(diǎn)數(shù) B. G 的生成樹中一定包含 n 個頂點(diǎn)C.從 G 中任意頂點(diǎn)出發(fā)一定能遍歷圖中所有頂點(diǎn)D. G 的鄰接矩陣一定是 n 階對稱矩陣 算法是問題求解過程的精確描述，它為解決某一特定類型的問題規(guī)定了一個運(yùn)算過程。以下關(guān)于算法的敘述中，錯誤的是（62） 。（62）A.流程圖（flo

25、w chart）是算法的一種圖形表示方法B.用偽代碼描述的算法易于轉(zhuǎn)換成程序C.用 N/S 盒圖可以保證算法的良好結(jié)構(gòu)（即由順序、選擇和重復(fù)結(jié)構(gòu)來表示算法）D.用 E-R 圖可以同時描述算法步驟和數(shù)據(jù)模型 下表列出了數(shù)字 09 的某種二進(jìn)制編碼值及其在某類應(yīng)用中出現(xiàn)的概率，這種編碼的平均位數(shù)大約為 （63） 。八、2009年下半年設(shè)數(shù)組a0.m,1.n的每個元素占用1個存儲單元，若元素按行存儲，則數(shù)組元素ai,j（0im，1jn）相對于數(shù)組空間首地址的偏移量為（32） 。（32）A. (i+1)*n+j B. i*n+j-1 C. i*m+j D. i*(m+1)+j-1 算術(shù)表達(dá)式a+b*(

26、c+d/e)可轉(zhuǎn)換為后綴表達(dá)式 （35） 。 （35）A. abcde*/+ B. abcde/+*+ C. abcde*+/+ D. abcde/*+ 以下關(guān)于算法的敘述中，錯誤的是 （36） 。 （36）A. 對同一個算法采用不同程序語言實(shí)現(xiàn)，其運(yùn)行時間可能不同 B. 在不同硬件平臺上實(shí)現(xiàn)同一個算法時，其運(yùn)行時間一定是相同的C. 對非法輸入的處理能力越強(qiáng)的算法其健壯性越好 D. 算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn) 棧和隊(duì)列都是線性的數(shù)據(jù)結(jié)構(gòu)。以下關(guān)于棧和隊(duì)列的敘述中，正確的是 （37） 。 （37）A. 棧適合采用數(shù)組存儲，隊(duì)列適合采用循環(huán)單鏈表存儲B. 棧適合采用單鏈表存儲，隊(duì)列適合采用數(shù)組存

27、儲C. 棧和隊(duì)列都不允許在元素序列的中間插入和刪除元素D. 若進(jìn)入棧的元素序列確定，則從棧中出來的序列也同時確定 （38） 并不是算法必須具備的特性。 （38）A. 可行性 B. 可移植性 C. 確定性 D. 有窮性 若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）個數(shù)是（39） 。（39）A. 不確定 B. 9 C. 11 D. 15 對具有n個元素的順序表（采用順序存儲的線性表）進(jìn)行（40） 操作，其耗時與n的大小無關(guān)。A. 在第i（1<=i<=n）個元素之后插入一個新元素 B. 刪除第i（1<=i<=n）個元素 C. 對順序表中的

28、元素進(jìn)行排序 D. 訪問第i（1<=i<=n）個元素的前驅(qū)和后繼 以下關(guān)于圖及其存儲結(jié)構(gòu)的敘述中，正確的是 （41） 。 A. 無向圖的鄰接矩陣一定是對稱的 B. 有向圖的鄰接矩陣一定是不對稱的C. 無向圖采用鄰接表存儲更節(jié)省存儲空間D. 有向圖采用鄰接表存儲更節(jié)省存儲空間 對于n個元素的關(guān)鍵字序列K1,K2,Kn，若有Ki<=K2i且Ki<=K2i+1（i=1,2, ,2i+1<=n），則稱其為小根堆。以下關(guān)于小根堆及其元素關(guān)系的敘述中，錯誤的是（42） 。（42）A. 關(guān)鍵字序列K1,K2,Kn呈非遞減排序時一定為小根堆 B.小根堆中的序列K1,K2,K4,K

29、2j（2j<=n）一定為非遞減序列 C.小根堆中元素K2i與K2i+1(2i<=n,2i+1<=n)之間的大小關(guān)系不能確定 D.小根堆的最后一個元素一定是序列的最大元素若構(gòu)造哈希表時不發(fā)生沖突，則給定的關(guān)鍵字與其哈希地址之間的對應(yīng)關(guān)系是 （43）。（其中n>1且m>1）（43）A.1:1 B.1:n C.n:1 D.n:m九、2010年上半年若在單向鏈表上，除訪問鏈表中所有結(jié)點(diǎn)外，還需在表尾頻繁插入結(jié)點(diǎn)，那么采用（31）最節(jié)省時間。（31）A.僅設(shè)尾指針的單向鏈表 B.僅設(shè)頭指針的單向鏈表C.僅設(shè)尾指針的單向循環(huán)鏈表 D.僅設(shè)頭指針的單向循環(huán)鏈表表達(dá)式“a*(b

30、c)+d”的后綴式為（32）。（32）A. abcd*-+ B. ab*c-d+ C. ab-cd+* D. abc-*d+已知某二叉樹的先序遍歷序列是 ABDCE，中序遍歷序列是 BDAEC，則該二叉樹為（33）。對于二維數(shù)組 a1.6,1.8，設(shè)每個元素占 2 個存儲單元，且以列為主序存儲，則元素 a4,4相對于數(shù)組空間起始地址的偏移量是（34）個存儲單元。（34）A. 28 B. 42 C. 48 D. 54已知某帶權(quán)圖 G 的鄰接表如下所示，其中表結(jié)點(diǎn)的結(jié)構(gòu)為：則圖 G 是（35）。（35）A.無向圖 B.完全圖 C.有向圖 D.強(qiáng)連通圖已知棧 S 初始為空，對于一個符號序列a1a2a

31、3a4a5（入棧次序也是該次序），當(dāng)用I表示入棧、O表示出棧，則通過棧S得到符號序列a2a4a5a3a1的操作序列為（36）。（36）A. I O I I O O I O O I B. I I O I O I O I O O C. I O O I I O I O I O D. I I O I I O I O O O隊(duì)列是一種按“先進(jìn)先出”原則進(jìn)行插入和刪除操作的數(shù)據(jù)結(jié)構(gòu)。若初始隊(duì)列為空，輸入序列為 a b c d e，則可得到的輸出序列為（37）。（37）A. abcde B.abdce C.edcba D. edabc 對于n個元素的關(guān)鍵字序列k1, k2,.,kn，當(dāng)且僅當(dāng)滿足關(guān)系時稱為小

32、根堆（小頂堆）。以下序列中， （38） 不是小根堆。（38）A. 12, 20, 36, 48, 25, 50, 40 B. 12, 36, 20, 48, 40, 25, 50C. 12, 20, 25, 36, 40, 48, 50 D. 12, 36, 20, 48, 25, 50, 40十、2010年下半年l 以下關(guān)于哈希表的敘述中，錯誤的是（36） 。（36）A.哈希表中元素的存儲位置根據(jù)該元素的關(guān)鍵字值計(jì)算得到 B.哈希表中的元素越多，插入一個新元素發(fā)生沖突的可能性越小 C.哈希表中的元素越多，插入一個新元素發(fā)生沖突的可能性越大 D.哈希表中插入新元素發(fā)生沖突時，需要與表中某些元素進(jìn)行比較l 下三角矩陣A08，08如下圖所示，若將其下三角元素（即行下標(biāo)不小于列下標(biāo)的所有元素）按列壓縮存儲在數(shù)組M0m中，即A0,0存儲在M0、A1,0存儲在M1、A2,0存儲在M2，A8,8存儲在M44，則元素A5,5存儲在（37） 。若將其下三角元素按列壓縮存儲在數(shù)組M0m中，即A0,0存儲在M0、A1,0存儲在M1、A1,2存儲在M2，A8,8存儲在M44，則元素A5,5存儲在（38） 。 （37）A.M15 B.M20 C.M35 D.M39（38）A.M1