2017年北京交通大学计算机与信息技术学院926数据结构与软件工程之数据结构考研仿真模拟题
● 摘要
一、填空题
1． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
2． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
3． 设广义表
则 是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
4． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素
为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
5． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
6． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
7． 设二维数组A 的行和列的下标范围分别为【答案】
当其值为
第 2 页，共 47 页 的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址和每个元素占2个单元，按行优先顺处的元素为_____。 序存储，第一个元素的存储起始位置为b ，则存储位置为【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
时，则i=2，j=3。
8． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
9． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。 【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
10．对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
11．在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
12．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动
13．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
14．设有两个算法在同一机器上运行，其执行时闻分别为
_____。
【答案】15
【解析】当
时，而，时， 要使前者快于后者，n 至少为
第 3 页，共 47 页
15．循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
二、选择题
16．文件系统中，文件访问控制信息存储的合理位置是（ ）。
A. 文件控制块
B. 文件分配表
C. 用户口令表
D. 系统注册表
【答案】A
【解析】文件控制块是文件存在的标志，文件的相关信息（基本信息、存取控制信息以及使用信息）都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息。
17．算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
18．若某通信链路的数据传输速率为
A.600波特
B.1200波特
C.4800波特
D.9600波特
【答案】B
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系：B = 2xH （Baud ）, 而奈奎斯特公式一无噪信道传输能力公式是
而可以得到波特率与数据传输速率的关系，即
N=4，因此波特率是1200, 答案是B 。
第 4 页，共 47 页 采用4相位调制，则该链路的波特率是（ ）。 N 为一个码元所取的离散值个数。从在本题中数据传输速率C = 2400,