数据结构考研分类复习真题 第一章 答案[6]

．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

[] [] [] [] [] [] [] [] []