标签：结点 排序 元素 存储 背诵 二叉树 顶点 数据结构 考研

第一章       绪论

1. 1.        数据元素之间的关系在计算机中有几种表示方式？各有什么特点？

a)       顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。储存位置反映数据元素之间的逻辑关系。存储密度大，但有些操作（插入、删除）效率较差。

b)       链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（插入、删除等），但储存空间开销大（用于指针），另外不能随机查找。

c)        索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态的特性。

d)       散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式成为散列存储。其特点是存储速度快，只能按关键字随机存取。

1. 2.        数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？

a)       数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。

b)       抽象数据类型是指一个数学模型及定义在该模型上的一组操作。

c)        抽象数据类型的定义仅取决于它的逻辑特性，而与其计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。

1. 3.        在数据结构中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？

a)       数据逻辑结构反映数据元素之间的逻辑关系。

b)       数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。

c)        数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是以来与存储结构。

1. 4.        若逻辑结构相同但存储结构不同，则为不同的数据结构。说法正确？举例说明。

a)       逻辑结构相同但存储不同，可以是不同的数据结构。

b)       例如，线性表的逻辑结构属于线性结构，才用顺序存储结构为顺序表，而采用链式存储结构成为线性链表。

1. 5.        在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。说法正确？举例说明。

a)       栈和队列的逻辑结构相同，其存储表示也可相同，但由于其运算集合不同而成为不同的数据结构。

1. 6.        评价各种不同数据结构的标准是什么？

a)       所选数据结构时候准确、完整的刻画了问题的基本特征

b)       是否容易实现；逻辑结构的选择是否适合运算的功能，是否有利于运算的实现；基本运算的选择是否恰当。

1. 7.        评价一个好的算法，从哪几个方面来考虑？

a)       算法的正确性

b)       算法的易读性

c)        算法的健壮性

d)       算法的时间复杂度和空间复杂度

1. 8.        算法的时间复杂度是算法输入规模的函数。算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目，或于此数目有关的其它阐述。有时考虑算法的最坏情况下的时间复杂度或平均时间复杂度。
2. 9.        根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？

a)       集合、线性结构、树形结构、图形结构

1. 10.    对于一个数据结构，一般包括哪三个方面的讨论？

a)       逻辑结构、存储结构、操作

1. 11.    当你为解决某一问题而选择数据结构时，应从哪些方面考虑？

a)       通常考虑算法所需要的存储空间量和算法所需要的时间量。

b)       后者又涉及到四方面：

                      i.             程序运行时，所需输入的数据总量

                    ii.             对源程序进行编译所需时间

                   iii.             计算机执行每条指令所需时间和程序中指令重复执行的次数

1. 12.    若将数据结构定义为一个二元组（D，R），说明符号D，R应分别表示什么？

a)       D是数据元素的有限集合

b)       S是D上数据元素之间关系的有限集合。

1. 13.    数据结构和数据类型有什么区别？

a)       数据结构的三个方面：

                      i.             数据的逻辑结构

                    ii.             数据的存储结构

                   iii.             对数据进行的操作

b)       数据类型

                      i.             值的集合

                    ii.             操作的集合

1. 14.    试举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。

a)       线性表的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O(n)；而链式存储方式下，插入和删除时间复杂度都是O(1)

 

第二章       线性表

1. 1.        线性表L=(a1,a2,…,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 (n-1)/2
2. 2.        在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时，需向后移动 n-i+1 个元素。
3. 3.        顺序存储结构是通过 物理上相邻 表示元素之间的关系的；链式存储结构是通过 指针 表示元素之间的关系。
4. 4.        对于双向链表，在两个结点之间插入一个新结点需修改的指针共 4 个，单链表为 2 个。
5. 5.        循环单链表的最大优点是：从任一结点出发都可以范文到链表中每一个元素。
6. 6.        线性表有两种存储结构：一是顺序表，二是链表。试问：

a)       如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？

选用链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为O(1)。

b)       若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应该采用哪种存储结构？为什么？

选顺序存储结构。顺序表可以随机存取，时间复杂度为O(1)。

1. 7.        线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定能够克服上述三个弱点？

