全國(guó)自考《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》真題及答案解析

1、全國(guó)自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論真題及答案解析一、單選題 （共30題，共60分） 1.在順序表中查找第 i 個(gè)元素，時(shí)間效率最高的算法的時(shí)間復(fù)雜度為（） A.O(1) B.O(n ) C.O(log 2n) D.O(n) 2.樹(shù)形結(jié)構(gòu)中，度為0的結(jié)點(diǎn)稱(chēng)為（） A.樹(shù)根 B.葉子 C.路徑 D.二叉樹(shù) 3.已知有向圖 G=(V ,E)，其中 V=V 1,V2,V 3,V4,V 5,V6,V 7，E= ，則圖 G 的拓?fù)湫蛄惺牵ǎ?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.有關(guān)圖中路徑的定義，表述正確的是（） A.路徑是頂點(diǎn)和相鄰頂點(diǎn)偶對(duì)構(gòu)成的邊所形成的序列 B.路徑是不同頂點(diǎn)所形成的序列 C.路徑是不同邊所形成的序列 D.路徑是不同頂點(diǎn)和不同邊所形成的集合 5.串的長(zhǎng)度是指（） A.串中所含不同字母的個(gè)數(shù) B.串中所含字符的個(gè)數(shù) C.串中所含不同字符的個(gè)數(shù) D.串中所含非空格字符的個(gè)數(shù) 6.組成數(shù)據(jù)的基本單位是（） A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)類(lèi)型 C.數(shù)據(jù)元素 D.數(shù)據(jù)變量 7.程序段的時(shí)間復(fù)雜度為（） A.O（1）= B.O（n） C.O（n 2 D.O(n 3 ) 8.與串的邏輯結(jié)構(gòu)不同的數(shù)據(jù)結(jié)構(gòu)是（） A.線性表 B.棧 C

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

4、T，則運(yùn)算S=CONCAT(SUBSTR(S1,2,LENGTH(S2),SUBSTR(S1,LENGTH(S2),2)后S的結(jié)果為() A.BCQR B.BCDEF C. BCDEFG D.BCDEFEF 13.在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并且A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則使其平衡的調(diào)整方法為() A.LL 型 B.LR 型 C.RL 型 D.RR 型 14.如果結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)，而且B為A的雙親，則B的度為（） A.1 B.3 C.4 D.5 15.數(shù)據(jù)表A中每個(gè)元素距其最終位置較近，則最省時(shí)間的排序算法是（） A.堆排序 B

5、.插入排序 C.直接選擇排序 D.快速排序 16.在表長(zhǎng)為n的順序表上做插入運(yùn)算，平均要移動(dòng)的結(jié)點(diǎn)數(shù)為（） A.n/4 B.n/3 C.n/2 D.n 17.順序表中有19個(gè)元素，第一個(gè)元素的地址為200，且每個(gè)元素占一個(gè)字節(jié)，則第14個(gè)元素的存儲(chǔ)地址為() A.212 B.213 C.214 D.215 18.由頂點(diǎn)V1，V2，V3構(gòu)成的圖的鄰接矩陣為，則該圖中頂點(diǎn)V1的出度為(C) A.0 B.1 C.2 D.3 19.元素的進(jìn)棧次序?yàn)?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.由帶

6、權(quán)為 9，2，5，7 的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)， 該樹(shù)的帶權(quán)路徑長(zhǎng)度為（） A.23 B.37 C.44 D.46 21.在已知尾指針的單循環(huán)鏈表中，插入一個(gè)新結(jié)點(diǎn)使之成為首結(jié)點(diǎn)，其算法的時(shí)間復(fù)雜度為（） A.O（ 1） B.（log 2n） C.O（ n） D.O(n 2 ) 22.已知一個(gè)有序表為(13，18，24，35，47，50，62，83，90，115，134)，當(dāng)二分查找值為90的元素時(shí)，查找成功時(shí)需比較的次數(shù)為（） A.1 B.2 C.3 D.4 23.在查找順序表各結(jié)點(diǎn)概率相等的情況下，順序按值查找某個(gè)元素的算法時(shí)間復(fù)雜度為（） A.O(1) B.O(n) C.O( n

7、) D.O(log 2n) 24.下列各項(xiàng)鍵值序列中不是堆的為（） 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.在線性表的下列存儲(chǔ)結(jié)構(gòu)中進(jìn)行插入、刪除運(yùn)算，花費(fèi)時(shí)間最多的是（） A.單鏈表 B.雙鏈表 C.順序表 D.單循環(huán)鏈表 26.在棧中進(jìn)行插入和刪除操作的一端稱(chēng)為（） A.棧頂 B.棧底 C.任意位置 D.指定位置 27.用n個(gè)值構(gòu)造一棵二叉排序樹(shù)，它的最大高度為 A.n/2 B.n C.n D.log 2n 2

