北京航空航天大学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/DEB、?A B*CD/EC、- *ABC/DED、- 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、nB、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(即当i3、（20分） 已知在某并发处理系统的Petri网基础上建立的可达图如图1所示。图中每个顶点表示系统运行中的一种状态，有向边(弧)表示事件(用t表示)，例如有向边(Vi，Vj)表示系统在状态Vi时出现该事件将引发系统由状态Vi到状态Vj。 ①请分别给出该可达图的邻接表、邻接矩阵以及邻接矩阵的三元组形式，要求每种存储结构能够表达出该可达图的全部信息，并分别对这三种形式中每个部分的含义(物理意义)予以简要说明。 ②若假设每个域（包括指针域）的长度为一个字节，请分别计算出这三种结构所占用的空间大小。
图1题3图 4、（本题10分，每小题5分) 在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助于一棵平衡二叉树(也称判定树)来模拟，树中结点的值为记录在文件中的位置序号。 ①若文件中有l9个记录，请画出这棵判定树； ②当文件中有n个记录时，求出该判定树的深度。 5、（10分） 已知非空线性链表第一个节点由list指出，请写一算法，交换p所指的节点与其下一个节点在链表中的位置（设p指向的不是链表最后那个节点）。 6、（15分） 已知Ackermann函数定义如下：
①写出Ack(2，1)的计算过程。 ②写出计算Ack(m，n)的非递归算法。 7、（15分） 已知深度为h的二叉树采用顺序存储结构已存放于数组BT〔1：2h－1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为 根结点所在链结点的指针由T给出。
页:
[1]