南京晓庄学院-数据结构与算法习题册（1）绪论数据结构和算法

一、填空题

1.从逻辑关系上讲，数据结构的类型主要分为_____、_____、_____ 和_____。参考解答： 1)集合结构 2)线性结构 3)树形结构 4)图状结构解析：(见下图) 注意题干中的逻辑关系。

文章图片

2.数据的存储结构主要有_____和_____两种基本方法，不论哪种存储结构，都要存储两方面的内容：_____和_____。参考解答： 1)顺序存储 2)链式存储 3)数据元素的值 4)数据元素之间的关系解析：(见下图) 数据的存储结构有4种方法，分别为顺序存储、链式存储、索引存储以及散列存储。主要有顺序存储和链式存储两种基本方法。

文章图片

3.算法具有五个特性，分别是_____、_____、_____、_____、_____。参考解答： 1)有穷性 2)确定性 3)可行性 4)输入 5)输出解析：(见下图)

文章图片

4.算法设计要求中的健壮性指的是_____。参考解答：算法能处理一些异常情况。解析：(见下图) 王道书上关于健壮性的完整表述为输入非法数据时，算法的适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。

文章图片

二、选择题

1.顺序存储结构中数据元素之间的逻辑关系是由_____表示的，链接存储结构中的数据元素之间的逻辑关系是由_____表示的。 A.线性结构B.非线性结构C.存储位置D.指针参考解答：C、D 解析：(见下图) 数据的逻辑结构分为线性结构和非线性结构。线性表、栈、队列属于线性结构；树、图、集合属于非线性结构。 A、B选项不符合题干要求。

文章图片

2.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是。 A.树B.图C.线性表D.集合参考解答：A 解析：(见下图) 从画出的逻辑结构图中，可知数据元素之间存在一对多的关系，符合树形结构的定义，故选择 A选项。

【南京晓庄学院-数据结构与算法习题册（1）绪论】

文章图片

3.算法指的是_____。 A.对特定问题求解步骤的一种描述，是指令的有限序列。 B.计算机程序 C.解决问题的计算方法 D.数据处理参考解答：A 解析：(见下图)

文章图片

三、简答题

文章图片

参考解答： (1)基本运算(最深层循环内的语句，k=k+10*i; i++; )执行了n-2次，因此T(n)=O(n)。问：n-2是怎么得到的？答：一开始i=1，执行一次while循环，i的值自增1，当i的值增加到等于n-1的时候，则while循环结束。故从1增加到n-1，一共执行了n-2次自增操作。 (2) 基本运算(最深层循环内的语句，，k=k+10*i; i++; )执行了n次，因此Tn=O(n)。问：n是怎么得到的？答： do-while循环，一开始必定会执行1次，即第1次while循环判断的条件是2<=n。当i的值自增至n+1的时候，不满足while循环条件，才结束。故从2增加到n+1，一共执行了n-1次自增操作，加上第1次的自增操作，共执行了n次。