《2017年上海海事大学信息工程学院821数据结构考研冲刺密押题.doc》由会员分享，可在线阅读，更多相关《2017年上海海事大学信息工程学院821数据结构考研冲刺密押题.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2017年上海海事大学信息工程学院821数据结构考研冲刺密押题一、填空题1 抽象数据类型的定义仅取决于它的一组_，而与_无关, 即不论其内部结构如何变化，只要它的_不变，都不影响其外部使用。【答案】逻辑特性；在计算机内部如何表示和实现；数学特性2 已知二维数组为1000的连续存储区域时，【答案】1196【解析】设元素的行标为i ，列标为j 。则它的存储位置为： 3 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。【答案】 【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。 4 在双向循
2、环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_、_、_、_。【答案】5 设数组储，则元素为_。【答案】9174；8788【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为若以列序为主存储顺序，则它的存储地址为 的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存的存储地址为_；若以列序为主序顺序存储，则元素的存储地址中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_。6 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个顶点用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。（1）若是
3、边，则的值等于_，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若【答案】（1） 已包括进生成树，就把矩阵元素A （i ，j ）置成 边上的权值；都大的数；（2）1; 负值；（3）为负；边（3）算法结束时，相邻矩阵中。 7 数据结构是研讨数据的_和_以及它们之间的相互关系，并对与这种结构定义相应的_，设计出相应的_。；算法 【答案】逻辑结构；物理结构；操作（运算）8 设有两个算法在同一机器上运行，其执行时闻分别为_。【答案】15【解析】当时，而，时， 9 若不考虑基数排序，则在
4、排序过程中，主要进行的两种基本操作是关键字的_和记录的_，【答案】比较；移动10二叉树由_，_，_三个基本单元组成。【答案】根结点；左子树；右子树 11每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_。【答案】 【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。12二进制地址为011011110000，大小为【答案】011011110100；011011100000011011110000是块的起始地址，【解析】大小分别为式如下：和其伙伴块的起始地址计算公.要使前者快于后者，n 至少为，则它的后庁序列是_
5、。设上述二叉树是由某棵树转换而成，则该树的和块的伙伴地址分别为：_ 当大小为4时，起始地址为 当大小为16时，起始地址为：二、选择题13在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。A.B.C.D. 【答案】C14某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有（ ）。A.5位 B.6位 C.15 位 D.33 位 【答案】C 。，根据每个类中微命令的多少可以分别【解析】33个微命令分成5个互斥类（即5个字段）确定字段的长度 为3、2、4、3、3位，又因为采用直接编码方式，所以它们之和就是操作控制字段的位数。 15对序列A.1 B.4 C.3 D.2 【答案】B【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。 16已知广义表用和数取出LS 中原子e 的运算是（ ）。 【答案】C【解析】操作就是得到广义表中第一个的原子。也用希尔排序方法排序，经一趟后序列变为则该次采用的增量是（ ）。操作就是得到除第一个原子外剩下元一、填空题考研试题
