数据结构习题集

数据结构习题

第一二章 绪论 线形表

一、填充题

1、计算机算法分析的两个主要方面分别是 和 。

时间复杂度 空间复杂度

2、数据元素都不是孤立存在的，而是在它们之间存在着某种关系。这种数据元素之间的相互关系称之为 。 结构

3、数据结构通常被分为 和 两大类。 逻辑结构 物理结构

4、线性表的长度被定义为表中元素的 。 个数

5、所谓的双向链表，是指在每一个结点中，有两个指针域，其中一个指向该结点的直接后继结点，而另一个则指向 。 其直接前趋结点

6、我们通常把性质相同的数据元素的集合称为 ，它是数据的一个子集。 数据对象

7、线性表的顺序映象就是逻辑上 的两个数据元素，在物理存储上赋予 位置的一

种存储分配方式。 相连 相邻

8、1976年，Wirth教授发表了名为 的著作，该著作在全世界第一次系统地阐

明了 的重要作用。 算法+数据结构=程序 算法与数据结构在程序设计中

9、数据元素之间的相互关系由一组运算和规则描述的数据元素的集合，

称为数据的 结构。 逻辑

10、数据元素之间的关系在计算机中有两种不同的表示方式，即顺序映象和非顺序映象。由此而得

出的两种不同的物理结构分别是 和 。 顺序物理结构 链式物理结构

11、计算机算法必备的三个主要特征分别是 、 和 。 确定性、有穷性和可执行性。

12、线性表的顺序存储结构是一种 存取的存储结构。 随机

13、线性表的链式存储结构是一种 存取的存储结构。 顺序

14、计算机算法是指 。 解题步骤的精确描述

15、计算机算法分析的目的主要是 分析。 效率

16、在线性结构中，开始结点 前趋结点，其余每个结点有且只有 前趋结点。 没有 一个

17、线性表的 被定义为表中元素的个数。 长度 二、单选题

1、计算机算法分析的目的是 。

A、使算法简明易懂业务 B、找出数据结构的合理性

C、研究算法的输入/输出关系 D、分析算法的效率，寻求改进途径

D

2、数组通常具有的两种基本操作是 。 A、建立与删除 B、索引与修改

C、查找与修改 D、查找与索引 C

三、判断题（正确的写Y，反之写N）

1、线性链表是一种顺序存取的存储结构。 （ ） Y

2、要存储1000个人名，用线性链表比用普通数组需要更少的存储空间。 （ ） N

3、能在线性表上进行的操作，就一定能在栈上进行。 （ ） N

4、虽说静态链表是用数组来实现的，但对其进行插入和删除操作时，却并不涉及数组元素的移动问题。 （ ）

Y

5、由于静态链表是用数组来实现的，所以在对其进行插入和删除操作时，存在着一个数组元素的移动问题。 （ ）

N

6、线性表的顺序存储结构是一种随机存取的存储结构。 （ ） Y

7、由于线性链表的存取必须顺序进行，所以在线性链表上删除一个结点时，必须移动其后的所有结点，才能继续保持一个顺序存取的关系。 （ ）

N

8、线性表顺序存储结构的存储密度大于线性表的链式存储结构。 （ ） Y

9、由于线性表的链式存储结构可以见缝插针的有效地利用存储空间，所以线性表的链式存储结构的存储密度大于线性表的顺序存储结构。 （ ）

N

10、线性表的逻辑顺序与存储顺序总是一致的。 （ ） N

11、线性表的链式存储结构和顺序存储结构不同，它要求内存中可用的存储单元的地址一定是不连续的。 （ ）

N 四、简答题

1、什么是线性表？它的三个基本特征是什么？ 答：

所谓线性表，是指由n(n≥0)个数据元素构成的有限序列。表中除第一个和最后一个以外的每个数据元素均有且仅有一个直接前趋元素和一个直接后继元素。

线性表的三个基本特征是：

（1）表中所有数据元素性质相同，即具有相同的数据类型；

（2）数据元素在表中的位置只取决于它们自己的序号，数据元素之间的相对位置是线性的；

（3）线性表的长度被定义为表中元素的个数。

2、什么是时间复杂度？影响时间复杂度主要因素是什么？ 答：

时间复杂度是指：当问题的规模以某种单位由1增加到n时，依据求解该问题的算法所编制的程序运行时所消耗的时间也以某种单位由1增加到Ctf(n)，Ct为常数， f(n)是问题规模的函数。我们通常称T(o)=O(f(n))为时间复杂度。

影响时间复杂度主要因素是：程序运行时所需输入的数据总量；对源程序编译的时间以及编译所产生的代码质量；计算机执行每条指令的时间；程序中指令重复执行的次数（语句频度），这一点最重要。

五、算法设计题

1、已知线性链表LA，用户输入一个数据元素值，假定该值一定在LA中。请设计一个在用户给定值

