2018年武汉纺织大学数学与计算机学院848数据结构考研核心题库
● 摘要
一、填空题
1． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
2． 对n 个记录的表进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n (n－1) /2
【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要
3． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】
要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
4． 中缀式
运算结果为_____。 【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
5． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
6． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;
第 2 页，共 35 页 。 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，(c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式的；2；k
7． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；
【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py
8． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
9． 在单链表中设置头结点的作用是_____。
【答案】方便运算
10．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
二、解答题
11．设与记录
对应的关键字分别是
。如果存在
和使得j 且 成立，试证明经过一趟起泡后，一定有记录与进行交换。 【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极值。由题假设知在，又因之前且，则，故，即说明和是反序；设对于和之前全部记录:(其中包括) 中关键字最大为，故经过起泡排序前i-2次比较后， 必定交换。 的关键字一定为和Rf 为反序，由此可知 12．某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时, 若有空座位, 则到取号机上领取一个号, 等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时, 通过叫号选取一位顾客, 并为其服务。顾客和营业员的活动过程描述如下: 第 3 页，共 35 页 请添加必要的信号量和P 、V(或wait （ ）、signal （ ）) 操作, 实现上述过程中的互斥与同步。要求写出完整的过程, 说明信号量的含义并赋初值。 【答案】(1)互斥资源:取机号, 故设一个互斥信号量mutex 。 (2)同步问题:顾客需要获得空座位等待叫号, 当营业员空闲时, 将选取一位顾客为其服务。空座位的有、无影响等待顾客数量, 顾客的有、无决定两营业员是否能开始服务。另外, 顾客获得空座位后, 需要等待叫号和被服务, 顾客与营业员就服务何时开始有同步关系。设信号量teller , customer 和mutex 初值分别为0, 0和1, 设waiting 为整型量, 表示排队的储户数量, 其初始为0, 表示顾客初始时为0, 最大不超过10(10把座椅) , 各进程的具体实现如下所示: 座椅数, 也是最多排队的储户数 定义信号量 等待储户的柜员资源 排队等待服务的储户数量 对排队机操作的互斥量 在座椅上休息等待的储户数 储户进程 先获得排队机 若还有座椅则取号 取号, 占用座椅等待叫号 告知系统储户加 1 释放排队机 等待柜员叫号 进入窗口被服务 若没有座椅了, 则不取号 不取号, 释放排队机 离开 并发调度无限循环 叫号 需要获得排队机的控制权 将等候的顾客数减1 第 4 页，共 35 页