西交《数据结构》faq（一）

Andy老师

西交《数据结构》FAQ（一）
第一章 绪论
1、什么是数据结构？
数据的组织形式。一门技术：着重存储结构。
“简单来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作的学科。”
一门课：着重逻辑结构
相互之间存在一种或多种特定关系的数据元素的集合。
是一种实用性很强的专业技术。
具体存储形式
线性 数组、串、表、队、栈
非线性 树、图
文件 非线性/线性  即可视为….又可视为….
2、数据结构有哪些内容？
数据结构一般包括以下三方面内容：
数据的逻辑结构：它从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
数据的存储结构：它是逻辑结构用计算机语言的实现，依赖于计算机语言。
数据的运算：即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
3、数据有哪几种存储方法？
1）顺序存储方法：主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。
2）链接存储方法：不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。
3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。
4）散列存储方法：该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址。
上面四种基本存储方法，即可单独使用，也可组合起来对数据结构进行存储映像。
4、数据的逻辑结构分为哪几类？
数据的逻辑结构分为 线性结构和非线性结构两类。
线性结构：其逻辑特征是，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。（栈、队列、串等都是线性结构）
非线性结构：其逻辑特征是，一个结点可能有多个直接前趋和直接后继。（数组、广义表、树和图等数据结构都是非线性结构）
5、数据结构三方面的关系？
数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。存储结构是数据结构不可缺少的一个方面，同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。
6、什么是算法? 算法的5个特性是什么?
通常，定义算法为"为解决某一特定任务而规定的一个指令序列"。
一个算法应当具有以下特性：
① 有输入。一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。这些输入取自
于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内
给定。
② 有输出。一个算法应有一个或多个输出，输出的量是算法计算的结果。
③ 确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、
清晰地规定。
④ 有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。
⑤ 有效性。算法中每一条运算都必须是足够基本的。就是说，它们原则上都能精确地执行，甚至人们
仅用笔和纸做有限次运算就能完成。
7、什么是好的算法设计？
好的算法设计应考虑到下面问题：
程序需要原始任务说明？
程序工作正确？
程序包含方案如何使用及方案如何解题？
程序有效的利用了函数来建立逻辑单元？
程序的代码是可读的？
程序有效的利用了内存和外存？
解决问题的程序运行时间可接受？
8、好的程序有哪些标准？
计算机科学的核心是算法。名人所言
计算机科学工作者要与程序打交道。必然事实
过去，软件/程序以存储省、速度快为目标。
现在，则以正确、易懂、易修改、易测试为标准。
9、数据结构的重要性
专业核心课之一。
软/硬件应用的基础。用计算机者皆须先修此课！考研必修课！68年，国外开始出现此课。78年，交大开设此课。本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986