2018年北京服装学院机械电子工程910数据结构与算法之数据结构考研核心题库
● 摘要
一、填空题
1． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____
【答案】FEGHDCB ；BEF
【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。
2． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
3． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数目。例f(5，3) ＝5, 有5种表示方式:3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1，1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
_____
_____；
}
_____；
}
，
_____)
②执行程序，f(6，4) ＝_____。 【答案】①1; 1; f(m, n ﹣1) ; n ②9
4． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。
5． —个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
6． 已知有序表为(12，18，24，35，47，50，62，83，90，115，134) 当用二分法查找90时，需次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2; 4; 3
【解析】二分法查找元素次数列表
查找100是找到115就停止了。
7． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
8． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
9． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
10．二进制地址为011011110000, 大小为
【答案】011011110100；011011100000
【解析】011011110000是块的起始地址，大小分别为算公式如下:
和块的伙伴地址分别为:_____
和
其伙伴块的起始地址计
当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。
11．组成串的数据元素只能是_____。
【答案】字符
12．深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
二、单项选择题
13．若一棵完全二叉树有768个结点, 则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385
【答案】C
【解析】由
和
可知,
, 即
, 显然
则
384, 所以二叉树的叶结点个数是384。
还可以根据完全二叉树的另一个性质:
最后一个分支结点的序号为384, 而叶子结点的个数为。(表示不大于x 的最大整数, 比如 14．参考模型的网络层提供的是（ ）。
A. 无连接不可靠的数据报服务 B. 无连接可靠的数据报服务 C. 有连接不可靠的虚电路服务 D. 有连接可靠的虚电路服务 【答案】A
【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务, 因此答案是A 。
15．ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址 B. 根据MAC 地址查询IP 地址 C. 根据域名查询IP 地址 D. 根据IP 地址查询域名
, 故非叶子结点数为
) 。