资源预览内容
第1页 / 共14页
第2页 / 共14页
第3页 / 共14页
第4页 / 共14页
第5页 / 共14页
第6页 / 共14页
第7页 / 共14页
第8页 / 共14页
第9页 / 共14页
第10页 / 共14页
亲,该文档总共14页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构java语言描述课后答案【篇一:数据机构第一章一一java语言描述第1章绪 论习题参考答案】概念题1. 试述下列各组概念:数据、数据兀素、数据项数据结构、数据的逻辑结构、数据的存储结构数据类型、数据操作算法、算法的时间复杂度、算法的空间复杂度参考答案:略2. 试述数据结构研究的3个方面的内容。参考答案:数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构 和数据的运算(操作)。3 .试述集合、线性结构、树型结构和图型结构四种常用数据结构 的特性。参考答案:集合结构:集合中数据元素之间除了 “同属于一个集合”的特性外, 数据元素之间无其它关系,它们之间的关系是松散性的。线性结构:线性结构中数据元素之间存在“一对一”的关系。即若结 构非空,则它有且仅有一个开始结点和终端结点,开始结点没有前 趋但有一个后继,终端结点没有后继但有一个前趋,其余结点有且 仅有一个前驱和一个后继。树形结构:树形结构中数据元素之间存在“一对多”的关系。即若结 构非空,则它有一个称为根的结点,此结点无前驱结点,其余结点 有且仅有一个前驱,所有结点都可以有多个后继。图形结构:图形结构中数据元素之间存在“多对多”的关系。即若结 构非空,则在这种数据结构中任何结点都可能有多个前驱和后继。4.设有数据的逻辑结构的二元组定义形式为b=(d,r),其中 d=a1,a2,?,an,r=ai,ai+1| i=1,2,?,n-1,请画由此逻辑结构对 应的顺序存储结构和链式存储结构的示意图。参考答案:顺序存储结构示意图如下:0 1 2 ?n-2 n-1链式存储结构示意图如下:w !=5 设一个数据结构的逻辑结构如图1.9所示,请写出它的二元组 定义形式。图1.9第5题的逻辑结构图参考答案:它的二元组定义形式为b=(d,r),其中d=k1,k2,k3,k4,k5,k6,k7,k8,k9, r=k1,k3,k1,k8,k2,k3k2,k4,k2,k5,k3,k9,k4,k6,k4,k7,k5,k6,k8,k9,k9, k7 。6.设有函数 f (n)=3n2-n+4,请证明 f (n)=o(n2)。书p16的定义可得f (n)=o(n2)。7 .请比较下列函数的增长率,并按增长率递增的顺序排列下列函 数:(1) 2100 (2) (3/2)n(3) (4/3)n (4) nn(5) n2/3(6) n3/2 (7) n!(8)n n (10) log2n(11) 1/log2n (12)log2(log2n)(13)nlog2n(14) nlog2n参考答案:按增长率递增的排列顺序是:1/log2n 2100 log2(log2n)log2nn1/2 n2/3 n nlog2n n3/2 nlog2n(4/3)n (3/2)n n! nn8.试确定下列程序段中有标记符号“*的语句行的语句频度(其中n为正整数)。i=1; k=0;while ( i=n-1) k += 10 * i; /*i+; i=1; k=0;do k +=10 * i; /*i+; while(i=n-1); i = 1; k = 0;while (i=n-1) i+ ;k+= 10 * i; /* k=0;for( i=1; i=n; i+) for (j=1 ; j=i; j+)k+; /* i=1; j=0;while (i+j=n) (if (ij ) j+ ; /* else i+ ;x=n; y=0; / n是不小于1的常数while (x=(y+1)*(y+1) y+; /* x=91; y=100;while (y0 ) if (x100 ) x -= 10; y- -; /* else x+; a=1; m=1;while(an)m+=a;a*=3;/*参考答案:(7) 1100(8) log3n二、算法设计题1 .有一个包括100个数据元素的数组,每个数据元素的值都是实|=最数,试编写一个求最大数据元素的值及其下标的算法,并分析算法的时间复杂度。参考答案:void max(double a) double max = a0;/初始化最大值为数组中的第一个元素int index = 0;/for (int i = 0; i a.length; i+) if (max ai) max = ai;index = i;=J最system.out.println(最大的实数为:+ max + n其在数组中的下标为:+ index);此算法的时间复杂度为o(n),其中n为数组的长度。2 .试编写一个求一元多项式pn(x)?axii?0ni的值pn(x0)的算法,并确定算法中每一条语句的执行次数和整个算法的时间复杂度。输入是ai(i=0J1,2,?,n-1)和x0,输出为pn(x0)。参考答案:0 double getpolynomialresult(double a, double x) ( /a 是多项式中系数数组1 double result = 0;2 double powx = 1;/临时变量,用于减少计算x幂的计算次数3 for (int i = 0; i a.length; i+) 4result += ai * powx;5powx *= x;6 7 return result;8语句17的执行次数分别是:1、1、a.length+1、a.length、a. length、1、1此算法的时间复杂度为o(a.length),其中a.length也是多项式中的 项数。三、上机实践题1 .编写一个实现将整型数组中的数据元素按值递增的顺序进行排序 的java程序。参考答案:package ch01exercise;public class exercise1_3_1 public int bubblesort(int a) / a 为待排序的整数数组int n = a.length;boolean isexchange = true; / 交换标志=j最for (int i = 0; i n - 1isexchange; i+) / 最多做 n-1 趟排序isexchange = false;for (int j = 0; j n - i - 1; j+) /对当前无序区进行排序 if (aj aj + 1) /交换数据元素 int temp = aj;aj = aj + 1;aj + 1 = temp;isexchange = true; /发生了交换,故将交换标志置为真if (!isexchange)break; /本趟排序未发生交换,提前终止算法return a;public static void main(string args) int values = 49, 38, 65, 97, 76, 13, 27, 49 ;system.out.println(排序前数组中数据元素:49 38 65 97 76 13 2749);system.out.print(排序后数组中数据元素:);exercise1_3_1 e = new exercise1_3_1();values = e.bubblesort(values);for (int i = 0; i values.length; i+)system.out.print(valuesi + );运行结果2 .设计一个复数类,要求:(1)在复数内部用双精度浮点数定义其实部和虚部。给复数的实部,虚部为0;第3个构造函数将两个双精度浮点数分 别赋给复数的实部和虚部。(3) 编写获取和修改复数的实部和虚部的成员函数。(4) 编写实现复数的减法、乘法运算的成员函数。设计一个测试主函数,使其实际运行验证类中各成员函数的正确性。参考答案:package ch01exercise;/复数类class complex 【篇二:数据结构(java语言版)试卷1】考试科目:数据结构考试形式:闭卷适应班级:软开1431- 1439,目a. 2,3,4,1,5 b. 2,3,1,4,5 c. 5,4,1,3,2d. 1,5,4,3,2 11、判断一个 循环队列(m0为最大队列长度(以元素为单位),front和rear分别为队列的队头指针和队尾指针)为空队列的条件是()。a. front = rearb. front != rearc. front = (rear+1) % m0d. front != (rear+1) % m0一、单项选择(共20题,每题2分,共40分)12、判断一个循环 队列(m0为最大队列长度(以元素为单位),front和rear分别为队列 的队头指针和队尾指针)1、以下数据结构中哪一个是非线性结构? ()为满队列的条件是()。a.队列 b.栈 c.二叉树 d.线性表 a. front= rearb. front!= rear c. front=( rear+1) % m0 d. front!=( rear+1) % m0 2、()不 是算法的主要特性。金输入性输出性c有穷性d.高效性13、串是一种特殊的线 性表,其特殊性体现在()。a可以顺序存储b,数据元素是一 个字符3、()不是线性表的存储结构。c,可以链式存储d数 据元素可以是多个字符a叉链表b .单链表c,双向链表d.循环链表14、假设s=abcaabcaaabca”,t=bca”,s.indexof (t,3)(其中 3 为索引号, 索引号从0开始编号)4、线性表是:果是()a. 一个有限序列,可以为空;b. 一个有限序列,不能为空;a. 1b. 5c. 10 d. 0 c. 一个无限序列,可以为空;d. 一个无序序列, 不能为空15、二叉树的数据结构描述了数据之间的()关系。5、 用链表表示线性表的优点是()。a链接关系b.层次关系a, 便于随机存取c.网状关系d随机关系b花费的存储空间较顺序 存储少c,便于插入和删除16、()遍历方法在遍历它的左子树和 右子树后再遍历它自身。d,数据元素的物理顺序与逻辑顺序相同a. 先序遍历b.后序遍历c.中序遍历d.层次遍历6、若某线性表中 最常用的操作是在最后一个元素之后插入一个元素和删除第一个元 素,则采用()存储方式最节省运算时间。17、在构造哈夫曼树 的过程中说法正确的是()。a.单链表b.仅有头指针的单循环链表 c.双链表d.仅有尾指针的单循环链表a. 使权值越大的叶结点越远离根结点,而权值越小的叶结点越靠近 根结点b. 使权值越大的叶结点越靠近根结点,而权值越小的叶结点越远离 根结点7、栈中元素的进出原则是()=jc. 最终是带权路径长度最大的二叉树a.先进先出b.后进先出c.栈空则进d.栈满则出d. 构造的过程是一次到位8、若已知一个栈的入栈序列是1, 2, 3, ?, n,其输出序
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号