链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需要移动元素，只修改指针，故时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。

1. 8.        若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？

采用链式存储结构，它可根据实际需要申请内存空间，当不需要时又可见不用结点空间返还系统。在链式存储结构中插入和删除操作不需要移动元素。

1. 9.        线性结构包括 线性表 、 队列 、 栈 和 串 。线性表的存储结构分成 顺序存储结构 和 链式存储结构 。
2. 10.    线性表(a1,a2,…,an)用顺序映射表示时，ai和ai+1 (1<=i<n)的物理位置相邻么？链接表示时呢？

顺序映射时，ai和ai+1的物理位置相邻；

链表表示时，ai和ai+1的物理位置不要求相邻。

1. 11.    说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。

在线性表的链式存储结构中，

l  头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针有标识的作用，故常用头指针冠以链表的名字。

l  头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义(当然有些情况下也可存放链表的长度、用作监视哨等等)，有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其他结点的操作统一了。

l  而且无论链表是否为空，头指针均不为空。

l  首元结点也就是一个元素结点，它是头结点后面的第一个结点。

1. 12.    在单链表和双向链表中，能否从当前结点出发访问到任何一个结点？

l  在单链表中不能从当前结点(若当前结点不是第一个结点)出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每一个结点。

l  在双链表中中求前驱和后续都容易，从当前结点向前到第一结点，向后到最后，可以范文到任何一个结点。

1. 13.    如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？

链表的逆置问题。

设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一个元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。

 

第三章       栈和队列

1. 1.        循环队列的引入，目的是为了克服 假溢出时大量移动数据元素 。
2. 2.        区分循环队列的满与空，只有两种方法： 牺牲一个存储单元 和 设标记 。
3. 3.        解释：队列和栈、循环队列。

l  栈：只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，后进先出。

l  队列：允许在一端插入而在另外一端删除的线性表，允许插入的一端叫队列，允许删除的一端叫队头。最先插入队的元素最先删除。先进先出。

l  循环队列：用常规意义下存续存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成假溢出现象，即队尾已到达一维数组的高下标。不能再插入了，然后队中元素个小于队列的长度。循环队列是解决假溢出的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用牺牲一个存储单元或作标记的方法解决队满和队空的判定问题。

1. 4.        假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示。
   1. 1.        试指出判别给定序列是否合法的一般规则。

通常有两个原则。

l  给定序列中S的个数和 X的个数相等。

l  从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。

1. 2.        两个不同合法序列(对同一输入序列)能否得到相同的输出元素序列？如能得到，请举例说明。

可以得到相同的输出序列。

例如：输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用SXSXSX操作序列；对于合法序列BAC，我们使用SSXXSX操作序列。

1. 5.        试证明：若借助栈由输入序列1,2,…,n,得到输出序列为P1,P2,…,Pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k,使Pj<Pk<Pi。

如果i<j，则对于Pi<Pj情况，说明Pi在Pj入栈前先出栈。

而对于Pi>Pj的情况，则说明要将Pj压到Pi之上，也就是在Pj出栈之后Pi才能出栈。

这就说明，对于i<j<k，不可能出现Pj<Pk<Pi的输出序列。换句话说，对于输入序列1,2,3,不可能出现3,1,2的输出序列。

1. 6.        什么是递归程序？递归程序的优缺点是什么？递归程序在执行时，应借助于什么来完成？递归程序的入口语句、出口语句一般用什么语句实现？

l  一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。

l  递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。

l  递归程序执行中需要借助栈这种数据结构来实现。

l  递归程序的入口语句和出口语句一般用条件判断语句来实现。

1. 7.        内存中一片连续空间(不妨假设地址从1到m)提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才会发生上溢。

S1和S2共享内存中一片连续空间(地址1到m),可以将S1和S2的栈底设在两端，两栈顶想共享空间的中心延伸，仅当两栈顶指针相邻时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈为空。

1. 8.        将两个栈存入数组V[1…m]应如何安排最好？这时栈空、栈满的条件是什么？

l  设栈S1和S2共享V[1…m]

