数据结构第二章线性表1答案.pdf

《数据结构第二章线性表1答案.pdf》由会员分享，可在线阅读，更多相关《数据结构第二章线性表1答案.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二部分第二部分 线性表线性表一、选择题1关于顺序存储的叙述中,哪一条是不正确的( B )A. 存储密度大B. 逻辑上相邻的结点物理上不必邻接C. 可以通过计算直接确定第i 个结点的位置D. 插入、删除操作不方便2长度为 n 的单链表连接在长度为m 的单链表后的算法的时间复杂度为 ( C )AO(n)BO(1)CO(m)DO(m+n)3在 n 个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( A )A访问第 i 个结点（1=i=n）和求第 i 个结点的直接前趋（2=i=n）B在第 i 个结点（1=i=n）后插入一个新结点C删除第 i 个结点（1=ilink=p;p-link=s;（B）

2、s-link=p-link;p-link=s;（C）s-link=p-link;p=s;（D）p-link=s;s-link=p;16. 在循环链表中 first 为指向链表表头的指针，current 为链表当前指针，在循环链表中检测current 是否达到链表表尾的语句是(D)。（A）current-link=NULL(B)first-link=current（C）first=current(D)current-link=first17. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较(D)个结点。A. nB. n/2C.（n-1）/2D. (n+1

3、)/218. 在一个具有 n 个结点的有序单链表中，插入一新结点并仍然有序的时间复杂度为( B )。A. O(1)B. O(n)C. O(n2)D. O(nlog2n)19. 用链表表示线性表的优点是 ( C)。A. 便于随机存取B. 花费的存储空间比顺序表少C. 便于插入与删除D. 数据元素的物理顺序与逻辑顺序相同20. 当需要随机查找线性表的元素时,宜采用( C )作存储结构。A. 双向链表B. 循环链表C. 顺序表D. 单链表21. 线性表的链接实现有利于（ A ）运算。A、插入b、读表元c、查找d、定位22. 线性表采用链式存储时，其地址（ D ） 。A必须是连续的B部分地址是连续的C

4、一定是不连续的D连续与否均可以23. 设单链表中指针 p 指着结点 a，若要删除 a 之后的结点（若存在） ，则需要修改指针的操作为（A） 。A、p-next=p-next-nextb、p=p-nextC、 p= p-next-nextd、p-next=p24. 向一个有 127 个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（ B ）个元素。A、8B、63.5C、63D、725. 向一个有 127 个元素的顺序表中删除一个元素，平均要移动（ C ）个元素（A） 8（B） 63.5（C） 63（D） 726. 用链表表示线性表的优点是（ A ）A 便于插入和删除操作B 数据元素的

5、物理顺序与逻辑顺序相同D 便于随即存取C 花费的存储空间较顺序存储少27. 以下数据结构中不属于线性数据结构的是（ C ）A 队列B 线性表C 二叉树D 栈28对长度为 N 的线性表进行顺序查找，在最坏情况下所需要的比较次数为（ B ） 。AN+1BNC(N+1)/2DN/229下列叙述中正确的是( A )。A. 线性表是线性结构B. 栈与队列是非线性结构D. 二叉树是线性结构C. 线性链表是非线性结构30在单链表中，增加头结点的目的是( A )。A. 方便运算的实现B. 使单链表至少有一个结点D. 说明单链表是线性表的链式存储实现C. 标识表结点中首结点的位置31线性表的顺序存储结构和线性表

6、的链式存储结构分别是（ B ） 。A. 顺序存取的存储结构、顺序存取的存储结构B. 随机存取的存储结构、顺序存取的存储结构C. 随机存取的存储结构、随机存取的存储结构D. 任意存取的存储结构、任意存取的存储结构33线性表中正确的说法是( D )。A. 每个元素都有一个直接前驱和一个直接后继B. 线性表至少要求一个元素C. 表中的元素必须按由小到大或由大到小排序D. 除了第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继34线性表是具有 n 个（ C ）的有限序列。A. 表元素B. 字符C. 数据元素D. 数据项35 若长度为 n 的线性表采用顺序存储结构， 在其第 i 个

