2017年北京市培养单位光电研究院863计算机学科综合(专业)之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
2． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
3． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
4． 顺序栈用
【答案】
值32）所组成的字符串；空格个数
，
则结点
和
在同一层上的条件是
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
5． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
6． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
7． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
8． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
9． 实现字符串拷贝的函数strcpy 为：
【答案】
10．如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】序查找效率一样为
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺
二、判断题
11．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）
【答案】√
【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。
12．哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ）
【答案】×
【解析】哈夫曼树不存在度数为1的结点。度数为2和0的结点数之差为1。
13．深度为k 的二叉树中结点总数小于等于
【答案】√
（ ）
【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为
14．负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）
【答案】√
【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素：哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。
15．倒排文件是对次关键字建立索引。（ ）
【答案】√
，将所有具有相同【解析】倒排文件是对每一个次关键字项建立次关键字索引（称为倒排表）次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。
16．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）
【答案】√
【解析】可以有长度无穷大的广义表，只是在计算机中不能实现。
17．广义表的长度是4。（ ）
【答案】×
【解析】长度为1。因为只含一个元素即子表
18．—个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）
【答案】×
【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
且ri 在rj 之前，而在排序后的
序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。
19．设模式串的长度为m , 目标串的长度为n ，当且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ）
【答案】
【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。
20．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）
【答案】×
【解析】外部排序方法：按可用内存大小，将外存上含n 个记录的文件分成若干长度为z 的