数据结构基础及深入及考试复习资料
习题及实验参考答案见附录
结论
1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态
线性表
1、线性表的存储结构包括顺序存储结构和链式存储结构两种。2、表长为
的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。A、
12B、
C、
1D、
1E、
2F、
12G、
223、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、headNULLB、head
extNULLC、head
extheadD、headNULL6、不带头结点的单链表head为空的判定条件是（A）A、headNULLB、head
extNULLC、head
extheadD、headNULL7、非空的循环单链表head的尾结点P满足（C）A、p
extNULLB、pNULLC、p
extheadD、phead8、在一个具有
个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O1B、O
C、O
2D、O
log2

f9、在一个单链表中，若删除p所指结点的后继结点，则执行（A）A、p
extp
ext
extB、pp
extp
extp
ext
extC、p
extp
extD、pp
ext
ext10、在一个单链表中，若在p所指结点之后插入s所指结点，则执行（B）A、s
extpp
extsB、s
extp
extp
extsC、s
extp
extr