l  初始时，S1的栈顶指针top[0]=0，S2的栈顶指针top[1]=m+1，当top[0]=0时，S1为空，top[1]=m+1时，S2为空；当两个条件同时满足的时候，全栈空。

l  当top[0]+1==top[1]成立时，栈满。

1. 9.        在一个算法中需要建立多个堆栈时，可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么缺点？

a)       分别用多个顺序存储空间建立多个独立的堆栈；

每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。

b)       多个堆栈共享一个顺序存储空间；

多个栈共享一个顺序存储空间，充分利用存储空间，只有在整个存储空间都用完时，才能产生溢出，其缺点是当一个栈满时，要向左、向右查询有无空闲单元。如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作平方，计算复杂并且耗费时间。

c)        分别建立多个独立的链接堆栈。

多个链栈一般不考虑栈的溢出，缺点是栈中元素要以指针相连接，比顺序存储多占用了存储空间。

1. 10.    利用两个栈S1，S2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。

栈的特点是后进先出，队列的特点是先进先出。初始时，设栈S1和S2均为空。

用S1和S2模拟一个队列的输入：设S1和S2容量相等。分以下三种情况讨论：

1)       若S1未满，则元素入S1栈；若S1满，S2空，则将S1全部元素退栈，再压入栈S2，之后元素入S1栈；若S1满，S2不空，则不能入队。

2)       用栈S1和S2模拟队列出队：若栈S2不空，退栈，即是队列的队；若S2为空且S1不空，则将S1栈中全部元素退栈，并以此压入栈S2中，S2栈顶元素退栈，这就是相当于队列的出队。若栈S1为空，并且S2也为空，队列空，不能出队。

3)       判队空：若栈S1和S2容量之和是队列的最大容量。其操作时，S1栈满后，全部退栈，并压入栈S2.再入栈S1直至S1满。则相当于队列元素入队完毕。出队时，S2退栈完毕后，S1栈中元素以此退栈到S2，S2退栈完毕，相当于队列中全部元素出队。

4)       在栈S1不空情况下，若要求入队操作，只要S1不满，就可压入S1中。若S1满和S2不空状态下要求队列的入队时，按出错处理。

 

第四章       树和二叉树

1. 1.        树在计算机内的表示方式有 双链表表示法 、 孩子链表表示法 、 孩子兄弟表示法 。
2. 2.        中缀式a+b*3+4*(c-d)的对应前缀式为 ++a*b3*4-cd 。
3. 3.        二叉树中某一节点左子树的深度-右子树的深度称为该节点的 平衡因子 。
4. 4.        一颗有n个结点的满二叉树有 0 个度为1的结点，有 (n-1)/2 个分支(非终端)结点和 (n+1)/2 个叶子，该满二叉树的深度为 ┌log2 (n+1)┐或└log2 n┘+1 。
5. 5.        高度为K的完全二叉树至少有 2^(k-2) 。
6. 6.        一个深度为k的，具有最少的结点数的完全二叉树按层次，(同层次从左到右)用自然数依次对结点编号，则编号最小的叶子的序号是 2^(k-2)+1 ；编号是i的结点所在的层次号是 └log2 i┘+1 (根所在的层次号规定为1层)。
7. 7.        对于一个具有n个结点的二元树，当它为一颗 完全二叉树 时具有最小高度，当它为一颗 单枝树 时，具有最大高度。
8. 8.        含2个度为2的结点和5个叶子结点的二叉树，可有 0至多个 度为1的结点。
9. 9.        n(n>1)个结点的各棵树中，其深度最小的那棵树的深度是 2 。它共有 n-1 个叶子结点和 1 个非叶子结点，其中深度最大的那棵树的深度是 n ，它共有 1 个叶子结点和 n-1个非叶子结点。
10. 10.    二叉树的先序遍历和中序遍历相同的条件是 任何结点都只有右子树的二叉树 。
11. 11.    一个无序序列可以通过构造一颗 二叉排序树 而变成一个有序的序列，构造树的过程即为对无序序列进行排序的过程。
12. 12.    在一颗存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子树，且它的双亲有右子树，则这个结点在后序遍历中的后序结点是 双亲的右子树中最左的的叶子结点 。
13. 13.    设一颗后序线索树的高为50，结点x是树中的一个结点，其双亲是结点y，y的右子树高度为31，x是y的左孩子。则确定x的后继最多需经过 31 个中间结点(不含后继及x本身)。
14. 14.    从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

