中国人民公安大学数据结构2005年考研真题考研试题

中国人民公安大学 2005 年硕士研究生入学考试
试题（数据结构）
请将所有答案标明题号，写在答题本上，试题纸上请勿答题。严禁在答题
纸密封线以外留下姓名、考号等任何标记，否则该卷无效。
一、 名词解释（每小题 5 分，共 30 分）
1． 描述线性表中三个概念的区别：头指针、头结点、首元结点（第 1 个元
素结点）。
2． 数据结构
3． 二叉排序树
4． 关键路径
5． 稀疏矩阵
6． 连通图
二、 单项/多项选择题（每空 3 分，共 30 分）
1． 具有 N 个结点的二叉树的二叉链表结构中，指针域为 NULL 的
数目应为（ ）；
A) N B) 2N
C) N+1； D) 2N+1
2． 假定有 T1、T2、T3、T4、T5 五个元素进栈，进栈次序为 T1T2T3T4T5，
不可能的出栈序列有（ ）；
A）T1T2T3T4T5 B）T5T4T3T2T1
C）T1T2T5T3T4 D）T3T2T4T5 T1
E）T3T5T2T4 T1 F）T2T4 T3T5 T1
3． 表达式(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+*/
4． 下列各函数是按照增长率由大至小的顺序排列的是（ ）；
A） mmm ,!,,m 2
3
3
2
B）
3
2
2
3
m,,,! mmm
C） mm ,,m,m! 3
2
2
3
D） !,m,, 2
3
3
2
mmm
5． 已知 L 是带表头结点的单链表，其 P 结点既不是首结点（第一
结点），也不是尾结点：
1) 删除 P 结点的直接后继结点的语句序列是（ ）；
2) 删除 P 结点的语句序列是（ ）；
3) 删除首结点的语句序列是（ ）；
4) 删除尾结点的语句序列是（ ）；
A) P=P→next ;