2017年云南大学软件学院904计算机程序设计[专业硕士]之数据结构考研题库
● 摘要
一、填空题
1． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树 【解析】二叉排序树
或者是一棵空树，或者是具有下列性质的二叉树：①若它
的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
2． 试利用下列栈和串的基本操作完成下述填空题。
initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；
置串 判串 返回联接
empty （st ） 判串空函数
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）
第 2 页，共 27 页
为空串；
是否相等的函数；
之后的串；
length （st ） 返回串st 的长度；
sub （S , i , 1） 返回S 中第i 个字符；
注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11
）（12）
取栈顶操作符 操作符取出后，出栈
将pre 的最后一个字符（操作数）加入到中缀式exp 的最后
编号，以rear 指示实际的队尾元素，现
若ch 是操作数且栈非空，则形成部分中缀表达式
栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符
如ch 是运算符，则入操作符栈s 判栈8是否为空
若读出ch 是操作数且栈为空，则按出错处理
3． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】
要在此队列中插入一个新元素，新元素的位置是（ ）。
4． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
5． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
6． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
第 3 页，共 27 页
【答案】
【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。
7． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。 8． 设有一个10阶对称矩阵A 采用压缩存储方式， （以行为主序存储：）则的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若的地址为将代入得33。
9． 设有个结点的完全二叉树顺序存放在向量则
【答案】
则
的地址为
若
中，其下标值最大的分支结点为_____。
【解析】最大的分支结点是最后一个叶子结点的父结点。
10．—个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
11．在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】
12．求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】 13
．
已
求REPLACE （S ，V , m ）=_____。
【答案】
14．设数组储，则元素为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
第 4 页，共 27 页
知
的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存
的存储地址为_____；若以列序为主序顺序存储，则元素
的存储地址