2012數(shù)據(jù)結(jié)構(gòu)題

1、_(4)_的特點(diǎn)是數(shù)據(jù)結(jié)構(gòu)中元素的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系。(4)A樹形存儲結(jié)構(gòu)B鏈?zhǔn)酱鎯Y(jié)構(gòu)C索引存儲結(jié)構(gòu)D散列存儲結(jié)構(gòu)若循環(huán)隊(duì)列以數(shù)組 QO.m-1 作為其存儲結(jié)構(gòu)變量 rear 表示循環(huán)隊(duì)列中隊(duì)尾元素的實(shí)際位置，其移動按 rear=(rear+1) mod m 進(jìn)行，變量 length 表示當(dāng)前循環(huán)隊(duì)列中的元素個數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是_(5)_。(5)Arear-lengthB(rear-length+m) mod m C(1+rear+m-length) mod mDm-length一個含有n個頂點(diǎn)和e條邊的簡單無向圖，在其鄰接矩陣存儲結(jié)構(gòu)中共有_(6)_個

2、零元素。(6)AeB2eCn2-eDn2-2e若一棵哈夫曼(Huffman)樹共有9個頂點(diǎn)，則其葉子結(jié)點(diǎn)的個數(shù)為_(7)_。(7)A4B5 C6 D7若采用鄰接矩陣來存儲簡單有向圖，則其某一個頂點(diǎn)i的入度等于該矩陣_(8)_。(8)A第i行中值為1的元素個數(shù) B所有值為1的元素總數(shù) C第i行及第i列中值為1的元素總個數(shù)D第i列中值為1的元素個數(shù)在棵度為3的樹中，若有2個度為3的結(jié)點(diǎn)，有1個度為2的結(jié)點(diǎn)，則有_(9)_個度為0的結(jié)點(diǎn)。(9)A4B5C6D7設(shè)結(jié)點(diǎn)x和y是二叉樹中任意的兩個結(jié)點(diǎn)，在該二叉樹的先根遍歷序列中x在y之前，而在其后根遍歷序列中x在y之后，則x和y的關(guān)系是_(10)_。(1

3、0)Ax是y的左兄弟Bx是y的右兄弟Cx是y的祖先Dx是y的后裔設(shè)順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索引表采用順序查找方法來確定子塊，且在確定的子塊中也采用順序查找方法，則在等概率的情況下，分塊查找成功的平均查找長度為_(11)_。 (11)A21B23C41D62DCDBDCCB(順序查找平均查找長度是：（n+1）/2 (1+3)/2+(41+1)/2=23 123/3=41)在一棵完全二叉樹中，其根的序號為1，_(33)_可判定序號為p和q的兩個結(jié)點(diǎn)是否在同一層。(33)ALlog2P=Llog2qBlog2P = log2qCLlog2P+1=

4、Llog2qDLlog2P=Llog2q+1堆是一種數(shù)據(jù)結(jié)構(gòu)，_(34)_是堆。(34)A(10,50,80,30,60,20,15,18)B(10,18,15,20,50,80,30,60)C(10,15,18,50,80,30,60,20)D(10,30,60,20,15,18,50,80)_(35)_從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上，所經(jīng)過的結(jié)點(diǎn)序列必按其關(guān)鍵字降序排列。(35)A二叉排序樹 B大頂堆 C小頂堆 D平衡二叉樹若廣義表L=(1,2,3)，則L的長度和深度分別為_(36)_。(36)A1和1 B1和2 C1和3 D2和2若對27個元素只進(jìn)行三趟多路歸并排序，則選取的歸并路數(shù)

5、為_(37)_。(37)A2B3C4D5拉斯維加斯(Las Vegas)算法是一種常用的_(55)_算法。(55)A確定性B近似C概率D加密在分支-限界算法設(shè)計(jì)策略中，通常采用_(56)_搜索問題的解空間。(56)A深度優(yōu)先B廣度優(yōu)先C自底向上D拓?fù)湫蛄性谙铝兴惴ㄔO(shè)計(jì)方法中，_(57)_在求解問題的過程中并不從整體最優(yōu)上加以考慮，而是做出在當(dāng)前看來是最好的選擇。利用該設(shè)計(jì)方法可以解決 _(58)_問題。(57)A分治法B貪心法C動態(tài)規(guī)劃方法D回溯法(58)A排序B檢索C背包D0/1背包以關(guān)鍵字比較為基礎(chǔ)的排序算法在最壞情況下的計(jì)算時間下界為O(nlogn)。下面的排序算法中，最壞情況下計(jì)算時間

