北京航空航天大学数据结构1999.docxVIP

PAGE PAGE 1 北京航空航天大学数据结构1999-2002年研究生入学考试试题 北京航空航天大学1999年研究生入学考试 数据结构试题 1 （20分，每小题2分） 单项选择题 ①若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1) A．O(0) B．O(1) C.O(n) D．O(n2) ② 若在线性表中采用折半查找法查找元素，该线性表应该( )。 A．元素按值有序 B．采用顺序存储结构 C．元素按值有序，且采用顺序存储结构 D．元素按值有序，且采用链式存储结构 ③ 已知一算术表达式的中缀形式为A＋B *C-D/E，后缀形式为ABC *+DE/-，其前缀形式为( )。 A. –A+B*C/DE B. –A+B*CD/E C.-+*ABC/DE D.-+A*BC/DE ④ 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用( )遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 ⑤ 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行( )元素间的比较。 A．4次 B．5次 C. 7次 D．10次 ⑥ 对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的排序序列。 A. 前序 B．中序 C．后序 D．按层次 ⑦ 具有n个顶点的有向图最多有( )条边。 A．n B．n(n—1) C n(n+1) D. n2 ⑧ 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。 A．插入 B．选择 C．谢尔 D．二路归并 ⑨ 排序趟数与序列的原始状态有关的排序方法是( )排序法。 A. 插入 B．选择 C. 泡 D．快速 ⑩ 下面给出的四种排序法中( )排序法是不稳定性排序法。 A．插入 B．泡 C．二路归并 D．堆积 2 (10分) 已知n阶下三角矩阵A(即当ij时，有aij0)，按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组B中。请写出从第一列开始采用列序为主序分配方式时在B中确定元素aij的存放位置的公式。 3 （20分） 已知在某并发处理系统的Petri网基础上建立的可达图如图1所示。图中每个顶点表示系统运行中的一种状态，有向边(弧)表示事件(用t表示)，例如有向边(Vi，Vj)表示系统在状态Vi时出现该事件将引发系统由状态Vi到状态Vj。 请分别给出该可达图的邻接表、邻接矩阵以及邻接矩阵的三元组形式，要求每种存储结构能够表达出该可达图的全部信息，并分别对这三种形式中每个部分的含义(物理意义)予以简要说明。 若假设每个域（包括指针域）的长度为一个字节，请分别计算出这三种结构所占用的空间大小。 4 (本题10分，每小题5分) 在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助于一棵平衡二叉树(也称判定树)来模拟，树中结点的值为记录在文件中的位置序号。 若文件中有l 9个记录，请画出这棵判定树； 当文件中有n个记录时，求出该判定树的深度。 5 （10分） 已知非空线性链表第一个节点由list指出，请写一算法，交换p所指的节点与其下一个节点在链表中的位置（设p指向的不是链表最后那个节点）。 6 （15分） 已知Ackermann函数定义如下： 写出Ack(2，1)的计算过程。 写出计算Ack(m，n)的非递归算法。 7 （15分） 已知深度为h的二叉树采用顺序存储结构已存放于数组BT〔1：2h－1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为 根结点所在链结点的指针由T给出。 　北京航空航天大学 一九九八年招收研究生　　 题单号：461 数据结构试题（共5页） 本试卷共六大题。写算法的语言可以用类PASCAL语言，也可以用某一种程序设计语言，但不得采用生僻古怪的表示方法。 一、（本题共40分，每小题4分） 简要回答下列各题： 对一个算法进行分析的前提条件是什么？主要从哪几个大的方面对一个算法进行分析？ 2．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种