技术标签: 算法 c null n2 存储 【大学课程之数据结构】 数据结构
第2章 线性表
一 选择题
1.下述哪一条是顺序存储结构的优点?( A )
A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示
2.下面关于线性表的叙述中,错误的是哪一个?( B )
A.线性表采用顺序存储,必须占用一片连续的存储单元。
B.线性表采用顺序存储,便于进行插入和删除操作。
C.线性表采用链接存储,不必占用一片连续的存储单元。
D.线性表采用链接存储,便于插入和删除操作。
3.线性表是具有n个( C )的有限序列(n>0)。
A.表元素 B.字符 C.数据元素 D.数据项 E.信息项
4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( A )存储方式最节省时间。
A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表
5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( D )存储方式最节省运算时间。
A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表
6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( D )最节省时间。
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用( D )存储方式最节省运算时间。
A.单链表 B.双链表 C.单循环链表 D.带头结点的双循环链表
8. 静态链表中指针表示的是( BC ).
A. 内存地址 B.数组下标 C.下一元素地址 D.左、右孩子地址
9. 链表不具有的特点是( C )
A.插入、删除不需要移动元素 B.可随机访问任一元素
C.不必事先估计存储空间 D.所需空间与线性长度成正比
10. 下面的叙述不正确的是( BC )
A.线性表在链式存储时,查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时,查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时,查找第i个元素的时间同i 的值成正比
D. 线性表在顺序存储时,查找第i个元素的时间同i的值无关
11. 线性表的表元存储方式有(顺序)和链接两种。试指出下列各表中使用的是何种存储方式:表1是(顺序)存储方式;表2是(循环链接)存储方式;表3是(单向链接)存储方式;表4是(双向链接)存储方式。表左的s指向起始表元。
表元编号 | 货号 | 数量 | 表元间联系 |
1 | 618· | 40 | 2 |
2 | 205 | 2 | 3 |
3 | 103 | 15 | 4 |
4 | 501 | 20 | 5 |
5 | 781 | 17 | 6 |
6 | 901 | 24 | 0 |
表1
s→
表元编号 | 货号 | 数量 | 表元间联系 |
1 | 618· | 40 | 5 |
2 | 205 | 2 | 1 |
3 | 103 | 15 | 4 |
4 | 501 | 20 | 2 |
5 | 781 | 17 | 6 |
6 | 901 | 24 | 3 |
表2
s→
表元编号 | 货号 | 数量 | 表元间联系 |
1 | 618· | 40 | 5 |
2 | 205 | 2 | 1 |
3 | 103 | 15 | 6 |
4 | 501 | 20 | 0 |
5 | 781 | 17 | 4 |
6 | 901 | 24 | 3 |
表3
s—>
表元编号 | 货号 | 数量 | 1 2 |
1 | 618· | 40 | 5 2 |
2 | 205 | 2 | 1 0 |
3 | 103 | 15 | 4 6 |
4 | 501 | 20 | 0 3 |
5 | 781 | 17 | 6 1 |
6 | 901 | 24 | 3 5 |
表4
s→
供选择的答案:
A.连续 B.单向链接 C.双向链接 D.不连接 E.循环链接
F.树状 G.网状 H.随机 I.顺序 J.顺序循环
12.(1) 静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第i个元素的时间与i无关。
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。
以上错误的是( B )
A.(1),(2) B.(1) C.(1),(2),(3) D.(2)
13. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为( C )(1<=i<=n+1)。
A. O(0) B. O(1) C. O(n) D. O(n2)
14. 对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为( C )。
A.O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
15.线性表( a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为( C )
A.O(i) B.O(1) C.O(n) D.O(i-1)
16.非空的循环单链表head的尾结点p满足( A )。
A.p.link=head B.p.link=NIL C.p=NIL D.p= head
17.循环链表H的尾结点P的特点是( A )。
A.P.NEXT=H B.P.NEXT= H.NEXT C.P=H D.P=H.NEXT
18.在一个以 h 为头的单循环链中,p 指针指向链尾的条件是(A)
A. p.next=h B. p.next=NIL C. p^.next.^next=h D. p^.data=-1
二、判断
1. 链表中的头结点仅起到标识的作用。( × )
2. 顺序存储结构的主要缺点是不利于插入或删除操作。(√ )
3.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。( √ )
4.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。( × )
5. 对任何数据结构链式存储结构一定优于顺序存储结构。(× )
6.顺序存储方式只能用于存储线性结构。( × )
7.集合与线性表的区别在于是否按关键字排序。( × )
8. 所谓静态链表就是一直不发生变化的链表。( × )
9. 线性表的特点是每个元素都有一个前驱和一个后继。( × )
10. 取线性表的第i个元素的时间同i的大小有关. ( × )
11. 循环链表不是线性表. ( × )
12. 线性表只能用顺序存储结构实现。( × )
13. 线性表就是顺序存储的表。( × )
14.为了很方便的插入和删除数据,可以使用双向链表存放数据。( √ )
15. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。( × )
16. 链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存储结构中效率高。 ( √ )
三、填空
1.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用____顺序___存储结构。
2.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是____n-1/2____。
3.设单链表的结点结构为(data,next),next为指针域,已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点 , 若将结点y插入结点x之后,则需要执行以下语句:___py->next=px->next___; ____px->next=py__;
4.在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时,需向后移动____n-i+1____个元素。
5.在单链表中设置头结点的作用是___主要是使插入和删除等操作统一,在第一个元素之前插入元素和删除第一个结点不必另作判断。另外,不论链表是否为空,链表指针不变。_____。
6.对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为___o(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为___O(n)_____。
7.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成___单链表_____和___多重链表____;而又根据指针的连接方式,链表又可分成____动态链表____和___静态链表_____。
8. 在双向循环链表中,向p所指的结点之后插入指针f所指的结点,其操作是____f->next=p->next;___、___f->next=p;____、___p->next->prior=f;____、____p->next=f;____。
10.链接存储的特点是利用____指针____来表示数据元素之间的逻辑关系。
11.顺序存储结构是通过____物理上相邻____表示元素之间的关系的;链式存储结构是通过_____指针___表示元素之间的关系的。
12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ___4___个,单链表为____2___个。
13. 循环单链表的最大优点是:____从任一结点出发都可访问到链表中每一个元素____。
14. 已知指针p指向单链表L中的某结点,则删除其后继结点的语句是:___q=p->next; p->next=q->next;delete q;_____
15. 带头结点的双循环链表L中只有一个元素结点的条件是:___ L->next->next==L 或者L->next->prior==L 或者L->prior->next==L或者L->prior->prior==L_____
16. 在单链表L中,指针p所指结点有后继结点的条件是:__ p->next!=null
17.带头结点的双循环链表L为空表的条件是:____ L->next==L &&L->prior==L ____。
18. 在单链表p结点之后插入s结点的操作是:__ s->next=p->next;p->next=s _____。
四 应用题
1.线性表有两种存储结构:一是顺序表,二是链表。试问:
(1)如果有 n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会自动地改变。在此情况下,应选用哪种存储结构? 为什么?
答:选链式存储结构,它可动态申请内存空间,不受长度(即表中元素个数)的影响,插入、删除复杂度为O(1)
(2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构?为什么?
答:选取顺序结构,顺序表可以随机存取,时间复杂度为O(1)。
2.线性表的顺序存储结构具有三个弱点:其一,在作插入或删除操作时,需移动大量元素;其二,由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;其三,表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点,试讨论之。
答:链式存储结构一般说克服了顺序存储结构的三个弱点。首先,插入、删除不需移动元素,只修改指针,时间复杂度为O(1);其次,不需要预先分配空间,可根据需要动态申请空间;其三,表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销,当空间不允许时,就不能克服顺序存储的缺点。
3.若较频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构?为什么?
答:采用链式存储结构,它根据实际需要申请内存空间,而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。
4.线性结构包括___线性表___、___栈___、___队列____和___串____。线性表的存储结构分成___顺序存储结构___和____链式存储结构__。
5.线性表(a1,a2,…,an)用顺序映射表示时,ai和ai+1(1<=i<n〉的物理位置相邻吗?链接表示时呢?
答:顺序映射时,ai与ai+1的物理位置相邻;链表表示时ai与ai+1的物理位置不要求相邻。
6. 说明在线性表的链式存储结构中,头指针与头结点之间的根本区别;头结点与首元结点的关系。
答:在线性表的链式存储结构中,头指针指链表的指针,若链表有头结点则是链表的头结点的指针,头指针具有标识作用,故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的,放在第一元素结点之前,其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等),有头结点后,对在第一元素结点前插入结点和删除第一结点,其操作与对其它结点的操作统一了。而且无论链表是否为空,头指针均不为空。首元结点也就是第一元素结点,它是头结点后边的第一个结点。
7. 在单链表和双向链表中,能否从当前结点出发访问到任何一个结点?
答:在单链表中不能从当前结点(若当前结点不是第一结点)出发访问到任何一个结点,链表只能从头指针开始,访问到链表中每个结点。在双链表中求前驱和后继都容易,从当前结点向前到第一结点,向后到最后结点,可以访问到任何一个结点。
8. 如何通过改链的方法,把一个单向链表变成一个与原来链接方向相反的单向链表?
答:链表逆置问题。设该链表带头结点,将头结点摘下,并将其指针域置空。然后从第一元素结点开始,直到最后一个结点为止,依次前插入头结点的后面,则实现了链表的逆置。
文章浏览阅读76次。第一种方案DAO层的函数方法1Public User selectUser(String name,String area);对应的Mapper.xml123<select id="selectUser" resultMap="Bas..._ 查询传多个值
文章浏览阅读1.7k次。主要用用获取手机屏幕尺寸_如何实时获取手机屏幕内容
文章浏览阅读1.7w次,点赞9次,收藏21次。获取打印输出流打印输出流:response.getWriter() 返回的是 PrintWriter可以通过 response.getWriter().write()和response.getWriter().print()响应数据给客户端,如果前端没有接收数据的位置,就会在浏览器上生成一个新的页面来显示内容。区别:write():仅支持输出字符类型数据,字符、字符数组、字符串等print():可以将各种类型(包括Object)的数据通过默认编码转换成bytes字节形式,这些字节都通过writ_servlet response返回数据
文章浏览阅读98次。JAVA毕业设计Web企业差旅在线管理系统计算机源码+lw文档+系统+调试部署+数据库。springcloud基于微服务架构的小区生活服务平台的设计与实现。jsp会议管理系统的设计与实现sqlserver。ssm+sqlserver精准扶贫项目管理系统。ssm+sqlserver音乐资源分享网站。ssm基于Web的精品课程网站的设计与实现。ssm基于JavaEE的网上图书分享系统。_基于javaweb的差旅报销系统毕业设计
文章浏览阅读2.4k次。我是从3.8.3更新到3.11.4,pycharm版本是2020.1.2,所以网上说的更改文件权限、检查路径是否有中文我统统都试过了,所以我狠心直接重装新版本的2022.3.3,一顿操作过后发现能成功创建project了也不报错。将python版本更新后,使用pycharm突然无法创建虚拟环境virtualenv失败,提示路径从C:\Users\Lenovo\AppData\Local\下的什么什么到创建的路径的下的什么什么 我这里已经解决了忘记截图保存。_error: the executable g:\workspace\pythonproject\venv\scripts\python.exe is
文章浏览阅读80次。如今社会上各行各业,都喜欢用自己行业的专属软件工作,互联网发展到这个时候,人们已经发现离不开了互联网。新技术的产生,往往能解决一些老技术的弊端问题。因为传统商品交易信息管理难度大,容错率低,管理人员处理数据费工费时,所以专门为解决这个难题开发了一个电商平台,可以解决许多问题。电商平台可以实现商家管理,商品订单管理,用户管理,商品管理,商品评价管理等功能。该系统采用了Mysql数据库,Java语言,Spring Boot框架等技术进行编程实现。电商平台可以提高商品交易信息管理问题的解决效率,优化商品交
文章浏览阅读400次。“三人行,必有我师焉”,学习就是要从别人身上学到好的。今天特意给大家推荐10个优质公众号,目前属于活跃度非常高的几个原创公众号,涵盖了python和AI,重点是他们还坚持在原创技术免费分享的第一线!SQL数据库开发专注数据相关领域,主要分享MySQL,数据分析,Python,Excel 等相关技术内容,关注回复「1024」获取资源大礼包。点击上方名片可关注深度学习与图网络..._公众号 跟我学ai
文章浏览阅读167次。NetMQ 是 ZeroMQ的C#移植版本。ZeroMQ是一个轻量级的消息内核,它是对标准socket接口的扩展。它提供了一种异步消息队列,多消息模式,消息过滤(订阅),对多种传输协议的无缝访问。NetMQ 也是一个社区开源项目,网站在Github上 https://github.com/zeromq/netmq, 可以通过Nuget包获取http://nuget.org/package..._netmq kafka
文章浏览阅读483次。 前一段时间买了几本新版金庸小说口袋本,包括变动比较大的《天龙八部》与《射雕英雄传》。《天龙八部》的改动还是比较大的。大家非常熟悉的”降龙十八掌”变成了”降龙二十八掌”,到了小说的最后,萧峰和虚竹二人将”二十八掌”精简成了”十八掌”,又绕了回来,作为铁杆金庸读者我觉得这样的变化有些画蛇添足,也不知道金庸老先生这样改的目的为何。小说中的线索也变化了很多,增加了诸如丁...
文章浏览阅读47次。springboot基于Springbootvue的教学辅助系统设计与实现。springboot基于springboot的智能ERP管理系统。springboot基于Springboot的高校教室管理系统。springboot基于springboot的产后护理系统。springboot基于java电商后台管理系统。springboot特困生在线申报和信息服务系统。ssm基于微信小程序的汉服租赁平台的设计与实现。ssm基于vue的高校宿舍报修系统的设计与实现。springboot少数民族饰品销售系统。
文章浏览阅读3.2k次。wkt 、wkb、几何对象的转换_arcgis shape字段wkb
文章浏览阅读972次。./qt-creator-linux-x86-opensource-2.6.1.bin./qt-creator-linux-x86-opensource-2.6.1.bin:: error while loading shared libraries: libgobject-2.0.so.0: cannot open shared object file: No such file or ..._error while loading shared libraries: libgobject-2.0.so.0: cannot open share