java数据结构之家族亲属关系查询系统
家谱
else if(getCol6Guanxi15==3){
jTextField19.setText("舅母");
if(getNanNvjTF14)
jTextField18.setText("外甥侄子");
else
jTextField18.setText("外甥侄女");
}
else if(getCol6Guanxi15==4){
jTextField19.setText("姑父");
if(getNanNvjTF14)
jTextField18.setText("表侄子");
else
jTextField18.setText("表侄女");
}
else ;
}
else if(getjTF15col==6){
if(getCol6Guanxi14==1){
if(getNanNvjTF14)
jTextField18.setText("堂兄/堂弟");
else
jTextField18.setText("堂姐/堂妹");
if(getNanNvjTF15)
jTextField19.setText("堂弟/堂兄");
else
jTextField19.setText("堂妹/堂姐");
}
else if(getCol6Guanxi14==2){
if(getNanNvjTF14)
jTextField18.setText("表兄/表弟");
else
jTextField18.setText("表姐/表妹");
if(getNanNvjTF15)
jTextField19.setText("表弟/表兄");
else
jTextField19.setText("表妹/表姐");
}
else if(getCol6Guanxi14==3){
if(getNanNvjTF14)
jTextField18.setText("表兄/表弟");
else
jTextField18.setText("表姐/表妹");
if(getNanNvjTF15)
jTextField19.setText("表弟/表兄");
else
jTextField19.setText("表妹/表姐");
}
else if(getCol6Guanxi14==4){
if(getNanNvjTF14)
jTextField18.setText("表兄/表弟");
else
jTextField18.setText("表姐/表妹");
if(getNanNvjTF15)
jTextField19.setText("表弟/表兄");
else
jTextField19.setText("表妹/表姐");
}
else ;
}
else ;
7
else if(getjTF14col==6){
if(getjTF15col==1){
if(getCol6Guanxi15==1){
jTextField19.setText("伯父/叔叔");
if(getNanNvjTF14)
jTextField18.setText("侄子");
else
jTextField18.setText("侄女");
}
else if(getCol6Guanxi15==2){
jTextField19.setText("姨姨");
if(getNanNvjTF14)
jTextField18.setText("侄子");
else
jTextField18.setText("侄女");
}
6
else if(getjTF14col==5){
if(getjTF15col==1){
if(getCol6Guanxi15==1){
jTextField19.setText("哥哥/弟弟");
jTextField18.setText("弟妹/嫂子");
}
else if(getCol6Guanxi15==2){
jTextField19.setText("姐姐/妹妹");
jTextField18.setText("妹夫/姐夫");
}
else if(getCol6Guanxi15==3){
jTextField19.setText("大舅子/小舅子");
jTextField18.setText("妹夫/姐夫");
}
else if(getCol6Guanxi15==4){
jTextField19.setText("姐姐/妹妹");
jTextField18.setText("弟妹/嫂子");
}
else ;
}
else if(getjTF15col==5){
if(getCol6Guanxi14==1){
jTextField18.setText("妯娌");
jTextField19.setText("妯娌");
}
else if(getCol6Guanxi14==2){
jTextField18.setText("一单挑");
jTextField19.setText("一单挑");
}
else if(getCol6Guanxi14==3){
jTextField18.setText("嫂子/弟妹");
jTextField19.setText("妹夫/姐夫");
}
else if(getCol6Guanxi14==4){
jTextField18.setText("姐夫/妹夫");
jTextField19.setText("弟妹/嫂子");
}
else ;
}
else if(getjTF15col==6){
if(getCol6Guanxi14==1){
jTextField18.setText("伯母/婶婶");
if(getNanNvjTF15)
jTextField19.setText("侄子");
else
jTextField19.setText("侄女");
}
else if(getCol6Guanxi14==2){
jTextField18.setText("姨夫");
if(getNanNvjTF15)
jTextField19.setText("表侄子");
else
jTextField19.setText("表侄女");
}
else if(getCol6Guanxi14==3){
jTextField18.setText("舅母");
if(getNanNvjTF15)
jTextField19.setText("外甥侄子");
else
jTextField19.setText("外甥侄女");
}
else if(getCol6Guanxi14==4){
jTextField18.setText("姑父");
if(getNanNvjTF15)
jTextField19.setText("表侄子");
else
jTextField19.setText("表侄女");
}
else ;
}
else ;
}
5
if(getjTF14col==1){
if(getjTF15col==5){
if(getCol6Guanxi14==1){
jTextField18.setText("哥哥/弟弟");
jTextField19.setText("弟妹/嫂子");
}
else if(getCol6Guanxi14==2){
jTextField18.setText("大姨子/小姨子");
jTextField19.setText("妹夫/姐夫");
}
else if(getCol6Guanxi14==3){
jTextField18.setText("大舅子/小舅子");
jTextField19.setText("妹夫/姐夫");
}
else if(getCol6Guanxi14==4){
jTextField18.setText("姐姐/妹妹");
jTextField19.setText("弟妹/嫂子");
}
else ;
}
else if(getjTF15col==6){
if(getCol6Guanxi14==1){
jTextField18.setText("伯父/叔叔");
if(getNanNvjTF15)
jTextField19.setText("侄子");
else
jTextField19.setText("侄女");
}
else if(getCol6Guanxi14==2){
jTextField18.setText("姨姨");
if(getNanNvjTF15)
jTextField19.setText("侄子");
else
jTextField19.setText("侄女");
}
else if(getCol6Guanxi14==3){
jTextField18.setText("舅舅");
if(getNanNvjTF15)
jTextField19.setText("外甥侄子");
else
jTextField19.setText("外甥侄女");
}
else if(getCol6Guanxi14==4){
jTextField18.setText("姑姑");
if(getNanNvjTF15)
jTextField19.setText("娘家侄子");
else
jTextField19.setText("娘家侄女");
}
else ;
}
else ;
}
4
else if(getjTF15col==3){
if(isNanOrNv((String) jTable1.getValueAt(row,1))){
jTextField19.setText("爷爷");
if(getNanNvjTF14)
jTextField18.setText("孙子");
else
}
else {
jTextField19.setText("外公");
if(getNanNvjTF14)
jTextField18.setText("外甥");
else
jTextField18.setText("外甥女");
}
}
else if(getjTF15col==4){
if(isNanOrNv((String) jTable1.getValueAt(row,1))){ jTextField19.setText("奶奶");
if(getNanNvjTF14)
jTextField18.setText("孙子");
else
jTextField18.setText("孙女");
}
else {
jTextField19.setText("外婆");
if(getNanNvjTF15)
jTextField18.setText("外甥");
else
jTextField18.setText("外甥女");
}
}
else if(getjTF15col==5){
if(isNanOrNv((String) jTable1.getValueAt(row,1))) jTextField19.setText("母亲");
else
jTextField19.setText("父亲");
if(getNanNvjTF15)
jTextField18.setText("儿子");
else
jTextField18.setText("女儿");
}
else if(getjTF15col==6){
if(getNanNvjTF14)
jTextField18.setText("哥哥/弟弟");
else
jTextField18.setText("姐姐/妹妹");
if(getNanNvjTF15)
jTextField19.setText("弟弟/哥哥");
else
}
else ;
}
else ;
}
3
else if(getjTF15col==4){
if(isNanOrNv((String) jTable1.getValueAt(row,1))){
jTextField18.setText("儿媳");
jTextField19.setText("婆婆");
}
else {
jTextField18.setText("女婿");
jTextField19.setText("岳母");
}
}
else if(getjTF15col==6){
if(isNanOrNv((String) jTable1.getValueAt(row,1)))
jTextField18.setText("母亲");
else
jTextField18.setText("父亲");
if(getNanNvjTF15)
jTextField19.setText("儿子");
else
jTextField19.setText("女儿");
}
else ;
}
else if(getjTF14col==6){
if(getjTF15col==1){
if(getNanNvjTF14)
jTextField18.setText("儿子");
else
jTextField18.setText("女儿");
if(getNanNvjTF15)
jTextField19.setText("父亲");
else
jTextField19.setText("母亲");
}
2
else if(getjTF14col==4){
if(getjTF15col==1){
jTextField18.setText("母亲");
if(getNanNvjTF15)
jTextField19.setText("儿子");
else
jTextField19.setText("女儿");
}
else if(getjTF15col==3){
jTextField18.setText("妻子");
jTextField19.setText("丈夫");
}
else if(getjTF15col==5){
if(isNanOrNv((String) jTable1.getValueAt(row,1))){
jTextField18.setText("婆婆");
jTextField19.setText("儿媳");
}
else {
jTextField18.setText("岳母");
jTextField19.setText("女婿");
}
}
else if(getjTF15col==6){
if(isNanOrNv((String) jTable1.getValueAt(row,1))){
jTextField18.setText("奶奶");
if(getNanNvjTF15)
jTextField19.setText("孙子");
else
jTextField19.setText("孙女");
}
else {
jTextField18.setText("外婆");
if(getNanNvjTF15)
jTextField19.setText("外甥");
else
jTextField19.setText("外甥女");
}
}
else ;
}
else if(getjTF14col==5){
if(getjTF15col==1){
if(getNanNvjTF14){
jTextField18.setText("丈夫");
jTextField19.setText("妻子");
}
else {
jTextField18.setText("妻子");
jTextField19.setText("丈夫");
}
}
else if(getjTF15col==3){
if(isNanOrNv((String) jTable1.getValueAt(row,1))){
jTextField18.setText("儿媳");
jTextField19.setText("公公");
}
else {
jTextField18.setText("女婿");
jTextField19.setText("岳父");
}
}
1
if(getjTF14col==1){
if(getjTF15col==3){
if(getNanNvjTF14)
jTextField18.setText("儿子");
else
jTextField18.setText("女儿");
jTextField19.setText("父亲");
}
else if(getjTF15col==4){
if(getNanNvjTF14)
jTextField18.setText("儿子");
else
jTextField18.setText("女儿");
jTextField19.setText("母亲");
}
else if(getjTF15col==5){
if(getNanNvjTF14){
jTextField18.setText("丈夫");
jTextField19.setText("妻子");
}
else {
jTextField18.setText("妻子");
jTextField19.setText("丈夫");
}
}
else if(getjTF15col==6){
if(getNanNvjTF14){
jTextField18.setText("父亲");
if(getNanNvjTF15)
jTextField19.setText("儿子");
else
jTextField19.setText("女儿"); }
else{
jTextField18.setText("母亲");
if(getNanNvjTF15)
jTextField19.setText("儿子");
else
jTextField19.setText("女儿"); }
}
else ;
}
else if(getjTF14col==3){
if(getjTF15col==1){
jTextField18.setText("父亲");
if(getNanNvjTF14)
jTextField19.setText("儿子");
else
jTextField19.setText("女儿");
}
else if(getjTF15col==4){
jTextField18.setText("丈夫");
jTextField19.setText("妻子");
}
else if(getjTF15col==5){
if(getNanNvjTF14){
jTextField18.setText("公公");
jTextField19.setText("儿媳");
}
else {
jTextField18.setText("岳父");
jTextField19.setText("女婿");
}
}
else if(getjTF15col==6){
if(isNanOrNv((String) jTable1.getValueAt(row,1))){
jTextField18.setText("爷爷");
if(getNanNvjTF15)
jTextField19.setText("孙子");
else
jTextField19.setText("孙女");
}
else {
jTextField18.setText("外公");
if(getNanNvjTF15)
jTextField19.setText("外甥");
else
jTextField19.setText("外甥女"); }
}
else ;
}
数据结构-第六章-图-练习题及答案详细解析(精华版)
图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度
⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。
数据结构复习资料,java数据结构期末考试
第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长
数据结构与算法(JAVA语言版)_
目录 第一章 Java 与面向对象程序设计........................................................................................1 Java 语言基础知识....................................................................................................1 基本数据类型及运算.......................................................................................1 流程控制语句...................................................................................................3 字符串...............................................................................................................3 数组...................................................................................................................5 Java 的面向对象特性................................................................................................7 类与对象...........................................................................................................7 继承...................................................................................................................9 接口.................................................................................................................10 异常.........................................................................................................................11 Java 与指针..............................................................................................................12 数据结构与算法基础.............................................................................................15 数据结构.................................................................................................................15 基本概念.........................................................................................................15 抽象数据类型.................................................................................................17 小结.................................................................................................................19 算法及性能分析.....................................................................................................19 算法.................................................................................................................19 时间复杂性.....................................................................................................20 空间复杂性.....................................................................................................24 算法时间复杂度分析.....................................................................................25 最佳、最坏与平均情况分析.........................................................................27 均摊分析.........................................................................................................29 线性表.....................................................................................................................32 线性表及抽象数据类型.........................................................................................32 线性表定义.....................................................................................................32 线性表的抽象数据类型.................................................................................32 List 接口 ..........................................................................................................34 Strategy 接口 ...................................................................................................35 线性表的顺序存储与实现.....................................................................................36 线性表的链式存储与实现.....................................................................................42 单链表.............................................................................................................42 双向链表.........................................................................................................46 线性表的单链表实现.....................................................................................48 两种实现的对比.....................................................................................................53 基于时间的比较.............................................................................................53 基于空间的比较.............................................................................................53 链接表.....................................................................................................................54 基于结点的操作.............................................................................................54 链接表接口.....................................................................................................54 基于双向链表实现的链接表.........................................................................56 1.1 1.1.1 1.1.2 1.1.3 1.1.4 1.2 1.2.1 1.2.2 1.2.3 1.3 1.4 第二章 2.1 2.1.1 2.1.2 2.1.3 2.2 2.2.1 2.2.2 2.2.3 2.2.4 2.2.5 2.2.6 第三章 3.1 3.1.1 3.1.2 3.1.3 3.1.4 3.2 3.3 3.3.1 3.3.2 3.3.3 3.4 3.5 3.4.1 3.4.2 3.5.1 3.5.2 3.5.3
数据结构选择题集锦
单项选择 （ B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII码B) BCD码C)二进制D)十六进制 （ D ）3. 软件与程序的区别是∶ A)程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 （ C ）4. 所谓“裸机”是指∶ A) 单片机B)单板机C) 不装备任何软件的计算机D) 只装备操作系统的计算机 （ D ）5. 应用软件是指∶ A)所有能够使用的软件B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件D) 专门为某一应用目的而编制的软件 （A）6. C语言中的常量可分为整型常量、实型常量、字符型常量及(枚举)四种。 （A）符号常量（B）长整型常量（C）逻辑常量（D）二进制整数 （ C ）7. 编译程序的功能是∶ A)发现源程序中的语法错误B)改正源程序中的语法错误 C)将源程序编译成目标程序D)将某一高级语言程序翻译成另一种高级语言程序 （A）8. 系统软件中最重要的是∶ A) 操作系统B) 语言处理系统C) 工具软件D) 数据库管理系统 （ C ）9. 可移植性最好的计算机语言是∶ A) 机器语言B)汇编语言C) 高级语言D) 自然语言
（ B ）10. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 （ C ）11. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储 （ C ）12. 算法分析的目的是： A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性 （A）13. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性B) 正确性和简明性 C) 可读性和文档性D) 数据复杂性和程序复杂性 （ C ）14. 计算机算法指的是： A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法 （ B ）15. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性D) 易读性、稳定性和安全性 （ C ）16．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构 （ B ）17.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）120 （A）18. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）19. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素 （A）8 （B）63.5 （C）63 （D）7 （A）20. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
数据结构(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 ） =(rear-1)%m; =(front+1)%m; =(front-1)%m; =(rear+1)%m; 5、栈和队列的共同点是__C______ A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 6、已知一堆栈的进栈序列为1234,则下列哪个序列为不可能的出栈序列______D__ 7、具有线性结构的数据结构是（ C ） A．树 B．图 C．栈和队列 D．广义表 8、假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ） A．3 B．37 C．50 D．97
9、若栈采用链式存储结构，则下列说法中正确的是（ B ） A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空 D．不需要判断栈满也不需要判断栈空 10、若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ C ） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 11、若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（ B ） 12、在n个结点的线索二叉树中，线索的数目为_C_______ A．n-1 B. n +1 13、一棵完全二叉树有1001个结点,其中有____B_____叶子结点 15、一个有n个顶点的无向图最多有___C____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 16、以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）
《数据结构》期末考试题及答案
2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序
《数据结构Java版》习题解答
第0章Java程序设计基础 (1) 【习0.1】实验0.1 哥德巴赫猜想。 (1) 【习0.2】实验0.2 杨辉三角形。 (1) 【习0.3】实验0.3 金额的中文大写形式。 (1) 【习0.4】实验0.4 下标和相等的数字方阵。 (1) 【习0.5】实验0.5 找出一个二维数组的鞍点 (2) 【习0.6】实验0.6 复数类。 (2) 【习0.7】实验0.8 图形接口与实现图形接口的类 (2) 第1章绪论 (3) 【习1.1】实验1.1 判断数组元素是否已按升序排序。 (3) 【习1.2】实验1.3 用递归算法求两个整数的最大公因数。 (3) 第2章线性表 (5) 【习2.1】习2-5 图2.19的数据结构声明。 (5) 【习2.2】习2-6 如果在遍历单链表时，将p=p.next语句写成p.next=p，结果会怎样？ (5) 【习2.3】实验2.2 由指定数组中的多个对象构造单链表。 (5) 【习2.4】实验2.2 单链表的查找、包含、删除操作详见8.2.1。 (5) 【习2.5】实验2.2 单链表的替换操作。 (6) 【习2.6】实验2.2 首尾相接地连接两条单链表。 (6) 【习2.7】实验2.2 复制单链表。 (6) 【习2.8】实验2.2 单链表构造、复制、比较等操作的递归方法。 (7) 【习2.9】建立按升序排序的单链表（不带头结点）。 (8) 【习2.10】实验2.6 带头结点的循环双链表类，实现线性表接口。 (10) 【习2.11】实验2.5 建立按升序排序的循环双链表。 (14) 第3章栈和队列 (17) 【习3.1】习3-5 栈和队列有何异同？ (17) 【习3.2】能否将栈声明为继承线性表，入栈方法是add(0,e)，出栈方法是remove(0)？为什么？ (17) 【习3.3】能否用一个线性表作为栈的成员变量，入栈方法是add(0,e)，出栈方法是remove(0)？ 为什么？ (17) 【习3.4】能否将队列声明为继承线性表，入队方法是add(e)，出队方法是remove(0)？为什么？ (17) 第4章串 (18) 【习4.1】实验4.6 找出两个字符串中所有共同的字符。 (18) 【习4.2】习4-9(1) 已知目标串为"abbaba"、模式串为"aba"，画出其KMP算法的匹配过程，并给出比较次数。 (18)
2015年数据结构期末考试题及答案
2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。
s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。
数据结构(Java版)-线性表的实现与应用完整版
数据结构(Java版)-线性表的实现与应用完整版
实验报告 课程名称数据结构 实验项目线性表的实现及应用 实验仪器PC机一台 学院_____ 专业 班级/学号 姓名 实验日期 成绩 指导教师
北京信息科技大学 信息管理学院 （数据结构课程上机）实验报告 专业: 班级: 学号: 姓名: 成绩: 实验名称线性表的实现及应用实验地点实验时间 1.实验目的： （1）理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。 （2）熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。 2.实验要求： （1）学时为8学时； （2）能在机器上正确、调试运行程序； （3）本实验需提交实验报告； （4）实验报告文件命名方法：数据结构实验_信管16xx_学号_姓名.doc。 3.实验内容和步骤： 第一部分顺序表的实现与应用 （1）基于顺序表实现线性表的以下基本操作： public interface LList
数据结构选择题集锦
数据结构选择题集锦
单项选择 （ B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII码B) BCD码C) 二进制D)十六进制 （ D ）3. 软件与程序的区别是∶ A)程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。
（ C ）4. 所谓“裸机”是指∶ A) 单片机B)单板机C) 不装备任何软件的计算机D) 只装备操作系统的计算机 （ D ）5. 应用软件是指∶ A)所有能够使用的软件 B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件D) 专门为某一应用目的而编制的软件 （ A ）6. C语言中的常量可分为整型常量、实型常量、字符型常量及(枚举)四种。 （A）符号常量（B）长整型常量 （C）逻辑常量（D）二进制整数 （ C ）7. 编译程序的功能是∶ A)发现源程序中的语法错误 B)改正源程序中的语法错误 C)将源程序编译成目标程序 D)将某一高级语言程序翻译成另一种高级语言
程序 （ A ）8. 系统软件中最重要的是∶ A) 操作系统B) 语言处理系统 C) 工具软件D) 数据库管理系统 （ C ）9. 可移植性最好的计算机语言是∶ A) 机器语言B)汇编语言C) 高级语言D) 自然语言 （ B ）10. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 （ C ）11. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储
数据结构(Java版)习题解答
A I N D E X 练习题答案
第一章练习题答案(a) n+(n–1)+(n–2)+…+2+1 = 2)1 (+ n n (b) n+(n–1)+(n–2)+…+2+1 = 2 )1 (+ n n f(n)≦c.g(n) →f(n)=O(g(n)) (a) f(n)=100n+9 c=101, g(n)=n, n0=10 得知f(n)=O(n) (b) f(n)=1000n2+100n–8 c=2000, g(n)= n2, n0=1 得知f(n)=O(n2) (c) f(n)=5*2n+9 n2+2 c=10, n0=5 得知f(n)=O(2n) f(n)≧c g(n) →f(n)=Ω(g(n)) (a) f(n)=3n+1 c=2, n0=1, g(n)=n 得知f(n)=Ω(n)(b) f(n)=100n2+4n+5 c=10, n0=1, g(n)= n2 得知f(n)=Ω(n2) (c) f(n)=8*2n+8n+16 c=8, n0=1, g(n)= 2n 得知f(n)=Ω(n2) c1.g(n)≦f(n)≦c2.g(n) →f(n)= Θ(g(n)) (a) f(n)=3n+2 c1=3, c2=6, n0=1 得知f(n) = Θ (n) (b) f(n)=9n2+4n+2 c1=9, c2=16, n0=1 得知f(n) = Θ (n2) (c) f(n)=8n4+5n3+5 c1=8, c2=20, n0=1 得知f(n) = Θ (n4)
练习题解答 第二章练习题答案 1. 分别以行为主和以列为主说明之。 (a) 以行为主 A(i, j)=l0+(i–1)*u2*d+(j–1)*d (b) 以列为主 A(i, j)=l0+(j–1)*u1*d+(i–1)*d 2. 以列为主 A(i, j)=l0+(j–12)*md+(i–l1)d m=u1–l1+1=5–(–3)+1=9 m=u2–l2+1=2–(–4)+1=7 A(1, 1) =100+(1–(–4))*9+(1–(–3)) =100+45+4=149 3. 分别以行为主和以列为主的说明。 由于数组为A(1：u1, 1：u2, 1：u3)，因此p = u1-l1+1, q = u2- l2+1, r = u3- l3+1 所以p = u1-1+1 = u1, q = u2-1+1 = u2, r = u3-1+1 = u3 (a) 以行为主 A(i, j, k)=l0 + (i–1)*u2*u3*d + (j–1)*u3*d +(k-1) (b) 以列为主 A(i, j, k)=l0 + (k–1)*u1*u2*d + (j–1)*u1*d + (i-1)*d 4. 以列为主：A(i, j, k)=l0 + (k–l3)*pqd + (j–l2)*pd + (i-l1)*d p = 5-(-3) + 1 = 9, q = 2-(-4)+1 = 7, r = 5-1+1 = 5 A(2, 1, 2) = 100 + (2-1)*9*7*1 + (1-(-4))*9*1 + (2-(-3))*1 = 100 + 63 + 45 + 5 = 253
数据结构Java版第二章习题
（按照自己的情况选作部分习题，不要抄袭） 第二章习题 顺序存储线性表 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。√ 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。× 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。√ 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。×6．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。√ 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( A ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 三填空题
1．在顺序表中做插入操作时首先检查___表是否满了______________。 四算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。 3．编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。 提示：可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。 4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R 中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。（研54） 5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表 （a1, a2, … , a m, b1, b2, … , b n）改变为： （b1, b2, … , b n , a1, a2, … , a m）。 五上机实习题目 约瑟夫环问题 约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，
数据结构复习题及答案(12级).
一、选择题。(每小题2分，共40分) (1) 计算机识别.存储和加工处理的对象被统称为____A____。 A.数据 B.数据元素 C.数据结构 D.数据类型 (2) 数据结构通常是研究数据的____ A _____及它们之间的联系。 A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 (3) 不是数据的逻辑结构是____ A ______。 A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为
《数据结构》期末考试试题及答案
《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。 for(i=n-1；i>=0；i--) for(j=0；j