数据结构1
- 格式:doc
- 大小:29.50 KB
- 文档页数:2
数据结构(一)目录第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(总分:100.00,做题时间:90分钟)一、单项选择题(总题数:25,分数:74.00)1.在下列关于线性表的叙述中,正确的是______。
(分数:2.00)A.线性表的逻辑顺序与物理顺序总是一致的B.线性表的顺序存储表示优于链式存储表示C.线性表若采用链式存储表示时,所有存储单元的地址可连续也可不连续D.每种数据结构都应具备三种基本运算:插入、删除和查找√解析:[解析] 本题主要考查线性结构的特点和线性表的定义。
线性表的顺序存储与链式存储在不同的情况下各有利弊,无优劣之分。
链式存储表示要求结点内的存储单元一定连续。
2.在线性表中的每一个表元素都是数据对象,它们是不可再分的______。
(分数:2.00)A.数据项B.数据记录C.数据元素√D.数据字段解析:[解析] 线性表是n(n≥0)个数据元素的有限序列。
数据记录、数据字段是数据库文件组织中的术语。
数据项相当于数据元素中的属性。
本题考查的依然是线性表的基本定义。
3.对于顺序存储的线性表,其算法的时间复杂度为O(1)的运算应是______。
(分数:2.00)A.将n个元素从小到大排序B.从线性表中删除第i个元素(1≤i≤n)C.查找第i个元素(1≤i≤n)√D.在第i个元素后插入一个新元素(1≤i≤n)解析:[解析] 在顺序存储的线性表中查找第i个元素时可直接访问。
4.下面的叙述正确的是______。
(分数:2.00)A.线性表在链式存储时,查找第i个元素的时间同i的值无关B.线性表在链式存储时,查找第i个元素的时间同i的值成反比C.线性表在顺序存储时,查找第i个元素的时间同i的值成正比D.线性表在顺序存储时,查找第i个元素的时间同i的值无关√解析:[解析] 本题主要考查的知识点是顺序存储结构和链式存储结构中查找一个元素的时间复杂度。
顺序存储的主要优点:可以随机存取表中任一元素,因此,查找第i个元素的时间同i的值无关。
第 1 章 绪 论1.1 数据结构的兴起和发展一、数据结构起源于程序设计。
·程序设计的新问题:应如何组织待处理的数据以及数据之间的关系(结构)。
·70年代初,数据结构作为一门独立的课程开始进入大学课堂。
二、数据结构随着程序设计的发展而发展。
程序设计经历了三个阶段:无结构阶段、结构化阶段和面向对象阶段,相应地,数据结构的发展也经历了三个阶段:三、数据结构的发展并未终结。
1. 数据结构将继续随着程序设计的发展而发展;2. 面向各专门领域的数据结构得到研究和发展,各种空间数据结构也在探索中。
应用领域:科学计算;程序设计面向计算机 应用领域:科学计算与非数值处理;算法+数据结构=程序 应用领域:更多地应用于非数值处理;(算法+数据结构)=程序1.2 数据结构的研究对象例1-1 学籍管理问题例1-2 人——机对弈问题例1-3 教学计划编排问题表1-1 学生学籍登记表 (a) 井字棋的一个格局 (b) 对弈树的局部 图1-2 对弈问题中格局之间的关系1.3 数据结构的基本概念1.3.1 数据结构1. 数据:在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。
2. 数据元素:是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
构成数据元素的不可分割的最小单位称为数据项。
3. 数据对象:是具有相同性质的数据元素的集合,是数据的子集。
4. 数据结构:是指相互之间存在一定关系的数据元素的集合。
按照视点的不同,数据结构分为逻辑结构和存储结构。
数据的逻辑结构是指数据元素之间逻辑关系的整体。
根据数据元素之间逻辑关系的不同,数据结构分为四类:⑴集合数据元素之间的关系是。
⑵线性结构数据元素之间的关系是。
⑶树结构数据元素之间的关系是。
⑷图结构数据元素之间的关系是。
数据的存储结构又称为物理结构,是数据及其逻辑结构在计算机中的表示。
有两种存储结构:顺序存储结构和链接存储结构。
1.在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为:【正确答案: C】A top不变B top=0C top--D top++得分:0.002.经过以下运算后,x的值是:InitStack (s); Push(s, a); Push(s, b); Pop(s, x); GetTop(s,x) 【正确答案: A】A aB 0C bD 1得分:0.003.元素A、B、C、D依次进栈后,栈顶元素是:【正确答案: B】A CB DC BD A得分:0.004.在带头节点的单链表L为空的判定条件是:【正确答案: A】A L->NEXT==NULLB L!=NULLC L->NEXT==LD L==NULL得分:0.005.将两个长度为n、m的递增有序表归并成一个有序顺序表,其最少的比较次数是(MIN表示取最小值):【正确答案: B】A nB MIN(m, n)C mD 不确定得分:0.006.如果最常用的操作时取第i个元素及前驱元素,则下列存储方式最节省时间是:【正确答案: A】A 顺序表B 循环单链表C 双链表D 单链表得分:0.007.线性表的顺序存储结构和链式存储结构相比,优点是:【正确答案: D】A 所有的操作算法实现简单B 便于插入和删除C 节省存储空间D 便于随机存取得分:0.008.最不合适用做链队的不带头节点的链表是:【正确答案: B】A 以上都不合适B 只带队首节点指针的非循环单链表C 只带队尾节点指针的循环双链表D 只带队首节点指针的循环双链表得分:0.009.带表头结点的双循环链表L为空表的条件是:【正确答案: C】A L->prior==NULLB L==NULLC L->next==LD L->next->prior==NULL得分:0.0010.在某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素。
第1章概论习题参考解答一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系,通常有下列4类:()、()、()、()。
【答】集合、线性结构、树型结构和图状结构。
2、数据的存储结构是数据在计算机存储器里的表示,主要有4种基本存储方法:()、()、()、()。
【答】顺序存储方法、链接存储方法、索引存储方法和散列存储方法。
二、选择题1、一个算法必须在执行有穷步之后结束,这是算法的()。
(A)正确性(B)有穷性(C)确定性(D)可行性【答】B。
2、算法的每一步,必须有确切的定义。
也就是说,对于每步需要执行的动作必须严格、清楚地给出规定。
这是算法的()。
(A)正确性(B)有穷性(C)确定性(D)可行性【答】C。
3、算法原则上都是能够由机器或人完成的。
整个算法好像是一个解决问题的“工作序列”,其中的每一步都是我们力所能及的一个动作。
这是算法的()。
(A)正确性(B)有穷性(C)确定性(D)可行性【答】D。
三、简答题1、算法与程序有何异同?【答】尽管算法的含义与程序非常相似,但两者还是有区别的。
首先,一个程序不一定满足有穷性,因此它不一定是算法。
例如,系统程序中的操作系统,只要整个系统不遭受破坏,它就永远不会停止,即使没有作业要处理,它仍处于等待循环中,以待一个新作业的进入。
因此操作系统就不是一个算法。
其次,程序中的指令必须是计算机可以执行的,而算法中的指令却无此限止。
如果一个算法采用机器可执行的语言来书写,那么它就是一个程序。
2、什么是数据结构?试举一个简单的例子说明。
【答】数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系(即数据元素的组织形式)。
例如,队列的逻辑结构是线性表(先进先出);队列在计算机中既可以采用顺序存储也可以采用链式存储;对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。
3、什么是数据的逻辑结构?什么是数据的存储结构?【答】数据元素之间的逻辑关系,也称为数据的逻辑结构。
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)。