第1章 绪论
一、填空题(每空1分,共35分)
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和 等的学科。
2. 数据结构被形式地定义为(D, R),其中D是 的有限集合,R是D上的 有限集合。
3. 数据结构按逻辑结构可分为两大类,它们分别是 和 。若细分为4类,分别是 、 、 和 。
4. 线性结构中元素之间存在 关系,树形结构中元素之间存在 关系,图形结构中元素之间存在 关系。
5. 在线性结构中,第一个结点 前驱结点,其余每个结点有且只有 个前驱结点;最后一个结点 后继结点,其余每个结点有且只有 个后继结点。
6. 在树形结构中,树根结点没有 结点,其余每个结点有且只有 个前驱结点;叶子结点没有后继结点,其余每个结点的后继结点数可以任意。
7. 在图形结构中,每个结点的前驱结点数和后继结点数可以 。
8. 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。
9. 数据的存储结构可用四种基本的存储方法表示,它们分别是 、 、 和 。
10. 数据的运算最常用的有5种,它们分别是 、 、 、 、 。
11. 一个算法的效率可分为 效率和 效率。
二、单项选择题(每小题1分,共5分)
1. 数据结构中,与所使用的计算机无关的是数据的( )结构。
A、存储 B、物理 C、逻辑 D、物理和存储
2. 算法分析的目的是( )。
A、找出数据结构的合理性 B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进 D、分析算法的易懂性和文档性
3. 算法分析的两个主要方面是:( )。
A、空间复杂性和时间复杂性 B、正确性和简明性
C、可读性和文档性 D、数据复杂性和程序复杂性
4. 计算机算法指的是( )。
A、计算方法 B、排序方法
C、解决问题的有限运算序列 D、调度方法
5. 计算机算法必须具备输入、输出和( )等5个特性。
A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性
C、确定性、有穷性和稳定性 D、易读性、稳定性和安全性
三、判断下列叙述的对错。如果正确,在题前的括号内填入“”,否则填入“”。(每题1分,共8分)
1. ( )数据元素是数据的最小单位。
2. ( )数据结构是数据对象与对象中数据元素之间关系的集合。
3. ( )数据结构是具有结构的数据对象。
4. ( )算法和程序原则上没有区别,在讨论数据结构时二者是通用的。
5. ( )所谓数据的逻辑结构是指数据元素之间的逻辑关系。
6. ( )数据的逻辑结构与数据元素本身的内容和形式无关。
7. ( )数据结构是指相互之间存在一种或多种关系的数据元素的全体。
8. ( )从逻辑关系上讲,数据结构主要分为两大类:线性结构和非线性结构。
四、设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。(每题4分,共24分)
(1) for (int i = 1;i <= n;i++)
for (int j = 1; j <= n; j++)
{
c[i][j]=0.0;
for(int k = 1; k <= n; k++)
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
(2) x = 0;y = 0;
for ( int i = 1; i <= n; i++)
for( int j = 1; j <= i; j++)
for( int k = 1; k <= j; k++)
x = x + y;
(3)k=0;
for(i=1; i<=n; i++)
for(j=I; j<=n; j++)
k++;
(4) i=1; j=0;
while(i+j<=n) {
if(i>j) j++;
else i++;
}
(5) x=n; y=0;
while(x>=(y+1)*(y+1))
y++ ;
(6) x=91; y=100;
while(y>0) {
if(x>100) {x-=10; y--; }
else x++;
}
五、分析下面各程序段的时间复杂度(每小题4分,共16分)
2. s=0;
for i=0; i
for(j=0; j
s+=B[i][j];
sum=s;
1. for (i=0; i
for (j=0; j
A[i][j]=0;
3. x=0;
for(i=1; i
for (j=1; j<=n-i; j++)
x++;
4. i=1;
while(i<=n)
i=i*3;
六、设有数据逻辑结构S=(D,R),试按各小题所给条件画出这些逻辑结构的图示,并确定相对于关系R,哪些结点是开始结点,哪些结点是终端结点?(每小题4分,共12分)
1. D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) }
2. D={d1,d2,…,d9}
R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }
3. D={d1,d2,…,d9}
R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)}
本文档为【河南科技学院新科学院数据结构第1章测试题】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。