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

全國2013年1月數據結構導論試題

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

  一單項選擇題(本大題共小題每小題分)

  在每小題列出的四個備選項中只有一個是符合題目要求的請將其代碼填寫在題後的括號內錯選多選或未選均無分

  數據的四種基本邏輯結構是指( )

  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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.