《数据结构》第一章习题 殷人昆版

《数据结构》第一章习题

一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）

1、一些表面上很不相同的数据可以有相同的逻辑结构。（√ ） 2、用C语言等高级语言实现的算法就是程序。（ × ） 3、课本P37 1.5题 4、课本P37 1.6题

二、单项选择题

1、从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2、程序段 for(int i = n-1; i >= 1; i--) for(int j = 1; j <= i; j++) if(A[j]>A[j+1])

A[j]←→A[j+1]； // A[j]与A[j+1]交换值

其中n为正整数，则最后一行的语句频度在最坏情况下是（ A ）。 A．O(n) B．O(nlogn) C．O(n3) D．O(n2) 3、下面说法错误的是（ c ）

（1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （3）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3)

三、填空题

1、数据的逻辑结构是指（从解决问题的需要出发，为实现必要的功能所建立的数据结构）。数据的物理结构包括（顺序结构）的表示和_（链式结构）的表示。 2、数据结构的抽象数据类型ADT可用三元组表示（D，S，P），其中D是数据对象，S是D上的关系集，P是对D的基本操作集。

3、在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着_（直接存取结构）、（顺序存取结构）和（字典结构）的联系。

4、顺序存储结构是通过（顺序表）表示元素之间的关系的；链式存储结构是通过（链表）表示元素之间的关系的。

5．一个算法具有5个特性:_有穷性、确切性、能行性、有零个或多个输入、有一个或多个输出 。

6、一算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n), 可近似表示为___O（n）。

四、综合题

1、什么是数据结构？有关数据结构的讨论涉及哪三个方面？

答：数据结构由某一数据元素的集合和该集合中数据元素之间的关系组成。记：Data_Structure={D,R}数据结构包含三个方面：数据的逻辑结构，数据的存储结构和数据的操作

2、数据的存储结构由哪四种基本的存储方法实现？

答：顺序存储方法，连接存储方法，索引存储方法，散列存储方法 3、评价一个好的算法，可以从哪几方面来考虑？

答，可以从计算机系统，编译器，可用存储空间大小以及比较算法复杂性来评价算法优劣，其中最好的是从比较算法的复杂性来考虑。 4、数据结构与数据类型有什么区别？

数据结构由某一数据元素的集合和该集合中数据元素之间的关系组成。按逻辑关系可以分为线性结构和非线性结构。数据类型是指一种类型，以及定义于这个值集合上的一组操作的总称，数据类型和数据结构的主要区别是前者面向系统，后者面向对象，是高一层的数据抽象，如果程序设计语言提供有抽象数据类型设施，那么两者可以统一一起

5、课本P39 1.13题

1、设有如下遗产继承规则：丈夫和妻子可以互相继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。表示该遗产继承关系最合适的数据结构应该是（A）。

A．树 B．图 C．数组 D．二叉树 2、在数据结构中，从逻辑上可以把数据结构分成（C）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 3、计算机算法是指（C）。

A．计算方法论 B．排序方法 C．解决问题的有限运算序列 D．调试方法 4、以下说法正确的是（D）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位

C．数据结构是带结构的数据项的集合

D．一些表面上很不相同的数据可以有相同的逻辑结构 5、在决定选取何种存储结构时，一般不考虑（A）。 A．各结点的值如何时 B．结点个数的多少

C．对数据有哪些运算 D．所用编程语言实现这种结构是否方便 6、与线性璷的链接存储相符的特性是（A）。

A．插入和删除操作灵活 B．需要连续的存储空间 C．便于随机访问团 D．存储密度大

7、在单向循环链表中，基头指针为h，那么p所指结点为尾结点的条件是（D）。 A．p = NULL B．p.next=NULL C．p =h D．p.next=h 8与线性表的链接存储不相符的特性是（B）

A．插入和删除操作灵活 B．需要连续的存储空间

C．存储空间动态分配权 D．需另外开辟空间来保存元素间的关系 9、链表不具备的特点是（A）

A．可随机访问任一结点 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与其长度成正比 10、带头结点的单链表head为空的判定条件是（B）

A．head == NULL B．head.next == NULL C．head.next == head D．head != NULL

本文来源：https://www.bwwdw.com/article/8yth.html