《数据结构java语言描述课后答案》由会员分享，可在线阅读，更多相关《数据结构java语言描述课后答案（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构java语言描述课后答案【篇一：数据机构第一章一一java语言描述第1章绪 论习题参考答案】概念题1. 试述下列各组概念：数据、数据兀素、数据项数据结构、数据的逻辑结构、数据的存储结构数据类型、数据操作算法、算法的时间复杂度、算法的空间复杂度参考答案：略2. 试述数据结构研究的3个方面的内容。参考答案：数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构 和数据的运算(操作)。3 .试述集合、线性结构、树型结构和图型结构四种常用数据结构 的特性。参考答案：集合结构：集合中数据元素之间除了 “同属于一个集合”的特性外， 数据元素之间无其它关系，它们之间的关系是松散性的。线性结构：线
2、性结构中数据元素之间存在“一对一”的关系。即若结 构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前 趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且 仅有一个前驱和一个后继。树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结 构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点 有且仅有一个前驱，所有结点都可以有多个后继。图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结 构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。4.设有数据的逻辑结构的二元组定义形式为b=(d,r)，其中 d=a1,a2,?,an，r=ai,ai+1| i=1,2
3、,?，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的定
4、义可得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
5、为正整数)。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;w
6、hile (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 =
7、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 =
8、 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
9、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; /发生了交换，
10、故将交换标志置为真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
11、 i = 0; i values.length; i+)system.out.print(valuesi + );运行结果2 .设计一个复数类，要求：(1)在复数内部用双精度浮点数定义其实部和虚部。给复数的实部，虚部为0;第3个构造函数将两个双精度浮点数分 别赋给复数的实部和虚部。(3) 编写获取和修改复数的实部和虚部的成员函数。(4) 编写实现复数的减法、乘法运算的成员函数。设计一个测试主函数，使其实际运行验证类中各成员函数的正确性。参考答案：package ch01exercise;/复数类class complex 【篇二：数据结构(java语言版)试卷1】考试科目：数据结构考试形式：闭
12、卷适应班级：软开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
13、、以下数据结构中哪一个是非线性结构？ （）为满队列的条件是（）。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.inde
14、xof （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,其输出序
