一單項選擇題(本大題共小題每小題分共分)
在每小題列出的四個備選項中只有一個是符合題目要求的請將其代碼填寫在題後的括號內錯選多選或未選均無分
數據的四種基本邏輯結構是指( )
A數組鏈表樹圖形結構 B線性表鏈表棧隊列數組廣義表
C線性結構鏈表樹圖形結構 D集合線性結構樹圖形結構
數據結構中通常采用兩種方法衡量算法的時間復雜性即( )
A最大時間復雜性和最小時間復雜性
B最好時間復雜性和最壞時間復雜性
C部分時間復雜性和總體時間復雜性
D平均時間復雜性和最壞時間復雜性
下列關於線性表的敘述中不正確的是( )
A線性表是n個結點的有窮序列
B線性表可以為空表
C線性表的每一個結點有且僅有一個前趨和一個後繼
D線性表結點間的邏輯關系是:的聯系
在一個單鏈表中若p所指結點不是最後結點則刪除p所指結點的後繼結點的正確操作是( )
Ap=p>next Bp>next=p>next
Cp>next=p>next>next Dp>next=p
棧和隊列( )
A共同之處在於二者都是先進先出的特殊的線性表
B共同之處在於二者都是先進後出的特殊的線性表
C共同之處在於二者都只允許在頂端執行刪除操作
D沒有共同之處
二維數組A[][]采用按列為主序的存儲方式每個元素占個存儲單元若A[][]的存儲地址是則A[][]的存儲地址是( )
A B
C D
深度為k的二叉樹至多有( )
Ak個結點 Bk個結點
Ck個結點 Dk個結點
對於如圖所示二叉樹采用中根遍歷正確的遍歷序列應為( )
AABCDEF BABECDF
CCDFBEA DCBDAEF
下面關於生成樹的描述中不正確的是( )
A生成樹是樹的一種表現形式
B生成樹一定是連通的
C生成樹一定不含有環
D若生成樹頂點個數為n則其邊數一定為n
圖的鄰接表如下所示從頂點V出發采用深度優先搜索法遍歷該圖則可能的頂點序列 是( )
AVVVVV BVVVVV
CVVVVV DVVVVV
下列查找方法中不屬於動態的查找方法是( )
A二叉排序樹法 B平衡樹法
C散列法 D斐波那契查找法
要解決散列引起的沖突問題常采用的方法有( )
A數字分析法平方取中法
B數字分析法線性探測法
C二次探測法平方取中法
D二次探測法鏈地址法
用於外存儲器的數據組織結構散列文件主要適用於( )
A順序存取 B隨機存取
C索引存取 D以上三種都可以
堆排序屬於一種選擇排序其時間復雜性為( )
AO() BO(nlogn)
CO(n) DO(n)
下列排序方法中屬於不穩定的排序方法是( )
A直接插入排序法 B冒泡排序法
C基數排序法 D歸並排序法
二填空題(本大題共小題每小題分共分)
請在每小題的空格中填上正確答案錯填不填均無分
根據不同的描述方式對數據的操作運算通常可分為加工型運算和__________兩種基本類型
數據結構中的算法通常采用最壞時間復雜度和____________兩種方法衡量其效率
判斷帶頭結點head的單鏈表為空的條件是___________
若順序表每個元素長度均為其中第一個元素的存儲地址為則第個元素的存儲地址為___________
若front和rear分別表示循環隊列Q的頭指針和尾指針m表示該隊列的最大容量則判斷循環隊列為滿的條件是___________
對於順序存儲結構的二維數組通常采用___________兩種存放方式存儲數據元素
若某二叉樹的先根遍歷序列為CEDBA中根遍歷序列為DEBAC則其後根遍歷序列為___________
具有n個結點的完全二叉樹其深度為___________
圖主要采用___________兩種存儲結構存放
索引順序查找通常分兩個階段進行首先采用順序查找法或二分法確定所要查找的塊然後再用___________法在塊中找到具體的元素值
二叉排序樹是一種特殊的有序表若要保證輸出序列其鍵值完全按遞增排列則應對二叉排序樹采用___________法遍歷
文件常見的存儲結構有順序文件鏈接文件 索引文件和___________四種
在各種內部排序中占用存儲空間較大的排序通常是___________排序
三應用題(本大題共小題每小題分共分)
已知某二叉樹的順序存儲結構如圖所示試畫出該二叉樹
A
B
C
D
E
F
G
試用Prim算法構造下圖的最小生成樹要求分步給出構造過程
已知散列函數為H(key)=key%散列表長度為(散列地址空間為)待散列序列為()要求
()根據以上條件構造一散列表並用線性探測法解決有關地址沖突;
()若要用該散列表查找元素給出所需的比較次數
已知一組鍵值序列為()試采用快速排序法對該組序列作升序排序並給出每一趟的排序結果
已知一組鍵值序列()試采用二路歸並排序法對該組序列作升序排序並給出每一趟的排序結果
四設計題(本大題共小題每小題分共分)
試編寫一算法以完成在帶頭結點單鏈表L中第i個位置前插入元素X的操作
二叉樹是由所有度數不大於的結點構成的一種特定樹若某結點度為則該結點有左右兩個孩子請編寫算法計算一二叉樹所有度數為的結點個數
From:http://tw.wingwit.com/Article/program/sjjg/201311/23379.html
