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

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

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2011 年上海海事大学数据结构考研真题一.判断题（本题 20 分，每小题 2 分） 1.为了很方便地插入和删除数据，可以使用双向链表存放数据。 2.两个栈共享一片连续内存空间时，为了提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 3.数组是同类型值的集合。 4.在查找树（二叉排序树）中插入一个新结点，总是插入到叶子结点的下面。 5.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中顶点的个数有关，而与图的边数无关。 6.顺序存储方式只能用于存储线性结构，不能用于存储二叉树。 7.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。 8.数据的逻辑结构被分为集合结构、线性结构、树型结构、图结构四种。 9.将一棵树转换成二叉树后，根结点没有左子树。 10.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。二.填空题（本题 30 分，每空 2 分）

8.若对线性表进行的操作主要不是插入和删除，则该线性表宜采用（14）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用（15）__存储结构。三.选择题（本题 20 分，每空 2 分） 1.权值为{1，2，6.8}的四个结点构成的哈夫曼树的带权路径长度是（）。 A)18 B) 28 C)19 D)29 2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A)1/2 B)1 C)2 D)4 3.无向图 G=（V，E），其中∶V={a，b，c，d，ef，E={（a，b），（a，e），（a，c），（be），（c， f，（d），（e，d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。 A) a,b,e,c,d,f B)a,c,f,e,b,d C) a,e,b,c,f,d D) a,e,d,f,c,b 4.有 8 个结点的无向连通图最少有（）条边。 A)5 B)6 C) 7 D) 8 5.在一棵度为 3 的树中，度为 3 的节点个数为 2，度为 2 的节点个数为 1，则度为 0 的节点个数为（）。 A)4 B)5 C)6 D)7

6.对广义表 L=（a，b），（c，d），（e，f）执行操作 tailtail（L））的结果是（）。 7.引起循环队列队头位置发生变化的操作是（）。 A）出队 B）入队 C）取队头元素 D）取队尾元素 8.一个栈的入栈序列是 a，b，c，de，则栈的不可能的输出序列是（）。 A) edcba B) decba C) dceab D)abede 9.下列排序算法中，不稳定的排序是（）。 A）直接插入排序 B）冒泡排序 C）堆排序 D）选择排序 10.顺序栈 S 中 top 为栈顶指针，指向栈顶元素所在的位置，elem 为存放栈的数组，则元素 e 进栈操作的主要语句为（）。 A)s.elem[ top] =e; s.top=s.top+1; B) s.elem [ top+1] =e; s.top=s.top+1; C) s.top=s.top+1; s.elem [ top ] =e; C) s.top=s.top+1; s.elem [ top+1 ]=e; 四.（本题 20 分，每小题 10 分） 1.某二叉树的结点数据采用顺序存储结构如下∶ 试解答下列问题∶ 1）画出该二叉树;

2）画出把此二叉树还原成森林的图; 2.已知一棵二叉树的中序序列和后序序列分别为，中序序列∶CDBAFGEKHL 后序序列∶DCBGFKLHEA 请根据画出该树的结构并写出其先序序列。五.（本题 12 分）设散列表为 HT[0.12]，即表的长度为 13。散列函数为∶H（key）=key%13，采用线性探测再散列法解决冲突，若插入的关键码序列为{25，9.36.43.15.28.51.67，94}。 1.试画出插入这 9 个关键码后的散列表。 2.计算在等概率情况下查找成功的平均查找长度 ASL。六.（本题 12 分，每小题 6 分）已知待排序记录的关键字序列为 {435，183，506，289，318，705，76，632，826，245}，需要按关键字值递增的次序进行排序，请分别写出用下列两种排序方法进行第一趟扫描的过程和结果。 1.以第一个元素为基准的快速排序 2.冒泡排序八.编程题（本题 24 分，每小题 12 分） 1.已知 A、B 为两个递增有序的线性表，试编写函数实现对 A 表的如下操作∶删去其中那些在 B 表中出现的元素。 2.已知 T 为一棵二叉排序树，设计算法按递减次序打印各节点的值。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料