2013年武汉某校848数据结构真题

数据结构的形式定义Data_Structure（D,S）中

D表示:有限的数据元素集合
S表示:D里元素间关系的集合
1
2

以下程序的的时间复杂度是：

for i=2   to   n	
  for   j=2   to   i-1
  		++x；
问题角度：直接看++x执行了多少次

外圈for的有效循环为n-2+1次，也即是n-1次
内圈for
	2到2		1次
	2到3		2次
	2到4		3次
	2到5		4次
	。。。。。。。。
	2到n		n-2+1次=n-1次
问题变成：求和  从1+2+3+4+....+n-1
 				= [[n(n+1)]/2]-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度取最高次幂，也就是O（n^2）

一个空栈，push（s，5）、push（s，2）、push（s，4）、Pop（s，x）和Get（s，x）后x的值为：

   空栈 s.top=-1
   入栈	:判断栈是否满，不满top++，再压入元素
   出栈	:判断栈是否空，不空，取出栈顶元素，top--
   Push(s,5) 栈不满就把5压入栈顶
   Push(s,2) 栈不满就把2压入栈顶
   Push(s,4) 栈不满就把4压入栈顶
   Pop（s，x）栈不为空，弹出栈顶元素，用x表示
   GetTop（s，x）读栈顶元素，若栈非空，则用x返回栈顶元素
   5在最下面，2在5的上面，4在2的上面，4被弹出取，GetTop获取到的值是2
1
2
3
4
5
6
7
8
9

n个节点的树中，所有节点度数的和为多少？

 度：可以理解成节点上有几条边
 n个节点的树，有n-1个边，度就为n-1
1
2

树的度：树中节点的最大度数是树的度，下图树的度为4，叶子节点度为0。

树中的路径是由节点组成，路径长度是由边组成

表长为n的顺序存储结构的线性表插入一个元素平均移动元素个数为n/2

在含有n（n>1）个节点的树中,深度最小的树有几个分支节点？

 n>