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

1、讀書(shū)破萬(wàn)卷 下筆如有神 )數(shù)據(jù)結(jié)構(gòu)試題(模A) 2004-5-1 一、單項(xiàng)選擇題(從下列各題四個(gè)備選答案中選出一個(gè)正確答案,將其代號(hào) (A,B,C,D)寫(xiě)在下表中,答題寫(xiě)在其它地方無(wú)效；每小題1分,共11分) 題號(hào) 1 2 3 4 5 6 7 8 9 10 11 答案 1.數(shù)據(jù)的不可分割的基本單位是_。 A.元素 B.結(jié)點(diǎn) C.數(shù)據(jù)類(lèi)型 D.數(shù)據(jù)項(xiàng) 2.下列算法suanfa2的時(shí)間復(fù)雜度為_(kāi)。 int suanfa2(int n) int t=1； while(t0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是_。 A.log2(n) B.log2(n)+1 C.?log2(n+1)? D.?log2(n)+1

2、? 7.與中綴表達(dá)式a+b*c-d等價(jià)的前綴表達(dá)式是_。 A.+a-*bcd B.*+-abcd C.-+a*bcd D.abcd+*- 8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次 與表中元素_進(jìn)行比較,。 A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,37 9.對(duì)長(zhǎng)度為10的表作選擇(簡(jiǎn)單選擇)排序,共需比較_次關(guān)鍵字。 A.45 B.90 C.55 D.110 10.對(duì)n個(gè)元素的表作快速排序,在最壞情況下,算法的時(shí)間復(fù)雜度為_(kāi)。 A.O(log2 n) B.O(nlog2 n) C.O(n

3、2) D.O(2n ) 共5 頁(yè)第1頁(yè) 11.對(duì)長(zhǎng)度為10的表作2_路歸并排序,共需移動(dòng)_次(個(gè))記錄。 A.20 B.45 C.40 D.30 二、填空(每空1分,共11分) 1.一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映象)稱(chēng)為 _?。 稱(chēng)為表的長(zhǎng)度。_ 線(xiàn)性表中2.讀書(shū)破萬(wàn)卷 下筆如有神 3.棧中元素的進(jìn)出原則為 _ 。 4.設(shè)數(shù)組A1.10,1.8的基地址為2000,每個(gè)元素占2個(gè)存儲(chǔ)單元,若以行序?yàn)橹餍蝽樞虼鎯?chǔ),則元素A4,5的存儲(chǔ)地址為_(kāi)；若以列序?yàn)橹餍蝽樞虼鎯?chǔ),則元素A4,5的存儲(chǔ)地址為_(kāi)。 5.一棵深度為6的滿(mǎn)二叉樹(shù)有_個(gè)非終端結(jié)點(diǎn)。 6.若一棵二叉樹(shù)中有8個(gè)度為2的結(jié)點(diǎn),則它有_個(gè)葉子

4、。 7.順序查找n個(gè)元素的順序表,當(dāng)使用監(jiān)視哨時(shí),若查找成功,比較關(guān)鍵字的次數(shù)至少為_(kāi)次, 最多為_(kāi)次；若查找失敗,比較關(guān)鍵字的次數(shù)為_(kāi)次。 8.對(duì)長(zhǎng)度為400的表采用分塊(區(qū))查找,最理想的塊長(zhǎng)為_(kāi)。 三、回答下列問(wèn)題 (每小題5分,共10分) 1.線(xiàn)性表的存儲(chǔ)結(jié)構(gòu),在什么情況下采用順序結(jié)構(gòu)? 為什么? 2.二叉樹(shù)有哪幾種基本形態(tài)? 畫(huà)圖說(shuō)明之。 四、試畫(huà)出下列存儲(chǔ)結(jié)構(gòu)圖(每小題4分,共20分) 1.數(shù)組A1.2,0.2 的以列序?yàn)橹餍虻捻樞虼鎯?chǔ)結(jié)構(gòu)。 共5 頁(yè)第2頁(yè) 2.依次將元素 A,C,D,B 插入一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫(huà)出所有插入完成之后的鏈?zhǔn)綏！?3.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu):

5、 4.圖的鄰接矩陣: 5.有向圖的逆鄰接表: 讀書(shū)破萬(wàn)卷 下筆如有神 五、求解下列問(wèn)題 (每小題6分,共24分) 1.給定30個(gè)字符組成的電文: D D D D D 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è)計(jì)哈夫曼(Huffman)編碼。 (1)畫(huà)出相應(yīng)的哈夫曼樹(shù)； (2)分別列出 A、B、C、D、E、F 的哈夫曼碼； (3)計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。 共5 頁(yè)第3頁(yè) 2.試按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 將所有元素插入一棵初始為空的二叉排序樹(shù)中

