数据结构习题1

存储的原则是只存储非零元。

三、计算题

(1) 228 (2) 1282 (3) 1072 (4) 1276 四、设计题

1． void proc1(matrix A) /*第(1)题解*/

{

int s=0,i,j;

for(i=0;i

for(i=0;i

for(j=0;j

for(j=0;j

s=s+A[m][j];

s=s-A[0][0]-A[0][n-1]-A[m-1][0]-A[m-1][n-1]; /*减去4个角的重复元素值*/ printf(\}

void proc2(matrix A) /*第(2)题解*/ {

int s=0,i,j; i=0;

while(i

j=0; while(j

s=s+A[i][j];

j=j+2; /*跳过一列*/ }

i=i+2; /*跳过一行*/ }

printf(\}

void proc3(matrix A) /*第(2)题解*/ {

int i,s;

if(m!=n) printf(\ else { s=0;

for(i=0;i

s=s+A[i][i]; /*求第一列对角线之和*/ for(i=0;i

16

s=s+A[n-i-1][i]; /*累加第二条对角线之和*/ printf(\ } }

2． void mmult(){

matrix A; int i,s;

for(i=0;i<4;i++) for(j=0;j<4;j++) scanf(\ s=1;

for(i=0;i<4;i++) s=s*A[i][i];

for(i=0;i<4;i++) s=s*A[3-i][i]; printf(\两条对角线元素之积：%d\\n\}

习题6参考答案

一、选择题

1. B 2. A 3. A 4. B 5. B 6. D 7. C 8. A 9. D 二、设计题 1．答案略。

2. 解：给定二叉树的先序序列和中序序列可以重构出该二叉树；给定二叉树的先序序列和后序序列则不能构造出该二叉树。反例为：

a a

b b

先序序列ab，后序序列ba可对应两棵二叉树。 3.解：

(1)mk-1

(2)(mh-1)/(m-1)

(3)i=1时,该结点为根,无双亲结点;否则其双亲结点的编号为(i+m-2)/m (4)编号为i的结点的第j个孩子结点(若有)的编号为i*m+(j-(m-1)) 4. 解：

52 23 10 5 2

3

17

29 13 6

14 7 15 8

5.解：

void Release(BiTree T){

if (T!=NULL){ Release(T->lchild); }

Release(T->rchild); free(T);

} 6. 解：

int Depth(BiTree T){ if (!T) return 0; } 7.解：

void Level(BiTree b,BiTree p, int *h,int lh){ if (b==NULL) *h=0; }

else if(p==b) *h=lh; else { }

Level(p,b->lchild,h,lh+1); if(*h==-1) Level(p,b->rchild,h,lh+1); else { }

// 如果T为空，则其深度为0

// 若T不空返回其子树中深度较大值加1

if ( Depth(T->lchild) >= Depth(T->rchild)) return Depth(T->lchild)+1; else return Depth(T->rchild)+1;

习题7参考答案

一、选择题

1. C 2. D 3. A 4. B 5. B 6. D 7. A 8. D 9. C 10. C 11. D 12. C

二、简答题

1. 对于无向图，如果在深度优先遍历中遇到回边，则必定存在环。对于有向图，如果从有向图的某个顶点v出发的遍历，在DFS(v)结束之前出现了一条从顶点u指向v的回边，则此有向图必定存在环。因为u在深度优先生成树上是v的子树，即存在u到v的路径，现在又出现一条从u指向v的弧，则它们必然构成一条回路。

2. 用邻接矩阵表示图时，矩阵元素的个数与顶点个数无关；但和边数有关。

习题8参考答案

18

一、选择题

1. C 2. D3. B 4. A 5. B 6. D 7. C 二、简答题

1. 答：静态查找是指只在数据元素集合中查找是否存在关键字等于某个给定关键字的数据元素。动态查找除包括静态查找的要求外，还包括在查找过程中同时插入数据元素集合中不存在的数据元素，或者从数据元素集合中删除已存在的某个数据元素的要求。

2. 答：为了确定要查找的记录位置，与给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度ASL(Average Search Length)。对于含有n个记录的表，平均查找长度的计算公式为：

nASL?

其中，Pi为查找第i个元素的概率。 三、设计题 Dec 1．解：

2.解：

(1) m的取值为13 (2)

地址 key

0 1 5 2 6 3 5 4 7 Apr

Aug

Feb

Nov June July Jan

Mar

May

Oct

?PCii?1i

Sept

5 10 6 7 8 9 10 11 12 11 51 80 75 88 90 102 113 126 11 47 35 23 探测次数 6 习题9参考答案

一、选择题

1. B 2. D 3. B 4. C 5. D 6. C 二、设计题

1. 解：

int QuickSort(SeqList R,int j,int low,int high){ //对R[low..high]快速排序 int pivotpos; //划分后的基准记录的位置

if(low

if (pivotpos==j) return r[j];

19