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