《2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研题库.doc》由会员分享，可在线阅读，更多相关《2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研题库.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研题库目录 2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研题库（一） . 2 2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研题库（二） . 12 2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研题库（三） . 24 2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研题库（四） . 35 2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研题库（五） . 43一、填空题1 当线性表的元素总数基本稳定
2、，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。【答案】顺序【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。 2 二叉树由_，_，_三个基本单元组成。【答案】根结点；左子树；右子树3 组成串的数据元素只能是_。【答案】字符 4 在二叉树中，指针p 所指结点为叶结点的条件是_。【答案】 【解析】叶子节点的左右孩子都不存在。5 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 【答案】（1）（
3、2）链表未到尾就一直进行将当前结点作为头结点后的第一元素结点插入 6 求最短路径的Dijkstra 算法的时间复杂度为_。【答案】 7 对于一个具有n 个结点的二叉树，当它为一棵_二叉树时具有最小高度，当它为一棵_ 时. 具有最大高度【答案】完全；只有一个叶结点的二叉树 8 阅读下列程序，指出其功能，并写出空格处应填上的语句。 的元素，如该元素已在哈希表中，报告出错。 【答案】【解析】本题是在哈希表ht中插入值为9 个字符串中_称为该串的子串。【答案】任意个连续的字符组成的子序列10数据结构中评价算法的两个重要指标是_。【答案】算法的时间复杂度和空间复杂度11分别采用堆排序，快速排序，起泡排序
4、和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。【答案】起泡；快速，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为（n ）而快速排序算法需要比较的次数达到最大，时间复杂度为 12循环队列的引入，目的是为了克服_。【答案】假溢出时大量移动数据元素【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。 二、选择题13由3个结点可以构造出多少种不同的有向树？（ ）A.2 B.3 C.4 D.5【答案】A【解析】满足以下条
5、件的有向图称为有向树：有且仅有一个结点的入度为0; 除树根外结点的入度为1; 从树根到任一结点有一有向通路。 14假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。A.146k B.147K C.148K D.158K 【答案】B【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放
6、4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K 个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容=147K。 量为： 15循环队列存储在数组中，则入队时的操作为（ ）。A. B. C. D. 【答案】D16单链表中，增加一个头结点的目的是为了（ ）。A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现D. 说明单链表是线性表的链式存储 【答案】C【解析】单链表中增加一个头结点的目的是为了方便运算的实现，使得对第一个元素的操作与其它元素的操作相同。 17下列关于闪存（FlashMemory ）的叙述中，错误的是（ ）。A. 信息可读可写，并且读、写速度一样快 B. 存储元由MOS 管组成，是一种半导体存储器 C. 掉电后信息不丢失，是一种非易失性存储器 D. 采用随机访问方式，可替代计算机外部存储器考研试题
