1．数据结构是一门研究非数值计算的程序设计问题中计算机的
①以及它们之间的②和运算等的学科。CB
①A.数据元素B.计算方法C.逻辑存储D.数据映像
②A.结构B.关系C.运算D.算法
2．数据结构被形式地定义为(K，R)，其中K是①的有限集，R是K上的②有限集。BD
①A.算法B.数据元素C.数据操作D.逻辑结构
②A.操作B.映象C.存储D.关系
．在数据结构中，从逻辑上可以把数据结构分成C。
A.动态结构和静态结构B.紧凑结构和非紧凑结构
C.线性结构和非线性结构D.内部结构和外部结构
4．线性结构的顺序存储结构是一种①的存储结构，线性表的链式存储结构是一种②的存储结构。AB
A.随机存取B.顺序存取C.索引存取D.散列存取
5．算法分析的目的是①，算法分析的两个主要方面是②。CA
①A.找出数据结构的合理性B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进D.分析算法的易懂性和文档性
②A.空间复杂度和时间复杂度B.正确性和简单性
C.可读性和文档性D.数据复杂性和程序复杂性
6．计算机算法指的是①，它必具备输入、输出和②等五个特性。CB
①A.计算方法B.排序方法
C.解决问题的有限运算序列D.调度方法
②A.可执行性、可移植性和可扩充性B.可行性、确定性和有穷性
C.确定性、有穷性和稳定性D.易读性、稳定性和安全性
7．线性表的逻辑顺序与存储顺序总是一致的，这种说法。B
A.正确B.不正确
8．线性表采用链式存储结构时，要求内存中可用存储单元的地址。D
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续不连续都可以
9．在以下的叙述中，正确的是。B
A.线性表的线性存储结构优于链表存储结构
B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出
D.队列的操作方式是先进后出
10．每种数据结构都具备三个基本运算：插入、删除和查找，这种说法.AA.正确B.不正确
1.2.2填空题1．数据逻辑结构包括哪四种类型，树形结构和图形结构合称为什么?
集合，线性，树形，图状非线性
2．在线性结构中，第一个结点①没有前驱结点，其余每个结点有且只有②1个前驱结点；最后一个结点③没有后续结点，其余每个结点有且只有④1个后续结点。
5．线性结构中元素之间存在①1对1关系，树形结构中元素之间存在②1对多关系，图形结构中元素之间存在③多对多关系。
6．算法的五个重要特性是①有穷性、②确定性、③可行性、④输入、⑤输出。
7．下面程序段的时间复杂度是O(m*n)。
for(i=0；in；i++)
for(j=0；jm；j++)
A[i][j]=0；
8．下面程序段的时间复杂度是O(n)。
i=s=0；
while(sn)
{i++；/*i=i+1*/
s+=i；/*s=s+i*/
}
9．下面程序段的时间复杂度是O(n的平方)。
s=0；
for(i=0；in；i++)
for(j=0；jn；j++)
s+=B[i][j]；
sum=s；
1.2.综合题1．设有数据逻辑结构为：
B=(K，R)K={k1，k2，...，k9}
R={k1，k，k1，k8，k2，k，k2，k4，k2，k5，k，k9，k5，k6，k8，k9，k9，k7，k4，k7，k4，k6}
画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点?
解：该题的逻辑结构图示如图1.2所示。
图1.2一个逻辑结构图示
开始结点是指无前驱的结点，这里满足该定义的开始结点为k1，k2。
终端结点是指无后续的结点，这里满足该定义的终端结点为k6，k7。
该逻辑结构是非线性结构中的图形结构。
2．设有如图1.所示的逻辑图，给出它的逻辑结构。
解：本题的逻辑结构如下：
B=(K，R)K={k1，k2，...，k9}
R={k1，k2，k1，k，k，k4，k，k6，k6，k8，k4，k5，k6，k7，k8，k9}
该逻辑结构是一个树形结构，其树根为k1，叶子结点为k2、k5、k7和k9。
图1.一个逻辑结构图示
．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它
分别属于何种结构。
（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}
（）C=(K，R)，其中：
K={1，2，，4，5，6}
R={r}
r={(1，2)，(2，)，(2，4)，(，4)，(，5)，(，6)，(4，5)，(4，6)}
这里的圆括号对表示两结点是双向的。
（4）D=(K，R)，其中：
K={48，25，64，57，82，6，75}
R={r1，r2}
r1={25，6，6，48，48，57，57，64，64，75，75，82}r2={48，25，48，64，64，57，64，82，25，6，82，75}
解：（1）A对应逻辑图形如图1.4所示，它是一种线性结构。
图1.4对应A的逻辑结构图示
（2）B对应逻辑图形如图1.5所示，它是一种树形结构。
图1.5对应B的逻辑结构图示
（）C对应逻辑图形如图1.6所示，它是一种图形结构。
图1.6对应C的逻辑结构图示
（4）D对应逻辑图形如图1.7所示，它是一种图形结构，r1（对应图中虚线部分）为线性结构，r2（对应图中实线部分）则为树形结构。
图1.7对应D的逻辑结构图示
4．有如下递归函数fact(n)，分析其时间复杂度。
fact(intn)
{if(n=1)return(1)；①
elsereturn(n*fact(n-1))；②
}
解：设fact(n)的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+O(1)，其中O(1)为运算的时间。
因此：
则：T(n)=O(1)+T(n-1)
=2*O(1)+T(n-2)
…
=(n-1)*O(1)+T(1)
=n*O(1)
=O(n)
即fact(n)的时间复杂度为O(n)。
5．指出下列各算法的时间复杂度。
（1）
prime(intn)/*n为一个正整数*/
{inti=2；
while((n%i)!=0i*1.0sqrt(n))i++；
if(i*1.0sqrt(n))
printf(%d是一素数\n，n)；
elseprintf(%d不是一素数\n，n)；
}
（2）sum1(intn)/*n为一个正整数*/
{intp=1，sum=0，i；
for(i=1；i=n；i++)
{p*=i；
sum+=p；
}
return(sum)；
}
（）sum2(intn)/*n为一个正整数*/
{intsum=0，i，j；
for(i=1；i=n；i++)
{p=1；
for(j=1；j=i；j++)p*=j；
sum+=p；
}
return(sum)；
}
解：算法的时间复杂度是由嵌套最深层语句的频度决定的。
（1）prime()的嵌套最深层语句：
i++；
它的频度由条件((n%i)!=0i*1.0sqrt(n))决定，显然i*1.0sqrt(n)，即执行频度小于sqrt(n)，所以其时间复杂度是O()。
（2）sum1()的嵌套最深层语句：
p*=i；sum+=p；
它的频度为n次，所以其时间复杂度是O(n)。
（）sum2()的嵌套最深层语句：
p*=j；
它的频度为1+2++…+n=n(n+1)/2次，所以其时间复杂度是O(n)
6．求两个n阶矩形的乘法C=A×B，其算法如下：
#defineMAX
voidmaxtrixmult(intn，floata[MAX][MAX]，floatb[MAX][MAX]，floatc[MAX][MAX])
{inti，j，k；
floatx；
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；⑥
}
}
}
分析该算法的时间复杂度。
解：该算法中主要语句的频度分别是：
①n+1
②n(n+1)
③n2
④n2(n+1)
⑤n
⑥n2
则时间复杂度为所有语句的频度之和T(n)=2n+n+2n+1=O(n)。
7．简述下列术语：数据、数据元素、数据对象、存储结构、数据类型、和抽象数据类型。
8．试描述数据结构和抽象类型的概念与程序设计语言中数据类型概念的区别。
9．在程序设计中，常用下列三种不同的出错处理方式：
（1）用exit语句终止执行并报告错误；
（2）以函数的返回值区别正取返回或错误返回；
（）设置一个整型变量的函数参数以区别正取返回或错误返回；
试讨论这三种方法各自的优点
10．在程序设计中，可采用下列三种方法实现输出和输入：
（1）通过scanf和printf语句；
(2)通过函数的参数显示传递；
（）通过全局变量隐式传递。
试讨论这三种方法的优缺点。
11．设n为正整数。试确定下列各程序段中前置以记号
的语句的频度：(1)i=1;k=0;
While(i=n-1){
k+=10*I;i++;
}
答：n-1
(2)i=1;k=0;
do{
k+=10*I;i++;
}while(I=n-1);
答：n-1
()i=1;k=0;
While(i=n-1){
i++;
k+=10*i;}
答：n-1
(4)k=0;
for(i=1;i=n;i++){
for(j=i;j=n;j++)
k++;}
答：(n+1)*n/2
(5)for(i=1;i=n;i++){
for(j=i;j=n;j++){
for(k=1;k=j;k++)
x+=delta;}
答：1/6*n*(n+1)*(n+2)
(6)i=1;j=0;
While(i+j=n){
if(ij)j++;elsei++;
}
答：n
(7)x=n;y=o;
while(x=(y+1)*(y+1)){
y++;}
答：??n?
(8)x=91;y=;
while(y0){
if(x){x-=10;y--;}elsex++;
}
答：1
12．按增长率由小到大的顺序排列下列各函数：
2(/2)n(2/)n(4/)nnnn/2n2/n!
n,log2nlog22nlog2(log2n)nlog2nnlog2n
1．试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。
解：
voidprint_descending(intx,inty,intz)//按从大到小顺序输出三个数{scanf(%d,%d,%d,x,y,z);if(xy)x-y;//-为表示交换的双目运算符,以下同if(yz)y-z;if(xy)x-y;//冒泡排序printf(%d%d%d,x,y,z);}//print_descending
14．试编写算法，计算i!.2i的值并存入数组a[0…arrsize-1]的第i-1个分量中（I=1,2,….,n）。假设计算机中允许的整数最大值为maxint,则当narrsize或对某个k(1≤k≤n)使k!.2kmaxint时，应按出错处理，注意选择你认为较好的出错处理方法。
解：
Statusalgo(inta[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))reurnOVERFLOW;last=a[i-1];returnOK;}}//algo分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.
1.2.1单项选择题1．数据结构是一门研究非数值计算的程序设计问题中计算机的
①以及它们之间的②和运算等的学科。CB
①A.数据元素B.计算方法C.逻辑存储D.数据映像
②A.结构B.关系C.运算D.算法
2．数据结构被形式地定义为(K，R)，其中K是①的有限集，R是K上的②有限集。BD
①A.算法B.数据元素C.数据操作D.逻辑结构
②A.操作B.映象C.存储D.关系
．在数据结构中，从逻辑上可以把数据结构分成C。
A.动态结构和静态结构B.紧凑结构和非紧凑结构
C.线性结构和非线性结构D.内部结构和外部结构
4．线性结构的顺序存储结构是一种①的存储结构，线性表的链式存储结构是一种②的存储结构。AB
A.随机存取B.顺序存取C.索引存取D.散列存取
5．算法分析的目的是①，算法分析的两个主要方面是②。CA
①A.找出数据结构的合理性B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进D.分析算法的易懂性和文档性
②A.空间复杂度和时间复杂度B.正确性和简单性
C.可读性和文档性D.数据复杂性和程序复杂性
6．计算机算法指的是①，它必具备输入、输出和②等五个特性。CB
①A.计算方法B.排序方法
C.解决问题的有限运算序列D.调度方法
②A.可执行性、可移植性和可扩充性B.可行性、确定性和有穷性
C.确定性、有穷性和稳定性D.易读性、稳定性和安全性
7．线性表的逻辑顺序与存储顺序总是一致的，这种说法。B
A.正确B.不正确
8．线性表采用链式存储结构时，要求内存中可用存储单元的地址。D
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续不连续都可以
9．在以下的叙述中，正确的是。B
A.线性表的线性存储结构优于链表存储结构
B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出
D.队列的操作方式是先进后出
10．每种数据结构都具备三个基本运算：插入、删除和查找，这种说法.AA.正确B.不正确
1.2.2填空题1．数据逻辑结构包括哪四种类型，树形结构和图形结构合称为什么?
集合，线性，树形，图状非线性
2．在线性结构中，第一个结点①没有前驱结点，其余每个结点有且只有②1个前驱结点；最后一个结点③没有后续结点，其余每个结点有且只有④1个后续结点。
5．线性结构中元素之间存在①1对1关系，树形结构中元素之间存在②1对多关系，图形结构中元素之间存在③多对多关系。
6．算法的五个重要特性是①有穷性、②确定性、③可行性、④输入、⑤输出。
7．下面程序段的时间复杂度是O(m*n)。
for(i=0；in；i++)
for(j=0；jm；j++)
A[i][j]=0；
8．下面程序段的时间复杂度是O(n)。
i=s=0；
while(sn)
{i++；/*i=i+1*/
s+=i；/*s=s+i*/
}
9．下面程序段的时间复杂度是O(n的平方)。
s=0；
for(i=0；in；i++)
for(j=0；jn；j++)
s+=B[i][j]；
sum=s；
1.2.综合题1．设有数据逻辑结构为：
B=(K，R)K={k1，k2，...，k9}
R={k1，k，k1，k8，k2，k，k2，k4，k2，k5，k，k9，k5，k6，k8，k9，k9，k7，k4，k7，k4，k6}
画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点?
解：该题的逻辑结构图示如图1.2所示。
图1.2一个逻辑结构图示
开始结点是指无前驱的结点，这里满足该定义的开始结点为k1，k2。
终端结点是指无后续的结点，这里满足该定义的终端结点为k6，k7。
该逻辑结构是非线性结构中的图形结构。
2．设有如图1.所示的逻辑图，给出它的逻辑结构。
解：本题的逻辑结构如下：
B=(K，R)K={k1，k2，...，k9}
R={k1，k2，k1，k，k，k4，k，k6，k6，k8，k4，k5，k6，k7，k8，k9}
该逻辑结构是一个树形结构，其树根为k1，叶子结点为k2、k5、k7和k9。
图1.一个逻辑结构图示
．有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它
分别属于何种结构。
（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}
（）C=(K，R)，其中：
K={1，2，，4，5，6}
R={r}
r={(1，2)，(2，)，(2，4)，(，4)，(，5)，(，6)，(4，5)，(4，6)}
这里的圆括号对表示两结点是双向的。
（4）D=(K，R)，其中：
K={48，25，64，57，82，6，75}
R={r1，r2}
r1={25，6，6，48，48，57，57，64，64，75，75，82}r2={48，25，48，64，64，57，64，82，25，6，82，75}
解：（1）A对应逻辑图形如图1.4所示，它是一种线性结构。
图1.4对应A的逻辑结构图示
（2）B对应逻辑图形如图1.5所示，它是一种树形结构。
图1.5对应B的逻辑结构图示
（）C对应逻辑图形如图1.6所示，它是一种图形结构。
图1.6对应C的逻辑结构图示
（4）D对应逻辑图形如图1.7所示，它是一种图形结构，r1（对应图中虚线部分）为线性结构，r2（对应图中实线部分）则为树形结构。
图1.7对应D的逻辑结构图示
4．有如下递归函数fact(n)，分析其时间复杂度。
fact(intn)
{if(n=1)return(1)；①
elsereturn(n*fact(n-1))；②
}
解：设fact(n)的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+O(1)，其中O(1)为运算的时间。
因此：
则：T(n)=O(1)+T(n-1)
=2*O(1)+T(n-2)
…
=(n-1)*O(1)+T(1)
=n*O(1)
=O(n)
即fact(n)的时间复杂度为O(n)。
5．指出下列各算法的时间复杂度。
（1）
prime(intn)/*n为一个正整数*/
{inti=2；
while((n%i)!=0i*1.0sqrt(n))i++；
if(i*1.0sqrt(n))
printf(%d是一素数\n，n)；
elseprintf(%d不是一素数\n，n)；
}
（2）sum1(intn)/*n为一个正整数*/
{intp=1，sum=0，i；
for(i=1；i=n；i++)
{p*=i；
sum+=p；
}
return(sum)；
}
（）sum2(intn)/*n为一个正整数*/
{intsum=0，i，j；
for(i=1；i=n；i++)
{p=1；
for(j=1；j=i；j++)p*=j；
sum+=p；
}
return(sum)；
}
解：算法的时间复杂度是由嵌套最深层语句的频度决定的。
（1）prime()的嵌套最深层语句：
i++；
它的频度由条件((n%i)!=0i*1.0sqrt(n))决定，显然i*1.0sqrt(n)，即执行频度小于sqrt(n)，所以其时间复杂度是O()。
（2）sum1()的嵌套最深层语句：
p*=i；sum+=p；
它的频度为n次，所以其时间复杂度是O(n)。
（）sum2()的嵌套最深层语句：
p*=j；
它的频度为1+2++…+n=n(n+1)/2次，所以其时间复杂度是O(n)
6．求两个n阶矩形的乘法C=A×B，其算法如下：
#defineMAX
voidmaxtrixmult(intn，floata[MAX][MAX]，floatb[MAX][MAX]，floatc[MAX][MAX])
{inti，j，k；
floatx；
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；⑥
}
}
}
分析该算法的时间复杂度。
解：该算法中主要语句的频度分别是：
①n+1
②n(n+1)
③n2
④n2(n+1)
⑤n
⑥n2
则时间复杂度为所有语句的频度之和T(n)=2n+n+2n+1=O(n)。
7．简述下列术语：数据、数据元素、数据对象、存储结构、数据类型、和抽象数据类型。
8．试描述数据结构和抽象类型的概念与程序设计语言中数据类型概念的区别。
9．在程序设计中，常用下列三种不同的出错处理方式：
（1）用exit语句终止执行并报告错误；
（2）以函数的返回值区别正取返回或错误返回；
（）设置一个整型变量的函数参数以区别正取返回或错误返回；
试讨论这三种方法各自的优点
10．在程序设计中，可采用下列三种方法实现输出和输入：
（1）通过scanf和printf语句；
(2)通过函数的参数显示传递；
（）通过全局变量隐式传递。
试讨论这三种方法的优缺点。
11．设n为正整数。试确定下列各程序段中前置以记号
的语句的频度：(1)i=1;k=0;
While(i=n-1){
k+=10*I;i++;
}
答：n-1
(2)i=1;k=0;
do{
k+=10*I;i++;
}while(I=n-1);
答：n-1
()i=1;k=0;
While(i=n-1){
i++;
k+=10*i;}
答：n-1
(4)k=0;
for(i=1;i=n;i++){
for(j=i;j=n;j++)
k++;}
答：(n+1)*n/2
(5)for(i=1;i=n;i++){
for(j=i;j=n;j++){
for(k=1;k=j;k++)
x+=delta;}
答：1/6*n*(n+1)*(n+2)
(6)i=1;j=0;
While(i+j=n){
if(ij)j++;elsei++;
}
答：n
(7)x=n;y=o;
while(x=(y+1)*(y+1)){
y++;}
答：??n?
(8)x=91;y=;
while(y0){
if(x){x-=10;y--;}elsex++;
}
答：1
12．按增长率由小到大的顺序排列下列各函数：
2(/2)n(2/)n(4/)nnnn/2n2/n!
n,log2nlog22nlog2(log2n)nlog2nnlog2n
1．试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。
解：
voidprint_descending(intx,inty,intz)//按从大到小顺序输出三个数{scanf(%d,%d,%d,x,y,z);if(xy)x-y;//-为表示交换的双目运算符,以下同if(yz)y-z;if(xy)x-y;//冒泡排序printf(%d%d%d,x,y,z);}//print_descending
14．试编写算法，计算i!.2i的值并存入数组a[0…arrsize-1]的第i-1个分量中（I=1,2,….,n）。假设计算机中允许的整数最大值为maxint,则当narrsize或对某个k(1≤k≤n)使k!.2kmaxint时，应按出错处理，注意选择你认为较好的出错处理方法。
解：
Statusalgo(inta[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))reurnOVERFLOW;last=a[i-1];returnOK;}}//algo分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.
月季花幼教集团儿童剧丑小鸭精彩上月季花知识大全