数据结构知识点复习资料

数据结构复习资料一、填空题1、 数据结构就是一门讨论非数值计算得程序设计 问题中计算机得 操作对象 以及它们之间得 关系 与 运 算 等得学科.2、 数据结构被形式地定义为(Ｄ, R),其中 D 就是 数据元素 得有限集合，R 就是 D 上得 关系 有限集合。3、 数据结构包括数据得 逻辑结构 、数据得 存储结构 与数据得 运算 这三个方面得内容。4、 数据结构按逻辑结构可分为两大类,它们分别就是 线性结构 与 非线性结构 。5、 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系.6。 在线性结构中,第一个结点 没有 前驱结点，其余每个结点有且只有 1 个前驱结点;最后一个结点 没有 后续结点,其余每个结点有且只有 1 个后续结点。7、 在树形结构中,树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点,其余每个结点得后续结点数可以任意多个 。8、 在图形结构中，每个结点得前驱结点数与后续结点数可以 任意多个 。9。数据得存储结构可用四种基本得存储方法表示，它们分别就是顺序 、 链式 、 索引 与 散列 .10、 数据得运算最常用得有５种,它们分别就是插入 、 删除、修改、 查找 、排序。11、 一个算法得效率可分为 时间 效率与 空间 效率。12、 在顺序表中插入或删除一个元素,需要平均移动 表中一半元素，具体移动得元素个数与 表长与该元素在表中得位置 有关．13、 线性表中结点得集合就是 有限 得,结点间得关系就是 一对一 得。14、 向一个长度为 n 得向量得第 i 个元素(１≤i≤n＋1)之前插入一个元素时,需向后移动 n-i+1 个元素。15、 向一个长度为 n 得向量中删除第 i 个元素(１≤i≤ｎ)时，需向前移动 n— ｉ 个元素。16、 在顺序表中访问任意一结点得时间复杂度均为 O(1) ,因此,顺序表也称为 随机存取 得数据结构.17、 顺序表中逻辑上相邻得元素得物理位置 必定相邻．单链表中逻辑上相邻得元素得物理位置 不一定 相邻。18。在单链表中，除了首元结点外，任一结点得存储位置由 其直接前驱结点得链域得值 指示.19。 在 n 个结点得单链表中要删除已知结点＊p，需找到它得前驱结点得地址,其时间复杂度为 O(n)。20、 向量、栈与队列都就是 线性 结构,可以在向量得 任何 位置插入与删除元素；对于栈只能在 栈顶 插入与删除元素;对于队列只能...