2018年南京农业大学信息科学技术学院853计算机专业基础综合之数据结构考研核心题库
● 摘要
一、填空题
1． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
2． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
3． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
4． 模式串
【答案】01122312
5． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】
要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
6． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构；物理结构；操作(运算) ；算法
7． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1
【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明
的next 函数值序列为_____。 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
序列有序。
8． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
9． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。 【答案】；边稀疏
10．若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。 【答案】
. 。 【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因为每条边重复出现两次，所有无向完全图的边数为
二、单项选择题
11．在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0(n)
B.0(n+e) C. D.
【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0(n+e)
12．若下图为10BaseT 网卡接收到的信号波形, 则该比特串是（ ）
A.00110110
B.10101101
C.01010010
D.11000101
【答案】A
【解析】以太网采用曼彻斯特编码, 其将一个码元分成两个相等的间隔, 前一个间隔为高电平而后一个间隔为低电平表示1, 反之则表示0。故根据波形图, 可得答案为A 。
13．用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。
A.j ＝r[j].next
B.j ＝j ＋l
C.j ＝j ﹣＞next
D.j ＝r[j]﹣＞next
【答案】A
【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。
14．有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。
A.60
B.66
C.18000
D.33
【答案】B
【解析】如果是全部，则是需要100*90*2个字节；但是用三元组表示的话，只需要记录非零数据的X 坐标，Y 坐标，数值即可，就是每个非零数字需要占用三个整数的空间，即2*3＝6字节，10个非零整数则是2*3*10＝60字节；如果问有效元素占的空间大小，则选A 项，但是如果从整体来看，应该多一个用来记录矩阵宽(100)、高(90)、默认值(0)的元素，所以还应该多算6个字节。所以全部为66字节，选B 项。
15．float 型数据通常用IEEE754单精度浮点数格式表示。若编译器将float 型变量x 分配在一个32位浮点寄存器FR1中,
且
A.C1040000H
B.C2420000H
C.C1840000H
D.C1C20000H
【答案】A , 则FR1的内容是（ ）。
【解析】首先将十进制数转换为二进制数-1000.01,
接着把它写成规格化形式
IEEE754标准) , 然后计算阶码的移码=偏置值+
阶码真值(按, 最后短浮点数代码:数符位=1, 阶码=10000010, 尾数00001000000000000000000, 写成十六进制为C1040000H 。选项D 是一个很容易被误选的选项, 其错误在于没有考虑IEEE754标准中隐含最高位1的情况, 偏置值是128。
16．用海明码对长度为8位的数据进行检/纠错时, 若能纠正一位错, 则校验位数至少为（ ）
A.2
B.3
C.4