数据结构第1章绪论答案

第1章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 一个算法应该是（ ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 3．从逻辑上可以把数据结构分为（ ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 二、判断题

1. 数据元素是数据的最小单位。( )

2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 3．算法的优劣与算法描述语言无关，但与所用计算机有关。( ) 4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )

5. 算法可以用不同的语言描述，如果用C 语言来描述，则算法实际上就是程序了。( ) 6．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 三、填空

1．数据的物理结构包括 的表示和 的表示。

2. 对于给定的n个元素,可以构造

第1章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 一个算法应该是（ ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 3．从逻辑上可以把数据结构分为（ ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 二、判断题

1. 数据元素是数据的最小单位。( )

2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 3．算法的优劣与算法描述语言无关，但与所用计算机有关。( ) 4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )

5. 算法可以用不同的语言描述，如果用C 语言来描述，则算法实际上就是程序了。( ) 6．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 三、填空

1．数据的物理结构包括 的表示和 的表示。

2. 对于给定的n个元素,可以构造

数据结构与算法

第 1章 绪 论

数据结构与算法Data Structures and Algorithm教学安排：讲课学时：44 实验学时：12,课程设计：18+1周

考核要求：期末考试占60%,实验成绩占30% ,平时作业占10% 本学期上课时间：1-12周,周二5-6节，周四5-6节. 致知24 考 课 试 程 时 间：14周 设 计：7-15周2015秋

Slide. 1 - 1

理论系列 数据结构与算法 第一 学期 第二 学期 工科数析Ⅰ 代数与几何 工科数析Ⅱ 离散数学

系统系列 计算机导论 数字逻辑 计算机组成技术 数据结构与算法

工具系列 第1 章 绪 论 程序设计语言 C++语言 程序设计实践 Java语言

工程系列

管理系列

其他课程 军训 大学外语 体育 政治 大学外语 体育

计算机职业道德交流技巧 IT企业管理

第三 学期

Linux操作系统*

市场营销软件工程概论 合同法

概率论与数理统计

操作系统 数据结构与算法 课程设计 数据库系统

面向对象技术 与UML

马哲 英语限选 体育

第四 学期

.Net J2EE 系统分析与设计 财务管理 英语限选 体育 英语口语

运筹学

数据库系统 课程设计 计算机网络 编译原理

软件开发实践用户界面设计 面向服务的 计算技术

数据结构与算法

第 1章 绪 论

数据结构与算法Data Structures and Algorithm教学安排：讲课学时：44 实验学时：12,课程设计：18+1周

考核要求：期末考试占60%,实验成绩占30% ,平时作业占10% 本学期上课时间：1-12周,周二5-6节，周四5-6节. 致知24 考 课 试 程 时 间：14周 设 计：7-15周2015秋

Slide. 1 - 1

理论系列 数据结构与算法 第一 学期 第二 学期 工科数析Ⅰ 代数与几何 工科数析Ⅱ 离散数学

系统系列 计算机导论 数字逻辑 计算机组成技术 数据结构与算法

工具系列 第1 章 绪 论 程序设计语言 C++语言 程序设计实践 Java语言

工程系列

管理系列

其他课程 军训 大学外语 体育 政治 大学外语 体育

计算机职业道德交流技巧 IT企业管理

第三 学期

Linux操作系统*

市场营销软件工程概论 合同法

概率论与数理统计

操作系统 数据结构与算法 课程设计 数据库系统

面向对象技术 与UML

马哲 英语限选 体育

第四 学期

.Net J2EE 系统分析与设计 财务管理 英语限选 体育 英语口语

运筹学

数据库系统 课程设计 计算机网络 编译原理

软件开发实践用户界面设计 面向服务的 计算技术

数据结构答案

第 6 章 图

2005-07-14

第 6 章 图

课后习题讲解

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的（ ）。 【解答】出度

⑺ 图的深度优先遍历类似于树的（ ）遍历，它

第一章 数据结构与算法

1.1.1 算法的基本概念

算法是指解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。 程序的编制不可能优于算法的设计。 1．算法的基本特征

(1)可行性：算法中要执行的每一个步骤都可以在有限时间内完成，且正确，否则是不会得到满意结果的。

N=-10;

for( k=1;k<=n;k++ )

c=c+1;

(2)确定性：算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。

X=a·b/c·d X=a·b/(c·d) X=a·(b/c)·d

