|
第一部分 選擇題
一,、單項選擇題（本大題共14小題，每小題1分,，共14分）在每小題列出的四個選項中只有一個選項是符合題目要求的,，請將正確選項前的字母填在題后的括號內(nèi)。
1.算法分析的目的是( C ) A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中的輸入/輸出關(guān)系 C.分析算法的效率以求改進 D.分析算法的易讀性
2.在需要經(jīng)常查找結(jié)點的前驅(qū)與后繼的場合中,，使用( B )比較合適,。 A.單鏈表 B.雙鏈表 C.順序表 D.循環(huán)鏈表
3.下面關(guān)于線性表的敘述中，錯誤的為( D ) A.順序表使用一維數(shù)組實現(xiàn)的線性表 B.順序表必須占用一片連續(xù)的存儲單元 C.順序表的空間利用率高于鏈表 D.在鏈表中,，每個結(jié)點只有一個鏈域
4.帶頭結(jié)點的單鏈表head為空的判斷條件是( B ) A. head=NIL B. head->next=NIL C. head->next=head D. head< >NIL
5.隊列通常采用兩種存儲結(jié)構(gòu)是( A ) A.順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B.散列方式和索引方式 C.鏈表存儲結(jié)構(gòu)和數(shù)組 D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)
6.按照二叉樹的定義,，具有3個結(jié)點的二叉樹有( C )種。
A.3 B.4 C.5 D.6
7.二叉樹的結(jié)構(gòu)如下圖所示,，其中序遍歷的序列為( )
A.a,b,d,g,c,e,f,h B.d,g,b,a,e,c,h,f C.g,d,b,e,h,f,c,a D.a,b,c,d,e,f,g,h
8.深度為5的二叉樹至多有( C )個結(jié)點,。 (2^M-1) A.16 B.32 C.31 D.10
9.對于一個具有n個頂點的無向圖,，若采用鄰接表表示，則存放表頭結(jié)點的數(shù)組的大小為 ( A ) A.n B.n+1 C.n-1 D.n+邊數(shù)
10.在一個具有n個頂點的無向圖中,，要連通全部頂點至少需要( C )條邊,。 A.n B.n+1 C.n-1 D.n/2
11.靜態(tài)查找表與動態(tài)查找表二者的根本差別在于( B ) A.它們的邏輯結(jié)構(gòu)不一樣 B.施加在其上的操作不同 C.所包含的數(shù)據(jù)元素的類型不一樣 D.存儲實現(xiàn)不一樣
12.散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的存放地址。因為散列函數(shù)不是一對一的關(guān)系,，所以選擇好的( D )方法是散列文件的關(guān)鍵,。 A.散列函數(shù) B.除余法中的質(zhì)數(shù) C.沖突處理 D.散列函數(shù)和沖突處理
13.對于大文件的排序要研究在外設(shè)上的排序技術(shù)，即( C ) A.快速排序法 B.內(nèi)排序法 C.外排序法 D.交叉排序法
14.設(shè)有5000個無序的元素,，希望用最快的速度挑選出其中前50個最大的元素，最好選用( C )法,。 A.冒泡排序 B.快速排序 C.堆排序 D.基數(shù)排序
二,、判斷題(判斷下列各題，正確的在題干后面括號內(nèi)打“√”,，錯誤的打“×”,。每小題2分，共20分)
1.所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的邏輯關(guān)系,。( )
2.在線性結(jié)構(gòu)中,，每個結(jié)點都有一個直接前驅(qū)和一個直接后繼。( )
3.插入和刪除是數(shù)組的兩種基本操作,。( )
4.在鏈棧的頭部必須要設(shè)置頭結(jié)點,。( )
5.在二叉樹中插入結(jié)點則該二叉樹便不再是二叉樹。( )
6.查找表的邏輯結(jié)構(gòu)是集合,。( )
7.靜態(tài)查找表的檢索與修改被分成兩個不交叉的階段分別進行,。( )
8.在索引順序文件中插入新的記錄時，必須復(fù)制整個文件,。( )
9.如果某種排序算法是不穩(wěn)定的,，則該方法沒有實際的應(yīng)用價值。( )
10.對于n個記錄的集合進行冒泡排序,，在最壞情況下所需要的時間是0(n2)( )
三,、填空題(每小題2分，共30分)
1.程序設(shè)計的實質(zhì)是________和________,。
2.設(shè)由字符串a(chǎn)=′data′,、b=′structure′、c=′-′,則a與c連接然后與b連接的結(jié)果為：________,。
3.通常單鏈表的頭結(jié)點指的是________,；單鏈表的首結(jié)點指的是________。
4.一個隊列的入隊序列是a,、b,、c,、d，則隊列的輸出序列為________,。
5.棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是________和________,。
6.具有N個結(jié)點的完全二叉樹的深度為________。
7.樹的三種主要的遍歷方法是：________,、________和層次遍歷,。
8.在無向圖的鄰接矩陣A中，若A〔i,j〕等于1,，則A〔j,i〕等于________,。
9.采用散列技術(shù)實現(xiàn)散列表時，需要考慮的兩個主要問題是：構(gòu)造________和解決________,。
10.索引順序表上的查找分兩個階段：(1)________,；(2)________。
11.散列文件中的記錄通常是成組存放的,。若干的記錄組成一個存儲單位,，稱作________。
12.就文件而言,，按用戶的觀點所確定的基本存儲單元稱為________,。按外設(shè)的觀點所確定的基本存儲單元稱為________。
13.文件的檢索有三種方式：________存取,、________存取和按關(guān)鍵字存取,。
14.最簡單的交換排序方法是________排序。
15.外排序的基本方法是________,。
四,、應(yīng)用題(每小題6分，共18分)
1.假定在學(xué)生的檔案中含有：姓名,、學(xué)號,、年齡、性別,。如采用線性表作為數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)檔案管理問題,，分別給出線性表的在順序?qū)崿F(xiàn)下的類型定義和在鏈接實現(xiàn)下的類型定義。
2.有一份電文中共使用五個字符：a,、b,、c、d,、e,它們的出現(xiàn)頻率依次為8,、14、10,、4,、18,，請構(gòu)造相應(yīng)的哈夫曼樹(左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán))，求出每個字符的哈夫曼編碼,。
3.有初始的無序序列為{98,65,38,40,12,51,100,77,26,88},給出對其進行歸并排序(升序)的每一趟的結(jié)果,。
五、設(shè)計題(每小題6分,，共18分)
1.假設(shè)用一個循環(huán)單鏈表來表示隊列(稱為循環(huán)鏈隊),，該隊列中只設(shè)一個隊尾指 針rear,不設(shè)隊首指針。請編寫向循環(huán)鏈隊中插入一個元素X的過程,。
2.以鄰接表為存儲結(jié)構(gòu),，寫出連通圖的深度優(yōu)先搜索算法。
3.設(shè)有一組關(guān)鍵字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函數(shù)：H(key)=key MOD 13, 采用線性探測法解決沖突,，試在0～18的散列地址空間中對該關(guān)鍵字序列構(gòu)造散列表,。
數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題參考答案 一、單項選擇題(每小題1分,，共14分) 1.C 2.B 3.D 4.B 5.A 6.C 7.B 8.C 9.A 10.C 11.B 12.D 13.C 14.C 二,、判斷題(每小題2分,，共20分) 1. × 2. × 3. × 4. × 5. × 6. √ 7. √ 8. × 9. × 10. √ 三,、填空題(每小題2分，共30分) 1.(1)數(shù)據(jù)表示 (2)數(shù)據(jù)處理,。 2.′data-structure′,。 3.(1)在單鏈表第一個結(jié)點之前增設(shè)的一個類型相同的結(jié)點 (2)表結(jié)點中的第一個結(jié)點。 4. a,、b,、c、d,。 5.(1)順序存儲結(jié)構(gòu) (2)鏈表存儲結(jié)構(gòu),。 6.〔log2N〕+1。 7.(1)先根遍歷 (2)后根遍歷,。 8.1,。 9.(1)散列函數(shù) (2)沖突。 10.(1)確定待查元素所在的塊 (2)在塊內(nèi)查找待查的元素,。 11.桶,。 12.(1)邏輯結(jié)構(gòu) (2)物理結(jié)構(gòu)。 13.(1)順序 (2)直接,。 14.冒泡排序,。 15.歸并。 四,、應(yīng)用題(每小題6分,，共18分) 1.順序?qū)崿F(xiàn)： const maxsize∶=100; ｛順序表的容量｝ type datatype=record ｛檔案數(shù)據(jù)類型｝ name∶string〔10〕;｛姓名｝ number∶integer;｛學(xué)號｝ sex∶boolean;｛性別｝ age∶integer;｛年齡｝ end; type slist =record data∶array 〔1..maxsize〕 of datatype; last∶integer; end; 鏈接實現(xiàn)： type pointer=↑node; node=record name∶string 〔10〕;｛姓名｝ number∶interger,； ｛學(xué)號｝ sex∶ boolean;｛性別｝ age∶integer;｛年齡｝ next∶pointer;｛結(jié)點的后繼指針｝ end; list=pointer; 2.哈夫曼樹為：
相應(yīng)的哈夫曼編碼為： a:001 b:10 c:01 d:000 e:11 畫出正確的哈夫曼樹給4分，寫出相應(yīng)哈夫曼編碼給2分 3. 初始無序序列： 98 65 38 40 12 51 100 77 26 88 ｛98｝ ｛65｝ ｛38｝ ｛40｝ ｛12｝ ｛51｝ ｛100｝｛77｝ ｛26｝｛88｝ 第一次歸并： ｛65 98｝ ｛38 40｝ ｛12 51｝ ｛77 100｝ ｛26 88｝ 第二次歸并： ｛38 40 65 98｝ ｛12 51 77 100｝ ｛26 88｝ 第三次歸并： ｛12 38 40 51 65 77 98 100｝ ｛26 88｝ 第四次歸并： ｛12 26 38 40 51 65 77 88 98 100｝ 五,、設(shè)計題(每小題6分,，共18分) 1.PROCEDURE insert (VAR rear∶pointer; x∶integer); VAR head, tmp∶pointer; BEGIN new(tmp); tmp↑.data∶=x; if (rear=NIL) then ｛循環(huán)隊列為空，新結(jié)點是隊列的首結(jié)點｝ BEGIN rear∶=tmp; rear↑.next∶=tmp; END else ｛隊列不空,，將新結(jié)點插入在隊列尾｝ BEGIN head∶=rear↑.next; rear↑.next∶=tmp; rear∶=tmp; rear↑.next∶=head; END END; 2.procedure dfs(g:adj-list;v1∶integer); ｛從v1出發(fā),，深度優(yōu)先遍歷圖g｝ begin write(v1); visited(v1)∶=true; ｛標(biāo)志v1已訪問｝ p=g〔v1〕.link; ｛找v1的第一個鄰接點｝ while p< >nil do 〔 if not (visited〔p↑.vertex〕) then dfs(g,p↑.vertex); p∶=p↑.next〕 ｛找v1的下一個鄰接點｝ end; 以鄰接表為存儲結(jié)構(gòu)，連通圖的深度優(yōu)先搜索就是順序查找鏈表,。 3.構(gòu)造過程如下： H(19)=19 MOD 13=6 H(01)=01 MOD 13=1 H(23)=23 MOD 13=10 H(14)=14 MOD 13=1(沖突) H(14)=(1+1) MOD 19=2 H(55)=55 MOD 13=3 H(20)=20 MOD 13=7 H(84)=84 MOD 13=6 (沖突) H(84)=(6+1) MOD 19=7 (仍沖突) H(84)=(6+2) MOD 19=8 H(27)=27 MOD 13=1 (沖突) H(27)=(1+1) MOD 19=2 (沖突) H(27)=(1+2) MOD 19=3 (仍沖突) H(27)=(1+3) MOD 19=4 H(68)=68 MOD 13=3 (沖突) H(68)=(3+1) MOD 19=4 (仍沖突) H(68)=(3+2) MOD 19=5 H(11)=11 MOD 13=11 H(10)=10 MOD 13=10 (沖突) H(10)=(10+1) MOD 19=11 (仍沖突) H(10)=(10+2) MOD 19=12 H(77)=77 MOD 13=12 (沖突) H(77)=(12+1) MOD 19=13 因此,，各關(guān)鍵字相應(yīng)的地址分配如下： address(01)=1 address(14)=2 address(55)=3 address(27)=4 address(68)=5 address(19)=6 address(20)=7 address(84)=8 address(23)=10 address(11)=11 address(10)=12 address(77)=13 其余的地址中為空。
|
|
|
來自： 看風(fēng)景D人 > 《名企筆試題》
