for ( j=N*N; j>i; j-- ) A += B; }
else {
for ( i=0; ii; j-- ) A += B; }
【2，1，3】测试例1.3中秦九韶算法与直接法的效率差别。令i x x f i i /1)(100
1∑=+=，计算)1.1(f 的值。利用clock()函数得到两种算法在同一机器上的运行时间。 【3，1，3】 试分析最大子列和算法1.3的空间复杂度。 【4，1，3】试给出判断N 是否为质数的)(N O 的算法。
【5，2，2】请编写程序，输入整数n 和a ，输出S=a+aa+aa a+…＋aa…a(n 个a)的结果。
【6，2，3】请编写递归函数，输出123..n 的全排列（n 小于10）,并观察n 逐步增大时程序的运行时间。
【7，3，2】 给定一个顺序存储的线性表L = (1a , 2a , ⋯, n a )，请设计一个算法
2
删除所有值大于min 而且小于max 的元素。
【8，3，2】给定一个顺序存储的线性表L = (1a , 2a , , n a )，请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。
【9，3，3】 如果有1、2、3、4、5按顺序入栈，不同的堆栈操作（pop, push ）顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？ 【10，3，2】请编写程序将中缀表达式转换为后缀表达式。
【11，4，3】设二叉树的存储结构如下：
其中根结点的指针值为6，Lchild ，Rchild 分别为结点的左、右孩子指针域，data 为数据域。
（1） 画出二叉树的逻辑结构。
（2）写出该树的前序、中序和后序遍历的序列。
【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意4个。
1 2 3 4 5 6 7 8 9 10 Lchild 0 0 2 3 7 5 8 0 10 1 data J H F D B A C E G I Rchild
9
4
3
【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请回答： （1）画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）； （2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）；
【14，4，6】 假设一个文本使用的字符集为{a,b,c,d,e,f,g}, 字符的哈夫曼编码依次为{0110，10，110，111，00，0111，010}。
（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符； （2）若这些字符在文本中出现的频率分别为：{3,35,13,15,20,5,9}，求该哈夫曼树的带权路径长度。
【15，5，3】用公式5.6计算一下你的身份证号码的散列值是多少。
【16，5，4】设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为：H(key) = key % 17，采用平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。
【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H （key ）=（key×3）mod TableSize ，要求装入因子为0.7。
4
【18，6，3】已知一个无向图的顶点集为{V 0，V 1，…，V 7}，其邻接矩阵如下所示：
V 0
1 0 1 1 0 0 0 V 1 1 0 1 0 1 0 0 0 V
2 0 1 0 0 0 1 0 0 V
3 1 0 0 0 0 0 1 0 V
4 1 1 0 0 0 0 1 0 V
5 0 0 1 0 0 0 0 0 V
6 0 0 0 1 1 0 0 1 V
7 0 0 0 0 0 0 0 1
(1) 画出该图的图形；
(2) 给出从V 0出发的深度优先遍历序和广度优先遍历序。 【19，6，3】已知有向图如右图所示，请给出该图的 （1） 每个顶点的入度和出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表；
（5） 各个强连通分量。
【20，6，3】试利用Dijkstra 算法求下图在从顶点A 到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。
【21，6，3】给出如下图所示的具有7个结点的网G 。请：
（1） 画出该网的邻接矩阵；
（2） 采用Prim 算法，从4号结点开始，给出该网的最小生成树（画出Prim 算法
的执行过程及最小生成树的生成示意图）。
5
【22，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请分别用简单选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。
【23，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请分别用堆排序、快速排序和归并排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。
【24，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请用3种不同的增量序列分别进行希尔排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。
0 1
2 3
6 4
5
1 6
4 4 3
2 3 1 5 7 2 5