(3)有穷性：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。

算法的有穷性还应包括合理的执行时间的含义。 for( k=1;k<=n;k++ ) c=c+1;

下例是无限循环：

for( k=1;k<=-10;k++ ) c=c+1;

(4)拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。 2，算法的基本要素

数据结构第一章课件

西安科技大学精品课程

第一章 绪论主要内容： 数据结构的定义；数据结构研究的范围；研究数据结构采用的方法； 算法描述的工具；算法性能的评价。 教学目的： 使学生掌握数据结构中涉及的基本概念，为以后各章的学习打好基础。 重点： 数据结构的定义；算法描述的工具；算法性能的评价； 难点： 算法性能的评价；

数据结构第一章课件

西安科技大学精品课程

1.1 数据结构的基本概念一、数据结构的概念计算机可以处理： a、数值计算 b、非数值计算数据结构复杂，关系 无法用数学方程描述

用计算机解决一个具体问题的步骤：抽象数学模型 设计算法 编制程序,上机调试 寻求数学模型： 分析问题 提取操作对象 找操作对象之间关系 用数学的 语言描述

数据结构第一章课件

西安科技大学精品课程

二、有关术语简介1. 数据(Data)数据——所有能被输入到计算机中，并能被计算机处理的符号集合。是计 算机操作对象的总称。

数据是信息的载体，是计算机程序加工处理的原料。 2. 数据元素(Data Element)数据元素——是数据的基本单位, 在计算机中通常作为一个整体进行考 虑和处理。 eg:学生信息检索系统 3. 数据项(Data Item) 数据项------具有独立含义

《数据结构(C语言描述)》

21世纪高等院校规划教材 数据结构(C语言描述)

ISDN 7-5084-3301-7 斯庆巴拉 主编 中国水利水电出版社

《数据结构(C语言描述)》

第一章 学习数据结构课程的意义学习重点 掌握学习本课程的意义 掌握本课程的主体框架和讨论范围 掌握如何对算法进行描述和分析

《数据结构(C语言描述)》

引入：一般情况下，用计算机解决一 个实际问题时，都是先对具体问题抽 象，建立问题的求解模型，然后设计 相应的算法，编写程序并上机调试， 最后解决问题。

《数据结构(C语言描述)》

1.1 实例：高校选修课程管理 1.2 数据结构的主要内容 1.3 算法和算法分析

本章总结

《数据结构(C语言描述)》

1.1 实例：高校选修课程管理1.1.1 问题描述 1.1.2 问题的分析 1.1.3 学习本课程的意义

《数据结构(C语言描述)》

1.1.1 问题描述表1-1是一所学校学生选修课程的选 修情况登记表。要求用计算机来完成对 学生选修课程的全程管理。 通常必备的功能有登记，修改、查 询和打印等。在本例中重点完成查询功 能。

《数据结构(C语言描述)》

表1-1 某学校学生选修课程情况登记表选修课程名 学号 姓名 系别 课程名 0

第四章 串

一、选择题

1．下面关于串的的叙述中，哪一个是不正确的？（ ）【北方交通大学 2001 一、5（2分）】

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（ ）【北方交通大学 1999 一、5 （25/7分）】

A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234

3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A．求子串 B．联接 C．匹配 D．求串长 【北京邮电大学

第一章 绪论 一、选择题

1．数据结构是一门研究非数值计算的程序设计问题中计算机的⑴以及它们之间的⑵和运算等的学科。 ⑴A操作对象 B计算方法 C逻辑存储 D数据映像

⑵A结构 B关系 C运算 D算法 2．数据结构被形式定义为（K，R），其中K是⑴的有限集，R是K上的⑵有限集。 ⑴A算法 B数据元素 C数据操作 D逻辑结构 ⑵A操作 B映象 C存储 D关系 3．在数据结构中，从逻辑上可以把数据结构分成⑴。 A动态结构和表态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构

4．线性结构的顺序存储结构是一种⑴的存储结构，线性表的链式存储结构是一种⑵的存储结构。 ⑴A随机存取 B顺序存取 C索引存取 D散列存取 ⑵A随机存取 B顺序存取 C索引存取 D散列存取 5．算法分析的目的是⑴，算法分析的两个主要方面是⑵。 ⑴A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性 ⑵A空间复杂度和时间复杂度，正确性和简单性 B可读性和文档性 C数据复杂性和程序复杂性 6