2017年上海市培养单位上海微系统与信息技术研究所866计算机原理之数据结构考研题库
● 摘要
一、填空题
1． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
2． 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的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
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。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
第 2 页，共 60 页
；
（“图有回路”）
②执行程序，f （6，4）=_____。 【答案】①1; 1; f （m ，n －1）; n ②9
4． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
5． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为
一个元素时，此时堆的元素个数最少，元素个数为
6． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：_____;
【答案】
7． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
8． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
第 3 页，共 60 页
9． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
10．从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
11．在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
12．线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平均次数为
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
二、选择题
13．
协议对
A.011111000011111010
B.011111000111110101111110 C.01111100011111010
D.011111000111111001111101 【答案】A
HDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】
开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。
14．一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11 B.12 C.13 D.14
【答案】B
第 4 页，共 60 页
组帧后对应的比特串为（ ）