2018年长春理工大学计算机科学技术学院809数据结构考研基础五套测试题
● 摘要
一、填空题
1． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
2． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3，4先出栈的序列有34521、34215、34251共3个。
3． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则的地址为l ＋2＋... ＋i ﹣l ＋j ＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
4． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】
。当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为
一个元素时，此时堆的元素个数最少，元素个数为。
5． 假定查找有序表 中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。
【答案】
表
平均查找次数为
。 【解析】折半查找时每个的次数如表所示:
二、单项选择题
6． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数
(2)边数大于顶点个数减1
(3)至少有一个顶点的度为1
A. 只有(1)
B. 只有(2)
C. (1)和(2)
D.(1)和(3)
【答案】A
【解析】在图中，
顶点的度之和与边的数目满足关系式：(n为图的总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”的反例如下图2所示
.
图
1
图2
7． n 个结点的线索二叉树上含有的线索数为（ ）。
A.2n
B.n ﹣1
C.n ＋1
D.n
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n ＋1个空链域。
8． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为:双亲表示法、孩子链表示法、孩子兄弟表示法。
9． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法（ ）。
A. 分块
B. 顺序
C. 折半
D. 哈希
【答案】A
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
10．在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps ，分组大小为1000B ，其中分组头大小20B ，若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）
.
A.80ms B.
C.
D.
【答案】c
【解析】由题设可知，分组携带的数据长度为980B ，文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B ，总共需要传送的数据量大小为IMB. 由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机. 当t ＝lM ×8/100Mbps＝80ms 时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，每次转发的时间为t 0＝lK ×8/100Mbps＝，所以，在不考虑分组拆装时间和传播延时的情况下，当时，H2接受完文件，
即所需的时间至少为
11．当系统发生抖动(thrashing)时, 可以采取的有效措施是（ ）。
Ⅰ. 撤销部分进程
Ⅱ. 增加磁盘交换区的容量
Ⅲ. 提高用户进程的优先级
A. 仅Ⅰ
B. 仅Ⅱ
相关内容
相关标签