2018年北京联合大学数字艺术803软件基础之数据结构考研核心题库
● 摘要
一、填空题
1． 在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。 【答案】
【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少
2． 索引顺序文件既可以顺序存取，也可以 _____存取。
【答案】随机
3． 空格串是指_____，其长度等于_____。
【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数
4． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
5． 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序找，每个元素占4个字节。
【答案】23；100CH
二、单项选择题
6． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储
B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储
D. 以链接方式存储，且数据元素有序
【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
7． 程序段
与对换；
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
A.D(n)
B.O(nlogn)
C.O(n3)
D.O(n2)
【答案】D
【解析】这个是冒泡排序，最坏的情况下需要进行l ＋2＋... ＋n ﹣l 次交换，即时间复杂度是0(n2) 。
8． 用户程序发出磁盘
（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的, 所以答案选C 。
9． 对于循环队列（ ）。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
【答案】D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断:①另设一个布尔变量来区别队列是空还是满；②队满时，
(rear+1)
font 。
10．下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA C. D.
请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
【答案】D
【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。
11．对进行基数排序，一趟排序的结果是:（ ）
A. 05， 46， 13， 55， 94， 17， 42 B.
C. 42，13， 94，05， 55， 46，17
D. 05，13， 46，55，17，42，94
【答案】C
【解析】基数排序有两种:最低位优先和最高位优先。
①最低位优先的过程
先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是 根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。
②以r 为基数的最低位优先排序的过程 假设线性表由结点序列
成，
其中
分配:开始时，把
收集:把构成，每个结点的关键字由d 元组。在排序过程中，使用r 个队列组。排序过程就是对i=0， 1，... ，d －1，依次做一次“分配”和“收集”。 各个队列置成空队列，然后依次考察线性:
表中的每一个结点各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的。如果的关键字k=k，就把放进Q k 队列中。
线性表。
12．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进
行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。