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