专业课资料附有答案

专业课资料[复制]名词解释：

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储和数据组织的方式，它分为三个方面，即数据的逻辑结构，数据的物理结构，数据的操作。

数据项：是数据不可分割的最小单位，用它可以识别一个或一个组数据，一个数据元素可由若干数据项组成。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中被计算机程序处理的符号的总称，是计算机化的信息。

数据类型：是一个值的集合以及定义在这个值集上的一组操作，可分为原子类型和结构类型。

抽象数据类型：是基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。

逻辑结构：是数据元素之间逻辑关系的描述。

物理结构（存储结构）：是指数据的逻辑结构在计算机中的映像（又称表示），即数据结构在计算机中的存储方法。

算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

时间复杂度：算法执行所需时间的量度。

空间复杂度：算法执行所需存储空间的量度。

存储密度：指结点数据本身所占存储量和整个结构所占存储量之比。

填空题：

程序设计的一些基本原则：分解、抽象和信息隐蔽。

根据数据元素之间关系的不同特性，有四类基本的数据结构：集合结构，线性结构，树形结构，图形结构（网状结构）。

数据的存储结构有：顺序存储结构、链式（链接）存储结构、索引结构、散列存储结构

常用的两种存储结构：顺序存储结构和链式存储结构。

算法的五个特性：确定性、有穷性、可行性、输入和输出。（可以有零个或多个数据输入，但必须至少有一个输出数据。

算法设计的要求：正确性、可读性、稳健性、高效率低存储量。

沃斯公式：程序=算法+数据结构。

（算法分析）衡量算法的两个标准：时间复杂度和空间复杂度。

一个算法的设计取决于所选的逻辑结构。

一个算法的实现取决于所选的存储结构。

结构化程序设计思想的要求：自顶向下、逐步细化、模块化设计、结构化编程。

简答题：

