1、數據結構模擬卷一、選擇題1 .在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為（）。A. O（n）B. O（n/2）C. O（1）D. O（n 2）2 .帶頭結點的單鏈表first 為空的判定條件是：（）。A. first = NULL;B. first->link = NULL;C. first->link = first;D. first != NULL;3 .從邏輯上可以把數據結構分為（）兩大類。A.動態結構、靜態結構B.順序結構、鏈式結構C.線性結構、非線性結構D ,初等結構、構造型結構4 .在系統實現遞歸調用時需利用遞歸工作記錄保存實際參數的值。在傳值參數

2、情形，需為對應形式參數分配空間，以存放實際參數的副本；在引用參數情形，需保存實際參數的（）,在被調用程序中可直接操縱實際參數。A.空間B.副本 C.返回地址D.地址5 .以下數據結構中，哪一個是線性結構（）。A.廣義表 B. 二叉樹 C. 稀疏矩陣D.串6 .以下屬于邏輯結構的是（）。A.順序表 B. 哈希表C.有序表 D. 單鏈表7 .對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長 度為（）的值除以9。A. 20B. 18C.25D. 228 .在有向圖中每個頂點的度等于該頂點的（）。A.入度B. 出度C.入度與出度之和D.入度與出度之差9 .在基于排序碼比較的

3、排序算法中，（）算法的最壞情況下的時間復雜度不高于O（nlog 2n） 。A.起泡排序B.希爾排序C.歸并排序 D.快速排序）的查找速度。10 .當“的值較小時，散列存儲通常比其他存儲方式具有（A.較慢B.較快C.相同 D.不同二、填空題1 .二維數組是一種非線性結構，其中的每一個數組元素最多有 2 個直接前驅（或直接后繼）。2 .將一個n階三對角矩陣A的三條對角線上的元素按行壓縮存放于一個一維數組 B中， A00存放于B0中。對于任意給定數組元素BK,它應是A中第【（K+1） /3】行的元素。3 .鏈表對于數據元素的插入和刪除不需移動結點，只需改變相關結點的 指針 域的值。4 .在一個鏈式棧

4、中，若棧頂指針等于NULL則為一空棧。5 .主程序第一次調用遞歸函數被稱為外部調用，遞歸函數自己調用自己被稱為內部調用， 它們都需要利用棧保存調用后的返回 地址。6 .在一棵機中， 葉子結點沒有后繼結點。7 . 一棵樹的廣義表表示為a （b （c, d （e, f）, g （h） ）, i （j, k （x, y）,結點 f的層數為3。假定根結點的層數為0。8 .在一棵AVL樹（高度平衡的二叉搜索樹）中，每個結點的左子樹高度與右子樹高度之差的絕對值不超過1。9 . n （n > 0）個頂點的無向圖最多有 n（n-1）/2 條邊，最少有 0 條邊。10 .在索引存儲中，若一個索引項對應數據

5、對象表中的一個表項（記錄），則稱此索引為 稠密 索引，若對應數據對象表中的若干個表項，則稱此索引為 稀疏 索引。三、判斷題1 .數組是一種復雜的數據結構，數組元素之間的關系既不是線性的也不是樹形的（對）2 .鏈式存儲在插入和刪除時需要保持物理存儲空間的順序分配，不需要保持數據元素之間的邏輯順序（錯）3 .在用循環單鏈表表示的鏈式隊列中，可以不設隊頭指針，僅在鏈尾設置隊尾指針（對）4 .通常遞歸的算法簡單、易懂、容易編寫，而且執行的效率也高（錯）5 . 一個廣義表的表尾總是一個廣義表（對）6 .當從一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后 再按條件把它逐層向下調整

