2018年北京市培养单位光电研究院866计算机原理之数据结构考研仿真模拟五套题
● 摘要
目录
2018年北京市培养单位光电研究院866计算机原理之数据结构考研仿真模拟五套题（一） ... 2 2018年北京市培养单位光电研究院866计算机原理之数据结构考研仿真模拟五套题（二） . 14 2018年北京市培养单位光电研究院866计算机原理之数据结构考研仿真模拟五套题（三） . 27 2018年北京市培养单位光电研究院866计算机原理之数据结构考研仿真模拟五套题（四） . 42 2018年北京市培养单位光电研究院866计算机原理之数据结构考研仿真模拟五套题（五） . 54
一、填空题
1． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。 【答案】
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
2． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为_____；若以列序为主序顺序存储，则元素a[45，68]的存储地址为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为2000＋((i﹣l)*80＋j ﹣
1) 2。若以列序为主存储顺序，则它的存储地址为2000＋((j﹣l)*50＋i ﹣l)*2。
3． 在单链表中设置头结点的作用是_____。
【答案】方便运算
4． 组成串的数据元素只能是_____。
【答案】字符
5． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表
中插入值为item 的元素，如该元素已在哈希表中，报告出错。
6． 栈是_____的线性表，其运算遵循_____的原则。
【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出
7． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增
量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; (10，7，-9，0，47，23，1，8，98，36)
8． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；
【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py
9． 已知；；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，t) ，LEN(t)＋1))
:
【答案】 ，求REPLACE(S，V ，m) ＝_____。
10．当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
二、判断题
11． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
【答案】 ×
【解析】数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。
12．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）
【答案】 ×
【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。
13．倒排文件是对次关键字建立索引。（ ）
【答案】√
【解析】倒排文件是对每一个次关键字项建立次关键字索引(称为倒排表) ，将所有具有相同次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。
14．哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念（ ）
【答案】×
【解析】哈希文件是使用一个函数(算法) 来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值而直接进行访问的数据结构。
15．在链队列中，即使不设置尾指针也能进行入队操作。（ ）
【答案】 √
【解析】因为存在头指针，根据链表的性质，根据头指针可以找到为指针。
16．在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（ ）
【答案】√
【解析】最佳适配法:将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户；最先适配法:从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。
17．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
【答案】 √
【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
18．折半查找与二元查找树的时间性能在最坏的情况下是相同的。（ ）
【答案】×
【解析】不是，当二元查找树是一棵单支树时，时间性能是O(n)。而折半查找依然是
19．顺序存储结构的主要缺点是不利于插入或删除操作。（ ）
【答案】 √
【解析】因为顺序表的插入删除会移动大量的元素。
20．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
【答案】 ×
【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。
三、算法设计题
21．假设K1，... ，Kn 是n 个关键词，试解答：
(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，
相关内容
相关标签