【正文】 )，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（ A ）。 (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc200． 下列程序段的時(shí)間復(fù)雜度為（ A ）。for(i=0； im； i++) for(j=0； jt； j++) c[i][j]=0；for(i=0； im； i++) for(j=0； jt； j++) for(k=0； kn； k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]； (A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)201． 設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)（ A ）個(gè)元素。 (A) ni (B) n+l i (C) n1i (D) i202． 設(shè)F是由TT2和T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B，TT2和T3的結(jié)點(diǎn)數(shù)分別為NN2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為（A ）。 (A) N11 (B) N21 (C) N2+N3 (D) N1+N3203． 利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（ C ）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(log2n)204． 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為（ D ）。 (A) pright=s； sleft=p； prightleft=s； sright=pright； (B) sleft=p；sright=pright；pright=s； prightleft=s； (C) pright=s； prightleft=s； sleft=p； sright=pright； (D) sleft=p；sright=pright；prightleft=s； pright=s；205． 下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（ D ）。 (A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序206． 設(shè)輸入序列…、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是（ C ）。 (A) ni (B) n1i (C) n+l i (D) 不能確定207． 設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇（ B ）。 (A) 小于等于m的最大奇數(shù) (B) 小于等于m的最大素?cái)?shù) (C) 小于等于m的最大偶數(shù) (D) 小于等于m的最大合數(shù)208． 設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（ C ）個(gè)。 (A) 4 (B) 5 (C) 6 (D) 7209． 設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（ A ）條邊。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) (n1)/2210． 設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為（ C ）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n1)/2211． 設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（ C ）次比較。 (A) 1 (B) 2 (C) 3 (D) 4212． 設(shè)順序線性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為（ D ）。 (A) 6 (B) 11 (C) 5 (D) 213． 設(shè)有向無(wú)環(huán)圖G中的有向邊集合E={1，2，2，3，3，4，1，4}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵?A ）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3214． 設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（ A ）。 (A) 4 (B) 5 (C) 6 (D) 7215． 下列程序段的時(shí)間復(fù)雜度為（ A ）。i=0，s=0； while (sn) {s=s+i；i++；} (A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)216． 設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（ D ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 (A) 單向鏈表 (B) 單向循環(huán)鏈表 (C) 雙向鏈表 (D) 雙向循環(huán)鏈表217． 設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)X的操作序列為（ B ）。(A) snext=pnext；pnext=s； (B) qnext=s； snext=p；(C) pnext=snext；snext=p； (D) pnext=s；snext=q；218． 設(shè)輸入序列為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，3219． 設(shè)有一個(gè)10階的下三角矩陣A（包括對(duì)角線），按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則A[5][4]地址與A[0][0]的地址之差為（ B ）。 (A) 10 (B) 19 (C) 28 (D) 55220． 設(shè)一棵m叉樹中有N1個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的結(jié)點(diǎn)，……，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹中共有（ D ）個(gè)葉子結(jié)點(diǎn)。 (A) (B) (C) (D) 221． 二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（ A ）根結(jié)點(diǎn)的值。 (A) (B) (C) = (D) !=222． 設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長(zhǎng)度為（ D ）。 (A) 129 (B) 219 (C) 189 (D) 229223． 設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到HASH表中需要做（ D ）次線性探測(cè)。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n1)/2224． 設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（ C ）個(gè)結(jié)點(diǎn)。 (A) 2n (B) n+l (C) 2n1 (D) 2n+l 225． 設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為8，則最多經(jīng)過（ B ）趟插入排序可以得到有序序列。 (A) 6 (B) 7 (C) 8 (D) 9226． 設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（ D ）。(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，Y227． 設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。（ C ） (A)688 (B) 678 (C)692 (D) 696228． 若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為（ D ）。 (A) 1，2，3 (B) 9，5，2，3 (C) 9，5，3 (D) 9，4，2，3229． 對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為（ C ）。 (A) O（1） 　　 (B) O（n）　　 (C) O（1og2n） (D) O（n2）230． 對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用 H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ D ）個(gè)。 (A) 1 (B) 2 (C) 3 (D) 4231． 設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（ A ）條邊才能確保是一個(gè)連通圖。 (A) 5 (B) 6 (C) 7 (D) 8232． 設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（ B ）個(gè)空指針域。 (A) 2m1 (B) 2m (C) 2m+1 (D) 4m二、判斷題1． 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。（ ）2． 鏈表的每個(gè)結(jié)點(diǎn)都恰好有一個(gè)指針。（ ）3． 同一組不重復(fù)輸入序列執(zhí)行不同的入棧出棧組合操作，所得結(jié)果也可能相同。（ ）4． 改進(jìn)的KMP算法中，字符串”abaaaba”的nextval數(shù)組值是0101110。（ ）5． 用六叉鏈表表示30個(gè)結(jié)點(diǎn)的六叉樹，則樹中共有151個(gè)空指針。（ ）6． 數(shù)組是一種線性結(jié)構(gòu)，因此只能用來(lái)存儲(chǔ)線性表。（ ）7． 若有向圖不存在回路，即使不用訪問標(biāo)志位同一結(jié)點(diǎn)也不會(huì)被訪問兩次。（ ）8． 若裝填因子a為1，則向散列表中散列元素時(shí)一定會(huì)產(chǎn)生沖突。（ ）9． 若把堆看成是一個(gè)完全二叉樹，則該樹一定是一棵排序二叉樹。（ ）10． 外排中使用置換選擇排序的目的，是為了增加初始?xì)w并段的長(zhǎng)度。（ ）11． 抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān)。（Y ）12． 線性表的插入和刪除總是伴隨著大量數(shù)據(jù)的移動(dòng)。（ N ）13． 隊(duì)列在程序調(diào)用是必不可少，因此遞歸離不開隊(duì)列。（ N ）14． 字符串’aababaaaba’的改進(jìn)函數(shù)nextval數(shù)組值是0020200320。(Y )15． 二叉樹中有雙子女的父結(jié)點(diǎn)，在中序遍歷中后繼一定是其中一個(gè)子女結(jié)點(diǎn)。（ N ）16． 不用遞歸就不能實(shí)現(xiàn)二叉樹的前序遍歷。（ N ）17． 若有向圖有n個(gè)頂點(diǎn)，則其強(qiáng)連通分量最多有n個(gè)。(Y )18． 平衡二叉樹一定是一棵完全二叉樹。（ N ）19． 若某內(nèi)部排序算法不穩(wěn)定，則該算法沒有使用價(jià)值。（ N ）20． 倒排文件的目的是為了多關(guān)鍵字查找。(Y )21． 已知指針curr指向鏈表中的某結(jié)點(diǎn)，執(zhí)行語(yǔ)句curr=currnext；不會(huì)刪除該鏈表中的結(jié)點(diǎn)。 ( )22． 若二叉樹的葉結(jié)點(diǎn)數(shù)為1，則其高度等于結(jié)點(diǎn)數(shù)(僅含根結(jié)點(diǎn)的二叉樹高度 為1)。 （ ） 23． 按中序周游二叉樹時(shí)，某個(gè)結(jié)點(diǎn)的直接后繼是它的右子樹中第一個(gè)被訪問 的結(jié)點(diǎn)。 ( ) 24． 完全二叉樹的某結(jié)點(diǎn)若無(wú)左孩子，則它必是葉結(jié)點(diǎn)。 ( ) 25． 向二叉檢索樹中插入一個(gè)新結(jié)點(diǎn)，需要比較的次數(shù)不可能大于此二叉樹的高度。 ( ) 26． 對(duì)一個(gè)堆按層次周游，一定能得到一個(gè)有序序列。 ( ) 27． 一棵樹中的葉子結(jié)點(diǎn)數(shù)一定等于其對(duì)應(yīng)的二叉樹中的葉子結(jié)點(diǎn)數(shù)。 ( ) 28． 將一棵樹轉(zhuǎn)換為二叉樹表示后，該二叉樹的根結(jié)點(diǎn)沒有右子樹。 ( ) 29． 任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)湫蛄?，而且拓?fù)湫蛄胁晃ㄒ弧?( ) 30． 快速排序在最差情況下的時(shí)間復(fù)雜度是0(n2)，此時(shí)它的性能并不比冒泡排序更好。 ( )31． AVL樹的任何子樹都是AVL樹。（ Y） 32． 用相鄰矩陣表示圖所用的存儲(chǔ)空間大小與圖的邊數(shù)成正比。（ N） 33． 霍夫曼樹一定是滿二叉樹。（ Y）34． 棧是一種線性結(jié)構(gòu)。（Y ） 35． B＋樹既適于隨機(jī)檢索，也適于順序檢索。（N ） 36． 記錄是數(shù)據(jù)處理的最小單位。 （ ） 37． 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。( )38． 算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。（ ）39． 健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。( Y )40． 算法可以用不同的語(yǔ)言描述，如果用C 語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述，則算法實(shí)際上就是程序了。（ ）41． 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。( Y )42． 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。（ ）43． 在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。（ ）44． 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（ ）45． 數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。( Y )46． 數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu). （ ）