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

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

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

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

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

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

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

7、位置越靠近序列前端，查找該元素所需的比較次數(shù)越少 三、2007年上半年 若將下圖(a)所示的無(wú)向圖改為完全圖，則還需要增加 （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)行存儲(chǔ)和查找。設(shè)散列函數(shù)為H(Key)=Key mod 7并采用線性探查法（順序地探查可用存儲(chǔ)單元）解決沖突，則構(gòu)造的散列表為 （38） ，其中，mod表示整除取余運(yùn)算。 （38） 在執(zhí)行遞歸過(guò)程時(shí)，通常使用的數(shù)據(jù)結(jié)構(gòu)是 （39） 。 （39）A. 堆棧

8、(stack) B.隊(duì)列(queue) C.圖 (graph) D. 樹(shù)(tree) 用二分法來(lái)檢索數(shù)據(jù)，最確切的說(shuō)法是 （40） 。 （40）A. 僅當(dāng)數(shù)據(jù)隨機(jī)排列時(shí)，才能正確地檢索數(shù)據(jù) B. 僅當(dāng)數(shù)據(jù)有序排列時(shí)，才能正確地檢索數(shù)據(jù) C. 僅當(dāng)數(shù)據(jù)量較大時(shí)，才能有效地檢索數(shù)據(jù) D. 僅當(dāng)數(shù)據(jù)量較小時(shí)，才能有效地檢索數(shù)據(jù) 若原始數(shù)據(jù)序列（23,4,45,67,12,8,19,7）采用直接插入排序法（順序地將每個(gè)元素插入到它之前的適當(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 對(duì)下圖所示的二叉樹(shù)進(jìn)行后序遍歷（左子樹(shù)、右子樹(shù)、根結(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按列存儲(chǔ)。若第一個(gè)元素的首地址為100，且每個(gè)元素占用4個(gè)存儲(chǔ)單元，則元素A2,3的存儲(chǔ)地址為 （43） 。 （43）A. 244 B. 260 C. 364 D. 300 四、2007年下半年 n個(gè)元素依次全部進(jìn)入棧后，再陸續(xù)出棧并經(jīng)過(guò)一個(gè)隊(duì)列輸出。那么， （36

10、） 。（36）A. 元素的出隊(duì)次序與進(jìn)棧次序相同 B. 元素的出隊(duì)次序與進(jìn)棧次序相反 C. 元素的進(jìn)棧次序與進(jìn)隊(duì)次序相同 D. 元素的出棧次序與出隊(duì)次序相反 若一個(gè)棧以向量V1.n存儲(chǔ)，且空棧的棧頂指針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)先遍歷的含義是：從圖中某個(gè)頂點(diǎn)v出發(fā)，在訪問(wèn)了v之后依次訪問(wèn)v的各個(gè)未被訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)

11、它們的鄰接點(diǎn)，且“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wè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 對(duì)于長(zhǎng)度為11的順序存儲(chǔ)的有序表，若采用折半查找（向下取整），則找到第5個(gè)元素需要與表中的 （39） 個(gè)元素進(jìn)行比較操作（包括與第5個(gè)元素的比較）。（39）A. 5 B. 4C. 3 D. 2 與單向鏈表相比，雙向鏈表 （40） 。（40）A. 需要較少的存儲(chǔ)空間 B. 遍歷元素需要的時(shí)間較短 C. 較易于訪

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