a)       树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就说树(树是森林的特例，即森林中只有一棵树的特殊情况)可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。

b)       树和二叉树的区别

                      i.             二叉树的度至多为2，树无此限制。

                    ii.             二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制。

                   iii.             二叉树允许为空，树一般不允许为空。

1. 15.    树和二叉树和之间有什么样的区别与联系？

树和二叉树逻辑上都是树形结构，区别上同。二叉树不是树的特例。

1. 16.    设有一颗算术表达式树，用什么方法可以对该树所表示的表达式求值？

a)       方法一：对该算术表达式(二叉树)进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值

b)       方法二：递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(+-*/)进行最后求值。

1. 17.    一颗有n(n>0)个结点的d度树，若用多重链表表示，树种每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域？为什么？

n(n>0)个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个

1. 18.    证明任一结点个数为n的二叉树的高度至少为O(log2 n)

最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点树都应达到各层的最大值。设n个结点的二叉树的最低高度为h，则n应该满足2^(h-1)<n<=2^h-1关系式。解此不等式，并考虑h是整数，则有h=└log2 n┘+1，即任一结点个数为n的二叉树的高度至少为O(log2 n)。

1. 19.    有n个结点并且其高度为n的二叉树的数目是什么？

2^n-1

1. 20.    已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点树最多是多少？

235。2^(7-1)=64，64-10=54，2^7-1+54*2=235

1. 21.    任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有m-1个度为2，其余度为1。

N=n0+n1+n2=1+n1+2*n2 => n2=n0-1=m-1

1. 22.    求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。

最大的端点编号为n/2，故最小的叶子编号就为n/2+1

 

第五章       图

1. 1.        图中有关路径的定义是 由顶点和相邻顶点序构成的边所形成的序列 。
2. 2.        用DFS遍历一个无环有向图，并在DFS算法退栈返回时，打印相应的顶点，则输出的顶点序列是 逆拓扑有序 。
3. 3.        可以判断出一个有向图是否有环(回路)： 深度优先遍历(DFS)、拓扑排序 。
4. 4.        当各边上的权值 均相等 时， BFS算法可用来解决单源最短路径问题。
5. 5.        求解最短路径的Floyd算法的时间复杂度为 O(|V^3|) 。
6. 6.        在用邻接表表示图时，拓扑排序算法时间复杂度为 O(n+e) 。
7. 7.        关键路径是事件结点网络中 从源点到汇点的最长路径 。
8. 8.        下面关于求关键路径的说法不正确的是（C）。

a)       求关键路径是以拓扑排序为基础的

b)       一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

c)        一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差(一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的和)

d)       关键活动一定位于关键路径上

1. 9.        无向图：多重邻接表；       有向图：十字链表&遍集数组；共有：邻接表&邻接矩阵。
2. 10.    需要借助一个 栈 来实现DFS算法；      需要借助一个 队列 来实现 BFS算法。
3. 11.    只有图为 无向连通图 时，才能生成树。
4. 12.    最小生成树问题是构造连通网的 最小代价生成树 。
5. 13.    无环有向图 才能进行拓扑排序。     拓扑排序算法仅能适用于 有向无环图 。X
6. 14.    AOV网的含义： 顶点表示活动的网络 。边表示 活动间的优先关系 。
7. 15.    AOE网的含义： 边表示活动的网络 。顶点表示 事件 。
8. 16.    判断一个无向图是一棵树的条件是： 有n个顶点，n-1条边的无向连通图 。
9. 17.    有向图G的强连通分量是指： 有向图的极大强连通子图 。
10. 18.    一个连通图的 生成树 是一个极小连通子图。
11. 19.    图G是一个非连通无向图，共有28条边，则该图至少有 9 个顶点。 28*2=8*7;8+1=9;
12. 20.    如果含有n个顶点的图形形成一个环，则它有 n 棵生成树。
13. 21.    在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是： 第I列非零元素个数 。
14. 22.    遍历图的过程实质上是 查找顶点的邻接点的过程 。
15. 23.    构造连通网最小生成树的两个典型算法是 Prim算法和Kruskal算法 。
16. 24.    求图的最小生成树有两种算法， Kruskal算法 适合于稀疏图(边稀疏)的最小生成树。
17. 25.    Prim算法适用于求 边稠密 的网的最小生成树。
18. 26.    有向图G可拓扑排序的判别条件是 不存在环 。
19. 27.    当一个AOV网用链接表表示时，可按下列方法进行拓扑排序。

