2017年北京师范大学地理学与遥感科学学院978数据结构考研导师圈点必考题汇编
● 摘要
目录
2017年北京师范大学地理学与遥感科学学院978数据结构考研导师圈点必考题汇编（一）.... 2 2017年北京师范大学地理学与遥感科学学院978数据结构考研导师圈点必考题汇编（二）.. 12 2017年北京师范大学地理学与遥感科学学院978数据结构考研导师圈点必考题汇编（三）.. 23 2017年北京师范大学地理学与遥感科学学院978数据结构考研导师圈点必考题汇编（四）.. 33 2017年北京师范大学地理学与遥感科学学院978数据结构考研导师圈点必考题汇编（五）.. 43
一、填空题
1． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
2． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
3． 设数组储，则元素为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
4． 二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，【解析】大小分别为式如下：
当大小为4时，起始地址
为
．
当大小为16时，起始地址为
：和
其伙伴块的起始地址计算公
和
块的伙伴地址分别为：_____
的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存
的存储地址为_____；若以列序为主序顺序存储，则元素
的存储地址
5 已
知
求REPLACE （S ，V , m ）=_____。
【答案】
6． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
7． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注：（1）图的顶点号从0开始计；
（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；
（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。
）
.
【答案】0; j; i; 0; indegree[i]=0; [vex][i]; k==l; indegree[i]=0
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
8． 在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
9． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历
；
（“图有回路”）
序列相同，则任何结点都没有左子树。
10．在一棵m
阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。
【答案】
【解析】m
阶树除根结点和叶子结点外，结点中关键字个数最多是最少
11．求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
12．分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为
13．设广义表 则是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
14．在单链表中设置头结点的作用是_____。
【答案】方便运算
15．在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
二、选择题
16．某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的百分比至少是（ ）
A.
B.
C.
D.
时间占整个CPU 时间