2018年北京工业大学城市交通学院894C语言与数据结构之数据结构考研核心题库
● 摘要
目录
2018年北京工业大学城市交通学院894C 语言与数据结构之数据结构考研核心题库（一） .... 2
2018年北京工业大学城市交通学院894C 语言与数据结构之数据结构考研核心题库（二） .. 14
2018年北京工业大学城市交通学院894C 语言与数据结构之数据结构考研核心题库（三） .. 28
2018年北京工业大学城市交通学院894C 语言与数据结构之数据结构考研核心题库（四） .. 40
2018年北京工业大学城市交通学院894C 语言与数据结构之数据结构考研核心题库（五） .. 51
一、填空题
1． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。
2． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数目。例f(5，3) ＝5, 有5种表示方式:3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1，1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
_____
_____；
}
_____；
}
，
_____)
②执行程序，f(6，4) ＝_____。
【答案】①1; 1; f(m, n ﹣1) ; n ②9
3． 试利用下列栈和串的基本操作完成下述填空题。
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 个字符；
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 的最后
4． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
5． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。
【答案】top ﹣1
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。
6． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
7． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】O(1)；O(n)；O(1)；O(1)
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
8． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
9． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。
【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)
相关内容
相关标签