a)       查邻接表中入度为 0 的顶点，并进栈；

b)       若栈不为空，就①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是 Vk度-1，若Vk入度已为0，则Vk入栈 。

c)        若栈空时，输出顶点数小于图的顶点数，说明有 环 ，否则拓扑排序完成。

1. 28.    如果G1是一个具有n个顶点的连通无向图，那么G1最多有 n(n-1)/2 条边。G1最少有 n-1 条边。
2. 29.    如果G2是一个具有n个顶点的强连通有向图，那么G2最多有 n(n-1) 条边。G2最少有 n 条边。
3. 30.    如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有 n(n-1) 条边。G3最少有 n-1 条边。
4. 31.    证明：具有n个顶点和多于n-1条边的无向连通图G是一定不是树。

具有n个顶点n-1条边的无向连通图是自由树，即没有确定根节点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多一条通路，即形成回路。形成回路的连通图不再是树。

1. 32.    证明对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。

该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角元素均为0。

先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(A[i][j]=1)自然是落到下三角矩阵中；

命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。

1. 33.    用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关?

设图的顶点个数为n(n>=0)，则邻接矩阵元素个数为n^2；与图的边数无关。

1. 34.    对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

使用DFS，按退出DFS过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行DFS(v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。

1. 35.    对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？

开始遍历的顶点不同；存储结构不同；邻接表情况下邻接点的顺序不同。

1. 36.    在什么情况下，Prim算法与Kruskual算法生成不同的MST？

在有相同权值边生成不同的MST，在这种情况下，两种算法会生成不同的MST。

1. 37.    对于有向无环图，叙述求拓扑有序序列的步骤。

a)       在有向图中选一个没有前驱(即入度为0)的顶点并输出。

b)       在图中删除该顶点即所有以它为尾的弧。

c)        重复a)和b)，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

1. 38.    有向图的拓扑排序能否用图的深度搜索模式来查找？若能，请简述方法；若不能，请简述原因。

图的DFS可用于拓扑排序。带环的有向图不能拓扑排序。

步骤：若从有向图某个顶点V出发进行遍历，在DFS(v)结束之前出现从顶点W到顶点V的回边，由于W在生成树上是V的子孙，则有向图必定存在包含顶点V和W的环。

1. 39.    何为AOE网的始点和终点，一个正常的AOE网是否只有一个始点和一个终点？

AOE网的始点事入度为0的顶点，该顶点所代表的时间无任何先决条件，可首先可是。

终点是初度为0的顶点，表示一项工程的结束。

正常的AOE网只有一个始点和一个终点。

 

第六章       集合

1. 1.        哈希表是通过将查找码按选定的 哈希函数 和 解决冲突的方法 ，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是 选好哈希函数 和 处理冲突的方法 。一个好的哈希函数其转换地址应尽可能 均匀 ，而且函数运算应尽可能 简单 。
2. 2.        平衡二叉树又称 AVL树 ，其定义是 二叉树中任意结束左子树高度与右子树高度差绝对值小于0 。
3. 3.        对于长度为255的表，采用分块查找，每块的最佳长度为 16 。     sqrt(255)≈16
4. 4.        有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 45 ，分成 45 块最为理想，平均查找长度是 46 。
5. 5.        执行顺序查找时，存储方式可以是 顺序储存或链式存储 。二分法查找时，要求线性表 顺序存储且有序 。分块查找时要求线性表 块内顺序存储，块间有序 。而散列表的查找，要求线性表的存储方式是 散列存储 。
6. 6.        如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为 (n+1)/2 。
7. 7.        平衡因子的定义是 结点左子树的高度-右子树的高度 。
8. 8.        查找是非数值程序设计的一个重要技术问题，基本上分成 顺序表查找 ， 树表查找 和哈希表查找 。处理哈希冲突的方法有： 开放定址法 、 再哈希 和 建立公共溢出区 。
9. 9.        直接定址法 构造的哈希函数肯定不会发生冲突。
10. 10.    具有N个关键字的B树的查找路径长度不会大于 log└m/2┘((n+1)/2)+1 。
11. 11.    高度为8的平衡二叉树的结点数至少有 54 个。