6、可以達(dá)到O(nlogn)的是_(59)_；該算法采用的設(shè)計(jì)方法是_(60)_。(59)A歸并排序 B插入排序 C選擇排序 D冒泡排序(60)A分治法 B貪心法 C動態(tài)規(guī)劃方法 D回溯法ABCBB CBBCAA循環(huán)鏈表的主要優(yōu)點(diǎn)是_(38)_ A.不再需要頭指針了B.已知某個結(jié)點(diǎn)的位置后，能很容易找到它的直接前驅(qū)結(jié)點(diǎn)C.在進(jìn)行刪除操作后，能保證鏈表不斷開D.從表中任一結(jié)點(diǎn)出發(fā)都能遍歷整個鏈表達(dá)式a*(b+c)-d的后綴表達(dá)形式為_(39)_。A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd若二叉樹的先序遍歷序列為ABDECF，中序遍歷序列DBEAFC，則其后序遍歷序

7、列為_(40)_。A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA無向圖中一個頂點(diǎn)的度是指圖中_(41)_。（41）A.通過該頂點(diǎn)的簡單路徑數(shù) B.通過該頂點(diǎn)的回路數(shù)C.與該頂點(diǎn)相鄰的頂點(diǎn)數(shù) D.與該頂點(diǎn)連通的頂點(diǎn)數(shù)DBDC在11個元素的有序表A1.11中進(jìn)行折半查找（ ）查找元素A11時，被比較的元素的下標(biāo)依次是_(44)_。供選擇的答案：(44)A.6,8,10,11 B.6,9,10,11 C.6,7,9,11D.6,8,9,11關(guān)于維護(hù)軟件所需的成本，以下敘述正確的是_(45)_。供選擇的答案：(45)A.糾正外部和內(nèi)部設(shè)計(jì)錯誤比糾正源代碼錯誤需要更大的成本B.與

8、需求定義相比，源代碼的文字量大得多，所以源代碼的維護(hù)成本更高C.用戶文檔需要經(jīng)常更新，其維護(hù)成本超過了糾正設(shè)計(jì)錯誤的成本D.需要定義的錯誤會在設(shè)計(jì)時被發(fā)現(xiàn)并糾正，因此需求定義糾錯的成本小于源代碼糾錯的成本由元素序列（27,16,75,38,51）構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根（即離插入結(jié)點(diǎn)最近且平衡因子的絕對值為2的結(jié)點(diǎn)）為_(46)_。供選擇的答案：(46)A.27 B.38 C.51 D.75若排序前后關(guān)鍵字相同的兩個元素相對位置不變，則稱該排序方法是穩(wěn)定的。_(47)_排序是穩(wěn)定的。供選擇的答案：(47)A.歸并 B.快速 C.希爾 D.堆BADA設(shè)求解某問題的遞歸算法如

9、下：F(int n) if(n=1) Move();elseF(n-1);Move(n);F(n-1);求解該算法的計(jì)算時間時,僅考慮算法Move所做的計(jì)算為主要計(jì)算,且Move為常數(shù)級算法。則算法F的計(jì)算時間T(n)的遞推關(guān)系式為_(53)_；設(shè)算法Move的計(jì)算時間為k，當(dāng)n=4時，算法F的計(jì)算時間為_(54)_。供選擇的答案：（53）A.T(n)=T(n-1)+1 B.T(n)=2T(n-1)C.T(n)=2T(n-1)+1D.T(n)=2T(n+1)+1（54) A.14k B.15k C.16k D.17k利用貪心法求解0/1背包問題時，_(55)_能夠確保獲得最優(yōu)解。用動態(tài)規(guī)劃方法

