北大數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)踐考前練習(xí)題

1. 編一C程序，它能讀入集合A的一串整數(shù)（以-9999為結(jié)束標(biāo)記，整數(shù)個(gè)數(shù)小于1000）和集合B的一串整數(shù)（以-9999為結(jié)束標(biāo)記，整數(shù)個(gè)數(shù)小于1000），計(jì)算出A與B的交集，并以由小到大的次序輸出A與B的交集中的所有整數(shù)（輸入整數(shù)時(shí)，相鄰的兩個(gè)用空格隔開。為A或B輸入時(shí)，同一個(gè)數(shù)可能出現(xiàn)多次，而A與B的交集中同一個(gè)數(shù)不能出現(xiàn)多次）。

（注：程序的可執(zhí)行文件名必須是 e1.exe）。

2. 編一C程序，它能根據(jù)讀入的數(shù)據(jù)構(gòu)造有向圖G，并輸出G的DFS遍歷序列（從V0開始），圖的輸入形式為n V0 Vi0 V1 Vi1 V2 Vi2……Vi Vin -1 -1（-1，-1為輸入結(jié)束標(biāo)記，其余的值都 =0且 n），它們都是整數(shù)，且100 n 0.（注：程序的可執(zhí)行文件名必須是 e2.exe）。

3. 編一C程序，它能讀入一串整數(shù)（以-9999為結(jié)束標(biāo)記）并對它們進(jìn)行從小到大直接插入排序，同時(shí)輸出排序時(shí)對這些整數(shù)進(jìn)行比較的總次數(shù)（輸入整數(shù)時(shí)，相鄰的兩個(gè)用空格隔開，整數(shù)個(gè)數(shù) 2000）。

（注：程序的可執(zhí)行文件名必須是 e3.exe）。

4. 編一C程序，它能讀入集合A的一串整數(shù)（以-9999為結(jié)束標(biāo)記，整數(shù)個(gè)數(shù)小于1000）和集合B的一串整數(shù)（以-9999為結(jié)束標(biāo)記，整數(shù)個(gè)數(shù)小于1000），計(jì)算并以從小到大的次序輸出A-B的所有元素（為A或B輸入時(shí)，同一個(gè)數(shù)可能出現(xiàn)多次，而A與B的差集中同一個(gè)數(shù)不能出現(xiàn)多次）。

（注：程序的可執(zhí)行文件名必須是 e4.exe）。

5. 編一C程序，它能根據(jù)讀入的數(shù)據(jù)構(gòu)造有向圖G，圖的輸入形式為n V0 Vi0 V1 Vi1 V2 Vi2……Vi Vin -1 -1（-1 -1是輸入結(jié)束標(biāo)記），它們都是整數(shù)，且100 n 0，其余的值都 =0且 n，輸出圖G的拓?fù)湫蛄小?/p>

（注：程序的可執(zhí)行文件名必須是 e5.exe）

6. 編一C程序，它能讀入一串整數(shù)（不多于2000，并以-9999為結(jié)束標(biāo)記）及另一整數(shù)n，判斷n是否在那一串?dāng)?shù)中，若是，則輸出yes及該數(shù)在那串整數(shù)中的序號（序號從0開始），否則輸出no.（輸入整數(shù)時(shí)，相鄰的兩個(gè)用空格隔開）。

（注：程序的可執(zhí)行文件名必須是 e6.exe）。

7. 編一C程序，它能把讀入的整數(shù)依次插入到一個(gè)初始為空的二叉排序樹中，一直讀到-9999為止。再從該二叉排序樹中刪除讀入的第三個(gè)整數(shù)，之后輸出該二叉排序樹的前序序列、中序序列及葉結(jié)點(diǎn)的個(gè)數(shù)。（輸入時(shí)，兩個(gè)相鄰的整數(shù)用空格隔開）。

（注：程序的可執(zhí)行文件名必須是 e7.exe，存于你的賬號或其debug目錄下）。

8. 編一C程序，它能根據(jù)輸入的二叉樹前序和中序序列來構(gòu)造該二叉樹，并能輸出該二叉樹的后序序列和該二叉樹度為1的結(jié)點(diǎn)的個(gè)數(shù)。（輸入次序是：表示前序序列的字符串、表示中序序列的字符串）。

（注：程序的可執(zhí)行文件名必須是 e8.exe，存于你的賬號或其debug目錄下）。