数据结构：线性表基础习题

《数据结构：线性表基础习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、存储表中的数据元素。)(8)线性表采用顺序存储，必须占用一片连续的存储单元。)(9)顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。(X用。)(10)插入和删除操作是数据结构中最基木的两种操作，所以这两种操作在数组中也经常使二.填空题(1)顺序表中逻辑上相邻的元素在物理位置上必须相连。(可以、必需、不能等)(2)(3)(4)(5)(6)(7)(8)(9)线性表中结点的集合是有限的，结点间的关系是依次相连关系。顺序表相对于链表的优点是：可以随机查找和随机存取。链表相对于顺序表的优点是：删除和插入方便。采用地址连续存储单元依次存储的存储结构的线性表叫顺

3、序表。顺序表中访问任意一个结点的时间复杂度均为0(1)。饌表相对于顺序表的优点是插入、删除方便：缺点是存储密度小。在双链表中要删除已知结点*P,其时间复杂度为0(1)。在单链表中要在已知结点*PZ前插入一个新结点，盂找到忖的直接前趋结点的地址，其查找的时间复杂度为(10)(11)(12)(13)(14)单链表中需知道才能遍历整个餡表。性表中第一•个结点没有总接询趋，称为结点。在一个长度为n的顺序表中删除第i个元素，要移动个元素。在一个长度为n的顺序表中，如果要在第i个元素询插入一个元素，要后移个元素。在无头结点的单链表中，第一个结点的地址存放在头指针中，而

4、其它结点的存储地址存放在结戊的指针域中。(15)当线性表的元索总数基木稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元索时，应采用存储结构。(16)(17)在线性表的礁式存储中，元素之间的逻辑关系是通过决定的。在双向链表中，每个结点都冇两个指针域，它们一个指向其结点，另—个指向其结点。（18）对一个需要经常进行插入和删除操作的线性表，采用存储结构为宜。（19）双链表屮，设p是指向其屮待删除的结点，则需要执行的操作为：o（20）在如图所示的链表屮，若在指创P所在的结点之示插入数据域值为a和b的两个结点，则可用下列两个语句：L和P->next二

5、S;来实现该操作。三.选择题（1）在具有n个结点的单链表中，实现（A.遍历链表或求链表的第i个结点C.删除开始结点）的操作，其算法的时间复杂度都是O（n）0B・在地址为P的结点Z后插入一个结点D.删除地址为P的结点的后继结点（2）设a、b、c为三个结点,p、10、20分别代表它们的地址,则如下的存储结构称为（）。P——>a10►b20>CAA.循环链表B.单链表C.双向循环链表D.双向链表（3）单链表的存储密度（）。A.大于1B.等于1C.小于1D.不能确定（4）己知一个顺序存储的线性衣，设每个结点占m个存储单元，若第一个结点的地址为B,则第i个结点的地址

6、为（）。B.B+i*mC.B—i*m（5）在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（）0A.0(1)B.0(n)C.0(n2)D.0(log2n)（6）设Llink、Rlink分别为循环双链衣结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（）。A.P=LB.P->Llink==LC.P二二NULLD.P->Rlink==L（7）两个指针P和Q,分别指向单链衣的两个元索,P所指元索是Q所指元索前驱的条件是（）A.P->ncxt==Q->nextB.P->next=Q（8）用链表存储的线性表，其优点是（）。A.便于随机存

7、取C.便于插入和删除（9）在单链表中，增加头结点的目的是（）。A.使单链表至少有一个结点C.方便运算的实现（10）下面关于线性表的叙述中，错误的是（A.顺序表必须占一片地址连续的存储单元C.Q->next==PD.P==QB.花费的存储空间比顺序表少D.数据元索的物理顺序与逻辑顺序相同B.标志表中首结点的位置D.说明该单链表是线性表的链式存储结构）关系。B.顺序表可以随机存取任一元素C.链表不必占用一片地址连续的存储单元D.链表可以随机存取任一元素(11)L是线性表,已知Leng山List(L)的值是5,经DelList(L,2)运算后,LengthLis

8、t(L)的值是()。A.2B.3C.4D.5(12)单链表的示意图