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

數據結構筆試題

2022-06-13   來源: 數據結構 

第一部分 選擇題

單項選擇題(本大題共小題每小題分)在每小題列出的四個選項中只有一個選項是符合題目要求的請將正確選項前的字母填在題後的括號內

算法分析的目的是( ? C? )

A找出數據結構的合理性 B研究算法中的輸入/輸出關系

C分析算法的效率以求改進 D分析算法的易讀性

在需要經常查找結點的前驅與後繼的場合中使用(? B )比較合適

A單鏈表 B雙鏈表

C順序表 D循環鏈表

下面關於線性表的敘述中錯誤的為(? D ? )

A順序表使用一維數組實現的線性表

B順序表必須占用一片連續的存儲單元

C順序表的空間利用率高於鏈表

D在鏈表中每個結點只有一個鏈域

帶頭結點的單鏈表head為空的判斷條件是( B )

A head=NIL ? B head>next=NIL

C head>next=head ? D head< >NIL

隊列通常采用兩種存儲結構是( A )

A順序存儲結構和鏈表存儲結構 B散列方式和索引方式

C鏈表存儲結構和數組 D線性存儲結構和非線性存儲結構

按照二叉樹的定義具有個結點的二叉樹有(? C? )種

A ? B ? C ? D

二叉樹的結構如下圖所示其中序遍歷的序列為( ? )

Aabdgcefh

Bdgbaechf

Cgdbehfca

Dabcdefgh

深度為的二叉樹至多有(? C? )個結點 (^M)

A ? B ? C ? D

對於一個具有n個頂點的無向圖若采用鄰接表表示則存放表頭結點的數組的大小為 (? A? )

An ? Bn+ ? Cn ? Dn+邊數

在一個具有n個頂點的無向圖中要連通全部頂點至少需要(? C? )條邊

An ? Bn+ ? Cn ? Dn/

靜態查找表與動態查找表二者的根本差別在於(? B? )

A它們的邏輯結構不一樣

B施加在其上的操作不同

C所包含的數據元素的類型不一樣

D存儲實現不一樣

散列文件使用散列函數將記錄的關鍵字值計算轉化為記錄的存放地址因為散列函數不是一對一的關系所以選擇好的( ?D? )方法是散列文件的關鍵

A散列函數 ? B除余法中的質數

C沖突處理 ? D散列函數和沖突處理

對於大文件的排序要研究在外設上的排序技術即( C? )

A快速排序法 ? B內排序法

C外排序法 ? D交叉排序法

設有個無序的元素希望用最快的速度挑選出其中前個最大的元素最好選用(? C? )法

A冒泡排序 B快速排序

C堆排序 D基數排序

判斷題(判斷下列各題正確的在題干後面括號內打錯誤的打×每小題分)

所謂數據的邏輯結構指的是數據元素之間的邏輯關系( ? )

在線性結構中每個結點都有一個直接前驅和一個直接後繼( ? )

插入和刪除是數組的兩種基本操作( ? )

在鏈棧的頭部必須要設置頭結點( ? )

在二叉樹中插入結點則該二叉樹便不再是二叉樹( ? )

查找表的邏輯結構是集合( ? )

靜態查找表的檢索與修改被分成兩個不交叉的階段分別進行( ? )

在索引順序文件中插入新的記錄時必須復制整個文件( ? )

如果某種排序算法是不穩定的則該方法沒有實際的應用價值( ? )

對於n個記錄的集合進行冒泡排序在最壞情況下所需要的時間是(n)( ? )

填空題(每小題分)

程序設計的實質是________和________

設由字符串a=′data′b=′structure′c=′則a與c連接然後與b連接的結果為________

通常單鏈表的頭結點指的是________單鏈表的首結點指的是________

一個隊列的入隊序列是abcd則隊列的輸出序列為________

棧結構通常采用的兩種存儲結構是________和________

具有N個結點的完全二叉樹的深度為________

樹的三種主要的遍歷方法是________________和層次遍歷

在無向圖的鄰接矩陣A中若A〔ij〕等於則A〔ji〕等於________

采用散列技術實現散列表時需要考慮的兩個主要問題是構造________和解決________

索引順序表上的查找分兩個階段()________()________

散列文件中的記錄通常是成組存放的若干的記錄組成一個存儲單位稱作________

就文件而言按用戶的觀點所確定的基本存儲單元稱為________按外設的觀點所確定的基本存儲單元稱為________

文件的檢索有三種方式________存取________存取和按關鍵字存取

最簡單的交換排序方法是________排序

外排序的基本方法是________

應用題(每小題分)

假定在學生的檔案中含有姓名學號年齡性別如采用線性表作為數據結構來實現檔案管理問題分別給出線性表的在順序實現下的類型定義和在鏈接實現下的類型定義

