北大数据结构上机实践考前练习题

1. 编一C程序，它能读入集合A的一串整数（以-9999为结束标记，整数个数小于1000）和集合B的一串整数（以-9999为结束标记，整数个数小于1000），计算出A与B的交集，并以由小到大的次序输出A与B的交集中的所有整数（输入整数时，相邻的两个用空格隔开。为A或B输入时，同一个数可能出现多次，而A与B的交集中同一个数不能出现多次）。

（注：程序的可执行文件名必须是 e1.exe）。

2. 编一C程序，它能根据读入的数据构造有向图G，并输出G的DFS遍历序列（从V0开始），图的输入形式为n V0 Vi0 V1 Vi1 V2 Vi2……Vi Vin -1 -1（-1，-1为输入结束标记，其余的值都 =0且 n），它们都是整数，且100 n 0.（注：程序的可执行文件名必须是 e2.exe）。

3. 编一C程序，它能读入一串整数（以-9999为结束标记）并对它们进行从小到大直接插入排序，同时输出排序时对这些整数进行比较的总次数（输入整数时，相邻的两个用空格隔开，整数个数 2000）。

（注：程序的可执行文件名必须是 e3.exe）。

4. 编一C程序，它能读入集合A的一串整数（以-9999为结束标记，整数个数小于1000）和集合B的一串整数（以-9999为结束标记，整数个数小于1000），计算并以从小到大的次序输出A-B的所有元素（为A或B输入时，同一个数可能出现多次，而A与B的差集中同一个数不能出现多次）。

（注：程序的可执行文件名必须是 e4.exe）。

5. 编一C程序，它能根据读入的数据构造有向图G，图的输入形式为n V0 Vi0 V1 Vi1 V2 Vi2……Vi Vin -1 -1（-1 -1是输入结束标记），它们都是整数，且100 n 0，其余的值都 =0且 n，输出图G的拓扑序列。

（注：程序的可执行文件名必须是 e5.exe）

6. 编一C程序，它能读入一串整数（不多于2000，并以-9999为结束标记）及另一整数n，判断n是否在那一串数中，若是，则输出yes及该数在那串整数中的序号（序号从0开始），否则输出no.（输入整数时，相邻的两个用空格隔开）。

（注：程序的可执行文件名必须是 e6.exe）。

7. 编一C程序，它能把读入的整数依次插入到一个初始为空的二叉排序树中，一直读到-9999为止。再从该二叉排序树中删除读入的第三个整数，之后输出该二叉排序树的前序序列、中序序列及叶结点的个数。（输入时，两个相邻的整数用空格隔开）。

（注：程序的可执行文件名必须是 e7.exe，存于你的账号或其debug目录下）。

8. 编一C程序，它能根据输入的二叉树前序和中序序列来构造该二叉树，并能输出该二叉树的后序序列和该二叉树度为1的结点的个数。（输入次序是：表示前序序列的字符串、表示中序序列的字符串）。

（注：程序的可执行文件名必须是 e8.exe，存于你的账号或其debug目录下）。