《數(shù)據(jù)結(jié)構(gòu)》期末考試卷 -B卷

1、-作者xxxx-日期xxxx數(shù)據(jù)結(jié)構(gòu)期末考試卷 -B卷【精品文檔】東莞理工學(xué)院城市學(xué)院（本科）試卷（B卷）2016 -2017 學(xué)年第二學(xué)期開課單位： 計(jì)信系 ，考試形式： 閉 卷，允許帶 入場(chǎng)科目： 數(shù)據(jù)結(jié)構(gòu) 班級(jí)：15級(jí)軟件工程16班，姓名： 學(xué)號(hào)： 題序一二三四總 分得分評(píng)卷人一、填空題（每題2分，共12分）1、 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中基本存儲(chǔ)方式有 結(jié)構(gòu)和 結(jié)構(gòu) 。2、棧(又稱為堆棧)是操作受限的線性結(jié)構(gòu)，其操作的基本原則是 ，插入和刪除元素的一端稱為 。3、深度為k（根的深度為1）的完全二叉樹至少有_ _個(gè)結(jié)點(diǎn)，至多有 _ _個(gè)結(jié)點(diǎn)。4、 對(duì)于一個(gè)有n個(gè)頂點(diǎn)的完全無向圖，具有 條邊；而對(duì)

2、于一個(gè)有n個(gè)頂點(diǎn)的完全有向圖，具有 條弧。5、 在進(jìn)行排序時(shí)，最基本的操作是 和 。6、 哈希函數(shù)是一種映象，是從 到 的一種映象。二、單項(xiàng)選擇題（請(qǐng)將答案寫在題目后的括號(hào)中。每題2分，共40分）1、 下面結(jié)構(gòu)中，不屬于數(shù)據(jù)邏輯結(jié)構(gòu)的是（ ）。（A） 線性鏈表 （B） 樹形結(jié)構(gòu) （C） 線性結(jié)構(gòu) （D） 網(wǎng)狀結(jié)構(gòu)2、 下面說法正確的是（ ）。（A） 數(shù)據(jù)元素是數(shù)據(jù)的最小單位 （B） 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位（C） 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合（D） 上述說法都是錯(cuò)誤的3、 有下列算法，其時(shí)間復(fù)雜度是（ ）。x=1 ;while (xnext=q-next；free(p) ; （B） p-n

3、ext=q-next；free(q) ;（C） q-next=p-next；free(p) ; （D） q-next=p-next；free(q) ; 6、 棧和隊(duì)列的共同點(diǎn)時(shí)（ ）。（A） 都是先進(jìn)先出 （B） 都是后進(jìn)先出（C） 只允許在端點(diǎn)處插入和刪除元素 （D） 沒有共同點(diǎn)7、 設(shè)有一個(gè)棧頂指針為top的順序棧S，top為0時(shí)表示?？眨瑒t向堆棧S中壓入一個(gè)元素x執(zhí)行的操作是（ ）。（A） Stop+=x； （B） S+top=x；（C） S-top=x； （D） Stop-=x； 8、 設(shè)循環(huán)隊(duì)列Q的最多元素個(gè)數(shù)為m，隊(duì)尾指針是rear，隊(duì)首指針是front，則隊(duì)列為滿的條件是（ ）。

4、（A） Q.rear=Q.front ； （B） Q.rear!=Q.front ；（C） (Q.rear+1)%m!=Q.front； （D） (Q.rear+1)%m=Q.front；9、 廣義表(a),(b),c),(d,e),(a,b)的長(zhǎng)度是 ，深度是 。（ ）（A） 4, 4 （B） 4, 5 （C） 3, 5 （D） 3, 410、有一個(gè)12階下三角矩陣A，上三角的所有元素均為0， A00的地址是BA，若每個(gè)元素占3個(gè)存儲(chǔ)單元，采用行優(yōu)先壓縮存儲(chǔ)，則A65的地址是（ ）。（A） BA+75 （B） BA+78 （C） BA+81 （D） BA+8411、 在二叉樹中，指針P所指的

5、結(jié)點(diǎn)是非葉子結(jié)點(diǎn)的條件是（ ）。（A） P-Lchild =NULL& P-Rchild=NULL ； （B） P-Lchild !=NULL& P-Rchild !=NULL ；（C） P-Lchild =NULL &P-Rchild !=NULL ； （D） P-Lchild !=NULL |P-Rchild !=NULL ；12、 將一棵一般的樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 （ ）。（A） 唯一的 （B） 有多種，但根結(jié)點(diǎn)都沒有左子結(jié)點(diǎn)（C） 有多種 （D） 有多種，但根結(jié)點(diǎn)都沒有右子結(jié)點(diǎn)13、 設(shè)由n（n2）個(gè)權(quán)值都互不相同的字符構(gòu)成的哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是 （ ）