有一份電文中共使用五個字符abcde它們的出現頻率依次為請構造相應的哈夫曼樹(左子樹根結點的權小於等於右子樹根結點的權)求出每個字符的哈夫曼編碼

有初始的無序序列為{}給出對其進行歸並排序(升序)的每一趟的結果

設計題(每小題分)

假設用一個循環單鏈表來表示隊列(稱為循環鏈隊)該隊列中只設一個隊尾指 針rear不設隊首指針請編寫向循環鏈隊中插入一個元素X的過程

以鄰接表為存儲結構寫出連通圖的深度優先搜索算法

設有一組關鍵字{}采用散列函數H(key)=key MOD 采用線性探測法解決沖突試在的散列地址空間中對該關鍵字序列構造散列表

數據結構導論試題參考答案

單項選擇題(每小題分) ? C ? B ? D ? B ? A

C ? B? C ? A ? C

B D C C

判斷題(每小題分)

× ? × ? × × ? ×

√ ? √ ? × × √ 三填空題(每小題分) ? ()數據表示? ()數據處理 ?′datastructure′ ? ()在單鏈表第一個結點之前增設的一個類型相同的結點

()表結點中的第一個結點 ? abcd ? ()順序存儲結構? ()鏈表存儲結構

〔logN〕+

()先根遍歷? ()後根遍歷

()散列函數? ()沖突

()確定待查元素所在的塊 ()在塊內查找待查的元素

()邏輯結構 ? ()物理結構

()順序? ()直接

冒泡排序 ? 歸並應用題(每小題分) ? 順序實現

const maxsize∶=; {順序表的容量} ? type datatype=record {檔案數據類型}

name∶string〔〕;{姓名}

number∶integer;{學號}

sex∶boolean;{性別}

age∶integer;{年齡}

end;

type slist =record

data∶array 〔maxsize〕 of datatype;

last∶integer;

end;

鏈接實現

type pointer=↑node;

node=record

name∶string 〔〕;{姓名}

number∶interger {學號}

sex∶ boolean;{性別}

age∶integer;{年齡}

next∶pointer;{結點的後繼指針}

end;

list=pointer;

哈夫曼樹為

相應的哈夫曼編碼為

a: ? b: ? c: ? d: ? e:

畫出正確的哈夫曼樹給寫出相應哈夫曼編碼給

初始無序序列? ? ? ?

} {} {} {} {} {} {}{} {}{

第一次歸並 } { } { }? { }? {

第二次歸並 ? { ? ? } { ? }? {

第三次歸並 ? }? {

第四次歸並 ? ?

設計題(每小題分)

PROCEDURE insert (VAR rear∶pointer; x∶integer);

VAR head tmp∶pointer;

BEGIN

new(tmp);

tmp↑data∶=x;

if (rear=NIL) then {循環隊列為空新結點是隊列的首結點}

BEGIN

rear∶=tmp;

rear↑next∶=tmp;

END

else {隊列不空將新結點插入在隊列尾}

BEGIN

head∶=rear↑next;

rear↑next∶=tmp;

rear∶=tmp;

rear↑next∶=head;

END

END;

procedure dfs(g:adjlist;v∶integer);

{從v出發深度優先遍歷圖g}

begin

write(v);

visited(v)∶=true; ? {標志v已訪問}

p=g〔vlink; ? {找v的第一個鄰接點}

while p< >nil do

〔 if not (visited〔p↑vertex〕)

then dfs(gp↑vertex);

p∶=p↑next〕 {找v的下一個鄰接點}

end;

以鄰接表為存儲結構連通圖的深度優先搜索就是順序查找鏈表

構造過程如下

H()= MOD =

H()= MOD =

H()= MOD =

H()= MOD =(沖突)

H()=(+) MOD =

H()= MOD =

H()= MOD =

H()= MOD = (沖突)

H()=(+) MOD = (仍沖突)

H()=(+) MOD =

H()= MOD = (沖突)

H()=(+) MOD = (沖突)

H()=(+) MOD = (仍沖突)

H()=(+) MOD =

H()= MOD = (沖突)

H()=(+) MOD = (仍沖突)

H()=(+) MOD =

H()= MOD =

H()= MOD = (沖突)

H()=(+) MOD = (仍沖突)

H()=(+) MOD =

H()= MOD = (沖突)

H()=(+) MOD =

因此各關鍵字相應的地址分配如下

address()=

address()=

address()=

address()=

address()=

address()=

address()=

address()=

address()=

address()=

address()=

address()=

其余的地址中為空


From:http://tw.wingwit.com/Article/program/sjjg/201404/30585.html
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2022 電腦知識網 Computer Knowledge   All rights reserved.