数据结构常见笔试题汇总
需积分: 26 164 浏览量
2013-07-02
17:26:15
上传
评论 1
收藏 58KB DOC 举报
数据结构笔试题基础(一)
2008 年 03 月 28 日 星期五 下午 11:52
第一章 数据结构与算法
一.算法的基本概念
计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。
1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。
2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。
3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯
法。
4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求
二.算法的复杂度
1.算法的时间复杂度：指执行算法所需要的计算工作量
2.算法的空间复杂度：执行这个算法所需要的内存空间
三.数据结构的定义
1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的
逻辑结构包括集合、线形结构、树形结构和图形结构四种。
2.数据的存储结构：数据的逻辑结构在计算机存储空间种的存放形式称为数据
的存储结构。常用的存储结构有顺序、链接、索引等存储结构。
四.数据结构的图形表示：
在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。
插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复
制和修改等。
五.线性结构和非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为
两大类型：线性结构和非线性结构。
线性结构：非空数据结构满足：有且只有一个根结点；每个结点最多有一个前
件，最多只有一个后件。非线性结构：如果一个数据结构不是线性结构，称之
为非线性结构。
常见的线性结构：线性表、栈、队列
六.线性表的定义
线性表是 n 个元素构成的有限序列（A1，A2，A3……）。表中的每一个数据
元素，除了第一个以外，有且只有一个前件。除了最后一个以外有且只有一个
后件。即线性表是一个空表，或可以表示为（a1,a2,……an）, 其中
ai(I=1,2,……n)是属于数据对象的元素，通常也称其为线性表中的一个结点。
非空线性表有如下一些特征：
（1）有且只有一个根结点 a1,它无前件；
（2）有且只有一个终端结点 an，它无后件；
（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有
一个后件。线性表中结点的个数 n 称为线性表的长度。当 n=0 时称为空表。
七.线性表的顺序存储结构
线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元
素。
线性表的顺序存储结构具备如下两个基本特征：
剩余10页未读，继续阅读
资源评论