10、求解0/1背包問題時，將“用前i個物品來裝容量是X的背包”的0/1背包問題記為KNAP(1,i,X),設(shè)fi(X)是KNAP(1,i,X)最優(yōu)解的效益值，第j個物品的重量和放入背包后取得效益值分別為Wj和pj(j=1n)。則依次求解f0(X)、f1(X)、.、fn(X)的過程中使用的遞推關(guān)系式為_(56)_。供選擇的答案：(55)A.優(yōu)先選取重量最小的物品 B.優(yōu)先選取效益最大的物品C.優(yōu)先選取單位重量效益最大的物品 D.沒有任何準(zhǔn)則(56)A.fi(X)=minfi-1(X),fi-1(X)+piB.fi(X)=maxfi-1(X),fi-1(X-Wi)+piC.fi(X)=minfi-1(

11、X-Wi),fi-1(X-Wi)+piD.fi(X)=maxfi-1(X-Wi),fi-1(X)+piCBDB 拓?fù)湫蛄惺菬o環(huán)有向圖中所有項(xiàng)點(diǎn)的一個線性序列，圖中任意路徑中的各個頂點(diǎn)在該圖的拓?fù)湫蛄兄斜３窒群箨P(guān)系，（52）為下圖所示有向圖的一個拓?fù)湫蛄小?（52）A1 2 3 4 5 6 7 B1 5 2 6 3 7 4 C5 1 2 6 3 4 7 D5 1 2 3 7 6 4(53)(53) 為便于存儲和處理一般樹結(jié)構(gòu)形式的信息，常采用孩子兄弟表示法將其轉(zhuǎn)換成二叉樹（左子關(guān)系表示父子、右子關(guān)系表示兄弟），與下圖所示的樹對應(yīng)的二叉樹是（53）。 給定個有n個元素的有序線性表。若采用順序存儲結(jié)

12、構(gòu)則在等概率前提下，刪除其中的一個元素平均需要移動 （54） 個元素。 （54）A B C D1 在平衡二叉樹中， （55） 。 （55）A任意結(jié)點(diǎn)的左、右子樹結(jié)點(diǎn)數(shù)目相同 B任意結(jié)點(diǎn)的左、右子樹高度相同 C任意結(jié)點(diǎn)的左右子樹高度之差的絕對值不大于1D不存在度為1的結(jié)點(diǎn) 在 （56） 存儲結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中元素的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系。 （56）A順序（Sequence） B鏈表（Link） C索引（Index） D散列（Hash） 對于求取兩個長度為n的字符串的最長公共子序列（LCS）問題，利用（57）策略可以有效地避免子串最長公共子序列的重復(fù)計(jì)算，得到時間復(fù)雜度為O（n2）

13、的正確算法。串<1,0,0,1,0,1,0,1>和<0,1,0,1,1,0,1,1>的最長公共子序列的長度為 （58） 。 （57）A分治 B貪心 C動態(tài)規(guī)劃 D分支一限界 （58）A3 B4 C5 D6 設(shè)某算法的計(jì)算時間可用遞推關(guān)系式T（n）2T（n2）n表示，則該算法的時間復(fù)雜度為 （59） 。 （59）AO（lgn） BO（nlgn） CO（n） DO（n2） （60） 在其最好情況下的算法時間復(fù)雜度為O(n)。 （60）A插入排序 B歸并排序 C快速排序 D堆排序 BACCD CDBA 結(jié)點(diǎn)數(shù)目為n的二叉查找樹（二叉排序樹）的最小高度為（52）、最大高度為（5

14、3）。 某雙向鏈表中的結(jié)點(diǎn)如下圖所示，刪除t所指結(jié)點(diǎn)的操作為（54）。（54）At->prior->next=t->next; t->next->prior=t->prior;  Bt->prior->prior=t->prior; t->next->next=t->next;  Ct->prior->next=t->prior; t->next->prior=t->next;  Dt->prior->prior=t->next; t-&g

15、t;next->prior=t->prior; 對于二維數(shù)組a0.4,1.5 ,設(shè)每個元素占1個存儲單元，且以列為主序存儲，則元素a2,2相對于數(shù)組空間起始地址的偏移量是 （55） 。（55）A5 B7 C10 D15 對于n個元素的關(guān)鍵字序列k1,k2,.,kn，當(dāng)且僅當(dāng)滿足關(guān)系kik2i且kik2i+1 (2in,2i1n)稱其為小根堆，反之則為大根堆。以下序列中，（56）不符合堆的定義。（56）A（4,10,15,72,39,23,18） B（58,27,）6,12,8,23,9）  C（4,10,18,72,39,23,15） D（58,36,27,12,8,23

16、,9） 求單源點(diǎn)最短路徑的迪杰斯特拉（Dijkstra）算法是按(57)的順序求源點(diǎn)到各頂點(diǎn)的最短路徑的。（57）A路徑長度遞減 B路徑長度遞增  C頂點(diǎn)編號遞減 D頂點(diǎn)編號遞增（58）算法策略與遞歸技術(shù)的聯(lián)系最弱。（58）A動態(tài)規(guī)劃 B貪心 C回溯 D分治 對于具有n個元素的一個數(shù)據(jù)序列，若只需得到其中第k個元素之前的部分排序，最好采用（59），使用分治(Divide and Conquer)策略的是（60）算法。（59）A希爾排序 B直接插入排序 C快速排序 D堆排序（60）A冒泡排序 B插入排序 C快速排序 D堆排序DAABC BBDC以下是2007年11月份考的 拓?fù)渑判蚴侵?/p>

