2016年福州大学福建省空间信息工程研究中心数据结构与程序设计(C语言)之数据结构考研复试题库
● 摘要
一、选择题
1． 程序段
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
答:D
【解析】这个是冒泡排序，最坏的情况下需要进行
2． 串的长度是指（ ）。
A. 串中所含不同字母的个数
B. 串中所含字符的个数
C. 串中所含不同字符的个数
D. 串中所含非空格字符的个数
答:B
【解析】串中字符的数目n 称为字符的长度，不必考虑其中单个字符是否相等。
3． 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。
A. 必定快
B. 不一定
C. 在大部分情况下要快
D. 取决于表递增还是递减
答:C
【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。
4． 排序算法的稳定性是指（ ）。
A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变
B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变
C. 算法的排序性能与被排序元素的数量关系不大
第 2 页，共 45 页 次交换，即时间复杂度是
D. 算法的排序性能与被排序元素的数量关系密切
答:A
【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
且在之前，而在排序后的序列中，仍在之前，则称这种排序算法是稳定的；否则称为不稳定的。
5． 已知程序如下：
{
}
{
}
程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（ ）。
A. B. C. D.
答:A
【解析】函数S （intn ）是一个递归函数：①当实际参数小于等于零时则返回0, 并终止递归；
，并将S （n-1）的结果加上n 作为返回值。程序从②当实际参数大于零时则递归调用S （n-1）
main （ ）函数开始，首先调用main （ ）函数；在main （ ）函数中调用S （1）
；由于函数S （1）的函数时，将main （ ）函数的上下文保存到栈中，并进入函数S （1）
；在S 实际参数大于零，需要调用S （0）, 故将S （1）函数的上下文保存到栈中，进入S （0）
（0）中，实际参数小于等于零，递归终止。
6． 设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）
A.1, 2, 1, 2
B.2, 2, 1, 1
C.3, 4, 2, 3
D.4, 4, 2, 2
答:C
【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
第 3 页，共 45 页