2023年自考-自考專業(計算機信息管理)-數據結構導論筆試歷年高頻考點試題附答案（圖片大小可任意調節）第1卷一.單選題(共10題)1.數據表A中每個元素距其最終位置較近，則最省時間的排序算法是（）A.堆排序B.插入排序C.直接選擇排序D.快速排序2.有關圖中路徑的定義，表述正確的是（）A.路徑是頂點和相鄰頂點偶對構成的邊所形成的序列B.路徑是不同頂點所形成的序列C.路徑是不同邊所形成的序列D.路徑是不同頂點和不同邊所形成的集合3.冒泡排序的時間復雜度是（）A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)4.順序表中有19個元素，第一個元素的地址為200，且每個元素占一個字節，則第14個元素的存儲地址為()A.212B.213C.214D.2155.在線性表的下列存儲結構中進行插入、刪除運算，花費時間最多的是（）A.單鏈表B.雙鏈表C.順序表D.單循環鏈表6.設單鏈表中指針p指向結點A，若要刪除A的直接后繼，則所需修改指針的操作為（）A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p7.下列排序算法中，某一趟結束后未必能選出一個元素放在其最終位置上的是（）A.堆排序B.冒泡排序C.直接插入排序D.快速排序8.已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={}，則圖G的拓撲序列是（）A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V79.在已知尾指針的單循環鏈表中，插入一個新結點使之成為首結點，其算法的時間復雜度為（）A.O（1）B.（log2n）C.O（n）D.O(n2)10.已知一個有序表為(13，18，24，35，47，50，62，83，90，115，134)，當二分查找值為90的元素時，查找成功時需比較的次數為（）A.1B.2C.3D.4二.填空題(共5題)1.二路歸并排序的平均時間復雜度為________。2.向一個棧頂指針為top的鏈棧中插入一個新結點*p時，應執行_____和top=p操作。3.有向圖G的鄰接矩陣為A，如果圖中存在弧，則A[i][j]的值為________。4.深度為k的二叉樹，結點數最多有_______個。5.數據的邏輯結構被分為集合結構、________、樹形結構和圖狀結構4種。第2卷一.單選題(共10題)1.二叉樹的第i(i≥1)層上所擁有的結點個數最多為（）A.B.2iC.D.2.由帶權為9，2，5，7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為（）A.23B.37C.44D.463.與串的邏輯結構不同的數據結構是（）A.線性表B.棧C.隊列D.樹4.用n個值構造一棵二叉排序樹，它的最大高度為A..n/2B.nC.√nD.log2n5.在順序表中查找第i個元素，時間效率最高的算法的時間復雜度為（）A.O(1)B.O(√n)C.O(log2n)D.O(n)6.如果結點A有3個兄弟結點，而且B為A的雙親，則B的度為（）A.1B.3C.4D.57.下列各項鍵值序列中不是堆的為（）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}8.設字符串S1=″ABCDEFG″，S2=″PQRST″，則運算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的結果為()A.″BCQR″B.″BCDEF″C.″BCDEFG″D.″BCDEFEF″9.樹形結構中，度為0的結點稱為（）A.樹根B.葉子C.路徑D.二叉樹10.在查找順序表各結點概率相等的情況下，順序按值查找某個元素的算法時間復雜度為（）A.O(1)B.O(n)C.O(√n)D.O(log2n)二.填空題(共5題)1.某二叉樹的后根遍歷為ABKCBPM，則該二叉樹的根為________。2.下列程序段的時間復雜度為________3.線性表中所含結點的個數稱為________。4.順序查找算法的平均查找長度為________。5.設一個順序棧S，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素的退棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為_______。第1卷參考答案一.單選題1.參考答案：B2.參考答案：A3.參考答案：A4.參考答案：B5.參考答案：C6.參考答案：A7.參考答案：C8.參考答案：A9.參考答案：A10.參考答案：B二.填空題1.參考答案：O(nlog2n)2.參考答案：P—>next=top3.參考答案：14.參考答案：2k_-15.參考答案：線性結構第2卷參考答案一.單選題1.參考答案：C2.參考答案：C3.參考答案：D4.參考答案：B5.參考答案：A6.參考答案：C7.參考答案：C8.參考答案：D9.