武汉软件工程职业学院软件技术专业大二2019数据结构第十一单元

1、武汉软件工程职业学院软件技术专业大二2019数据结构第十一单元您的姓名： 填空题 *_1. (专基)下列选项中关于链表是线性表的哪种存储结构正确的是（）。 单选题 *链式结构(正确答案)顺序结构散列结构索引结构2. 数据结构中单链表是含有（ ）个指针域的链表 单选题 *两三零一(正确答案)3. 在单链表p结点之后插入s结点，正确的操作是（ ） 单选题 *p->next=s; s->next=p->next;s->next= p->next; p->next=s;(正确答案)p->next=s; p->next= s->next;p->

2、next=s; p->next= s->next;4. (专基)单链表中修改第i个元素的时间复杂度是（）。 单选题 *O（1）O（n）(正确答案)O（n*n）都不对5. 单链表中删除p指针指向结点的后继则时间复杂度是（假设存在）（） 单选题 *O（n）O（1）(正确答案)O（n*n）都不对6. (专基)线性表L在（）情况下适用于使用链式结构实现。 单选题 *需不断对L进行删除插入(正确答案)需经常修改L中的结点值L中结点结构复杂L中含有大量的结点7. 带头结点的单链表H为空的条件应该是下面描述正确的是( ) 单选题 *next=NULLH=NULLH->next=NULL(正

3、确答案)以上都不对8. （专基)顺序表和链表分别指（）。 单选题 *线性表的顺序存储结构和链式存储结构(正确答案)线性表的顺序存储结构和随机存储结构线性表的顺序存储结构和索引存储结构线性表的顺序存储结构和散列存储结构9. 在一个具有n个结点的单链表中修改一个结点数据域的值，时间复杂度是（） 单选题 *O(1)O(n)(正确答案)O(n*n)O(nlog2n)10. 在双向链表的一个结点中有（ ）个指针 单选题 *2(正确答案)10311. (专基)单链表中删除p指针指向结点的后继（假设存在）的语句序列是 单选题 *p->next=p->next;p->next=p->n

4、ext->next;(正确答案)p->next=p;p=p->next;12. 单链表的结点包含两部分：( )域和指针域 单选题 *指针域链域数据域(正确答案)散列域13. 带头结点的单链表head为空的判断条件是（ ） 单选题 *head=NULLhead->next =NULL(正确答案)head->next =headhead!=NULL14. 顺序表与链表的区别在于（） 单选题 *存储方式不同(正确答案)元素个数不同逻辑关系不一样都不对15. 顺序表与链表的相同点在于（） 单选题 *存储方式相同元素个数不同逻辑关系相同(正确答案)都不对16. 不带头结点的

5、单链表head为空的判断条件是（ ） 单选题 *head=NULL(正确答案)head->next =NULLhead->next =headhead!=NULL17. 单链表插入的时间复杂度（） 单选题 *O（1）(正确答案)O（log2n）O（n）O（n2）18. 删除p结点的后继结点并回收空间，错误的语句序列是（ ） *p->next= p->next->next;(正确答案)p->next= p->next->next free(p);(正确答案)q=p->next p->next= p->next->next;

6、free(q);q=p->next->next; p->next->next= p->next->next; free(q);(正确答案)19. 对于只在表的首、尾两端进行插入操作的线性表，不宜采用的存储结构为（ ） *顺序表(正确答案)有头指针的单向链表(正确答案)有头指针和尾指针的双向链表有头指针的单向循环链表(正确答案)20. 在单链表的开始结点之前附加一个结点，不是（ ） *头指针(正确答案)头结点尾指针(正确答案)尾结点(正确答案)21. 在具有n个结点的单链表中，实现（ ）的操作，其时间复杂度为O(n) *遍历链表(正确答案)找链表的第i个结点(

7、正确答案)在p指针的结点之后插入一个结点删除p指向结点的后继结点22. L是线性表，已知表长度length的值是5，经过一次插入运算后，length的值不是（ ） *4(正确答案)7(正确答案)5(正确答案)623. 有关链式存储的存储结构所占存储空间说法错误的是（） *分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针只有一部分，存放结点的值(正确答案)只有一部分，存储表示结点间关系的指针(正确答案)分两部分，一部分存放结点的值，另一部分存放结点所占单元素(正确答案)24. 每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式不是（ ）存储方式 *顺序(正确答案)链式索

