某高校考研数据结构真题

标签：编码 结点 数据结构 真题 算法 二叉树 顶点 排序 考研

真题

1. 1.       试说明什么是好的散列函数？

“好”的散列函数应满足的条件：①均匀分布，少冲突

                                                 ②计算简便，快速

1. 2.       设散列表的地址范围是[0…M-1],写出除留余数法的散列函数公式。

h(key)=key mod P(P为不大于M的最大素数)

1. 3.       试说明线性探测法的不足之处。

产生基本聚集——易使表中连成一片，使探测次数增加，影响效率。

1. 4.       现采用除留余数法计算地址，取M=11，并采用线性探测法处理冲突。若输入一组记录，其关键字值依次为：（60，78，63，121，77，80，35），请画出所构造的散列表。

0	1	2	3	4	5	6	7	8	9	10
121	78	77	80	35	60			63

H(key)=key mod 11;

1. 5.       快速排序被认为在已知的排序算法中速度较快的算法。

a)       是否在所有情况下快速排序都优于直接插入排序？为什么？

不是。当数据量较大且无序时，快速排序是较快的，且时间复杂度为O（nlog₂n）；当数据为有向或逆向基本有序时，快速排序的时间复杂度为O（n²）。

b)      快速排序的最坏和平均情况时间复杂度各是多少？

1. 最坏时间复杂度：O（n²）。
2. 平均时间复杂度：O（nlog₂n）。

c)       为什么说采用三者取中法选择划分（主）元素（即选择被划分的集合的最左、最右和位于（left+right）/2处的三个元素的中间值作为划分元素）可改进快速排序的性能？

因为快速排序在基本有序或逆向有序时，由于分割元素总在它的一边，所以快速排序的性能退化；如果用三个元素的中间值算法，可以避免将待排元素划分在分割元素一边的情况发生，使快速排序的优越性得到体现，改善其性能。

d)      采用什么措施可改善快速排序的最坏情况的时间性能。

1. 改进主元的选择方法：在每趟排序前选择主元时可以作如下三种处理：

1)       将(left+right)/2位置处的元素作为主元，与left处的位置交换。

2)       选left到right间的随机整数j，将它作为主元。

3)       取left, (left+right)/2和right处的中间值为主元

1. 在快速排序过程中，子序列会变得越来越小，当子序列小到一定值时，快速排序的速度反而不如一些简单的排序算法。这时我们可以选择其他的排序算法。
2. 递归算法的效率常常不如相应的非递归算法，所以为了进一步提高快速排序的速度，可以设计非递归的快速排序算法。
3. 6.       设一个散列表的长度M=7，其下标从0到6。现采用线性探查法解决冲突。

a)       请从空散列表开始，通过依次将下列元素插入散列表中的方式建立散列表。散列函数采用除留余数法（区域运算）。13，22，31，55，26，63

0	1	2	3	4	5	6
55	22	63	31		26	13

b)      对于除留余数法散列函数的模M，一般应如何选择。

不大于M的最大素数。

c)       给出一种从上述散列表中删除元素的可行且有效的方法，并说明理由。

删除时只是将其标记为Neverused而不是实际删除，这样就可以跳过元素继续查找，而插入时可在该位置插入元素。

1. 7.       如图所示的哈夫曼树可得字母F，G，H，I和J的编码。

a)       设某字母串经编码后为“011101011101”，译出原串。

F:00      G:01     H:10     I:110     J:111

011101011101:G,I,H,J,G

b)      说明哈弗曼编码和ASCII编码的不同。

哈弗曼编码是根据元素和权值的不同进行的编码，权值大的编码短，权值小的编码长，且任何短的编码不为长的编码的前缀的不等长编码，而ASCII编码则是按顺序进行等长的编码。

c)       为什么采用哈夫曼编码。

对常用的字符用较少的码位编码。对不常出现的字符用较多的编码位编码，以减少文本的存储长度，提高存储和处理文本的效率。所以采用哈夫曼编码。

d)       试证明有n个叶子的哈弗曼树共有2n-1个结点

哈夫曼树是一颗扩充的二叉树，树中只有度为0和2的结点

N=n0+n2    n0=n2+1    N=2n0-1    N=2n-1

e)       简要说明使用哈弗曼树的优点。

对使用频率较大的字符用较短的码位编码，对使用频率较小的字符用较长的码位编码，可以减少文本存储空间，提高存储的查找效率。

1. 给定一个图，可以有哪些方法判定其是否有回路，请用文字简要说明各种方法的判定过程。

a)       采用深度优先遍历有向图思想设计算法，对于一个有向无环图在DFS算法的执行中，如果在dfs(u)过程调用返回时记录定点u，则可以得到该图的逆拓扑结构是逆拓扑序列。若在执行dfs(u)退出前检查发现顶点u到某个顶点v的反向边<u,v>由于在生成树上v是u的祖先从顶点v到顶点u存在一条路径<u,v>出现说明包含存在顶点v和顶点u的环。

b)       采用拓扑排序思想：若所有节点可纳入到拓扑序列中，则无回路，否则有回路。

1. 9.       试阐述求最小代价生成树中Prim算法和Kruskal算法的基本原理，并从算法设计角度对这两个算法进行分析，比较其相同点与不同点。

