习题 3（链表） 一、选择题 （1）链接存储的存储结构所占存储空间（ A ）。 A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B）只有一部分，存放结点值 C）只有一部分，存储表示结点间关系的指针 D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 （2）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A）必须是连续的 B）部分地址必须是连续的 C）一定是不连续的 D）连续或不连续都可以 （3）线性表Ｌ在（ B ）情况下适用于使用链式结构实现。 A）需经常修改结点值 B）需不断删除插入 C）含有大量的结点 D）结点结构复杂 （4）单链表的存储密度（ C ）。 A）大于 1 B）等于 1 C）小于 1 D）不能确定 （5）若指定有 n 个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ C ）。 A）O(1) B）O(n) C）O(n2) D）O(nlog2n) （6）在单链表中，要将 s 所指结点插入到 p 所指结点之后，其语句应为（ D ）。 A）s->next=p+1; p->next=s; B）(*p).next=s; (*s).next=(*p).next; C）s->next=p->next; p->next=s->next; D）s->next=p->next; p->next=s; （7）在双向链表存储结构中，删除 p 所指的结点时须修改指针（ A ）。 A）p->next->prior=p->prior; p->prior->next=p->next; B）p->next=p->next->next; p->next->prior=p; C）p->prior->next=p; p->prior=p->prior->prior; D）p->prior=p->next->next; p->next=p->prior->prior; （8）在双向循环链表中，在 p 指针所指的结点后插入 q 所指向的新结点，其修改指针的操作是（ C ）。 A）p->next=q; q->prior=p; p->next->prior=q; q->next=q; B）p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C）q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D）q->prior=p; q->next=p->next; p->next=q; p->next->prior=q; （9）链表可以带表头结点，也可以不带表头结点，前者最主要的好处是（ B ）。 A）加快表的遍历 B）使空表和非空表的处理统一 C）节省存储空间 D）提高存取元素的速度 （10）在单链表指针 p 所指向的结点后面插入一个新结点 q 的操作语句序列为（ A ）。 A）q->next=p->next; p->next=q; B）p=p->next; p->next=q->next; C）q=p->next; q->next=p->next; D）p->next=q; q->next=p->ne...
