全國自考《數據結構導論》真題及答案解析

1、全國自考數據結構導論真題及答案解析一、單選題 （共30題，共60分） 1.在順序表中查找第 i 個元素，時間效率最高的算法的時間復雜度為（） A.O(1) B.O(n ) C.O(log 2n) D.O(n) 2.樹形結構中，度為0的結點稱為（） A.樹根 B.葉子 C.路徑 D.二叉樹 3.已知有向圖 G=(V ,E)，其中 V=V 1,V2,V 3,V4,V 5,V6,V 7，E= ，則圖 G 的拓撲序列是（） A.V 1,V3,V 4,V6,V 2,V5,V 7 B.V 1,V 3,V2,V6,V4,V5,V 7 C.V1,V3,V 4,V5,V 2,V6,V7 D.V 1,V 2,V5

2、,V 3,V4,V 6,V 7 4.有關圖中路徑的定義，表述正確的是（） A.路徑是頂點和相鄰頂點偶對構成的邊所形成的序列 B.路徑是不同頂點所形成的序列 C.路徑是不同邊所形成的序列 D.路徑是不同頂點和不同邊所形成的集合 5.串的長度是指（） A.串中所含不同字母的個數 B.串中所含字符的個數 C.串中所含不同字符的個數 D.串中所含非空格字符的個數 6.組成數據的基本單位是（） A.數據項 B.數據類型 C.數據元素 D.數據變量 7.程序段的時間復雜度為（） A.O（1）= B.O（n） C.O（n 2 D.O(n 3 ) 8.與串的邏輯結構不同的數據結構是（） A.線性表 B.棧 C

3、.隊列 D.樹 9.二叉樹的第i(i1)層上所擁有的結點個數最多為（） A. B.2i C. D. 10.設單鏈表中指針p指向結點A，若要刪除A的直接后繼，則所需修改指針的操作為（） A.p->next=p->next->next B.p=p->next C.p=p->next->next D.p->next=p 11.下列排序算法中，某一趟結束后未必能選出一個元素放在其最終位置上的是（） A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序 12.設字符串S1=ABCDEFG，S2=PQRST，則運算S=CONCAT(SUBSTR(S1,2,LE

4、NGTH(S2),SUBSTR(S1,LENGTH(S2),2)后S的結果為() A.BCQR B.BCDEF C. BCDEFG D.BCDEFEF 13.在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A，并且A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則使其平衡的調整方法為() A.LL 型 B.LR 型 C.RL 型 D.RR 型 14.如果結點A有3個兄弟結點，而且B為A的雙親，則B的度為（） A.1 B.3 C.4 D.5 15.數據表A中每個元素距其最終位置較近，則最省時間的排序算法是（） A.堆排序 B.插入排序 C.直接選擇排序 D.快速排序 16.在表長

5、為n的順序表上做插入運算，平均要移動的結點數為（） A.n/4 B.n/3 C.n/2 D.n 17.順序表中有19個元素，第一個元素的地址為200，且每個元素占一個字節(jié)，則第14個元素的存儲地址為() A.212 B.213 C.214 D.215 18.由頂點V1，V2，V3構成的圖的鄰接矩陣為，則該圖中頂點V1的出度為(C) A.0 B.1 C.2 D.3 19.元素的進棧次序為 A，B，C，D，E，則退棧中不可能的序列是（） A.A，B，C，D，E B.B，C，D，E，A C.E，A，B，C，D D.E，D，C，B，A 20.由帶權為 9，2，5，7 的四個葉子結點構造一棵哈夫曼樹，

6、該樹的帶權路徑長度為（） A.23 B.37 C.44 D.46 21.在已知尾指針的單循環(huán)鏈表中，插入一個新結點使之成為首結點，其算法的時間復雜度為（） A.O（ 1） B.（log 2n） C.O（ n） D.O(n 2 ) 22.已知一個有序表為(13，18，24，35，47，50，62，83，90，115，134)，當二分查找值為90的元素時，查找成功時需比較的次數為（） A.1 B.2 C.3 D.4 23.在查找順序表各結點概率相等的情況下，順序按值查找某個元素的算法時間復雜度為（） A.O(1) B.O(n) C.O( n ) D.O(log 2n) 24.下列各項鍵值序列中不是

7、堆的為（） A.5 ，23，16，68，94，72，71， 73 B.5 ，16，23，68，94，72，71， 73 C.5 ，23，16，73，94，72，71， 68 D.5 ，23，16，68，73，71，72， 94 25.在線性表的下列存儲結構中進行插入、刪除運算，花費時間最多的是（） A.單鏈表 B.雙鏈表 C.順序表 D.單循環(huán)鏈表 26.在棧中進行插入和刪除操作的一端稱為（） A.棧頂 B.棧底 C.任意位置 D.指定位置 27.用n個值構造一棵二叉排序樹，它的最大高度為 A.n/2 B.n C.n D.log 2n 28.冒泡排序的時間復雜度是（） A.O(n 2 ) B.

8、O(nlog 2n) C.O(n) D.O(log 2n) 29.設無向圖的鄰接表如題14圖所示，則該圖的邊數為（） A.4 B.5 C.10 D.20 30.帶表頭結點鏈隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為（） A.front=rear B.front!=NULL C.rear!=NULL D.front=NULL 二、填空題 （共13題，共26分） 31.下列程序段的時間復雜度為 _ 32.數據的邏輯結構被分為集合結構、 _、樹形結構和圖狀結構 4 種。 33.線性表中所含結點的個數稱為_。 34.向一個棧頂指針為top的鏈棧中插入一個新結點*p時，應執(zhí)行_和

9、top=p操作。 35.設一個順序棧S，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素的退棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為_。 36.若滿二叉樹的結點數為n，則其高度為_。 37.在一棵具有n個結點的完全二叉樹中，從樹根起，自上而下、從左到右地給所有結點編號。若編號為i的結點有父結點，那么其父結點的編號為_。 38.深度為k的二叉樹，結點數最多有_個。 39.某二叉樹的后根遍歷為ABKCBPM，則該二叉樹的根為_。 40.在一個具有n個頂點的無向圖中，頂點的度最大可達_。 41.有向圖G的鄰接矩陣為A，如果圖中存在弧，則Aij的值為_。 42.順序

10、查找算法的平均查找長度為_。 43.二路歸并排序的平均時間復雜度為 _。 1、正確答案： A 2、正確答案： B 3、正確答案： A 4、正確答案： A 5、正確答案： B 6、正確答案： C 7、正確答案： B 8、正確答案： D 9、正確答案： C 10、正確答案： A 11、正確答案： C 12、正確答案： D 13、正確答案： B 14、正確答案： C 15、正確答案： B 16、正確答案： C 17、正確答案： B 18、正確答案： C 19、正確答案： C 20、正確答案： C 21、正確答案： A 22、正確答案： B 23、正確答案： B 24、正確答案： C 25、正確答案： C 26、正確答案： A 27、正確答案： B 28、正確答案： A 29、正確答案： B 30、正確答案： A 31、正確答案：O(n) 32、正