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

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

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2010 年上海海事大学数据结构考研真题一.判断题（本题 20 分，每小题 2 分） 1.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。 2.两个栈共享一片连续内存空间时，为了提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 3.单链表从任何一个结点出发，都能访问到所有结点。 4.假定 n 和 m 为二叉树中的两个结点，m 所在的层数大于 n 所在的层数，则前序遍历时 n 一定在 m 之后。 5.采用链地址法解决冲突时，若规定插入总是在链首，则插入任一个元素的时间是相同的. 6.在查找树（二叉排序树）中插入一个新结点，总是插入到叶子结点的下面。 7.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中顶点的个数有关，而与图的边数无关。 8.排序方法是否稳定的，指的是该方法在各种情况下的时间效率是否相差不大。 9.对大小均为 n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，它们对于查找成功的平均查找长度是相同的，而对于查找失败的平均查找长度是不同的。 10.索引无序文件是指主文件无序而索引表有序。二.填空题（本题 30 分，每空 2 分） 2.有一个二维数组 A[16，0.7]，每个数组元素用相邻的 6 个字节存储，存储器按字编址，那末，这个数组的体积是（3）个字节。假设存储数组的首地址是 0，则若按行存储，数组元素 A[2，4]的第一个字节的地址是__（4）_;若按列存储，数组元素 A[5，7]的第一个字节的地址是（5）。 3.广义表 A=（a，b，（c，d），（e，（f，g）），取表头和表尾函数分别为 head（）和 tail （），则 tail head （tail （tail （A）= _（6）_，而从表中取出原子项 e 的运算为_（7）

4.由带权为 3，9，6，2，5 的 5 个叶子结点构成一棵哈夫曼（Huffiman）树，则其带权路径长度为__（8），高度为__（9） 5.在堆排序、快速排序和归并排序中，若仅从存储空间考虑，则应首先选取_10 方法，其次选取_（1）方法，最后选取（12）_方法;若只从排序结果的稳定性考虑，则应选取（13）方法;若只从平均情况下排序最快考虑，则应选取（14）方法;若只从最坏情况下排序最快并且要节省内存考虑，则应选取_（15）__方法。三.选择题（本题 20 分，每空 2 分） 1.在一个单链表中，已知*q 结点是*p 结点的前驱结点，若在*q 和*p 之间插入*s 结点，则须执行操作_（A）_在双向循环链表中，在 p 所指的结点之后插入 s 指针所指的结点，其操作是__（B） 2.在一棵非空二叉树的中序遍历序列中，根结点的右边（C） C: （1）只有右子树上的所有结点（2）只有右子树上的部分结点（3）只有左子树上的所有结点（4）只有左子树上的部分结点 3.倒排文件的主要特点是___（D） D: （1）便于进行插入和删除运算（2）便于进行文件的合并（3）能大大提高次关键字的查找速度度（4）能大大节省存储空间 4.对于一个具有 n 个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为__（E）对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则表向量的大小为_（F），所有顶点邻接表的结点总数为_（G），采用邻接表存储的图的深度优先遍历算法四.（本题 20 分，第 1 题 12 分，第 2 题 8 分）

1.某二叉树的结点数据采用顺序存储结构如下∶∶ 试解答下列问题∶ 1）画出该二叉树; 2）写出结点值为 D 的双亲结点及左、右子树; 2.已知一棵二叉树的先序序列和中序序列分别为，先序序列∶ABDFKICEHJG 中序序列∶DBKFIAHEJCG 请根据画出该树的结构并写出其后序序列。五.（本题 12 分）设散列表为 HT[0.12]，即表的大小为 m=13。采用线性探测再散列法解决冲突，散列函数为∶ H（key）= key 13;若插入的关键码序列为{15，7，32，28，16，19，53，27}。 1.试画出插入这 8 个关键码后的散列表。 2.计算在等概率情况下查找成功的平均查找长度 ASL。六.（本题 12 分，每小题 6 分）已知待排序记录的关键字序列为{335，183，56，429，138，275，736，562，86， 385}，需要按关键字值递增的次序进行排序，请分别写出用下列两种排序方法进行第一趟扫描的过程和结果。 1.以第一个元素为基准的快速排序 2.冒泡排序

八. 编程题（本题 24 分，每小题 10 分） 1.编写一函数 ReverseQueue（ Queue &qu），利用队列和栈的基本运算将给定队列中的数据元素逆转顺序，同时简要说明所用到的每一个基本运算的功能。 2.有一个数学函数定义如下，试编写程序实现该函数。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料