北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地（www.e-studysky.com）；咨询QQ：26966701261北京科技大学1998年硕士学位研究生入学考试试题考试科目：数据结构适用专业：计算机应用技术，计算机软件与理论一、回答下列问题。1．根据数据元素之间的逻辑关系，一般有哪几种基本数据结构？2．元素的进栈序列为：a、b、c、d、e，运用栈操作，能否得到出栈序列b、c、a、e、d和d、b、a、c、e？3．设一棵完全二叉树叶子节点数为k，最后一层节点数＞2。4．目前内部排序的方法大致可归纳为哪几类？二、代码填空题（pascal语言）。Proceduredelmax(:pointer);Varp,q,r:pointer;m:integer;BeginR:=l,p:=l^.next;Ifp<>nilthen[M:=p^.data;()(填空)p:=p^.next;whilep<>nildo[if()then[();m:=p^.data;]()p:=p^.next;]q:=r.^.next;()dispose(q);end;三、设某表h如下：ABCa1a2b1c1c2X其中A、B、C为子表名，a1、a2、b1、c1、c2、x为其元素。1．试用广义表形式表示h，并写出运算HEAD(h)和TAIL(h)函数从h中取出单元素a2的运算；2．画出表的链式存储结构。北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地（www.e-studysky.com）；咨询QQ：26966701262四、（10分，此题统考生做）已知一棵二叉树的先序和中序遍历序类如下：DLR先序：ABDECFGLDR中序：BEDAFGC请画出此二叉树的逻辑结构和后序线索二叉树。五、（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)=keyMOD11，解决冲突的方法为线性探测再散列，请按此条件将K中各值依次填入下表中：01234567891011并求对该表的平均查找长度ASL。七、（10分）设纪录关键字集合K=(27，6，38，2，62，12，60，49)写出对K进行“快速排序”时，各趟排序结束时的结果，并将K整成一个堆顶元素取最大值的堆。八、（20分，此题统考生做）用PASCAL语言（或类PASCAL语言）完成下列各题：1．设表达式2+b*(c-d)-e/f可以表示成如下二叉树结构：其中t为根结点指针，试运用后序遍历二叉树的表达式求值的算法：EXPVALUE2．写出求无向图G中各连通分量可调用的运算是：FIRST_ADJ
