燕山大学数据结构2001考研试题研究生入学考试试题考研真题
● 摘要
2001年硕士研究生入学考试试题
科目：数据结构
一、 选择题（本题共十分，每小题2分）
1、栈和队列的共同点是（）
A 都是先进先出 B 都是先进后出
C 只允许在端点处插入和删除元素 D 没有共同点
2、 有一个10阶的对称矩阵A ，采用压缩存储方式， 以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址空间为（）
A 13 B33 C18 D40
3、快速排序方法在（ ）情况下最不利发挥其长处
A 要排序的数据量太大 B 要排序的数据中含有多个相同值 C 要排序的数据个数为奇数 D 要排序的数据已基本有序
4、一组纪录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，异地一个纪录为基准得到的一次划分结果为（ ）
A ．(38,40,46,56,79,84) B 、(40,38,46,79,56,84)
C ．(40,38,46,56,79,84) D 、(40,38,46,84,56,79)
5、对线性表进行二分查找时，要求线性表必须（ ）
A 以顺序方式存储 B 以顺序方式存储，且数据元素有序 C 以链接方式存储 D 以链接方式存储, 且数据元素有序
二、填空题（本题共30分，每小题3分）
1、 在一个单链表中的P^结点之前插入一个s^结点，可执行如下操作
（1） s^.next:=______________________
（2） p^.next:=s;
（3） t:=p^.data;
（4） p^.data:=________________________
（5） s^.data:=________________________
2、 已知广义表LS=(a.(b,c,d),e),运用head 和tail 函数取出LS 中原子b 的运算是____________
3、 数据的逻辑结构是指_________________________数据的存储结构基本上可分为_____________________,____________________
4、 假定查找有序表A[1..12]中每个元素的概率相等，则进行二分查找似的平均查找长度__________
5、 在图G 的临界表表示中，每个定点临界表中所含的结点数，对于无向图来说等于该顶点的_____________; 对于有向图来说等于该顶点的_____________;
三、简答题（本题共20分，每小题5分）
1． 一棵度为2的树与一棵二叉树有何区别？
2． 请提出一种判定一个有向图是否有环（回路）的方法。
3． 选择排序算法是否稳定？为什么？