《數(shù)據(jù)結(jié)構(gòu)》試題

1、)數(shù)據(jù)結(jié)構(gòu)試題(模A) 2004-5-1一、單項選擇題(從下列各題四個備選答案中選出一個正確答案,將其代號 (A,B,C,D)寫在下表中，答題寫在其它地方無效；每小題1分，共11分) 題號 1 2 3 4 5 6 7 8 9 10 11答案數(shù)據(jù)的不可分割的基本單位是。A.元素 B.結(jié)點(diǎn)C.數(shù)據(jù)類型D.數(shù)據(jù)項下列算法 suanfa2 的時間復(fù)雜度為。int suanfa2(int n) int t=1 ； while(t0)個結(jié)點(diǎn)的完全二叉樹的深度是。A.elog2(n)uB.elog2(n) + 1uC.elog2(n + 1)uD.elog2(n) + 1u與中綴表達(dá)式 a+b*c-d 等價

2、的前綴表達(dá)式是。A.+a-*bcdB.*+-abcdC.-+a*bcdD.abcd+*-折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次 與表中元素進(jìn)行比較,。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,37對長度為10的表作選擇(簡單選擇)排序,共需比較次關(guān)鍵字。 TOC o 1-5 h z A.45B.90C.55D.110對n個元素的表作快速排序，在最壞情況下,算法的時間復(fù)雜度為。A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n ) 共 5 頁第 1 頁對長度為10的表作

3、2_路歸并排序,共需移動次(個)記錄。A.20B.45C.40D.30二、填空(每空1分,共11分)一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示(映象)稱為 。線性表中 稱為表的長度。 TOC o 1-5 h z 棧中元素的進(jìn)出原則為 。4.設(shè)數(shù)組 A1.10,1.8的基地址為 2000,每個元素占 2 個存儲單元,若以行序為主序順序存儲 ,則元素A4,5的存儲地址為；若以列序為主序順序存儲,則元素A4,5的存儲地址為。一棵深度為 6 的滿二叉樹有個非終端結(jié)點(diǎn)。若一棵二叉樹中有8個度為2的結(jié)點(diǎn),則它有個葉子。順序查找 n 個元素的順序表,當(dāng)使用監(jiān)視哨時,若查找成功,比較關(guān)鍵字的次數(shù)至少為 次, 最多為次；若查

4、找失敗,比較關(guān)鍵字的次數(shù)為次。對長度為 400 的表采用分塊（區(qū)）查找,最理想的塊長為。三、回答下列問題 （每小題5分,共10分）線性表的存儲結(jié)構(gòu),在什么情況下采用順序結(jié)構(gòu)? 為什么?二叉樹有哪幾種基本形態(tài)? 畫圖說明之。四、試畫出下列存儲結(jié)構(gòu)圖（每小題4分,共20分）1.數(shù)組 A1.2,0.2 的以列序為主序的順序存儲結(jié)構(gòu)。共 5 頁第 2 頁依次將元素 A,C,D,B 插入一個初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出所有插入完成之后的鏈?zhǔn)綏?。二叉樹的順序存儲結(jié)構(gòu):4.圖的鄰接矩陣:5.有向圖的逆鄰接表: 五、求解下列問題 (每小題6分,共24 分)1.給定 30 個字符組成的電文:D D D D D

5、 A A A B E E A A F C D A A C A B B C C C B A A D D 試為字符A、B、C、D、E、F設(shè)計哈夫曼(Huffman)編碼。畫出相應(yīng)的哈夫曼樹；分別列出 A、 B、 C、 D、 E、 F 的哈夫曼碼； (3)計算該樹的帶權(quán)路徑長度 WPL。共 5 頁第 3 頁2.試按表( 10,8,9,12,20,5,6,15,19,25 ) 中元素的排列次序, 將所有元素插入一棵初始為空的二叉排序 樹中, 使之仍是一棵二叉排序樹。試畫出插入完成之后的二叉排序樹；若查找元素 17,它將依次與二叉排序樹中哪些元素比較大小?假設(shè)每個元素的查找概率相等,試計算該樹的平均查找

6、長度 ASL。對該樹進(jìn)行中序遍歷,試寫出中序遍歷序列。3.試將森林 F= T1,T2,T3,T4 轉(zhuǎn)換為一棵二叉樹。T1 T2 T3 T4找出下面網(wǎng)絡(luò)的最小生成樹。六、填空題(在算法中有下劃線的位置填空,使之成為完整、正確的算法)算法說明：已知r1.n是n個記錄的遞增有序表，用折半查找法查找關(guān)鍵字為k的記錄，若查找失敗，則輸 出” Failure”，返回零；否則輸出” Success”，并返回該記錄的序號值。(共8分)算法(C函數(shù))：共5 頁第4頁int bin_search(struct arecord r,int n,k：keytype)/* r1.n為n個記錄的遞增有序表水為關(guān)鍵字*/

