2018年暨南大学信息科学技术学院830数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
2． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
3． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
4． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；(动态) 链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
5． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
6． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
7． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】P ﹣＞next! ＝NULL
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
8． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
9． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。
10．若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。 【答案】
. 。 【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因为每条边重复出现两次，所有无向完全图的边数为
二、单项选择题
11．系统为某进程分配了4个页框, 该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7, 依据LRU 算法, 应淘汰页的页号是（ ）。
A.2
B.3
C.4
D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框, 题中访问过程中页框的变化如下:
访问页号为7的页时, 内存中存在的页的页号是:3、8、4和5, 根据LRU 定义应淘汰的是3。
12．连续存储设计时，存储单元的地址（ ）。
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
【答案】A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
13．n 个结点的正则二叉树中有每个结点的度或者为0或者为2的二叉树称为正则二叉树。（ ）个叶子。 A.
B.
C.
D. 【答案】D
【解析】二叉树结点总数n ＝n 0＋n 1＋n 2(n0，n 1，n 2分别代表度为0，度为1，度为2的结点数) 。又在非空二叉树中:n 0＝n 2＋l ，且本题所给树为正则二叉树，n 1＝0，所以n ＝2*n0﹣l ，因此n 1＝(n+1)/2。
14．下面关于哈希(Hash，杂凑) 查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可
【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，称这个对应关系f 为哈希(Hash)函数，哈希函数的选择要视具体情况而定。
15．某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段. 假定取指令时，每取一个字节PC 自动加1. 若某转移指令所在主存地址为2000H ，相对位移量字段的内容为06H ，则该转移指令成功转移后的目标地址是（ ）.
A.2006H
B.2007H
相关内容
相关标签