大连海事96考研题

一 1。解释下列名词（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）逆邻接表