数据结构各章复习资料
数据结构复习参考题资料
计算机科学与技术专业
202010
f数据结构各章复习资料
第一章绪论
一、选择题
1、在数据结构的讨论中把数据结构从逻辑上分为C。
A、内部结构与外部结构
B、静态结构与动态结构
C、线性结构与非线性结构
D、紧凑结构与非紧凑结构
2、下面程序段的时间复杂度为C。
fori
ti0imi
fori
tj0j
j
aijij
A、Om2
B、O
2
C、Om
D、Om

3、执行下面程序段时，执行S语句的次数为D。
fori
ti1i
i
fori
tj1jij
S
A、
2
B、
22
C、
1D、
12
４、某算法的时间代价为T（
）100
10
Log2
210，其时间复杂度为（C）。
A、O（
）B、O
log2
C、O
2D、O1
二、填空题
１、数据结构的抽象数据类型ADT可用三元组表示（D，S，P），其中D是（数据对象），S是关系集，P是操作集。２、数据的基本单位是数据元素最小单位是数据项。3、一个算法的时间复杂性通常用它的T（
）OF
形式表示，当一个算法的时间复杂性与问题的规模
大小无关时，则表示为O1；成正比时，则表示为O
；成对数关系时，则表示为Olog2
；成平方关系时，则表示为O
2。4、我们常常称数据的逻辑结构为数据结构，数据的逻辑结构有两类：线性结构，非线性结构。5、一个算法应该具有有穷性、确定性、可行性、零个或多个输入、一个或多个输出五个特征。6、数据结构中的逻辑结构具体分为四种分别是（线性结构）（树型结构）（图或网型结构）（集合）。7、数据结构中的存储结构具体分为二种分别是（顺序存储结构）（链式存储结构）。
三、简答题
1、比较顺序存储结构和链式存储结构的优缺点？参考答案：1）顺序表的特点是逻辑上相邻的数据元素，物理存储位置也相邻，并且，顺序表的存储空间需要预先分配。它的优点是：
f数据结构各章复习资料
（1）方法简单，各种高级语言中都有数组，容易实现。（2）不用为表示节点间的逻辑关系而增加额外的存储开销。（3）顺序表具有按元素序号随机访问的特点。缺点：（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对
较大的顺序表效率低。（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。2）在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。链表的最大特点是：插入、删除运算方便。缺r