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

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

2、? 7.與中綴表達(dá)式a+b*c-d等價的前綴表達(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.對長度為10的表作選擇(簡單選擇)排序,共需比較_次關(guān)鍵字。 A.45 B.90 C.55 D.110 10.對n個元素的表作快速排序,在最壞情況下,算法的時間復(fù)雜度為_。 A.O(log2 n) B.O(nlog2 n) C.O(n

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

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

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

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

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

8、t1.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)計(專升本)數(shù)據(jù)結(jié)構(gòu)試題(模B)2004-5-1 一、單項(xiàng)選擇題(從下列各題四個備選答案中選出一個正確答案,將其代號 (A,B,C,D)寫在下表中,答題寫在其它地方無效；每小題1分,共11分) 題號 1 2 3 4 5 6 7 8 9 10 11 答案 。_數(shù)據(jù)的基本單位是1.讀書破萬卷 下筆如有神 A.結(jié)點(diǎn) B.數(shù)據(jù)元素 C.數(shù)據(jù)類型

9、D.數(shù)據(jù)項(xiàng) 2.下列算法suanfa1中語句硜砽月；的執(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.log2(n)+1 B.log2(n)-1 C.?log2(n)-1? D.?log2(n)+1? 9.與中綴表達(dá)式a-b/c+d等價的前綴表達(dá)式是_。 A.-a+/bcd B./-+bcd C.+-/bcd D.abcd-/+ 10.對有3600個記錄的索引順序表(分塊表)進(jìn)行查找,最理想的塊長為_。 A.1800 B.60 C.1200 D.log2 3600 共5

10、頁第1頁 11.對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個元素之間插入一個元素, 共需移動 _ 個元素(1in)。 3.一個字符串中 _ 稱為該串的子串。 4.樹中結(jié)點(diǎn)A的 _ 稱為結(jié)點(diǎn)A的度。 5.一棵深度為4的二叉樹最多有 _ 個結(jié)點(diǎn)。 。_ 邊的總數(shù)最多為,個頂點(diǎn)的無向圖10具有6.讀書破萬卷 下筆如有神 7.順序查找n個

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

12、法畫出下列樹的存儲結(jié)構(gòu)圖。)(3.試用孩子兄弟左孩子右兄弟 樹 讀書破萬卷 下筆如有神 4.試畫出下列有向網(wǎng)的逆鄰接表。 有向網(wǎng) 共5 頁第3頁 五、求解下列問題 (每小題6分,共24分) 1.已知二叉樹的前序遍歷序列和中序遍歷序列分別是： 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)試畫出插入完成之后的二叉排序樹；(2)若查找元素17,它將依次與二叉排序樹中哪些元素比較大小?(3)假設(shè)每個元素的查找概率

13、相等,試計算該樹的平均查找長度 ASL；(4)對該樹進(jìn)行中序遍歷,試寫出中序遍歷序列。 3.試用權(quán)集合4,6,5,12,2,1,13,構(gòu)造赫夫曼(Huffman)樹,(1)列出構(gòu)造過程, (2)分別計算該赫夫曼樹的路徑長度和帶權(quán)路徑長度。 4.找出下面網(wǎng)絡(luò)的最小生成樹: 共5 頁第4頁 六、執(zhí)行下面的C程序,指出輸出結(jié)果。(8分) #include #include 讀書破萬卷 下筆如有神 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è)計(算法中必須有注釋,每小題8分,共16分) 1.設(shè)n個元素的線性

15、表順序存儲在一維數(shù)組 st1.maxlen 的前n個位置上,試寫出算法:刪除表中第i(1in)個元素。 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 8 9 10 11 12 12 14 15 題號讀書破萬卷 下筆如有神 答案 1.由_組成的集合是一

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

17、(假定無第0行第0列元素) A.4072 B.4104 C.4102 D.4074 6.設(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,b 7._ 又是一棵滿二叉樹。 A.二叉排序樹 B.深度為5有31個結(jié)點(diǎn)的二叉樹 C.有15個結(jié)點(diǎn)的完全二叉樹 D.哈夫曼(Huffman)樹 8.深度為k的滿二叉樹有_個分枝結(jié)點(diǎn)。 A.2k-1 B.2k-1-1 C.2k+1 D.2k-1+1 9.具有n(n0)個結(jié)點(diǎn)的完全二叉樹的深度為_。 A.log2(n) B.?log2(n)? +1 C.log2(

18、n+1) D.?log2(n+1)? 10.折半查找20個記錄的有序表,若查找失敗,比較關(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.線性探測再散列法 C.直接地址法 D.鏈地址法 共5頁第1頁 13.對有10個記錄的表作簡單選擇排序,需要比較_次關(guān)鍵字。 A.100 B.45 C.50 D.9

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