数据结构第一章 绪论答案[2]

()逻辑结构相同但存储不同可以是不同的数据结构例如线性表的逻辑结构属于线性结构采用顺序存储结构为顺序表而采用链式存储结构称为线性链表

()栈和队列的逻辑结构相同其存储表示也可相同(顺序存储和链式存储)但由于其运算集合不同而成为不同的数据结构

()数据结构的评价非常复杂可以考虑两个方面一是所选数据结构是否准确完整的刻划了问题的基本特征;二是是否容易实现(如对数据分解是否恰当;逻辑结构的选择是否适合于运算的功能是否有利于运算的实现;基本运算的选择是否恰当)

评价好的算法有四个方面一是算法的正确性;二是算法的易读性;三是算法的健壮性;四是算法的时空效率(运行)

()见上面题 ()见上面题 ()见上面题

()算法的时间复杂性是算法输入规模的函数算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目或与此数目有关的其它参数有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度

()算法是对特定问题求解步骤的描述是指令的有限序列其中每一条指令表示一个或多个操作算法具有五个重要特性有穷性确定性可行性输入和输出

()频度在分析算法时间复杂度时有时需要估算基本操作的原操作它是执行次数最多的一个操作该操作重复执行的次数称为频度

集合线性结构树形结构图形或网状结构 逻辑结构存储结构操作(运算)

通常考虑算法所需要的存储空间量和算法所需要的时间量后者又涉及到四方面程序运行时所需输入的数据总量对源程序进行编译所需时间计算机执行每条指令所需时间和程序中指令重复执行的次数

D是数据元素的有限集合S是D上数据元素之间关系的有限集合

数据结构这一术语有两种含义一是作为一门课程的名称;二是作为一个科学的概念作为科学概念目前尚无公认定义一般认为讨论数据结构要包括三个方面一是数据的逻辑结构二是数据的存储结构三是对数据进行的操作(运算)而数据类型是值的集合和操作的集合可以看作是已实现了的数据结构后者是前者的一种简化情况

见上面题

将学号姓名平均成绩看成一个记录(元素含三个数据项)将个这样的记录存于数组中因一般无增删操作故宜采用顺序存储

typedef struct

{int num;//学号

char name[];//姓名

float score;/平均成绩

}node;

node student[];

见上面题()

应从两方面进行讨论如通讯录较少变动(如城市私人电话号码)主要用于查询以顺序存储较方便既能顺序查找也可随机查找;若通讯录经常有增删操作用链式存储结构较为合适将每个人的情况作为一个元素(即一个结点存放一个人)设姓名作关键字链表安排成有序表这样可提高查询速度

线性表中的插入删除操作在顺序存储方式下平均移动近一半的元素时间复杂度为O(n);而在链式存储方式下插入和删除时间复杂度都是O()

对算法A和A的时间复杂度T和T取对数得nlog和logn显然算法A好于A

struct node

{int yearmonthday; };

typedef struct

{int num;//帐号

char name[];//姓名

struct node date;//开户年月日

int tag;//储蓄类型如 零存 一年定期……

float put;//存入累加数;

float interest;//利息

float total;//帐面总数

}count;

()n ()n+ ()n ()(n+)(n)/ ()(n+)(n)/ ()n

[] [] []