2017年浙江理工大学信息学院991数据结构考研仿真模拟题
● 摘要
一、填空题
1． 二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，【解析】大小分别为式如下：
当大小为4时，起始地址
为
2． 表达式
【答案】
3． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
4． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
5． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
6．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
7． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
和块的伙伴地址分别为：_____ 和
其伙伴块的起始地址计算公
当大小为16时，起始地址为
：
的后缀表达式是_____。
其中
队头和队尾指针分别为front 和rear , 则此循
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
8． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若
是边，则
的值等于_____，若
不是边，则
的值是一个比任
何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
【答案】（1）
已包括进生成树，就把矩阵元素A （i ，j ）置成 边上的权值；都大的数；（2）1; 负值；（3）为负；边
（3）算法结束时，相邻矩阵中。
9． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为一个元素时，此时堆的元素个数最少，元素个数为
10．空格串是指_____，其长度等于_____。
【答案】由空格字符（
值32）所组成的字符串；空格个数
二、选择题
11．采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多 B. 负载因子过大 C. 哈希函数选择不当 D. 解决冲突的算法选择不好 【答案】D
【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
12．向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
【答案】D
【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。
13．下列关于USB 总线特性的描述中，错误的是（ ）。
A. 可实现外设的即插即用和热插拔 B. 可通过级联方式连接多台外设
C. 是一种通信总线，可连接不同外设 D. 同时可传输2位数据，数据传输率高 【答案】D 。
【解析】USB 总线即通用串行总线，它的特点有：（1）即插即用；（2）热插拔；（3）有很强的链接能力能将所有外设链接起来，且不损失带宽；（4）有很好的可扩展性；（5）高速传输，速度可达480Mbps 。所有A , B, C都符合USB 总线的特点。对于选项D , USB 是串行总线，不能同时传输两位数据，所以答案为D 。
14．一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。
A. B. C. D.
字节
字节
字节
字节
【答案】C
【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下32-8=24位是段内位移空间，因此最大段长为B 。
15．n 个结点的完全有向图含有边的数目（ ）。
A.n*n
B.n （n+l） C.n/2
D.n*（n-l ）
【答案】D
【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有
条边。如是有向图，需要在无向图的最多边的基础上乘以2，则
为n （n-l ）。
16．设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串 B. 判断是否相等 C. 模型匹配 D. 连接 【答案】C
【解析】常用的串的基本操作有七种，INDEX （s ，t ）是其中的定位函数，这种运算就是所说的模式匹配。
17．对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n
相关内容
相关标签