2014广东省JAVA版数据结构最新考试题库(完整版)_图文

数据结构试卷（一）王彬一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

java数据结构期末考试题及答案一、选择题（每题2分，共20分）1. 在Java中，哪个类提供了栈的实现？A. ArrayListB. LinkedListC. StackD. Vector答案：C2. 下列哪个选项是二叉树的遍历方式？A. 先序遍历B. 中序遍历C. 后序遍历D. 所有以上答案：D3. Java中HashMap的默认初始容量是多少？A. 10B. 16C. 32D. 64答案：B4. 在Java中，哪个接口定义了集合？A. CollectionB. IterableC. ListD. Set答案：A5. 下列哪个不是Java集合框架中的接口？A. ListB. SetC. MapD. Array答案：D6. Java中ArrayList和LinkedList的主要区别是什么？A. ArrayList基于动态数组实现，LinkedList基于链表实现B. ArrayList基于链表实现，LinkedList基于动态数组实现C. ArrayList和LinkedList都是基于链表实现D. ArrayList和LinkedList都是基于动态数组实现答案：A7. 在Java中，哪个类实现了优先队列？A. PriorityQueueB. QueueC. StackD. Deque答案：A8. Java中，哪个方法用于将数组转换为ArrayList？A. Arrays.asList()B. Collections.addAll()C. Arrays.copyOf()D. Collections.copy()答案：A9. 下列哪个不是Java集合框架中的类？A. HashSetB. TreeSetC. LinkedHashMapD. Object答案：D10. 在Java中，哪个类提供了双向队列的实现？A. QueueB. StackC. DequeD. List答案：C二、填空题（每题2分，共20分）1. Java中的______类实现了双端队列接口。

二级JAVA真题2014年09月(总分：100.00，做题时间：90分钟)一、{{B}}选择题{{/B}}(总题数：40，分数：40.00)1.下列数据结构中，属于非线性结构的是______。

∙ A.循环队列∙ B.带链队列∙ C.二叉树∙ D.带链栈（分数：1.00）A.B.C. √D.解析：[解析] 线性结构满足两个条件：有且仅有一个根结点；每个结点最多有一个前件，也最多一个后件，栈和队列均满足这两个条件，属于线性结构。

二叉树属于非线性结构，因为除了叶子结点外，每个结点都可以有两个后件，不满足线性表的条件。

2.下列数据结构中，能够按照“先进后出”原则存取数据的是______。

∙ A.循环队列∙ B.栈∙ C.队列∙ D.二叉树（分数：1.00）A.B. √C.D.解析：[解析] 栈是一种线性表，其插入或者删除运算都在表的一端进行，即按照“先进后出”原则存取数据。

3.对于循环队列，下列叙述中正确的是______。

∙ A.队头指针是固定不变的∙ B.队头指针一定大于队尾指针∙ C.队头指针一定小于队尾指针∙ D.队头指针可以大于队尾指针，也可以小于队尾指针（分数：1.00）A.B.C.D. √解析：[解析] 在循环队列中用队尾指针(Rear)指向队列中的队尾元素，用队头指针(Front)指向队头元素的前一个位置。

在循环队列结构中，一般情况下rear＞front，当存储空间的最后一个位置已被使用，而要进行入队时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。

此时便有front＞rear。

4.算法的空间复杂度是指______。

∙ A.算法在执行过程中所需要的计算机存储空间∙ B.算法所处理的数据量∙ C.算法程序中的语句或指令条数∙ D.算法在执行过程中所需要的临时工作单元数（分数：1.00）A. √B.C.D.解析：[解析] 算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间。

