大连海事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)逆邻接表