欢迎来到天天文库
浏览记录
ID:48525497
大小:110.50 KB
页数:9页
时间:2020-02-25
《单元练习2_答案.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、单元练习2一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳)(×)(1)线性表的链式存储结构优于顺序存储。(×)(2)链表的每个结点都恰好包含一个指针域。(√)(3)在线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。(×)(4)顺序存储方式的优点是存储密度大,插入、删除效率高。(×)(5)线性链表的删除算法简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。(×)(6)顺序表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。(√)(7)线性表链式
2、存储的特点是可以用一组任意的存储单元存储表中的数据元素。(√)(8)线性表采用顺序存储,必须占用一片连续的存储单元。(×)(9)顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。(ㄨ)(10)插入和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也经常使用。二.填空题(1)顺序表中逻辑上相邻的元素在物理位置上必须相连。(2)线性表中结点的集合是有限的,结点间的关系是一对一关系。(3)顺序表相对于链表的优点是:节省存储和随机存取。(4)链表相对于顺序表的优点是:插入、删除方便。(5)采用顺序存储结构
3、的线性表叫顺序表。(6)顺序表中访问任意一个结点的时间复杂度均为O(1)。(7)链表相对于顺序表的优点是插入、删除方便;缺点是存储密度小。(8)在双链表中要删除已知结点*P,其时间复杂度为O(1)。(9)在单链表中要在已知结点*P之前插入一个新结点,需找到*P的直接前趋结点的地址,其查找的时间复杂度为O(n)。(10)单链表中需知道头指针才能遍历整个链表。(11)性表中第一个结点没有直接前趋,称为开始结点。(12)在一个长度为n的顺序表中删除第i个元素,要移动n-i个元素。(13)在一个长度为n的顺序表中,如果要在
4、第i个元素前插入一个元素,要后移n-i+1个元素。(14)在无头结点的单链表中,第一个结点的地址存放在头指针中,而其它结点的存储地址存放在前趋结点的指针域中。(15)当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快速度存取线性表中的元素时,应采用顺序存储结构。(16)在线性表的链式存储中,元素之间的逻辑关系是通过指针决定的。(17)在双向链表中,每个结点都有两个指针域,它们一个指向其前趋结点,另一个指向其后继结点。(10)对一个需要经常进行插入和删除操作的线性表,采用链式存储结构为宜。(11)双链
5、表中,设p是指向其中待删除的结点,则需要执行的操作为:p->prior->next=p->next。(12)在如图所示的链表中,若在指针P所在的结点之后插入数据域值为a和b的两个结点,则可用下列两个语句: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
6、为三个结点,p、10、20分别代表它们的地址,则如下的存储结构称为(B)。a10c^b20PA.循环链表B.单链表C.双向循环链表D.双向链表(3)单链表的存储密度(C)。A.大于1B.等于1C.小于1D.不能确定(4)已知一个顺序存储的线性表,设每个结点占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(log2
7、n)(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->next==Q->nextB.P->next==QC.Q->next==PD.P==Q(8)用链表存储的线性表,其优点是(C)。A.便于随机存取B.花费的存储空间比顺序表少C.便于插入和删除D.数据元素的物理顺
8、序与逻辑顺序相同(9)在单链表中,增加头结点的目的是(C)。A.使单链表至少有一个结点B.标志表中首结点的位置C.方便运算的实现D.说明该单链表是线性表的链式存储结构(10)下面关于线性表的叙述中,错误的是(D)关系。A.顺序表必须占一片地址连续的存储单元B.顺序表可以随机存取任一元素C.链表不必占用一片地址连续的存储单元D.链表可以随机存取任一元素(11)
此文档下载收益归作者所有