6、, 使之仍是一棵二叉排序樹(shù)。 (1)試畫(huà)出插入完成之后的二叉排序樹(shù)； (2)若查找元素17,它將依次與二叉排序樹(shù)中哪些元素比較大小? (3)假設(shè)每個(gè)元素的查找概率相等,試計(jì)算該樹(shù)的平均查找長(zhǎng)度 ASL。 (4)對(duì)該樹(shù)進(jìn)行中序遍歷,試寫(xiě)出中序遍歷序列。 3.試將森林 F= T1,T2,T3,T4 轉(zhuǎn)換為一棵二叉樹(shù)。 T1 T2 T3 T4 4.找出下面網(wǎng)絡(luò)的最小生成樹(shù)。 六、填空題(在算法中有下劃線(xiàn)_的位置填空,使之成為完整、正確的算法) 算法說(shuō)明:已知r1.n是n個(gè)記錄的遞增有序表,用折半查找法查找關(guān)鍵字為k的記錄,若查找失敗,則輸出”Failure”,返回零；否則輸出”Success”,并返

7、回該記錄的序號(hào)值。(共8分) 算法(C函數(shù)): 共5 頁(yè)第4頁(yè) int bin_search(struct arecord r,int n,k:keytype) 讀書(shū)破萬(wàn)卷 下筆如有神 /* r1.n為n個(gè)記錄的遞增有序表,k為關(guān)鍵字 */ int low, mid, hig ； low=1； hig=n ； /* 各變量初始化 */ while( _ ) mid=_ ； if(krmid.key) _ ； else if(k=rmid.key) _ ； _ ； else _ ； _ ； _ ； 七、算法設(shè)計(jì)(算法中必須有注釋,每小題8分,共16分) 1.設(shè)n個(gè)元素的線(xiàn)性表順序存儲(chǔ)在一維數(shù)組s

8、t1.maxlen的前n個(gè)位置上,試將新元素e插入表中第i-1個(gè)和第i個(gè)元素之間,寫(xiě)出算法。 2.設(shè)Head為帶表頭結(jié)點(diǎn)的單鏈表的頭指針,試寫(xiě)出算法:若為非空表,則輸出首結(jié)點(diǎn)和尾結(jié)點(diǎn)的值(data值)；否則輸出:”Empty list！”。 共5 頁(yè)第5頁(yè) 網(wǎng)計(jì)(專(zhuān)升本)數(shù)據(jù)結(jié)構(gòu)試題(模B)2004-5-1 一、單項(xiàng)選擇題(從下列各題四個(gè)備選答案中選出一個(gè)正確答案,將其代號(hào) (A,B,C,D)寫(xiě)在下表中,答題寫(xiě)在其它地方無(wú)效；每小題1分,共11分) 題號(hào) 1 2 3 4 5 6 7 8 9 10 11 答案 。_數(shù)據(jù)的基本單位是1.讀書(shū)破萬(wàn)卷 下筆如有神 A.結(jié)點(diǎn) B.數(shù)據(jù)元素 C.數(shù)據(jù)類(lèi)型

9、D.數(shù)據(jù)項(xiàng) 2.下列算法suanfa1中語(yǔ)句硜砽月；的執(zhí)行次數(shù)是_。 void suanfa1(int n) int i,j,x=1； for(i=1；i=n；i+) for(j=i；j0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是_。 A.log2(n)+1 B.log2(n)-1 C.?log2(n)-1? D.?log2(n)+1? 9.與中綴表達(dá)式a-b/c+d等價(jià)的前綴表達(dá)式是_。 A.-a+/bcd B./-+bcd C.+-/bcd D.abcd-/+ 10.對(duì)有3600個(gè)記錄的索引順序表(分塊表)進(jìn)行查找,最理想的塊長(zhǎng)為_(kāi)。 A.1800 B.60 C.1200 D.log2 3600 共5

10、頁(yè)第1頁(yè) 11.對(duì)n個(gè)元素的表作堆排序,在最壞情況下,算法的時(shí)間復(fù)雜度為_(kāi)。 A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n ) 二、填空題(每空1分,共11分) 1.一個(gè)算法具有5個(gè)特性:_、_、_、有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。 2.設(shè)長(zhǎng)度為n的線(xiàn)性表順序存貯,若在它的第i-1和第i個(gè)元素之間插入一個(gè)元素, 共需移動(dòng) _ 個(gè)元素(1in)。 3.一個(gè)字符串中 _ 稱(chēng)為該串的子串。 4.樹(shù)中結(jié)點(diǎn)A的 _ 稱(chēng)為結(jié)點(diǎn)A的度。 5.一棵深度為4的二叉樹(shù)最多有 _ 個(gè)結(jié)點(diǎn)。 。_ 邊的總數(shù)最多為,個(gè)頂點(diǎn)的無(wú)向圖10具有6.讀書(shū)破萬(wàn)卷 下筆如有神 7.順序查找n個(gè)