13、 中（i、j、k均從1開(kāi)始取值），且S1=A11，則k與i、j的對(duì)應(yīng)關(guān)系是 （43） 。例如，元素A32存在S5中。（43）A. B. C. D. 五、2008年上半年 若二維數(shù)組 P1.5, 0.8的首地址為 base，數(shù)組元素按行存儲(chǔ)，且每個(gè)元素占用 1個(gè)存儲(chǔ)單元，則元素 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、二叉樹(shù)的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，因此對(duì)于高度為 h(h>1)的滿二叉樹(shù)，其結(jié)點(diǎn)總數(shù)為 （36） 。對(duì)非空滿二叉樹(shù)，由根結(jié)點(diǎn)開(kāi)始，按照先根后子樹(shù)、先左子樹(shù)后右子樹(shù)的次序，從 1、2、3、依次編號(hào)，則對(duì)于樹(shù)中編號(hào)為 i 的非葉子結(jié)點(diǎn)，其右子樹(shù)的編號(hào)為 （37） （高度為 3 的滿二叉樹(shù)如下圖所示）。（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.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)采用哈希（或散列）技術(shù)構(gòu)造查找表時(shí)，需要考慮沖突（碰撞）的處理，沖突是指（39）。（39）A.關(guān)鍵字相同的記錄被映射到不同的哈希地址 B.關(guān)鍵字依次被映射到編號(hào)連續(xù)的哈希地址C.關(guān)鍵字不同的記錄被映射到同一個(gè)哈希地址D.關(guān)鍵字的數(shù)目超過(guò)哈希地址的數(shù)目數(shù)據(jù)結(jié)構(gòu)中的樹(shù)最適合用來(lái)表示（40）的情況。（40）A.數(shù)據(jù)元素有序 B.數(shù)據(jù)元素之間具有多對(duì)多關(guān)系 C.數(shù)據(jù)元素?zé)o序 D.數(shù)據(jù)元素之間具有一對(duì)多關(guān)系某循環(huán)隊(duì)列的容量為M，隊(duì)頭指針指向隊(duì)頭元素，隊(duì)尾指針指向隊(duì)尾元素之后，如下圖所示（M=8），則隊(duì)列中的元素?cái)?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二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有如下性質(zhì)的二叉樹(shù)：若其左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若其右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；其左、右子樹(shù)本身就是兩棵二叉排序樹(shù)。根據(jù)該定義，對(duì)一棵非空的二叉排序樹(shù)進(jìn)行 （42）遍歷，可得到一個(gè)結(jié)點(diǎn)元素的遞增序列。（42）A.先序（根、左、右） B.中序（左、根、右）C.后序（左、右、根） D.層序（從樹(shù)根開(kāi)始，按層次） 對(duì)于 n 個(gè)元素

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

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

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

20、的所有鄰接點(diǎn)都已訪問(wèn)，則回到 v 在遍歷序列的直接前驅(qū)頂點(diǎn)，再進(jìn)行深度優(yōu)先遍歷，直至圖中所有頂點(diǎn)被訪問(wèn)過(guò)。 （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兩個(gè)遞增序列 A 和 B 的長(zhǎng)度分別為 m 和 n（m<n），將二者歸并為一個(gè)長(zhǎng)度為 m+n的遞增序列時(shí)，（42），歸并過(guò)程中元素的比較次數(shù)

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

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

23、歸過(guò)程或函數(shù)時(shí)，處理參數(shù)及返回地址需要用一種稱為 （39） 的數(shù)據(jù)結(jié)構(gòu)。（39）A.隊(duì)列 B.棧 C.多維數(shù)組 D.順序表已知對(duì)稱矩陣 An*n（Ai,j=Aj,i）的主對(duì)角線元素全部為 0，若用一維數(shù)組 B 僅存儲(chǔ)矩陣 A 的下三角區(qū)域的所有元素（不包括主對(duì)角線元素），則數(shù)組 B 的大小為 （40） 。（40）A. n(n-1) B. n2/2 C. n(n-1)/2 D. n(n+1)/2設(shè) S 是一個(gè)長(zhǎng)度為 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折半（二分）查找方法對(duì)查找表的要求是 （42）。（42）A.鏈表存儲(chǔ)結(jié)構(gòu)，元素有序排列 B.鏈表存儲(chǔ)結(jié)構(gòu)，元素?zé)o序排列 C.順序存儲(chǔ)結(jié)構(gòu)，元素有序排列 D.順序存儲(chǔ)結(jié)構(gòu)，元素?zé)o序排列若無(wú)向連通圖 G 具有 n 個(gè)頂點(diǎn)，則以下關(guān)于圖 G 的敘述中，錯(cuò)誤的是 （43） 。A. G 的邊數(shù)一定多于頂點(diǎn)數(shù) B. G 的生成樹(shù)中一定包含 n 個(gè)頂點(diǎn)C.從 G 中任意頂點(diǎn)出發(fā)一定能遍歷圖中所有頂點(diǎn)D. G 的鄰接矩陣一定是 n 階對(duì)稱矩陣 算法是問(wèn)題求解過(guò)程的精確描述，它為解決某一特定類型的問(wèn)題規(guī)定了一個(gè)運(yùn)算過(guò)程。以下關(guān)于算法的敘述中，錯(cuò)誤的是（62） 。（62）A.流程圖（flo

