|
大连海事大学大连海事大学大连海事大学大连海事大学 1996 年硕士研究生入学考试试题年硕士研究生入学考试试题年硕士研究生入学考试试题年硕士研究生入学考试试题
数据结构数据结构数据结构数据结构
一、解释下列名词（10 分）
1 数据 2 数据元素 3 数据对象 4 数据结构 5 线性表
6 队列 7 广义表 8 树 9 图 10 串
二 1 试编是制在线性表L={12,13,21,24,30,42,}中插入数据元素
26 的程序。（该程序用turbo Pascal 语言编制并能在记算机上运行结点类型
为链式结构）（16 分）
2 请分别叙述线性表的顺序有序结构和链式有序结构的优，缺点。（2 分）
3 评价一个好的算法您是从哪几方面来考虑的？（2 分）
4 （1）什么是递归程序？
（2）递归程序的优，缺点是什么
（3）递归程序在执行时应借助于什么来完成？
（4）递归程序的入口语言出口语言一般用什么语句实现（4 分）
三 1 KMP 酸法（字符串匹配算法）较Brute(朴素的字符串匹配)算法有哪些
改进？（2 分）
2 描述以下概念的区别（6 分）
（1）空格与空串 （2）折半查找与哈希查找
（3）拓扑排序与冒泡排序
四 1 数组中每个元素的长度32 个二进位行下表从-1 到9，列下标从 1 到11，
从首址S 开连续存放主存序器中，主存储器字长为16 位。
求：（1）存放该数组所需多少单元？
（2）存放数组第4 列所有元素至少需多少单元？
（3）数组按行存放时，元素A[7，4]的起始地址是多少？
（4）数组按列序存放时元素的起始地址是多少？（共6 分）
2 画出下列广义表的存储结构图（2 分）
A=（ ），B=（A，e,d）
C=(A) ,D=(e,(a,b,B),A,C)
五 1 证明：对任意满二叉树的分支数B,满足 B=2(n0-1),其中 n0 为终端结点数.(2 分)
2.假设用于通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别
为7，19，2，6，32，21，10。试为这个字母设计哈夫曼编码。使用 0——7 的
二进制表示形式是另一 种编码方案。对于上述实例，比较两种方案的优缺
点。（8 分）
六 1 下图所示为一有向图，请给出该图的下述要求：（4 分）
（1）每个顶点的入度和出度；（2）邻接矩阵
（3）邻接表 （4）逆邻接表
购买考研、考博历年真题资料，请到考研秘籍网| http://www.kaoyanmiji.com 查询清单、购买下载电子版真题
购买考研、考博历年真题资料，请到考研秘籍网| http://www.kaoyanmiji.com 查询清单、购买下载电子版真题
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
