数据结构笔试题总结(针对19校招

总结19年校招遇到的数据结构笔试面试题,分门别类,放好备用。


赫夫曼树

哈夫曼树 C语言实现

路径长度
从树中一个结点到另一个结点之间的分支构成两个节点的路径,路径上的分支数目称作路径长度。

WPL带权路径长度
路径长度与节点上权的乘积。

WPL最短的树叫做赫夫曼树。

赫夫曼编码

字符集d1 d2 d3… 频率w1 w2 w3…

d为结点 w为权值构造赫夫曼树 左分支代表0 右分支代表1 根节点到叶子结点所经过的0和1的序列,即为赫夫曼编码。

构造规则

假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:

(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);

(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;

(3)从森林中删除选取的两棵树,并将新树加入森林;

(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。


数组

  1. 设数组定义为a[60][70],每个元素占2个存储单元,数组按照列优先存储,元素a[0][0]的地址为1024,那么元素a[32][58]的地址为(8048)

a[60][70]有60行、70列,a[32][58]位于整个数组的33行、59列处,因为数组按照列优先存储,所以a[32][58]前面一共有

(59-1)60+(33-1)=5860+32=3512个元素,每个元素占2个存储单元,则一共占3512*2=7024个存储单元,

又因为a[32][58]的地址在2个存储单元的最前端,所以其地址为1024+7024=8048


排序

  1. 设有序表中有1000个元素,则用二分查找查找元素X最多需要比较【 】次.

比较10次。
1个元素的时候比较1次
2~3个元素比较2次
4~7个元素比较3次
8~15 4
16~31 5
32~63 6
64~127 7
128~255 8
256~511 9
512~1023 10
就是log2n取整后 +1

  1. 220下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是( )。

A.快速排序
B.希尔排序
C.堆排序
D.起泡排序

B

  1. 对大量数据排序(100万个),多种排序方法中,哪种最快、效率最高

快速排序>堆排序>归并排序>插入排序 数据达到10000000 堆排序优于快速排序

各种排序查询的算法效率比较


二叉树

  1. 已知一棵二叉树,如果先序遍历的节点顺序是:ADCEFGHB,中序遍历是:CDFEGHAB,则后序遍历结果为:()

CFHGEDBA

先序遍历简单记为:根左右
中序遍历简单记为:左根右
后序遍历简单记为:左右根

  1. 红黑树的性质

map的底层实现

红黑树,作为一棵二叉查找树,满足二叉查找树的一般性质。下面,来了解下 二叉查找树的一般性质。
二叉查找树,也称有序二叉树(ordered binary tree),或已排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:
若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
任意节点的左、右子树也分别为二叉查找树。
没有键值相等的节点(no duplicate nodes)。
因为一棵由n个结点随机构造的二叉查找树的高度为lgn,所以顺理成章,二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后,则这些操作最坏情况运行时间为O(n)。
红黑树虽然本质上是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢?这就引出了红黑树的5个性质:

  • 每个结点要么是红的要么是黑的。
  • 根结点是黑的。
  • 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。
  • 如果一个结点是红的,那么它的两个儿子都是黑的。
  • 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

正是红黑树的这5条性质,使一棵n个结点的红黑树始终保持了logn的高度,从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。


链表

  1. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用( )存储方式最节省运算时间。

双循环链表能够通过头结点的前驱就是尾结点,能够迅速找到尾结点,然后进行插入和删除操作

  1. 已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0..6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为_

如果一个元素存入时,进行了N次散列,相应的查找次数也是N,所以38,25,63这三个元素的查找长度为1,74的查找长度为2,48的查找长度为3,52的查找长度为4。所以平均查找长度为:(1+1+1+2+3+4)/6=2。


Hash

  1. 哈希冲突。解决办法

1)开放定址法:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定 的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的 地址则表明表中无待查的关键字,即查找失败。
2) 再哈希法:同时构造多个不同的哈希函数。
3)链地址法:将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
4)建立公共溢出区:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

Author: Ykk
Link: https://ykksmile.top/posts/44954/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.