2022年第三章单链表题目和答案.docx

《2022年第三章单链表题目和答案.docx》由会员分享，可在线阅读，更多相关《2022年第三章单链表题目和答案.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 第 2 章 自测卷答案一、填空1.次序表中规律上相邻的元素的物理位置相互相邻；单链表中规律上相邻的元素的物理位置不相邻；2.在单链表中,除了首元结点外,任一结点的储备位置由 其直接前驱结点值域 指示；3 在 n 个结点的单链表中要删除已知结点 *p ,需找到它的 地址；二、判定正误（在正确的说法后面打勾,反之打叉）1. 链表的每个结点中都恰好包含一个指针；X 2. 链表的物理储备结构具有同链表一样的次序；X 3. 链表的删除算法很简洁,由于当删除链中某个结点后,运算机会自动地将后续的各个单元向前移动；X 4. 线性表的每个结点只能是一个简洁类型

2、,而链表的每个结点可以是一个复杂类型；Y 5. 次序表结构相宜于进行次序存取,而链表相宜于进行随机存取；Y6. 次序储备方式的优点是储备密度大,且插入、删除运算效率高；X 7. 线性表在物理储备空间中也肯定是连续的；X 8. 线性表在次序储备时,规律上相邻的元素未必在储备的物理位置次序上相邻；X 9. 次序储备方式只能用于储备线性结构；X 10. 线性表的规律次序与储备次序总是一样的；X三、单项挑选题（ A ）1. 链接储备的储备结构所占储备空间：（ A）分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针（ B）只有一部分,存放结点值（C） 只有一部分,储备表示结点间关系的指针（D）

3、 分两部分,一部分存放结点值,另一部分存放结点所占单元数（B ）2. 链表是一种采纳 储备结构储备的线性表；（ A）次序（B）链式（C）星式（D）网状（ D）3. 线性表如采纳链式储备结构时,要求内存中可用储备单元的地址 : （A ）必需是连续的（ B）部分地址必需是连续的（C）肯定是不连续的（ D）连续或不连续都可以（B）4 线性表在 情形下适用于使用链式结构实现；（）需常常修改中的结点值（）需不断对进行删除插入（）中含有大量的结点（）中结点结构复杂（ C）5 单链表的储备密度名师归纳总结 （）大于1； （）等于1；（）小于1； （）不能确定第 1 页,共 5 页（ A ）6、在单链表的一个

4、结点中有个指针；- - - - - - -精选学习资料 - - - - - - - - - A 、1 B、2 C、3 D、4 （D ）7、设一个链表最常用的操作是在末尾插入结点和删除尾结点,就选用最节约时间；A、单链表B、单循环链表C、带尾指针的单循环链表D、带头结点的双循环链表（B ）8、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是；A、 p-next=s;s-next=p-next; C、 p-next=s;p-next=s-next; B、s-next=p-next;p-next=s; D、p-next=s-next;p-next=s; （C ）9、对于一个头指针为he

5、ad 的带头结点的单链表,判定该表为空表的条件是；A、 head=NULL B、headnext=NULL C、 headnext=head D、head.=NULL （head 指向谁的 （ c ） 10、在双向链表指针p 的结点前插入一个指针q 的结点操作是；A、 p-prior=q;q-next=p;p-prior-next=q;q-prior=q; B、 p-prior=q;p-prior-next=q;q-next=p;q-prior=p-prior; C、 q-next=p;q-prior=p-prior;p-Prior-next=q;p-prior=q; D、 q-prior=p

6、-prior;q-next=q;p-prior=q;p-prior=q; （A ）11、在一个单链表中,如删除P 所指结点的后续结点,就执行；A 、p-next=p-next-next; B、p=p-next;p-next=p-next-next; C、p-next=p-next; D、p=p-next-next; （ A ）12、不带头结点的单链表 head为空的判定条件是；A、head=NULL B、head-next=NULL C、head-next=head D、head.=NULL （ B ）13、链表不具有的特点是；A、插入、删除不需要移动元素 B、可随机拜访任一元素 C、不必事先

7、估量储备空间 D、所需空间与线性长度成正比）1. 链表的每个结点中都恰好包含一个指针；答：错误；链表中的结点可含多个指针域,分别存放多个指针；例如,双向链表中的结点可 以含有两个指针域,分别存放指向其直接前趋和直接后继结点的指针；（ ）2. 链表的物理储备结构具有同链表一样的次序；而链表的示意图有序；错,链表的储备结构特点是无序,（ ）3. 链表的删除算法很简洁,由于当删除链中某个结点后,运算机会自动地将后续的各个单元向前移动；错,链表的结点不会移动,只是指针内容转变；（ ）4. 线性表的每个结点只能是一个简洁类型,而链表的每个结点可以是一个复杂类型；错,混淆了规律结构与物理结构,链表也是线性

