2018年云南省培养单位云南天文台862计算机学科综合(非专业)之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3，4先出栈的序列有34521、34215、34251共3个。
2． 串是一种特殊的线性表，_____；其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
3． 建立索引文件的目的是_____。
【答案】提高查找速度
4． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
5． 有向图G=(V, E) ，其中
权d 。E(G)为
，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。
【答案】50；4
6． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
7． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。
【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
第 2 页，共 74 页 ，用三元组表示弧及弧上的
8． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:
(_____i)；
＝
_____.
_____
【答案】a ＋l ；n%10
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
9． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
10．以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。
第 3 页，共 74 页
【答案】
二、单项选择题
11．下列有关RAM 和ROM 的叙述中, 正确的是（ ）。
Ⅰ.RAM 是易失性存储器, ROM 是非易失性存储器
Ⅱ.RAM 和ROM 都采用随机存取方式进行信息访问
Ⅲ.RAM 和ROM 都可用作Cache
Ⅳ.RAM 和ROM 都需要进行刷新
A. 仅Ⅰ和Ⅱ
B. 仅Ⅱ和Ⅲ
C. 仅Ⅰ、Ⅱ和Ⅳ
D. 仅Ⅱ、Ⅲ和Ⅳ
【答案】A
【解析】RAM 中的内容断电后即丢失(易失性) , ROM 中的内容断电后不会丢失(非易失性) , 同时RAM 和ROM 都采用随机存取方式(即CPU 对任何一个存储单元的存取时间相同) , 区别在于RAM 可读可写, ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新, 所以Ⅲ和Ⅳ的叙述都是错误的。
12．设与某资源相关联的信号量初值为3，当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）.
A.0、1
B.1、0
C.1、2
D.2、0
【答案】B
【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0.
13．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
A.(2，5，12，16)26(60，32，72)
B.(5，16，2，12)28(60，32，72)
C.(2，16，12，5)28(60，32，72)
D.(5，16，2，12)28(32，60，72)
【答案】B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记
第 4 页，共 74 页