11、元素的順序表,當(dāng)不使用監(jiān)視哨時(shí),若查找成功,比較關(guān)鍵字的次數(shù)最多為 _ 次；若查找失敗,比較關(guān)鍵字的次數(shù)為 _ 次。 8.折半查找有序表( 2,4,6,12,20,28,38,50,70,100 ),若查找表中元素12,它依次與表中元素 _ 比較大小。 三、回答下列問(wèn)題 (每小題5分,共10分) 1.線(xiàn)性表的存儲(chǔ)結(jié)構(gòu),在什么情況下采用鏈接表(如:單鏈表)結(jié)構(gòu)?為什么? 2.空格串與空串有區(qū)別? 舉例說(shuō)明之。 共5 頁(yè)第2頁(yè) ) 每小題20分5分,共四、試畫(huà)出下列存儲(chǔ)結(jié)構(gòu)圖( 1.試畫(huà)出下列稀疏矩陣以列序?yàn)橹餍虻娜M表。 稀疏矩陣 試畫(huà)出下列二叉樹(shù)的中序線(xiàn)索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)圖。2. 二叉樹(shù) 表示

12、法畫(huà)出下列樹(shù)的存儲(chǔ)結(jié)構(gòu)圖。)(3.試用孩子兄弟左孩子右兄弟 樹(shù) 讀書(shū)破萬(wàn)卷 下筆如有神 4.試畫(huà)出下列有向網(wǎng)的逆鄰接表。 有向網(wǎng) 共5 頁(yè)第3頁(yè) 五、求解下列問(wèn)題 (每小題6分,共24分) 1.已知二叉樹(shù)的前序遍歷序列和中序遍歷序列分別是： B,A,C,D,F,E,G和D,C,A,F,G,E,B, 試畫(huà)出該二叉樹(shù)。 2.試按表(25,15,19,24,20,5,16,45,40,38)中元素的排列次序,將所有元素插入一棵初始為空的二叉排序樹(shù)中,使之仍是一棵二叉排序樹(shù)。(1)試畫(huà)出插入完成之后的二叉排序樹(shù)；(2)若查找元素17,它將依次與二叉排序樹(shù)中哪些元素比較大小?(3)假設(shè)每個(gè)元素的查找概率

13、相等,試計(jì)算該樹(shù)的平均查找長(zhǎng)度 ASL；(4)對(duì)該樹(shù)進(jìn)行中序遍歷,試寫(xiě)出中序遍歷序列。 3.試用權(quán)集合4,6,5,12,2,1,13,構(gòu)造赫夫曼(Huffman)樹(shù),(1)列出構(gòu)造過(guò)程, (2)分別計(jì)算該赫夫曼樹(shù)的路徑長(zhǎng)度和帶權(quán)路徑長(zhǎng)度。 4.找出下面網(wǎng)絡(luò)的最小生成樹(shù): 共5 頁(yè)第4頁(yè) 六、執(zhí)行下面的C程序,指出輸出結(jié)果。(8分) #include #include 讀書(shū)破萬(wàn)卷 下筆如有神 struct node char data； struct node *next； ； void link_list(struct node *p) while(p!=NULL) printf(%c,p-d

14、ata)； p=p-next； printf()； 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-next； 七、算法設(shè)計(jì)(算法中必須有注釋,每小題8分,共16分) 1.設(shè)n個(gè)元素的線(xiàn)性

15、表順序存儲(chǔ)在一維數(shù)組 st1.maxlen 的前n個(gè)位置上,試寫(xiě)出算法:刪除表中第i(1in)個(gè)元素。 2.設(shè)Head為帶表頭結(jié)點(diǎn)的單鏈表的頭指針,試寫(xiě)出算法:若為非空表,則輸出:最大結(jié)點(diǎn)和最小結(jié)點(diǎn)的值(data值)；否則,輸出:“Empty list”。 共5 頁(yè)第5頁(yè) 網(wǎng)計(jì)(專(zhuān)升本)數(shù)據(jù)結(jié)構(gòu)試題(模C) 2004-5-1 一、選擇題(從下列各題的4個(gè)備選答案中選出1至2個(gè)正確答案,將其代號(hào)(A,B,C,D)寫(xiě)在下表中,答題寫(xiě)在其它地方無(wú)效；每小題1分,共15分) 1 2 3 4 5 6 7 8 9 10 11 12 12 14 15 題號(hào)讀書(shū)破萬(wàn)卷 下筆如有神 答案 1.由_組成的集合是一

