2017年中国民航大学航空自动化学院833算法与数据结构考研题库
● 摘要
一、填空题
1． 实现字符串拷贝的函数strcpy 为：
【答案】
2． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
3． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
4． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
5． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
6． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
7． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
8． 在哈希函数
中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
9． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
10．在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】
在B
11．假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵，将代入得93。
12．已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时
，
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
13．执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储 14．对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
15．文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
的地址是：_____。
二、选择题
16．假定变量i 、f 和d 的数据类型分为int 、float 和double （int 用补码表不，float 和double 分，已知别用IEEE754单精度和双精度浮点数格式表示）
位机器中执行下列关系表达式，则结果为“真”的是（ ）。
A. 仅I 和II B. 仅I 和III
若在32
C. 仅II 和III D. 仅III 和IV 【答案】B
II 中，f 的数据类型从float 【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。转换为int 时，小数点后面4位会丢失，故II 的结果不为真；IV 中，d+f时需要对阶，对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故IV 的结果也不为真。I 和II 进行数据类型的转换的时候并没有改变其值。
17．分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
【答案】C
【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
18．某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的百分比至少是（ ）
A.
B.
C.
D. 【答案】B
【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的
时间占用CPU 时间
百分比为中断响应容许的延迟时间对此没有影响，属于干扰条件。
19．下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，起泡排序 【答案】D
20．计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。
A. 可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【答案】B
时间占整个CPU 时间