数据结构与算法离线作业2014春

【26，4，4】n个结点的二叉排序树的最大深度是 n ，最小深度为 [log2n]+1 。

【27，4，3】下列二叉树的中序遍历序列是____DBNGOAEC_______;后序遍历序列是_______DNOGBECA_______________________________。

【28，5，3】设HASH表的大小为 n (n=10), HASH函数为 h(x)=x % 7, 如果二次探测再散列方法Hi=(H(key)+di) mod 10 (di = 12,22,32,…,)解决冲突，在HASH表中依次插入关键字{1,14,55,20,84,27}以后，关键字1、20和27所在地址的下标分别是 1 、 7__ 和 5 。插入上述6个元素的平均比较次数是 2 。

【29，6，3】设无权图G的邻接矩阵为A，若（vi,vj）属于图G的边集合，则对应元素A[i][j]等于 1 ，设无向图G的邻接矩阵为A，若A[i][j]等于0，则A[j][i]等于 0 。

【30，6，3】若一个图用邻接矩阵表示，则删除从第i个顶点出发的所有边的方法是 矩阵第i行全部置为零 。

【31，6，2】设一个图

G={V,{A}},V={a,b,c,d,e,f},A={,,,,,,}。那么顶点e的入度是 2 ；出度是 1 ；通过顶点f的简单回路有 2 条；就连通性而言，该图是 强连通 图；它的强连通分量有 1 个；其生成树可能的最大深度是 5 。

【32，10，1】排序过程一般需经过两个基本操作，它们是 比较 和 移动 。

5

【33，10，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较 3 次。

【34，10，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有 希尔排序、快速排序、堆排序 。

6

二、综合题（选自教材《数据结构》各章习题，采用word文件格式上传）

【1，1，3】试分析下面一段代码的时间复杂度：

if ( A > B ) {

for ( i=0; i

for ( j=N*N; j>i; j-- ) A += B; }

else {

for ( i=0; ii; j-- ) A += B; }

If A>B为真，则for语句的外循环N次，内循环为N*N-N=N（N-1）次，因此时间复杂度为O(N* N（N-1）)，也就是N的三次方。

If A>B为假，则for语句的外循环2N次，内循环为2*N-N=N次，因此时间复杂度为O（2N*N），也就是N的平方。

整段取大的，时间复杂度就是N立方。

【2，1，3】测试例1.3中秦九韶算法与直接法的效率差别。令f(x)?1??i?1xi/i，计算f(1.1)的值。利用clock()函数得到两种算法在同一机器上的运行时间。 直接法：0.1μs 秦九韶算法：0.04μs

【3，1，3】 试分析最大子列和算法1.3的空间复杂度。 【4，1，3】试给出判断N是否为质数的O(N)的算法。

int sushu(int N) { int i; int flag=1;

if (N==1) return false; if (N==2) return true; for (i=2;i<=sqrt(N);i++)

{ if (N%i==0){ flag=0 ; break; }}

7

100

return flag; }

【5，2，2】请编写程序，输入整数n和a，输出S=a+aa+aaa+…＋aa…a(n个a)的结果。

#include\int main() {

int a,b,n,i,s=0;

scanf(\ b=a;

for(i=1;i<=n;i++) {

s+=a;

a=a*10+b; }

printf(\}

【6，2，3】请编写递归函数，输出123..n的全排列（n小于10）,并观察n逐步增大时程序的运行时间。

#include #define N 8 int n = 0;

void swap(int *a, int *b) {

int m;

m= *a; *a = *b; *b = m; }

void perm(int list[], int k, int m) {

int i; if(k > m) {

for(i = 0; i <= m; i++)

printf(\ printf(\

8