數(shù)據(jù)結(jié)構(gòu)期末考卷12-13級(jí)

數(shù)據(jù)結(jié)構(gòu)期末考卷1213級(jí)一、選擇題（每題2分，共20分）1.下列關(guān)于線性表的說(shuō)法中，正確的是（）A.線性表中的元素必須具有相同的類型B.線性表中的元素必須按照順序存儲(chǔ)C.線性表中的元素可以通過(guò)下標(biāo)直接訪問(wèn)D.線性表中的元素個(gè)數(shù)是固定的2.下列關(guān)于棧的說(shuō)法中，正確的是（）A.棧是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)B.棧只能通過(guò)棧頂元素進(jìn)行操作C.棧的插入和刪除操作都在棧底進(jìn)行D.棧的刪除操作叫做入棧3.下列關(guān)于隊(duì)列的說(shuō)法中，正確的是（）A.隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)B.隊(duì)列的插入操作叫做入隊(duì)，刪除操作叫做出隊(duì)C.隊(duì)列的刪除操作在隊(duì)頭進(jìn)行，插入操作在隊(duì)尾進(jìn)行D.隊(duì)列的元素可以通過(guò)下標(biāo)直接訪問(wèn)4.下列關(guān)于二叉樹(shù)的性質(zhì)中，正確的是（）A.二叉樹(shù)的每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)B.二叉樹(shù)的每個(gè)節(jié)點(diǎn)至少有一個(gè)子節(jié)點(diǎn)C.二叉樹(shù)的葉子節(jié)點(diǎn)都在同一層D.二叉樹(shù)的每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)5.下列關(guān)于圖的存儲(chǔ)方式中，正確的是（）A.鄰接矩陣是一種順序存儲(chǔ)方式B.鄰接表是一種鏈?zhǔn)酱鎯?chǔ)方式C.鄰接矩陣和鄰接表都可以用于存儲(chǔ)有向圖和無(wú)向圖D.鄰接矩陣和鄰接表都不能用于存儲(chǔ)帶權(quán)圖6.下列關(guān)于排序算法的說(shuō)法中，正確的是（）A.冒泡排序是一種穩(wěn)定的排序算法B.選擇排序是一種不穩(wěn)定的排序算法C.插入排序的時(shí)間復(fù)雜度是O(n^2)D.快速排序的時(shí)間復(fù)雜度是O(nlogn)7.下列關(guān)于查找算法的說(shuō)法中，正確的是（）A.順序查找的時(shí)間復(fù)雜度是O(n)B.折半查找的時(shí)間復(fù)雜度是O(nlogn)C.折半查找必須基于有序表進(jìn)行D.哈希查找的時(shí)間復(fù)雜度是O(1)8.下列關(guān)于二叉搜索樹(shù)的說(shuō)法中，正確的是（）A.二叉搜索樹(shù)是一種有序樹(shù)B.二叉搜索樹(shù)的每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)C.二叉搜索樹(shù)的左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值D.二叉搜索樹(shù)的右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值9.下列關(guān)于平衡二叉樹(shù)的說(shuō)法中，正確的是（）A.平衡二叉樹(shù)是一種特殊的二叉搜索樹(shù)B.平衡二叉樹(shù)的每個(gè)節(jié)點(diǎn)的左右子樹(shù)高度差不超過(guò)1C.平衡二叉樹(shù)的插入和刪除操作的時(shí)間復(fù)雜度都是O(n)D.平衡二叉樹(shù)可以用于實(shí)現(xiàn)字典和集合數(shù)據(jù)結(jié)構(gòu)10.下列關(guān)于B樹(shù)的說(shuō)法中，正確的是（）A.B樹(shù)是一種平衡多路查找樹(shù)B.B樹(shù)的每個(gè)節(jié)點(diǎn)都包含多個(gè)關(guān)鍵字和多個(gè)子節(jié)點(diǎn)C.B樹(shù)的每個(gè)節(jié)點(diǎn)都包含一個(gè)指向父節(jié)點(diǎn)的指針D.B樹(shù)的插入和刪除操作的時(shí)間復(fù)雜度都是O(logn)二、填空題（每題2分，共20分）1.在線性表中，第一個(gè)元素的位置稱為_(kāi)_______。2.在棧中，允許插入和刪除的一端稱為_(kāi)_______。3.在隊(duì)列中，允許插入的一端稱為_(kāi)_______，允許刪除的一端稱為_(kāi)_______。4.一個(gè)非空二叉樹(shù)的第i層上至多有________個(gè)節(jié)點(diǎn)。5.在一棵二叉樹(shù)中，度為0的節(jié)點(diǎn)總是比度為2的節(jié)點(diǎn)多一個(gè)，這棵二叉樹(shù)的節(jié)點(diǎn)數(shù)是________。6.在無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為_(kāi)_______。7.在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條邊，則稱該圖為_(kāi)_______。8.在鄰接矩陣中，如果頂點(diǎn)i和頂點(diǎn)j之間有邊，則矩陣的第i行第j列的值為_(kāi)_______。9.在鄰接表中，每個(gè)頂點(diǎn)都對(duì)應(yīng)一個(gè)鏈表，鏈表的每個(gè)節(jié)點(diǎn)都包含一個(gè)頂點(diǎn)的________。10.在哈希表中，解決沖突的方法有________和________。三、簡(jiǎn)答題（每題10分，共30分）1.簡(jiǎn)述線性表、棧和隊(duì)列的特點(diǎn)和區(qū)別。2.簡(jiǎn)述二叉一、選擇題答案1.A2.B3.A4.A5.A6.C7.B8.D9.A10.A二、填空題答案1.第一個(gè)元素的位置稱為頭結(jié)點(diǎn)。2.允許插入和刪除的一端稱為棧頂。3.允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。4.第i層上至多有2^(i1)個(gè)節(jié)點(diǎn)。5.節(jié)點(diǎn)數(shù)是2^(n+1)1。6.完全圖。7.完全無(wú)向圖。8.1。9.鄰接點(diǎn)。10.開(kāi)放地址法和鏈地址法。三、簡(jiǎn)答題答案1.線性表的特點(diǎn)是元素有序排列，可以通過(guò)下標(biāo)訪問(wèn)，長(zhǎng)度可變；棧的特點(diǎn)是后進(jìn)先出，只能在棧頂進(jìn)行操作；隊(duì)列的特點(diǎn)是先進(jìn)先出，在隊(duì)頭刪除，隊(duì)尾插入。2.二叉樹(shù)的特點(diǎn)是每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)，分別為左子樹(shù)和右子樹(shù)。二叉搜索樹(shù)的特點(diǎn)是左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值，右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值。3.哈希表是通過(guò)哈希函數(shù)將鍵映射到表中的一個(gè)位置來(lái)訪問(wèn)數(shù)據(jù)，解決沖突的方法有開(kāi)放地址法和鏈地址法。散列表的特點(diǎn)是查找速度快，但是空間利用率低，適合快速查找和插入刪除操作。1.線性表、棧和隊(duì)列：考查了線性表、棧和隊(duì)列的基本概念和特點(diǎn)，以及它們之間的區(qū)別。2.二叉樹(shù)和圖：考查了二叉樹(shù)的基本概念和性質(zhì)，以及圖的基本概念和存儲(chǔ)方式。3.查找和排序：考查了哈希表的基本概念和解決沖突的方法，以及排序算法的基本思想和時(shí)間復(fù)雜度。4.數(shù)據(jù)結(jié)構(gòu)的應(yīng)用：考查了數(shù)據(jù)結(jié)構(gòu)在實(shí)際問(wèn)題中的應(yīng)用，如二叉搜索樹(shù)和平衡二叉樹(shù)在查找和排序中的應(yīng)用。各題型所考察學(xué)生的知識(shí)點(diǎn)詳解及示例：1.選擇題：考查了學(xué)生對(duì)基本概念和性質(zhì)的理解，需要學(xué)生掌握線性表、棧、隊(duì)列、二叉樹(shù)、圖、哈希表等基本數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和性質(zhì)。2.填空題：考查了學(xué)生對(duì)基本概念的掌握，