下载文档原格式
第 1 章 绪 论(2005-07-14) -第 1 章 绪 论课后习题讲解1. 填空⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
【解答】数据元素⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。
【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。
⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。
【解答】集合，线性结构，树结构，图结构⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。
【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。
【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。
【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。
【解答】问题规模⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为n*log25n，则表示成数量级的形式为（ ）。
【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。
2. 选择题⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。
A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。
⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
数据结构第一章课后习题与答案资料1.什么是数据结构？答：数据结构是指数据对象以及数据对象之间的关系、操作和约束的一种逻辑结构。
它关注如何将数据以及数据之间的关系组织起来，以便更高效地进行操作和使用。
2.数据结构的分类有哪些？答：数据结构可以分为线性数据结构和非线性数据结构。
线性数据结构包括数组、链表、栈和队列；非线性数据结构包括树和图。
3.什么是算法？答：算法是指解决特定问题的一系列步骤和规则。
它可以描述为一个有限的指令集，用于将输入数据转换为输出结果。
4.算法的特征有哪些？答：算法具有以下特征：•输入：算法必须有输入，可以是零个或多个。
•输出：算法必须有输出，可以是零个或多个。
•有穷性：算法必须在有限步骤内结束。
•确定性：算法的每一步骤必须明确且无歧义。
•可行性：算法的每一步骤必须可行，即可以执行。
5.算法的时间复杂度是什么？如何表示时间复杂度？答：算法的时间复杂度是指算法执行所需的时间。
它通常用大O符号表示。
常见的时间复杂度有O(1)、O(n)、O(n^2)等。
6.算法的空间复杂度是什么？如何表示空间复杂度？答：算法的空间复杂度是指算法执行所需的额外空间。
它通常用大O符号表示。
常见的空间复杂度有O(1)、O(n)、O(n^2)等。
7.什么是数据的逻辑结构？答：数据的逻辑结构是指数据对象之间的关系。
常见的逻辑结构有线性结构、树形结构和图形结构。
8.什么是数据的存储结构？答：数据的存储结构是指数据在计算机内存中的表示方式。
常见的存储结构有顺序存储结构和链式存储结构。
9.顺序存储结构和链式存储结构有什么区别？答：顺序存储结构将数据存储在一块连续的内存空间中，可以随机访问元素，但插入和删除操作需要移动大量元素。
链式存储结构将数据存储在不连续的内存空间中，通过指针相连，插入和删除操作只需要修改指针，但访问元素需要遍历链表。
10.数组和链表的区别是什么？答：数组是一种顺序存储结构，元素在内存中连续存储，可以通过下标直接访问元素；链表是一种链式存储结构，元素在内存中不连续存储，通过指针相连。
1.6 习题1.6.1知识点：数据结构的定义一、选择题1①数据结构通常是研究数据的（ A ）及它们之间的相互联系。
A．存储和逻辑结构B．存储结构C．顺序结构D．链式存储结构2①数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ C ）A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构3①线性结构是数据元素之间存在一种（D ）。
A．一对多关系 B. 多对多关系 C 多对一关系D 一对一关系4①计算机内部数据处理的基本单位是（ B ）。
A. 数据B．数据元素 C.数据项D．数据库5②从逻辑上可以把数据结构分为（C ）两大类。
【武汉交通科技大学1996】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构二、填空题1①数据结构按逻辑结构可分为四大类，它们分别是集合、线性、树、图。
2①数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、散列、索引。
三、判断题（F）1①数据元素是数据的最小单位。
（T ）2①记录是数据处理的最小单位。
（ F ）3①数据的逻辑结构是指数据的各数据项之间的逻辑关系。
（T ）4①数据的物理结构是指数据在计算机内的实际存储形式。
四、简答题1①简述什么是数据结构?2②数据结构与数据类型有什么区别? 【哈尔滨工业大学2001】1.6.2知识点：算法的概念一、选择题1①计算机算法指的是（C ）A．计算方法B．排序方法C．解决问题的有限运算序列D．调度方法2①算法分析的目的是（（1）C ），算法分析的两个主要方面（（2）A ）．（1） A ．找出数据结构的合理性 B ．研究算法中的输入与输出的关系C ．分析算法的效率以求改进D ．分析算法的易查性和文档性（2） A ．空间复杂度和时间复杂度 B ．正确性和简明性C ．可读性和文档性D ．数据复杂性和程序复杂性3② 设语句X++的时间是单位时间，则语句：for （i=1;i<=n;i++）x++;时间复杂度为（ C ）。
习题一1.1有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。
1．A=(K,R) 其中K={a1,a2,a3,…,a n}R={}2．B=(K,R)，其中K={a,b,c,d,e,f,g,h}R={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}3．C=(K,R)，其中K={a,b,c,d,e,f,g,h}R={<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>}4．D=(K,R)，其中K={1,2,3,4,5,6}R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} 5．E=(K,R)，其中K={48,25,64,57,82,36,75,43}R={r1,r2,r3}r1={<48,25>,<25,64>,<64,57>,<57,82>,<82,36>,<36,75>,<75,43>}r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>,<36,43>}r3={<25,36>,<36,43>,<43,48>,<48,57>,<57,64>,<64,75>,<75,82>} 解：⑴是集合结构；⑵是线性结构；⑶⑷是树型结构；⑸散列结构1.2用C语言函数编写下列每一个算法，并分别求出它们的时间复杂度。
一、填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。
02、数据结构被形式地定义为(D,R)，其中D是(数据元素)的有限集合，R是D上的(关系)有限集合。
03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。
04、数据结构按逻辑结构可分为两大类，它们分别是(线性结构)和(非线性结构)。
05、线性结构中元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中元素之间存在(多对多)关系。
06、在线性结构中，第一个结点(没有)前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点(没有)后续结点，其余每个结点有且只有1个后续结点。
07、在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(1)个前驱结点；叶子结点没有(后续)结点，其余每个结点的后续结点数可以(任意多个)。
08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个)。
09、数据的存储结构可用四种基本的存储方法表示，它们分别是(顺序)、(链式)、(索引)、(散列)。
10、对于给定的n个元素，可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。
11、数据的运算最常用的有5种，它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。
12、一个算法的效率可分为(时间)效率和(空间)效率。
13、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。
14、一个数据结构在计算机中的(映射)称为存储结构。
15、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。
16、已知如下程序段for (i=n; i>=1; i--) //语句1{ x++; //语句2for (j=n; j>=i; j--) //语句3y++; //语句4}语句 1 执行的频度为(n+1)；语句2执行的频度为(n)；语句3执行的频度为(n(n+3)/2)；语句4执行的频度为(n(n+1)/2)。
Ch1绪论1．下列与数据元素有关的叙述中，哪一个是不正确的（B）。
A．数据元素是数据的基本单位，即数据集合中的个体B．数据元素是有独立含义的数据最小单位C．数据元素又称结点D．数据元素又称作记录2．下列关于数据的逻辑结构的叙述中，哪一个是正确的（A）。
A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构3．数据的基本单位是（数据元素），在计算机中通常作为一个（整体）进行处理。
4．所有能输入到计算机中并被计算机程序处理的（符号）称为数据。
5．数据结构是一门研究非数值计算的程序设计问题中计算机的（①A）以及它们之间的（②B）和运算等的学科。
① A．数据元素 B．计算方法 C．逻辑存储 D．数据映像② A．结构 B．关系 C．运算 D．算法6．数据结构被形式的定义为（K，R），其中K是（①B）的有限集，R是K上的（②D）有限集。
① A．算法 B．数据元素 C．数据操作 D．逻辑结构② A．操作 B．映像 C．存储 D．关系7．具有线性结构的数据结构是（D）。
A．树B．图C．广义表D．栈8．在数据结构中，从逻辑上可以把数据结构分为（D）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．内部结构和外部结构D．线性结构和非线性结构9．线性结构中元素之间存在（A）关系。
A．一对一B．一对多C．多对一D．多对多10．数据逻辑结构包括（集合）、（线性结构）、（树形结构）和（图状结构）四种类型，树形结构和图形结构合称为（非线性结构）。
11．在线性结构中，第一个结点（没有）前驱结点，其余每个结点有且只有（1）个前驱结点，最后一个结点（没有）后继结点，其余每个结点有且只有（1）个后继结点。
12．在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（1）个前驱结点，叶子结点没有（后继）结点，其余每个结点的后继结点可以（任意多个）。
