数据结构第二章习题

1、第2章 线性表一、单项选择题1线性表是具有n个_的有限序列。a表元素 b字符c数据元素 d数据项2线性表是_。a一个有限序列，可以为空 b一个有限序列，不可以为空c一个无限序列，可以为空 d一个无限序列，不可以为空3线性表采用链表存储时，其地址_。a必须是连续的 b一定是不连续的c部分地址必须是连续的 d连续与否均可以4链表不具备的特点是_。a可随机访问任一结点 b插入删除不需要移动元素c不必事先估计存储空间 d所需空间与其长度成正比5设线性表有n个元素，以下操作中，_在顺序表上实现比在链表上实现效率更高。a输出第i(1in)个元素值b交换第1个元素与第2个元素的值c顺序输出这n个元素的值d输

2、出与给定值x相等的元素在线性表中的序号6设线性表中有2n个元素，以下操作中，_在单链表上实现要比在顺序表上实现效率更高。a删除指定的元素b在最后一个元素的后面插入一个新元素c顺序输出前k个元素d交换第i个元素和第2n-i-1个元素的值(i=0,1,n-1)7如果最常用的操作是取第i个结点及其前驱，则采用_存储方式最节省时间。a单链表 b双链表c单循环链表 d顺序表8与单链表相比，双链表的优点之一是_。a插入和删除操作更简单 b可以进行随机访问c可以省略表头指针或表尾指针 d访问前后相邻结点更灵活9带头结点的单链表l为空的判定条件是_。al= =null bl-next= =nullcl-nex

3、t= =l dl!=null10在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_。ao(1) bo(n)co(n2) do(nlog2n)11在一个长度为n(n1)的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行_操作与链表的长度有关。a删除单链表中的第一个元素b删除单链表中的最后一个元素c在单逻表第一个元素前插入一个新元素d在单链表最后一个元素后插入一个新元素12对于一个具有n个元素的线性表，建立其单链表的时间复杂度_。ao(log2n) bo(1)co(n2) do(n)二、填空题1在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链

4、式存储中，元素之间的逻辑关系是通过_决定的。2向一个长度为n的顺序表中的第i个元素(1in)之前插入一个元素时，需向后移动_个元素。3在一个长度为n的顺序表中删除第i个元素(1in)时，需向前移动_个元素。4为了设置一个空的顺序表l，应采用的操作是_。5删除顺序表的_元素，不需要移动任何元素。6删除顺序表的_元素，需要移动的元素最多。7在顺序表_元素后面插入一个元素，不需要移动任何元素。8在顺序表的第_元素前插入元素1个元素，需要移动的元素最多。9 在长度为n的顺序表l中查找与指定元素值相同的元素，其时间复杂度为_。10在单链表中设置头结点的作用是_。11在单链表中，要删除某一指定的结点，必须

5、找到该结点的_结点。12访问单链表中的结点，必须沿着_依次进行。13求单链表长度的时间复杂度为_。14删除单链表l中某结点*p之后的一个结点，其时间复杂度为_。15删除单链表l中某结点*p之前的一个结点，其时间复杂度为_。16在一个单链表l中，指针p指向l的某个结点，在p之前插入一个指针s所指结点时的操作为：(1) s-next=_； (2) p-next=s；(3) t=p-data；(4) p-data=_；(5) s-data=_；17在一个单链表（已知每个结点含有数据域data和指针域next）中删除p所指结点时的操作为：(1) q=p-next；(2) p-data=q-data；(

6、3) p-next=_；(4) free(q)；18在一个单链表l中，p指向l中的某个结点，在指针p指向的结点之后插入指针s指向的结点时，应执行s-next=_和p-next=_的操作。19对于一个具有n个结点的单链表，在指针p指向结点之后插入一个新结点的时间复杂度是_；在给定值为x的结点后插入一个新结点的时间复杂度是_。三、判断题1线性表中每个元素都有一个直接前驱和一个直接后继。2线性表中所有元素的排列顺序必须由小到大或由大到小。3线性表的顺序存储结构优于链式存储结构。4在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。5在单链表中，可以从头结点开始查找任何一个结点

7、。6在双链表中，可以从任一结点开始沿同一方向查找到任何其他结点。四、简答题1简述顺序表和链表存储方式的特点。2在什么情况下使用顺序表比链表好。3若频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构，为什么？4对链表要设置头结点的作用是什么？（至少说出两条好处）5在单链表双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去（不允许进行结点之间数据域的复制）？若可以，其时间复杂度各为多少？五、算法设计题1设计一个求元素逆置的算法。(1) 将顺序表的所有元素逆置，要求算法空间复杂度为o(1)。(2) 将带头结点的单链表的所以元素逆置，要求空间复

8、杂度为o(1)。2设计一些有关删除元素的算法。(1) 从顺序表中删除所有元素值为x的元素，要求空间复杂为o(1)。(2) 从顺序表中删除元素值在x到y（xy）之间的所有元素，要求空间复杂度为o(1)。(3) 从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。(4) 从单链表l中删除值为x的结点的直接前驱结点。(5) 从带头结点的单链表l中删除一个最小值的结点。(6) 从一个递增单链表中，删除值域重复的结点。并分析算法的时间复杂度。(7) 从一个非有序单链表（允许出现值域重复的结点）中，删除值域重复的结点。(8) 从一个带头结点递增有序表的单链表l中，删除表中data值在大于或等于mi

9、n且小于或等于max之间的结点（若表中有这样的结点），同时释放被删结点的空间，这里min和max是两个给定的参数。(9) 从一个带头结点非有序表的单链表l中，删除表中data值在大于或等于min且小于或等于max之间的结点（若表中有这样的结点），同时释放被删结点的空间，这里min和max是两个给定的参数。并分析算法的时间复杂度。3设计与集合运算有关的算法。(1) 用顺序表表示集合，实现集合的交集、并集和差集的运算。(2) 用单链表表示集合，实现集合的交集、并集和差集的运算。4综合问题的算法(1) 设有一个顺序表，其元素为整型数据，设计一个算法将中所有小于的整数放在前半部分，大于的整数放在后半部分。 (2) 设c=a1,b1,a2,b2,an, bn 为