上海海事大学数据结构2014考研试题研究生入学考试试题考研真题
● 摘要
2014年上海海事大学攻读硕士学位研究生入学考试试题
（重要提示：答案必须做在答题纸上，做在试题上不给分）
考试科目代码 考试科目名称 数据结构
一．判断题（本题10分，每小题1分）
1、若某顺序表采用顺序存储结构，每个元素占10个存储单元，首地址为200，则下标为11（第12个）的元素的存储起始地址为320。
2、若对线性表进行的主要操作不是插入和删除，则该线性表宜采用顺序存储结构。
3、对一个空栈按a, b, c, d, e, f, g顺序依次读入，经过多次入栈和出栈的操作后，能得到按f, e, g, d, a, c, b顺序的出栈序列。
4、假定在顺序表中每个位置插入的概率相同，向一个有64个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动33个元素。
5、含有3个结点（元素值均不相同）的二叉排序树共有30种。
6、n 个顶点的连通图至少有n-1条边。
7、在无向图G 的邻接矩阵A 中，若A[i][j]等于1，则A[j][i]等于0。
8、采用顺序检索法在一个有123个元素的有序顺序表中查找，若每个元素的查找概率相等，则成功检索的平均查找长度ASL 为61。
9、在散列存储中，装载因子 的值越大，发生冲突的可能性就越大。
10、快速排序是一种稳定的排序方法。
二．填空题（本题30分，每空2分）
1．分析下列程序段，其时间复杂度分别为：
i = m = 0;
while (m i++; s+=i; } m=0; for(i=1; i<=n; i++) for(j=2*i; j<=n; j++) m++; 2．广义表A = (a, (a, b), ((i, j), k), d, e)的长度是，深度是，取表头和表尾函数分别为head ( ) 和tail ( )，则head (tail (head (tail (A))))) = ⑸ ，而从表中取出原子项j 的运算为 ⑹ 。 3．有一个二维数组A[0..6][2..9]，每个数组元素占用8个存储单元，并且A[2][5]的存储地址为2080，若按行序为主序方式存储，数组元素A[4][6]的存储地址是 ⑺ 。 - 2014试题1/4 -