《数据结构第二章线性表1答案》由会员分享，可在线阅读，更多相关《数据结构第二章线性表1答案（9页珍藏版）》请在金锄头文库上搜索。
1、第二部分 线性表一、选择题1关于顺序存储的叙述中,哪一条是不正确的 （ B ）A. 存储密度大B. 逻辑上相邻的结点物理上不必邻接C. 可以通过计算直接确定第i个结点的位置D. 插入、删除操作不方便2长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为（C ）A O（n） B O（1） C O（m） D O（m+n）3. 在n个结点的顺序表中，算法的时间复杂度是0（1）的操作是：（A ）A 访问第i个结点（1v = iv = n）和求第i个结点的直接前趋（2v = iv = n）B在第i个结点（1v = iv = n）后插入一个新结点C 删除第i个结点（1v = iv = n）D 将
2、n 个结点从小到大排序4一个向量第一个元素的存储地址是 100 ，每个元素的长度为 2 ，则第 5 个元素的地址是（ B ）（ A ） 110 （ B ） 108 （ C ） 100 （ D ） 1205. 已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da, 则第 i 个结点的地址为： （ A ）A） da+（i-1）*m B） da+i*m C） da-i*m D） da+（i+1）*m6. 在具有n个结点的单链表中，实现（A ）的操作，其算法的时间复杂度为0（n）。A）遍历链表和求链表的第i个结点 B）在地址为p的结点之后插入一个结点C）删除开始结点D）删除
3、地址为p的结点的后继结点7. 链表是一种采用（ B ）存储结构存储的线性表。（ A ）顺序 （ B ）链式 （ C ）星式 （ D ）网状8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（ D ）（ A ）必须是连续的 （ B ）部分地址必须是连续的（ C ）一定是不连续的 （ D ）连续或不连续都可以9. 线性表1在_ （ B ）情况下适用于使用链式结构实现。（A）需经常修改L中的结点值（B）需不断对L进行删除插入(C)L中含有大量的结点10 在长度为 n的顺序表的第 i11( A)A.n-i+1线性表是(B.n-i)。C.iD.i-1a、一个有限系列，可以为空c、一个无限系
4、列，可以为空b、一个有限系列，不能为空d、一个无限系列，不能为空12.A )线性表。A.(孔子,诸葛亮，曹雪芹)B.A,B,C,D(D)L中结点结构复杂(1ilink=p;p-link=s;(B) 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
5、(D)current-link=first17. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较( D )个结点。A. nB. n/2C.(n-1) /2D. (n+1)/218. 在一个具有 n 个结点的有序单链表中，插入一新结点并仍然有序的时间复杂度为( B )A. O(1)B. O(n)C. O(n2)D. O(nlog2n)19. 用链表表示线性表的优点是 ( C )。A. 便于随机存取B.花费的存储空间比顺序表少C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同20. 当需要随机查找线性表的元素时,宜采用( C )作存储结构。A. 双向链表
6、 B. 循环链表 C. 顺序表 D. 单链表21. 线性表的链接实现有利于（ A ）运算。A、插入 b、读表元 c、查找 d、定位22. 线性表采用链式存储时，其地址（ D ）。A 必须是连续的B 部分地址是连续的C 一定是不连续的D 连续与否均可以23. 设单链表中指针p指着结点a,若要删除a之后的结点（若存在），则需要修改指针的操作为（ A ）。b、 p=p-nextd、 p-next=pA、 p-next=p-next-nextC、 p= p-next-next24. 向一个有127 个元素原顺序表中插入一个新元素并保存原来顺序不变,平均要移动（ B ）个元素。A、 8B、 63.5C、
7、 63D、 725. 向一个有 127 个元素的顺序表中删除一个元素,平均要移动（ C ）个元素（A） 8（B） 63.5（C） 63（D） 726. 用链表表示线性表的优点是（ A ）A 便于插入和删除操作C 花费的存储空间较顺序存储少B 数据元素的物理顺序与逻辑顺序相同D 便于随即存取27. 以下数据结构中不属于线性数据结构的是（ C ）A 队列 B 线性表C 二叉树D 栈28. 对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为（B ）AN+1BNC（N+1）/2DN/229. 下列叙述中正确的是（ A ）。A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线
8、性结构D. 二叉树是线性结构30. 在单链表中，增加头结点的目的是（ A ）。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现31. 线性表的顺序存储结构和线性表的链式存储结构分别是（ B ）。A. 顺序存取的存储结构、顺序存取的存储结构B. 随机存取的存储结构、顺序存取的存储结构C. 随机存取的存储结构、随机存取的存储结构D. 任意存取的存储结构、任意存取的存储结构33.线性表中正确的说法是（ D ）。A. 每个元素都有一个直接前驱和一个直接后继B. 线性表至少要求一个元素C. 表中的元素必须按由小到大或由大到小排序D. 除
9、了第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继34. 线性表是具有门个(C )的有限序列。A. 表元素 B. 字符 C. 数据元素 D. 数据项35. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂 度为(C )。(1WiWn+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. 某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是 指删除表
10、头第一个元素，那么采用( A )存储方式最节省运算时间。A. 仅有尾指针的单向循环链表B. 仅有头指针的单向循环链表C. 单向链表D. 双向链表二、填空题1. 在单项链表中删除一个指定结点的后继的时间复杂度为 O(1) 2. 线性表中数据元素的个数_称为表的长度。3. 在n个结点的单链表中，在P指向的结点之后插入一个结点的时间复杂度为_O (n)o4. 设长度为 n 的线性表顺序存贮,若在它的第 i-1 和第 i 个元素之间插入一个元素, 共需移动_n-i+1_ _个元素(IviWn)。5. 在顺序表中访问任意结点的时间复杂度为0(1)，因此顺序表也称为随机存储 的数据结构。6. 在单链表中要
11、在已知结点*p之前插入一新结点，需找到 插入点，其时间复杂度为 0 (n)，而在双链表中，完成同样操作的时间复杂度为0 (1)。7. 循环链表的主要优点是从任何一个结点出发可以遍历所有结点。8. 在一个单链表中删除p所指结点的下一个结点时，应执行以下操作： q=p-link;p-link=Delete q9. 将适当的语句添入单链表搜索函数find中。templateListNode*List:find(Type value) current=first-link；while(current!=NULL)if(current-data=value) breakelse current=curr
12、ent-link;return current10. 顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。11. 顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻。因此，这种表便于 随机访问，是一种随机访问存储结构。12. 在一个不带头结点的单链表中，在表头插入或删除与其在其他位置插入或删除操作的过程。13. 已知L是无头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点，添加 合适的语句。1) P 结点之后插入结点 S： S-next=P-next; P-next=S;2) P 结点之前插入结点 S：pre=L;while(pre-next!=P) pre=pre
13、-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 结点的直接后继结点：Q=P-ne
14、xt; 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若频繁地对线性表进行插入和删除操作,该线性表采用顺序存储结构更合适。 ( W )3若线性表采用顺序存储结构,每个数据元素占用4 个存储单元,第12 个数据元素的存 储地
