没有合适的资源?快使用搜索试试~ 我知道了~
第一章概论 自测题答案 一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。2. 数据结构被形
资源详情
资源评论
资源推荐
数据结构测试题 卫信 06
第 1 页 共 20 页
1
第一章概论 自测题答案
一、填空题
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系
和运算等的学科。
2. 数据结构被形式地定义为(D, R),其中 D 是 数据元素 的有限集合,R 是 D 上的 关系 有限集
合。
3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类,它们分别是 线性结构 和 非线性结构 。
5. 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存
在多对多关系。
6. 在线性结构中,第一个结点 没有 前驱结点,其余每个结点有且只有 1 个前驱结点;最后一个结点
没有 后续结点,其余每个结点有且只有 1 个后续结点。
7. 在树形结构中,树根结点没有 前驱 结点,其余每个结点有且只有 1 个前驱结点;叶子结点没
有 后续 结点,其余每个结点的后续结点数可以任意多个 。
8. 在图形结构中,每个结点的前驱结点数和后续结点数可以 任意多个 。
9.数据的存储结构可用四种基本的存储方法表示,它们分别是顺序 、 链式 、 索引 和 散列 。
10. 数据的运算最常用的有 5 种,它们分别是插入 、 删除、修改、 查找 、排序。
11. 一个算法的效率可分为 时间 效率和 空间 效率。
二、单项选择题
( B )1. 非线性结构是数据元素之间存在一种:
A)一对多关系 B)多对多关系 C)多对一关系 D)一对一关系
( C )2. 数据结构中,与所使用的计算机无关的是数据的 结构;
A) 存储 B) 物理 C) 逻辑 D) 物理和存储
( C )3. 算法分析的目的是:
A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系
C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
( A )4. 算法分析的两个主要方面是:
A) 空间复杂性和时间复杂性 B) 正确性和简明性
C) 可读性和文档性 D) 数据复杂性和程序复杂性
( C )5. 计算机算法指的是:
A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法
( B )6. 计算机算法必须具备输入、输出和 等 5 个特性。
A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性
C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性
三、简答题
2.【严题集 1.2②】数据结构和数据类型两个概念之间有区别吗?
答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素,而且
还在其上定义了一组操作。
数据结构测试题 卫信 06
第 2 页 共 20 页
2
3. 简述线性结构与非线性结构的不同点。
答:线性结构反映结点间的逻辑关系是 一对一的,非线性结构反映结点间的逻辑关系是多对多的。
四、【严题集 1.8④】分析下面各程序段的时间复杂度
五、设有数据逻辑结构 S=(D,R),试按各小题所给条件画出这些逻辑结构的图示,并确定相
对于关系 R,哪些结点是开始结点,哪些结点是终端结点?
1. 【严蔚敏习题集 P7 1.3②】
D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) }
答: d1→d2→d3→d4 d1—无直接前驱,是首结点 d4—无直接后继是尾结点
2。D={d1,d2,…,d9}
R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }
答: 此图为树形结构 d1—无直接前驱,是根结点 d2,d5,d7,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)}
答: 此图为图形结构 d1,d2—无直接前驱,是开始结点 d6,d7—无直接后继是终端结点
(2) (3)
2. s=0;
for i=0; i<n; i++)
for(j=0; j<n; j++)
s+=B[i][j];
sum=s;
答:O(n
2
)
1. for (i=0; i<n; i++)
for (j=0; j<m; j++)
A[i][j]=0;
答:O(m*n)
3. x=0;
for(i=1; i<n; i++)
for (j=1; j<=n-i; j++)
x++;
解:因为 x++共执行了 n-1+n-2+……+1=
n(n-1)/2,所以执行时间为 O(n
2
)
4. i=1;
while(i<=n)
i=i*3;
答:O(log
3
n)
数据结构测试题 卫信 06
第 3 页 共 20 页
3
第 2 章 自测卷答案
一、填空
1. 【严题集 2.2①】在顺序表中插入或删除一个元素,需要平均移动 表中一半元素,具体移动的元素个
数与 表长和该元素在表中的位置 有关。
2. 线性表中结点的集合是 有限 的,结点间的关系是 一对一 的。
3. 向一个长度为 n 的向量的第 i 个元素(1≤i≤n+1)之前插入一个元素时,需向后移动 n-i+1 个元素。
4. 向一个长度为 n 的向量中删除第 i 个元素(1≤i≤n)时,需向前移动 n-i 个元素。
5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ,因此,顺序表也称为 随机存取 的数据结
构。
6. 【严题集 2.2①】顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元素的物
理位置 不一定 相邻。
7. 【严题集 2.2①】在单链表中,除了首元结点外,任一结点的存储位置由 其直接前驱结点的链域的值
指示。
8. 在 n 个结点的单链表中要删除已知结点*p,需找到它的前驱结点的地址,其时间复杂度为 O(n)。
二、判断正误(在正确的说法后面打勾,反之打叉)
( × )1. 链表的每个结点中都恰好包含一个指针。
答:错误。链表中的结点可含多个指针域,分别存放多个指针。例如,双向链表中的结点可以含有两个指针
域,分别存放指向其直接前趋和直接后继结点的指针。
( × )2. 链表的物理存储结构具有同链表一样的顺序。错,链表的存储结构特点是无序,而链表的示意图有序。
( × )3. 链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向
前移动。错,链表的结点不会移动,只是指针内容改变。
( × )4. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。
错,混淆了逻辑结构与物理结构,链表也是线性表!且即使是顺序表,也能存放记录型数据。
( × )5. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。
错,正好说反了。顺序表才适合随机存取,链表恰恰适于“顺藤摸瓜”
( × )6. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。
错,前一半正确,但后一半说法错误,那是链式存储的优点。顺序存储方式插入、删除运算效率较低,
在表长为 n 的顺序表中,插入和删除一个数据元素,平均需移动表长一半个数的数据元素。
( × )7. 线性表在物理存储空间中也一定是连续的。
错,线性表有两种存储方式,顺序存储和链式存储。后者不要求连续存放。
( × )8. 线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序上相邻。
错误。线性表有两种存储方式,在顺序存储时,逻辑上相邻的元素在存储的物理位置次序上也相邻。
( × )9. 顺序存储方式只能用于存储线性结构。
错误。顺序存储方式不仅能用于存储线性结构,还可以用来存放非线性结构,例如完全二叉树是属于
非线性结构,但其最佳存储方式是顺序存储方式。(后一节介绍)
( × )10. 线性表的逻辑顺序与存储顺序总是一致的。
错,理由同 7。链式存储就无需一致。
三、单项选择题
剩余19页未读,继续阅读
本本纲目
- 粉丝: 20
- 资源: 294
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0