顺序存储结构的特点？（顺序存储和链式存储的优缺点）1、结点中只存放数据元素本身的信息，无附加内容。（优点）[填空题]_________________________________2、可直接存储数据元素。（优点）[填空题]_________________________________3、存储操作速度较快。（优点）[填空题]_________________________________4、插入、删除数据元素时，由于需要保持数据元素之间的逻辑关系，必须大量移动元素，因此实现起来比较慢。（缺点）[填空题]_________________________________5、顺序存储是一种静态结构、存储密度大，空间利用率低，预分配空间大小难以确定，（缺点）[单选题]*链式存储结构的特点？（顺序存储和链式存储的优缺点）(正确答案)1、结点中除存放数据元素本身的信息外，还需存放附加的指针。[填空题]_________________________________2、不能直接存取数据元素，需顺链路查找，存取速度较慢。[填空题]_________________________________3、插入、删除元素时不必移动其他元素，速度较快。（优点）[填空题]_________________________________4、链式存储是一种动态存储结构，空间利用率高，存储密度小，不存在预分配空间问题。[单选题]*线性结构与非线性结构的特点（或差异）？(正确答案)线性结构的特点：是除第一个元素和最后一个元素外，每个数据元素都有唯一的前驱和唯一的后继，第一个元素没有前驱，最后一个元素没有后继，关系是一对一的。非线性结构的特点是：表示结点间关系的前驱后继不具有唯一性，结点间是一对多或多对多的关系。逻辑结构与物理结构的区别和联系？1、数据的物理结构也为存储结构。[填空题]_________________________________2、数据的逻辑结构仅考虑数据之间的逻辑关系。[填空题]_________________________________3、数据的物理结构是数据的逻辑结构在计算机中的映像。[填空题]_________________________________4、数据的逻辑结构独立于数据的存储介质。[单选题]*数据结构与数据类型的区别和联系？(正确答案)数据结构是相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储和数据组织的方式，它分为三个方面，即数据的逻辑结构，数据的物理结构，数据的操作，它偏向于逻辑方面，而数据类型是一个值的集合以及定义在这个值上的一组操作，可分为原子类型和结构类型，它偏向于物理方面的线性表。名词解释：线性表：是最常用，最简单的一种数据结构，一个线性表是n个数据元素的有限序列，除首尾元素外，每个元素有唯一的前驱和唯一的后继。顺序表：采用顺序存储结构的线性表通常称为顺序表。链表：采用链式存储结构的线性表通常称为顺序表。结点：由数据元素和指示其后继结点地址的信息组成的存储映像称为结点。表长：表中元素的个数称为表的表长。循环链表：是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。双链表：采用链式存储结构的线性表，每个结点除一个数据域外，还有两个指针域，其一指向直接前驱，另一指向直接后继。静态单链表：是利用一块连续的空间，按链表的存储方式组织数据，按顺序存储结构分配空间，所构成的一种链表。头指针：是指向链表表头结点的指针，只要链表存在，该指针始终不会改变，单链表由头指针唯一确定，因单链表可以用头指针的名字来命名。头结点：在链表的开始结点之前附加的一个结点，是链表的表头，当链表不空时，其内的指针指向链表的第一个结点，当链表是空链表时，该指针为空指针。填空题：线性表的两种基本的存储结构：顺序结构和链式存储结构。从实现角度看，链表可分为静态链表和动态链表。从链接方式的角度看，链表可以分为单链表，循环链表，双链表。添加哨兵可以保持首指针的稳定性，方便表示空表。一元多项式的表示和相加可以使用链表实现。简答题：顺序表的优缺点？优点：1、无需为表示结点间的逻辑关系而增加额外的存储空间，存储密度大2．可随机存取表中的任一元素，查找方便[单选题]*缺点：1．插入，删除运算不方便，须移动大量元素，效率较低(正确答案)2．存在预分配空间问题[单选题]*链表的优缺点？(正确答案)优点：1．插入，删除操作很方便2．空间利用率高[单选题]*缺点：1．查找不方便，需顺链查找(正确答案)2．存储密度小[单选题]*顺序表和链表的区别和联系及适用范围？(正确答案)顺序表：内存中地址连续长度一般不可变更支持随机查找，可在O（1）内查找元素适用于需要大量访问元素的，而少量増删元素的程序链表：内存中地址连续或非连续都可以长度可实时变化不支持随机查找，查找元素的时间复杂度为O（n）适用于需要大量增删元素，而对访问元素几乎无要求的程序头指针和头结点的作用？1．头指针是指向链表表头结点的指针，只要链表存在，该指针就不会变化，已知该指针便己知该链表[填空题]_________________________________2．头结点是在链表的开始结点之前夫妇家的一个结点，当链表是空链表时，该指针为空指针，因此空表和非空表的处理也就统一了[单选题]*简述在单循环链表上尾指针取代头指针的作用？(正确答案)在用头指针表示的单循环链表中，找开始结点a1的时间是O（1），然而要找终端结点an则需要从头指针开始遍历整个链表，其时间是O（n），在很多实际问题中，表的操作常常是在表尾进行的，此时头指针表示的单循环链表就显得不够方便，如果改用尾指针来表示单循环链表，则查找开始结点a1和终端结点an都很方便查找时间都是O（1）名词解释：栈：也叫后进先出表，是限定仅在表尾进行插入和删除操作的线性表，表尾端称为栈顶，表头端称为栈底，不含元素的空表称为空栈顺序栈：采用顺序存储结构的栈称为顺序栈链栈：采用链式存储结构的栈称为链栈．队列：是一种先进先出的线性表，它只允许在表的一段进行插入，而另一端删除元素，允许插入的一端叫做队尾，允许删除的一端称为队首链队列：用链表示的队列，需要两个指针分别指示队头和队尾，为了操作方便，也给链队列添加一个哨兵结点循环队列：队列是＂先进先出表”，随着入队出队的进行，会使整个队列整体向后移动，当队尾指针移到最后，若再有元素入队就会出现“假溢出”，因为此时队头部分还有空间可用，循环队列是将队列的数据区看成头尾相接的循环结构，可解决“假溢出”双端队列：是限定插入，删除在表的两端进行的线性表，这两端分别称为端点。填空题栈的两种存储方式：顺序存储和链式存储满的判断条件：s.top＝stack.size栈空的判断条件：s.top＝0栈满入栈栈上溢，栈空出栈栈下溢链栈使用多栈共享技术时，可使用静态链表结构实现队列的两种存储方式：顺序存储和链式存储循环队列采用少用一个元素存储空间的办法下，判断队列满的条件：front==（rear+1）%size循环队列判断队列满的方法有：少用一个元素存储空间，增设一个标志量，使用计数器队列的应用：杨辉三角栈的应用：数制转换，括号匹配，表达式求值，汉诺塔（递归用栈实现）简答题：什么是多栈共享技术？在一个程序中经常会同时使用多个栈，使用顺序存储结构的栈．空间大小难以估计，这样使得有的栈已出，有的栈还有空闲空间，可以让多个栈共享一个足够大的连续向量空间（数组），通过利用栈的动态特性来使其存储空间互相补充，这就是多栈的共享技术，两个栈共享空间，主要利用了“栈底位置不变，栈顶位置动态变化”的特性顺序队列相比，循环队列有哪些优点？可解决假溢出现象（内容自行拓展）简述线性表