6、。（A） 該樹一定是一棵完全二叉樹（B） 樹中一定沒有度為1的結(jié)點(diǎn)（C） 樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)（D） 樹中任一非葉子結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值14、 以下描述中，關(guān)于無向圖鄰接矩陣的特性不正確的是（ ）。（A） 鄰接矩陣是對(duì)稱方陣。（B） 若頂點(diǎn)vi在頂點(diǎn)數(shù)組中的存儲(chǔ)位置為i，則其度數(shù)是第i行的非0元素的個(gè)數(shù)。（C） 無向圖的邊數(shù)是上(或下)三角形矩陣中非0元素個(gè)數(shù)。（D）圖的度是矩陣中非0元素個(gè)數(shù)。15、 對(duì)于有向圖，下述關(guān)于圖、頂點(diǎn)的度、入度、出度的論述中，錯(cuò)誤的是（ ）。（A） 頂點(diǎn)的度是頂點(diǎn)的入度、出度之和（B） 圖的度是圖的入度、出度之和（C） 頂點(diǎn)的入

7、度等于頂點(diǎn)的出度（D） 圖的入度等于圖的出度16、 對(duì)于有n個(gè)頂點(diǎn)e(en)條邊的帶權(quán)無向圖，以下關(guān)于該圖的最小生成樹的描述正確的是（ ）。（A） 最小生成樹是唯一的。（B） 最小生成樹中所有邊上的權(quán)值之和是唯一的。（C） 最小生成樹有n條邊。（D） 最小生成樹有n個(gè)頂點(diǎn)e-1條邊。17、 適用于折半查找的表的存儲(chǔ)方式以及元素排列要求是（ ）。（A）順序存儲(chǔ)方式，元素有序 （B）順序存儲(chǔ)方式，元素?zé)o序（C） 鏈接存儲(chǔ)方式，元素?zé)o序 （D）鏈接存儲(chǔ)方式，元素有序18、 采用線性探測(cè)法解決沖突，可能要探測(cè)多個(gè)位置，在查找成功的情況下，所探測(cè)的這些位置上的關(guān)鍵字（ ）。（A） 不一定都是同義詞 （B

8、） 一定都是同義詞 （C） 一定都不是同義詞 （D） 都相同19、 從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（ ）。（A） 歸并排序 （B） 冒泡排序 （C） 選擇排序 （D） 插入排序20、 若一組記錄的排序碼為（46，79，56，38，40，84），則采用快速排序法，以第一個(gè)記錄為基準(zhǔn)得到的依次劃分結(jié)果是（ ）。（A） 38，40，46，56，79，84 （B） 40，38，46，79，56，84 （C） 40，38，46，56，79， 84 （D） 40，38，46，84，56，79三、分析題（每題8分，

9、共40分）1、 設(shè)有一棵二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下。 畫出該二叉樹 ； 分別寫出該二叉樹的中序遍歷序列和后序遍歷序列； A B C D E F G H I J K L M1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 232、 若以7, 9, 13, 6, 5, 3, 17, 10作為葉子結(jié)點(diǎn)的權(quán)值，請(qǐng)構(gòu)造對(duì)應(yīng)的Huffman樹，然后求出其帶權(quán)路徑長(zhǎng)度WPL。3、 設(shè)有帶權(quán)的無向圖的順序存儲(chǔ)結(jié)構(gòu)如下： 畫出該圖； 給出用普里姆(Prime)算法從頂點(diǎn)V2出發(fā)的最小生成樹。vexs012345V0V1V2V3V4V5 5 3 5 6

10、 3 3 6 4 8 10 4 5 3 8 7 10 5 7 4、 將關(guān)鍵字序列（29，33，23，43，38，27，31，25，21）依次插入到初態(tài)為空的二叉排序樹中，請(qǐng)畫出所得到的樹T；然后畫出刪除23之后的二叉排序樹T1；最后再畫出在T1中插入23之后的二叉排序樹T2。5、 線性表的關(guān)鍵字集合31，25，18，29，42，36，73，53，17，16，47，94，43，共有13個(gè)元素，已知散列函數(shù)為：H（key） = key MOD 11，采用鏈地址法處理沖突，請(qǐng)給出對(duì)應(yīng)的散列表結(jié)構(gòu)。四、編寫算法（8分）設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義如下，試寫一個(gè)函數(shù)Delete_linkList實(shí)現(xiàn)通過一趟遍歷刪除以L為頭結(jié)點(diǎn)的單鏈表中值在x到y(tǒng)(x的大小