2018年湘潭大学信息工程学院870数据结构(二)[专业硕士]考研基础五套测试题
● 摘要
目录
2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研基础五套测试题（一） .... 2 2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研基础五套测试题（二） .. 14 2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研基础五套测试题（三） .. 24 2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研基础五套测试题（四） .. 34 2018年湘潭大学信息工程学院870数据结构（二）[专业硕士]考研基础五套测试题（五） .. 45
一、填空题
1． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4；2
2． 在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。
【答案】
3． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
2n
【解析】当时，100n2>2n，而，时，100n ＜2
4． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录
的_____。
【答案】比较；移动
5． 已知一循环队列的存储空间为则此循环队列判满的条件是_____
【答案】
6． 试利用下列栈和串的基本操作完成下述填空题。
initstack(S)置S 为空栈； push(S，X) 元素X 入栈； pop(S)出栈操作； gettop(S)返回栈顶元素； sempty(S)判栈空函数； setnull(St)置串St 为空串； length(st)返回串st 的长度；
equal(S1，S 2) 判串S 1并S 2是否相等的函数； concat(S1，S 2) 返回联接S 1和S 2之后的串； sub(S，i ，1) 返回S 中第i 个字符；
，其中n ＞m ，队头和队尾指针分别为front 和rear ，
empty(st)判串空函数
FUNCinvert(pre:string ；V ARexp :string) :boolean ；
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true ，否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。
)
_____；_____；
_____THEN_____
IF_____THEN_____
(_____，_____)；
(_____，_____)；
_____
_____THEN
注意:每个空格只填一个语句。
【答案】(1)initstack(S)//栈s 初始化为空栈 (2)setnull(exp)//串exp 初始化为空串 (3)chinopset//判取出字符是否是操作符
(4)push(s，ch)//如ch 是运算符，则入操作符栈s (5)sempty(s)//判栈s 是否为空
(6)succ:＝false//若读出ch 是操作数且栈为空，则按出错处理 (7)exp
(8)ch//若ch 是操作数且栈非空，则形成部分中缀表达式 (9)exp
(10)gettop(s)//取栈顶操作符 (11)pop(s)//操作符取出后，出栈
(12)sempty(s)//将pre 的最后一个字符(操作数) 加入到中缀式exp 的最后
二、单项选择题
7． 下列命中组合情况中, 一次访存过程中不可能发生的是（ ）。
A.TLB 未命中, Cache 未命中, Page 未命中
B.TLB 未命中, Cache 命中, Page 命中 C.TLB 命中, Cache 未命中, Page 命中 D.TLB 命中, Cache 命中, Page 未命中 【答案】D
【解析】TLB(快表) 和慢表(页表, Page) 构成二级存储系统, 若TLB 命中, 则Page 必命中。因此不可能发生的是D 选项。
8． 已知三叉树T 中6个叶结点的权分别是2, 3, 4, 5, 6, 7, T 的带权(外部) 路径长度最小是 （ ）
A.27 B.46 C.54 D.56
【答案】B 【解析】利用三叉树的6个叶子结点的权构建最小带权生成树, 最小的带权路径长度为
9． 设文件F1的当前引用计数值为1，先建立F1的符号链接(软链接) 文件F2，再建立F1的硬链接文件F3，然后删除F1. 此时，F2和F3的引用计数值分别是（ ）.
A.0、1 B.1、1 C.1、2 D.2、1 【答案】B
【解析】为了使文件实现共享，通常在使用该形式文件系统的文件索引节点中设置一个链接计数字段，用来表示链接到本文件的用户目录项的数目(引用计数值) ，这是共享的一种方法. 当新文件建立时，一般默认引用计数值为1. 硬链接可以看作是已存在文件的另一个名字，新文件和被链接文件指向同一个节点，引用计数值加1. 当删除被链接文件时，只是把引用计数值减1，直到引用计数值为0时，才能真正删除文件. 软链接又叫符号链接，在新文件中只包含了被链接文件的路径名，新文件和被链接文件指向不同的节点. 建立软链接文件时，文件的引用计数值不会增加. 在这种方式下，当被链接文件删除时，新文件仍然是存在的，只不过是不能通过新文件的路径访F1和F2的引用计数值都为1. 当再建立F3时，问被链接文件而已. 因此，在本题中，当建立F2时，F1和F3的引用计数值就都变成了2. 当后来删除F1时，F3的引用计数值为2﹣1＝1.F2的引用计数值仍然保持不变，所以F2和F3的引用计数值分别是：1，1.
10．文件系统中，文件访问控制信息存储的合理位置是（ ）.
A. 文件控制块 B. 文件分配表 C. 用户口令表
相关内容
相关标签