下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 第二章 线性表

第二章 线性表.doc

第二章 线性表

Catherine丽娜
2019-03-11 0人阅读 举报 0 0 暂无简介

简介:本文档为《第二章 线性表doc》,可适用于高等教育领域

第二章线性表一选择题.下述哪一条是顺序存储结构的优点?(A)A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示.下面关于线性表的叙述中错误的是哪一个?(B)A.线性表采用顺序存储必须占用一片连续的存储单元。B.线性表采用顺序存储便于进行插入和删除操作。C.线性表采用链接存储不必占用一片连续的存储单元。D.线性表采用链接存储便于插入和删除操作。.线性表是具有n个(C)的有限序列(n>)。A.表元素B.字符C.数据元素D.数据项E.信息项.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算则利用(A)存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素则采用(D)存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表.设一个链表最常用的操作是在末尾插入结点和删除尾结点则选用()最节省时间。DA单链表B单循环链表C带尾指针的单循环链表D带头结点的双循环链表.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用(D)存储方式最节省运算时间。A.单链表B.双链表C.单循环链表D.带头结点的双循环链表静态链表中指针表示的是(C)A.内存地址B.数组下标C.下一元素地址D.左、右孩子地址链表不具有的特点是(B)A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比下面的叙述不正确的是(BC)A.线性表在链式存储时查找第i个元素的时间同i的值成正比B线性表在链式存储时查找第i个元素的时间同i的值无关C线性表在顺序存储时查找第i个元素的时间同i的值成正比D线性表在顺序存储时查找第i个元素的时间同i的值无关二、判断链表中的头结点仅起到标识的作用。(×)顺序存储结构的主要缺点是不利于插入或删除操作。(√).线性表采用链表存储时结点和结点内部的存储空间可以是不连续的。(√).顺序存储方式插入和删除时效率太低因此它不如链式存储方式好。(×)对任何数据结构链式存储结构一定优于顺序存储结构。(×).顺序存储方式只能用于存储线性结构。(×).集合与线性表的区别在于是否按关键字排序。(×)所谓静态链表就是一直不发生变化的链表。(×)线性表的特点是每个元素都有一个前驱和一个后继。(×)取线性表的第i个元素的时间同i的大小有关(×)三、填空.当线性表的元素总数基本稳定且很少进行插入和删除操作但要求以最快的速度存取线性表中的元素时应采用存储结构。.线性表L=(a,a,…,an)用数组表示假定删除表中任一元素的概率相同则删除一个元素平均需要移动元素的个数是。.设单链表的结点结构为(data,next)next为指针域已知指针px指向单链表中data为x的结点指针py指向data为y的新结点,若将结点y插入结点x之后则需要执行以下语句:.在一个长度为n的顺序表中第i个元素(<=i<=n)之前插入一个元素时需向后移动ni个元素。.在单链表中设置头结点的作用是 主要是便于插入和删除等操作统一在第一个元素之前插入元素和删除第一个结点不必另作判断另外不论链表里是否为空链头指针不变。.对于一个具有n个结点的单链表在已知的结点*p后插入一个新结点的时间复杂度为,在给定值为x的结点后插入一个新结点的时间复杂度为。.根据线性表的链式存储结构中每一个结点包含的指针个数将线性链表分成单链表和多种链表而又根据指针的连接方式链表又可分成动态链表和静态链表。.在双向循环链表中,向p所指的结点之后插入指针f所指的结点其操作是、、、。在双向链表结构中若要求在p指针所指的结点之前插入指针为s所指的结点则需执行下列语句:s^next:=ps^prior:=p^prior:=s:=s.链接存储的特点是利用来表示数据元素之间的逻辑关系。.设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p所指结点之前插入一s结点的C语言描述语句、、、 。四、应用题下面是一算法的核心部分试说明该算法的功能。pre:=L↑next{L是一单链表结点有数据域data和指针域next}IFpre<>NILTHENWHILEpre↑next<>NILDOBEGINp:=pre↑nextIFp↑data>=pre↑dataTHENpre:=pELSEreturn(false)ENDreturn(true)设单链表结点指针域为next试写出删除链表中指针p所指结点的直接后继的C语言语句。有线性表(a,a,…,an),采用单链表存储头指针为H每个结点中存放线性表中一个元素现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。()线性表中元素无序。()线性表中元素按递增有序。()线性表中元素按递减有序。.设papb分别指向两个带头结点的有序(从小到大)单链表。仔细阅读如下的程序并回答问题:()程序的功能。()ss中值的含义。()papb中值的含义。PROCEDUREexam(pa,pb)BEGINp:=pa↑nextp:=pb↑nextpa↑next:=∧s:=s:=WHILEp≠∧ANDp≠∧DOCASEp↑data<p↑data:p:=pp:=p↑nexts:=sdispose(p)p↑data>p↑data:p:=p↑nextp↑data=p↑data:p:=pp:=p↑nextp↑next:=pa↑nextpa↑next:=pp:=p↑nexts:=sENDWHILEp≠∧DOp:=pp:=p↑nextdispose(p)s:=sEND已解决在双向循环链表中,在p所指的结点之后插入s指针所指的结点,其操作是悬赏分:解决时间::在双向循环链表中,在p所指的结点之后插入s指针所指的结点,其操作是(A)p>next=s       s>prior=p(p>next)>prior=s s>next=p>next(B)s>prior=p      s>next=p>nextp>next=s       p>next>prior=s(C)p>next=s       p>next>prior=ss>prior=p       s>next=p>next(D)s>prior=p       s>next=p>nextp>next>prior=s   p>next=s选哪个请说明原因。为什么要那样?提问者:xingdabo三级最佳答案A就是正确的,让P的后指针指向S,让S的前指针等于P,也就是指向P所指的结点然后让P的后指针所指的结点(也就是P后边的那个结点)的前指针指向S,让S的后指针等于P的后指针,这样就把S所指向的结点插到P所指向的结点后边了,画个图就好理解了,把P和P后边的结点,还有S都画出来,按照语句挪一下指针就明白了

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/8

第二章 线性表

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利