2014年江西理工大学数据结构考研真题.doc

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

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

文本预览

2014 年江西理工大学数据结构考研真题一、选择题（每小题 2 分共 20 分） 1.数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 SA 开始连续存放的存储器内，该数组按行存放，元素 A[8][5]的起始地址为（）. A.SA＋141 B.SA＋144 C.SA＋22 D.SA＋225 2.下面关于串的的叙述中，哪一个是不正确的?（） A.串是字符的有限序列 B. 空串是由空格构成的串 C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 3.设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为 M1，M2 和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是（） A. M1 B.M+HM2 C.M3 D.M2+M3 4.采用邻接表存储的图的广度优先遍历算法类似于二叉树的（） A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历 5.对稀疏矩阵进行压缩存储目的是（）。 A.便于进行矩阵运算 B.便于输入和输出

C.节省存储空间 D.降低运算的时间复杂度 6.下面哪一方法可以判断出一个有向图是否有环（回路）∶（）。 A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（） A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 8. 在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是 ∶（）。 A.p>next=s;s>next-p>next; B.s→next=p→nextp>next=s; C. p->next=s;p>next=s->next; D.p>next=s→next;p>next=s; 9.深度为 5 的二叉树至多有（） A. 16 B.32 C. 31 D.108 10.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100），当折半查找值为 82 的结点时，（）次比较后查找成功。 A.11 B.5 C.4 D.8 二、判断题（每小题 2 分共 20 分）

1.线性表的特点是每个元素都有一个前驱和一个后继。（） 2.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（） 3.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（） 4.数组不适合作为任何二叉树的存储结构。（） 5.二维以上的数组其实是一种特殊的广义表。（） 6.完全二叉树中，若一个结点没有左孩子，则它必是树叶。（） 7.拓扑排序算法仅能适用于有向无环图。（） 8.在 AOE 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（） 9.在用堆排序算法排序时，如果要进行增序排序，则需要采用"大根堆"。（） 10.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。（）三.调用下列 C 函数 f（n），回答下列问题∶（10 分）（1）试指出 f（n）值的大小，并写出 f（n）值的推导过程;（2）假定 n=4，试指出 f（4）值的大小和执行 f（4）时的输出结果。四．设一棵二叉树的先序、中序遍历序列分别为∶先序遍历序列∶ABDFCE GH 中序遍历序列∶ BFDAGEHC（16 分）（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。（3）将这棵二叉树转换成对应的树（或森林）五.对于键值序列（49，38，65，97，76，13，27，50），使用堆排序算法完成由大到小的排

序过程。（10 分）要求∶ （1）画出初始堆（用二叉树表示）。（2）画出分别输出 1327 后重建的两个堆。六.对于下图，完成下列操作（18 分）（1）.给出本图的邻接表;（要求邻接点顺序由小到大）（2）.若从顶点 6 出发对该图进行遍历，在（1）的基础上给出本图的按深度优先搜索的顶点序列; （3）给出用 Prim 算法构造最小生成树的过程。七.下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求∶（20 分）（1）.划出该带权有向图的图形; （2）.从顶点 VI 为起点的广度优先遍历的顶点序列及对应的生成树; （3）.以顶点 V1 为起点的深度优先遍历生成树; （4）.由顶点 V1 到顶点 V3 的最短路径。

八.已知记录关键字集合为（53，17，19，61，98，75，79，63，46，49）要求散列到地址区间（100，101，102，103，，104，，105，106，107，108，109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数;形成的散列表;计算出等概率下查找成功时平均查找长度。（10 分）九.设 L 为单链表的头结点地址，其结点的数据都是正整数且无相同的，试设计利用直接播入的原则把该链表整理成数据递增的有序单链表的算法。（13 分）十.设二叉树采用二叉链表作为存储结构。写算是法实现按前序遍历顺序输出二叉树中结点的非递归算法。（13 分）要求定义所用结构。设栈已经定义∶initstack（S），stackempty（S）push（S，p），pop （S，p），分别为栈初始化，判栈空，入栈，出栈等操作

分享到：

赞收藏

资料库

2014年江西理工大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料