Java数据结构习题.doc

《Java数据结构习题.doc》由会员分享，可在线阅读，更多相关《Java数据结构习题.doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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()=head B. p. getNext()=null C. p=null D. p=head3、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修

5、改指针的操作是（ ）。A. p.setNext(q);q.setPrior(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)

6、;4、带头结点的单链表head为空的判定条件是（ ）。A. head=null B. head.getNext()=null C. head.getNext()=head D. head!=null5、在一个长度为n的顺序表中删除第i个元素，需要向前移动（ ）个元素。A. n-i B. n-i+1C. n-i-1 D. i+16、在一个单链表中，若删除p所指向结点的后续结点，则执行（ ）。A. p.setNext(p.getNext().getNext();B. p=p.getNext();p.setNext(p.getNext().getNext();C. p =p.getNext();D.

7、 p=p. getNext().getNext();7、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）。A. 访问某个元素的前驱B. 在某个元素之后插入一个新元素( )C. 删除某个元素D. 对顺序表中元素进行排序8、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p. getNext().getNext()=head，则（ ）。A. p指向头结点B. p指向尾结点C. p的直接后继是头结点D. p的直接后继是尾结点线性表的遍历各种线性表遍历参考：顺序表：for(int i=0; i n;i+) /n为线性表长度单链表用于删除或插入时：Node p=he

8、ad; /head为单链表头结点while(p.getNext()!=null)p=p.getNext();单链表用于访问元素时：Node p=head.next; /head为单链表头结点while(p!=null)p=p.getNext();习题：为单链表（带头结点）增加一个函数replaceAll，其功能为将链表中所有与oldElement相等的元素替换为newElement元素。注：单链表的部分结构如下public class SinglyLinkedList /* * 头结点 */private Node head;public SinglyLinkedList() head = n

9、ew Node();public void replaceAll (E oldElement, E newElement)/需要完成的代码第三章 栈和队列（第二重点）栈和队列的概念及其基本概念（定义、特点、栈顶、栈底、入栈、出栈、队头、队尾、入队、出队）习题：1、队列的插入操作是在（ ）。A. 队尾 B. 队头C. 队列任意位置D. 队头元素后2、队和栈的主要区别是（ ）。A. 逻辑结构不同 B. 存储结构不同C. 所包含的运算个数不同 D. 限定插入和删除的位置不同3、栈和队列都是（ ）。A. 链式存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线

10、性结构栈的出栈次序习题：1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（ ）。A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a判断顺序栈空、满：空top=0(或者top=-1) 满top=value.length(或者top=value.length-1)判断链式栈空：top=null循环队列：使用原因(假溢出)front,rear意义（front队头下标，rear队尾下一个的下标）下标变化规律(front=(front+1)%length,rear=(rear+1)%length)队空(front=rear)、队满条

11、件(front=(rear+1)%length)统计队中元素个数：1、当frontrear时，个数为(rear+length)-front。 上两式可统一为：(rear+length-front)%length链式队列的队空条件：front=null & rear=null习题：1、判断一个循环队列Q（最多n个元素）为满的条件是（ ）。A. rear= front B. rear= front+1 C. front=( rear+1)%n D. front=( rear-1)%n2、判定一个顺序栈（栈空间大小为n）为空的条件是（ ）。A. top=0 B. top!=0C. top=nD. t

12、op!=n3、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（ ）。A. NB. N+1C. N-1D. N-24、设循环队列的容量为70，某个状态时front为11，rear为20，则队列中元素的个数为 ；再经过一系列的入队和出队操作后front为20，rear为11，则队列中元素的个数为 。5、在某短信系统中，生成模块和发送模块的处理速度可能会不一致。通常设置一个短信缓冲区，生成模块将生成好的短信依次写入该缓冲区，而发送则从该缓冲区中取走短信向客户发送。该缓冲区应该是一个（ ）结构。A. 栈 B. 队列C. 数组 D. 线性表6、设计一个判别表达式中左右括号是否配对出现的算法，采

13、用（ ）数据结构最佳。A. 线性表的顺序存储结构B. 队列C. 栈 D. 线性表的链式存储结构栈、队列的常用函数及应用栈的常用函数：入栈、出栈、判断栈空、取栈顶元素队列的常用函数：入队、出队、判断队空习题：1、若用一个大小为7的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除两个元素，再加入三个元素后，rear和front的值分别为 ， 。2、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（ ）。A. a B. b C. c D. d3、依次在初始为空的栈中插入元素a,b,c,d以后，紧接着做了两次出栈操作，此时的栈顶元素

14、是（ ）。A. a B. b C. c D. d4、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（ ）。A. front=front.getNext() B. rear= rear.getNext()C. rear.setNext(front)D. front.setNext(rear)队列及栈的应用：递归习题：1、使用递归求2的N次方（N为0到63之间） 2、使用递归求1+2+3+100第四章 字符串字符串的概念及其基本概念（定义、串长、子串与主串、空串与空白串、子串的位置、串相等）String类或StringBuffer类的一些常用函数：lengt

15、h, charAt, substring, startsWith, endsWith, append, delete, deleteCharAt习题：1、串与普通的线性表相比较，它的特殊性体现在（ ）。A. 顺序的存储结构B. 链式存储结构C. 数据元素是一个字符 D. 数据元素任意2、String str = “StringBuffer”。则str.length()= , str.charAt(3)= , str.indexOf(“tr”)= , str.substring( , )=”ing”, str.delete(1, 6)= 。第五章 数组与矩阵数组的定义（与线性表的关系）一维数组即

16、为线性表的物理存储的实现。二维及多维数组可以看作是特殊的线性表，特殊性在于其数据元素是数组。数组的遍历矩阵的存储特殊矩阵的存储的目的对一些特殊矩阵采用压缩存储的目的主要是为了（ ）。A. 表达变得简单 B. 对矩阵元素的存取变得简单C. 去掉矩阵中的多余元素 D. 减少不必要的存储空间的开销稀疏矩阵的存储习题：1、如图有一个稀疏矩阵，请写出它的三元组表。 2、有一个6*7的稀疏矩阵，其三元组线性表为（0，2，11），（0，4，17），（1，1，20），（3，0，24），（3，5，28），（4，4，50），请写出此矩阵。第六章 查找查找的分类：动态查找（查找的同时对表做修改运算）、静态查找（查找

17、的同时不对表做修改运算）。各种查找及适用场合顺序查找不需要附加条件，但查找速度较低。折半查找效率稍高，需要查找表有序。索引查找需要建立索引。习题：1、有关键字序列1， 3，-9， 2， 90，8，30。现使用顺序查找找90，则需要查找 次能找到。2、有有序关键字序列1，3，5， 9，20，23，30。现使用折半查找找23，则需要找 次能找到。第七章 排序三种基本排序（包括时间、空间复杂度及稳定性）三种基本排序的时间复杂度都为O(n2)，空间复杂度都为O(1)直接插入排序是稳定的冒泡排序是稳定的简单选择排序是不稳定的习题：分别使用直接插入排序、冒泡排序、简单选择排序对数组73 80 21 20 85 12 9 45 17 93进行排序，写出各趟排序的结果