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

O(n)

① () () ()f(mn) ()n ②

n(n)/

四．应用题

．数据结构是一门研究在非数值计算的程序设计问题中计算机的操作对象及对象间的关系和施加于对象的操作等的学科

．四种表示方法

（）顺序存储方式数据元素顺序存放每个存储结点只含一个元素存储位置反映数据元素间的逻辑关系存储密度大但有些操作（如插入删除）效率较差

（）链式存储方式每个存储结点除包含数据元素信息外还包含一组（至少一个）指针指针反映数据元素间的逻辑关系这种方式不要求存储空间连续便于动态操作（如插入删除等）但存储空间开销大（用于指针）另外不能折半查找等

（）索引存储方式除数据元素存储在一地址连续的内存空间外尚需建立一个索引表索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）兼有静态和动态特性

（）散列存储方式通过散列函数和解决沖突的方法将关键字散列在连续的有限的地址空间内并将散列函数的值解释成关键字所在元素的存储地址这种存储方式称为散列存储其特点是存取速度快只能按关键字随机存取不能顺序存取也不能折半存取

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