25、w chart）是算法的一種圖形表示方法B.用偽代碼描述的算法易于轉(zhuǎn)換成程序C.用 N/S 盒圖可以保證算法的良好結(jié)構(gòu)（即由順序、選擇和重復(fù)結(jié)構(gòu)來(lái)表示算法）D.用 E-R 圖可以同時(shí)描述算法步驟和數(shù)據(jù)模型 下表列出了數(shù)字 09 的某種二進(jìn)制編碼值及其在某類應(yīng)用中出現(xiàn)的概率，這種編碼的平均位數(shù)大約為 （63） 。八、2009年下半年設(shè)數(shù)組a0.m,1.n的每個(gè)元素占用1個(gè)存儲(chǔ)單元，若元素按行存儲(chǔ)，則數(shù)組元素ai,j（0im，1jn）相對(duì)于數(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)于算法的敘述中，錯(cuò)誤的是 （36） 。 （36）A. 對(duì)同一個(gè)算法采用不同程序語(yǔ)言實(shí)現(xiàn)，其運(yùn)行時(shí)間可能不同 B. 在不同硬件平臺(tái)上實(shí)現(xiàn)同一個(gè)算法時(shí)，其運(yùn)行時(shí)間一定是相同的C. 對(duì)非法輸入的處理能力越強(qiáng)的算法其健壯性越好 D. 算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn) 棧和隊(duì)列都是線性的數(shù)據(jù)結(jié)構(gòu)。以下關(guān)于棧和隊(duì)列的敘述中，正確的是 （37） 。 （37）A. 棧適合采用數(shù)組存儲(chǔ)，隊(duì)列適合采用循環(huán)單鏈表存儲(chǔ)B. 棧適合采用單鏈表存儲(chǔ)，隊(duì)列適合采用數(shù)組存

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

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

29、2j（2j<=n）一定為非遞減序列 C.小根堆中元素K2i與K2i+1(2i<=n,2i+1<=n)之間的大小關(guān)系不能確定 D.小根堆的最后一個(gè)元素一定是序列的最大元素若構(gòu)造哈希表時(shí)不發(fā)生沖突，則給定的關(guān)鍵字與其哈希地址之間的對(duì)應(yīng)關(guān)系是 （43）。（其中n>1且m>1）（43）A.1:1 B.1:n C.n:1 D.n:m九、2010年上半年若在單向鏈表上，除訪問(wèn)鏈表中所有結(jié)點(diǎn)外，還需在表尾頻繁插入結(jié)點(diǎn)，那么采用（31）最節(jié)省時(shí)間。（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+已知某二叉樹(shù)的先序遍歷序列是 ABDCE，中序遍歷序列是 BDAEC，則該二叉樹(shù)為（33）。對(duì)于二維數(shù)組 a1.6,1.8，設(shè)每個(gè)元素占 2 個(gè)存儲(chǔ)單元，且以列為主序存儲(chǔ)，則元素 a4,4相對(duì)于數(shù)組空間起始地址的偏移量是（34）個(gè)存儲(chǔ)單元。（34）A. 28 B. 42 C. 48 D. 54已知某帶權(quán)圖 G 的鄰接表如下所示，其中表結(jié)點(diǎn)的結(jié)構(gòu)為：則圖 G 是（35）。（35）A.無(wú)向圖 B.完全圖 C.有向圖 D.強(qiáng)連通圖已知棧 S 初始為空，對(duì)于一個(gè)符號(hào)序列a1a2a

31、3a4a5（入棧次序也是該次序），當(dāng)用I表示入棧、O表示出棧，則通過(guò)棧S得到符號(hào)序列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 對(duì)于n個(gè)元素的關(guān)鍵字序列k1, k2,.,kn，當(dāng)且僅當(dāng)滿足關(guān)系時(shí)稱為小

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