2017年中国地质大学(武汉)信息工程学院873程序设计基础[专业学位]之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 在单链表L 中，指针P 所指结点有后继结点的条件是_____ 【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
2． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】
当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为
一个元素时，此时堆的元素个数最少，元素个数为
3． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
4． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。 【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
5． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
6． 设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。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②执行程序，f （6，4）=_____。
【答案】①1; 1; f （m ，n －1）; n ②9
7． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
8． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
9． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。
【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即
【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6次。
10．设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素
为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
11．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动
的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址
12．一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
二、选择题
13．程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A. 逻辑设备名
B. 物理设备名
C. 主设备号
D. 从设备号
【答案】A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。
14．计算机开后，操作系统最终被加载到（ ）
A.BIOS
B.ROM
C.EPROM
D.RAM
【答案】D
【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区，这段区城是RAM ，故答案选D 。
15．站点A 、B 、C 通过CDMA 共享链路，A 、B 、C 的码片序列（chipping sequence
）分别是
和
C 收到A 发送的数据是（ ）
A.000
B.101
C.110
D.111
【答案】B
【解析】用A 的码片与信息做内积运算
16．本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）。
A. 命令解释程序
B. 中断处理程序
C. 系统调用服务程序
D. 用户登录程序
【答案】B
若C 从链路上收到的序列是则
相关内容
相关标签