2002 年招收攻读硕士学位研究生 入学考试命题专用纸 招生专业:计算机科学与应用技术 考试科目:数据结构 试题编号:418 注: 答题（包括填空题、选择题）必须答在专用答题纸上，否则无效) －、单选题（每小题 2 分，共 20 分） 1.在一个具有 n个结点的有序单链表中插入一个新的结点使得单链表仍然有序的时间复杂度为 A.O(logn) B.O(1) C.O(n2) D.O(n) 2.若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用 存储方式节省时间。 A.单向链表 B.双向链表 C.单循环链表 D.顺序表 3.用单链表表示的链式队列的队头在链表的 位置。 A.链头 B.链尾 C.链中 4.对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用 顺序实现编号。 A.前序遍历 B.中序遍历 C.后序遍历 D.层序遍历 5.己知一算术表达式的中缀形式为 A+ B*C-D/E，后缀形式为 ABC*+DE/-，其前缀形式为 。 A.-A+B*C/DE B.-A+B*CD/E C.- + *ABC/DE D.- +A*BC/DE 6.利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对的二叉排序树以后，查找元素 35 要进行 次元素间的比较。 A.4 B.5 C.7 D.10 7.对于一个具有 n个顶点和e 条边的图，来用邻接矩阵表示的空间复杂度为 。 A.O(n) B.O(e) C. O(n2) D. (n+e) 8.设连通图G 的顶点数 n，则 G 的生成树的边数为 。 A.n B.n-1 C.2n D，2n-1 9.下列排序算法中， 算法可能出现下面的情况:在最后一趟排序开始之前，所有元素都不在最终的位置上。 A.堆排序 B.冒泡排序 C.快速排序 D.插入排序 10.设n，m 为一棵二叉树上的两个结点，在中序遍历时，n在 m 前的条件是 A.n在 m 右方 B.n是 m 祖先 C.n在 m 左方 D.n是 m 子孙 二、判断题（判断下列各小题的叙述是否正确，若正确打“√”，否则打“×”，每小题 1分，共10 分） 1. 线性表中每个元素都有一个前驱和一个后继。 2. 顺序表中逻辑关系上相邻的两个元素在物理位置上也相邻。 3. 在栈为空的情况下，不能作出栈操作，否则会产生“下溢”。 4. 对广义表A=（a，（b，c），d）的运算 head（tail（A））的结果不是 b。 5. 图 G 的一棵最小生成树的代价未必小于 G 的其他任何一棵生成树的代价。 6. 若从某顶点开始对含有n 个顶点的有向图 G 迸行深度优化先遍历，...
