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

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

2、本的操作是 和 。6、 哈希函數(shù)是一種映象，是從 到 的一種映象。二、單項選擇題（請將答案寫在題目后的括號中。每題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ù)項是數(shù)據(jù)的基本單位（C） 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合（D） 上述說法都是錯誤的3、 有下列算法，其時間復(fù)雜度是（ ）。x=1 ;while (xnext=q-next；free(p) ; （B） p-next=q-next；free(q) ;（C） q-next=p-

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

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

5、L& 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é)點都沒有左子結(jié)點（C） 有多種 （D） 有多種，但根結(jié)點都沒有右子結(jié)點13、 設(shè)由n（n2）個權(quán)值都互不相同的字符構(gòu)成的哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是 （ ）。（A） 該樹一定是一棵完全二叉樹（B） 樹中一定沒有度為1的結(jié)點

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

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

8、 從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（ ）。（A） 歸并排序 （B） 冒泡排序 （C） 選擇排序 （D） 插入排序20、 若一組記錄的排序碼為（46，79，56，38，40，84），則采用快速排序法，以第一個記錄為基準(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分，共40分）1、 設(shè)有一棵二叉樹的順序存儲結(jié)構(gòu)如下。 畫出該二叉樹

9、； 分別寫出該二叉樹的中序遍歷序列和后序遍歷序列； 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é)點的權(quán)值，請構(gòu)造對應(yīng)的Huffman樹，然后求出其帶權(quán)路徑長度WPL。3、 設(shè)有帶權(quán)的無向圖的順序存儲結(jié)構(gòu)如下： 畫出該圖； 給出用普里姆(Prime)算法從頂點V2出發(fā)的最小生成樹。vexs012345V0V1V2V3V4V5 5 3 5 6 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)為空的二叉排序樹中，請畫出所得到的樹T；然后畫出刪除23之后的二叉排序樹T1；最后再畫出在T1中插入23之后的二叉排序樹T2。5、 線性表的關(guān)鍵字集合31，25，18，29，42，36，73，53，17，16，47，94，43，共有13個元素，已知散列函數(shù)為：H（key） = key MOD 11，采用鏈地址法處理沖突，請給出對應(yīng)的散列表結(jié)構(gòu)。四、編寫算法（8分）設(shè)單鏈表的結(jié)點結(jié)構(gòu)定義如下，試寫一個函數(shù)Delete_linkList實現(xiàn)通過一趟遍歷刪除以L為頭結(jié)點的單鏈表中值在x到y(tǒng)(x