前言
拿下计算机基础这块硬骨头!!!面试就是Offer收割机! 下面放的是考研的关于数据结构的知识点,这个难度相当较低。每天更新,奥里给!!!
学习链接
B站搜一下就有了!
例题
1.为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是__
A.栈
B.队列
C.树
D.图
C 和 D 直接排除,缓冲区的特点需要先进先出,若用栈,则先进入缓冲区的数据则要排队到最后才能打印,不符题意,所以只有队列符合题意。
- 设栈 S 和队列 Q 的初始状态均为空,元素 a,b,c,d,e,f,g 依次进入栈 S。若每个元素出栈后立即进入队列 Q, 且 7 个元素出队的顺序是 b,d,c,f,e,a,g,则栈 S 的容量至少是__ A.1 B.2 C.3 D.4
时刻注意栈的特点是先进后出就可以了! 下面举个栗子:
栈内的最大深度为 3,故栈 S 的容量至少是 3。
- 给定二叉树如下图所示。设 N 代表二叉树的根,L 代表根结点的左子树,R 代表根结 点的右子树。若遍历后的结点序列是 3,1,7,5,6,2,4,则其遍历方式是? A.LRN B.NRL C.RLN D.RNL
分析遍历后的结点序列,可以看出根结点是在中间被访问的,而且右子树结点在左子树之前,则遍历的方法是 RNL
4. 下列二叉排序树中,满足平衡二叉树定义的是______。
根据平衡二叉树的定义有,任意结点的左右子树高度差的绝对值不超过
1。So easy
- 已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点,则该完全二叉树的结点个数最多是______ A. 39 B.52 C.111 D.119
完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶结点,而最后一层之上是个满二叉树,并且只有最后两层上有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7,显然树高为 7时结点更多。若第 6 层上有 8 个叶结点,则前六层为满二叉树,而第 7 层缺失了 8×2=16 个叶结点,故完全二叉树的结点个数最多为 2的7次方-1-16=111 个结点。