下载文档原格式
数据结构(一)目录第1章序论 (1)1.1 什么是数据? (1)1.2 什么是数据元素? (1)1.3 什么是数据结构及种类? (1)1.4 数据的逻辑结构 (1)1.5 数据的物理结构 (1)1.6 算法和算法分析 (1)1.7 算法的五个特性 (1)1.8 算法设计的要求 (2)1.9 算法效率的度量 (2)第2章线性表 (3)2.1 线性表举例 (3)2.2 线性表的存储 (4)2.3 线性表-栈 (4)2.4 队列 (4)2.5 双端队列 (6)第3章树和二叉树 (6)3.1 树 (6)3.1.1 树的基本概念 (6)3.1.2 树的常用存储结构 (6)3.1.3 树的遍历 (7)3.2 二叉树 (7)3.2.1 二叉树的基本概念 (7)3.2.2 二叉树与树的区别 (7)3.2.3 树及森林转到二叉树 (7)3.2.4 二叉树的性质 (8)3.2.5 满二叉树 (8)3.2.6 完全二叉树 (8)3.2.7 完全二叉树的性质 (9)3.2.8 二叉树的四种遍历 (9)3.2.9 二叉排序树 (10)3.2.10 平衡二叉树 (11)3.2.11 m阶B-树 (11)3.2.12 最优二叉树 (11)3.2.13 二叉树的存储结构 (12)3.3 广义表 (13)3.4 矩阵的压缩存储 (14)3.4.1 特殊矩阵 (14)3.4.2 压缩存储 (14)第4章历年真题讲解 (15)4.1 2009年上半年 (15)4.2 2009年下半年 (15)4.3 2010年上半年 (15)4.4 2011年上半年 (16)4.5 2011年下半年 (16)4.6 2012年上半年 (17)4.7 2012年下半年 (17)4.8 2013年上半年 (18)4.9 2013年下半年 (18)4.10 2014年上半年 (18)4.11 2014年下半年 (19)4.12 2015年上半年 (19)4.13 2015年下半年 (19)4.14 2016年上半年 (20)第1章序论什么是数据?所有能输入到计算机中并能够被计算机程序处理的符号的总称,它是计算机程序加工的原料。
一、填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。
02、数据结构被形式地定义为(D,R)，其中D是(数据元素)的有限集合，R是D上的(关系)有限集合。
03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。
04、数据结构按逻辑结构可分为两大类，它们分别是(线性结构)和(非线性结构)。
05、线性结构中元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中元素之间存在(多对多)关系。
06、在线性结构中，第一个结点(没有)前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点(没有)后续结点，其余每个结点有且只有1个后续结点。
07、在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(1)个前驱结点；叶子结点没有(后续)结点，其余每个结点的后续结点数可以(任意多个)。
08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个)。
09、数据的存储结构可用四种基本的存储方法表示，它们分别是(顺序)、(链式)、(索引)、(散列)。
10、对于给定的n个元素，可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。
11、数据的运算最常用的有5种，它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。
12、一个算法的效率可分为(时间)效率和(空间)效率。
13、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。
14、一个数据结构在计算机中的(映射)称为存储结构。
15、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。
16、已知如下程序段for (i=n; i>=1; i--) //语句1{ x++; //语句2for (j=n; j>=i; j--) //语句3y++; //语句4}语句 1 执行的频度为(n+1)；语句2执行的频度为(n)；语句3执行的频度为(n(n+3)/2)；语句4执行的频度为(n(n+1)/2)。
数据结构-1(总分100,考试时间90分钟)一、单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的1. 设数组data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为( )A. front:=front+1B. front:=(front+1)mod mC. rear:=(rear+1)mod mD. front:=(front+1)mod(m+1)2. 在Hash函数H(k)=k MOD m中，一般来讲，m应取( )A. 奇数B. 偶数C. 素数D. 充分大的数3. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用( )存储结构。
A. 二叉链表B. 广义表C. 三叉链表D. 顺序4. 向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为( )A. Top—＞next=s;B. s—＞next=Top—＞next;Top—＞next=s;C. s—＞next=Top;top=s;D. s—＞next=Top; Top=Top—＞next;5. 快速排序在最坏情况下的时间复杂度是( )A. O(nlogB. O(n2)C. O(n3)D. 都不对6. 内部排序的方法有许多种，( )方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。
A. 归并排序B. 插入排序C. 快速排序D. 选择排序7. 对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是( )A. (N-1)×(N-1)B. N×NC. (N+1)×(N+1)D. 不确定8. 在一个长度为n的顺序表(顺序存储的线性表)中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动( )个元素。
A. n-iB. n-i+1C. n-i-1D. i9. 下面四种排序方法中，平均查找长度最小的是( )A. 插入排序B. 选择排序C. 快速排序D. 归并排序10. 如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高h≥2)。
1.1 请说明算法具有哪些特性，各是什么含义？
算法的一般性质包括：（1）通用性对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的正确性.（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的.（3）确定性算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.（4）有穷性算法的执行必须在有限步内结束.
1.2简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类
型和抽象数据类型。
数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。
数据元素（data element）：数据集合中的一个实体，是计算机程序中加工处理的基本单位。
例如：一条学生记录（包括学号、姓名、年龄等）就是一个数据元素数据对象（data object）：性质相同的数据元素的集合。
是数据的一个子集。
数据结构(data structure)：相互之间存在一种或多种关系的数据元素的集合。
即包括数据元素的集合和数据元素之间的关系的集合。
存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。
又称为存储结构。
数据类型（data type）:是一个“值”的集合和定义在此集合上的“一组操作”的总称。
抽象数据类型（abstract data type，简称ADT）：是指一个数学模型以及定义在此数学模型上的一组操作。
1.3设n为正整数。
试确定下列各程序段中前置以记号@的语句频度：
(1) x=n; y=0; //n为不小于1的常数
while (x>=(y+1)*(y+1)) {
@ y++;
}
n1/2向下取整
(2) i=1; j=0;
while (i+j<=n) {
@ if (i>j) j++;
else i++;
}
n
注：@语句指的是if…else语句，语句频度为j++和i++执行的次数之和。
1.4请说明下列算法的时间复杂度。
(1) void sf1 (int n)
{ int i, x=0;
for(i=1; i<n+1; i++)
for(j=1; j<=8; j++)
x+=2;
}
(2) void sf2 (int n, int m)
{ for (i=0; i<m; i++)
for(j=0; j<n; j++)
x++;
}
1.1算法的一般性质包括：
（1）通用性对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的正确性.
（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的. （3）确定性算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.
（4）有穷性算法的执行必须在有限步内结束.
1.2
数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。
数据元素（data element）：数据集合中的一个实体，是计算机程序中加工处理的基本单位。
例如：一条学生记录（包括学号、姓名、年龄等）就是一个数据元素数据对象（data object）：性质相同的数据元素的集合。
是数据的一个子集。
数据结构(data structure)：相互之间存在一种或多种关系的数据元素的集合。
即包括数据元素的集合和数据元素之间的关系的集合。
存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。
又称为存储结构。
数据类型（data type）:是一个“值”的集合和定义在此集合上的“一组操作”的总称。
抽象数据类型（abstract data type，简称ADT）：是指一个数学模型以及定义在此数学模型上的一组操作。
1.3
(1) n1/2向下取整
(2) n
1.4
(1) o(8*n) 去常数项就是o(n)
(2) o（m*n）。