数据结构（java）复习题及答案⼀、选择题1、数据结构在计算机内存中的表⽰是指____A__A．数据的存储结构 B.数据结构C. 数据的逻辑结构D.数据元素之间的关系2、若⼀个算法的时间复杂度⽤T(n)表⽰，其中n的含义是（ A ）A．问题规模 B．语句条数C．循环层数 D．函数数量3、下列选项中与数据存储结构⽆关的术语是（ D ）A.顺序表B.链表C.链队列D.栈4、已知循环队列的存储空间⼤⼩为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下⼀个位置，则向队列中插⼊新元素时，修改指针的操作是（ D ）A.rear=(rear-1)%m;B.front=(front+1)%m;C.front=(front-1)%m;D.rear=(rear+1)%m;5、栈和队列的共同点是__C______A.都是先进后出B.都是先进先出C.只允许在端点处插⼊和删除元素D.没有共同点6、已知⼀堆栈的进栈序列为1234,则下列哪个序列为不可能的出栈序列______D__A.1234B.4321C.2143D.41237、具有线性结构的数据结构是（ C ）A．树 B．图C．栈和队列 D．⼴义表8、假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ）A．3 B．37C．50 D．979、若栈采⽤链式存储结构，则下列说法中正确的是（ B ）A．需要判断栈满且需要判断栈空B．不需要判断栈满但需要判断栈空C．需要判断栈满但不需要判断栈空D．不需要判断栈满也不需要判断栈空10、若⼀棵具有n(n>0)个结点的⼆叉树的先序序列与后序序列正好相反，则该⼆叉树⼀定是（ C ）A.结点均⽆左孩⼦的⼆叉树B.结点均⽆右孩⼦的⼆叉树C.⾼度为n的⼆叉树D.存在度为2的结点的⼆叉树11、若⼀棵⼆叉树中度为l的结点个数是3，度为2的结点个数是4，则该⼆叉树叶⼦结点的个数是（ B ）A.4B.5C.7D.812、在n个结点的线索⼆叉树中，线索的数⽬为_C_______A．n-1 B. nC.n+1D.2n13、⼀棵完全⼆叉树有1001个结点,其中有____B_____叶⼦结点A.500B.501C.503D.50515、⼀个有n个顶点的⽆向图最多有___C____条边。

二级JAVA真题2014年03月(总分：100.00，做题时间：90分钟)一、{{B}}选择题{{/B}}(总题数：40，分数：40.00)1.下列叙述中正确的是______。

∙ A.栈是“先进先出”的线性表∙ B.队列是“先进后出”的线性表∙ C.循环队列是非线性结构∙ D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构（分数：1.00）A.B.C.D. √解析：[解析] 栈是“先进后出”的线性表，而队列是“先进先出”的线性表，循环队列自然也是线性结构的，有序线性表即可以采用顺序存储结构，也可以采用链式存储结构。

2.支持子程序调用的数据结构是______。

∙ A.栈∙ B.树∙ C.队列∙ D.二叉树（分数：1.00）A. √B.C.D.解析：[解析] 在题目选项中，栈是一种只允许在一端进行插入和删除的线性表。

在高级语言中，函数的调用是通过栈来实现的。

在进行函数调用时，系统将所需的信息存放在栈中，如函数的局部变量、返回值等。

在系统中，每个函数的状态是由函数中的局部变量、函数参数值、函数的返回值地址决定的。

存储这些信息的数据区域称为活动记录，或称为栈帧，它是运行时系统栈上分配的空间，只要函数是正在执行的，它的记录就一直存在，只有当函数退出时才释放其空间。

3.某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是______。

∙ A.10∙ B.8∙ C.6∙ D.4（分数：1.00）A.B.C. √D.解析：[解析] 由二叉树的性质得。

对于一个非空的二叉树，叶子结点数等于度为2的结点数目+1。

4.下列排序方法中，最坏情况下比较次数最少的是______。

∙ A.冒泡排序∙ B.简单选择排序∙ C.直接插入排序∙ D.堆排序（分数：1.00）A.B.C.D. √解析：[解析] 考查各种排序方法的时间复杂度，冒泡排序，简单选择排序，直接插入排序在最坏的情况下比较次数都是O(n2)的，而堆排序的时间复杂度为O(nlog2n)，这也是堆排序的最大优点。

全国计算机等级考试二级JAVA真题题库1 2014年9月(总分：100.00，做题时间：120分钟)一、选择题（每小题1分，共40分）(总题数：40，分数：40.00)1.关系数据库管理系统能实现的专门关系运算包括（）。

（分数：1.00）A.排序、索引、统计B.选择、投影、连接√C.关联、更新、排序D.显示、打印、制表解析：关系数据库管理系统能实现的专门关系运算包括选择、投影、连接。

2.下列叙述中，正确的是（）。

（分数：1.00）A.Reader是一个读取字符文件的接口B.Reader是一个读取数据文件的抽象类√C.Reader是一个读取字符文件的抽象类D.Reader是一个读取字节文件的－般类解析：本题考查Reader类的概念。

