2017年北华大学计算机科学技术学院841数据结构考研题库
● 摘要
一、填空题
1． 已知二维数组
为1000的连续存储区域时
，
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
2． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
3． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
4． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
5． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
6． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
值32）所组成的字符串；空格个数
7． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
8． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
9． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
第 2 页，共 51 页
中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。
10．在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
11．检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
12．循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
二、选择题
13．若一个栈以向量
存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
【答案】C
【解析】题中初始栈顶指针top 为n+1, 而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
14．协议对
A.011111000011111010
B.011111000111110101111110 C.01111100011111010
D.011111000111111001111101 【答案】A
组帧后对应的比特串为（ ）
HDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】
开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。
15．某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位，并且数据按边界对齐存储。某C 语言程序段如下：
若record
变量的首地址为则地址中内容及record.c 的地址分别为（ ）。
第 3 页，共 51 页
A. B. C. D.
【答案】D 。
【解析】32位整数a 需要占4个字节，16位整数c 需要占2个字节，而字符数据b 占一个字节。a=273, 转换成十六进制是111H , 采用小端方式存放数据，地址0xC008中的内容为11H 。由于数据按边界对齐存储，地址
地址
中存放c 。
中存放a , 地址
中存放b , 地址
中空闲，
16．设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）
A.1, 2, 1, 2 B.2, 2, 1, 1 C.3, 4, 2, 3 D.4, 4, 2, 2 【答案】C
【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
17．n 个结点的线索二叉树上含有的线索数为（ ）。
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n+1个空链域。
18．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385 【答案】C
【解析】由
：_
则
和
_
_可知
，
即
显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个
性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
19．若串其子串的数目是（ ）。
A.8
第 4 页，共 51 页
相关内容
相关标签