习题3链表

习题 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—〉next； (11）在一个单链表中，若要删除p 个结点的后继结点，则执行（ A ) A)p-〉next=p—〉next—〉next； B)p=p—next； p-〉next-〉next； C）free（p—〉next）; D）p＝p—next-next; （12）设 rear 是指向非空带头结点的循环单链表的尾指针，则删除表首结点的操作可表示为( B） A)p＝rear； B)p= rear-〉next—next； Rear=rear—〉next； rear—〉next-〉next＝p—next; free（p)； free（p） ； C）rear：=rear-next—〉next； D）rear＝rear—〉next free(rear); free（rear); （13）循环链表主要优点是（ D ) A）不再需要头指针了 B）已知某个结点的位置后,能够容易找到它的直接前趋 C）在进行插入,删除运算时，能更好地保证链表断开 D）从表中任一结点出发都能扫描到整个链表 (14）用链表表示线性表的优点是（ C ) A）便于随机存取 B）花费的存储空间较顺序存储少 C）便于插入和删除操作 D）数据元素的物理顺序和逻辑顺序相同 （15)最常用操作是在最后一个元素之后插入一个元素和删除最后一个元素,则用( B )存储方式最佳. A)单链表 B）双链表 C）单循环链表 D）带头结点的双循环链表 (16)指针 p1 和 p2 分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单 循环链表，应执行的操作为（ D） A） p1-〉 next=p2-next； p2—〉 next=p1-〉 next; B） p2-〉 next=p1-next;p1-〉 next=p2—next； C）p=p2—next; p1-〉next=p;p2—〉next=p1-〉next; D）p=p1-〉next； p1—〉next= p2-next；p2-next=p； 二、填空题二、填空题 （1）在单向链表某 P 结点之后插入 S 结点的操作是（ s—〉next=p—〉next；p-next=s；） 。 （2） 对于一个具有n个结点的单链表,在已知的结点＊p后插入一个新结点的时间复杂度为 （ O （1）） , 在给定值为 x 的结点后插入一个新结点的时间复杂度为（ O（n)） 。 （3)设长度为 n 的链队列用只设尾指针的单循环链表表示，则出队操作的时间复杂度为 ( O（1)） ， 若用只设头指针的单循环链表表示，则出队操作的时间复杂度为（ O（1)） 。 （4)在双向链表中， 每个结点有两个指针域， 一个指向 （直接后继） ,另一个指向 （直接前驱） 。 （5）在一个单链表中的p 所指结点之后插入一个 s 所指结点时,执行的操作为（ s—next=p-〉next;p-〉next=s； )。 （6)在一个单链表中的p 所指结点之前插入一个s 所指结点时 ,执行的操作为（ s—〉next=p； p=s; )。 (7）在一个单链表中删除p 所指结点时，应执行的操作是（q=p;p=p-next;free（q）） 。 （8）对于双向链表,在两个结点之间插入一个新结点需修改的指针共( 4）个。 (9）带有一个头结点的单链表Head 为空的条件是（ Head—next=Null )。 (10）非空循环单链表 head 的尾结点(由 p 所指向)，满足条件( p-〉next=head )。 （11）对于一个具有n 个结点的单链表,在已知 p 所指结点后插入一个新结点的时间复杂度为（ O(1) )； 在给定值为 x 的结点后插入一个新结点的时间复杂度为(