的前一个位置插入一个新元素的算法。

评分注意：算法设计题的答案通常不唯一；允许学生用某种语言的程序或各种不同的伪码来描述自己的算法；评分时，先考虑算法是否正确解决了问题，然后再考虑算法是否是高效率的。

2一个有序的数据元素序列，以线性链表存储。请设计一个算法，在该链表上插入一个新的数据元素，并保持链表的有序性。

评分注意：算法设计题的答案通常不唯一；允许学生用某种语言的程序或各种不同的伪码来描述自己的算法；评分时，先考虑算法是否正确解决了问题，然后再考虑算法是否是高效率的。 3、计一个算法，将一个顺序存储的数据元素的有序序列就地逆置。

评分注意：算法设计题的答案通常不唯一；允许学生用某种语言的程序或各种不同的伪码来描述自己的算法；评分时，先考虑算法是否正确解决了问题，然后再考虑算法是否是高效率的。

第三章 栈和队列

一、填充题（每空1分，共21分）

1、队列是一种限定仅在一端进行插入（入队），而在另一端进行删除（出队）的线性表，允许进行删除（出队）操作的一端称之为 。

队头

2、栈是一种具有先进 出特性的线性表。 后

二、单选题（每题2分，共24分） 1、栈和队列都是 。

A、顺序存储的线性结构 B、链式存储的非线性结构 C、限制存取点的非线性结构 D、限制存取点的线性结构 D

2、表达式(8+3*6)/(2+3*5-4)的逆波兰形式是 。

A、8 3 6*+2 3 5*+4-/ B、8+3 6*2+3 5*-4/ C、8+*3 6+2*3 5/4- D、8 3 6 +*2 3 5+*4-/ A

3、设有三个数据元素X、Y、Z顺序进栈，在进栈过程中可以出栈，请问下列出栈次序中的错误排列是 。

A、XYZ B、YZX C、ZXY D、ZYX C

4、在列车调度网络中，有四个车皮编号分别为1，2，3，4，并按此顺序随时送入栈中进行调度，这些车皮取出的顺序可以是 。

A、4123 B、3241 C、3412 D、4312 B

5、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是 。 A、edcba B、decba C、dceab D、abcde C

6、已知一个栈的入栈序列是1，2，3，……，n，其输出序列是p1，p2，p3，……，pn，如果p1=n，则pi为 。

A、i B、n=i C、不确定 D、n-i+1 D

7、将递归算法转换成对应的非递归算法时，通常需要使用 。 A、栈 B、队列

C、链表 D、树 A

三、判断题（正确的写Y，反之写N。不答不得分，答错倒扣分。每题2分，共22分）

3、能在线性表上进行的操作，就一定能在栈上进行。 （ ） N

1、队列具有后进先出的特性。 （ ） N

2、对栈的操作，构成了对线性表操作的一个子集。 （ ）

Y

3、在用数组实现的顺序队列上，当队列的尾指针指向数组的末尾时，则该队列一定是存满了数据元素。 （ ）

N

4、一个栈的输入序列是12345，则可能的一种输出序列是43512。 （ ）

N

四、简答题（每题3分，共18分）

1、什么是队列的假溢出？通常可以采用什么办法解决假溢出？ 答：

所谓的假溢出是指：在用数组模拟的顺序队列中，队列的尾指针已指向数组的最大下标位置，而头指针却并非指向数组的最小下标的前一位置，而是指向数组中的某一位置。此时若作入队操作，则出现上溢现象，但实际上队列中却并未存满，故称为假溢出。

解决的办法通常是移动元素或利用循环队列，前者要增加时间复杂度，后者实现较复杂。

第四五章 串 数组和广义表

一、填充题（每空1分，共21分）

1、一个串中任意个 的字符组成的子序列称为该串的子串。 连续

2、串的静态存储结构中的两种不同的存储方式分别是 格式和 格式。 非紧缩 紧缩

3、计算Fibonacci序列第n项的值，可以利用关系式1： F1=0， F2=0， Fi=Fi-2+Fi-1 也可以利用关系式2：

F(1)=0 ， F(2)=0 ， F(i)=F(i-2)+F(i-1)

比较次两种方法可以知道，关系式1是 算法，而关系式2是 算法。 递推（迭代） 递归

4、两个串的相等，是指两个两串的 相等， 相同。 长度 对应位置的字符

二、单选题（每题2分，共24分）

1、给出字符串A=’abcd’，它的子串个数是 。 A、10 B、9 C、11 D、14 C

2、给出两个串A=’ABCDE’，B=’ABCdE’，它们的关系是不是 。 A、B串大于A串 B、B串等于A串

C、B串小于A串 D、B串是A串的子串 A

3、设有两个串A和B，求B在A中首次出现的位置的操作称作 。 A、连接 B、求串长