数据结构习题集(c语言版严蔚敏)第一二三章

《数据结构习题集(c语言版严蔚敏)第一二三章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章绪论1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。1.3设有数据结构(D,R)，其中，，试按图论中图的画法惯例画出其逻辑结构图。1.4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。1.5试画出与下列程序段等价的框图。(1)product=1;i=1;while(i<=n){product*=i;i++;}(2)i=0;do{i++;}while((i!=n)&&(a[i]!=x));

2、(3)switch{casex

3、设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：(1)i=1;k=0;while(i<=n-1){@k+=10*i;i++;}(2)i=1;k=0;do{@k+=10*i;i++;}while(i<=n-1);(3)i=1;k=0;while(i<=n-1){i++;@k+=10*i;}(4)k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)@k++;}(5)for(i=1;i<=n;i++){for(j=1;j<=i;j++){for(k=1;k<=j;k++)@x+=delta;}(6)i=1;j=0;while(i+j<=n){@i

4、f(i>j)j++;elsei++;}(7)x=n;y=0;//n是不小于1的常数while(x>=(y+1)*(y+1)){@y++;}(8)x=91;y=100;while(y>0){@if(x>100){x-=10;y--;}elsex++;}1.9假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。intTime(intn){count=0;x=2;while(x

5、00多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。1.12设有以下三个函数：，，请判断以下断言正确与否：(1)f(n)是O(g(n))(2)h(n)是O(f(n))(3)g(n)是O(h(n))(4)h(n)是O(n3.5)(5)h(n)是O(nlogn)1.13试设定若干n值，比较两函数和的增长趋势，并确定n在什么范围内，函数的值大于的值。1.14判断下列各对函数和，当时，哪个函数增长更快？(1)，(2)，(3)，(4)，1.15试用数学归纳法证明：(1)(2)

6、(3)(4)1.16试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值1.17已知k阶斐波那契序列的定义为，，…，，；，试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。1.18假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为项目名称性别校名成绩得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。1.19试编写算法，计算的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为maxin

7、t，则当n>arrsize或对某个，使时，应按出错处理。注意选择你认为较好的出错处理方法。1.20试编写算法求一元多项式的值的值，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为，和，输出为。第2章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。2.2填空题。(1)在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。(2)顺序表中逻辑上相邻的元素的物理位置紧邻。单链表中逻辑上相邻的元素