7、int low, mid, hig ； TOC o 1-5 h z low=1； hig=n ； /* 各變量初始化 */ while( ) mid= ；if(krmid.key) else if(k=rmid.key) ；else ；七、算法設(shè)計（算法中必須有注釋,每小題8分,共16 分）1設(shè)n個元素的線性表順序存儲在一維數(shù)組st1.maxlen的前n個位置上，試將新元素e插入表中第i-1 個和第 i 個元素之間,寫出算法。2設(shè)Head為帶表頭結(jié)點(diǎn)的單鏈表的頭指針，試寫出算法:若為非空表,則輸出首結(jié)點(diǎn)和尾結(jié)點(diǎn)的值（data 值）；否則輸出：Empty list!”。共 5 頁第 5 頁網(wǎng)計（

8、專升本）數(shù)據(jù)結(jié)構(gòu)試題（模 B）2004-5-1 一、單項選擇題（從下列各題四個備選答案中選出一個正確答案,將其代號 （A,B,C,D）寫在下表中，答題寫在其它地方無效；每小題1分，共11分）題號 1 2 3 4 5 6 7 8 9 10 11答案數(shù)據(jù)的基本單位是。結(jié)點(diǎn)B.數(shù)據(jù)元素C.數(shù)據(jù)類型D.數(shù)據(jù)項2下列算法suanfal中語句x=x*2；的執(zhí)行次數(shù)是void suanfa1(int n) int i,j,x=1 ；for(i=1； i=n； i+)for(j=i； j0)個結(jié)點(diǎn)的完全二叉樹的深度是。A.elog2(n) + 1uB.elog2(n)-1uC.elog2(n)-1uD.elo

9、g2(n) + 1u與中綴表達(dá)式 a-b/c+d 等價的前綴表達(dá)式是。A.-a+/bcdB./-+bcdC.+-/bcdD.abcd-/+對有3600個記錄的索引順序表(分塊表)進(jìn)行查找,最理想的塊長為。A.1800B.60C.1200D.elog2 3600心共 5 頁第 1 頁對n個元素的表作堆排序，在最壞情況下,算法的時間復(fù)雜度為。A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n )二、填空題(每空1 分,共 11 分)1. 一個算法具有 5 個特性:、有零個或多個輸入、有一個或多個輸出。2設(shè)長度為n的線性表順序存貯，若在它的第i-1和第i個元素之間插入一個

10、元素，共需移動 個元素(1iWn)。一個字符串中 稱為該串的子串。 樹中結(jié)點(diǎn)A的 稱為結(jié)點(diǎn)A的度。一棵深度為4的二叉樹最多有 個結(jié)點(diǎn)。具有10個頂點(diǎn)的無向圖,邊的總數(shù)最多為 。順序查找 n 個元素的順序表,當(dāng)不使用監(jiān)視哨時,若查找成功,比較關(guān)鍵字的次數(shù)最多為 次；若查找失敗,比較關(guān)鍵字的次數(shù)為 次。8.折半查找有序表（ 2,4,6,12,20,28,38,50,70,100 ）,若查找表中元素 12, 它依次與表中元素 比較大小。三、回答下列問題 （每小題5分,共10 分）線性表的存儲結(jié)構(gòu),在什么情況下采用鏈接表（如:單鏈表）結(jié)構(gòu)?為什么?空格串與空串有區(qū)別? 舉例說明之。共 5 頁第 2 頁

11、 四、試畫出下列存儲結(jié)構(gòu)圖（每小題5 分,共 20分） 1.試畫出下列稀疏矩陣以列序為主序的三元組表。稀疏矩陣試畫出下列二叉樹的中序線索二叉樹存儲結(jié)構(gòu)圖。二叉樹試用孩子兄弟（左孩子右兄弟）表示法畫出下列樹的存儲結(jié)構(gòu)圖。試畫出下列有向網(wǎng)的逆鄰接表。有向網(wǎng)共 5 頁第 3 頁五、求解下列問題 (每小題6分,共24 分)已知二叉樹的前序遍歷序列和中序遍歷序列分別是 B,A,C,D,F,E,G 和 D,C,A,F,G,E,B, 試畫出該二叉樹。2.試按表(25,15,19,24,20,5,16,45,40,38)中元素的排列次序,將所有元素插入一棵初始為空的二叉排 序樹中,使之仍是一棵二叉排序樹。(1

12、)試畫出插入完成之后的二叉排序樹；(2)若查找元素 17,它將依次與 二叉排序樹中哪些元素比較大小?(3)假設(shè)每個元素的查找概率相等,試計算該樹的平均查找長度 ASL；(4) 對該樹進(jìn)行中序遍歷,試寫出中序遍歷序列。3試用權(quán)集合4,6,5,12,2,1,13,構(gòu)造赫夫曼(Huffman)樹,(1)列出構(gòu)造過程，(2)分別計算該赫夫曼 樹的路徑長度和帶權(quán)路徑長度。找出下面網(wǎng)絡(luò)的最小生成樹:共 5 頁第 4 頁六、執(zhí)行下面的C程序，指出輸出結(jié)果。(8分)#include#includestruct node char data ；struct node *next；void link_list(s

