2017年三峡大学计算机与信息学院837计算机综合之数据结构考研题库
● 摘要
一、填空题
1．
给定一组数据
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
2． 建立索引文件的目的是_____。
【答案】提高查找速度
3． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
4． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；（动态）链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
5． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵
，
将
代入得93。
在B
6． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
7． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
8． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
9． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
10．索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
二、选择题
11．下列关于虚拟存储的叙述中，正确的是（ ）。
A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术 C. 虚拟存储容量只受外存容量的限制 D. 虚拟存储容量只受内存容量的限制 【答案】D 。
【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断，技术）将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件 机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中 的A ，B ，C 都是错误的，所以答案是D 项。
12．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法。
A. 分块 B. 顺序 C. 折半 D. 哈希 【答案】A
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
13．在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps 分组大小为1000B , 其中分组头大小20B , 若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）。
A.80ms
B.80.08ms C.80.16ms D.80.24ms 【答案】C
【解析】由题设可知，分组携带的数据长度为980B , 文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B , 总共需要传送的数据量大小为1MB 。由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机。当t ＝1M ×8／100Mbps ＝80ms 时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，
每次转发的时间为
所以，在不考虑分组拆
装时间和传播延时的情况下，当时，H2接受完文件，即所需的时间至少为80.16ms
14．用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。
A. 仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都可能要修改 D. 队头、队尾指针都要修改
相关内容
相关标签