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

北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解 详见：网学天地（详见：网学天地（www.e-）；咨询）；咨询 QQ：2696670126 1北京科技大学北京科技大学 1999 年硕士学位研究生入学考试试题年硕士学位研究生入学考试试题 考试科目：数据结构考试科目：数据结构 适用专业：计算机应用技术适用专业：计算机应用技术 计算机软件与理论计算机软件与理论 说明：统考生做一八题，单考生做一，二，三，五，七，九，十题。一、（16 分）回答下列各题：1对于一个数据结构，一般包括哪三个方面的讨论？2设单链表中某指针 P 所指结点（即 P 结点）的数据域为 DATA，链指针域为 NEXT，请写出在 P 节点之前插入 S 节点的操作（PASCAL 语句）。3请画出双端队列的示意图，并指明队中二个端点的位置及插入和删除方向。4一棵哈夫曼树的代权路径长度 WPL=？5一个二部图的邻接矩阵 A 是一个什么类型的矩阵？6设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？7在含有 N 个结点的平衡二叉排序树上进行等概率查找的时间复杂度 T（N）=？8一个 ISAM 文件除了主索引外，还包括哪两级索引？二、（12 分）判断单链表 L 中结点数据值是否对称相等的类 PASCAL 语言算法如下，其中link 为指针变量说明符，PUSH（S，x）和 POP（s）分别为进栈过程和出栈函数。另外，若表的长度为 0 或为 1，均视为对称。请写出算法中空白之处，完成其功能。北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解 详见：网学天地（详见：网学天地（www.e-）；咨询）；咨询 QQ：2696670126 2三、（10 分）设对称矩阵 10020300A00052050=1若将 A 中包括主对角线的下三角元素按列:的顺序压缩到数组 S 中，试求出 A 中任一元素的行列下标i,j（1i,j4）与 S 中元素的下标 K 之间的关系。2若将 A 视为稀疏矩阵时,画出其三元组表形式压缩存储表。四、（10 分 此题统考生做）已知一棵二叉树 BT 如下：1请画出此二叉树的带头结点的中序线索链表结构；2将次二叉树转换成森林 F，并写出对森林 F 进行先序遍历的结果。五.(12 分)某田径赛中各选手的参赛项目表如下:设项目 A，B，F 各表示一数据元素，若两项目不能同时举行，则将其连线（约束条件）。1根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构；2写出从元素 A 出发按“广度优先搜索”算法遍历此图的元素序列。六、（10 分）设记录的关键字（key）集合 K=52,41,95,21,14,28,82,29 北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解 详见：网学天地（详见：网学天地（www.e-）；咨询）；咨询 QQ：2696670126 31请依次取 K 中各值,以插入方式将 K 建成一棵 3 阶 B-树 T（T 初值为空）；2设 HASA 表空间 选取 HASA 函数的方法为“保留余数法”，解决冲突的方法为“二次探测再散列”，请按此条件将 K 中各值依次填入上表中，并求对该表的平均查找长度 ASL。七、（10 分）设记录的关键字集合 K=23，9，39，5，68，12，62，48，33，给定的增量序列 D=4，2，1，请写出对 K 按“SHELL 方法”排序时各趟排序结束时的结果；若每次以表的第一元素为基准（或枢轴），写出对 K 按“快速排序方法”排序时，各趟排序结束时的结果。八、（20 分 此题统考生做）用类 PASCAL 语言（或 PASCAL 语言）完成下列各题：1设头结点指针分别为A和B的两单链表按结点数据值递增有序，试写出将两链表合并成一个递增单链表的算法：UNION（A，B）（合并后链表的头指针为 A）；2设元素集合已存入整型数组 A1.n中，试写出依次取 A 中各值 Ai（1in）构造一棵二叉排序树 T 的非递归算法：CSBT(T，A)。九、（10 分 此题单考生做）设一棵二叉树的先序和中序遍历结果如下：先序：A B C D E F G H 中序：B _ C A _ F H _ 但一些元素未给出，请画出此二叉树的逻辑结构和后序遍历结果。十、（20 分 此题单考生做）用类 PASCAL 语言（或 PASCAL 语言）完成下列各题：1设单链表头结点指针为 L，结点数据为整型，试写出对链表 L 按“插入方法”排序的算法：LINSORT（L）。2 设一棵二叉树的根结点指针为 T，C 为计数变量，初值为 0，试写出对此二叉树中结点计数的算法：BTLC（T，C）。