数据结构本形成性考核作业答案
作业1本部分作业覆盖教材第12章的内容
一单项选择题1C2D3B4C5D6C7B8C9A10B
11C12D13C14A15B16C
17C18B19B20D
二填空题1
i12
i3集合线性结构树形结构图状结构
4物理结构存储结构5线性结构6有穷性7图状结构8树形结构9线性结构10
1O
非线性结构确定性可形性有零个或多个输入有零个或多个输出
11s
extp
ext12head
f13q
extp
ext14p
exthead15单链表16顺序存储链式存储17存储结构18两个直接后继直接前驱19头结点的指针20链式链表尾结点头结点
指向第一个结点的指针
三问答题1简述数据的逻辑结构和存储结构的区别与联系它们如何影响算法的设计与实现答若用结点表示某个数据元素则结点与结点之间的逻辑关系就称为数据的逻辑结构数据在计算机中的存储表示称为数据的存储结构可见数据的逻辑结构是反映数据之间的固有关系而数据的存储结构是数据在计算机中的存储表示尽管因采用的存储结构不同逻辑上相邻的结点其物理地址未必相同但可通过结点的内部信息找到其相邻的结点从而保留了逻辑结构的特点采用的存储结构不同对数据的操作在灵活性算法复杂度等方面差别较大
2解释顺序存储结构和链式存储结构的特点并比较顺序存储结构和链式存储结构的优缺点答顺序结构存储时相邻数据元素的存放地址也相邻即逻辑结构和存储结构是统一的要求内存中存储单元的地址必须是连续的优点一般情况下存储密度大存储空间利用率高缺点1在做插入和删除操作时需移动大量元素2由于难以估计必须预先分配较大的空间往往使存储空间不能得到充分利用3表的容量难以扩充
f链式结构存储时相邻数据元素可随意存放所占空间分为两部分一部分存放结点值另一部分存放表示结点间关系的指针优点插入和删除元素时很方便使用灵活缺点存储密度小存储空间利用率低
3什么情况下用顺序表比链表好答顺序表适于做查找这样的静态操作链表适于做插入和删除这样的动态操作如果线性表的变化长度变化不大且其主要操作是查找则采用顺序表如果线性表的长度变化较大且其主要操作是插入删除操作则采用链表
4解释头结点第一个结点或称首元结点头指针这三个概念的区别答头结点是在链表的开始结点之前附加的一个结点第一个结点或称首元结点是链表中存储第一个数据元素的结点头指针是指向链表中第一个结点或为头结点或为首元结点的指针
5解释带头结点的单链表和不带r