首先应该明确，Reader是一个抽象类，字符输入流都是抽象类Reader 类的子类，它是用来读取字符文件的类。

字符输出流都是Writer抽象类的子类。

3.表达式(10*49．3)的类型是（）。

（分数：1.00）A.double √B.charC.longD.float解析：运算中自动类型转换按优先关系从低级数据转换成高级数据。

规定的优先次序是byte，short，char→int→long→float→double。

4.下列关于Java语言特点的叙述中，错误的是（）。

（分数：1.00）A.Java是面向过程的编程语言√B.Java支持分布式计算C.Java是跨平台的编程语言D.Java支持多线程解析：Java是新－代编程语言，具有很多特点：简单易学；利用面向对象技术；分布式计算；健壮性(鲁棒性)；安全性；跨平台(即体系结构中立)；可移植性；解释执行；高性能；多线程；动态性。

因此，本题的正确答案是A。

5.下列说法正确的是（）。

（分数：1.00）A.类FilelnputStream和FileOutputStream用来进行文件1/O处理，由它们所提供的方法可以打开本地主机上的文件，并进行顺序的读/写√B.通过类File的实例或者一个表示文件名称的字符串可以生成文件输人/输出流，在流对象生成的同时，文件被打开，但还不能进行文件读/写C.对于InputStream和OutputStream来说，它们的实例都是是非顺序访问流，即只能进行顺序的读/写D.当从标准输人流读取数据时，从键盘输人的数据直接输入到程序中解析：本题是考查对文件输入、输出流的理解。

Java数据结构试题及解析1 下列数据结构中，能用二分法进行查找的是__A____。

A、顺序存储的有序线性表B、线性链表C、二叉链表D、有序线性链表解析：二分法查找只适用于顺序存储的有序表。

在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等)。

2 在软件设计中，不属于过程设计工具的是__D____。

A、PDL(过程设计语言)B、PAD图C、N-S图D、DFD图解析：软件设计工具包括：程序流程图、N-S、PAD、HIPO，判定表，PDL(伪码)。

而DFD(数据流图)属于结构化分析工具。

3 在switch(expression)语句中，expression的数据类型不能是__A____。

A、doubleB、charC、byteD、short解析：表达式expression只能返回这个几种类型的值：int、byte、short和char。

多分支语句把表达式返回的值依次与每个case子句中的值相比较，如果遇到匹配的值，则执行该case子句后的语句序列。

4 下列叙述中，错误的是__D____。

A、父类不能替代子类B、子类能够替代父类C、子类继承父类D、父类包含子类5 通过继承实现代码复用：Java中所有的类都是通过直接或间接地继承ng.Object类得到的。

继承而得到的类称为子类，被继承的类称为父类。

子类不能继承父类中访问权限为private的成员变量和方法，子类可以重写父类的方法，及命名与父类同名的成员变量。

子类通过隐藏父类的成员变量和重写父类的方法，把父类的状态和行为改变为自身的状态和行为。

注意：子类中重写的方法和父类中被重写的方法要具有相同的名字，相同的参数表和相同的返回类型，只是函数体不同。

由于子类继承了父类所有的属性(私有的除外)，所以子类对象可以作为父类对象使用。

程序中凡是使用父类对象的地方，都可以用子类对象来代替。

一个对象可以通过引用子类的实例来调用子类的方法。

大题共4小题，每小题5分。

共20分)
请在答题卡上作答。

26．设Q是有N个存储空间的循环队列，初始状态front=rear=0，约定指针rear指向的单元始终为空，回答下列问题。

请根据最优二叉树的基本原理，采用类C语言，描述你所设计的成绩判定过程。

29．给定有向无环图G如题29图所示，写出G的5种不同的拓扑排序序列。

的单链表定义如下，其中freq域记录本结点被访问的次数，初值为0，单链表始终以freq 序。

函数f3l完成的功能是：查找给定关键字所在结点，若查找成功，则该结点的freq域加值调整结r旨位置。

请将空白处(1)～(3)补充完整。

在答题卡上作答。

回答下列问题。

五、算法设计题(本大题共l小题，共“l0分) 请在答题卡上作答。

34．已知带头结点的单链表类型定义如下：
- 10 -。