13、truct node *p) while(p!=NULL) printf(%c,p-data) ； p=p-next；printf(n)；main( ) char ch ；struct node *q,*p,*f,*head=NULL；for (ch=A；chdata=ch； p-next=head； head=p； link_list(p)；p=head； head=NULL；while(p!=NULL) q=p； p=p-next ； q-next=head ； head=q； f=head ；while(f-next!=NULL)link_list(head)； f=f-next-nex

14、t；七、算法設(shè)計(算法中必須有注釋,每小題8分,共16 分)1設(shè)n個元素的線性表順序存儲在一維數(shù)組st1.maxlen的前n個位置上，試寫出算法:刪除表中第i(1 WiWn)個元素。2.設(shè) Head 為帶表頭結(jié)點(diǎn)的單鏈表的頭指針,試寫出算法:若為非空表,則輸出:最大結(jié)點(diǎn)和最小結(jié)點(diǎn)的值 （data 值）；否則,輸出：“Empty list”。共 5 頁第 5 頁網(wǎng)計（專升本）數(shù)據(jù)結(jié)構(gòu)試題（模 C） 2004-5-1一、選擇題（從下列各題的4個備選答案中選出1至2個正確答案，將其代號（A,B,C,D）寫在下表中,答題寫 在其它地方無效；每小題 1 分,共15 分）題號 1 2 3 4 5 6 7

15、8 9 10 11 12 12 14 15答案由組成的集合是一個數(shù)據(jù)對象。A.不同類型的數(shù)據(jù)項A.不同類型的數(shù)據(jù)項C.相同類型的數(shù)據(jù)項2.是線性表。A.(孔子,諸葛亮，曹雪芹)不同類型的數(shù)據(jù)元素D.相同類型的數(shù)據(jù)元素A,B,C,D10,11,12,13,14D.(1,2,3,.) 是表示線性數(shù)據(jù)結(jié)構(gòu)的。A.循環(huán)鏈表B.鄰接多重表C.孩子鏈表 D.單鏈表將線性表的數(shù)據(jù)元素以結(jié)構(gòu)存放, 查找一個數(shù)據(jù)元素所需的時間不依賴于表的長度。A.循環(huán)雙鏈表B.哈希(Hash)表C.一維數(shù)組D.單鏈表設(shè)數(shù)組 A1.8,1.10的基地址為 4000, 每個元素占 2 個存儲單元,若以列序為主序順序存儲,則元素A4

16、,7的存儲地址是。(假定無第0行第0列元素)A.4072B.4104C.4102D.40746設(shè)依次進(jìn)入一個棧的元素序列為c,a,b,d,不可得到出棧的元素序列有A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b7._ 又是一棵滿二叉樹。A.二叉排序樹B.深度為5有31個結(jié)點(diǎn)的二叉樹C.有15個結(jié)點(diǎn)的完全二叉樹D.哈夫曼(Huffman)樹深度為 k 的滿二叉樹有個分枝結(jié)點(diǎn)。A.2k-1B.2k-1-1C.2k+1D.2k-1+19具有n(n0)個結(jié)點(diǎn)的完全二叉樹的深度為。A.elog2(n)uB.elog2(n)u +1C.elog2(n + 1)uD.elog2

17、(n + 1)u折半查找 20 個記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù)。A.最多為6B.最多為5 C.最少為3 D.最少為4折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次與表中元素進(jìn)行比較。A.25,40,60B.25,40C.20,36,40,60D.20,36,40 TOC o 1-5 h z 查找哈希(Hash)表,解決沖突的的方法有。A.除留余數(shù)法B.線性探測再散列法C.直接地址法 D.鏈地址法共5頁第1頁對有 10 個記錄的表作簡單選擇排序,需要比較_次關(guān)鍵字。A.100B.45C.50D.90對有 n 個記錄的表作快速排序,在最壞情況下,算

18、法的時間復(fù)雜度是。A.O(n) B.O(n2) C.O(nlog2n) D.O(n3)一個排序算法時間復(fù)雜度的大小有關(guān)。A與所需比較關(guān)鍵字的次數(shù) B與該算法的穩(wěn)定性不與所需移動記錄的數(shù)目D.與所需輔助存儲空間的大小二、畫圖題(每小題4分,共20分)依次輸入元素 X,Y,Z, 插入到一個初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出空的鏈?zhǔn)綏：兔坎迦胍粋€元素之后的 鏈?zhǔn)綏Ｊ疽鈭D。試用雙親表示法畫出下列樹 T 的存儲結(jié)構(gòu)圖。3試畫出有3行4列元素的二維數(shù)組B的以列序為主序的順序存儲結(jié)構(gòu)圖。試畫出下列圖的鄰接表。圖共 5 頁第 2 頁已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別是：I,A,B,E,F,G,C,H,D 和 A,E,F,B,I,G,H,C,D 試畫出該二叉樹。三、求解問題(每小題 7分,共28 分)1.用算符優(yōu)先法求下列算術(shù)表達(dá)式的值,試簡要說明求值過程,畫出*作數(shù)棧 和運(yùn)算符棧的主要變化過程12+20/(10-2*3)2.給定電文(文本):F