资源描述：
《北京科技大学 北科大 1999年数据结构 考研真题及答案解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、布丁考研网，在读学长提供高参考价值的复习资料www.ibudding.cn北京科技大学1999年硕士学位研究生入学考试试题考试科目：数据结构使用专业：计算机应用技术计算机软件与理论说明：统考生做一~八题，单考生做一，二，三，五，七，九，十题。一．（16分）回答下列各题：1．对于一个数据结构，一般包括哪三个方面的讨论？2．设单链表中某指针P所指结点（即P结点）的数据域为DATA，链指针域为NEXT，请写出在P节点之前插入S节点的操作（PASCAL语句）。3．请画出双端队列的示意图，并指明队中二个端点的位置及插入和删除方向。4．一棵哈夫曼树的代权路径长度WPL=？5．一个
2、二部图的邻接矩阵A是一个什么类型的矩阵？6．设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？7．在含有N个结点的平衡二叉排序树上进行等概率查找的时间复杂度T（N）=？8．一个ISAM文件除了主索引外，还包括哪两级索引？二（12分）判断单链表L中结点数据值是否对称相等的类PASCAL语言算法如下，其中link为指针变量说明符，PUSH（sax）和POP（s）分别为进栈过程和出栈函数。另外，若表的长度为0或为1，均视为对称。请写出算法中空白之处，完成其功能。FUNCTIONxyz(L:link):boolean;VARp,q:link;n,
3、n1,i:INTEGER;BEGINP:=L^.next;q:=p;n:=0;WHILEq<>NILDO[n:=n+1;q:=q^.next];n1:=___________;FORi:=1TOn1DO[PUSH(S,p^.data);_____________];IF______________THENp:=p^.next;WHILE(__________)AND(_________=POP(S))DOP:=p^.next;IF___________THENRETURN(true)EISERETURN(false)END;三．（10分）设对称矩阵
4、1002
5、A=
6、0
7、300
8、
9、0005
10、布丁考研网，在读学长提供高参考价值的复习资料www.ibudding.cn
11、2050
12、1.若将A中包括主对角线的下三角元素按列:的顺序压缩到数组S中,即S:10002300050下标:12------------------K----------------910试求出A中任一元素的行列下标[i,j](1<=i,j<=4)与S中元素的下标K之间的关系.2.若将A视为稀疏矩阵时,画出其三元组表形式压缩存储表.四.(10分,此题统考生做)已知一棵二叉树BT如下:1.请画出此二叉树的带头结点的中序线索链表结构;2.将次二叉树转换成森林F,并写出对森林F进
13、行先序遍历的结果.五.(12分)某田径赛中各选手的参赛项目表如下:姓名
14、参赛项目ZHAO
15、ABEQIAN
16、CDSHUN
17、CEFLI
18、DFAZHOU
19、BF设项目A,B,…F各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件).1.根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构;2.写出从元素A出发按”广度优先搜索”算法遍历此图的元素序列.六.(10分)设记录的关键字(KEY)集合K={52,41,95,21,14,28,82,29}1.请依次取K中各值,以插入方式将K建成一棵3阶B-树T（T初值为空）；2.设HASA表空间H：地址：01234
20、567891011选取HASA函数的方法为“保留余数法”，解决冲突的方法为“二次探测再散列”，请按此条件将K中各值依次填入上表中，并求对该表的平均查找长度ASL。七．（10分）设记录的关键字集合K={23，9，39，5，68，12，62，48，33}，给定的增量序列D={4，2，1}，请写出对K按“SHELL方法”排序时各趟排序结束时的结果；若每次以表的第一元素为基准（或枢轴），写出对K按“快速排序方法”排序时，各趟排序结束时的结果。八．（20分此题统考生做）用类PASCAL语言（或PASCAL语言）完成下列各题：布丁考研网，在读学长提供高参考价值的复习资料www.i
21、budding.cn1．设头结点指针分别为A和B的两单链表按结点数据值递增有序，试写出将两链表合并成一个递增单链表的算法：UNION（A，B）（合并后链表的头指针为A）；2．设元素集合已存入整型数组A[1。。N]中，试写出依次取A中各值A[I]（1〈=I〈=N〉构造一棵二叉排序树T的非递归算法：CSBT（T，A）。九．（10分此题单考生做）设一棵二叉树的先序和中序遍历结果如下：先序：ABCDEFGH中序：B–CA—FH—但一些元素未给出，请画出此二叉树的逻辑结构和后序遍历结果。十．（20分此题单考生做）用类PASCAL语言（或PASCAL语言）完成下