8、引(正确答案)散列(正确答案)25. 在单链表中，增加头结点的目的不是（ ） *使单链表至少有一结点(正确答案)标志表中首结点位置(正确答案)方便运算的实现说明单链表是线性表的链式存储实现(正确答案)26. 两个指针P和Q，分别指向单链表的两个元素，P是Q前驱的条件错误的是（ ） *P->next=Q->next(正确答案)Q->next= P(正确答案)P->next= QP= Q(正确答案)27. 在一个单链表中，q是p的前驱，若在q、p之间插入s结点，则不能执行（）操作 *s->next=p->next; p->next=s;(正确答案)q-&g

9、t;next=s; s->next=p;p->next= s->next; s->next=p;(正确答案)p->next=s; s->next=q;(正确答案)28. 单链表中，p是待删除的结点的前驱结点，则需要执行的操作为：p->next=p->next->next。（ ） 判断题 *对(正确答案)错29. 在链表中插入元素很方便，不需要移动大量的元素。( ) 判断题 *对(正确答案)错30. 在单链表中，每个结点都有一个指针域，用来指向其后继结点。（ ） 判断题 *对(正确答案)错31. 在单链表中删除元素方便，可以避免移动大量的元素

10、。( ) 判断题 *对(正确答案)错32. 单链表是一种一对多的逻辑结构。( ) 判断题 *对错(正确答案)33. 链式存储的特点是：在逻辑上相邻的元素在物理上必须不相邻（ ） 判断题 *对错(正确答案)34. 单链表中修改结点数据比较方便，因为时间复杂度是O（1）。( ) 判断题 *对错(正确答案)35. 在顺序表和单链表中实现读表元素运算的平均时间复杂度均为O(1)。( ) 判断题 *对错(正确答案)36. 在单链表中插入元素不方便，需要移动大量的元素。( ) 判断题 *对错(正确答案)37. 单链表是一种多对多的逻辑结构。( ) 判断题 *对错(正确答案)38. 下列选项中代表链表定位查

11、找第i个元素的时间复杂度是（ ）。 单选题 *O(1)O(n)(正确答案)O(n*n)O(0)39. 单链表的结点包含两部分：（ ）域和指针域 单选题 *指针域链域数据域(正确答案)散列域40. 带头结点的单链表head为空的判断条件是 单选题 *head=NULLhead->next=NULL(正确答案)head->next=headhead!=NULL41. 单链表插入的时间复杂度 单选题 *O(1)(正确答案)O(log2n)O(n)O(n2)42. 顺序表与链表的区别在于 单选题 *存储方式不同(正确答案)元素个数不同逻辑关系不一样都不对43. 顺序表与链表的相同点在于 单

12、选题 *存储方式相同元素个数不同逻辑关系相同(正确答案)都不对44. 不带头结点的单链表head为空的判断条件是（ ） 单选题 *head=NULL(正确答案)head->next=NULLhead->next=headhead!=NULL45. 在一个单链表中，q是p的前驱，若在q、p之间插入s结点，则不能执行（）操作 *s->next=p->next; p->next=s;(正确答案)q->next=s; s->next=p;p->next=s->next; s->next=p;(正确答案)p->next=s; s->

13、next=q;(正确答案)46. 对于只在表的首、尾两端进行插入操作的线性表，不宜采用的存储结构为（ ） *顺序表(正确答案)有头指针的单向链表(正确答案)有头指针和尾指针的双向链表有头指针的单向循环链表(正确答案)47. 有关链式存储的存储结构所占存储空间说法错误的是（ ） *分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针只有一部分，存放结点的值(正确答案)只有一部分，存储表示结点间关系的指针(正确答案)分两部分，一部分存放结点的值，另一部分存放结点所占单元数(正确答案)48. 每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式不是（ ）存储方式 *顺序(正确答案)链式索引(正确答案)散列(正确答案)49. 两个指针P和Q，分别指向单链表的两个元素，P是Q前驱的条件错误的是（ ） *P->next=Q->next;(正确答案)Q->next= P;(正确答案)P->next= Q;P= Q;(正确答案)50. 在单链表中，增加头结点的目的不是（ ） *使单链表至少有一结点(正确答案)标志表中首结点位置(正确答案)方便运算的实现说明单链表是线性表的链式存储实现(正确答案)51. 在单链表中删除元素方便，可以避免移动大量的元素。（） 判断题 *对(正确答案)错52. 单链表是一种一对多的逻辑结构。（） 判断题 *对错(正确答