下载文档原格式
Chap1一、选择题1. 算法的计算量的大小称为计算的（B ）。
A．效率 B. 复杂性 C. 现实性 D. 难度2.计算机算法指的是（1） C，它必须具备（2）B这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性3. 下面关于算法说法正确的是（ D ）。
A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性(基本运算执行有限次)是指指令不能有二义性D. 以上几个都是错误的4．从逻辑上可以把数据结构分为（ C ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构5．以下数据结构中，哪一个是线性结构（ D ）？A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串6．在下面的程序段中，对x的赋值语句的频度为（ C ）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)7．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（C）。
A. O（n）B. O(nlogn)C. O(n3)D. O(n2)8．以下哪个数据结构不是多型数据类型（D）A．栈 B．广义表 C．有向图 D．字符串（始终是字符型的，不会存在其他类型）9．以下数据结构中，（A）是非线性数据结构A．树 B．字符串 C．队 D．栈二、判断题1．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
( A )2．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。
第一章习题一、问答题1.什么是数据结构？2.叙述四类基本数据结构的名称与含义。
3.叙述算法的定义与特性。
4.叙述算法的时间复杂度。
5.叙述数据类型的概念。
6.叙述线性结构与非线性结构的差别。
7.叙述面向对象程序设计语言的特点。
8.在面向对象程序设计中，类的作用是什么？9.叙述参数传递的主要方式及特点。
10.叙述抽象数据类型的概念。
二、判断题（在各题后填写“√”或“×”）1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。
（）2.算法就是程序。
（）3.在高级语言（如C或 PASCAL）中，指针类型是原子类型。
（）三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;四、试编写算法，求一元多项式Pn (x)=a+a1x+a2x2+a3x3+…anx n的值Pn(x)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。
注意：本题中的输入ai (i=0,1,…,n),x和n，输出为Pn(x)。
通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。
（2）通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。
实习题设计实现抽象数据类型“有理数”。
基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。
第一章答案1.3计算下列程序中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/61.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。
《数据结构基础教程》习题及解答数据结构基础教程习题及解答第一章：数据结构简介1.1 什么是数据结构？数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，包括数据的逻辑结构、物理结构和数据元素之间的运算。
1.2 数据的逻辑结构有哪些？数据的逻辑结构包括线性结构、树形结构和图状结构。
1.3 数据的物理结构有哪些？数据的物理结构包括顺序存储结构和链式存储结构。
1.4 数据结构的主要目标是什么？数据结构的主要目标是提高数据的存储效率和运算效率。
第二章：线性表2.1 线性表的定义线性表是由n(≥0)个数据元素组成的有限序列。
线性表是一种常见的数据结构，常用的实现方式包括数组和链表。
2.2 线性表的顺序存储结构线性表的顺序存储结构是将线性表中的元素存储在连续的存储空间中，通过元素在内存中的物理位置来表示元素之间的关系。
2.3 线性表的链式存储结构线性表的链式存储结构是通过指针将线性表中的元素连接在一起，每个元素包括数据域和指针域。
2.4 线性表的基本操作包括初始化线性表、插入元素、删除元素、查找元素等。
第三章：栈与队列3.1 栈的定义与特性栈是一种具有后进先出特性的线性表，只允许在一端进行插入和删除操作，被称为栈顶。
3.2 栈的顺序存储结构和链式存储结构栈的顺序存储结构和链式存储结构与线性表的存储结构类似，不同之处在于栈只允许在一端进行插入和删除操作。
3.3 栈的应用栈在表达式求值、函数调用和递归等场景中有广泛应用。
3.4 队列的定义与特性队列是一种具有先进先出特性的线性表，允许在一端插入元素，在另一端删除元素。
3.5 队列的顺序存储结构和链式存储结构队列的顺序存储结构和链式存储结构与线性表的存储结构类似，不同之处在于队列允许在一端插入元素，在另一端删除元素。
3.6 队列的应用队列在模拟排队系统、操作系统进程调度等场景中有广泛应用。
第四章：树与二叉树4.1 树的基本概念树是由n(≥0)个节点组成的有限集合，其中有一个称为根节点，除了根节点之外的其余节点被分为m(m≥0)个互不相交的集合，每个集合本身又是一棵树。
数据结构第一章课后习题与答案资料1.什么是数据结构？答：数据结构是指数据对象以及数据对象之间的关系、操作和约束的一种逻辑结构。
它关注如何将数据以及数据之间的关系组织起来，以便更高效地进行操作和使用。
2.数据结构的分类有哪些？答：数据结构可以分为线性数据结构和非线性数据结构。
线性数据结构包括数组、链表、栈和队列；非线性数据结构包括树和图。
3.什么是算法？答：算法是指解决特定问题的一系列步骤和规则。
它可以描述为一个有限的指令集，用于将输入数据转换为输出结果。
4.算法的特征有哪些？答：算法具有以下特征：•输入：算法必须有输入，可以是零个或多个。
•输出：算法必须有输出，可以是零个或多个。
•有穷性：算法必须在有限步骤内结束。
•确定性：算法的每一步骤必须明确且无歧义。
•可行性：算法的每一步骤必须可行，即可以执行。
5.算法的时间复杂度是什么？如何表示时间复杂度？答：算法的时间复杂度是指算法执行所需的时间。
它通常用大O符号表示。
常见的时间复杂度有O(1)、O(n)、O(n^2)等。
6.算法的空间复杂度是什么？如何表示空间复杂度？答：算法的空间复杂度是指算法执行所需的额外空间。
它通常用大O符号表示。
常见的空间复杂度有O(1)、O(n)、O(n^2)等。
7.什么是数据的逻辑结构？答：数据的逻辑结构是指数据对象之间的关系。
常见的逻辑结构有线性结构、树形结构和图形结构。
8.什么是数据的存储结构？答：数据的存储结构是指数据在计算机内存中的表示方式。
常见的存储结构有顺序存储结构和链式存储结构。
9.顺序存储结构和链式存储结构有什么区别？答：顺序存储结构将数据存储在一块连续的内存空间中，可以随机访问元素，但插入和删除操作需要移动大量元素。
链式存储结构将数据存储在不连续的内存空间中，通过指针相连，插入和删除操作只需要修改指针，但访问元素需要遍历链表。
10.数组和链表的区别是什么？答：数组是一种顺序存储结构，元素在内存中连续存储，可以通过下标直接访问元素；链表是一种链式存储结构，元素在内存中不连续存储，通过指针相连。
1. 填空（1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
【解答】数据元素（2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。
【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。
（3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。
【解答】集合，线性结构，树结构，图结构（4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。
【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系（5）算法具有五个特性，分别是（）、（）、（）、（）、（）。
【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性（6）在一般情况下，一个算法的时间复杂度是（）的函数。
【解答】问题规模（7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。
【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。
2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。
A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。
⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
则表示该遗产继承关系的最合适的数据结构应该是（）。
A 树B 图C 线性表D 集合【解答】B【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。
⑶算法指的是（）。
数据结构课后习题及解析第一章第一章数据结构课后习题及解析数据结构是计算机科学中的重要基础知识，对于理解和解决实际问题起着关键的作用。
课后习题是巩固学习效果、帮助理解和掌握数据结构概念的重要途径。
本文将针对数据结构第一章的课后习题进行解析，帮助读者更好地理解和掌握相关概念和知识。
1. 为什么数据结构和算法是计算机科学的核心？数据结构和算法是计算机科学的核心，主要有以下几个原因：首先，数据结构和算法是解决实际问题的基础。
计算机科学的目标是通过编程实现问题的求解。
而数据结构和算法作为实现的基础，能够帮助我们对问题进行合理的建模和求解。
其次，数据结构和算法对程序性能有着重要影响。
在同一种情况下，采用不同的数据结构和算法实现同一个功能，其性能可能有很大的差异。
熟练掌握数据结构和算法，能够帮助我们选择最优的实现方式，提高程序的性能。
最后，数据结构和算法是计算机科学领域的核心知识。
无论是在学术研究还是工程实践中，数据结构和算法都是必备的知识。
熟练掌握数据结构和算法，对于深入理解计算机科学的理论和方法具有重要意义。
2. 什么是数据结构？数据结构是计算机中存储、组织和管理数据的方式。
它包括数据元素之间的关系、数据操作和存储结构等几个方面。
在数据结构中，数据元素是指存储数据的基本单位，可以是一个整数、一个字符或者一个记录。
数据元素之间的关系包括线性关系（如线性表）、非线性关系（如树和图）等。
数据操作则是指对数据的基本操作，如插入、删除、查找等。
存储结构则是指数据在计算机内存中的存放形式，可以是顺序存储结构或链式存储结构。
3. 请列举常见的数据结构类型。
常见的数据结构类型主要包括以下几种：- 数组：是最简单的数据结构，它由一组元素组成，可以通过索引来访问元素。
- 链表：是一种非连续存储的数据结构，其元素通过指针链接在一起。
- 栈：是一种具有特殊操作规则的线性结构，遵循先进后出的原则。
- 队列：是一种具有特殊操作规则的线性结构，遵循先进先出的原则。
数据结构（大专）第一章习题解答第一章绪论1．2 设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为QUAdratic，该类型的数据部分为三个系数项a、b和c，操作部分为：1.初始化数据成员a、b和c（假定用记录类型Quadratic定义数据成员），每个数据成员的默认值为0。
Qiadratic InitQuadratic(float aa=0, float bb=0, float cc=0);解：Quadratic InitQuadratic(float aa, float bb, float cc)｛Quadratic q;q·a=aa;q·b=bb;q·c=cc;return q;｝2.做两个多项式加法，即使对应的系数相加，并返回相加结果。
解：Quadratic Add(Quadratic q1,Quadratic q2);｛Quadratic q;q·a=q1·a+q2·a;q·b=q1·b+q2·b;q·c=q1·c+q2·c;retirn q;｝3.据给定x的值计算多项式的值。
float Eval(Quadratic q,float x);解：float Eval(Quadratic q, float x)｛return(q·a*x*x+q·b*x+q·c);｝4.计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是二次方程（即a= =0）这三种情况都要返回不同的整数值，以便调用函数做不同的处理。
int Root(Quadratic q, float& r1, float& r2);解：int Root (Quadratic q, float& r1, float& r2)｛if(q·a= =0) return –1;float x =q·b*q·b –4*q·a*q·c;if(x﹥=0)｛r1=(float) (-q·b+sqrt(x))/ (2*q·a);r2=(float) (-q·b-sqrt(x))/ (2*q·a);return 1;｝elsereturn 0;｝5.按照ax **2+bx+c的格式(x2用x **2表示)输出二次多项式，在输出时在注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。
《数据结构（C语言）》严蔚敏习题参考答案第一章绪论1.8 分析下列各算法的时间复杂度：（1）void prime(int n){/* 判断n是否是素数 */for (i=2; ((n%i)!=0)&&(i<sqrt(n)); i++);if i>sqrt(n) printf("%d is a prime number", n)else printf("%d is not a prime number", n);}/* prime */最坏情况下O(sqrt(n))(2) float sum1(int n){/* 计算1！+2！+…+n! */p=1; sum1=0;for (i=1; i<=n; ++i){p=p*i; sum1=sum1+p}}/* sum1 */O(n)(3) float sum2(int n){/* 计算1！+2！+…+n! */sum2=0;for (i=1; i<=n; ++i){p=1;for (j=1; j<=i; ++j) p=p*j;sum2=sum2+p;}}/* sum2 */O(n2)(4) void sort(int a[],int n){/* 将数组a中的元素按自小到大的顺序排列 */ for (i=1; i<=n-1; ++i){k=i;for (j=i+1; j<=n; ++j) if (a[j]<a[k]) k=j;if (k<>j) {x=a[i];a[i]=a[k];a[k]=x;}}}/* sort */O(n2)（5）void matrimult(a[m][n],b[n][l],c[m][l],int m,int n,int l){ /* a为m×n阶的矩阵，b为n×l阶的矩阵，c为m×l阶的矩阵 */ /* 计算c=a*b */for (i=1; i<=m; ++i)for (j=1; j<=l; ++j)c[i,j]=0;for (i=1; i<=m; ++i)for (j=1; j<=l; ++j)for (k=1; k<=n; ++k)c[i,j]=c[i,j]+a[i,k]*b[k,i];}/* matrimult */O(n3)1.16void print_descending(int x,int y,int z)//按从大到小顺序输出三个数{scanf("%d,%d,%d",&x,&y,&z);if(x<y) x<->y; //<->为表示交换的双目运算符,以下同if(y<z) y<->z;if(x<y) x<->y; //冒泡排序printf("%d %d %d",x,y,z);}//print_descending1.17Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f{int tempd;if(k<2||m<0) return ERROR;if(m<k-1) f=0;else if (m==k-1) f=1;else{for(i=0;i<=k-2;i++) temp[i]=0;temp[k-1]=1; //初始化for(i=k;i<=m;i++) //求出序列第k至第m个元素的值{sum=0;for(j=i-k;j<i;j++) sum+=temp[j];temp[i]=sum;}f=temp[m];}return OK;}//fib分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m).1.18typedef struct{char *sport;enum{male,female} gender;char schoolname; //校名为'A','B','C','D'或'E'char *result;int score;} resulttype;typedef struct{int malescore;int femalescore;int totalscore;} scoretype;void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中{scoretype score;i=0;while(result[i].sport!=NULL){switch(result[i].schoolname){case 'A':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0)score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;case 'B':score .totalscore+=result[i].score;if(result[i].gender==0)score .malescore+=result[i].score;else score .femalescore+=result[i].score;break;………………}i++；}for(i=0;i<5;i++){printf("School %d:\n",i);printf("Total score ofmale:%d\n",score[i].malescore);printf("Total score offemale:%d\n",score[i].femalescore);printf("Total score ofall:%d\n\n",score[i].totalscore);}}//summary1.19Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint{last=1;for(i=1;i<=ARRSIZE;i++){a[i-1]=last*2*i;if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;last=a[i-1];return OK;}}//algo119分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.1.20void polyvalue(){float ad;float *p=a;printf("Input number of terms:");scanf("%d",&n);printf("Input the %d coefficients from a0 to a%d:\n",n,n);for(i=0;i<=n;i++) scanf("%f",p++);printf("Input value of x:");scanf("%f",&x);p=a;xp=1;sum=0; //xp用于存放x的i次方for(i=0;i<=n;i++){sum+=xp*(*p++);xp*=x;}printf("Value is:%f",sum);}//polyvalue。
第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。
A．顺序队列 B. 链表 C. 有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
严蔚敏数据结构课后习题及答案解析第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。
（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。
①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像②（A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。
（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。
①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。
（）2.算法就是程序。
（）3.数据元素是数据的最小单位。
（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。
（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。
（）三、填空题1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。
2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。
3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。
