数据结构与算法：
本章的知识用于提高程序的效率以及对较复杂的问题进行求解。本章内容在计算机专业基础课中也属于比较难的一门，学习本章的内容必须进行理解，死记硬背是无效的。对于等级考试，本章重点的考核点主要在二叉树，同时这也是本章的难点，考核形式主要为二叉树的遍历问题（如给图求遍历序列、给前序、中序遍历求后序遍历等）、二叉树的结点问题（如给出一些条件然后求叶子结点个数）；还有排序和查找考试中也经常会涉及到，排序主要以计算时间复杂度的形式考核，查找主要以计算最佳/最坏比较次数的方式考核。其余的知识点主要以概念的形式考察，考生需要仔细看书并理解。
一、考试必备知识
1．算法
1）算法的基本概念：算法是指解题方案的准确而完善的描述。
算法的基本特征：可行性、确定性、有穷性、拥有足够的情报
算法的基本要素：
a.算法中对数据的运算和操作：基本的运算和操作包括算术运算、逻
辑运算、关系运算和数据传输；
b.算法的控制结构：基本的控制结构包括顺序结构、选择结构、循环
结构。
算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法2）算法的复杂度
算法的复杂度主要包括时间复杂度和空间复杂度。
①算法的时间复杂度：指执行算法所需要的计算工作量。算法的工作量可以用算
法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。
即：算法的工作量=f(n)，其中n是问题的规模。
在同一个问题规模下，如果算法执行所需得基本运算次数取决于某一特定的输入时，
可以用以下两种方法分析算法的工作量：
a.平均性态
平均形态分析，是指用各种特定输入下的基本运算次数的加权平均值来度量
算法的工作量。
b.最坏情况复杂性
最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。
②算法的空间复杂度：一般指执行这个算法所需要的内存空间。一个算法所占用
的存储空间包括算法程序所占的空间、输入的初始数据所占用的存储空间、算法执
行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以
及某种数据结构所需要的附加存储空间。
2．数据结构的基本概念
数据结构科学主要研究如下三个方面的内容：
①数据集合中各数据元素之间所固有的逻辑关系，及数据的逻辑结构
②在对数据进行处理时，各数据元素在计算机中的存储关系，及数据的存储结构
③对各种数据结构进行的运算
数据结构学科的研究目的：提高数据处理的效率。
主要包括：数据处理速度和尽量节省在数据处理过程中所占用的计算机存储空间。
数据结构的定义：
数据处理：数据处理是指对数据集合中各元素以各种方式进行运算
数据元素：在数据处理领域中，每一个需要处理的对象都可以抽象为数据元素
数据结构：数据结构是指反映数据元素之间关系的数据元素集合的表示
⑴数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。
它包含两个要素：a.数据元素的集合，通常记为D；b.D上的关
系，它反映了D中各数据元素之间的前后件关系，通常记为R。
形式如下：B=(D,R) 其中B表示数据结构
⑵数据的存储结构：是指数据的逻辑结构在计算机存储空间中的
存放形式。一般来说，一种数据结构的逻辑结构根据需要可以
表示成多种存储结构。常用的存储结构有顺序、链接、索引等
存储结构。
数据结构的图形表示：
图形表示方法：对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，
一般称之为数据结点，简称为结点；对于关系R中的每一个二元组，
用一条有向线段从前件结点指向后件结点，以表示数据元素之间的前
后件关系。
线性结构和非线性结构：
数据结构一般分为线性结构和非线性结构两大类。
线性结构满足：a.有且仅有一个根结点；b.每一个结点最多有一个前件，也最多有一
个后件;c.在一个线性结构中插入或删除任何一个结点后还是线性结
构。
如果一个数据结构不是线性结构，则称之为非线性结构。
3．线性表及其顺序存储结构
1）线性表的基本概念
线性表定义：线性表是由n(n>=0)个数据元素a1,a2,…,an组成的一个有限序列，表
中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且
只有一个后件。即线性表或是一个空表，或是可以表示为：(a1,a2,…,ai,…,an) 其中
ai(i=1,2,…,n)是属于数据对象的元素，通常也称为线性表中的一个结点。
非空线性表有如下结构特征：a.有且只有一个根结点a1，它无前件；b.有且只有一
个终端结点an，它无后件；c.除根结点与终端结点外，其他所有结点有且只有一个
前件，也有且只有一个后件。
线性表的长度：线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。
2）线性表的顺序存储结构
线性表的顺序存储结构的基本特点：a.线性表中所有元素所占的存储空间是连续的；
b.线性表中个数据元素在存储空间中是按逻辑顺序依次存放的。
线性表的随机存取地址的计算公式：ADD(ai)=ADD(a1)+(i-1)k
线性表的主要操作：线性表的插入、线性表的删除、线性表的查找、线性表的排序、线性表的分解、线性表的合并、线性表的复制、线性表的逆转。
3）线性表的插入运算：
设长度为n的线性表为：（a1,a2,…,ai,…,an）
①线性表插入操作的实现方法：
一般的，要在第i（1<=i<=n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间的n-i+1个元素依次向后移动一个位置，
移动结束后，第i个位置就被空出，然后将新的元素插入到第i项。插入结束后，线
性表的长度就增加了1。
②线性表插入操作算法的复杂度分析：
有线性表插入算法可知：如果插入的位置在第i（1<=i<=n）个元素之前，则原来第i个元素之后的所有元素都必须向后移动，在平均情况下，要在线性表中插入一
个新元素，需要移动表中一半的元素，最坏的情况下要移动表中的所有元素。
4）线性表的删除运算：
设长度为n的线性表为：（a1,a2,…,ai,…,an）
①线性表删除操作的实现方法：
一般的，要删除第i（1<=i<=n）个元素时，首先要从第i+1个元素开始，直到最后一个（即第n个）元素之间的n-i个元素依次向前移动一个位置。删除结束后，
线性表的长度就减少了1。
②线性表删除操作算法的复杂度分析：
有线性表删除算法可知：如果删除的是第i（1<=i<=n）个元素，则原来第i个元素之后的所有元素都必须向前移动一个位置，在平均情况下，要在线性表中删除一
个元素，需要移动表中一半的元素，最坏的情况下要移动表中的所有元素。
5）线性表顺序存储结构的使用场合：
线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适
的，因为顺序存储的结构比较简单。但这种顺序存储的方式对于元素需要变动的大
线性表就不太合适了，因为插入和删除的效率比较低。
4．栈和队列
1）栈及其基本运算：
栈的基本定义：栈是限定在一端进行插入和删除的线性表。它按照“后进先出”的
原则组织数据。
栈的顺序存储：在程序设计语言中，一般使用一维数组S(1:m)作为栈的顺序存储空
间，其中m为栈的最大容量。
栈的基本运算：
①入栈运算：首先将栈顶指针（top）加1，然后将新元素插
入到站顶指针指向的位置。当栈顶指针已经指向存储空间
的最后一个位置时，说明栈空间以满，不可能再进行入栈
操作。此时发生栈“上溢”错误。
②退栈运算：首先将栈顶元素赋给一个指定的变量，然后将
栈顶指针(top)减1，当栈顶指针为0时，说明栈空，不可能
进行退栈操作。此时，发生栈“下溢”错误。
③读栈顶元素：将栈顶元素赋给一个指定的变量，栈指针（top）
不变，当栈顶指针为0时，说明栈空，读栈顶元素失败。
2）队列及其基本运算
队列的定义：队列是指允许在一端进行插入，而在另一端进行删除的线性表。它按
照“先进先出”的原则组织数据。
循环队列空的状态：s=0,且front=rear=m
循环队列满的状态：s=1,且front=rear
循环队列的基本运算：
入队运算：首先将队尾指针加1，（rear=rear+1）,并当rear=m+1时置rear=1;然后将新元素插入到指针指向的位置。当循环队列满时（s=1，且front=rear）入队操作
将引起“上溢”错误。
退队运算：首先将排头指针加1（front=front+1）,并当front=m+1时置front=1；
然后将排头指针指向的元素赋给指定的变量。当循环队列为空时，（s=0,front=rear）,退队操作将引起“下溢”错误。
5．线性链表
1）线性链表的基本概念：线性表的链式存储结构称为线性链表。
①线性链表
线性链表的链式存储结构：相信链表的每个结点中数据域存放数据元素的值，
指针域存放后件结点的存储地址。
双向链表的链式存储结构：双向链表得链式存储结构比线性链表得链式存储结
构多出一个指针域，它用来存放前件结点的存储地址。
②带链的栈
栈的链式结构：栈的链式结构基本上和线性链表得链式存储结构相同。只是线
性链表的链式存储结构的头指针变成了栈的链式结构的栈顶指针。
③带链的队列
队列的链式结构：队列的链式结构和线性链表的链式存储结构也基本相同。只
不过队列地链式结构保持有两个指针：一个指向队列头的头指针和一个指向队
列尾的尾指针。
2）线性链表的基本运算
①线性链表的主要运算：线性链表的插入、线性链表的删除、线性链表的合并、
线性链表的分解、线性链表的逆转、线性链表的复制、线性链表的排序、线性
链表的查找。
②线性链表的查找：从头指针指向的节点开始往后沿指针进行扫描，直到后面已
没有结点或下一个结点的数据域为搜索值x为止。
③线性链表的插入：先从栈中为新元素分配一个新的结点p，并赋值。然后利用
线性链表的查找算法找到待插入位置的前一个结点的指针q。先将p指向q的
后件，然后将p挂接在q结点后面。
④线性链表的删除：利用线性链表的查找算法找到待删除元素的前一个结点p，
用另一个指针q暂时保存p的后续结点（即待删除结点），然后把q结点的后续
链结直接挂接在p的后面。最后归还q结点所分配的栈空间。
3）循环链表及其基本运算
循环链表有如下几个特点：
a.在循环链表中增加一个表头结点，使得循环链表对空表和非空表的操作实现
了统一。b.循环链表的最后一个结点的指针域不是空，而是指向表头结点。c.
判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结
点是否还是表头结点。d.在循环链表中，从任何一个结点出发都可以访问到表
中其他所有的结点
6．树与二叉树
1）树的基本概念
基本术语：根结点、父结点、子结点、叶子结点、结点的度、树的度、树的深度、子树。
要求考生掌握用树表式算术表达式的方法
要求考生了解树链表中的结点结构
2）二叉树及其基本性质
①二叉树的特点：儿叉数具有以下两个特点，一是非空儿叉树只有一个根结点，
二是每一个结点最多有两棵子树。
②二叉树的基本性质：
性质一：在二叉树的第k层上，最多有2 k-1(k>=1)个结点。
性质二：深度为m的二叉树最多有2 m-1个结点
性质三：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的
结点多一个。
性质四：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表式log2n 的整数部分。
3）满二叉树和完全二叉树
满二叉树定义：除最后一层外，每一层上的所有结点都有两个子结点（即每一层上
的结点数均达到最大值）
完全二叉树定义：除最后一层外，每一层上的结点数均达到最大值，在最后一层上
只缺少右边的若干结点。
性质五：满二叉树的第k层上有2k-1个结点，且其深度为m的满二叉树有2m-1
个结点。
性质六：具有n个结点的完全二叉树的深度为[log2n]+1
性质七：设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从
左到右）用自然数1,2,…,n给结点进行编号，则对于编号为k(k=1,2,…,n)的结点
有以下结论：
a.若k=1,则该结点为根结点，它没有父结点；.若k>1,则该结点的父结点编号
为[k/2]
b..若2k<=n,则编号为k的结点的左子结点编号为2k；否则该结点无左子结
点（显然也没有右子结点）
c.若2k+1<=n,则编号为k的结点的右子结点编号为2k+1；否则该结点无右子
结点
提示：二叉树、满二叉树、完全二叉树的定义和性质非常重要，请熟练理解和掌握4）二叉树的存储结构
L(i):左指针域，指向该结点的左子结点（存放左子结点的存储地址）
R(i):右指针域，指向该结点的右子结点（存放右子结点的存储地址）
V(i):数据域，存放结点的值
5）二叉树的遍历
二叉树的遍历集中的用到了递归的思想，它主要有三种遍历方式：
a.前序遍历（DLR）：先访问根结点，后前序遍历左子树，再前序遍历右子树
b.中序遍历（LDR）：先中序遍历左子树，后访问根结点，再中序遍历右子树
c.后序遍历（LRD）：先后序遍历左子树，后后序遍历右子树，再访问根结点，7．查找技术
1）顺序查找：
查找方法：从表头到表尾逐个比较，若相同则结束查找，否则一直继续比较下一个
表中元素直到整个表都遍历完。对于长度为n的线性表，平均要进行n/2次比较，
在最坏情况下要进行n次比较。
适用场合：无序表或采用链式存储的表（不管无序还是有序）
2）二分查找：
查找方法：每次把待查找值与表中间元素比较，以减半的方式缩小搜索范围。对于
长度为n的线性表，在最坏情况下要进行log2n次比较。
适用场合：顺序存储的有序表。
8．排序技术
1）交换类排序
常用的交换类排序有：冒泡排序法、快速排序法
2）插入类排序
常用的插入类排序有：简单插入排序法、希尔排序法
3）选择类排序
常用的选择类排序有：简单选择排序法、堆排序法
二、历届最新考题汇编
选择题：
1．数据的存储结构是指：
a.存储在外存中的数据
b.数据所占的存储空间量
c.数据在计算机中的顺序存储方式 c.数据的逻辑结构在计算机中的表示
2．下列关于栈的描述中错误的是
a.栈是先进后出的线性表
b.栈只能顺序存储
c.栈具有记忆作用
d.对栈的插入与删除操作中，不需要改变栈底指针
3．对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是
a.冒泡排序为n/2
b.冒泡排序为n
c.快速排序为n
d.快速排序为n(n-1)/2
4．对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为
a.log2n
b.n/2
c.n
d.n+1
5．对于线性链表的描述中正确的是
a.存储空间不一定是连续，且各元素的存储顺序是任意的
b.存储空间不一定是连续，且前件元素一定存储在后件元素的前面
c.存储空间必须连续，且前件元素一定存储在后件元素的前面
d.存储空间必须连续，且各元素的存储顺序是任意的
6．算法的时间复杂度是指
a.执行算法程序所需要的时间
b.算法程序的长度
c.算法执行过程中所需要的基本运算次数
d.算法程序的指令条数
7．算法的空间复杂度是指
a.算法程序的长度
b.算法程序的指令条数
c.算法程序所占的存储空间
d.算法执行过程中所需要的存储空间
8．下列叙述中正确的是
a.线性表是线性结构
b.栈和队列是非线性结构
c.线性链表是非线性结构
d.二叉树是线性结构
9．长度为10的顺序表的首地址是从1023开始的，顺序表中每个元素的长度为2，在第4个元素前面插入一个元素和删除第7个元素后，顺序表的总长度还是不变。问在执行插入和删除操作前，顺序表中的5个元素在执行插入和删除操作后的顺序表中的存储地址是
a.1028
b.1029
c.1031
d.1033
10．下列关于线性表的两种存储结构叙述正确的是
a.若存储相同数目的元素，则线性链表比顺序表要节省存储空间
b.对无序表的查找，顺序表和线性链表的效率是一样的
c.顺序表适用于插入、删除等更新操作频繁的场合
d.线性链表适用于查询操作比较频繁的场合
11．下列关于栈的叙述中不正确的是
a.在栈中只能在同一端插入、删除数据
b.再栈中只能在一端插入数据，在另一端删除数据
c.栈是先进后出的线性表
d.栈是后进先的线性表
12．已知元素的入栈顺序为abcde，则下列那种出栈顺序是不可能的（出栈和入栈操作可交叉进行）
a.edcba
b.cabde
c.dcbae
d.bcdea
13．在线性链表的插入算法中，若要把结点q插在结点p后面，下列操作正确的是
a.使结点p指向结点q，再使结点q指向结点p的后件结点
b.使结点q指向结点p的后件结点,再使结点p指向结点q
c.使结点q指向结点p，再使结点p指向结点q的后件结点
d.使结点p指向结点q的后件结点,再使结点q指向结点p
14．下列叙述中错误的是
a.循环链表中，通过表中的任何一个结点可以访问到表中其他所有结点
b.线性链表的插入和删除效率比顺序表的插入和删除效率高
c.线性链表与顺序表相比，它容易实现动态增长
d.在线性链表中查找一个元素要比在顺序表中查找一个元素快
15．一棵度数为4的树，它的4度结点有1个，3度结点有2个，2度结点有3个，1度结点有4个，问它的叶子结点有多少个
a. 5
b. 6
c.9
d.11
16．一棵深度为m的二叉树有2m-1个结点，则最多可以断定此二叉树是
a.满二叉树
b.一般的完全二叉树
c.一般的二叉树
d.一般的树
17．在一个n×m的二维线性表中顺序查找一个数据元素的算法时间复杂度是
a.O(n+m)
b.O(n×m)
c.O(n2)
d.O(m2)
18．下面排序算法中，平均排序速度最快的是
a.冒泡排序法
b.选择排序法
c.交换排序法
d.堆排序法
填空题：
1．某二叉树中度为2的结点有18个，则该二叉树中有（）个叶子结点。
2．问题处理方案的正确而完整的描述称为（）
3．已知被查项x再数组中出现的概率为q，且需要查找的x在数组中每个位置上的可能性是一样的。试分析采用顺序搜索方法，在长度为n的一维数组中查找值为x的元素的算法中，算法的平均时间复杂度是（），最坏情况下，它的时间复杂度是（）。
4．假如刚开始时栈为空，一次有’A’,’B’,’C’,’D’四个元素入栈，此时栈底指针指向元素（），栈顶指针值为（）（假设没个元素的长度为1）。执行四次出栈操作后把’E’,’F’,’G’压入栈，问此时栈底指针指向元素（），此时栈的长度为（）。
5．一个容量为15的循环队列中，若头指针front=6，为指针rear=4，则该循环队列中共有（）个元素；若头指针front=4，为指针rear=6，则该循环队列中共有（）个元素；若头指针front=6，为指针rear=6，则该循环队列中共有（）个元素。
6．拥有奇数个结点的完全二叉树中有4个内部结点（非叶子结点），请问它的叶子结点数是（）。
7．请写出用二分查找法在有序顺序表（1，2，3，4，6，8，9，11）中查找3的比较序列（）。
8．设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为（）。
9．请写出用冒泡排序法对序列（5，1，7，3，1，6，9，3，2，7，6）进行第一遍扫描后的中间结果是（）。
10．请写出用希尔排序法对序列（5，1，7，3，1，6，9，3，2，7，6）进行第一遍扫描后的中间结果是（）。
11．请写出用简单选择排序法对序列（5，1，7，3，1，6，9，3，2，7，6）进行第一遍扫描后的中间结果是（）。
三、全真试题训练
选择题：
1．下面哪一个不是算法的基本特征
a.可靠性
b.确定性
c.有穷性
d.拥有足够的情报
2．通过列举少量的特殊情况，经过分析，最后找出一般的关系的算法设计思想是
a.列举法
b.归纳法
c.递推法
d.递归法
3．常用于解决“是否存在”或“有多少种可能”等类型的问题（例如求解不定方程的问题）的算法设计基本方法是
a.归纳法
b.递推法
c.列举法
d.减半递推技术
4．以下算法设计基本方法中，基本思想不属于归纳法的是
a.递推法
b.递归法
c.减半递推技术
d.回溯法
5．在用二分法求解方程在一个闭区间上的实根时，采用的算法设计技术是
a.列举法
b.归纳法
c.递归法
d.减半递推法
6．对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为
a.n+2
b.n
c.(n+1)/2
d.n/2
7．下面那一项叙述不是非空线性表的结构特征的正确描述
a.有且只有一个根结点，它无前件
b.有且只有一个终端结点，它无后件
c.除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件
d.每一个结点都有一个前件和一个后件
8．已知线性表的首元素的地址是1025，每一个数据元素的长度为2，则第10个元素的地址为
a.1035
b.1045
c.1027
d.1043
9．下列关于队列的叙述中正确的是
a.在队列中只能删除数据
b.在队列中只能插入数据
c.队列是先进先出的线性表
d.队列是后进先出的线性表
10．下列关于链表结构的叙述正确的是
a.线性链表、带链的栈和带链的队列的结点的结构都是相同的
b.双向链表也就是循环链表
c.线性链表与带链的栈的结点的结构是不同的
d.在循环链表中通过任意一个结点可以找到链表中其他所有的结点，而在双向链表中做不到这一
点
11．在表示树的多重链表中，除了要存储结点的值和多个指针之外，还必须需要存储
a.结点的度
b.结点的层次
c.结点的高度
d.结点的深度
12．树T的度为4，其中度为1,2,3,4的结点个数分别为4,2,1,1。则T中的叶子结点数为
a.8
b.7
c. 6
d. 5
13．在深度为5的满二叉树中，叶子结点的个数为
a.32
b.31
c.16
d.15
14．具有8个结点的完全二叉树中编号为4的结点的右子结点的标号为
a.8
b.9
c.无此结点
d.8或9
15．在长为n的有序表中进行二分查找，需要的最大比较次数为
a.n
b.n/2
c.log2n
d.log2n/2
16．通过相邻数据元素的交换逐步将线性表变成有序的排序方法是
a.冒泡排序法
b.简单选择排序法
c.简单插入排序法
d.希尔排序法
17．快速排序法属于
a.选择类排序法
b.交换类排序法
c.插入类排序法
d.归并类排序法
18．对长度为n的线性表进行堆排序的时间复杂度是
a.O(n)
b.O(nlog2n)
c.O(n2)
d.O(n1.5)
填空题
1．算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是（）。
2．在一般的计算机系统中，有算术运算、逻辑运算、关系运算和（）四类基本的操作和运算。
3．算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释，也不允许有多义性，这是算法的（）特征。
4．算法必须能在有限的时间内完成，即算法必须能在执行有限个步骤之后终止，这是算法的（）特征。
5．（）是一组严谨的定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。
6．算法中各操作之间的执行顺序称为（）。描述算法的工具通常有（）、（）、（）等。
7．一个算法一般都可以用（）、（）、（）三种控制结构组合完成。
8．根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的，这是算法设计基本方法中的（）。
9．通过列举少量的特殊情况，经过分析，最后找出一般的关系，这是算法设计基本方法中的（）。10．从已知的初始条件出发，逐步推出所要求的各中间结果和最后结果，这是算法设计的基本方法中的（）。
11．将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止，这是算法设计基本方法中的（）。如果一个算法p显示的掉用自己则称为（）。如果算法p调用另一个算法q，而算法q又调用算法p，则称为（）。
12．将问题的规模减半，而问题的性质不变，再重复“减半”的过程，这是算法设计基本方法中的（）。13．通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探，这是算法设计基本方法中的（）。
14．算法的时间复杂度是用算法所执行的（）来度量。
15．反映数据元素之间逻辑关系的数据结构是（）。数据的逻辑机构在计算机存储空间中的存放形式称为（）。
16．数据的逻辑结构有两个要素：一是（），通常记为（）；而是（），通常记为（）。
17．表示数据结构的两种法是（）和（）。
18．在长度为n的顺序存储结构的线性表中，要在第i(1<=i<=n)个元素之前插入一个新元素，则需要移动表中的（）个元素，表的长度变为（）；若删除表中的第i(1<=i<=n)个元素，则需要移动表中的（）个元素，表的长度变为（）。
19．长度为n的顺序存储结构中的线性表中，插入（或删除）一个元素，在平均情况下需要移动表中的（）个元素，在最坏情况下需要移动表中的（）个元素。
20．已知线性表的每个元素占2个字节，它的第5个元素在内存中的存储地址是1005，那么它的第2个元素在内存中的存储地址是（）。
21．数据按照“先进后出”的顺序组织的数据结构是（），按照“后进先出”组织的数据结构是（），按照“先进先出”组织的数据结构是（）。
22．树是一种简单的（）（线性/非线性）结构，在树中，所有的数据元素之间的关系具有明显的（）特性。
23．设一棵完全二叉树共有700个结点，则在该二叉树中有（）个叶子结点。
24．具有16个结点的完全二叉树的深度为（）。
25．在最坏情况下，冒泡排序的时间复杂度为（），简单插入排序的时间复杂度为（），希尔排序的时间复杂度为（），简单选择排序的时间复杂度为（），堆排序的时间复杂度为。
26．以下排序技术中属于交换类排序法的有（），属于插入类排序法的有（），属于选择类排序法的有（）。
Ⅰ简单插入排序Ⅱ冒泡排序Ⅲ希尔排序Ⅳ堆排序Ⅴ快速排序Ⅵ简单选择排序
实验报告 课程名称:数据结构与算法 实验名称:树的应用 一、实验目的 ⑴、掌握二叉树的静态数组存放。 ⑵、掌握哈夫曼编码的基本概念。 ⑶、掌握哈夫曼编码树的构造方法。 ⑷、掌握哈夫曼编码的构造和使用。 ⑸、理解前缀编码的概念。 二、实验内容 ⑴、按照字符出现概率构造一个哈夫曼树。要求输入为一个文本文件（可以限 制文本仅仅包含字母），通过统计字符出现的次数计算概率，在此基础上构造哈夫曼树。 ⑵、打印出每一个字母对应的哈夫曼编码。 三、实验环境 硬件：Windows XP计算机、鼠标、键盘、显示器 开发环境：Microsoft Visual C++ 6.0 四、实验步骤 ①、点击开始菜单中的程序-Microsoft Visual C++ 6.0 点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入5.cpp,再点击确定. ②、编写程序如下： #include
数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：
（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满
2.3 课后习题解答 2.3.2 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×） 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×） 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 12．线性表的特点是每个元素都有一个前驱和一个后继。（×） 2.3.3 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ } } 时间复杂度为O(n)。
大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。
A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业 张铭编写并发布 mzhang@https://www.doczj.com/doc/f811109830.html, 第11次作业，12月17日（周一）课前提交，电子稿提交时间12月17日开课之前提交。 11.1 偶数阶的B 树插入上溢出时，中 位数有两个，需要注意采用统一的策略。例如，取第二个中位数， 即分裂后左(1)/2m ?????个关键码，右(1)/2m ?????； 或者取第一个中位数，分裂后左(1)/2m ????? 右(1)/2m ?????。请画出对右图的4阶B 树进行下来操作后的B 树。 (1) 分裂时采用第2个中位数为 分界码，请画出插入关键码113后的B 树；分析插入操作的访外次数。 (2) 分裂时采用第1个中位数为分界码，请画出插入关键码113后的B 树；分析插入操 作的访外次数。 (3) 在原树中删除关键码50；分析删除操作的访外次数（与1、2题无关，从根重新开 始操作）。 11.2 已知一组关键码为(20, 30, 50, 52, 60, 68, 70)，试依次插入关键码。 (1) 生成一棵3阶的B +树，画出插入所有关键码后B 树的结构。 (2) 画出删除50后的B + 状态，分析删除操作的访外次数。 11.3 假设一个数据文件每个记录对象需要占用128 字节（其中关键码占用4字节），且所 有记录均已按关键码有序地存储在主磁盘文件中。设磁盘页块大小为2048（= 2K ）字节，若主存中有12M 空间可以用来存储索引结构，索引项中每一个地址指针占8 字节。请简要回答以下问题（请写明你的计算过程）。 （1） 使用B 树索引，B 树的阶m 1最多可以为多少？4层m 1阶B 树，最多可以索引多 少字节的数据文件？ （2） 使用B +树索引，B +树的阶m 2最多可以为多少? （3） 假设B +树的叶层各结点链接成双链结构，B +树的叶结点阶m 2’可以跟内部结点不 一样，则阶m 2’为多少? （4） 在第(3)小题的基础上，计算4层B +树（内部结点为m 2阶，叶结点m 2’阶），最多 可以索引多少字节的数据文件？ （5） 假设尽量把B +树的头几层放入内存（本题规定不能超过12M ），那么给定关键码， 通过B +树查找到(4)小题中主数据文件的一个记录，最少几次访外？最多几次访 外？ 11.4 对于下面两种B +树，列表给出他们在1、2、3、4和5层（独根是一层树）的不同情 况下，能够存储的最大记录数和最小记录数。 (1) 对于教材定义那样的B +树，其内部结点阶为50，叶结点阶为50。 (2) 如讲义P89那样的混合型B +树，其内部结点阶为55，叶结点阶为25（叶结点除关 键码，还索引部分记录信息）。 4阶B 树
数据结构与方法 1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算与操作:算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括:时间复杂度、空间复杂度 6、算法的时间复杂度:指执行算法所需要的计算工作量 7、算法的空间复杂度:指执行这个算法所需要的内存空间 8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的:提高数据处理的效率 10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件与后件、在一个线性结构中插入与删除任何一个结点后还就是线性结构 19、线性表定义:线性表就是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个与最后一个外,其她所有结点只有一个前件与一个后件 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间就是连续的、各数据元素在存储空间中就是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义:栈就是限定在一端进行插入与删除的线性表,它按照“先进后出,后进先出”的原则组织数据 26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m 为栈的最大容量 27、栈的基本运算:入栈、退栈、读栈顶元素 28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列就是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列,
Data Structures and Algorithm 习题答案 Preface ii 1 Data Structures and Algorithms 1 2 Mathematical Preliminaries 5 3 Algorithm Analysis 17 4 Lists, Stacks, and Queues 23 5 Binary Trees 32 6 General Trees 40 7 Internal Sorting 46 8 File Processing and External Sorting 54 9Searching 58 10 Indexing 64 11 Graphs 69 12 Lists and Arrays Revisited 76 13 Advanced Tree Structures 82 i
ii Contents 14 Analysis Techniques 88 15 Limits to Computation 94
Preface Contained herein are the solutions to all exercises from the textbook A Practical Introduction to Data Structures and Algorithm Analysis, 2nd edition. For most of the problems requiring an algorithm I have given actual code. In a few cases I have presented pseudocode. Please be aware that the code presented in this manual has not actually been compiled and tested. While I believe the algorithms to be essentially correct, there may be errors in syntax as well as semantics. Most importantly, these solutions provide a guide to the instructor as to the intended answer, rather than usable programs.
2.3 课后习题解答 选择题 1、A 2、A 3、D 4、C 5、D 6、B 7、C 8、B 9、A 10、D 11、B 12、D 2.3.2 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×） 8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×） 11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 12．线性表的特点是每个元素都有一个前驱和一个后继。（×） 2.3.3 算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ }
《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 2015年秋季学期《数据结构》课程作业 一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。（每空1分，共30分） 1.鼓励独立完成作业，严惩抄袭！数据的逻辑结构被形式地定义为B=(K,R),其中K 是 ____C__的有限集合，R是K上的___H___的有限集合。（第一章） a 存储 b 数据操作c数据元素d操作 e逻辑结构 f 映象 g算法h关系 2.以下关于算法的说法不正确的是____B _________。（第一章） a 一个算法应包含有限个步骤 b算法越简单越好 c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之 d算法中的每个步骤都能在有限时间内完成 3．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03， 07>，<03，08>，<03，09>}，则数据结构A是______B________。（第一章） a 线性结构 b 树型结构 c 物理结构 d 图型结构 4.下面程序段的时间复杂度为___C___（第一章） int sum=0; for(i=0; i 数据结构与算法试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的 B 部分地址必须就是连续的 C 一定就是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数 组至少需要的存储字数就是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。 10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为front与rear,则当前队列中的元素个数就是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i 习题参考答案 一．选择题 1.从逻辑上可以把数据结构分为（C)两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.在下面的程序段中，对x的斌值语句的频度为（C)。 for( t＝1；k＜＝n;k＋＋） for（j=1;j＜＝n; j＋＋） x=x十1； A. O(2n) B. O (n) C. O (n2)． D. O（1og2n) 3.采用顺序存储结构表示数据时，相邻的数据元素的存储地址（A)。 A.一定连续B．一定不连续 C.不一定连续 D.部分连续，部分不连续 4.下面关于算法说法正确的是（D）。 A.算法的时间复杂度一般与算法的空间复杂度成正比 B.解决某问题的算法可能有多种，但肯定采用相同的数据结构 C.算法的可行性是指算法的指令不能有二义性 D.同一个算法，实现语言的级别越高，执行效率就越低 5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。 A.正确性 B.健壮性 C.可读性 D.可移植性 二、判断题 1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√） 2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（×） 3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×） 4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×） 5.算法必须有输出，但可以没有输人。（√） 三、筒答题 1．常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？ 【答】常见的四种逻辑结构： ①集合结构：数据元素之间是“属于同一个集合” ②线性结构：数据元素之间存在着一对一的关系 ③树结构：数据元素之间存在着一对多的关系 ④结构：数据元素之间存在着多对多的关系。 常见的四种存储结构有： ①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。 ②链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。 ③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。 ④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。 2．简述算法和程序的区别。 【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相 目录： 1、数据结构 2、算法的设计原则 3、总结 正文： 本系列博客我们将学习数据结构和算法，为什么要学习数据结构和算法，这里我举个简单的例子。 编程好比是一辆汽车，而数据结构和算法是汽车内部的变速箱。一个开车的人不懂变速箱的原理也是能开车的，同理一个不懂数据结构和算法的人也能编程。但是如果一个开车的人懂变速箱的原理，比如降低速度来获得更大的牵引力，或者通过降低牵引力来获得更快的行驶速度。那么爬坡时使用1档，便可以获得更大的牵引力；下坡时便使用低档限制车的行驶速度。回到编程而言，比如将一个班级的学生名字要临时存储在内存中，你会选择什么数据结构来存储，数组还是ArrayList，或者HashSet，或者别的数据结构。如果不懂数据结构的，可能随便选择一个容器来存储，也能完成所有的功能，但是后期如果随着学生数据量的增多，随便选择的数据结构肯定会存在性能问题，而一个懂数据结构和算法的人，在实际编程中会选择适当的数据结构来解决相应的问题，会极大的提高程序的性能。 1、数据结构 数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 一、数据结构的基本功能 ①、如何插入一条新的数据项 ②、如何寻找某一特定的数据项 ③、如何删除某一特定的数据项 ④、如何迭代的访问各个数据项，以便进行显示或其他操作 二、常用的数据结构 这几种结构优缺点如下：先有个大概印象，后面会详细讲解！！！ 算法简单来说就是解决问题的步骤。 在Java中，算法通常都是由类的方法来实现的。前面的数据结构，比如链表为啥插入、删除快，而查找慢，平衡的二叉树插入、删除、查找都快，这都是实现这些数据结构的算法所造成的。后面我们讲的各种排序实现也是算法范畴的重要领域。 第七章树 PROBLEM 2 (1/1 分) 一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）There is a full k-ary tree, whose depth is h. How many nodes can it have at most? (The depth of a tree, which only has a root node, is 0.) k^(h-1) k^h (k^(h+1)-1)/(k-1) (k^(h+1)-1)/(k-1) - 正确 (k^h-1)/(k-1) Explanation 层数---节点数 number of levels---number of nodes 0---1 1---k 2---k^2 3---k^3 .... h---k^h 所以答案是： so, the answer is： 1+k+k^2+k^3+...+k^h = (k^(h+1)-1)/(k-1) PROBLEM 3 (1/1 分) 2-3树是一种特殊的树，它满足两个条件： （1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同； 如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。(多项) 2-3 tree is a special kind of tree, it satisfy: （1）Every internal node has 2 or 3 child nodes. (2)All the leaf nodes have the same length of the path to the root node. If a 2-3 tree has 9 leaf nodes, then it may have __________ non-leaf nodes.（There are more than one correct answers） 4, 7, - 正确 4 5 6 7 Explanation 倒数第二层若是3个结点，深度为2，加上根结点，一共4个非叶子结点。 倒数第二层若是4个结点，深度为3，倒数第三层（第二层）有2个结点，一共4+2+1=7个非叶子结点。 If the second level from the bottom has 3 nodes, the depth of tree will be 2, and the tree will has 4 non-leaf nodes, including the root node. If the second level from the bottom has 4 nodes, the depth of tree will be 3, the third level from the bottom will has 2 nodes, and the tree will has 4+2+1=7 non-leaf nodes 学院 《数据结构与算法》之实际应用 二零一三年三月十三日 目录 数据结构与算法在实际中的应用 (2) 摘要： (2) 一、定义：............................ 错误！未定义书签。 二、在各领域中的实际应用.............. 错误！未定义书签。 （一）、排队叫号系统（尾插法） (2) （二）、搜索引擎与数据结构算法 (4) （三）、图论应用 (5) （四）、最小生成树在城市高速公路问题中的应用 (5) 三、小结 (6) 四、参考文献 (6) 小组成员： 数据结构与算法在实际中的应用 摘要： 计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理。何为信息，信息就是大量的数据，需要对大量的数据进行处理。进而我们需要《数据结构与算法》这门课作为基础，去发展计算机学科。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。通过《数据结构与算法》的学习，我们能够解决很多学科问题、生活实际问题。 一、定义 《数据结构与算法》应该包括两个部分：数据结构、算法。 数据结构在计算机科学界至今没有标准的定义。根据各自的理解的不同而有不同的表述方法，数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用时间复杂度和空间复杂度衡量。 二、在各领域中的应用 在我们的日常生活中，应用到数据结构的地方有很多地方，实例到处都是，比如说，做搜索引擎，对字符串的各种查找、索引的算法就有很高要求；做人工智能，对模式识别、搜索的要求就很高；做数据库设计，对字典、内外排序、搜索与索引以及数据的连接方式都有很高要求；做通讯密码，对数论、Fourier分析有要求等等。 （一）、排队叫号系统（尾插法） 数据结构包含数的操作,排序和查找等一系列问题。其中，排序的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的排列。数据结构的排序有5种。 常用的大数据结构与算法 在学习了解这些数据结构和算法之前，引用一位前辈的话： “我们不需要你能不参考任何资料，实现红黑树；我们需要的是你能在实践当中，选择恰当的数据结构完成程序开发；在必要的时候，能在已有的数据结构基础上进行适当改进，满足工程需要。但要做到这一点，你需要掌握基础的算法和数据结构，你需要理解并应用一些高级数据结构和算法的思想。因此，在程序员这条道路上，你要想走得更远，你需要活用各种数据结构，你需要吸收知名算法的一些思想，而不是死记硬背算法本身。” 那么，工程实践当中，最常用的算法和数据结构有哪些？ 以下是Google工程师Arjun Nayini在Quora给出的答案，得到了绝大多数人的赞同。 最常用的算法 1.图搜索算法(BFS,DFS) 2.排序算法 3.通用的动态规划算法 4.匹配算法和网络流算法 5.正则表达式和字符串匹配算法 最常用的数据结构 1.图，尤其是树结构特别重要 2.Maps结构 3.Heap结构 4.Stacks/Queues结构 5.Tries树 其他一些相对比较常用的数据算法还有：贪心算法、Prim’s / Kruskal’s算法、Dijkstra’s 最短路径算法等等。 怎么样才能活用各种数据结构？ 你能很清楚的知道什么时候用hash表，什么时候用堆或者红黑色？在什么应用场景下，能用红黑色来代替hash表么？要做到这些，你需要理解红黑树、堆、hash表各有什么特性，彼此优缺点等，否则你不可能知道什么时候该用什么数据结构。 常言道： 程序=算法＋数据结构 程序≈数据结构 小编希望这些算法的掌握能够帮助大家拓宽握数据结构和算法的视野，提高算法设计和动手编程的能力。 [试题分类]：数据结构与算法 1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。 A.操作 B.存储映像 C.关系 D.数据元素 答案:C 题型:单选题 知识点:1.2 基本概念和术语 难度:1 2.一般而言，最适合描述算法的语言是( )。 A.自然语言 B.计算机程序语言 C.介于自然语言和程序设计语言之间的伪语言 D.数学公式 答案:C 题型:单选题 知识点:1.4 算法和算法分析 难度:1 3．在下列序列中，不是线性表的是( )。 A. (‘a’,‘b’) B. (a, b) C. (‘AB’,‘CD’) D. (‘a’, b) 答案:D 题型:单选题 知识点:2.1 线性表的类型定义 难度:2 4.对于顺序表的优缺点，以下说法错误的是( )。 A.插入和删除操作较方便 B.可以方便地随机存取表中的任一结点 C.无需为表示结点间的逻辑关系而增加额外的存储空间 D.由于顺序表要求占用连续的空间，存储分配只能预先进行 题型:单选题 知识点:2.2线性表的顺序表示和实现 难度:2 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。 A. s->next=p->next;p->next=s; B. p->next=s->next;s->next=p; C. q->next=s;s->next=p; D. p->next=s;s->next=q; 题型:单选题 知识点:2.3线性表的链式表示和实现 难度:2 6.若某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。 A.单链表 B.带头结点的单链表 C.单循环链表北大2015年秋季学期数据结构课程作业
数据结构与算法试题
数据结构与算法第三版第章参考答案
数据结构与算法分析
北大PKU 慕课 EDX 数据结构与算法 第七章图 quiz答案与解析
数据结构与算法实际应用
常用的大数据结构与算法
数据结构与算法
相关主题
文本预览