Java数据结构习题.doc

《Java数据结构习题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第一章绪论数据结构研究内容：数据的逻辑结构、存储结构及其操作逻辑结构的分类：两大类分为线性结构、非线性结构；三大类分为线性结构、树、图物理结构：顺序存储和链式存储（特点、优缺点...）1、对存储的连续性要求：顺序存储要求连续；链式存储连续与否均可2、存储密度：顺序存储的存储密度大，可达100%；链式存储存储密度较小3、对元素的访问：顺序存储比较方便。顺序存储是随机访问；链式存储是顺序访问4、删除和插入操作：链式存储的删除和插入操作较简单算法分析的两个方面：时间复杂度、空间复杂度程序段的时间复杂度第二章线性表（重点）线性表的基本概念习题：线性表L=(a1,a2,……,an)，下列说法正确的

2、是（）。A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继线性表的两种存储方式习题：1、链表不具有的特点是（）。A.可随机访问任一元素　B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比2、线性表采用链式存储时，结点的存储地址（）。A.必须是连续的B.必须是不连续的C.连续与否均可D.和头结点的存储地址相连续3、在以下的叙述中，正确的是（）。A.线性表的顺序存储结构优于链表存储结构　B.线性表的顺序存储结构适用于频

3、繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构4、判断：在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。（）单链表、循环链表、双向链表的特点与优缺点习题：1、从表中任一结点出发，都能扫描整个表的是（）。A.单链表B.顺序表C.循环链表D.静态链表2、循环链表的主要优点是（）。A.不再需要头指针B.已知某结点位置后能容易找到其直接前驱C.在进行插入、删除运算时能保证链表不断开D.在表中任一结点出发都能扫描整个链表3、判断各种线性表的空（或满）：判断顺序表的空及满判断单链表的空判断循环

4、链表的空判断双向链表的空习题：1、带头结点的单链表head为空的条件是。各链表中特殊结点（第一个结点和尾结点）顺序表、单链表、双向链表结点的删除和插入习题：1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句：；。2、非空的循环单链表head的尾结点p满足（）。A.p.getNext()==headB.p.getNext()==nullC.p==nullD.p==head3、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。A.p.setNext(q);q.setPri

5、or(p);p.getNext.setPrior(q);q.setNext(q);B.p.setNext(q);p.getNext.setPrior(q);q.setPrior(p);q.setNext(p.getNext());C.q.setPrior(p);q.setNex(p.getNext());p.getNext.setPrior(q);p.setNex(q);D.q.setNnex(p.getNext());q.setPrio(p);p.setNext(q);p.getNext.setPrior(q);4、带头结点的单链表head为空的判定条件是（）。A.head==null

6、B.head.getNext()==nullC.head.getNext()==headD.head!=null5、在一个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。A.n-iB.n-i+1C.n-i-1D.i+16、在一个单链表中，若删除p所指向结点的后续结点，则执行（）。A.p.setNext(p.getNext().getNext());B.p=p.getNext();p.setNext(p.getNext().getNext());C.p=p.getNext();D.p=p.getNext().getNext();7、在下列对顺序表进行的操作中，算法时间复杂度为O(

7、1)的是（）。A.访问某个元素的前驱B.在某个元素之后插入一个新元素()C.删除某个元素D.对顺序表中元素进行排序8、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p.getNext().getNext()==head，则（）。A.p指向头结点　B.p指向尾结点C.p的直接后继是头结点D.p的直接后继是尾结点线性表的遍历各种线性表遍历参考：顺序表：for(inti=0;i