北科大1998年《数据结构》考研真题.pdf

北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解 详见：网学天地（详见：网学天地（www.e-）；咨询）；咨询 QQ：2696670126 1北京科技大学北京科技大学 1998 年硕士学位研究生入学考试试题年硕士学位研究生入学考试试题 考试科目：数据结构考试科目：数据结构 适用专业：计算机应用技术，计算机软件与理论适用专业：计算机应用技术，计算机软件与理论 一、回答下列问题。一、回答下列问题。1根据数据元素之间的逻辑关系，一般有哪几种基本数据结构？2元素的进栈序列为：a、b、c、d、e，运用栈操作，能否得到出栈序列 b、c、a、e、d 和d、b、a、c、e？3设一棵完全二叉树叶子节点数为 k，最后一层节点数2。4目前内部排序的方法大致可归纳为哪几类？二、代码填空题（二、代码填空题（pascal 语言）。语言）。Procedure delmax(:pointer);Var p,q,r:pointer;m:integer;Begin R:=l,p:=l.next;If pnil then M:=p.data;()(填空)p:=p.next;while pnil do if ()then ();m:=p.data;()p:=p.next;q:=r.next;()dispose(q);end;三、设某表三、设某表 h 如下：如下：A B C a1 a2 b1 c1 c2 X 其中 A、B、C 为子表名，a1、a2、b1、c1、c2、x 为其元素。1试用广义表形式表示 h，并写出运算 HEAD(h)和 TAIL(h)函数从 h 中取出单元素 a2的运算；2画出表的链式存储结构。北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解 详见：网学天地（详见：网学天地（www.e-）；咨询）；咨询 QQ：2696670126 2四、（四、（10 分，此题统考生做）分，此题统考生做）已知一棵二叉树的先序和中序遍历序类如下：已知一棵二叉树的先序和中序遍历序类如下：DLR 先序：A B D E C F G LDR 中序：B E D A F G C 请画出此二叉树的逻辑结构和后序线索二叉树。五、（五、（10 分）设无向图分）设无向图 G 如下：如下：1写出图 G 的邻接矩阵 A，并画出图 G 的邻接表结构；2写出按“深度优先搜索”算法遍历图 G 的所得到的各连通分量的顶点集；六、（六、（22 分）设记录关键字（分）设记录关键字（key）集合）集合 K=11，13，22，10，8，14，1以 K 为权集，构造一棵哈夫曼树，并求其加权路径长度 WPL；2依次取 K 中各值，构造一棵二叉排序树，并画出删除值 11 后的二叉排序树；3设选取的散列函数 H(key)=key MOD 11，解决冲突的方法为线性探测再散列，请按此条件将 K 中各值依次填入下表中：0 1 2 3 4 5 6 7 8 9 10 11 并求对该表的平均查找长度 ASL。七、（七、（10 分）设纪录关键字集合分）设纪录关键字集合 K=(27，6，38，2，62，12，60，49)写出对 K 进行“快速排序”时，各趟排序结束时的结果，并将 K 整成一个堆顶元素取最大值的堆。八、（八、（20 分，此题统考生做）用分，此题统考生做）用 PASCAL 语言（或类语言（或类 PASCAL 语言）完成下列各题：语言）完成下列各题：1设表达式 2+b*(c-d)-e/f 可以表示成如下二叉树结构：其中 t 为根结点指针，试运用后序遍历二叉树的表达式求值的算法：EXPVALUE 2写出求无向图 G 中各连通分量可调用的运算是：FIRST_ADJ