2004年上海海事大学数据结构考研真题.doc

发布时间：2022-09-19 发布人：admin 分类：说明书资料大小：0.44M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2004 年上海海事大学数据结构考研真题一、判断题（本题 20 分，每小题 2 分） 1 为了很方便地插入和删除数据，可以使用双向链表存放数据。 2 两个栈共享一片连续内存空间时，为了提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 3 数组是同类型值的集合。 4 若一棵二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点。 5 采用链地址法解决冲突时，若规定插入总是在链首，则插入任一个元素的时间是相同的。 6 在查找树（二叉排序树）中插入一个新结点，总是插入到叶子结点的下面。 7 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间人小与图中顶点的个数有关，而与图的边数无关。 8 散列表的平均查找长度只与表的长度有关，而与处理冲突的方法无关。 9 顺序查找法适用于存储结构为顺序或链表存储的线性表。 10 在外部排序时，利用选择树方法在能容纳 m 个记录的内存缓冲区中产生的初始归并段的平均长度为 2m 个记录。二、填充题（本题 25 分，每小题 5 分） 1 表长为 n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相同时，插入一个元素所需移动元素的平均个数为（1），删除一个元素所需移动元素的平均个数为（2）· 2 广义表 A=（a，b，（cd），（e，f，g）），取表头和表尾函数分别为 head（）和 tail（），则 tail head（tail tail （A））=（1），而从表中取出原子项 e 的运算为（2）_。 3 假定一棵树的广义表表示为 A（B （E），C（F（H，1，D， G），D）∶则该树的度为（1），深度为（2），终端结点（叶子）的个数为③3），C 结点的双亲结点为（4），其子孙有（5）个结点。 4 由带权为 3，9，6，2，5 的 5 个叶子结点构成一棵哈夫曼（Huffman）树，则其带权路径长度为（1）_。 5 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取（1）方法，

其次选取（2）方法，最后选取（3）方法;若只从排序结果的稳定性考虑，则应选取（4）方法∶若只从平均情况下排序最快考虑，则应选取（5）方法∶若只从最坏情况下排序最快并且要节省内存考虑，则应选取（6）方法。

1 画出该有向图以及它的邻接表存储方式;  2 若上述网络图是某一工程作业的 AOE 网，试计算每个结点的最早开工时间和最迟开工时间，并求出它的关键路径和完成该工程所需的最少时间。  七、（20 分）在内部排序的过程中，通常需要对待排序的关键码进行多遍扫描。采用不同的 排序方法，会产生不同的中间结果。 设要将序列（O、H、C、Y、P、A、M、S、R、D、 F、X）中的关键码按字母排序的升序重新排序。请分别使用冒泡排序、初始步长为 4 的 Shell

排序、归并排序和以第一个元素为分界元素的快速排序进行第一趟扫描的过程和结果，以及使用堆排序进行初始建堆的过程和结果。 

分享到：

赞收藏

资料库

2004年上海海事大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料