2018年北京林业大学信息学院839数据结构[专业硕士]考研核心题库
● 摘要
一、填空题
1．
【答案】5
2． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
3． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则的地址为l ＋2＋... ＋i ﹣l ＋j ＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
4． 实现字符串拷贝的函数strcpv 为:
(_____)
【答案】s++＝*t++或(*s++＝*t++)!＝'\0’
5．
线性表
【答案】(n﹣1)/2
【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。
6． 对n 个记录的表进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n (n－1) /2
【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要
。用数组表示，假定删除表中任一元素的概率相同，则删除一个元＝_____ 素平均需要移动元素的个数是_____。
7． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
8． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】P ﹣＞next! ＝NULL
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
9．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，带权路径长度WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
10．起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块的起始地址为_____; 。
【答案】480+8=488，480－32=448
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:
根据上述公式起始地址就为488。
11．在单链表中设置头结点的作用是_____。
【答案】方便运算
12．设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
【解析】当
时，100n2>2n，而，2n 时，100n ＜2
二、单项选择题
13．已知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA
B.FEDCBA
C.CBEDFA
D. 不定
【答案】A
【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。
14．若用户进程访问内存时产生缺页, 则下列选项中, 操作系统可能执行的是（ ）
Ⅰ. 处理越界错
Ⅱ. 置换页
Ⅲ. 分配内存
A. 仅Ⅰ、Ⅱ
B. 仅Ⅱ、Ⅲ
C. 仅Ⅰ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】B
【解析】用户进程访问内存时缺页会发生缺页中断。发生缺页中断, 系统地执行的操作可能是置换页面或分配内存。系统内没有越界的错误, 不会进行越界出错处理。
15．FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。
A. 建立在TCP 之上的控制连接
B. 建立在TCP 之上的数据连接
C. 建立在UDP 之上的控制连接
D•建立在UDP 之上的数据连接
【答案】A
【解析】对于FTP , 为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接:一条为控制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。
16．下列有关总线定时的叙述中, 错误的是（ ）。
A. 异步通信方式中, 全互锁协议最慢
B. 异步通信方式中, 非互锁协议的可靠性最差
C. 同步通信方式中, 同步时钟信号可由多设备提供
D. 半同步通信方式中, 握手信号的采样由同步时钟控制
【答案】C