6、，直到調整到合適位置為止（對）7 .對于一棵具有 n個結點，其高度為 h的二叉樹，進行任一種次序遍歷的時間復雜度為O(h)(錯)而且與圖的邊數也有8 .存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數有關,關(錯)9 .直接選擇排序是一種穩定的排序方法(錯)10 .閉散列法通常比開散列法時間效率更高(錯)四、運算題1 .設有一個10 10的對稱矩陣A,將其下三角部分按行存放在一個一維數組 存放于B0中，那么A85存放于B中什么位置。2 .這是一個統計單鏈表中結點的值等于給定值x的結點數的算法，其中請重新編寫出正確的while循環。int count ( ListNode * Ha, Ele

7、mType x ) / Ha為不帶頭結點的單鏈表的頭指針int n = 0;while ( Ha->link != NULL ) Ha = Ha->link;if ( Ha->data = x ) n+;return n;3 .已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, E, F, D, I, H, J, G后序序列：4 . 已知一個有序表 (15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 )于一維數組a12中，根據折半搜索過程

8、填寫成功搜索下表中所給元素94時的比較次數。B 中，A00while循環有錯,順序存儲34, 56, 58, 63,3456586394元素值 比較次數5 .設散列表為 HT17,待插入關鍵碼序列為 Jan, Feb, Mar, Apr, May, June,July, Aug, Sep, Oct, Nov, Dec ,散列函數為 H (key) = i 2 ,其中，i 是關鍵碼第一個字母在字母表中的序號。現采用線性探查法解決沖突。字母ABCDEFGHIJKLM序號12345678910111213字母NOPQRSTUVWXYZ序號14151617181920212223242526(1)試畫

9、出相應的散列表;(2)計算等概率下搜索成功的平均搜索長度；參考答案：1.根據題意，矩陣 A中當元素下標I與J滿足I >J時，任意元素 AIJ在一維數組B中的存放位置為I * (I + 1) / 2 + J ,因此，A85在數組B中位置為8 * (8 + 1) / 2 + 5 = 41。2 .while ( Ha != NULL ) if ( Ha->data = x ) n+;Ha = Ha->link;3 .后序序列：C, B, F, E, I, J, H, G, D, A4.3456586394021344元素值比較次數/對1個給1分，全對給8分AprAugDecFebJ

10、anMarMayJun eJulySepOctNov067(1)(2)(2)(4)(5)(2)(5)(6)1112138910123455.H(Jan)=102H(Feb) =62 = 3 ,成功.H(Mar)=132H(Apr) =1 2 = 0 ,成功.H(May)=132H(June) =10 2 = 5 , = 6 ,功.H(July)=H(Aug)=H(Sep) =19 2 = 9H(Oct)=11 ,成功.H(Nov)=11 , = 12 ,成功.H(Dec)=42 = 2 ,成功.相應的散列表(6分)，錯一個存儲位置扣1分，最多扣6分。(2)搜索成功的平均搜索長度為1/12 *

