中国人民公安大学2005年硕士研究生入学考试试题（数据结构）
请将所有答案标明题号，写在答题本上，试题纸上请勿答题。严禁在答题纸密封线以外留下姓名、考号等任何标记，否则该卷无效。
一、名词解释（每小题5分，共30分）
描述线性表中三个概念的区别:头指针、头结点、首元结点（第1个元素结点）。
数据结构
二叉排序树
关键路径
稀疏矩阵
连通图
二、单项/多项选择题（每空3分，共30分）
具有n个结点的二叉树的二叉链表结构中，指针域为null的数目应为（ ）；
a) n b) 2n
c) n+1； d) 2n+1
假定有t1、t2、t3、t4、t5五个元素进栈，进栈次序为t1t2t3t4t5，不可能的出栈序列有（ ）；
a）t1t2t3t4t5 b）t5t4t3t2t1
c）t1t2t5t3t4 d）t3t2t4t5 t1
e）t3t5t2t4 t1 f）t2t4 t3t5 t1
表达式(15-3)*6/3*(20+6)的逆波兰式，正确的是（ ）；
a）15 3 6 3 20 6-*/*+ b）15 3-6 *3/20 6+*
c）15 3 - 6 3 20 6+*/* d）15 3-6 3*20 6+*/
下列各函数是按照增长率由大至小的顺序排列的是（ ）；
a） b）
c） d）
已知l是带表头结点的单链表，其p结点既不是首结点（第一结点），也不是尾结点:
删除p结点的直接后继结点的语句序列是（ ）；
删除p结点的语句序列是（ ）；
删除首结点的语句序列是（ ）；
删除尾结点的语句序列是（ ）；
p=p→next ;
p→next=p ;
p→next=p→next→next ;
p=p→next→next ;
while p !=null { p=p→next ;}
while p→next !=null { p=p→next ;}
while p→next !=q {p=p→next ;}