栈，队列的区别和联系？相同点：都是线性结构，都是逻辑结构的概念，都可以用顺序存储或链式存储，栈和队列是两种特殊的线性表，即受限的线性表，只对插入和删除运算加以限制不同点：1，运算规则不同，线性表为随机存取，而栈只允许在一端进行插入、，删除运算，因而是后进先出表，队列只允许在一端进行插入，另一端删除运算，因而是先进先出表2．用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理，指[单选题]*令寄存及其他运算等(正确答案)串：是由零个或多个字符組成的有限序列．子串：串中任意个连续的字符组成的子序列称作该串的子串主串：包含子串的串相应的称为主串子串在主串中的位置：子串的第一个字符在主串中的位置表示空串：长度为零的串称为空串空格串：串中元素均为空格的串称为空格串．串相等：长度相等且对应位置字符都相等在程序中，串分为串常量和串变量串的存储结构：顺序存储结构，链式存储结构，堆存存储结构串的应用：文本編辑串和线性表的区别？串的逻辑结构与线性表极为相似，区别仅在于串的数据对象约束为字符集，然而串的操作与线性表有很大的差别，在线性表基本操作中，大多以单个元素作为操作对象；而在串的基木操作中通常以“串的整体”作为操作对象简述静态分配的顺序串与动态分配的顺序串的区别？程序运行前被分配以一个给定大小的数组空间的顺序串称为静态顺序串，在程序运行过程中，动态分配空间能以链表形式存在的顺序串称为动态顺序串，静态申在内存一片连续的数据区中，动态串在内存堆中．串的链式存储与串顺序存储相比，在哪些操作上效率更高？插入，删除，因为无需移动其他元素（内容自行扩充）广义表：是由零个或多个单元素或子表所构成的有限序列，是线性表的推广，也有人称其为列表数组：类型一致的有限个数据元素按顺序连续存储矩阵的压缩存储：有的矩阵中有许多值相同元素或者是零元素，为了节省存储空间对这类矩阵采用多个值相同的元素只分配一个存储空间，有时零元素不存储的存储策略，称为矩阵的压缩存储特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律的矩阵称为特殊矩阵稀疏矩阵：非零的数据元素个数很少的矩阵称为稀疏矩阵对称矩阵：一个n阶方阵，若满足aij=aji，则称该矩阵为对称矩阵三角矩阵：主对角线上方和下方的元素（不包括对角线）均为常数或零元素的矩阵行表：记录稀疏矩阵中每行非零元素在三元组表中的起始位置的表三元组表：若线性表顺序存储的每一个结点均是三元组，则该线性表的存储结构称为三元组表带状矩阵：所有非零元素均集中在以主对角线为中心的带状区域的矩阵数组的两种存储方式：顺序存储和链式存储．数组的顺序存储有两种方式：按行存储和按列存储．稀疏矩阵可以采用三元组表和十字链表来存储广义表和线性表的区别？1广义表是线性表的推广，是由零个或多个单元素或子表所构成的有限序列[填空题]_________________________________2．线性表的成分都是结构上不可分制的单个数据元素，而广义表的成分既可以是单元素，也可以是有结构的表其定义是递归的定义[单选题]*名词解释：(正确答案)树：是n个结点的有限集合，n≥0，有且只有一个称为根的结点，根结点无前驱有序树：树中结点的各子树看成是从左至右依次有序的，且不能交换森林：m（m≥1）棵互不相交的树的集合二叉树：是一种树型的结构，它的特点是每个结点之多有两棵子树，且有左右之分，不可任意颠倒。完全二又树：深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时满二叉树：是一棵深度为k的，且有（2^k）-1个结点的二又树遍历二叉树：是按照某种搜索路径巡访二叉树中的每个结点，使得这些结点均被访问一次线索二叉树：由每个结点中包含左指针，左标志位，数据域，右标志位，右指针五部分组成的二叉链表，叫做线索链表，指向前驱或后继的指针叫做线索，以二又树某种遍历顺序给空指针加线索的过程叫做线索化，线索化了的二叉树称为线索二叉树哈夫曼树：又称最优二叉树，是一类带权路径长度最短的树．哈夫曼编码：在哈夫曼树中，约定左分支代表0，右分支代表1，把叶子结点到根结点的路径上的左右分支代表的码从下至上一次连接起来，组成的字符串称为该叶子结点的哈夫曼编码，这就是哈夫曼编码二又排序树：或者是空树，或者是符合以下性质的二叉树1若它的左子树不空，则左子树上所有结点均小于它的根结点值[填空题]_________________________________2．若它的右子树不空则右子树上所有结点均大于它的根结点值．[单选题]*平衡二叉排序树（AVL树）：或者是空树，或者是符合一下性质的二又排序树(正确答案)1．左子树和右子树的高度之差的绝对值小于等于1[填空题]_________________________________2左子树和右子树也是平衡二叉排序树[单选题]*在二叉树中，第i层结点最多为2^k—1个深度为k的二又树中，结点总数最多为（2^k）—1个二叉树中，n0＝n2＋1，n2＝n0－1（no为二又树中度为0的结点的个数n2为二叉树中度为2的结点的个数）有n个结点的完全二叉树，深度为k，则k＝[log2n]＋1（log以2为底括号是向下取整不是方括号）k层的完全二叉树至少有2^k－2个叶子结点二叉树的两种存储结构：顺序存储结构和链式存储结构树的三种常用的存储方法：孩子表示法，双亲表示法和孩子兄弟表示法树的遍历方法：先根遍历和后根遍历简答题1非线性结构的特点？表示结点间关系的前驱后继不具有唯一性，结点间是一对多或多对多的关系二叉树的五种基本形态？只有三个结点的二叉树的五种形式？因为二又树是有序树，所有有左右之分，这是五棵不同的二叉树，但若下列五棵是树，不是二叉树，则后面四种为同一棵树名词解释：1图：图G由两个集合V和E组成，记为G＝（V，E），其中V是顶点的有穷非空集合，E是由V中顶点的序偶组成的有穷集，这些序偶称为边或弧完全图：边数恰好等于n（n－1）/2的n个顶点的无向图称为完全图（无向图中任意两个顶点之间都有一条边相连，称该图为完全图）有向完全图：有n(n-1）条边的有向图称为有向完全图（图中每个顶点和其余n-1个顶点都有弧相连）入度：以顶点V为头的弧的数目称为V的入度出度：以顶点V为尾的弧的数目称为V的出度连通图：在无向图中，任意两个顶点之间都有路径相通强连通图：在有向图中，任意两个顶点之间都有来回路径相通生成树：生成树是无向连通图的一个极小连通子图，它含有图中的全部顶点和使任意顶点都连通的最少的边邻接矩阵：表示图中结点之间关系的矩阵称为邻接矩阵邻接表：由顶点数据表和表示数据关系的边（弧）构成的表十字链表：可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种存储形式图的遍历：从某一顶点出发按序访问图中所有结点，且使每个结点仅被访问一次最小生成树：无向网中边上权值之和为最小的生成树DAG：有向无环网拓扑排序：由某个集合上的一个偏序得到该集合上一个全序的操作称为拓扑排序关键路径：在AOE网中，从源点到汇点的最长路径称为关键路径AOE网：用顶点表示事件，用弧表示活动，弧的权值表示活动所需的时间，构造的有向网称为AOE网简单路径：一条路径上除了开始顶点和结束顶点外，其余顶点均不相同弧头：边的终点称为弧头弧尾：边的始点称为弧尾填空题：1边很少的图称为稀疏图，反之称为稠密图有向图中，所有顶点的入度与出度的和等于边个数的2倍图的存储方法：邻接矩阵，邻接表，邻接多重表，十字链表和边集数组图的深度优先搜索类似于树的先根遍历(正确答案)图的广度优先搜索类似于树的层次遍历连通图→深度优先搜索遍历→深度搜索生成树连通图→广度优先搜索遍历→广度搜索生成树简答题111邻接矩阵表示法的特点？1．对于无向图而言，它的邻接矩阵是对称矩阵，因此可以采用特殊矩阵的压缩存储法，但对于有向图而言，其中的弧是有方向的，因此有向图的邻接矩阵不一定是对称矩阵，对于有向图的邻接矩阵的存储则需要n*n个存储空间．[填空题]_________________________________2．采用邻接矩阵表示法，便于判断图中任意两个顶点之间是否有边相连，即根据邻接矩阵中的信息来判断，另外还便于求得各个顶点的度，对于无向图而言，其邻接矩阵第i行元素之和就是图中第i个顶点的度[单选题]*邻接表表示法的特点？(正确答案)1．n个顶点，e条边的无向图，若采取邻接表作为存储结构，需要n个顶点数据和2e个表示边的结点，显然在边很稀疏的情况下，用邻接表存储所需的空间比邻接矩阵所需的空间少[填空题]_________________________________2．无向图的度，在无向图的邻接表中，顶点Vi的度恰好就是第i个边链表上结点的[填空题]_________________________________3．有向图的度，在有向图中，第i个边链表上结点的个数就是顶点Vi的出度，只需通过表头向量表中找到第i个顶点的边链表的头指针，实现顺链查找计数即可[单选题]*DFS（深度优先搜索遍历）的基本思路？(正确答案)假设初始状态是图中所有顶点均未被访问过，则深度优先搜索可从某个顶点V出发，首先访间此顶点（称此顶点为初始点），然后依次从V的任一个未被访问的邻接点出发进行深度优先搜索遍历，直到图中所有与有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为初始点，重复上述步骤，直到图中所有顶点都被访问过为止BFS（广度优先搜索遍历）的基本思路？1．从图中某个顶点VO出发，首先访问VO，依次访问Vo的各个未被访间的邻接点[填空题]_________________________________2．分别从这些邻接点（端结点）出发，依次访问各个未被访问的邻接点，访问时应保证：如果Vi和Vk为当前结点，且Vi在Vk之前被访问，则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问[填空题]_________________________________3．重复步骤2，直到所有结点均没有未被访问的邻接点[填空题]_________________________________4．若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止[单选题]*名词解释1(正确答案)关键字：是数据元素中某个数据项的值，用它可以识别一个或一组数据元素査找：根据给定的关键字的值，检索某个与该值相等的数据元素是否在查找表中找到为查找成功，找不到为查找失败査找表：是由同一类型的数据元素或记录构成的集合静态査找表：査询某个特定的数据元素是否在査找表中，检素某个特定的数据元素的各种属性动态査找表：在查找过程中同时插入查找不存在的数据元素，或者从査找表中删除已存在的某个数据元素平均査找长度（ASL）：为确定数据元素在査找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度．冲突：两个不同的关键字，其散列函数值相同，因而被映射到同一表位置的现象称为冲突填空题1哈希函数的构造方法：直接定址法，数字分析法，平方取中法，折叠法，除留余数法和随机数法哈希函数处理冲突的方法：开放地址法，再哈希法，链地址法和建立一个公共溢出区。简答题：1各查找方法的基本思想，平均査找长度？顺序查找的基本思路：对于给定的关键字k，从线性表的第一个元素开始依次向后与记录的关鍵字域相比较，如果某个记录的关键字等于k，则查找成功，否则查找失败，平均查找长度ASL=3（n＋1）/4．折半（二分）查找的基本思路：先取表的中间位置的记录关键字和所给关键字进行此较，若相等，则查找成功，如果给定关键字比该记录的关键字小，则说明所要查找的记录只可能在表的前半部分，反之，则在后半部分，重复步骤，每一次比较就可以将查找范围缩小一半，直到找到给定的关键字的记录，查找成功，找不到为查找失败，平均查找长度ASL＝log2（n＋1）-1分块查找（索引顺序表查找）的基本思路：先确定待査记录所在的块（子表）然后在块中顺序查找．平均查找长度ASL=1/2(n/s)+1]+s/2哈希查找（散列查找）的基本思路：在进行查找时，在记录的存储位置与它的关键字之间建立一个确定的对应关系h，以线性表中每个元素的关键字k为自变量通过函数h（k）计算出该元素的存储位置，我们将h函数称为散列函数或哈希函数，这种査找方法称为散列查找或哈希查找名词解释：1排序：就是按关键字值的递增或递减的次序，把文件中的各记录一次排列起来，可使一个无序文件变成有序文件的一种操作排序算法的稳定性：相同元素排序前后的相对位置没有发生变化，则为稳定，反之为不稳定内部排序：在排序过程中，所有待排序记录都放在内存中进行的排序称为内部排序外部排序：当待排序的记录很多，排序时不仅要使用