数据结构单元2练习参考答案

《数据结构单元2练习参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单元练习2一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（×）（1）线性表的链式存储结构优于顺序存储。（×）（2）链表的每个结点都恰好包含一个指针域。（√）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。（×）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。（√

2、）（8）线性表采用顺序存储，必须占用一片连续的存储单元。（×）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。二．填空题（1）顺序表中逻辑上相邻的元素在物理位置上必须相连。（2）线性表中结点的集合是有限的，结点间的关系是一对一关系。（3）顺序表相对于链表的优点是：节省存储和随机存取。（4）链表相对于顺序表的优点是：插入、删除方便。（5）采用顺序存储结构的线性表叫顺序表。（6）顺序表中访问任意一个结点的时间复杂度均为O(1)。（7）链表相对于顺序表的优点是插入、删除方便；

3、缺点是存储密度小。（8）在双链表中要删除已知结点*P，其时间复杂度为O(1)。（9）在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为O(n)。（10）单链表中需知道头指针才能遍历整个链表。（11）线性表中第一个结点没有直接前趋，称为开始结点。（12）在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。（13）在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n-i+1个元素。（14）在无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储地址存放在前趋结点的指针域中。（15）当线性表的元

4、素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储结构。（16）在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。（17）在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结点。（10）对一个需要经常进行插入和删除操作的线性表，采用链式存储结构为宜。（11）双链表中，设p是指向其中待删除的结点，则需要执行的操作为：p->prior->next=p->next;p->next->prior=p->prior。（12）在如图所示的链表中，若在指针P所在的结点之后插入数据域值为a和b的两个结点，则可用

5、下列两个语句：S->next->next=P->next和P->next=S来实现该操作。PΛabS三．选择题（1）在具有n个结点的单链表中，实现（A）的操作，其算法的时间复杂度都是O（n）。A．遍历链表或求链表的第i个结点B．在地址为P的结点之后插入一个结点C．删除开始结点D．删除地址为P的结点的后继结点（2）设a、b、c为三个结点，p、10、20分别代表它们的地址，则如下的存储结构称为（B）。a10c^b20PA．循环链表B．单链表C．双向循环链表D．双向链表（3）单链表的存储密度（C）。A．大于1B．等于1C．小于1D．不能确定（4）已知一个顺序存储的线性表，设每个结

6、点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（A）。A．B+(i-1)*mB．B+i*mC．B-i*mD．B+(i+1)*m（5）在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（B）。A．O（1）B．O（n）C．O（n2）D．O（log2n）（6）设Llink、Rlink分别为循环双链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（D）。A．P==LB．P->Llink==LC．P==NULLD．P->Rlink==L（7）两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（B）。A．P->ne

7、xt==Q->nextB．P->next==QC．Q->next==PD．P==Q（8）用链表存储的线性表，其优点是（C）。A．便于随机存取B．花费的存储空间比顺序表少C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同（9）在单链表中，增加头结点的目的是（C）。A．使单链表至少有一个结点B．标志表中首结点的位置C．方便运算的实现D．说明该单链表是线性表的链式存储结构（10）下面关于线性表的叙述中，错误的是（D）关系。A．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素C．链表不必占用一片地址连续