熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

2013年(下)數據結構試卷

2013-11-15 15:25:57  來源: 數據結構 

  一單項選擇題(在每小題列出的四個備選答案中選出一個正確的答案並將其號碼填在題干的括號內每小題分)

  下列有關線性表的敘述中正確的是( )

  A線性表中的元素之間隔是線性關系

  B線性表中至少有一個元素

  C線性表中任何一個元素有且僅有一個直接前趨

  D線性表中任何一個元素有且僅有一個直接後繼

  下列關於串的敘述中正確的是( )

  A一個串的字符個數即該串的長度

  B一個串的長度至少是

  C空串是由一個空格字符組成的串

  D兩個串S和S若長度相同則這兩個串相等

  

  以數組Q[m ]存放循環隊列中的元素變量rear和qulen分別指示循環隊列中隊尾元素的實際位置和

  當前隊列中元素的個數隊列第一個元素的實際位置是( )

  Arear qulen

  Brear qulen + m

  Cm qulen

  D +(rear + m qulen)mod m

  高二叉樹根結點的層次為所有含有個結點的二叉樹中最小高度是( )

  A

  B

  C

  D

  設結點x和結點y是二叉樹T中的任意兩個結點若在先根序列中x在y之前而在後根序列中x在y之後則x和y的關系是( )

  Ax是y的左兄弟

  Bx是y的右兄弟

  Cx是y的祖先

  Dx是y的後代

  下列四種排序方法中不穩定的方法是( )

  A直接插入排序

  B冒泡排序

  C歸並排序

  D直接選擇排序

  設有一個長度為的已排好序的表用二分查找進行查找若查找不成功至少比較( )次

  A

  B

  C

  D

  一棵二叉排序樹T用( )方法進行遍歷可以得到各結點鍵值的遞增序列

  A先根遍歷

  B中根遍歷

  C層次遍歷

  D後根遍歷

  

  二判斷題(判斷下列各題是否正確正確的在括號內打錯誤的打×每小題分)

  數據的機內表示稱為數據的存儲結構( )

  線性表的鏈接存儲表中元素的邏輯順序與物理順序一定相同( )

  二叉樹中任何一個結點的度都是( )

  由二叉樹結點的先根序列的後根序列可以唯一地確定一棵二叉樹( )

  一個無向圖的鄰接矩陣中各元素之和與圖中邊的條數相等( )

  用直接選擇排序方法分別對序列S=()和序列S=()

  進行排序兩者的比較次數不相同( )

  一棵哈夫曼樹中不存在度為的結點( )

  用二分查找法對一個順序表進行查找這個順序表可以是按各鍵值排好序的也可以是沒有按鍵值排好序的( )

  順序文件適宜順序存取不適宜隨機存取( )

  平衡二叉排序樹上任何一個結點的左右子樹的高度之差的絕對值不大於( )

  三填空題(每空分)

  一個n×n的下三角矩陣A中的元素aij(i≥j≤ij≤n)按行存於一個一維數組B[n(n

  +)/]中對其中的任一元素aij若在B中的位置為k則k=____________

  含有個結點的樹有____________條邊

  一棵二叉樹有個結點這些結點的度要麼是要麼是這棵二叉樹中度為的結點有_________個

  在一個無環有向圖G中若存在一條從頂點i到頂點j的弧則在頂點的拓撲序列中頂點i與頂點j的先後次序是____________

  在一個無向圖的鄰接表中若表結點的個數是m則圖中邊的條數是____________條

  設一個閉散列表的容量為m用線性控測法解決沖突要插入一個鍵值若插入成功至多要進行____________次比較

  設一棵二叉樹結點的先根序列為ABDECFGH中根序列為DEBAFCHG則二叉樹中葉子結點是____________

  一棵哈夫曼樹有個結點則其葉子結點的個數是____________

  將兩個長度分別m和n(m>n)的排好序的表歸並成一個排好序的表至少要進行____________次鍵值比較

  設二維數組M:array[]of integer每個元素(整數)占個存儲單元元素按行的順序存儲數組的起始地址為元素M[]的地址是____________

  線性表L=(aaan)采用順序存儲假定在不同的n

  + 個位置上插入的概率相同則插入一個新元素平均需要移動的元素個數是____________

  設棧S和隊列Q的初始狀態皆為空元素aaaaa和a依次通過一個棧一個元素出棧後即進入隊列Q個元素出隊列的順序是aaaaaa則棧S至少應該容納____________個元素

  兩個序列如下

  L={}

  L={}

  用冒泡排序方法分別對序列L和L進行排序交換次序較少的是序列____________

  將一棵有個結點的完全二叉樹從根結點開始由根向下每一層從左至右順序地存儲在一個一維

  數組bt[]中這棵二叉樹最下面一層上最左邊一個結點存儲在數組元素____________中

  一個索引文件由____________兩部分組成

  四應用題(共分)

  

  初始輸入序列的鍵值如下

  ()

  試采用二路歸並排序法進行從小到大的排序寫出該序列在每遍掃描時的合並過程(分)

  

  

  五設計題(共分)

  修改冒泡排序法以實現雙向冒泡排序即第一次把最大記錄放到表尾第二次將最小記錄放到表頭如此反復進行直至排序結束試編寫此算法(分)

  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23399.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.