7、位置插入一个新元素的算法的时间复杂度为（ C ） 。 （1in+1）A. O(0)B. O(1)C. O(n)D. O(n2)36在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度（B） 。A. O(1)B. O(n)C. O(nlogn)D. O(n2)37某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素，那么采用（ A ）存储方式最节省运算时间。二、填空题1在单项链表中删除一个指定结点的后继的时间复杂度为 O(1) 2线性表中 _数据元素的个数_ 称为表的长度。3. 在 n 个结点的单链表中，在 P 指向的结点之后插

8、入一个结点的时间复杂度为 _O（n） 。4设长度为 n 的线性表顺序存贮,若在它的第 i-1 和第 i 个元素之间插入一个元素, 共需移动_n-i+1_ 个元素(1link;p-link=_ p-link -link _Delete q9将适当的语句添入单链表搜索函数find 中。templateListNode*List:find(Type value)A. 仅有尾指针的单向循环链表C. 单向链表B. 仅有头指针的单向循环链表D. 双向链表current=first-link；while(current!=NULL)if(current-data=value)breakelse curren

9、t=current-link;return _ current _10顺序存储方法是把逻辑上相邻的结点存储在物理位置 _也相邻_ 的存储单元中。11顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻。因此，这种表便于_随机_访问，是一种_随机访问存储结构_。12 在一个不带头结点的单链表中， 在表头插入或删除与其在其他位置插入或删除操作的过程_不相同_。13已知 L 是无头结点的单链表，且 P 结点既不是首元素结点，也不是尾元素结点，添加合适的语句。1) P 结点之后插入结点 S：S-next=P-next; P-next=S;2) P 结点之前插入结点 S：pre=L;while(pr

10、e-next!=P) pre=pre-next;S-next=P; pre-next=S;3) 在表首插入结点 S：S-next=L; L=S;4) 在表尾插入结点 S：while(P-next) P=P-next;P-next=S; S-next=NULL;14已知 P 结点是某双向链表的中间结点，添加合适的语句。1) P 结点之后插入结点 S：S-next=P-next; S-prior=P;P-next-Prior=S; P-next=S;2) P 结点之前插入结点 S：S-next=P; S-prior=P-prior;P-prior-next=S; P-prior=S;3) 删除 P

11、 结点的直接后继结点：Q=P-next; P-next=Q-next; Q-next-prior=P; free(Q);4) 删除 P 结点的直接前驱结点：Q=P-prior; P-prior=Q-prior; Q-prior-next=P; free(Q);5) 删除 P 结点：P-prior-next=P-next; P-next-prior=P-prior; free(P);15 在链表的结点中， 数据元素所占存储量和整个结点所占的存储量之比称作存储密度。三、判断题1线性链表中各个链结点之间的地址不一定要连续。( R )2若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适

12、。( W )3若线性表采用顺序存储结构，每个数据元素占用 4 个存储单元，第 12 个数据元素的存储地址为 144，则第 1 个数据元素的存储地址是 101。( W )4若长度为 n 的线性表采用顺序存储结构，删除表的第 i 个元素之前需要移动表中 n-i+1个元素。( W )5在顺序表中取出第 i 个元素所花费的时间与 i 成正比。 （ W ）四、写出下列算法完成的功能1）ListNode *Demo1(LinkList L, ListNode *p)/*L 是带有头结点的单链表*/ListNode *q = L-next;while(q & q-next !=p)q = q-next;if

13、(q)return q;elseerror(“*p is not in L!”);寻找结点 P 的前驱结点，若存在则返回前驱结点的地址，若不存在则给出错误信息2) void Demo2(ListNode *p, ListNode *q)DataType temp;temp = p-data;p-data = q-data;q-data = temp;交换结点 p 和 q 数据域的内容3) LinkList Demo3(LinkList L)/*L 是无头结点的单链表*/ListNode *p, *q;if(L & L-next)q=L;return L;L=L-next;p=L;While(p-next)p-next = q;q-next = NULL;p=p-next;将链表 L 第一个结点变为最后一个结点4) LinkList *Connect(LinkList *L1, LinkList *L2)/* L1,L2 是带有头结点的单链表*/LinkList *p;p=L1;while(p-next!=NULL)p-next = L2-next;return(L1);p=p-next;将 L2 连接到 L1 后面