考研核心题型数据结构部分第章线性表

《考研核心题型数据结构部分第章线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2016年考研核心考点命题思路解密数据结构梦享团队主编第2章线性表2.1线性表的定义和基本操作温馨提示：线性表的定义和基本操作部分，从历年统考和高校自主命题的真题来看，主要考察了两个问题：1、什么是线性表？2、线性表存储方式？3、线性表怎么样插入、删除。请同学们围绕这三个问题，展开复习，其中第3个问题是本考点的重点。1.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则执行（）。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->

2、next=s;s->next=q;【2013年——昆明理工大学】【考查内容】在单链表中插入结点的正确操作。【解析】单链表中插入和删除结点操作是常见的操作，希望大家要多练习，掌握这些基本的操作。说透了，其实不同的题目中，这些操作都大同小异的，学会灵活应用，才是硬道理。已知*q结点是*p结点的前驱结点，在*q结点和*p结点之间插入*s结点，如图2.1所示。sq×p图2.1注意插入结点的过程中，要防止“掉链”的情况（即指针调整的过程中，后续指针出现错误）。为了防止“掉链”，需要把q的指针先赋给s的指针，然后再调整q的指针指向结点*s。即“s->next=q->next;q->nex

3、t=s”。当然，若3个结点的指针都很明确，像本题三个结点的指针p、q、s均已知的情况下，可以直接调整指针“q->next=s;s->next=p”。A答案应该改成：“s->next=q->next;q->next=s”，B答案显然不正确，D答案可改成:“q->next=s;s->next=p”。【参考答案】C我方慎重声明，各盈利机构若采用我方资料，必追究法律责任132016年考研核心考点命题思路解密数据结构梦享团队主编2.在长度为n的顺序表中删除第i个元素（1≤i≤n）时，元素移动的次数为（）。A.n-iB.n-i+1C.iD.i+1【2008年——太原科技大学】【考查内容】

4、顺序表中删除元素需要移动元素的次数。【解析】在长度为n的顺序表中删除第i个元素（1≤i≤n）时，将第i+1个位置的元素移动到第i个位置，将第i+2个位置的元素移动到第i+1个位置,…,将第n-1个位置的元素移动到第n-2个位置，将第n个位置的元素移动到第n-1个位置。图2.2给出元素的移动示意图。12...i-1ii+1i+2...n-2n-1n图2.2显然，除了从第i+1个元素到第n个元素总共n-i个元素都需要移动。为什么不是n-(i+1)呢？比如，从第3到第5个元素都需要移动，也就是说i=2,n=5,那么需要移动的元素个数是n-i=5-2=3个，而不是n-(i+1)=5-

5、3=2个。这些细节的问题，请同学们要注意了，不要弄错了。【参考答案】A3.链表不具有的特点是（）。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性表长度成正比【2011年——南京邮电大学】【考查内容】链表的特点。【解析】链表中，插入和删除结点直接修改指针就可以了，不需要移动元素。所以，A答案正确。链表不像顺序表，地址不能通过直接计算得到。链表的表结点一般由数据域和指针域组成，只有当前结点才知道下一个结点的指针，其他的结点并不知道。所以，不能随机访问任一元素。这里我们来举一个简单的例子，我们把数据域记成姓名，指针域记成家庭住址。假设张

6、三知道李四的家庭地址，李四知道王五的家庭地址，王五知道赵六的家庭地址…除此之外，每个人都不再知道其他人的家庭地址。那么，想知道赵六的地址，他得先去张三家找到张三，从张三那儿知道李四家的地址；然后再去李四家找到李四，问李四王五家的地址；然后再去王五家找到王五，去问赵六家的地址。最终，找到赵六。所以，B答案错误。我方慎重声明，各盈利机构若采用我方资料，必追究法律责任142016年考研核心考点命题思路解密数据结构梦享团队主编链表的结点空间是动态申请的，不必像数组一样，一次申请完所有的存储空间。链表所需的存储空间仍然与线性表的长度成正比。比如，对于结点只有数据域和指针域的单链表，链表

7、的存储空间大小P=n×(数据域所占存储空间+指针域所占存储空间)显然，D答案正确。【参考答案】B4.顺序表不具有的特点是（）。A.不能随机访问任一元素B.插入、删除元素不需要移动元素C.需要事先估计存储空间D.所需空间与线性长度成正比【2012年——青岛大学】【考查内容】顺序表的特点。【解析】顺序表是线性表的顺序存储表示，能随机访问任何一个元素，但是必须事先分配一片连续的存储空间，所以需要先估计存储空间的大小。这片存储空间的大小，与顺序表的长度成正比。所以，A、C、D答案都是正确的。顺序表在某一个位置插