17、有向圖中的所有頂點(diǎn)排成一個線性序列的過程，若在有向圖中從頂點(diǎn)vi到vj有一條路徑，則在該線性序列中，頂點(diǎn)vi必然在頂點(diǎn)vj之前。因此，若不能得到全部頂點(diǎn)的拓?fù)渑判蛐蛄?，則說明該有向圖一定 （57） 。（57）A. 包含回路 B. 是強(qiáng)連通圖 C. 是完全圖 D. 是有向樹 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素按照a、b、c、d、e的次序進(jìn)入棧S，當(dāng)一個元素從棧中出來后立即進(jìn)入隊(duì)列Q。若隊(duì)列的輸出元素序列是c、d、b、a、e，則元素的出棧順序是 （58） ，棧S的容量至少為 （59） 。（58）A. a、b、c、d、eB. e、d、c、b、aC. c、d、b、a、e D. e、a、b、d、c（59

18、）A. 2B. 3C. 4 D. 5 對于n（n0）個元素構(gòu)成的線性序列L，在 （60） 時適合采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。（60）A. 需要頻繁修改中元素的值B. 需要頻繁地對進(jìn)行隨機(jī)查找C. 需要頻繁地對進(jìn)行刪除和插入操作D. 要求L存儲密度高 對于二叉查找樹（Binary Search Tree），若其左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若其右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；左、右子樹本身就是兩棵二叉查找樹。因此，對任意一棵二叉查找樹進(jìn)行 （61） 遍歷可以得到一個結(jié)點(diǎn)元素的遞增序列。在具有n個結(jié)點(diǎn)的二叉查找樹上進(jìn)行查找運(yùn)算，最壞情況下的算法復(fù)雜度為 （62） 。

19、（61） A. 先序B. 中序C. 后序D. 層序 （62） A. O(n2)B. O(nlog2n)C. O(log2n)D. O(n) 迪杰斯特拉（Dijkstra)算法按照路徑長度遞增的方式求解單源點(diǎn)最短路徑問題，該算法運(yùn)用了 （63） 算法策略。（63）A. 貪心 B. 分而治之C. 動態(tài)規(guī)劃D. 試探回溯 關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系， （64） 是正確的。（64）A. 算法的實(shí)現(xiàn)依賴于數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) B. 算法的效率與數(shù)據(jù)結(jié)構(gòu)無關(guān)C. 數(shù)據(jù)結(jié)構(gòu)越復(fù)雜，算法的效率越高 D. 數(shù)據(jù)結(jié)構(gòu)越簡單，算法的效率越高 若一個問題既可以用迭代方式也可以用遞歸方式求解，則 （65） 方法具有更高的時空效

20、率。（65）A. 迭代 B. 遞歸C. 先遞歸后迭代 D. 先迭代后遞歸以上是2007年11月份考的一個具有 m 個結(jié)點(diǎn)的二叉樹，其二叉鏈表結(jié)點(diǎn)（左、右孩子指針分別用 left 和 right表示）中的空指針總數(shù)必定為（57）個。為形成中序（先序、后序）線索二叉樹，現(xiàn)對該二叉鏈表所有結(jié)點(diǎn)進(jìn)行如下操作：若結(jié)點(diǎn) p 的左孩子指針為空，則將該左指針改為指向p 在中序（先序、后序）遍歷序列的前驅(qū)結(jié)點(diǎn)；若 p 的右孩子指針為空，則將該右指針改為指向 p 在中序（先序、后序）遍歷序列的后繼結(jié)點(diǎn)。假設(shè)指針 s 指向中序（先序、后序）線索二叉樹中的某結(jié)點(diǎn)，則 （58） 。（57）A. m+2 B. m+1 C