8、8.冒泡排序的時(shí)間復(fù)雜度是（） A.O(n 2 ) B.O(nlog 2n) C.O(n) D.O(log 2n) 29.設(shè)無(wú)向圖的鄰接表如題14圖所示，則該圖的邊數(shù)為（） A.4 B.5 C.10 D.20 30.帶表頭結(jié)點(diǎn)鏈隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則判斷隊(duì)空的條件為（） A.front=rear B.front!=NULL C.rear!=NULL D.front=NULL 二、填空題 （共13題，共26分） 31.下列程序段的時(shí)間復(fù)雜度為 _ 32.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、 _、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu) 4 種。 33.線性表中所含結(jié)點(diǎn)的個(gè)數(shù)稱(chēng)為_(kāi)。 34.向一個(gè)

9、棧頂指針為top的鏈棧中插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行_和top=p操作。 35.設(shè)一個(gè)順序棧S，元素s1，s2，s3，s4，s5，s6依次進(jìn)棧，如果6個(gè)元素的退棧順序?yàn)閟2，s3，s4，s6，s5，s1，則順序棧的容量至少為_(kāi)。 36.若滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)數(shù)為n，則其高度為_(kāi)。 37.在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，從樹(shù)根起，自上而下、從左到右地給所有結(jié)點(diǎn)編號(hào)。若編號(hào)為i的結(jié)點(diǎn)有父結(jié)點(diǎn)，那么其父結(jié)點(diǎn)的編號(hào)為_(kāi)。 38.深度為k的二叉樹(shù)，結(jié)點(diǎn)數(shù)最多有_個(gè)。 39.某二叉樹(shù)的后根遍歷為ABKCBPM，則該二叉樹(shù)的根為_(kāi)。 40.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，頂點(diǎn)的度最大可達(dá)_。 41.有向圖G的鄰接

10、矩陣為A，如果圖中存在弧，則Aij的值為_(kāi)。 42.順序查找算法的平均查找長(zhǎng)度為_(kāi)。 43.二路歸并排序的平均時(shí)間復(fù)雜度為 _。 1、正確答案： A 本題解析：暫無(wú)解析 2、正確答案： B 本題解析：暫無(wú)解析 3、正確答案： A 本題解析：暫無(wú)解析 4、正確答案： A 本題解析：暫無(wú)解析 5、正確答案： B 本題解析：暫無(wú)解析 6、正確答案： C 本題解析：暫無(wú)解析 7、正確答案： B 本題解析：暫無(wú)解析 8、正確答案： D 本題解析：暫無(wú)解析 9、正確答案： C 本題解析：暫無(wú)解析 10、正確答案： A 本題解析：暫無(wú)解析 11、正確答案： C 本題解析：暫無(wú)解析 12、正確答案： D 本題

11、解析：暫無(wú)解析 13、正確答案： B 本題解析：暫無(wú)解析 14、正確答案： C 本題解析：暫無(wú)解析 15、正確答案： B 本題解析：暫無(wú)解析 16、正確答案： C 本題解析：暫無(wú)解析 17、正確答案： B 本題解析：暫無(wú)解析 18、正確答案： C 本題解析：暫無(wú)解析 19、正確答案： C 本題解析：暫無(wú)解析 20、正確答案： C 本題解析：暫無(wú)解析 21、正確答案： A 本題解析：暫無(wú)解析 22、正確答案： B 本題解析：暫無(wú)解析 23、正確答案： B 本題解析：暫無(wú)解析 24、正確答案： C 本題解析：暫無(wú)解析 25、正確答案： C 本題解析：暫無(wú)解析 26、正確答案： A 本題解析：暫無(wú)解析 27、正確答案： B 本題解析：暫無(wú)解析 28、正確答案： A 本題解析：暫無(wú)解析 29、正確答案： B 本題解析：暫無(wú)解析 30、正確答案： A 本題解析：暫無(wú)解析 31、正確答案： O(n) 32