11、(1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12(2分)五、算法設計題已知二叉樹中的結點類型用BinTreeNode表示，被定義為：struct BTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中 data為結點值域，leftChild 和rightChild分別為指向左、右子女結點的指針域，根據下面函數聲明編寫出求一棵二叉樹中結點總數的算法，該總數值由函數返回。假定參數BT初始指向這棵二叉樹的根結點。int BTreeCount ( BinTreeNode*

12、 BT );解:int BTreeCount ( BinTreeNode* BT ) if ( BT = NULL ) return 0;else return BTreeCount ( BT->leftChild ) + BTreeCount(BT->rightChild )+ 1數據結構模擬卷、單項選擇題1 .以下與數據的存儲結構無關的術語是（）。A.循環隊列B. 鏈表C.哈希表 D. 棧2 .以下數據結構中，哪一個是線性結構（）。A.廣義表 B. 二叉樹 C. 稀疏矩陣D.串3 .以下那一個術語與數據的存儲結構無關？（）。A.棧B.哈希表 C. 線索樹 D.雙向鏈表4 .在下

13、面的程序段中，對x的賦值語句的頻度為（）。FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A. O（2n） B . O（n）C. O（n2）D . O（log J）5 .下面關于線性表的敘述中，錯誤的是哪一個（）。A.線性表采用順序存儲，必須占用一片連續的存儲單元。B.線性表采用順序存儲，便于進行插入和刪除操作。C.線性表采用鏈接存儲，不必占用一片連續的存儲單元。D.線性表采用鏈接存儲，便于插入和刪除操作。6 .線性表是具有 門個（）的有限序列（n>0）。A.表元素 B .字符C.數據元素D .數據項 E .信息項則利7 .若某線性表最常用的操作是存取任一指

14、定序號的元素和在最后進行插入和刪除運算,9 .下面給出的四種排序法中（）A.插入 B. 冒泡10 .下列排序算法中，其中（A.堆排序，冒泡排序C.直接選擇排序，歸并排序11 .已知一算術表達式的中綴形式為A. -A+B*C/DE B. -A+B*CD/E C-+*ABC/DED. -+A*BC/DE用（）存儲方式最節省時間。A.順序表 B .雙鏈表 C .帶頭結點的雙循環鏈表D .單循環鏈表8 .某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節省運算時間。A.單鏈表 B .僅有頭指針的單循環鏈表C .雙鏈表D.僅有尾指針的單循環鏈表排序法是不穩定性

15、排序法。C.二路歸并D.堆積）是穩定的。B.快速排序，堆排序D.歸并排序，冒泡排序A+B*C-D/E,后綴形式為 ABC*+DE/-,其前綴形式為12.算術表達式a+b* （c+d/e ）轉為后綴表達式后為（）。A. ab+cde/*B . abcde/+*+C . abcde/*+ D . abcde*/+二、填空題，在橫線處填寫合適內容1 .數據結構的存儲結構包括順序、鏈接、索引和散列等四種。2 .在程序運行過程中可以擴充的數組是 動態 分配的數組。這種數組在聲明它時需要使用數組指針。3 .在鏈表中進行插入和刪除操作的效率比在順序存儲結構中進行相同操作的效率4 .棧是一種限定在表的一端進行

16、插入和刪除的線性表，又被稱為 后進先出 表。5 .如果一個對象部分地包含自己，或自己定義自己，則稱這個對象是 遞歸 的對象。6 . 一棵樹的廣義表表示為a（b（c,d（e,f）,g（h）,i（j,k（x,y），結點f的層數為 3假定樹根結點的層數為0。7 . 一棵樹按照左子女-右兄弟表示法轉換成對應的二叉樹，則該二叉樹中樹根結點肯定沒有 右 子女。8 .向一棵二叉搜索樹中插入一個元素時，若元素的值小于根結點的值，則應把它插入到根 結點的 左子樹 上。9 .設圖 G=（V,E） , V=1,2,3,4,E=<1,2>,<1,3>,<2,4>,<3,4&g

17、t;，從頂點 1 出發，對圖 G進行廣度優先搜索的序列有 2 種。10 .每次直接或通過基準元素間接比較兩個元素，若出現逆序排列就交換它們的位置，這種排序方法叫做 交換 排序。11 .快速排序在平均情況下的空間復雜度為 O （log2n） 。12 .若對長度n=10000的線性表進行二級索引存儲，每級索引表中的索引項是下一級20個表項的索引，則一級索引表的長度為 500。三、判斷題1 .在順序表中進行順序搜索時，若各元素的搜索概率不等，則各元素應按照搜索概率的降序排列存放，則可得到最小的平均搜索長度（ 對）2 .在二叉搜索樹中，若各結點的搜索概率不等，使得搜索概率越小的結點離樹根越近，則得到的

18、是最優二叉搜索樹（ 錯）3 .對于AOER絡，加速任一關鍵活動都能使整個工程提前完成（ 錯）4 .直接選擇排序是一種穩定的排序方法（ 錯）5 .閉散列法通常比開散列法時間效率更高（ 錯）6 .數據的邏輯結構是指各數據元素之間的邏輯關系，是用戶根據應用需要建立的（對）7 .順序表和一維數組一樣，都可以按下標隨機（或直接）訪問（對）8 .在一個順序存儲白循環隊列中，隊頭指針指向隊頭元素的后一個位置（ 錯）9 .用非遞歸方法實現遞歸算法時一定要使用遞歸工作棧（ 錯）10 .在一棵二叉樹中，假定每個結點只有左子女，沒有右子女，對它分別進行中序遍歷和后序遍歷，則具有相同的結果（ 對）四、運算題1 .設有

19、一個二維數組 A1020,按行存放于一個連續的存儲空間中，A00的存儲地址是200,每個數組元素占1個存儲字，則A62的存儲字地址是多少。A62 的存儲字地址:2 .已知一棵二叉樹的中序和后序序列如下，求該二叉樹的高度(假定空樹的高度為-1)和度為2、度為1及度為0的結點個數。中序序歹 U： c,b,d,e,a,g,i,h,j,f后序序歹 U： c,e,d,b,i,j,h,g,f,a求解一下問題：高度：度為2的結點數：度為1的結點數：度為0的結點數：3 .假定一組記錄為(36,75,83,54,12,67,60,40),將按次序把每個結點插入到初始為空的一棵AVL樹中，請回答在插入時需進行“左

20、單旋轉”、“右單旋轉”、“先左后右雙旋轉”、“先右后左雙旋轉”，“不調整”的結點數各是多少？左單旋轉結點個數：右單旋轉結點個數：先左后右雙旋轉結點個數：先右后左雙旋轉結點個數：不調整結點個數：4 .已知一個帶權圖的頂點集V和邊集G分別為：V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12;試根據迪克斯特拉(Dijkstra)算法求出從頂點0到其余各頂點的最短路徑，在下面填寫對應的路徑長度。頂點： 0123 4560路徑長度:5.已知一個數據表為

21、36,25,25*,62,40,53，請寫出在進行快速排序的過程中每次劃分后數據表的變化。(0) 36 25 25* 62 40 53(2)參考答案：1. A62的存儲字地址：322答案說明：按行存儲時，計算 Aij地址的公式為LOC(i,j)=LOC(0,0)+(i*n+j)*d其中首地址LOC(0,0)=200,每個數組元素的存儲占用數d=1,二維數組的列數 n=20,根據題意，元素A62的存儲地址為LOC(6,2)=200+(6*20+2)*1=3222.高度：4度為2的結點數：3度為1的結點數：3度為0的結點數：43.左單旋轉結點個數：1先左后右雙旋轉結點個數:先右后左雙旋轉結點個數：

22、0不調整結點個數：64. 錯1個數彳1扣2分，最多扣全部 8分。0161014252131頂點： 0123 45 6路徑長度:5.(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 53(2) 25* 25 36 53 40 62(3) 25*25 36 40 53 62五、算法設計題1.設有一個表頭為first的單鏈表。試設計一個算法，通過遍歷一趟鏈表，將鏈表中所有結點按逆序鏈接。參考答案：解答1template <class Type > void List <Type>: : Tnerse() if (first= NULL )re

23、turn ;ListNode <Type >* p=first link ; , *pr =NULL ;While (p !=NULL ) First f link =pr ;Pr =first ;first =p ;p =pf link;first ->link =pr ;解答2template <class Type > void List <Type>: : Tnerse() ListNode <Type >* p , *head = new ListNode <Type > ();While (first ! = NUL

24、L ) P=first ;first = firstf link;尸 link =head f link ; head f link =p;first = head flink ; delete head ;數據結構模擬卷、單項選擇題1 .數據結構是（）。A. 一種數據類型B.數據的存儲結構C. 一組性質相同的數據元素的集合D.相互之間存在一種或多種特定關系的數據元素的集合2 .算法分析的目的是（）。A.辨別數據結構的合理性B.評價算法的效率C.研究算法中輸入與輸出的關系D.鑒別算法的可讀性3 .在線性表的下列運算中，不改變數據元素之間結構關系的運算是（）。A.插入B.刪除C.排序D.定位4

25、.若進棧序列為1,2, 3, 4, 5, 6,且進棧和出棧可以穿插進行，則可能出現的出棧序列為（）。A. 3, 2, 6, 1, 4, 5C. 1,2, 5, 3, 4, 6B. 3, 4, 2, 1, 6, 5D. 5, 6, 4, 2, 3, 15.設串 sl= " Data Structureswith Java" ,s2= " it ",則子串定位函數index(s1,s2)值為（）。A. 15B. 16C. 17D. 186 .二維數組A89按行優先順序存儲，若數組元素A23的存儲地址為1087, A47的存儲地址為1153,則數組元素A67的

26、存儲地址為（）。A.1207B,1209C.1211D.12137 .在按層次遍歷二叉樹的算法中，需要借助的輔助數據結構是（）。A.隊列B.棧C.線性表D.有序表8 .在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關系（）。A.不一定相同B,都相同C.都不相同D.互為逆序9 .若采用孩子兄弟鏈表作為樹的存儲結構，則樹的后序遍歷應采用二叉樹的（）。A.層次遍歷算法B.前序遍歷算法C.中序遍歷算法D.后序遍歷算法10 .若用鄰接矩陣表示一個有向圖，則其中每一列包含的1的個數為（）。A.圖中每個頂點的入度B.圖中每個頂點的出度C.圖中弧的條數D.圖中連通分量的數目11 .圖的鄰接矩陣表

27、示法適用于表示（）。A.無向圖B.有向圖C.稠密圖D.稀疏圖12 .在對n個關鍵字進行直接選擇排序的過程中，每一趟都要從無序區選出最小關鍵字元 素，則在進行第i趟排序之前，無序區中關鍵字元素的個數為（）。A. iB. i+1C. n-iD. n-i+1二、填空題1 .棧是特殊 的線性表，其運算遵循后進先出 的原則。2 .棧 是限定僅在表尾進行插入或刪除操作的線性表。3 . 一個棧的輸入序列是：1, 2, 3則不可能的棧輸出序列是 3, 1, 2。4 .二叉樹由(1)根節點 ,(2)左子樹, (3)右子樹三個基本單元組成。5 .在二叉樹中，指針 p 所指結點為葉子結點的條件是=p->lch

28、ild=NULL&&p->rchild=NULL 。6 .具有256個結點的完全二叉樹的深度為_9。7 .已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該 樹有 12 個葉子結點。8 .若不考慮基數排序，則在排序過程中，主要進行的兩種基本操作是關鍵字的比較和記錄的移動 。9 .分別采用堆排序， 快速排序，冒泡排序和歸并排序，對初態為有序的表，則最省時間的是冒泡排序 算法，最費時間的是快速排序算法。10 .不受待排序初始序列的影響，時間復雜度為O(M)的排序算法是選擇排序，在排序 算法的最后一趟開始之前， 所有元素都可能不在其最終位置上的排序算

29、法是歸并排序 C三、解答題1 .某廣義表的表頭和表尾均為(a,(b,c),畫出該廣義表的圖形表示。2 .已知二叉樹的先序序列和中序序列分別為HDACBGFE ADCBHFEG(1)畫出該二叉樹；(2)畫出與(1)求得的二叉樹對應的森林。3 .已知帶權圖的鄰接表如下所示，其中邊表結點的結構為：依此鄰接表從頂點 C出發進行深度優先遍歷。(1)畫出由此得到的深度優先生成樹；(2)寫出遍歷過程中得到的從頂點C到其它各頂點的帶權路徑及其長度。參考答案：1.2.頂點C到頂點A的帶權路徑為（C,D,B,A）,其長度為8+20+11=39頂點C到頂點B的帶權路徑為（C,D,B）,其長度為8+20=28頂點C到頂點D的帶權路徑為（C,D）,其長度為8頂點C到頂點E的帶權路徑為（C,D,B,F,E ）,其長度為8+20+9+14=51頂點C到頂點F的帶權路徑為（C,D,B,F ）,其長度為8+20+9=37四、算法設計題1 .已知中序線索二叉樹 T右子樹不空。設計算法，將 S所指的結點作為T的右子樹中的 一個葉子結點插入進去，并使之成為TT的右子樹的（中序序列）第一個結點（同時要修改相應的線索關系）。2 .寫出在中序線索二叉樹里；找指定結點在后序下的前驅結點的算法。 參考答案：1 .答案：題目分析若使新插入的葉子結點 S成T右子樹中序序列的第一個結點，則應在 T 的右子樹中最左面的結