16、個(gè)數(shù)據(jù)對(duì)象。 A.不同類(lèi)型的數(shù)據(jù)項(xiàng) B.不同類(lèi)型的數(shù)據(jù)元素 C.相同類(lèi)型的數(shù)據(jù)項(xiàng) D.相同類(lèi)型的數(shù)據(jù)元素 2._是線(xiàn)性表。 A.(孔子,諸葛亮,曹雪芹) B.A,B,C,D C.10,11,12,13,14 D.(1,2,3,.) 3._ 是表示線(xiàn)性數(shù)據(jù)結(jié)構(gòu)的。 A.循環(huán)鏈表 B.鄰接多重表 C.孩子鏈表 D.單鏈表 4.將線(xiàn)性表的數(shù)據(jù)元素以_結(jié)構(gòu)存放, 查找一個(gè)數(shù)據(jù)元素所需 的時(shí)間不依賴(lài)于表的長(zhǎng)度。 A.循環(huán)雙鏈表 B.哈希(Hash)表 C.一維數(shù)組 D.單鏈表 5.設(shè)數(shù)組A1.8,1.10的基地址為4000, 每個(gè)元素占2個(gè)存儲(chǔ)單元,若以列序?yàn)橹餍蝽樞虼鎯?chǔ),則元素A4,7的存儲(chǔ)地址是_。

17、(假定無(wú)第0行第0列元素) A.4072 B.4104 C.4102 D.4074 6.設(shè)依次進(jìn)入一個(gè)棧的元素序列為c,a,b,d,不可得到出棧的元素序列有_。 A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b 7._ 又是一棵滿(mǎn)二叉樹(shù)。 A.二叉排序樹(shù) B.深度為5有31個(gè)結(jié)點(diǎn)的二叉樹(shù) C.有15個(gè)結(jié)點(diǎn)的完全二叉樹(shù) D.哈夫曼(Huffman)樹(shù) 8.深度為k的滿(mǎn)二叉樹(shù)有_個(gè)分枝結(jié)點(diǎn)。 A.2k-1 B.2k-1-1 C.2k+1 D.2k-1+1 9.具有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)。 A.log2(n) B.?log2(n)? +1 C.log2(

18、n+1) D.?log2(n+1)? 10.折半查找20個(gè)記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù)_。 A.最多為6 B.最多為5 C.最少為3 D.最少為4 11.折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次與 表中元素_進(jìn)行比較。 A.25,40,60 B.25,40 C.20,36,40,60 D.20,36,40 12.查找哈希(Hash)表,解決沖突的的方法有_。 A.除留余數(shù)法 B.線(xiàn)性探測(cè)再散列法 C.直接地址法 D.鏈地址法 共5頁(yè)第1頁(yè) 13.對(duì)有10個(gè)記錄的表作簡(jiǎn)單選擇排序,需要比較_次關(guān)鍵字。 A.100 B.45 C.50 D.9

19、0 14.對(duì)有n個(gè)記錄的表作快速排序,在最壞情況下,算法的時(shí)間復(fù)雜度是_。 A.O(n) B.O(n2) C.O(nlog2n) D.O(n3) 15.一個(gè)排序算法時(shí)間復(fù)雜度的大小_有關(guān)。 A.與所需比較關(guān)鍵字的次數(shù) B.與該算法的穩(wěn)定性 C.不與所需移動(dòng)記錄的數(shù)目 D.與所需輔助存儲(chǔ)空間的大小 二、畫(huà)圖題(每小題4分,共20分) 1.依次輸入元素X,Y,Z, 插入到一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫(huà)出空的鏈?zhǔn)綏：兔坎迦胍粋€(gè)元素之后的 鏈?zhǔn)綏Ｊ疽鈭D。讀書(shū)破萬(wàn)卷 下筆如有神 2.試用雙親表示法畫(huà)出下列樹(shù)T的存儲(chǔ)結(jié)構(gòu)圖。 3.試畫(huà)出有3行4列元素的二維數(shù)組B的以列序?yàn)橹餍虻捻樞虼鎯?chǔ)結(jié)構(gòu)圖。 4.試畫(huà)出下列圖的鄰接表。 圖 共5頁(yè)第2頁(yè) 5.已知一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列分別是： I,A,B,E,F,G,C,H,D 和 A,E,F,B,I,G,H,C,D 試畫(huà)出該二叉樹(shù)。 三、求解問(wèn)題(每