第1章 数据结构与算法
1.1 算法
1.1.1算法的基本概念
所谓算法是指解题
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
的准确而完整的描述。
算法并不等于程序。
54_5问题处理方案的正确而完整的描述称为 【5】 。
算法
1.算法的基本特征
作为一个算法,一般应具有以下几个基本特征。
(l)可行性(effectiveness)
得到满意的结果
(2)确定性(definiteness)
算法中的每一个步骤都必须是有明确定义的
(3)有穷性(finiteness)
在有限的时间内做完
(4)拥有足够的信息
一为算法所提供的信息是否足够(有输入输出)
3.1.84_5)算法的有穷性是指
A 算法程序的运行时间是有限的
B 算法程序所处理的数据量是有限的
C 算法程序的长度是有限的
D 算法只能被有限的用户使用
2.算法的基本要素
一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构。
(1)算法中对数据的运算和操作
基本的运算和操作有以下四类:
①算术运算:主要包括加、减、乘、除等运算。
②逻辑运算:主要包括“与”、“或”、“非”等运算。
③关系运算:主要包括“大于”、“小于”、“等于”、“不等于”等运算。
④数据传输:主要包括赋值、输入、输出等操作。
(2)算法的控制结构
可以用顺序、选择、循环三种基本控制结构组合而成。
3.算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
基本方法
(1)列举法
(2)归纳法
(3)递推
(4)递归
递归分为直接递归与间接递归两种。如果一个算法P显式地调用自己则称为直接递归。如果算法P调用另一个算法Q,而算法Q又调用算法P,则称为间接递归调用。
(5)减半递推技术
(6)回溯法
1.1.2算法的复杂度
算法的复杂度主要包括时间复杂度和空间复杂度。
1、算法的时间复杂度
所谓算法的时间复杂度,是指执行算法所需要的计算工作量。
用基本运算的次数来度量算法工作量
1.算法的时间复杂度是指 ( c )
A)执行算法程序所需要的时间
B)算法程序的长度
C)算法执行过程中所需要的基本运算次数
D)算法程序中的指令条数
103_2)算法的时间复杂度是指
a)算法的执行时间
b)算法所处理的数据量
c)算法程序中的语句或指令条数
d)算法在执行过程中所需要的基本运算次数
d
算法所执行的基本运算次数还与问题的规模有关
算法的工作量 = f(n) 其中n是问题的规模
对于一个固定的规模,算法所执行的基本运算次数还可能与特定的输入有关。
在同一个问题规模下,如果算法执行所需的基本运算次数取决于某一特定输入时,可以用以下两种方法来分析算法的工作量。
(l)平均性态(Average Behavior)
(2)最坏情况复杂性(Worst-Case Complexity)
W(n)的计算要比A(n)的计算方便得多。由于W(n)实际上是给出了算法工作量的一个上界,因此,它比A(n)更具有实用价值。
2、算法的空间复杂度
一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。
2算法的空间复杂度是指 ( d )
A)算法程序的长度
B)算法程序中的指令条数
C)算法程序所占的存储空间
D)算法执行过程中所需要的存储空间
69_7)下列叙述中正确的是
A)一个算法的空间复杂度大,则其时间复杂度也必定大
B)一个算法的空间复杂度大,则其时间复杂度必定小
C)一个算法的时间复杂度大,则其空间复杂度必定小
D)上述三种说法都不对
69_1算法复杂度主要包括时间复杂度和 【2】 复杂度。
99_4. 算法的空间复杂度是指( )。
A.算法在执行过程中所需要的计算机存储空间
B.算法所处理的数据量
C.算法程序中的语句或指令条数
D.算法在执行过程中所需要的临时工作单元数
答案 A
解析:算法的空间复杂度是指执行算法所需要的内存空间,包括算法程序所占空间,输入的初始数据所占空间和执行过程中所需要的额外空间.
1.2 数据结构的基本概念
数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题:
①数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构。
②在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。
③对各种数据结构进行的运算。
(操作后应保持原有结构不被破坏)
1.2.1 什么是数据结构
35
16
78
85
43
29
33
21
54
46
16
21
29
33
35
43
46
54
78
85
简单地说,数据结构是指相互有关联的数据元素的集合。
数据元素具有广泛的含义。一般来说,现实世界中客观存在的一切个体都可以是数据元素。
数据元素一般具有某种共同特征。
在数据处理领域中,通常把数据元素之间这种固有的关系简单地用前后件关系(或直接前驱与直接后继关系)来描述。
1.数据的逻辑结构
一个数据结构应包含以下两方面的信息:
①表示数据元素的信息;
②表示各数据元素之间的前后件关系。
在以上所述的数据结构中,其中数据元素之间的前后件关系是指它们的逻辑关系,而与它们在计算机中的存储位置无关。因此,上面所述的数据结构实际上是数据的逻辑结构。
2.数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。
54_1数据的存储结构是指
A) 存储在外存中的数据
B) 数据所占的存储空间量
C) 数据在计算机中的顺序存储方式
D) 数据的逻辑结构在计算机中的表示
4 数据的存储结构是指 (b )
A)数据所占的存储空间量
B)数据的逻辑结构在计算机中的表示
C)数据在计算机中的顺序存储方式
D)存储在外存中的数据
红60_20数据结构中,与所用的计算机无关的是数据的
A 存储结构
B 物理结构
C逻辑结构
D 物理和存储结构
62_14数据结构包括数据的 结构和数据的存储结构
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。
一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接。索引等存储结构。而采用不同的存储结构,其数据处理的效率是不同的。因此,在进行数据处理时,选择合适的存储结构是很重要的。
4.2.79_5下列叙述中正确的是
A程序执行的效率与数据的存储结构密切相关
B程序的执行效率只取决于程序的控制结构
C程序执行的效率只取决于所处理的数据量
D以上三种说法都不对
4.3.79_6下列叙述中正确的是
A数据的逻辑结构与存储结构必定是一一对应的
B由于计算机存储空间是向量式的存储结构,因此,数据的存储结构一定是线性结构
C程序设计语言中的数组一般是顺序存储结构,因此,利用数组只能处理线性结构
D以上三种说法都不对
红57_2下面的叙述正确的是
A 算法的执行效率与数据的存储结构无关
B 算法的空间复杂度是指算法程序中指令(或语句)的条数
C算法的有穷性是指算法必须能在执行有限个步骤之后终止
D以上三种描述都不对
59_4下列叙述中正确的是
A) 一个逻辑数据结构只能有一种存储结构
B) 数据的逻辑结构属于线性结构,存储结构属于非线性结构
C) 一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率
D) 一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率
1.2.2 数据结构的图形表示
在数据结构中,没有前件的结点称为根结点;没有后件的结点称为终端结点(也称为叶子结点)。数据结构中除了根结点与终端结点外的其他结点一般称为内部结点。
在对数据结构的处理过程中,不仅数据结构中的结点(即数据元素)个数在动态地变化,而且,各数据元素之间的关系也有可能在动态地变化。
1.2.3 线性结构与非线性结构
如果一个非空的数据结构满足下列两个条件:
①有且只有一个根结点;
②每一个结点最多有一个前件,也最多有一个后件。
则称该数据结构为线性结构。线性结构又称线性表。
在一个线性结构中插入或删除任何一个结点后还应是线性结构。
如果一个数据结构不是线性结构,则称之为非线性结构。
一个空的数据结构究竟是属于线性结构还是属于非线性结构,这要根据具体情况来确定。如果对该数据结构的运算是按线性结构的
规则
编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf
来处理的,则属于线性结构;否则属于非线性结构。
1.3 线性表及其顺序存储结构
由若干数据项组成的数据元素称为
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
(record)。可以表示为
(a1,a2,…,ai,…,an)
其中 (ai=1,2,…,n)是属于数据对象的元素,通常也称其为线性表中的一个结点。
线性表中结点的个数n称为线性表的长度。当n=0时,称为空表。
1.3.2线性表的顺序存储结构
线性表的顺序存储结构具有以下两个基本特点:
①线性表中所有元素所占的存储空间是连续的;
②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
红62_22
顺序存储方法是把相邻的结点存储在物理位置 的存储单元中. 相邻
优点:便于查找元素
缺点:做插入删除操作时需要移动元素
1.3.3 顺序表的插入运算
在一般情况下,要在第i(1≤ i≤n)个元素之前插入一个新元素时,首先要从最后一个(即第n个)元素开始,直到第i个元素之间共n十l个元素依次向后移动一个位置,移动结束后,第i个位置就被空出,然后将新元素插入到第i项。插入结束后,线性表的长度就增加了1。
29
18
56
63
35
24
31
47
29
18
56
63
35
24
31
47
29
87
18
56
63
35
24
31
14
47
l.3.4 顺序表的删除运算
在一般情况下,要删除第i (1≤ i≤n)个元素时,则要从第 i+1个元素开始,直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后,线性表的长度就减小了1。
29
18
56
63
35
24
47
29
18
56
63
35
24
31
47
18
56
63
35
24
31
47
6.1.89_4)下列叙述中正确的是( )。
A)顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的
B)顺序存储结构只针对线性结构,链式存储结构只针对非线性结构
C)顺序存储结构能存储有序表,链式存储结构不能存储有序表
D)链式存储结构比顺序存储结构节省存储空间
109_1下列叙述中正确的是
A) 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B) 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C) 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D) 上述三种说法都不对
B
1.4 栈和队列
1.4.1 栈及其基本运算
1.什么是栈
栈是一种特殊的线性表。其插入与删除运算都只在线性表的一端进行。
栈(stack)是限定在一端进行插入与删除的线性表。
在栈中,允许插入与删除的一端称为栈顶,而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,从而也是最先能被删除的元素:栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。即栈是按照"先进后出"(FILO--First In Last Out)或"后进先出"(LIFO-Last In First Out)的
原则
组织架构调整原则组织架构设计原则组织架构设置原则财政预算编制原则问卷调查设计原则
组织数据的,因此,栈也被称为"先进后出"表或"后进先出"表。
6 下列关于栈的叙述中正确的是 ( d )
A)在栈中只能插入数据
B)在栈中只能删除数据
C)栈是先进先出的线性表
D)栈是先进后出的线性表
59_3下列关于栈的描述正确的是
A) 在栈中只能插入元素而不能删除元素
B) 在栈中只能删除元素而不能插入元素
C) 栈是特殊的线性表,只能在一端插入或删除元素
D) 栈是特殊的线性表,只能在一端插入元素,而在另一端删除元素
样1下列关于栈的叙述正确的是
A栈是非线性结构
B栈是一种树状结构
C栈具有先进先出的特征
D栈具有后进先出的特征
64_4)按照“后进先出”原则组织数据的数据结构是
A)队列 B)栈
C)双向链表 D)二叉树
99_2. 下列数据结构中,能够按照”先进后出”原则存取数据的是( )。
A. 循环队列 B.栈 C.队列 D.二叉树
答案 B
解析:栈是先进后出或后进先出的线性表
9.2.69_4)按“先进后出”原则组织数据的数据结构是_______。
84_7)下列关于栈的叙述正确的是
A 栈按“先进先出”组织数据 B 栈按“先进后出”组织数据
C 只能在栈底插入数据 D 不能删除数据
通常用指针top来指示栈顶的位置,用指针bottom指向栈底。
往栈中插入一个元素称为入栈运算,从栈中删除一个元素(即删除栈顶元素)称为退栈运算。
栈的基本运算有三种:入栈、退栈与读栈顶元素。
(l)入栈运算
入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作:首先将栈顶指针进一(即top加1),然后将新元素插入到栈顶指针指向的位置。
当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间己满,不可能再进行入栈操作。这种情况称为栈"上溢"错误。
10
9
8
7
top6
F
5
E
4
D
3
C
2
B
botton1
A
10
9
8
top 7
X
6
F
5
E
4
D
3
C
2
B
botton1
A
10
9
top 8
Y
7
X
6
F
5
E
4
D
3
C
2
B
botton1
A
(2)退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作:首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量,然后将栈顶指针退一(即 top减 1)。
当栈顶指针为0时,说明栈空,不可能进行退栈操作。这种情况称为栈"下溢"错误。
(3)读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意,这个运算个删除栈顶元素,只是将它的值赋给一个变量,因此,在这个运算中,栈顶指针不会改变。
当栈顶指针为0时,说明栈空,读不到栈顶元素。
109_2)下列叙述中正确的是
A)在栈中,栈中元素随栈底指针与栈顶指针的变化而动态变化
B)在栈中,栈顶指针不变,栈中元素随栈底指针的变化而动态变化
C)在栈中,栈底指针不变,栈中元素随栈顶指针的变化而动态变化
D)上述三种说法都不对
C
8.1.89_1)一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈,然后再依次出栈,则元素出栈的顺序是()。
A)12345ABCDE B)EDCBA54321
C)ABCDE12345 D)54321EDCBA
109_1)一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈,然后退栈一次,再将元素A,B,C,D依次入栈,之后将所有元素全部退栈,则所有元素退栈(包括中间退栈的元素)的顺序为【1】。
1DCBA2345
红60_21栈底至栈顶依次存放元素ABCD,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是
A abced B dbcea C cdabe D dcbea
93_2)支持子程序调用的数据结构是
A)栈 B)树 C)队列 D)二叉树
A
93_1)假如用一个长度为50的数组(数组元素的下标从0到49)作为栈的存储空间,栈底指针bottom指向栈底元素,栈顶指针top指向栈顶元素,如bottom=49,top=30(数组下标),则栈中具有__【1】个元素。
20
1.4.2 队列及其基本运算
1.什么是队列
队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾,通常用一个称为尾指针(rear)的指针指向队尾元素,即尾指针总是指向最后被插入的元素;允许删除的一端称为排头(也称为队头),通常也用一个排头指针(front)指向排头元素的前一个位置。显然,在队列这种数据结构中,最先插入的元素将最先能够被删除,反之,最后插入的元素将最后才能被删除。因此,队列又称为"先进先出"(FIFO——First In First Out)或"后进后出"(LILO——Last In Last Out)的线性表,它体现了"先来先服务"的原则。
A
B
C
D
E
F
Front rear
5 下列关于队列的叙述中正确的是 ( c )
A)在队列中只能插入数据
B)在队列中只能删除数据
C)队列是先进先出的线性表
D)队列是先进后出的线性表
9.4.74_5)下列对队列的叙述正确的是
A)队列属于非线性表
B)队列按“先进后出”原则组织数据
C)队列在队尾删除数据
D)队列按“先进先出”原则组织数据
往队列的队尾插入一个元素称为入队运算,从队列的排头删除一个元素称为退队运算。
在队列的末尾插入一个元素(入队运算)只涉及队尾指针rear的变化,而要删除队列中的排头元素(退队运算)只涉及排头指针front的变化。
103_1)一个队列的初始状态为空。现将元素a,b,c,d,e,f,5,4,3,2,1依次入队,然后再依次退队,则元素退队的顺序为 【1】 。a,b,c,d,e,f,5,4,3,2,1
62_17 栈和队列的共同点是
A 都是先进后出
B都是先进先出
C只允许在端点处插入和删除元素
D没有共同点
2.循环队列及其运算
所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。
9.2.89_2)下列叙述中正确的是( )。
A)循环队列有队头和队尾两个指针,因此,循环队列是非线性结构
B)在循环队列中,只需要队头指针就能反映队的中元素的动态变化情况
C)在循环队列中,只需要队尾指针就能反映队的中元素的动态变化情况
D)循环队列中元素的个数是由队头指针和队尾指针共同决定
D
99_3. 对于循环队列,下列叙述中正确的是( )。
A.队头指针是固定不变的
B.队头指针一定大于队尾指针
C.队头指针一定小于队尾指针
D.队头指针可以大于队尾指针,也可以小于队尾指针
答案 D
解析:如果队头指针大于队尾指针说明队列已经循环存放数据了,如果队头指针小于队尾指针说明没有进行循环存放
59_5数据结构分为逻辑结构和存储结构,循环队列属于 【5】 结构。
9.1.79_三线性表的存储结构主要分为顺序存储结构和链式存储结构.队列是一种特殊的线性表,循环队列是队列的顺序存储结构
93_1)下面叙述中正确的是
A)栈是“先进先出”的线性表
B)队列是“先进后出”的线性表
C)循环队列是非线性结构
D)有序线性表既可以采用顺序存储结构,也可以采用链式存储结构
D
5.在一个容量为15的循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有 3 个元素。
84_3)设某循环队列的容量为50,头指针front=5(指向队头元素的前一位置),尾指针rear=29(指向队尾元素),则该循环队列中共有___[3]____个元素。24
103_2)设某循环队列的容量为50,如果头指针front=45(指向队头元素的前一位置),尾指针rear=10(指向队尾元素),则该循环队列中共有 【2】 个元素。
15
循环队列主要有两种基本运算:入队运算与退队运算。
每进行一次入队运算,队尾指针就进一。当队尾指针rear=m+l时,则置rear=l。
每进行一次退队运算,排头指针就进一。当排头指针front=m+l时,则置front=l。
在循环队列中,当front=rear时,不能确定是队列满还是队列空。在实际使用循环队列时,为了能区分队列满还是队列空,通常还需增加一个标志S,S值的定义如下:
由此可以得出队列空与队列满的条件如下:
队列空的条件为S=0;
队列满的条件为s=1且front=rear。
(1)入队运算
入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作:首先将队尾指针进一(即 rear=rear+l),并当rear=m+l时置rear=l;然后将新元素插入到队尾指针指向的位置。
当循环队列非空(S=l)日队尾指针等于排头指针时,说明循环队列已满,不能进行入队运算,这种情况称为"上溢"。
(2)退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。这个运算有两个基本操作:首先将排头指针进一(即ront=front+l),并当front=m+l时置ontel;然后将排头指针指向的元素赋给指定的变量。
当循环队列为空(S=0)时,不能进行退队运算,这种情况称为"下溢"。
1.5 线性链表
1.5.1线性链表的基本概念
由于线性表的顺序存储结构存在以上这些缺点,因此,对于大的线性表,特别是元素变动频繁的大线性表不宜采用顺序存储结构,而是采用下面要介绍的链式存储结构。
假设数据结构中的每一个数据结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。
在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。
在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构。也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时,其指针域的个数要多一些。
l.线性链表
线性表的链式存储结构称为线性链表。
在线性链表中,用一个专门的指针HEAD指向线性链表中第一个数据元素的结点(即存放线性表中第一个数据元素的存储结点的序号)。线性表中最后一个元素没有后件,因此,线性链表中最后一个结点的指针域为空(用 NULL或 0表示),表示链表终止。
存储序号
数据域
指针域
V(i)
Next(i)
i
对于线性链表,可以从头指针开始,沿各结点的指针扫描到链表中的所有结点。
存储序号
数据域
指针域
Next(i)
i
1
A2
9
2
3
A1
1
4
5
A4
10
6
7
8
9
A3
5
10
A5
0
54_5下列对于线性链表的描述中正确的是
A) 存储空间不一定是连续,且各元素的存储顺序是任意的
B) 存储空间不一定是连续,且前件元素一定存储在后件元素的前面
C) 存储空间必须连续,且前件元素一定存储在后件元素的前面
D) 存储空间必须连续,且各元素的存储顺序是任意的
对线性链表中的每个结点设置两个指针,一个称为左指针(Llink),用以指向其前件结点;另一个称为右指针(Rlink),用以指向其后件结点。这样的线性链表称为双向链表。
2.带链的栈
栈也是线性表,也可以采用链式存储结构。
54_2下列关于栈的描述中错误的是
A) 栈是先进后出的线性表
B) 栈只顺序存储
C) 栈具有记忆作用
D) 对栈的插入与删除操作中,不需要改变栈底指针
3.带链的队列
与栈类似,队列也是线性表,也可以采用链式存储结构。
8.1.69_5)数据结构分为线性结构和非线性结构,带链的队列属于______。
1.5.2 线性链表的基本运算
1.在线性链表中查找指定元素
从头指针指向的结点开始往后沿指针进行扫描,直到后面已没有结点或下一个结点的数据域为x为止。因此,由这种方法找到的结点p有两种可能:当线性链表中存在包含元素x的结点时,则找到的p为第一次遇到的包含元素x的前一个结点序号;当线性链表中不存在包含元素x的结点时,则找到的p为线性链表中的最后一个结点号。
2.线性链表的插入
线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。
分配一个新的结点----查找指定位置-----插入结点
线性链表在插入过程中不发生数据元素移动的现象,只需改变有关结点的指针即可,从而提高了插入的效率。
3.线性链表的删除
线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点。
红61_25用链表表示线性表的优点是
A便于插入和删除操作
B数据元素的物理顺序与逻辑顺序相同
C花费的存储空间较顺序存储少
D便于随机存取
1.5.3循环链表及其基本运算
循环链表的结构与前面所讨论的线性链表相比,具有以下两个特点:
(l)在循环链表中增加了一个表头结点,其数据域为任意或者根据需要来设置,指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
(2)循环链表中最后一个结点的指针域不是空,而是指向表头结点。即在循环链表中,所有结点的指针构成了一个环状链。
在循环链表中,只要指出表中任何一个结点的位置,就可以从它出发访问到表中其他所有的结点,而线性单链表做不到这一点。
另外,由于在循环链表中设置了一个表头结点,因此,在任何情况下,循环链表中至少有一个结点存在,从而使空表与非空表的运算统一。
1.6 树与二叉树
树(tree)是一种简单的非线性结构。
3 下列叙述中正确的是( a )
A)线性表是线性结构
B)栈与队列是非线性结构
C)线性链表是非线性结构
D)二叉树是线性结构
99_1.下列数据结构中,属于非线性结构的是( )。
A. 循环队列 B.带链队列C.二叉树 D.带链栈
答案 C
解析 树均是非线性结构
6.2.64_5)下列叙述中正确的是
A)线性链表是线性表的链式存储结构
B)栈与队列是非线性结构
C)双向链表是非线性结构
D)只有根结点的二叉树是线性结构
红57_1以下数据结构不属于线性数据结构的是
A队列
B线性表
C二叉树
D栈
有关树结构的基本术语:
在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称为树的根。
在树结构中,每一个结点可以有多个后件,它们都称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中,一个结点所拥有的后件个数称为该结点的度。在树中,所有结点中的最大的度称为树的度。
树结构具有明显的层次关系,即树是一种层次结构。在树结构中,一般按如下原则分层:
根结点在第1层。
同一层上所有结点的所有子结点都在下一层。
树的最大层次称为树的深度。
在树中,以某结点的一个子结点为根构成的树称为该结点的一棵子树。
在树中,叶子结点没有子树。
树在计算机中通常用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息,而每个结点中的链域(即指针域)个数将随树中该结点的度而定。
10.设树T的度为4,其中度为1,2,3,4的结点个数分别为4,2,l,l。则T中的叶子结点数为 ( a )
A)8 B)7
C)6 D)5
1.6.2 二叉树及其基本性质
1.什么是二叉树
二叉树具有以下两个特点:
①非空二叉树只有一个根结点;
②每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
2.二叉树的基本性质
二叉树具有以下几个性质:
性质1 在二叉树的第k层上,最多有2k-1(k≥1)个结点。
59_2一棵二叉树第六层(根结点为第一层)的结点数最多为 【4】 个。32
性质2 深度为m的二叉树最多有2m-1个结点。
性质3 在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。
54_1某二叉树中度为2的结点有18个,则该二叉树中有 【1】 个叶子结点。19
12.3.74_7)某二叉树中有n个度为2的结点,则该二叉树中的叶子结点数为
A)n+l B)n_1 C)2n D)n/2
93_3)某二叉树有5个度为2的结点,则该二叉树中的叶子结点数是
A)10 B) 8 C)6 D)4
C
11.1.79_8一颗二叉树中共有70个叶子结点与80个度为1的结点,则该二叉树中的总结点数是
A 219
B 221
C 229
D 231
99_1)某二叉树由5个度为2的结点以及3个度为1的结点,则该二叉树中共有 【1】 个结点。14
109_3)一棵二叉树有10个度为1的结点,7个度为2的结点,则该二义树共有【3】个结点。
25
性质4 具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。
3.满二叉树与完全二叉树
满二叉树与完全二叉树是两种特殊形态的二叉树。
(1)满二叉树
所谓满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。这就是说,在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。
8.在深度为5的满二叉树中,叶子结点的个数为 ( c )
A)32 B)31
C)16 D)15
12.2.84_2)深度为5的满二叉树有______个叶子结点。16
13.5.64_7)在深度为7的满二叉树中,叶子结点的个数为A)32 B)31 C)64 D)63
14.4.74_(1)在深度为7的满二又树中,度为2的结点个数为 【1】 。63
(2)完全二叉树
所谓完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
由满二叉树与完全二又树的特点可以看出,满二又树也是完全二叉树,而完全二叉树一般不是满二叉树。红62_9设一棵完全二叉树共有500个结点,则在该二叉树中有 个叶子结点。250
2.设一棵完全二叉树共有700个结点,则在该二叉树中有 350 个叶子结点。
完全二叉树还具有以下两个性质:
性质5 具有n个结点的完全二叉树的深度为[log2n]+1。
性质6 设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,…,n给结点进行编号,则对于编号为k(k=l,2,…,n)的结点有以下结论:
①若k=l,则该结点为根结点,它没有父结点;若k>l,则该结点的父结点编号为INT(k/2)。
②若2k≤n,则编号为k的结点的左子结点编号为2k:否则该结点无左子结点(显然也没有右子结点)。
②若 2k+1≤n,则编号为 k的结点的有子结点编号为2k+1;否则该结点无右子结点。
根据完全二叉树的这个性质,如果按从上到下、从左到右顺序存储完全二叉树的各结点,则很容易确定每一个结点的父结点、左子结点和右子结点的位置。
1.6.3二叉树的存储结构
二叉树通常采用链式存储结构。
与线性链表类似,用于存储二叉树中各元素的存储结点也由两部分组成:数据域与指针域。
但在二叉树中,由于每一个元素可以有两个后件(即两个子结点),因此,用于存储二叉树的存储结点的指针域有两个:一个用于指向该结点的左于结点的存储地址,称为左指针域;另一个用于指向该结点的右子结点的存储地址,称为右指针域。
二叉树的链式存储结构也称为二叉链表。
I
L(i) V(i)
R(i)
1
0
P
0
2
0
A
0
3
4
6
F
9
5
13
G
1
6
2
C
8
7
8
11
D
0
9
0
E
5
10
11
0
B
0
12
13
0
H
0
对于满二叉树与完全二叉树来说,根据完全二叉树的性质6,可以按层序进行顺序存储,这样,不仅节省了存储空间,又能方便地确定每一个结点的父结点与左右子结点的位置。
l.6.4 二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。
红61_6 在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:前序遍历、 遍历和后序遍历
l.前序遍历(DLR)
所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中,首先访问根结点,然后遍历左子树,最后遍历右子树:并且,在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。
12.2.74_6) 对下列二叉树
进行前序遍历的结果为
A) DyBEAFCZX B)YDEBFZXCA
C)ABDYECFXZ D)ABCDEFXYZ
2.中序遍历 (LDR)
12.1.89_1)对下列二叉树进行中序遍历的结果___________。
7 设有下列二叉树:
对此二叉树中序遍历的结果为 ( b )
A)ABCDEF B)DBEAFC
C)ABDECF
D)DEBFCA
79_4对下列二叉树进行中序遍历的结果是__
69_10)对下列二叉树
进行中序遍历的结果是
A)
ACBDFEG
B)ACBDFGE
C)ABDCGEF
D)FCADBEG
3.后序遍历(LRD)
3.设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为 DEBFCA。
64_6)对如下二叉树
进行后序遍历的结果为
A)ABCDEF B)DBEAFC
C)ABDECF D)DEBFCA
103_3)设二叉树如下:
对该二叉树进行后序遍历的结果为 【3】 。
EDBGHFCA
1.7 查找技术
所谓查找是指在一个给定的数据结构中查找某个指定的元素。
1.7.1 顺序查找
从线性表的第一个元素开始,依次将线性表中的元素与被查元素进行比较,若相等则表示找到(即查找成功):若线性表中所有的元素都与被查元素进行了比较但都不相等,则表示线性表中没有要找的元素(即查找失败)。P6
下列两种情况下也只能采用顺序查找:
(l)如果线性表为无序表(即表中元素的排列是无序的),则不管是顺序存储结构还是链式存储结构,都只能用顺序查找。
(2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。
15.4.69_8)在长度为64的有序线性表中进行顺序查找,最坏情况下需要比较的次数为
A)63
B)64
C)6
D)7
54_4对于长度为n的线性表进行顺序查找,在最坏情况下所需要的比较次数为
A) log2n
B) n/2
C) n
D) n+1
9.对长度为n的线性表进行顺序查找,在最坏情况下所需要的比较次数为 ( b )
A)n+I B)n
C)(n+l)/2 D)n/2
109_2)在长度为n的线性表中,寻找最大项至少需要比较【2】次。
n-1
1.7.2 二分法查找
二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大,但允许相邻元素值相等)。
59_1下列数据结构中,能用二分法进行查找的是
A) 顺序存储的有序线性表
B) 线性链表
C) 二叉链表
D) 有序线性链表
设有序线性表的长度为n,被查元素为x,则二分查找的方法如下:
将x与线性表的中间项进行比较:
若中间项的值等于x,则说明查到,查找结束;
若X小于中间项的值,则在线性表的前半部分(即中间项以前的部分)以相同的方法进行查找;
若X大于中间项的值,则在线性表的后半部分(即中间项以后的部分)以相同的方法进行查找。
这个过程一直进行到查找成功或子表长度为0 (说明线性表中没有这个元素)为止。
显然,当有序线性表为顺序存储时才能采用二分查找,并且,二分查找的效率要比顺序查找高得多。可以证明,对于长度为n的有序线性表,在最坏情况下,二分查找只需要比较log2n次,而顺序查找需要比较n次。P4
15.1.89_3)在长度为 n 的有序线性表中进行二分查找,最坏情况下需要比较的次数是()。
A)O(n) B)O(n2)
C)O(log2n) D)O(nlog2n)
1. 在长度为n的有序线性表中进行二分查找,需要的比较次数为 log2n 。
103_1)下列叙述中正确的是
a)对长度为n的有序链表进行查找,最坏情况下需要的比较次数为n
b)对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为(n/2)
c)对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为(log2n)
d)对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为(nlog2n)
a
1.8 排序技术
所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
排序可以在各种不同的存储结构上实现。在本节所介绍的排序方法中,其排序的对象一般认为是顺序存储的线性表。
1.8.1 交换类排序法
所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。
1.冒泡排序法
冒泡排序法是一种最简单的交换类排序方法,它是通过相邻数据元素的交换逐步将线性表变成有序。
冒泡排序法的基本过程如下:
首先,从表头开始往后扫描线性表,在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,称之为消去了一个逆序。显然,在扫描过程中,不断地将两相邻元素中的大者往后移动,最后就将纷性表中的最大者换到了表的最后,这也是线性表中最大元素应有的位置。
然后,从后到前扫描剩下的线性表,同样,在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中,后面的元素小于前面的元素,则将它们互换,这样就又消去了一个逆序。显然,在扫描过程中,不断地将两相邻元素中的小者往前移动,最后就将剩下线性表中的最小者换到了表的最前面,这也是线性表中最小元素应有的位置。
对剩下的线性表重复上述过程,直到剩下的线性表变空为止,此时的线性表已经变为有序。
在上述排序过程中,对线性表的每一次来回扫描后,都将其中的最大者沉到了表的底部,最小者象气泡一样冒到表的前头。冒泡排序由此而得名,且冒泡排序又称下沉排序。
假设线性表的长度为n,则在最坏情况下,冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描,需要的比较次数为n(n-1)/2。但这个工作量不是必需的,一般情况下要小于这个工作量。
4.在最坏情况下,冒泡排序的时间复杂度为n(n-1)/2。
17.3.79_7冒泡排序在最坏情况下的比较次数是
17.1.64_1)对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为 【1】 。45
2.快速排序法
快速排序法也是一种互换类的排序方法,但由于它比冒泡排序法的速度快,因此称之为快速排序法。
快速排序法的基本思想如下:
从线性表中选取一个元素,设为T,将线性表后面小于T的元素移到前面,而前面大于T的元素移到后面,结果就将线性表分成了两部分(称为两个子表),T插入到其分界线的位置处,这个过程称为线性表的分割。通过对线性表的一次分割,就以T为分界线,将线性表分成了前后两个于表,且前面子表中的所有元素均不大于 T,而后面子表中的所有元素均不小于 T。
如果对分割后的各子表再按上述原则进行分割,并且,这种分割过程可以一直做下去,直到所有子表为空为止,则此时的线性表就变成了有序表。
由此可知,快速排序法的关键是对线性表进行分割,以及对各分割出的于表再进行分割。
在对线性表或于表进行实际分割时,可以按如下步骤进行:
首先,在表的第一个、中间一个与最后一个元素中选取中项,设为P(k),并将P(k)赋给T,再将表中的第一个元素移到P(k)的位置上。
然后设置两个指针i和j分别指向表的起始与最后的位置。反复操作以下两步:
(1)将j逐渐减小,并逐次比较P(j)与T,直到发现一个P(j)<T为止,将P(j)移到P(i)的位置上。
(2)将i逐渐增大,并逐次比较P(i)与T,直到发现一个P(i)>T为止,将P(i)移到P(j)的位置上。
上述两个操作交替进行,直到指针i与j指向同一个位置(即i=j)为止,此时将T移到P(i)的位置上。
在快速排序过程中,随着对各子表不断的进行分割,划分出的于表会越来越多,但一次又只能对一个子表进行再分割处理,需要将暂时不分割的子表记忆起来,这就要用一个栈来实现。在对某个子表进行分割后,可以将分割出的后一个子表的第一个元素与最后一个元素的位置压人栈中,而继续对前一个子表进行再分割:当分割出的子表为空时,可以从栈中退出一个子表(实际上只是该于表的第一个元素与最后一个元素的位置)进行分割。这个过程直到栈空为止,此时说明所有子表为空,没有子表再需要分割,排序就完成了。
样1对于输入为n个数进行快速排序算法的平均时间复杂度是
54_3对于长度为n的线性表,在最坏情况下,下列各排序法所对应的比较次数中正确的是
A) 冒泡排序为n/2
B) 冒泡排序为n
C) 快速排序为n
D) 快速排序为n(n-1)/2
1.8.2 插入类排序法
1.简单插入排序法
所谓插入排序,是指将无序序列中的各元素依次插入到已经有序的线性表中。
插入过程如下:
首先将第j个元素放到一个变量T中,然后从有序子表的最后一个元素(即线性表中第j-1个元素)开始,往前逐个与T进行比较,将大于T的元素均依次向后移动一个位置,直到发现一个元素不大于T为止,此时就将T(即原线性表中的第j个元素)插入到刚移出的空位置上,有序子表的长度就变为j了。
在简单插入排序法中,每一次比较后最多移掉一个逆序,因此,这种排序方法的效率与冒泡排序法相同。在最坏情况下,简单插入排序需要n(n-1)/2次比较。
2.希尔排序法
希尔排序法的基本思想如下:
将整个无序序列分割成若干小的于序列分别进行插入排序。
子序列的分割方法如下:
将相隔某个增量h的元素构成一个子序列。在排序过程中,逐次减小这个增量,最后当h减到1时,进行一次插入排序,排序就完成。
增量序列一般取ht=n/2k(k=1,2,…,[log2n]),其中n为待排序序列的长度。
希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列,则在最坏情况下,希尔排序所需要的比较次数为O(n1.5)。
红59_12希尔排序法属于哪一种类型的排序法
A交换类排序法
B插入类排序法
C选择类排序法 D 建堆排序法
1.8.3 选择类排序法
1.简单选择排序法
选择排序法的基本思想如下:
扫描整个线性表,从中选出最小的元素,将它交换到表的最前面(这是它应有的位置);然后对剩下的子表采用同样的方法,直到子表空为止。
简单选择排序法在最坏情况下需要比较n(n-l)/2次。
2.堆排序法
具有n个元素的序列(h1,h2,…,hn),当且仅当满足
(i=l,2,…,n/2)时称之为堆。
堆顶元素(即第一个元素)必为最大项。
(91,85,53,36,47,30,24,12)
将下列序列调整为堆
(100,85,40,75,80,60,65,95,82,10,20)
堆排序的方法对于规模较小的线性表并不适合,但对于较大规模的线性表来说是很有效的。在最坏情况下,堆排序需要比较的次数为O(nlog2n)。
1.快速排序和堆排序速度快,时间复杂度为O(nlog2n)
2.其它排序方法为时间复杂度为O(n2)
归并排序
256 301 751 129 937 863 742 694 76 738
[256 301] [129 751][863 937][694 742][76 738]
[129 256 301 751] [694 742 863 937][76 738]
[129 256 301 694 742 751 863 937] [76 738]
[76 129 256 301 694 738 742 751 863 937]
红60_18 在下列排序方法中,要求内存量最大的是
A 插入排序
B选择排序
C快速排序 D归并排序
已知两个有序表,若要将它们组合成一个新的有序表,最好的方法是
A希尔排序
B插入