数据结构习题和答案及解析
第 1 章绪论
课后习题讲解
1. 填空
⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
【解答】数据元素
⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。
【解答】数据项，数据元素
【分析】数据结构指的是数据元素以及数据元素之间的关系。
⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。
【解答】集合，线性结构，树结构，图结构
⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。
【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系
⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。
【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性
⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。
【解答】自然语言，程序设计语言，流程图，伪代码，伪代码
⑺在一般情况下，一个算法的时间复杂度是（）的函数。
【解答】问题规模
⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。
【解答】Ο(1)，Ο(nlog2n)
【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。
2. 选择题
⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。
A 线性结构
B 非线性结构
C 存储位置
D 指针
【解答】C，D
【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。
⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。
A 树
B 图
C 线性表
D 集合
【解答】B
【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。
⑶算法指的是（）。
A 对特定问题求解步骤的一种描述，是指令的有限序列。
B 计算机程序
C 解决问题的计算方法
D 数据处理
【解答】A
【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。
⑷下面（）不是算法所必须具备的特性。
A 有穷性
B 确切性
C 高效性
D 可行性
【解答】C
【分析】高效性是好算法应具备的特性。
⑸算法分析的目的是（），算法分析的两个主要方面是（）。
A 找出数据结构的合理性
B 研究算法中输入和输出的关系
C 分析算法的效率以求改进
D 分析算法的易读性和文档性
E 空间性能和时间性能
F 正确性和简明性
G 可读性和文档性 H 数据复杂性和程序复杂性
【解答】C，E
⑴算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。
【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。
⑵每种数据结构都具备三个基本操作：插入、删除和查找。
【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。
⑶所谓数据的逻辑结构指的是数据之间的逻辑关系。
【解答】错。是数据之间的逻辑关系的整体。
⑷逻辑结构与数据元素本身的内容和形式无关。
【解答】对。因此逻辑结构是数据组织的主要方面。
⑸基于某种逻辑结构之上的基本操作，其实现是唯一的。
【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。
4. 分析以下各程序段，并用大O记号表示其执行时间。
【解答】⑴基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。
⑵基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。
⑶分析条件语句，每循环一次，i+j 整体加1，共循环n次，所以T(n)=O(n)。
⑷设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即：
(T(n)+1)2≤n，所以T(n)=O(n1/2)。
⑸ x++是基本语句，所以
5．设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，
R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种结构。【解答】其逻辑结构图如图1-3所示，它是一种图结构。
6. 为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。
【解答】整数的抽象数据类型定义如下：
ADT integer
Data
整数a：可以是正整数(1, 2, 3, … )、负整数(-1, -2, -3, …)和零Operation
Constructor
前置条件：整数a不存在
输入：一个整数b
功能：构造一个与输入值相同的整数
输出：无
后置条件：整数a具有输入的值
Set
前置条件：存在一个整数a
输入：一个整数b
功能：修改整数a的值，使之与输入的整数值相同
输出：无
后置条件：整数a的值发生改变
Add
前置条件：存在一个整数a
输入：一个整数b
功能：将整数a与输入的整数b相加输出：相加后的结果
后置条件：整数a的值发生改变Sub
前置条件：存在一个整数a
输入：一个整数b
功能：将整数a与输入的整数b相减输出：相减的结果
后置条件：整数a的值发生改变Multi
前置条件：存在一个整数a
输入：一个整数b
功能：将整数a与输入的整数b相乘输出：相乘的结果
后置条件：整数a的值发生改变
Div
前置条件：存在一个整数a
输入：一个整数b
功能：将整数a与输入的整数b相除
输出：若整数b为零，则抛出除零异常，否则输出相除的结果后置条件：整数a的值发生改变
Mod
前置条件：存在一个整数a
输入：一个整数b
功能：求当前整数与输入整数的模，即正的余数
输出：若整数b为零，则抛出除零异常，否则输出取模的结果后置条件：整数a的值发生改变
Equal
前置条件：存在一个整数a
输入：一个整数b
功能：判断整数a与输入的整数b是否相等
输出：若相等返回1，否则返回0
后置条件：整数a的值不发生改变
endADT
7. 求多项式A(x)的算法可根据下列两个公式之一来设计：
⑴ A(x)=anxn+an-1xn-1+…+a1x+a0
⑵A(x)=(…(anx+an-1)x+…+a1)x)+a0
根据算法的时间复杂度分析比较这两种算法的优劣。
【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。
8. 算法设计（要求：算法用伪代码和C++描述，并分析最坏情况下的时间复杂度）
⑴对一个整型数组A[n]设计一个排序算法。
【解答】下面是简单选择排序算法的伪代码描述。
下面是简单选择排序算法的C++描述。
分析算法，有两层嵌套的for循环，所以，。
⑵找出整型数组A[n]中元素的最大值和次最大值。
【解答】算法的伪代码描述如下：
算法的C++描述如下：
分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。学习自测及答案
1．顺序存储结构的特点是（），链接存储结构的特点是（）。
【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。
2. 算法在发生非法操作时可以作出处理的特性称为（）。
【解答】健壮性
3. 常见的算法时间复杂度用大Ｏ记号表示为：常数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)
4．将下列函数按它们在n 时的无穷大阶数，从小到大排列。
n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n
【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n!
5．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。
6. 对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图，并指出属于何种结构。
⑴ A=(D，R)，其中D={a1, a2, a3, a4}，R={ }
⑵ B=(D，R)，其中D={a, b, c, d, e, f}，R={,,,,}
⑶ C=( D，R)，其中D={a，b，c，d，e，f}，R={,,,,,}
⑷ D=(D，R)，其中D={1, 2, 3, 4, 5, 6}，
R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)}
【解答】⑴属于集合，其逻辑结构图如图1-4(a)所示；⑵属于线性结构，其逻辑结构图如图1-4(b)所示；
⑶属于树结构，其逻辑结构图如图1-4(c)所示；⑷属于图结构，其逻辑结构图如图1-4(d)所示。
7. 求下列算法的时间复杂度。
count=0; x=1;
while (x {
x*=2;
count++;
}
return count;
【解答】Ｏ(log2n)
第 2 章线性表
课后习题讲解
1. 填空
⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。
【解答】表长的一半，表长，该元素在表中的位置
⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。
【解答】108
【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108
⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。
【解答】p->next=(p->next)->next
⑷单链表中设置头结点的作用是（）。
【解答】为了运算方便
【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。
⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。
【解答】p->next=head
【分析】如图2-8所示。
⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。
【解答】s->next =rear->next; rear->next =s; rear =s;
q=rear->next->next; rear->next->next=q->next; delete q;
【分析】操作示意图如图2-9所示：
⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。
【解答】Ο(1)，Ο(n)
【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。
⑻可由一个尾指针唯一确定的链表有（）、（）、（）。
【解答】循环链表，循环双链表，双链表
2. 选择题
⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。
A 随机存取
B 顺序存取
C 索引存取
D 散列存取
【解答】A，B
【分析】参见2.2.1。
⑵线性表采用链接存储时，其地址（）。
A 必须是连续的
B 部分地址必须是连续的
C 一定是不连续的
D 连续与否均可以
【解答】D
【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。
⑶单循环链表的主要优点是（）。
A 不再需要头指针了
B 从表中任一结点出发都能扫描到整个链表；
C 已知某个结点的位置后，能够容易找到它的直接前趋；
D 在进行插入、删除操作时，能更好地保证链表不断开。
【解答】B
⑷链表不具有的特点是（）。
A 可随机访问任一元素
B 插入、删除不需要移动元素
C 不必事先估计存储空间
D 所需空间与线性表长度成正比
【解答】A
⑸若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。
A 顺序表
B 单链表
C 双链表
D 单循环链表
【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。
⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。
A 单链表
B 带头指针的单循环链表
C 双链表
D 带尾指针的单循环链表
【解答】D
【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D 。
⑺若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省运算时间。
A 单链表
B 循环双链表 C单循环链表 D 带尾指针的单循环链表
【解答】B
【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。
⑻在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。
A O(1)
B O(n)
C O(n2)
D O(nlog2n)
【分析】首先应顺序查找新结点在单链表中的位置。
⑼对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。
A O(1)
B O(n)
C O(n2)
D O(nlog2n)
【解答】C
【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。
⑽使用双链表存储线性表，其优点是可以（）。
A 提高查找速度
B 更方便数据的插入和删除
C 节约存储空间
D 很快回收存储空间
【解答】B
【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。
⑾在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（）操作。
A s->next=p->next; p->next=s;
B q->next=s; s->next=p;
C p->next=s->next; s->next=p;
D p->next=s; s->next=q;
【解答】B
【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。
⑿在循环双链表的p所指结点后插入s所指结点的操作是（）。
A p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
C s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
D s->prior=p; s->next=p->next; p->next->prior=s; p->next=s
【解答】D
【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。
3. 判断题
⑴线性表的逻辑顺序和存储顺序总是一致的。
【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。
⑵线性表的顺序存储结构优于链接存储结构。
【解答】错。两种存储结构各有优缺点。
⑶设p，q是指针，若p=q，则*p=*q。
【解答】错。p=q只能表示p和q指向同一起始地址，而所指类型则不一定相同。
⑷线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。
【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。
⑸在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。
4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。
⑴若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。
⑵如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。
⑶描述一个城市的设计和规划。
【解答】顺序表的优点：①无需为表示表中元素之间的逻辑关系而增加额外的存储空间；②可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：①插入和删除操作需移动大量元素；②表的容量难以确定；③造成存储空间的“碎片”。
单链表的优点：①不必事先知道线性表的长度；②插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：①指针的结构性开销；②存取表中任意元素不方便，只能进行顺序存取。
⑴应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。
⑵应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。
⑶应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。
5．算法设计
⑴设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环右移k个位置。
【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。
分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为
O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(n)。
⑵已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为Ｏ(n)。
【解答】从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。具体算法如下：
分析算法，两层循环将数组扫描一遍，所以，时间复杂度为Ｏ(n)。
2017年数据结构期末考试题及答案A
2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
数据结构试题库答案
数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 数据结构考试题库 绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。 ？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理，用心做精品2 A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中，从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时，要求内存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构 一、填空题 1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理，用心做精品3 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head！=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表：表中各结点都没有直接前趋和直接后继。 在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中，使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表 栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234，则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by . a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search 第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next 数据结构考试及答案（） 作者: 日期: 2 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D） A 必须是连续的B部分地址必须是连续的 C 一定是不连续的D可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 （D ）。 An B n/2 C （n-1）/2 D （n+1）/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D ）o A s—link = p—link ；p—link = s； B p—link = s; s—link = q; C p—link = s—link ；s—link = p； D q—link = s; s—link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（C ）方法最好。 A 起泡排序 B 堆排序C锦标赛排序 D 快速 排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（B ）o A 求子串B模式匹配C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j] 占用3个存储字，行下标i从1到8, 列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈B队列C循环队列D优先队列 9、一个队列的进队列顺序是1,2, 3, 4 ，则出队列顺序为（C ）。 10、在循环队列中用数组A[0.. m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A （ front - rear + 1） % m B （rear - front + 1） %m C （ front - rear + m） % m D （ rear - front + n） % m 11、一个数组元素a[i]与（A ）的表示等价。 A * （a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数 A指针 B 引用C值 D 变量 13、下面程序段的时间复杂度为（C) for (i nt i=0;i 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 数据结构习题 习题一 一、选择题 1、算法分析的两个主要方面是：（） A．正确性和简明性B．时间复杂度和空间复杂度 C．数据复杂性和程序复杂性D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3、计算机算法具备输入、输出和（）等5个特性： A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性 4、算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系， 图形结构中元素之间存在的关系。 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。 4、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。 5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j 绪论 一、填空题 1.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系 4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。 for(i=n-1；i>=0；i--) for(j=0；j数据结构考试题库
数据结构课后习题及解析第二章
数据结构期末考试试题及答案
数据结构题库教材
《数据结构》期末考试题及答案
数据结构例题解析(1)
数据结构相关题库及答案
数据结构考试及答案()
数据结构第一章课后习题与答案
2015年数据结构期末考试题及答案
数据结构题库汇总
数据结构考试题库
数据结构考试题库含参考答案
数据结构期末考试试题及答案
算法与数据结构题库与答案
数据结构期末考试试题及答案