1、除根結點外，樹上每個結點( )。 a. 可有一個孩子、任意多個雙親 b. 可有任意多個孩子、一個雙親 c. 只有一個孩子、一個雙親 d. 可有任意多個孩子、任意多個雙親 2、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（ ）。 a. (n+1)/2 b. n/2 c. (n-1)/2 d. n 3、采用二分查找方法查找長度為n的線性表時,每個元素的平均查找長度為（ ）。 a. O(log2n) b. O(n2) c. O(n) d. O(nlog2n) 4、設順序線性表中有n個數據元素，則刪除表中第i個元素需向前移動（ ）個元素。 a. n-1-i b. n-i c. i d. n+1-i 5、設順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數為（ ）。 a. (R-F+M)％M b. F-R c. (F-R+M)％M d. R-F 6、設輸入序列是1、2、3、…、n，經過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（ ）。 a. n-1-i b. 不能確定 c. n-i d. n+1-i 7、設輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（ ）。 a. 5，3，4，6，1，2 b. 1，5，4，6，2，3 c. 3，1，2，5，4，6 d. 3，2，5，6，4，1 8、設用鏈表作為棧的存儲結構，則退棧操作（ ）。 a. 必須判別棧是否為滿 b. 必須判別棧是否為空 c. 對棧不作任何判別 d. 必須判別棧元素的類型 9、設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為( )。 a. 第i列0元素的個數之和 b. 第i行0元素的個數之和 c. 第i列非0元素的個數之和 d. 第i行非0元素的個數之和 10、設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（ ）存儲方式最節(jié)省運算時間。 a. 雙向鏈表 b. 雙向循環(huán)鏈表 c. 單向循環(huán)鏈表 d. 單向鏈表 11、設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有( )。 a. 1024 b. 256 c. 20 d. 512 12、設某棵二叉樹的中序遍歷序列為ABCD，先序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為( )。 a. CDAB b. BADC c. CBDA d. BCDA 13、設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為( )。 a. 9 b. 11 c. 12 d. 10 14、設某棵二叉樹中只有度數為0和度數為2的結點，且度數為0的結點數為n，則這棵二叉樹中共有( )個結點。 a. n+1 b. 2n c. 2n+1 d. 2n-1 15、設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有( )條有向邊。 a. n-1 b. m c. n d. m-1 16、設某無向圖有n個頂點，則該無向圖的鄰接表中有( )個表頭結點。 a. 2n-1 b. n c. n/2 d. 2n 17、設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的度之和為( )。 a. 2e b. n c. e d. 2n 18、設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為( )。 a. O(n\*e) b. O(n+e) c. O(n2) d. O(n3) 19、設某數據結構的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數據結構A是( )。 a. 圖結構 b. 物理結構 c. 線性結構 d. 樹型結構 20、設某強連通圖中有n個頂點，則該強連通圖中至少有( )條邊。 a. n(n-1) b. n c. n+1 d. n(n+1) 21、設某完全無向圖中有n個頂點，則該完全無向圖中有( )條邊。 a. n b. n-1 c. n(n-1) d. n(n-1)/2 22、設某哈夫曼樹中有199個結點，則該哈夫曼樹中有( )個葉子結點。 a. 99 b. 101 c. 100 d. 102 23、設某二叉樹中度數為0的結點數為N0，度數為1的結點數為N1，度數為2的結點數為N2，則下列等式成立的是( )。 a. N0=N1+N2 b. N0=N2+1 c. N0=2N1+1 d. N0=N1+1 24、設有6個結點的無向圖，該圖至少應有( )條邊才能確保是一個連通圖。 a. 7 b. 6 c. 8 d. 5 25、設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（ ）條邊。 a. 2n-1 b. n c. n-1 d. 2n 26、設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為( )。 a. i/2 b. 2i+1 c. 2i d. 2i-1 27、設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作為（ ）。 a. top=top+1; b. top->next=top; c. top=top->next; d. top=top-1; 28、設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為（ ）。 a. p->next=s； s->prior=p； p->next->prior=s； s->next=p->next； b. s->prior=p； s->next=p->next； p->next=s； p->next->prior=s； c. p->next=s； p->next->prior=s； s->prior=p； s->next=p->next； d. s->prior=p；s->next=p->next；p->next->prior=s； p->next=s； 29、設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為（ ）。 a. q=p->next；q->data=p->data；p->next=q->next；free(q)； b. q=p->next；p->data=q->data；free(q)； c. q=p->next；p->next=q->next；free(q)； d. q=p->next；p->data=q->data；p->next=q->next；free(q)； 30、設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（ ）。 a. front->next=s；front=s； b. rear->next=s；rear=s； c. s->next=front；front=s； d. s->next=rear；rear=s； 31、設指針q指向單鏈表中結點A，指針p指向單鏈表中結點A的后繼結點B，指針s指向被插入的結點X，則在結點A和結點B插入結點X的操作序列為（ ）。 a. p->next=s->next；s->next=p； b. p->next=s；s->next=q； c. s->next=p->next；p->next=-s； d. q->next=s； s->next=p； 32、設帶有頭結點的單循環(huán)鏈表的頭指針為head，則其判空條件是（ ）。 a. head->next==head b. head==NULL c. head->next==NULL d. head!= NULL 33、設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有( )個空指針域。 a. 4m b. 2m-1 c. 2m+1 d. 2m 34、設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是( )。 a. 任一結點無左孩子 b. 任一結點無右孩子 c. 高度等于其結點數 d. 空或只有一個結點 35、設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為（ ）。 a. O(1) b. O(n) c. O(n2) d. O(nlog2n) 36、設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為( )。 a. 40 b. 45 c. 30 d. 20 37、設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為( )。 a. 7 b. 6 c. 5 d. 8 38、設一條單鏈表的頭指針為head，且該鏈表沒有頭結點，則其判空條件是（ ）。 a. head==NULL b. head->next==head c. head->next==NULL d. head!=NULL 39、設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數為( )。 a. N2+N3 b. N1-1 c. N1+N3 d. N2-1 40、若采用鄰接表存儲結構，則圖的深度優(yōu)先搜索類似于二叉樹的（） a. 層次遍歷 b. 先根遍歷 c. 中根遍歷 d. 后根遍歷 41、若采用鄰接表存儲結構，則圖的廣度優(yōu)先搜索類似于二叉樹的（） a. 先根遍歷 b. 后根遍歷 c. 層次遍歷 d. 中根遍歷 42、若線性表最常用的操作是存取第i個元素及其前驅的值，則采用（ ）存儲方式最節(jié)省時間。 a. 雙向鏈表 b. 順序表 c. 單鏈表 d. 單循環(huán)鏈表 43、若一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的第一趟結果為（ ）。 a. 40，38，46，56，79，84 b. 40，38，46，84，56，79 c. 38，40，46，56，79，84 d. 40，38，46，79，56，84 44、若一個圖的邊集為 {(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)} ，則從頂點 A 開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為（ ）。 a. A,B,C,F,D,E b. A,C,F,D,E,B c. A,B,D,F,E,C d. A,B,D,C,F,E 45、若一個圖的邊集為 {(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)} ，則從頂點 A 開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為（ ）。 a. A,B,C,F,D,E b. A,B,C,D,E,F c. A,B,D,C,E,F d. A,C,B,F,D,E 46、線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（ ）。 a. 連續(xù)或不連續(xù)都可以 b. 必須是連續(xù)的 c. 部分地址必須是連續(xù)的 d. 一定是不連續(xù)的 47、用鏈接方式存儲的隊列，在進行插入運算時（ ）。 a. 僅修改尾指針 b. 頭、尾指針都要修改 c. 僅修改頭指針 d. 頭、尾指針都不要修改 48、用鄰接表存儲圖所用的空間大?。?）。 a. 只與圖的邊數有關 b. 與圖的頂點數和邊數都有關 c. 只與圖的頂點數有關 d. 與邊數的平方有關 49、樹的后根遍歷序列等同于該樹對應的二叉樹的( )。 a. 先序序列 b. 中序序列 c. 后序序列 d. 層次序列 50、樹型結構最適合用來表示( )。 a. 無序數據元素 b. 有序數據元素 c. 元素之間無聯系的數據 d. 元素之間具有分支層次關系的數據 51、棧。和隊列的共同點是（ ）。 a. 只允許在端點處插入和刪除元素 b. 都是先進后出 c. 都是先進先出 d. 沒有共同點 52、數據結構是研究數據的（ ）以及它們之間的相互關系。 a. 理想結構，抽象結構 b. 物理結構，邏輯結構 c. 理想結構，物理結構 d. 抽象結構，邏輯結構 53、數據的最小單位是（ ）。 a. 數據元素 b. 數據項 c. 數據類型 d. 數據變量 54、已知一個有向圖的邊集為 {,,,,,} ，則由該圖產生的一種可能的拓撲序列為( )。 a. a,b,c,d,e b. a,c,b,e,d c. a,b,d,e,b d. a,c,d,b,e 55、對線性表進行二分查找時，要求線性表必須（ ）。 a. 以鏈接方式存儲 b. 以鏈接方式存儲，且結點按關鍵字有序排序 c. 以順序方式存儲，且結點按關鍵字有序排序 d. 以順序方式存儲 56、在長度為n的順序存儲的線性表中插入第i個元素(1≤i≤n)需向后移動（ ）個元素。 a. n-i b. i c. n-1-i d. n-i+1 57、在用鄰接表表示圖時，對圖進行深度優(yōu)先搜索遍歷的算法的時間復雜度為（ ）。 a. O(n2) b. O(n+e) c. O(n3) d. O(n) 58、在有向圖的鄰接表存儲結構中，頂點v在鏈表中出現的次數是( )。 a. 頂點v的度 b. 依附于頂點v的邊數 c. 頂點v的入度 d. 頂點v的出度 59、在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現的是（ ）。 a. G中有一條從Vi到Vj的路徑 b. G中有弧 c. G中沒有弧 d. G中有一條從Vj到Vi的路徑 60、在下列存儲形式中，哪一個不是樹的存儲形式？( ) a. 孩子鏈表表示法 b. 順序存儲表示法 c. 孩子兄弟表示法 d. 雙親表示法 61、在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點，則執(zhí)行（ ）。 a. q->next = s；s->next = p； b. s->next = p->next；p->next = s； c. p->next = s->next；s->next = p； d. p->next = s；s->next = q； 62、在一個具有n個頂點的無向圖中，每個頂點度的最大值為（ ） a. n-1 b. n+1 c. n d. 2(n-1) 63、圖的BFS生成樹的樹高比DFS生成樹的樹高（ ）。 a. 大或相等 b. 小 c. 小或相等 d. 大 64、含有n個結點的二叉樹采用二叉鏈表存儲時，空指針域的個數為( )。 a. n b. n+1 c. n+2 d. n-1 65、關于無向圖的鄰接矩陣的說法中正確的是（ ）。 a. 矩陣中的非零元素個數等于圖的邊數 b. 矩陣中非全零元素的行數等于圖中的頂點數 c. 第i行上非零元素個數和第i列上非零元素個數一定相等 d. 第i行上與第i列上非零元素總和等于頂點Vi的度數 66、二叉樹的第k層的結點數最多為( )。 a. 2k b. 2k -1 d. 2k-1 67、二叉排序樹按( )遍歷可以得到一個從小到大的有序序列。 a. 后序 b. 中序 c. 層次 d. 先序 68、下面程序的時間復雜為（ ）。 for(i=1, s=0; i<=n; i++) { t=1; for(j=1; j<=i; j++) t=t*j; s=s+t; } a. O(n3) b. O(n) c. O(n2) d. O(n4) 69、下面程序段的時間復雜度為（ ）。 s=i=0; do { i=i+1; s=s+i; } while(i<=n); a. O(n) b. O(nlog2n) c. O(n2) d. O(1) 70、下面關于線性表的敘述錯誤的是（ ）。 a. 線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間 b. 線性表采用順序存儲必須占用一片連續(xù)的存儲空間 c. 線性表采用順序存儲便于插入和刪除操作的實現 d. 線性表采用鏈式存儲便于插入和刪除操作的實現 71、下述編碼中哪一個不是前綴編碼( )。 a. 0,10,110,111 b. 00,01,10,11 c. 1,01,000,001 d. 0,1,00,11 72、下列說法不正確的是（ ）。 a. 圖的深度遍歷不適用于有向圖 b. 圖的深度遍歷是一個遞歸過程 c. 遍歷的基本方法有兩種：深度遍歷和廣度遍歷 d. 圖的遍歷是從給定的源點出發(fā)每個頂點僅被訪問一次 73、下列有關圖遍歷的說法中不正確的是（）。 a. 非連通圖不能用深度優(yōu)先搜索法 b. 連通圖的深度優(yōu)先搜索是一個遞歸過程 c. 圖的遍歷要求每一頂點僅被訪問一次 d. 圖的廣度優(yōu)先搜索中鄰接點的尋找具有“先進先出”的特征 74、下列哪種圖的鄰接矩陣為對稱矩陣? ( ) a. 帶權有向圖 b. 有向圖 c. 無向圖 d. 有向圖或無向圖 75、一個帶權的無向連通圖的最小生成樹（ ）。 a. 只有一棵 b. 一定有多棵 c. 有一棵或多棵 d. 可能不存在 76、順序表是線性表的（） a. 鏈式存儲結構 b. 順序存儲結構 c. 索引存儲結構 d. 散列存儲結構 77、線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（） a. 必須是連續(xù)的 b. 部分地址必須是連續(xù)的 c. 一定是不連續(xù)的 d. 連續(xù)或不連續(xù)都可以 78、一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（） a. e,d,c,b,a b. d,e,c,b,a c. d,c,e,a,b d. a,b,c,d,e 79、在下列鏈表中，不能從任一結點出發(fā)訪問到表中的所有結點的是（） a. 單鏈表 b. 單向循環(huán)鏈表 c. 雙向循環(huán)鏈表 d. 循環(huán)鏈表 80、二叉樹結點度的集合為（）。 a. （1） b. （0，1，2） c. （1，2） d. （0） 81、以二分查找方法查找一個線性表時，此線性表必須是（）。 a. 順序存儲的有序表 b. 鏈式存儲的有序表 c. 鏈表 d. 順序表 82、設哈夫曼樹的葉子結點的個數為n，那么該樹的結點總數為（） c.不能唯一確定 83、對二叉樹來說，第i層上至多有（）個結點。 a. 2i b. 2i-1 c. 2i-1 d. 2i-1-1 84、數據結構包括3個方面的內容，它們是（）。 a. 數據、數據元素、數據項 b. 數據元素、數據處理、算法實現 c. 數據元素、數據的邏輯結構、數據的存儲結構 d. 數據的邏輯結構、數據的存儲結構、數據的操作 85、數據在計算機存儲器內表示時，存儲結點連續(xù)存放且存儲順序與邏輯順序相同，這種存儲方式稱為（）。 a. 索引存儲方式 b. 順序存儲方式 c. 鏈式存儲方式 d. 散列存儲方式 86、冒泡排序屬于（）。 a. 插入排序 b. 選擇排序 c. 快速排序 d. 交換排序 87、下列程序段的時間復雜度為（）。 i=1;j=0; while（i+j<=n） {if（i>j）j++; elsei++; } a. O（n） b. O（nlog2n） c. O（i*j） d. O（i+j） 88、下面程序的時間復雜為（）。 for（i=1,s=0;i<=n;i++） {t=1;for（j=1;j<=i;j++）t=t*j;s=s+t;} a. O（n） b. O（n2） c. O（n3） d. O（n4） 89、含有n個結點的二叉樹采用二叉鏈表存儲時，空指針域的個數為（）。 a. n-1 b. n c. n+1 d. n+2 90、設某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。 a. n（n-1）/2 b. n（n-1） c. n d. n-1 1、調用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（F） 2、分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（T） 3、冒泡排序在初始關鍵字序列為逆序的情況下執(zhí)行的交換次數最多。（T） 4、滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（T） 5、設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（F） 6、線性表的順序存儲結構比鏈式存儲結構更好。（F） 7、不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。（T） 8、完全二叉樹中的葉子結點只可能在最后兩層中出現。（T） 9、由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（F） 10、線性表中的所有元素都有一個前驅元素和后繼元素。（F) 1、head指向單鏈表的表頭，p指向單鏈表的表尾結點，則執(zhí)行p->next=head后，該單鏈表構成 循環(huán)鏈表 2、在單鏈表中，若p和s是兩個指針，且滿足p->next與s相同，則語句p->next=s->next的作用是 刪除 s指向的結點。 3、在一個長度為n的順序表中的第i(1≤i≤n＋1)個元素之前插入一個元素時，需向后移動的元素個數為 n-i+1 。 4、設順序線性表中有n個數據元素，則刪除表中第i個元素需向前移動 n-i 個元素。 5、衡量一個算法，除了正確性之外，主要考慮的兩個方面是 時間復雜度 和 空間復雜度 。 6、在一個具有n個頂點的無向完全圖中，包含 n(n-1)/2 條邊。 7、對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為 n^2 。 8、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為 (n+1)/2 。 9、樹型結構最適合用來表示元素之間具有 分支層次關系 的數據。 1、已知一棵二叉樹的先（前）序遍歷序列為ABDEGCFH,中序遍歷序列為DBGEACFH,請畫出該二叉樹,并寫出該二叉樹的后序序列。 2、畫出一棵二叉樹,使其：中序序列為DCBGEAHFIJK,后序序列：DCEGBFHKJIA 3、請寫出對(53, 87, 12, 61,98,17, 97, 75, 53, 26)進行一次劃分的過程。 4、有一結點序列為(7,19,2,6,32,3,21,10),要求以該序列作為帶權二叉樹中結點的權值,構造并畫出一棵哈夫曼樹,并計算其帶權路徑長度。 5、對下面所示的無向網,要求構造出一棵最小生成樹（中間過程可以省略）,并計算該最小生成樹的權。 6、下面所示為有向圖的鄰接表,試畫出該有向圖,并給出由頂點V1開始的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的結果。 7、有一結點序列為(45,24,53,12,28,90),要求構造并畫出一棵二叉排序樹,并輸出以中序方式遍歷該樹的序列。