《数据结构与算法设计》习题册第一章绪论一、单项选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。

①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象②A. 结构 B. 关系 C. 运算 D. 算法2.数据结构被形式地定义为（K，R），其中K是①的有限集，R是K上的②有限集。

①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作②A. 操作 B. 存储 C. 映象 D. 关系3.在数据结构中，从逻辑上可以把数据结构分成。

A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构4.数据结构在计算机内存中的表示是指。

A. 数据的存储结构B. 数据结构C. 数据的逻辑结构D. 数据元素之间的关系5.在数据结构中，与所使用的计算机无关的是数据的结构。

A. 逻辑B. 存储C. 逻辑和存储D. 物理6.算法分析的目的是①，算法分析的两个主要方面是②。

①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性②A. 空间复杂度和时间复杂度 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性7.计算机算法指的是①，它必须具备输入、输出和②等5个特性。

①A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性8.在以下叙述中，正确的是。

A. 线性表的线性存储结构优于链表存储结构B. 二维数组是其数据元素为线性表的线性表C. 栈的操作方式是先进先出D. 队列的操作方式是先进后出9.在决定选取何种存储结构时，一般不考虑。

A. 各结点的值如何B. 结点个数的多少C. 对数据有哪些运算D. 所用编程语言实现这种结构是否方便10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。

A. 数据的处理方法B. 数据元素的类型C. 数据元素之间的关系D. 数据的存储方法11.下面说法错误的是。

（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界（4）同一个算法，实现语句的级别越高，执行效率越低A. （1）B. （1）、（2）C. （1）、（4）D. （3）12.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着。

A. 数据元素具有同一特点B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C. 每个数据元素都一样D. 数据元素所包含的数据项的个数要相等13.以下说法正确的是。

A. 数据元素是数据的最小单位B. 数据项是数据的基本单位C. 数据结构是带结构的各数据项的集合D. 一些表面上很不相同的数据可以有相同的逻辑结构二、填空题1.一个数据结构在计算机中的称为存储结构。

2.数据逻辑结构包括①、②和③三种结构，树形结构和图形结构合称为④。

3.在线性结构中，第一个结点①前驱结点，其余每个结点有且只有②个前驱结点；最后一个结点③后继结点，其余每个结点有且只有④个前驱结点。

4.在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后继结点可以有④个。

5.在图形结构中，每个结点的前驱结点数和后继结点数都可以有个。

6.线性结构中元素之间存在①关系，树形结构中元素之间存在②关系，图形结构中元素之间存在③关系。

7.算法的五个重要特性是、、、输入和输出。

8.算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。

这个断言是（正确的或错误的）。

三、简答题1.设有数据逻辑结构为：B=(K,R) K={k1,k2,...,k9}R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>}画出这个逻辑结构的图示，并确定相对关系R，哪些结点是开始结点，哪些结点是终端结点。

2.设有如图1所示的逻辑结构图示，给出它的逻辑结构。

图13.有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。

（1）A=(K,R)，其中：K={a,b,c,d,e,f,g,h} R={r}r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}（2）B=(K,R)，其中：K={a,b,c,d,e,f,g,h} R={r}r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}（3）C=(K,R)，其中：K={1,2,3,4,5,6} R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}这里的圆括号对表示两结点是双向的。

（4）D=(K,R)，其中：K={48,25,64,57,82,36,75} R={r1,r2}r1={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>}r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>}4.当你为解决某一问题而选择数据结构时，应从哪些方面考虑？四、算法设计题1.下面程序段的时间复杂度是。

for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;2.下面程序段的时间复杂度是。

i=s=0;while(s<n){i++; s+=i;}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.有如下递归函数fact(n)，分析其时间复杂度。

fact(int n){if(n<=1) return 1;else return (n*fact(n-1));}6.指出下列个算法的时间复杂度。

（1）prime(int n){ //n为一个正整数int i=2;while(n%i!=0&&i<sqrt(n)) i++;if(i*1.0>sqrt(n)) printf(“%d 是一素数\n”,n);else printf(“%d 不是一个素数\n”,n);}（2）sum1(int n){ //n为一个正整数int p=1,sum=0,i;for(i=1;i<=n;i++){p*=i; sum+=p;}return sum;}（3）sum2(int n){ //n为一个正整数int sum=0,i,j;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++) p*=j;sum+=p;}return sum;}7.求两个n阶矩阵的乘法C=A×B，其算法如下：#define MAX 100void MaxtrixMult(int n,float a[MAX][MAX], float b[MAX][MAX],float c[MAX][MAX]){int i,j,k;float x;for(i=1;i<=n;i++){for(j=1;j<=n;j++){x=0;for(k=1;k<=n;k++) x+=a[i][k]*b[k][j];c[i][j]+=x;}}}分析该算法的时间复杂度。

8.设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。

m=0;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;9.给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写一个算法，将数组a和b归并为递增有序数组c[1..m+n]，要求算法的时间复杂度为O(m+n)。

10.求解盘片为n的汉诺塔问题的算法如下，分析其算法时间复杂度。

void hanoi(int n,char x,char y,char z){if(n==1) printf(“Move disk %d from %c to %c.\n”,n,x,z);else{hanoi(n-1,x,z,y);printf(“Move disk %d from %c to %c.\n”,n,x,z);hanoi(n-1,y,x,z);}}11.分析以下程序段的时间复杂度。

s=0;for(i=0;i<=n;i++)for(j=0;j<=n;j++)for(k=0;k<i+j;k++)s++;。