上海海事大学数据结构及程序设计2014考研试题研究生入学考试试题考研真题
● 摘要
2014年上海海事大学攻读硕士学位研究生入学考试试题
（重要提示：答案必须做在答题纸上，做在试题上不给分）
考试科目代码 828考试科目名称 数据结构及程序设计
一、 填空题（共15题20空，每空2分，共40分）
1. 若一个栈的输入序列是1，2，3，…，n ，输出序列的第一个元素是n ，则第i 个输出的是 。
2. 一个需经常做插入、删除运算的线性表采用 存储结构比较合适。
3. 设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。
4. 数据结构可以形式地定义为是一个两元组（D ，S ）。其中，D 是数据元素的有限集，S 是 的有限集。
5. 在算法是正确的前提下，评价一个算法的两个标准是 和 。
6. 设树T 的度为3，其中度为1、2、3的结点个数分别为2、1、1，则T 中叶子结点的个数是 。
7. 设S=‘I am a student',则SubString(S,6,9) = 。
8. 假设有二维数组A 6×8，每个元素用相邻的5个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1200，若按行存储时，则元素A 14的第一个字节地址为 。
9. 已知二叉树各结点的先序、中序遍历序列分别为A 、B 、C 、D 、E 、F 和C 、B 、A 、E 、D 、F ，则后续遍历该二叉树得到序列为 。
10. 深度优先搜索遍历类似于树的______ 遍历，广度优先搜索遍历类似于树的______遍历，它们分别可以用______、______这两种数据结构来实现。
11. 折半查找的平均查找长度近似等于_____ ___。
则该二叉树的后序遍历序列为_ ____.
13. 有n 个顶点的无向图，至少需要_ __条边才能保证是连通的。
14. 已知广义表A=((a,b,c),(d,e,f)),则运算head(tail(head（A ）)))=__________________。
15. 栈结构允许进行删除操作的一端为_____________。
二、 选择题（共15题，每题3分，共45分）
1. 程序段
（1）i=1;k=0 （2） do{ （3） （4）
（5） k+ =10 * i; i++; }while(i<=n-1)