2018年北京工商大学计算机与信息工程学院818数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。 【答案】
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
2． 模式串的next 函数值序列为_____。
【答案】01122312
3． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
4． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
5． 有向图G=(V, E) ，其中
权d 。E(G)为
，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。
【答案】50；4
6． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
7． 设数组
址为_____。
【答案】9174；8788
第 2 页，共 38 页 ，用三元组表示弧及弧上的的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为_____；若以列序为主序顺序存储，则元素a[45，68]的存储地
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为2000＋((i﹣l)*80＋j ﹣
1) 2。若以列序为主存储顺序，则它的存储地址为2000＋((j﹣l)*50＋i ﹣l)*2。
8． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。 【答案】或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
9． 实现字符串拷贝的函数strcpv 为:
(_____)
【答案】s++＝*t++或(*s++＝*t++)!＝'\0’
10．从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;
；2；k
二、单项选择题
11．某主机的IP 地址为, 子网掩码为。若该主机向其所在子网发送广播分组, 则目的地址可以是（ ）。 A. B. C. D.
【答案】D 。
【解析IPv4地址中的特殊地址, 直接广播地址, 也就是把主机位全部设置为1, 这里77的二进制是01001101, 子网掩码252的二进制是11111100, 由此可以看到77的前6位作为子网位, 后四位
, 也就是作为主机位, 由此可以知道其广播地址是
12．要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n －1
B.n
C.n+1
D.2n
第 3 页，共 38 页 , 因此答案是D 。
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n －1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
13．某计算机存储器按字节编址, 采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位, 并且数据按边界对齐存储。某C 语言程序段如下:
若record 变量的首地址为0xC008, 则地址中内容及的地址分别为（ ）。 A. B. C. D.
【答案】D 。
32位整数a 需要占4个字节, 16位整数c 需要占2个字节, 而字符数据b 占一个字节。【解析】
a=273, 转换成十六进制是111H , 采用小端方式存放数据, 地址
边界对齐存储,
地址
中存放c 。
14．已知序列25, 13, 10, 12, 9是大根堆, 在序列尾部插入新元素18, 将其再调整为大根堆, 调整过程中元素之间进行的比较次数是（ ）。
A.1
B.2
C.4
D.5
【答案】B
【解析】对堆插入或删除一个元素, 有可能不满足堆的性质, 堆被破坏, 需要调整为新堆。
(1)为原堆,
(2)为插入18后,
(3)比较10与18, 交换后,
(4)比较25与18, 不交换, 即为调整后的新的大根堆。
因此调整过程中元素之间进行的比较次数为2。
中存放a ,
地址中的内容为11H 。由于数据按中存放b ,
地址中空闲,
地址
第 4 页，共 38 页