数据结构课后习题(第1章)

《数据结构课后习题(第1章)》由会员分享，可在线阅读，更多相关《数据结构课后习题(第1章)（5页珍藏版）》请在装配图网上搜索。

1、网络工程2011级1班、计算机科学与技术2011级2班算法与数据结构课后习题（第1章）【课后习题】第1章 绪论2011级 计科 (网工) 班 学号： 姓名： 一、单项选择(每题2分，共44分)题号1234567891011答案题号1213141516171819202122答案1、下列说法正确的是（ ）。 A.数据是数据元素的基本单位 B.数据元素是数据项中不可分割的最小单位 C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成2、数据元素是数据的基本单位，其内（ ）数据项。 A.只能包括一个 B.不包含 C.可以包含多个 D.可以包含也可以不包含3、数据结构本质上是由（ ）构成。

2、A、一个有限的数据元素集合及其上关系的有限集； B、一个特定的数据元素集合及其上关系的有限集； C、一个数据元素集合以及定义在该集合之上的一个关系的有限集； D、一个数据元素集合及其上关系的集合。4、逻辑结构是（ ）关系的整体。 A.数据元素之间逻辑 B.数据项之间逻辑 C.数据类型之间 D.存储结构之间5、一个存储结点存放一个（ ）。 A.数据项B.数据元素 C.数据结构 D.数据类型6、每个结点只存储一个数据元素，存储结点存放在连续的存储空间，该存储方是（ ）存储方式。 A.顺序 B.链式 C.索引 D.散列7、每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（ ）存储方式。

3、A.顺序 B.链式 C.索引 D.散列8、每个存储结点只含有一个数据元素，存储结点均匀地存放在连续的存储空间，使用函数值对应结点存储位置，该存储方式是（ ）存储方式。A.顺序 B.链式 C.索引 D.散列9、下列时间复杂度中最坏的是（ ）。A.O（1） B.O（m） C.O (1og2n) D.O(n2) 10、下列时间复杂度中最好的是（ ）。A.O（1） B.O（m） C.O(1og2n) D.O(n2) 11、记录中的各个数据项的类型（ ）。A.必须相同B.不必相同 C.不能相同 D.不确定 12、已知一个算法的执行时间大约为8n+5n3，则其复杂度通常用（ ）度量即可。A、O(5n+2n

4、3)； B、O(2n3)； C、O(n3)； D、O(n+n3)。13、通常设计一个算法设计时，应考虑使其达到（ ）的目标A、正确、可读、健壮以及高效率和低存储； B、速度快和占用存储空间少；C、正确、速度快和占用存储空间少； D、具有输入和输出。14、抽象数据类型本质上是由（ ）构成。A、一个数据结构加一个操作集合；B、数据和操作；C、一个数据元素集、一个定义在该集合之上关系集以及一个对该关系集的操作集；D、一个数据元素的有限集、一个定义在该集合之上关系的有限集以及一个对该关系集的操作有限集； 15、算法能正确的实现预定功能的特性称为（ ），算法的便于阅读和理解的特性称为（ ）。A.正确性B

5、.易读性 C.健壮性 D.高效率16、算法在发生非法操作时可以作出处理的特性称为（ ），算法可以达到所需时空的特性称为（ ）。A.正确性B.易读性 C.健壮性 D.高效率17算法分析的目的是 A辨别数据结构的合理性 B评价算法的效率C研究算法中输入与输出的关系 D鉴别算法的可读性18. 数据结构中，与所使用的计算机无关的是数据的（ ）结构；A) 线性 B) 非线性 C) 逻辑 D) 物理和存储19. 算法分析的两个主要方面是( )A) 数据复杂性和程序复杂性 B) 正确性和简明性C) 可读性和文档性 D) 空间复杂性和时间复杂性20. 某算法的时间复杂度为O(n1/2), 假设当n=100时，

6、算法的执行时间为5ms, 则当n=10000时，算法的执行时间可估计为（ ）msA) 50000 B)5000 C)500 D)5021、下列算法的时间复杂度是（ ）。for (i=0;im;i+)for (j=0;jn;j+)cij=i+j; A.O（1） B.O（m+n） C.O(1og2n) D.O(m*n)22、下列存储A、B、C、D、E的方式是（ ）存储方式。地址 元素1000A1001B1002C1003D1004EA.顺序 B.链式 C.索引 D.散列二、填空题（每空1.5分，共57分）1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。2

7、. 数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。3. 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是 和 。5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。6 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 后续结点，其余每个结点有且只有1个后续结点。7. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点数可以 。8. 在图形结构中，每个结点的前驱结点数

8、和后续结点数可以 。9.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。四种基本结构是：集合、 、 、 。10.存储结构是 的实现或映象。11.数据结构中元素之间的逻辑关系在计算机中使用不同的存储方法。具体的存储方法有：顺序存储、 、 和 。12. 数据的运算最常用的有5种，它们分别是 、 、 、 、 。13. 算法分析的两个主要方面是 _和 _。14通常从四个方面评价算法的质量： _、_ _、_ _和_ _。15、下列程序段的时间复杂性的量级为 。for (t=1;t=n;t+)t=t*3;*三、应用题(选做)1、画出线性结构的示意图。2、画出树形结构的示意图。3、画出图状结构的示

9、意图。4、什么是逻辑结构、存储结构？有哪几种存储结构？5、简述逻辑结构与存储结构的关系。第 4 页 共 4 页【课后习题】第1章 绪论(参考答案)一、单项选择(每题2分，共44分)题号1234567891011答案CCAABABDDAB题号1213141516171819202122答案CADABCDBCDDDA二、填空题（每空1.5分，共57分）1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。3. 数据结构包括数据的 逻辑结构 、数

10、据的 存储结构 和数据的 运算 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。6 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个

11、。9.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。四种基本结构是：集合、 线性结构 、 树型结构 、 图结构 。10.存储结构是 逻辑结构在计算机存储器中 的实现或映象。11.数据结构中元素之间的逻辑关系在计算机中使用不同的存储方法。具体的存储方法有：顺序存储、链式存储 、 索引存储 和 散列存储 。12. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。13. 算法分析的两个主要方面是时间复杂度和空间复杂度。14通常从四个方面评价算法的质量： 正确性 _、 可读性 、 健壮性 和 效率与低存储量需求 。15、下列程序段的时间复杂性的量级为O(1og3n) 。for (t=1;tn;t+)t=t*3;第 1 页 共 1 页