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

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

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

文本预览

2015 年上海海事大学数据结构考研真题一.判断题（本题 10 分，每小题 1 分） 1.线性表若采用顺序存储结构时，要求内存中可用存储单元的地址必须连续。 2.线性的数据结构可以顺序存储，也可链接存储;非线性的数据结构只能链接存储。 3.线性表的逻辑顺序与物理顺序总是一致的。 4.单链表从任何一个结点出发，都能访问到所有结点。 5.一个栈的输入序列是 12345，则栈的输出序列有可能为 43521。 6.设串 S 的长度为 n，则 S 的长度不为 0 的子串个数为 n（n+1）/2。 7.树和二叉树的结点数目都可以为 0。 8.无向网的最小生成树是唯一的。 9.在图的拓扑排序序列中，任意两个相继结点 V 和 V 都存在从 V;到 V 的路径。 10.深度优先遍历可以判断出一个有向图中是否有环（回路）。二.填空题（本题 30 分，每空 2 分） 1.分析下列程序段，其时间复杂度分别为∶（1）(2) 2.在长度为 n 的顺序表中删除第 i 个元素（0≤isn-1）时，需要向前移动（3）个元素。 3.在单链表中，要删除某一指定的结点，必须找到该结点的（4）_结点。 4.广义表 A=（（a），（（b），c），（（d）））的长度是_（5）__，深度是（6）__，取表头和表尾函数分别为 head（）和 tail（），则从表中取出原子项 c 的运算为（7） 6.一个深度为 k 的、具有最少结点的完全二叉树按层次用自然数对结点编号，则编号最小的叶子的序号是 10，编号为 i 的结点所在的层次号是 11 7.在有 n 个顶点的有向图中，每个顶点的度最大可达 12 8.对线性表进行二分查找时，要求线性表必须 13。 9.在对 n 个元素进行冒泡排序的过程中，最好情况下的时间复杂度为 14

10.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置的方法，称为 15 三.选择题（本题 20 分，每空 2 分） 1.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运行时间。 A. 单链表 B.仅有头指针的单循环链表 C.双向链表 D.仅有尾指针的单循环链表 2.用一维数组 Q[0 ..n-1]来存储一个循环队列，每个数组单元存放一个队列元素，记 f 为队头指针，r 为队尾指针，都为数组下标，若空队列的初始状态 f=r=0，则计算队列中元素个数的公式（式中 mod 为取余）为（）。 3.串的长度是（)。 A.串中不同字符的个数 B. 串中不同字母的个数 C.串中所含字符的个数且字符个数大于 0 D. 串中所含字符的个数 7.如果 G 是一个具有 n（n>1）个顶点的连通无向图，T 是 G 的一棵生成树，那么 T 有（）条边。 A.n - 1

B.n C. n+1 D.n + 2 8.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是（）。 A. 二叉排序树 B. 哈夫曼树 C.线索二叉树 D. 堆 9.一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。 A.38,40,46,56,79,84 B.40,38,46,79,56,84 C.40,38,46,56,79,84 D.40,38,46,84,56,79 10. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是。 A.选择排序 B.快速排序 C.插入排序 D.合并排序四.应用题（本题 60 分，每小题 10 分） 1.已知一棵二叉树的中序序列和后序序列分别为，中序序列∶DGBAECHKF 后序序列∶GDBEKHFCA 请画出该树的中序线索树并写出其先序序列。 2.某通信系统中共包含九个字符∶A、B、C、D、E、F、G、H、K，各个字符出现概率分别为∶ 0.05、0.10、0.18、0.09、0.13、0.15、0.21、0.03、0.06，试为它们构造一棵 Huffman 树（哈夫曼树），并给出这些字符的哈夫曼编码。

4.设散列表为 HT[0..16]，即表的长度为 17。散列函数为∶H（key）=key %，采用平方探测再散列法解决冲突，若插入的关键码序列为 {213 ， 54 ， 69 ， 127 ， 145 ， 73 ， 116 ， 85,173,107,209,159,241,92,258,168}。 1）试画出插入这 16 个关键码后的散列表。 2）计算在等概率情况下查找成功的平均查找长度 ASL。 5.试画出按正整数序列{42，91，53，29，17，49，35，74，23，83，11}的顺序建立平衡二叉树，以及插入结点 62 后的平衡二叉树和再插入结点 26 后的平衡二叉树。 6.已知待排序记录的关键字序列为{351，412，326，837，258，529，733，302， 148，652，582，761，315}，需要按关键字值递增的次序进行排序，试回答下列问题。 1）步长为 5、3、1 的 Shell 排序; 2）堆排序初始建堆后结果。五.编程题（本题 30 分，每小题 10 分） 1.对给定的 m，编写一个函数求满足 1*2 + 2*（3+4）+ 3*（4+5+6）＋...+n*（（n+1）+（n+2） + …+（n+n））>= m 的最小的 n。 2.试设计一个算法，在带头结点的单链表中去重，即使 data 域值重复的结点只留下一个，其它的都删除。表头指针为 first，存储结构为∶ 3.试编写函数计算树中每一个结点的度（叶结点的度为 0）。树用孩子-兄弟表示的二叉链表存储，定义为∶

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料