a)       Prim：从任意一个顶点开始，每次选择一个与当前顶点集最近的一个顶点，并将两顶点之间的边加入到树中。

b)       Kruskal：搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。

c)       相同点：均针对无向图

d)       不同点：从算法出发，Kruskal算法多出一个sort过程，效率较Prim低。

1. 对内排序中的直接插入排序、冒泡排序、希尔排序、简单选择排序、堆排序进行分析比较。

a)       时间复杂度依次分别是：O(n2)  O(n2)      O(nlog2n)   O(nlog2n)   O(n2)    O(nlog2n)

b)       空间复杂度依次分别是：O(1)    O(1)      O(1)      O(log2n)     O(1)      O(1)

1. 问

a)       逻辑结构、存储结构和运算之间的关系？

数据的逻辑结构反映数据元素之间的逻辑关系，与存储结构无关。数据的存储结构是数据在计算机中的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，与存储结构无关，而运算的实现依赖于存储结构。

b)       有相同的逻辑结构但不同的存储结构是不同的数据结,是否正确举例说明。

正确，二叉树顺序与链式存储。

c)       有相同的存储结构但逻辑结构不同是不同的额数据结构，是否正确举例说明。

正确。用链式存储的树与图。

1. 举例说明顺序队的“假溢出”现象，并给出解决方案。

一个空间为4的顺序队，有0~3号位。

Push->0; Push->1; Push->2; Pop 0; Pop 1; Push 3.

那么这时候再入队就会溢出，但0，1号位为空，这假溢出。解决方案：设置循环队列。

1. 什么是算法？算法有哪些特征？在程序设计算法中引入“程序步”，是不是“程序步”越少执行效率越高？

算法：由基本运算及规定的运算顺序所构成的完整的解题步骤。

特征：有穷性、确定性、输入、输出、可行性

不是。

1. 设T是具有n个内结点的扩充二叉树，I是它的内路径长度，L是它的外路径长度。

a)       试你用归纳法证明E=I+2n，n>=0。

设n=1，则e=0+2*1=2（只有一个根节点时，有两个外部结点）。公式成立。

设有n个结点时，公式成立，即En=ln+2n（1）

现在要证明，当有n+1个结点时，公式成立

增加一个内部结点，设路径长度为1，则ln+1=ln+I（2）

该内部结点，其实是冲一个外部结点便来的，即这时相当于也增加了一个外部是二店（原外部结点变成内部结点时，增加两个外部结点），则En+1=En+l+2（3）

由（1）和（2），则（3）推导为En+1=ln+2n+2=ln+1-l+2n+l+2=ln+1+2(n-1)

故命题成立

b)       你用（a）的结果试说明：成功查找的平均比较次数s与不成功查找的平均比较次数u之间的关系可用公式表示s=（1+1/n）u-1,n>=1。

成功查找的平均比较次数s=1/n

不成功查找的平均比较次数u=（E-n）/（n+1）=（l+n）/n+1

由以上二式，有s=(1+1/n)*u-1

1. 15.   说明树、森林、二叉树的数据结构含义。

森林是树的集合，二叉树是特殊的树。

树和二叉树的区别：

1)       二叉树的度至多为2，树无此限制；

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

3)       二叉树允许为空，树一般不允许为空

1. 16.   树、森林转换为二叉树的基本目的。

一般树在满足树的树的条件下可以是任意的形状，一个结点可以有任意子女。二叉树的每个结点最多只能有两个分支，即左孩子和右孩子，显然一般树处理起来要比二叉树复杂得多，而一般树可以通过一定的方式转化为二叉树以便于操作。

1. 17.   试证明当DFS应用于一个连通图时，所经历的边形成一棵树。

由DFS可知，途中每个顶点都分别访问有且仅有一次，从一个顶点到另外一个顶点必须经过这两个顶点的边，这样深度优先遍历把连通图全部顶点都访问过，共经过n-1条边，刚好使图连通，即为树。

1. 18.   有哪些评价程序执行的方法？优劣？

时间复杂度和空间复杂度。

优势：能够宏观的反应程序的运行时间和所需的辅助空间。

劣势：但不能定量分析

1. 19.   满二叉树T分支为B，证明：B=n-1

分支树为B,意味着有B个指针不为空，除了根节点外，任意一个结点都有指针指向，故若总节点数为n的，可能得到B=n-1。

1. 应用栈操作求解算术表达式：（28+10*2）/（11-5），画出栈的变化过程。

步骤	扫描项	项类型	动作	栈中内容
1	28	操作数	进栈	28.
2	10	操作数	进栈	28.10
3	2	操作数	进栈	28.10.2
4	*	操作符	出栈,计算2*10，结果再进栈	28.20
5	+	操作符	出栈,计算20+20, 结果再进栈	48
6	11	操作数	进栈	48.11
7	5	操作数	进栈	48.11.5
8	-	操作符	出栈,计算11-5, 结果再进栈	48.6
	/	操作符	出栈,计算48/6, 结果再进栈	8

标签：编码,结点,数据结构,真题,算法,二叉树,顶点,排序,考研
From： https://www.cnblogs.com/kaede/p/16824540.html