本文内容详情如下：
引论
1
【单选题】1.在数据结构中,从逻辑上可以把数据结构分成( )。C
?A、动态结构和静态结构
?B、紧凑结构和非紧凑结构
?C、线性结构和非线性结构
?D、内部结构和外部结构
2
【单选题】2. 在数据结构中,从存储结构上可以将之分为( )。B
?A、动态结构和静态结构
?B、顺序存储和非顺序存储
?C、紧凑结构和非紧凑结构
?D、线性结构和非线性结构
3
【单选题】3. 某算法的时间复杂度是O(n^2),表明该算法的( )。A
?A、执行时间与n^2成正比
?B、问题规模是n^2
?C、执行时间等于n^2
?D、问题规模与n^2成正比
4
【单选题】4. 在下面的程序段中,x=x+1;的语句频度为( )。错误or( i=1;i<=n;i++) 错误or( j=1;j<=n;j++) x=x+1; C
?A、O(2n)
?B、O(n)
?C、O(n^2)
?D、O(log2n)
【单选题】5. 以下数据结构中,( )是非线性数据结构。A
?A、树
?B、字符串
?C、队
?D、栈
6
【单选题】6. 顺序存储,存储单元的地址( )。A
?A、一定连续
?B、一定不连续
?C、不一定连续
?D、部分连续,部分不连续
7
【单选题】7.评价一个算法性能好坏的重要标准是( )。C
?A、算法的正确性
?B、算法易于调试
?C、算法的时间和空间复杂度
?D、算法易于理解
8
【单选题】8. 若需要利用形式参数直接访问修改实参值,则应将形参说明为( )参数。C
?A、值参数
?B、实地址
?C、指针
?D、地址参数
9
【判断题】9. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。错误
10
【判断题】10. 数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。正确
线性表
1
【单选题】1. 下述哪一条是顺序存储结构的优点()。D
?A、可方便地用于各种逻辑结构的存储表示
?B、插入运算方便
?C、删除运算方便
?D、存储密度大
2
【单选题】2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用()存储方式最节省时间。A
?A、顺序表
?B、双链表
?C、带头结点的双循环链表
?D、单循环链表
3
【单选题】3. 设某顺序表中第一个元素的地址是se(下标从1开始),每个结点占m个单元,则第i个结点的地址为()。A
?A、se+(i-1)×m
?B、se+(i+1)×m
?C、se+i×m
?D、se-i×m
4
【单选题】4. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间。B
?A、单链表
?B、仅有尾指针的单循环链表
?C、仅有头指针的单循环链表
?D、双链表
5
【单选题】5. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为()。A
?A、O(n)
?B、O(0)
?C、O(1)
?D、O(n^2)
6
【单选题】6. 在单链表指针为p的结点之后插入指针为s的结点,正确的操作是()。A
?A、s->nex 正确=p->nex 正确;p->nex 正确=s;
?B、p->nex 正确=s;s->nex 正确=p->nex 正确;
?C、p->nex 正确=s;p->nex 正确=s->nex 正确;
?D、p->nex 正确=s->nex 正确;p->nex 正确=s;
7
【单选题】7. 对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是()。 A ?A、head→nex正确==NULL;
?B、head==NULL;
?C、head→nex正确==he;
?D、head!=NULL;
8
【判断题】8. 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。正确9
【判断题】9. 顺序表适宜于顺序存取,而链表适宜于随机存取。错误
10
【判断题】10. 线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。正确
栈和队列
1
【单选题】1. 栈和队列都是( )。D
?A、限制存取点的非线性结构
?B、顺序存储的线性结构
?C、链式存储的非线性结构
?D、限制存取点的线性结构
2
【单选题】2. 设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后随即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是( )。A
?A、3
?B、6
?C、4
?D、2
3
【单选题】3. 设计一个判别表达式中括号是否匹配出现的算法,采用( )的数据结构最佳。A ?A、栈
?B、顺序表
?C、队列
?D、单链表
4
【单选题】4. 表达式a*(b+c)-d的后缀表达式是( )。A
?A、abc*+d-
?B、cb+a*d-
?C、abc+*d-
?D、abcd+*-
5
【单选题】5. 递归过程或函数调用时,处理参数及返回地址需要用一种( )的数据结构。A ?A、栈
?B、队列
?C、多维数组
?D、线性表
6
【单选题】6. 最大容量为n的循环队列,队尾指针为rear,队头指针为错误ron 正确,则队空的条件是( )。A
?A、rear== 错误ron 正确
?B、(rear+1)%n== 错误ron 正确
?C、rear+1== 错误ron 正确
?D、(rear-l)%n== 错误ron 正确
7
【单选题】7. 用带头结点的单链表表示队长大于1的队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时( )。A
?A、仅修改队头指针
?B、仅修改队尾指针
?C、队头、队尾指针都要修改
?D、队头,队尾指针都可能要修改
8
【单选题】8. 对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为( )。A
?A、O(1),O(n)
?B、O(n),O(n)
?C、O(1),O(1)
?D、O(n),O(1)
9
【判断题】9. 两顺序栈共享空间,也存在空间溢出问题。正确
10
【判断题】10.在对不带头结点的链队列作出队操作时,不会改变头指针的值。错误
无处不在的“辩论”
1
【单选题】在学习中，（D）才是最重要的。
?A、求合
?B、效率
?C、知识
?D、发现
2
【单选题】（B）是辩论的最终价值体现。
?A、争胜
?B、求和
?C、谋利
?D、口才
3
【判断题】权利被社会主流价值观念和判断所剥夺被称为显性剥夺。（错误）4
【判断题】学习的过程强调创造而不是模仿，尤其是思维创造。（正确）
辩论是一种“修养”
1
【单选题】下列选项中，哪位人物与“壕梁之辩”密切相关。（D）
?A、荀子
?B、墨子
?C、孙子
?D、庄子
2
【单选题】以下选项中错误表述“印象即真实”中“印象”一词的是（A）。
?A、是完整的、全部的
?B、有可能是真实的歪曲
?C、有可能是片断性的
?D、观察者的主观感知
3
【判断题】“白马非马”与“子非鱼，安知鱼之乐也”都是倾向于认知层面的辩论。（正确）4
【判断题】“本分而理”强调的是讨论具体事实和细节。（错误）
辩论的“真善美”
1
【单选题】（B）是辩论的最高层次。
?A、辞藻的华丽
?B、诗意的栖息
?C、肉体的搏斗
?D、完全的胜利
2
【判断题】信息的碎片化不会使我们对世界的认知有任何偏差。（错误）
3
【判断题】
价值观念的输出是交流的终极目的。（正确）
概念的内涵和外延
1
【单选题】在辩论中，如果将高考移民视为异地高考，这是D。
?A、模糊概念
?B、模糊内容
?C、偷换内容
?D、偷换概念
2
【单选题】将异地高考限定于外来务工子女异地参加高考，其实是为了（C）。
?A、扩大内涵
?B、扩大外延
?C、缩小外延
?D、缩小内涵
3
【单选题】概念的（B）是指概念最本质的对社会、对外界的反应。
?A、内容
?B、内涵
?C、范围
?D、外延
4
【判断题】异地高考的外延小于高考移民的外延。（错误）
5
【判断题】概念可以囊括的社会现象、同类事物等更多，也就是外延过大。（正确）
概念的定义
1
【单选题】以事实判断为主的概念和以（D）为主的概念，是辩题中经常出现的两类概念。?A、主观臆断
?B、客观存在
?C、群体意念
?D、价值判断
2
【单选题】在辩论教育公平时，可以暂且不考虑下列哪个因素？（C）
?A、资源分配合理
?B、结果公平
?C、性别平等
?D、机会均等
3
【单选题】“网络反腐是利大于弊还是弊大于利”应属于下列哪种辩题？（B）
?A、判断性辩题
?B、比较性辩题
?C、猜测性辩题
?D、事实性辩题
4
【判断题】在辩论中，进一步论辩的基础是对概念所具有的内涵和外延进行分析。（正确）5
【判断题】公平的全部内涵就是机会均等。（错误）
概念的对抗
1
【单选题】弱化对方认为对自己最有利的概念，对（D）是有益处的。
?A、压迫我方概念空间
?B、扩充对方概念空间
?C、平衡我方概念空间
?D、压迫对方概念空间
2
【单选题】（B）是辩论中第一个层次的对抗。
?A、价值对抗
?B、概念对抗
?C、行为对抗
?D、意义对抗
3
【多选题】概念对抗需考虑以下哪些因素？（ABC）
?A、底线
?B、概念的对抗性
?C、包容性
?D、交互性
4
【判断题】辩论中最高包容性的对抗，就是用对方概念作为本方概念的基石。（正确）
5
【判断题】概念持平的意思是概念偏向于一方，但其内涵和外延均不可跨界。（错误）杀人游戏中的价值判断
1
【单选题】辩论中，4号同学坚持投给1号，最终造成平局，其背后可能的原因是（C）。?A、角色同一
?B、价值消失
?C、价值失真
?D、判断正确
2
【单选题】（B）是平民、警察、杀手形成博弈的基础。
?A、相同的主体
?B、不同的价值目标
?C、不同的陈词
?D、相同的价值目标
3
【单选题】辩论中，四位同学在首轮发言中集体“装好人”，这是A的表现。
?A、角色感不强
?B、进入角色快
?C、了解角色
?D、角色感强
4
【判断题】在杀人游戏中，思考和判断要保持行为一致，逻辑上可以不一致。（错误）杀人游戏中的角色代入
1
【单选题】杀人游戏与社会生活均要求个体在活动中要主动（B）。
?A、抵抗
?B、参与
?C、操纵
?D、顺从
2
【单选题】2号在辩论中面对1号的指责，立即认定1号是杀手，这是2号陷入了（A）。?A、个体价值对抗误区
?B、群体行为对抗误区
?C、个体行为对抗误区
?D、群体价值对抗误区
3
【多选题】杀人游戏需要特别注意的事项有哪些？（ABC）
?A、精力集中
?B、角色融入感
?C、整体局势分析
?D、个体价值
4
【判断题】在杀人游戏中，每个人必须充分考虑全局，不需要考虑体验角色。（错误）辩论中的价值博弈
1
【单选题】人们对同性家庭收养的儿童是否有正常的社会生活持不同看法，这是（C）的体现。
?A、相同个体，不同价值
?B、不同个体、相同价值
?C、不同个体、不同价值
?D、相同个体，相同价值
2
【单选题】
（C）是辩论的最佳结果。
?A、
决胜
?B、
顺从
?C、
求合
?D、
搏斗
3
【判断题】辩论中，对价值主体的定义越少，辩论越容易操控。（正确）
4
【判断题】
任何一种现象的背后涵盖的价值主体和价值判断都不止一种。（正确）
5
【判断题】在存在冲突和博弈的价值空间里，具有可以独立进行价值判断的个体，这就是价值主体。（正确）
事实判断与价值判断
1
【单选题】辩论中，坚持或者反对某种观点的切入点可以是（D）。
?A、行为
?B、人员
?C、意义
?D、概念
2
【多选题】立论框架分为哪三个层次？（BCD）
?A、主观臆断
?B、概念
?C、逻辑论证
?D、价值判断标准
3
【多选题】以下属于“价值判断标准”的评判维度的有（ABD）。
?A、价值主体
?B、正交
?C、正趋
?D、正当
4
【判断题】在本方定义不够清晰明确的情况下，也可以轻而易举地攻击对方概念。（错误）5
【判断题】概念、价值主体以及二者关系对辩论思路和内容没什么影响。（错误）
立论中的概念
1
【单选题】辩者在“时势造英雄”的辩题中应该对（C）概念特别明确。
?A、英雄
?B、时势
?C、造、时势
?D、造
2
【单选题】在“人性本善”与“人性本恶”的辩论中，“人性本恶”想要取胜应将重点放在（C）。?A、对“恶”的明确界定
?B、对“本”的模糊界定
?C、对“本”的明确界定
?D、对“恶”的模糊界定
3
【判断题】逻辑论证是不能构成主要论证战场体系的。（错误）
4
【判断题】辩论中，被接受性差课由于价值主体过于集中导致。（正确）
5
【判断题】逻辑论证中，价值主体与价值判断应遵循价值主体不宜过于集中，价值判断不宜过于繁杂。（正确）
辩论中如何抓住“主干”
1
【单选题】（B）是逻辑论证的最终目标。
?A、价值表现
?B、价值升华
?C、价值泛化
?D、价值判断
2
【单选题】下列哪个选项可引起战场失衡？（A）
?A、泛化或狭隘概念
?B、多方面呈现概念
?C、呈现多层次概念
?D、明确表述概念
3
【多选题】以下对升华的概念表述正确的有（ABC）。
?A、升华不是为了煽动情绪
?B、是为了引领到终极的辩论意义。
?C、是为了发现共鸣之处
?D、是对具体事例或具体辩论价值主体的描述。
4
【判断题】立论的深度、广度是由看到的概念的层数所决定的。（正确）
5
【判断题】辩论中，辩者不能盲目泛化概念，而是要对论辩的范围、过程进行精准的控制。
（正确）
Java数据结构和算法 一、数组于简单排序 (1) 二、栈与队列 (4) 三、链表 (7) 四、递归 (22) 五、哈希表 (25) 六、高级排序 (25) 七、二叉树 (25) 八、红—黑树 (26) 九、堆 (36) 十、带权图 (39) 一、数组于简单排序 数组 数组（array）是相同类型变量的集合，可以使用共同的名字引用它。数组可被定义为任何类型，可以是一维或多维。数组中的一个特别要素是通过下标来访问它。数组提供了一种将有联系的信息分组的便利方法。 一维数组 一维数组（one-dimensional array ）实质上是相同类型变量列表。要创建一个数组，你必须首先定义数组变量所需的类型。通用的一维数组的声明格式是：type var-name[ ]; 获得一个数组需要2步。第一步，你必须定义变量所需的类型。第二步，你必须使用运算符new来为数组所要存储的数据分配内存，并把它们分配给数组变量。这样Java 中的数组被动态地分配。如果动态分配的概念对你陌生，别担心，它将在本书的后面详细讨论。 数组的初始化（array initializer ）就是包括在花括号之内用逗号分开的表达式的列表。逗号分开了数组元素的值。Java 会自动地分配一个足够大的空间来保存你指定的初始化元素的个数，而不必使用运算符new。 Java 严格地检查以保证你不会意外地去存储或引用在数组范围以外的值。Java 的运行系统会检查以确保所有的数组下标都在正确的范围以内（在这方面，
Java 与C/C++ 从根本上不同，C/C++ 不提供运行边界检查）。 多维数组 在Java 中，多维数组（multidimensional arrays ）实际上是数组的数组。你可能期望，这些数组形式上和行动上和一般的多维数组一样。然而，你将看到，有一些微妙的差别。定义多维数组变量要将每个维数放在它们各自的方括号中。例如，下面语句定义了一个名为twoD 的二维数组变量。 int twoD[][] = new int[4][5]; 简单排序 简单排序中包括了：冒泡排序、选择排序、插入排序； 1.冒泡排序的思想： 假设有N个数据需要排序，则从第0个数开始，依次比较第0和第1个数据，如果第0个大于第1个则两者交换，否则什么动作都不做，继续比较第1个第2个…，这样依次类推，直至所有数据都“冒泡”到数据顶上。 冒泡排序的的java代码： Public void bubbleSort() { int in,out; for(out=nElems-1;out>0;out--) for(in=0;in
实验报告 课程名称:数据结构与算法 实验名称:树的应用 一、实验目的 ⑴、掌握二叉树的静态数组存放。 ⑵、掌握哈夫曼编码的基本概念。 ⑶、掌握哈夫曼编码树的构造方法。 ⑷、掌握哈夫曼编码的构造和使用。 ⑸、理解前缀编码的概念。 二、实验内容 ⑴、按照字符出现概率构造一个哈夫曼树。要求输入为一个文本文件（可以限 制文本仅仅包含字母），通过统计字符出现的次数计算概率，在此基础上构造哈夫曼树。 ⑵、打印出每一个字母对应的哈夫曼编码。 三、实验环境 硬件：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表示队列满
《数据结构与算法》期末复习题 一、选择题。 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 学生学号Xxx实验课成绩 学生实验报告书 实验课程名称数据结构与算法综合实验 开课学院计算机科学与技术学院 指导教师姓名xxx 学生姓名xxx 学生专业班级xxxx 2015--2016学年第2学期 实验课程名称：数据结构与算法综合实验 实验项目名称二叉树与赫夫曼图片压缩报告成绩 实验者xx专业班级xxx组别 同组者完成日期2016年5月 2日第一部分：实验分析与设计（可加页） 一、实验目的和要求 1.目的 掌握树的存储结构 掌握二叉树的三种遍历方法 掌握 Huffman树、Huffman编码等知识和应用 使用 C++、文件操作和 Huffman算法实现“图片压缩程序”专题编程。 2.要求 针对一幅 BMP 格式的图片文件，统计 256 种不同字节的重复次数，以每种字 节重复次数作为权值，构造一颗有 256 个叶子节点的哈夫曼二叉树。 利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。 压缩后的文件与原图片文件同名，加上后缀.huf （保留原后缀），如 pic.bmp 压 缩后 pic.bmp.huf 二、分析与设计 依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为： ① 读取图片文件、统计权值 ②生成 Huffman树 ③生成 Huffman编码 ④ 压缩图片文件 ⑤ 保存压缩的文件 1.数据结构的设计 记录统计 256种不同字节的重复次数使用整型数组。 int weight[256] = { 0 }; 二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方 式存储二叉树。 Huffman编码存储结构 struct HTNode { int weight;//权值 数据结构与方法 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、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列, 四川大学期末考试试题 （2008-2009学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师： 1．数据类型为（）。 A）数据项的集合B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合D）关键字的集合 2．链表不具有的特点是（）。 A）可随机直接访问任一元素B）插入删除不需要移动元素 C）不必事先估计元素个数D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵A nxn压缩存储在一维数组B[m]中，则m的值至少为（）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A）2k-1-1 B）2k-1C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGH IJ 中序序列：CBEDAGHFJI 注：试题字迹务必清晰，书写工整。本题2页，本页为第1页 教务处试题编号： 数据结构与算法课程设计报告 题目 两两相连的房间问题： 一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？ 问题分析 此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。 实现本程序需要解决以下问题： 1.如何表示每一个房间，即存储房间的信息，并且还要确定这所房子里的各个房间的位置。 2.各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。 3.从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。 4.为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只 访问未走过的房间。 5.最后通过什么的遍历方式才能判断各个房间之间是否互相相通。 数据结构的选择和概要设计 通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a 房间的，从而可知该图为有向图，那么门就相当于有向图中的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。 对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。定义一个全局的整形变量flag，如果是连通图的话则flag=1，否则flag=0。 程序实现的流程图如下： 《数据结构》课程设计任务书 学期：11-12-2 班级：网络10 一、设计目的 《数据结构》是一门实践性较强的专业基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 二、设计要求 1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。 3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。 4、编程语言任选。 三、设计选题 题一：线索二叉树（**） 任务： 1.建立中序线索二叉树，并且中序遍历； 2.求中序线索二叉树上已知结点中序的前驱和后继； 需求分析和概要设计： 建立中序线索二叉树，并且中序遍历。首先就是要建立树，再将树中序线索化。求中序线索二叉树上已知结点中序的前驱和后继时，即是将树在遍历一遍。也可以在遍历的过程中，将树的结点放在数组中，当然必须讲述先遍历一遍，这是用空间来换时间。 详细设计： 树的结构体的声明： typedef char TElemtype; typedef enum PointerTag{Link,Thread}; //设置标志：Link为指针，Thread为线索typedef struct BiThrNode{ //树结点结构体 TElemtype data; struct BiThrNode *lchild,*rchild; PointerTag LTag,RTag; }BiThrNode,*BiThrTree; 相关函数的声明： 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; /*插入成功*/ } 北京交通大学考试试题（A卷） 课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为 的数据结构。 2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。 3. 直接插入排序用监视哨的作用是。 4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算 是。 5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有。 6. 在AOV网中，顶点表示，边表示。 7. 有向图G可进行拓扑排序的判别条件是。 8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行 Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。 二、选择题（每空2分，共20分） 1.在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法B．孩子链表表示法 C．孩子兄弟表示法D．顺序存储表示法 2.查找n个元素的有序表时，最有效的查找方法是（）。 A．顺序查找B．分块查找 C．折半查找D．二叉查找 3.将所示的s所指结点加到p所指结点之后，其语句应为（）。 p (A) s->next=p+1 ; p->next=s; (B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s; 4. 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。 A. 顶点v 的度 B. 顶点v 的出度 C. 顶点v 的入度 D. 依附于顶点v 的边数 5. 算法的时间复杂度为O （nlog 2n ）、空间复杂度为O(1)的排序算法是（ ）。 A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择 6. 设矩阵A 是一个对称矩阵，为了节省存储，将其 下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i ≤j), 在一维数组B 中下标k 的值是（ ）： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j 7. 由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下，查找成功的平均查找长度是（ ）。 A ．29/11 B. 31/11 C. 33/11 D.35/11 8. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。 A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为 （ ）。 A ．5 B ．6 C ．7 D ．8 三、 判断题（10分，每小题1分） 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 2. 数组不适合作任何二叉树的存储结构。（ ） 3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（ ） 4. 在含有n 个结点的树中，边数只能是n-1条。（ ） 5. 所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。（ ） 6. 简单选择排序在最好情况下的时间复杂度为O(n)。（ ） 7. 在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ） 8. 采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置 空，因为这会影响以后的查找。（ ） 9. 有n 个数存放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无 ?????? ? ???? ? ??=n n n n a a a a a a A ,2,1,2 ,21,21 ,1Λ Λ 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程 数据结构与算法 课程设计 名称 二叉排序树运算学生姓名顾成方 学号0704011033 专业班级08计科(2) 指导教师王昆仑张贯虹 2010 年 5 月 题目：（二叉排序树运算问题）设计程序完成如下要求：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。基本任务：⑴选择合适的储存结构构造二叉排序树；⑵对二叉排序树T作中序遍历，输出结果；⑶在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。 ⑷尽量给出“顺序和链式”两种不同结构下的操作，并比较。 一、问题分析和任务定义 本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。 实现本程序需要解决以下几个问题： 1、如何构造二叉排序树。 2、如何通过中序遍历输出二叉排序树。 3、如何实现多种查找。 4、如何实现插入删除等操作。 二叉排序树的定义： ⑴其左子树非空，则左子树上所有结点的值均小于根结点的值。 ⑵若其右子树非空，则右子树上所有结点的值大于根结点的值。 ⑶其左右子树也分别为二叉排序树。 本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。 本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确 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) 摘要： (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、在数据结构中，线性结构中元素之间存在____关系。 A: 一对一 B: 一对多 C: 多对一 D: 多对多 2、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的____和运算等的学科。 A: 结构 B: 关系 C: 操作 D: 算法 3、算法分析的两个主要方面是____。 A: 空间复杂度和时间复杂度 B: 正确性和简明性 C: 可读性和文档性 D: 数据复杂性和程序复杂性 4、顺序表中逻辑上相邻的节点其物理位置也____。 A: 一定相邻 B: 不必相邻 C: 按某种规律排列 D: 无要求 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; 6、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是____。 A: edcba B: decba C: dceab D: abcde 7、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。 A: (rear-front+m)%m B: rear-front+1 C: rear-front-1 D: rear-front 8、关于空格串，下列说法中正确的有____。 A: 空格串就是空串 B: 空格串是零个字符的串 C: 空格串的长度为零 D: 空格串的长度就是其包含的空格个数 9、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为____。A: SA+140 B: SA+144 C: SA+222 D: SA+225 10、对于一棵满二叉树，m个树叶，n个节点，深度为h，则____。 A: n=h+m B: h+m=2n C: m=h-1 D: n=2h-1 11、具有65个结点的完全二叉树其深度为____。（根的层次号为1） A: 8 B: 7 C: 6 D: 5 12、满二叉树____二叉树。 A: 一定是完全 B: 不一定是完全 C: 不是 D: 不是完全 13、将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为____。 A: 99 B: 98 C: 50 D: 48 14、如果T2是由森林T转换而来的二叉树，那么T中结点的后序遍历就是T2中结点的____。A: 先序遍历 B: 中序遍历 C: 后序遍历 D: 层次遍历 15、将递归算法转换成对应的非递归算法时，通常需要使用____。 A: 栈 B: 队列 C: 链表 D: 树 16、如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为____。 A: uwvts B: vwuts C: wuvts 1、线性表的各种基本操作在顺序存储结构上的实现均比在链式存储结构上的实现效率要低。( × ) 2、一个有向图的邻接表和逆邻接表中表结点的个数一定相等。( × ) 3、先序遍历森林和先序遍历与该森林相对应的二叉树，其结果不同。( √ ) 4、不使用递归，也可实现二叉树的先序、中序和后序遍历。( √ ) 5、散列法存储的基本思想是由关键字的值决定数据的存储地址。( √ ) 6、采用折半查找法对有序表进行查找总是比采用顺序查找法对其进行查找要快。( √ ) 7、在任何情况下，快速排序方法的时间性能总是最优的。( × ) 8. 二维数组是其数据元素为线性表的线性表。( × ) 9. 拓扑排序是一种内部排序方法。( × ) 10．数据的物理结构是指数据在计算机内实际的存储形式。( × ) 11、数据元素是数据的最小单位。( × ) 12、算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( √ ) 13、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( × ) 14、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( × ) 15、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 16、所谓取广义表的表尾就是返回广义表中最后一个元素。( × ) 17、完全二叉树中，若一个结点没有左孩子，则它必是树叶。( √ ) 18. 二叉树只能用二叉链表表示。( × ) 19．在二叉树的第i层上至少有2i-1个结点(i>=1)( × ) 20．度为二的树就是二叉树。( × ) 21. 有e条边的无向图，在邻接表中有e个结点。( × ) 22. 有向图的邻接矩阵是对称的。( × ) 23．任何无向图都存在生成树。( × ) 24. 不同的求最小生成树的方法最后得到的生成树是相同的. ( × ) 25. 有环图也能进行拓扑排序。( × ) 26. 关键路径是AOE网中从源点到终点的最长路径。( √ ) 27．内排序要求数据一定要以顺序方式存储。( × ) 28．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。( × ) 29．直接选择排序算法在最好情况下的时间复杂度为O（N）。( × ) 30．在待排数据基本有序的情况下，快速排序效果最好。( × ) 31．快速排序总比选择排序快。( √ ) 二．单选题（） 1. 单循环链表的主要优点是( D )。 A.不再需要头指针 B.已知某个结点的位置后，能够容易找到它的直接前趋 C.在进行插入，删除运算时，能更好地保证链表不断开 D.从表中任一结点出发都能扫描到整个链表 2. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( D )存储方式最节省时间。 A．顺序表B．单链表C．双链表D．单循环链表 3. 用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 4. 以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树 5. 图的深度优先遍历算法类似于二叉树的( A )，广度优先遍历算法类似于二叉树的( D )。 A．先序遍历B．中序遍历C．后序遍历D．层次遍历 6. 若广义表A满足Head(A)==Tail(A)，则A为( B )。 A. ( ) B. (( )) C. (( ),( )) D. (( ),( ),( )) 7. 下列二叉树中，( A )可用于实现符号的不等长高效编码。武汉理工大学数据结构与算法综合实验哈夫曼树(1)
数据结构与算法知识点必备
计算机学院数据结构与算法分析期末试题(2007级B)_无答案
大数据结构与算法课程设计程序及报告材料
数据结构树的有关算法
数据结构与算法第二版2-4章答案
北京交通大学数据结构与算法期末测验考试参考答案
二叉排序树运算-数据结构与算法课程设计报告_l
《数据结构与算法》课后习题答案
数据结构与算法实际应用
常用的大数据结构与算法
数据结构与算法上海第二工业大学二工大期末考试试卷
数据结构与算法设计期末复习资料
相关主题
文本预览