21、. m D. m-1（58）A. s>right 指向的結(jié)點(diǎn)一定是 s 所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)B. s>left 指向的結(jié)點(diǎn)一定是 s 所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)C. 從 s 所指結(jié)點(diǎn)出發(fā)的 right 鏈可能構(gòu)成環(huán)D. s 所指結(jié)點(diǎn)的 left 和 right 指針一定指向不同的結(jié)點(diǎn) （59）的鄰接矩陣是一個對稱矩陣。 （59）A. 無向圖 B. AOV 網(wǎng) C. AOE 網(wǎng) D. 有向圖 將一個無序序列中的元素依次插入到一棵（60），并進(jìn)行中序遍歷，可得到一個有序序列。 （60）A.完全二叉樹 B.最小生成樹 C.二叉排序樹 D.最優(yōu)二叉樹 廣義表中的元素可以是原子，也可以是表，因

22、此廣義表的適用存儲結(jié)構(gòu)是 （61） 。 （61）A.鏈表 B.靜態(tài)數(shù)組 C.動態(tài)數(shù)組 D.散列表某一維數(shù)組中依次存放了數(shù)據(jù)元素 12,23,30,38,41,52,54,76,85，在用折半（二分）查找方法（向上取整）查找元素 54 時，所經(jīng)歷“比較”運(yùn)算的數(shù)據(jù)元素依次為 （62） 。（62）A. 41, 52, 54 B. 41, 76, 54 C. 41, 76, 52, 54D. 41, 30, 76, 54具有 n 個頂點(diǎn)、e 條邊的圖采用鄰接表存儲結(jié)構(gòu)，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷運(yùn)算的時間復(fù)雜度均為（63）。（63）A. O(n2) B. O(e2) C. O(n*e) D. O

23、(n+e) 給定一組長度為 n 的無序序列，將其存儲在一維數(shù)組 a0.n-1中?，F(xiàn)采用如下方法找出其中的最大元素和最小元素：比較 a0和an-1，若 a0較大，則將二者的值進(jìn)行交換；再比較 a1和 an-2，若 a1較大，則交換二者的值；然后依次比較 a2和 an-3、a3和an-4、，使得每一對元素中的較小者被交換到低下標(biāo)端。重復(fù)上述方法，在數(shù)組的前 n/2 個元素中查找最小元素，在后 n/2 個元素查找最大元素，從而得到整個序列的最小元素和最大元素。上述方法采用的算法設(shè)計(jì)策略是 （64） 。（64）A.動態(tài)規(guī)劃法 B.貪心法 C.分治法 D.回溯法 設(shè)某算法的計(jì)算時間表示為遞推關(guān)系式 T(

24、n)= T(n-1) + n (n>0)及 T(0)=1，則該算法的時間復(fù)雜度為（65）。 （65）A.(lgn ) B.(n lg n) C.(n) D.(n2) BCACA BDCD一個算法是對某類問題求解過程的精確描述，算法中描述的操作都可以都過將已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)，這句話說明算法具有（可行性）特性。有窮性：算法中每個步驟都能在有限時間內(nèi)完成。采用動態(tài)規(guī)劃策略求解問題的顯著特征是滿足最優(yōu)性原理，其含義是_(52)B_。(52)A當(dāng)前所做出的決策不會影響后面的決策B原問題的最優(yōu)解包含其子問題的最優(yōu)解C問題可以找到最優(yōu)解，但利用貪心法不能找到最優(yōu)解D每次決策必須是當(dāng)前看

25、來最優(yōu)的決策才可以找到最優(yōu)解用線性探查法或鏈地址法構(gòu)建哈希表 及 求平均查找長度 應(yīng)會下面關(guān)于查找運(yùn)算及查找表的敘述，錯誤的是 （57）。 （57）A.哈希表可以動態(tài)創(chuàng)建B.二叉排序樹屬于動態(tài)查找表C.二分查找要求查找表采用順序存儲結(jié)構(gòu)或循環(huán)鏈表結(jié)構(gòu)D.順序查找方法既適用于順序存儲結(jié)構(gòu)，也適用于鏈表結(jié)構(gòu)下面關(guān)于圖（網(wǎng)）的敘述，正確的是 （58）。 （58）A.連通無向網(wǎng)的最小生成樹中，頂點(diǎn)數(shù)恰好比邊數(shù)多 1 B.若有向圖是強(qiáng)連通的，則其邊數(shù)至少是頂點(diǎn)數(shù)的 2 倍 C. 可以采用 AOV 網(wǎng)估算工程的工期 D.關(guān)鍵路徑是 AOE 網(wǎng)中源點(diǎn)至匯點(diǎn)的最短路徑下面關(guān)于二叉排序樹的敘述，錯誤的是 （59）。 （59）A.對二叉排序樹進(jìn)行中序遍歷，必定得到結(jié)點(diǎn)關(guān)鍵字的有序