S(n)=S(n-1)+S(n-2)+1      S(1)=1,S(2)=2;

1. 12.    高度为5(除叶子层之外)的三阶B-树至少有 31 个结点。2^n-1
2. 13.    假定查找有序表A[1…12]中每个元素的概率相等，则进行二分查找时的平均查找长度为 37/12 。
3. 14.    对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为 14 。 (144/8+8)/2+1=14。
4. 15.    127阶B-树中每个结点最多有 126 个关键字；除根节点外所有非终端结点至少有 64 颗子树。   最小高度：h>=logm(n+1)           最大高度：h<=log┌m/2┐[(n+1/2)]+1
5. 16.    哈希表：根据关键码值而直接进行访问的数据结构。
6. 17.    散列表存储的基本思想： 散列表存储的基本思想是用关键字的值决定数据元素的存储地址。
7. 18.    散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？

a)       开放定址法：形成地址序列的公式是：Hi=(H(key)+di)%m,其中m是表长，di是增量。根据di取法不同，又分为三种：

                      i.             di=1，2，…，m-1称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

                    ii.             di=1^2,-1^2,2^2,-2^2,…,±k^2(k<=m/2)称为二次探测再散列，它在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。

                   iii.             di=伪随机数序列，称为随机探测再散列。

b)       再散列法：Hi=RHi(key) i=1,2,…,k,是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。

c)        链地址法：将关键字为同义词的记录存储在同一链表中，啥列表地址区间用H[0…m-1]表示，分量初始值为空指针。凡散列地址为i(0<=i<=m-1)的记录均插在以H[i]为头指针的链表中。这种解决方式中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而a)中的散列表称闭散列表，含义是元素个数受表长限制。

d)       建立公共溢出区：设H[0…m-1]为基本表，凡关键字为同义词的记录，都填入溢出区O[0…m-1]。

1. 19.    用分离的同义词子表解决碰撞和同结合的同义词表解决碰撞属于哪种基本方法？他们各有何特点？

用分裂的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i(0<=i<=m-1)的第一个关键字存储在地址空间第i个分量的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面c)的优缺点；后者实际是静态链表，同义词存在同一地址向量空间(从最后向前找空闲单元)，以指针相连。节省了空间，但易产生“堆积”，查找效率低。

1. 20.    用线性探查法解决碰撞时，如何处理被删除的结点？为什么？

要在被删除结点的散列地址处作标记，不能物理删除。否则，中断了查找的通路。

1. 21.    散列表的平均检索长度不随 记录 的增加而增加，而是随 负载因子 的增大而增加。
2. 22.    如何分量hash函数的优劣：①能否将关键字均匀映射到哈希空间上②有无好的解决冲突的方法③计算哈希函数是否简单高效。
3. 23.    HASH方法的平均查找路长决定于什么？是否与结点个数N有关？      

哈希方法的平均查找路长主要取决于负载因子(表中实有元素数与表长之比)，它反映了哈希表的装满程度。

1. 24.    在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？

不一定相邻。哈希地址为i(0<=i<=m-1)的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。

1. 25.    在B-树和B+树中查找关键字时，有什么不同？

a)       B+树支持顺序和随机查找。

b)       B-树支持随机查找

1. 26.    包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？

Log (m/2) [(n+1)/2]+1

1. 27.    高度为h的m阶B-树至少有多少个结点？

{1-[m/2]^h } / {1-[m/2]}

1. 28.    满二叉树检索树符合B树定义吗？B树的插入和删除算法适用于满二叉检索树吗？为何？

