算法和数据结构12

Java数据结构和算法

一、数组于简单排序........................................................... 1

二、栈与队列 ................................................................ 4

三、链表 .................................................................... 7

四、递归 ................................................................... 22

五、哈希表 ................................................................. 25

六、高级排序 ............................................................... 25

七、二叉树 ................................................................. 25

八、红—黑树 ............................................................... 26

九、堆 ..................................................................... 36

十、带权图 ................................................................. 39

一、数组于简单排序

数组

数组（array）是相同类型变量的集合，可以使用共同的名字引用它。数组可被定义为任何类型，可以是一维或多维。数组中的一个特别要素是通过下标来访问它。数组提供了一种将有联系的信息分组的便利方法。

《数据结构与算法》二

您的姓名： [填空题] *

_________________________________

一、单选题

1. 深度优先搜索遍历类似于二叉树的（）. [单选题] *

A. 先序遍历(正确答案)

B. 中序遍历

C. 后序遍历

D. 按层次遍历

2. 无向图顶点v的度是关联于该顶点（）的数目. [单选题] *

A. 顶点

B. 边(正确答案)

C. 序号

D. 下标

3. 有n个顶点的无向图的邻接矩阵是用（）数组存储。. [单选题] *

A. 一维

B. n行n列(正确答案)

C. 任意行n列

D. n行任意列

4.对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（）. [单选题] * A. n-1

B. n+1

C. n(正确答案)

D. n+e

5. 对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）. [单选题] *

A. k1

B. k2(正确答案)

C. k1-k2

D. k1+k2

6. 广度优先遍历类似于二叉树的（）. [单选题] *

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 按层次遍历(正确答案)

7. 任何一个无向连通图的最小生成树（）. [单选题] *

A. 只有一棵

B. 有一棵或多棵(正确答案)

C.

一定有多棵

D. 可能不存在

二、多选题

8. 在某图中，下列选项中说法不正确的是（）. *

A. 不存在顶点到自身的边，或者重复的边，则该图是简单图 B. 不存在顶点到自身的边，或者重复的边，则该图是复杂图(正确答案)

C. 不存在顶点到自身的边，或者重复的边，则该图是无向图(正确答案)

D. 不存在顶点到自身的边，或者重复的边，则该图是有向图(正确答案)

9. 有关图的说法不正确的是（）. *

A. 有向图的边是有向的，又称为弧

B. 有向图的边是有向的，又称为箭头(正确答案)

1 [试题分类]：数据结构与算法

1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。

A.操作

B.存储映像

C.关系

D.数据元素

答案:C

题型:单选题

知识点:1.2 基本概念和术语

难度:1

2.一般而言，最适合描述算法的语言是( )。

A.自然语言

B.计算机程序语言

C.介于自然语言和程序设计语言之间的伪语言

D.数学公式

答案:C

题型:单选题

知识点:1.4 算法和算法分析

难度:1

3．在下列序列中，不是线性表的是( )。

A. (‘a’, ‘b’)

B. (a, b)

C. (‘AB’, ‘CD’)

D. (‘a’, b)

答案:D 2 题型:单选题

知识点:2.1 线性表的类型定义

难度:2

4.对于顺序表的优缺点，以下说法错误的是( )。

A.插入和删除操作较方便

B.可以方便地随机存取表中的任一结点

C.无需为表示结点间的逻辑关系而增加额外的存储空间

D.由于顺序表要求占用连续的空间，存储分配只能预先进行

题型:单选题

知识点:2.2线性表的顺序表示和实现

难度:2

5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。

A. s->next=p->next;p->next=s;

B. p->next=s->next;s->next=p;

C. q->next=s;s->next=p;

D. p->next=s;s->next=q;

题型:单选题

知识点:2.3线性表的链式表示和实现

难度:2

6.若某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。

A.单链表

B.带头结点的单链表

C.单循环链表 3 D.带头结点的双循环链表

题型:单选题

知识点:2 线性表

难度:3

7.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )。

数据结构：数据结构是指数据在计算机内存空间中或磁盘中的组织形式。

其实java只是摆脱了显式表露的指针，指针依旧以存储地址的形式埋藏在程序的深处。有时设置可以说，在java中所有东西都是指针。这句话虽不是百分之一百的正确，但也差不多。

引用（reference）

java中没有重载操作符。在java中，任何类似的重新定义都是不可能的，而可以使用命名的方法，例如add()或其他名字。

在c和c++中 int型的大小可能不同，这取决于它们运行的计算机环境；在java中，一个int型的变量永远是32位

数组：插入算法一步 查找 n/2步 删除需要（假设不允许数据项重复）查找平均n/2个数据项并平均移动剩下的n/2个数据项来填充删除而带来的洞。总共是N步。

有序数组：查找速度比无序的快很多 插入由于所有靠后的数据都需要移动以腾空空间，速度较慢

有序数组和无序数组的删除操作都很慢，数据项必须向前移动来填补已删除数据项的洞。

有序数组在查找频繁的情况下十分有用，若插入和删除较为频繁，则无法高效工作。

计算机算法效率：大O表示法

无序数组的插入：常数

T=K 在现实情况中，插入所需的实际时间（不管是微秒还是其他单位）与以下因素有关：微处理器，编译程序生成程序代码的效率

线性查找：与N成正比 T=K*N/2

二分查找：与log(N)成正比

T=K*log2(N)

大O表示法使用大写字母O,并省去了常数K. 可以认为O的含义是"order of"(大约是)。

O(1) 优秀 O(logN)良好 O(N) 还可以 O(N2) 差

大O表示法的实质并不是对运行时间给出时间值，而是表达了运行时间是如何受数据项个数所影响的。除了实际安装后真正测量一次算法的运行时间之外，这可能是对算法进行比较的最有意义的方法了。