8、表！且即使是次序表,也能存放记录型数据；2名师归纳总结 - - - - - - -第 2 页,共 5 页精选学习资料 - - - - - - - - - （ ）5. 次序表结构相宜于进行次序存取,而链表相宜于进行随机存取；错,正好说反了；次序表才适合随机存取,链表恰恰适于“ 顺藤摸瓜”（ ）6. 次序储备方式的优点是储备密度大,且插入、删除运算效率高；错,前一半正确,但后一半说法错误,那是链式储备的优点；次序储备方式插入、删除运算 效率较低,在表长为 n 的次序表中,插入和删除一个数据元素,平均需移动表长一半个数的 数据元素；（ ）7. 线性表在物理储备空间中也肯定是连续的；错,线性表有两种储

9、备方式,次序储备和链式储备；后者不要求连续存放；（ ）8. 线性表在次序储备时,规律上相邻的元素未必在储备的物理位置次序上相邻；错误；线性表有两种储备方式,在次序储备时,规律上相邻的元素在储备的物理位置次序上 也相邻；（ ）9. 次序储备方式只能用于储备线性结构；错误；次序储备方式不仅能用于储备线性结构,仍可以用来存放非线性结构,例如完全二叉 树是属于非线性结构,但其正确储备方式是次序储备方式；（后一节介绍）（ ）10. 线性表的规律次序与储备次序总是一样的；错,理由同 7；链式储备就无需一样；三、填空题 1、在带头结点的单链表 L 中,如要删除第一个元素,就需要执行以下三条语句：_；Lnex

10、t Unext ； free （U）；2、在单链表 L 中,如要在指针 P所指结点之后插入由指针 S-next=P-next ；_；S所指的结点,就需执行以下语句：3、在带有头结点的单链表L 中,第一个元素结点的指针是_；4、双循环链表 L 中由指针 P 所指向的某结点为尾结点的条件是_；1. 【严题集 2.2 】在次序表中插入或删除一个元素,需要平均移动 表中一半元素,详细移动的元素个数与 表长和该元素在表中的位置 有关；2. 线性表中结点的集合是 有限 的,结点间的关系是 一对一 的；3. 向一个长度为 n 的向量的第 i 个元素 1 i n+1之前插入一个元素时,需向后移动n-i+1 个

11、元素；3名师归纳总结 - - - - - - -第 3 页,共 5 页精选学习资料 - - - - - - - - - 4. 向一个长度为 n 的向量中删除第 i 个元素 1 i n 时,需向前移动 n-i 个元素；5. 在次序表中拜访任意一结点的时间复杂度均为 O1 ,因此,次序表也称为随机存取的数据结构；6. 【严题集 2.2 】次序表中规律上相邻的元素的物理位置邻的元素的物理位置不肯定相邻；必定相邻；单链表中规律上相7. 【严题集 2.2 】在单链表中,除了首元结点外,任一结点的储备位置由 其直接前驱结点的链域的值 指示；8在 n 个结点的单链表中要删除已知结点 O（n）；data ne

12、xt 四、算法设计题*p,需找到它的前驱结点的地址,其时间复杂度为1、设有两个单链表 L 和 L1,各结点结构如下：试画出该链表的结构图,并编写算法,判定单链表 1,不同返回 0；五、简答题L1 是否与单链表 L 相同,相同返回1. 【严题集 2.3 】试比较次序储备结构和链式储备结构的优缺点；在什么情形下用次序表 比链表好？答： 次序储备时,相邻数据元素的存放地址也相邻（规律与物理统一）；要求内存中可用 储备单元的地址必需是连续的；优点：储备密度大（ 1？）,储备空间利用率高；缺点：插入或删除元素时不便利；链式储备时,相邻数据元素可随便存放,但所占储备空间分两部分,一部分存放结点值,另一部分

13、存放表示结点间关系的指针 1）,储备空间利用率低；优点：插入或删除元素时很便利,使用敏捷；缺点：储备密度小（次序表相宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作；如线性表的长度变化不大,且其主要操作是查找,就采纳次序表；如线性表的长度变化较大,且其主要操作是插入、删除操作,就采纳链表；2 . 【严题集 2.1 】描述以下三个概念的区分：头指针、头结点、首元结点（第一个元素结 点）；在单链表中设置头结点的作用是什么？4名师归纳总结 - - - - - - -第 4 页,共 5 页精选学习资料 - - - - - - - - - 答：首元结点是指链表中储备线性表中第一个数据元素a1

14、 的结点；为了操作便利,通常在链表的首元结点之前附设一个结点,称为头结点, 该结点的数据域中不储备线性表的数据元素,其作用是为了对链表进行操作时,可以对空表、 非空表的情形以及对首元结点进行统一处理；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；如链表中附设头结点,就不管线性表是否为空表,头指针均不为空；否就表示空表的链表的头指针为空；这三个概 念对单链表、双向链表和循环链表均适用；是否设置头结点,是不同的储备结构表示同一逻 辑结构的问题；头结点headdatalink首元结点头指针简而言之,头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内 放头指针？那仍得另配一个头指针！）首元素结点是指链表中储备线性表中第一个数据元素 a1的结点；5名师归纳总结 - - - - - - -第 5 页,共 5 页