a)       符合

b)       不适用搜索，满二叉检索树不需要做平衡性调整。

1. 29.    含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？

a)       4

b)       8

1. 30.    直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一颗二叉排序树，然后对此树进行查找，其效率如何？为什么？

a)       若在有序序列中采用折半查找，效率相同。

b)       按输入的序列构造二叉排序树会造成高度为n的排序树，效率为O(n)。

1. 31.    用关键字1，2，3，4的四个结点

a)       能够造成出集中不同的二叉排序树？                     14个

b)       其中最优查找树有几种？                                      4个

c)        AVL树有几种？                                                    4个

d)       完全二叉树有几种？试着画出这些二叉排序树。   1个

1. 32.    一棵具有m层的AVL树至少有多少个结点，最多有多少个结点？

a)       f(m)=f(m-1)+f(m-2)+1

b)       2^m-1

1. 33.    在查找和排序算法中，监视哨的作用是什么？

防止越界，减少比较次数

1. 34.    当实现插入排序过程时，可以用折半查找来确定第I个元素在前I-1个元素中可能插入的位置，这样能否改善插入排序的时间复杂度？为什么？

可以，折半时间复杂度为O(log2 n)

1. 35.    折半查找的平均查找长度是多少？

log2 (n+1)-1

 

第七章       排序

排序类型	时间复杂度			空间复杂度	是否稳定
	最好情况	平均情况	最坏情况
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	是
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	是
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	否
希尔排序				O(1)	否
快速排序	O(nlog2 n)	O(nlog2 n)	O(n^2)	O(log2 n)	否
堆排序	O(nlog2 n)	O(nlog2 n)	O(nlog2 n)	O(1)	否
归并排序	O(nlog2 n)	O(nlog2 n)	O(nlog2 n)	O(n)	是
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	是

1. 1.        比较次数与序列初态无关的算法是：简单选择排序、二路归并、二分法插入
2. 2.        比较次数与序列初态有关的排序方法是：冒泡、快速排序
3. 3.        在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
4. 4.        若不考虑基数排序，则在排序中，主要进行的两种基本操作是关键字的 比较 和记录的 移动 。
5. 5.        不受待排序的初始序列的影响，时间复杂度为O(N^2)的排序算法是 简单选择 ，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是 直接插入 。
6. 6.        直接插入排序用监视哨的作用是 免去查找过程中每一步都检测整个表是否查找完毕，提高了查找效率。
7. 7.        快速排序在 最好每次划分能得到两个长度相等的子序列 的情况下最易发挥其长处。
8. 8.        堆排序是一种 选择 类型的排序，它的一个基本问题就是如何建堆，常用的建堆算法是Floy提出的 筛选法 。
9. 9.        在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该算法是不稳定的，这种说法对么？为什么？

这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。

1. 10.    区别：拓扑排序与冒泡排序。

a)       拓扑排序，是有向图的顶点依照弧的走向，找出一个全序集的过程，主要是根据与顶点连接的弧来确定顶点序列

b)       冒泡排序，借助交换思想通过比较相邻结点关键字大小进行排序的算法。

1. 11.    简述直接插入排序，简单选择排序，二路归并排序的基本思想。

a)       直接插入排序的基本思想：基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。

b)       简单选择排序的基本思想：基于选择，开始有序序列长度为0，第i(1<=i<n)趟简单选择排序是，从待排序列中找出最小的数加入到已排序的序列中。

c)        二路归并排序的基本思想：基本归并，开始将具有n个待排序记录的序列看成n个长度为1的有序序列，然后两两归并，得到n/2个长度为2的有序序列，再两两归并，直到合成1个长度为n的有序序列。

1. 12.    快速排序、堆排序、合并排序、shell排序中那种排序平均比较次数最好，哪种排序占用空间最多，哪几种排序算法是不稳定的？

a)       快速排序

b)       归并排序

c)        快速排序，堆排序，shell排序

标签：结点,排序,元素,存储,背诵,二叉树,顶点,数据结构,考研
From： https://www.cnblogs.com/kaede/p/16824533.html