2018年广东暨南大学数据结构考研真题.doc-资料库

第1页 / 共7页

第2页 / 共7页

第3页 / 共7页

第4页 / 共7页

第5页 / 共7页

第6页 / 共7页

第7页 / 共7页

2018 年广东暨南大学数据结构考研真题学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构 081201，计算机软件与理论 081202，计算机应用技术 081203，软件工程 083500，计算机技术(专业学位) 085211 考试科目名称及代码：数据结构 830 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、单项选择题(每题 2 分，共 30 分) 1. 任何一棵二叉树 T, 如果度为 1 的结点数为 2，度为 0 结点数为 11，其分支数为 ( ) 。 A. 23 B. 22 C. 24 D. 21 2. 深度为 k 的二叉树至多有( ) 个结点(k>=1)； A. 2k B. 2k-1 C. 2k+1 D.2k-1 3. 已知一棵二叉树结点的中序序列为 BDCEAFHG, 后序序列为 DECBHGFA, 则结点的先序序列为( ) 。 A. ABCDEFGH B. DGBFHCA C. DECBGFAH D. CAFHGDB 4. 在有向图的逆邻接表存储结构中，顶点 v 在表结点中出现的次数是（）。 A. 顶点 V 的度 B. 顶点 V 的出度 C. 顶点 V 的入度 D. 依附于顶点 V 的边数 5. 顺序栈 s 的 GetTop(s, e)操作是用 e 返回 s 的栈顶元素，则下列( )是正确的操作。 A. e=*(s.top) B. e=*(s.top-1) C. e=*(--s.top) D. e=s.top-1 6. 若线性表最常用的操作是存取第 i 个元素及其前趋的值, 则采用( )存储方式节省时间. A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表 7. 在一棵非空 m 阶的 B-树上，除根之外的所有非终端结点（）。 A. 至少有  2/m 棵子树 B. 至多有  2/m 棵子树 C. 至少有  2/m 棵子树 D. 至多有  2/m 棵子树 8. 若用单链表来表示队列，最适合队列操作的是（）。 A. 带尾指针的非循环队列 B. 带尾指针的循环链表 C. 带头指针的非循环链表 D. 带头指针的循环链表 9. 下面的序列中, ( )是堆。

A. 12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49 B. 12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49 C. 12, 36, 27, 20, 40, 34, 98, 81, 73, 55, 49 D. 12, 36, 35, 65, 40, 34, 98, 81, 73, 55, 49 10. 设有一个 10 阶的对称矩阵 A, 采用压缩存储方式, 以行序为主序存储其下三角,a11为第一个元素, 其首存储地址为 1, 每个元素占 1 个地址空间, 则 a85 的地址为( ) 。 A. 32 B. 33 C. 34 D. 40 11. 用带头结点的单链表存储队列，其队头指针指向头结点，队尾指针指向队尾结点，则在进行出队时（）。 A. 仅修改队头指针 B. 仅修改队尾指针 C. 对头、尾指针都要修改 D. 对头、尾指针都可能要修改 12. 由权为 7,2,4,5 的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（）。 A. 33 B. 36 C. 35 D. 34 13. 现有一"遗传"关系：设 x 是 y 的父亲，则 x 可以把它的属性遗传给 y。表示该遗传关系最适合的数据结构为 ( ) 。 A．向量 B．图 C．树 D．二叉树 14. 线性表是具有 n 个 ( )的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 15. 在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（）。 A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序二．填空题(每空 2 分，共 20 分) 1. 单链表中设置头结点的作用是 2. 操作系统中先来先服务是数据结构应用的典型例子。 3. 对线性表进行折半查找时，要求线性表必须。。 4. 在中序线索二叉树上，若当前访问节点的右标志为 0，根据中序遍历的定义，它的后继结点是。 5. 哈夫曼树是带权路径长度的二叉树 , 通常权值较大的结点离根。 6. 在 m 阶 B-树中某结点插入一个关键字后，若该结点的关键字数目已达时，就要对

该结点进行分裂。 7. 顺序查找一个共有 n 个元素的线性表，其时间复杂度为。 8. 对于含有 n 个顶点 e 条边的无向连通图, 利用广度优先搜索遍历图的时间复杂度为。 9. Dijkstra 算法是按次序产生一点到其余各定点最短路径的算法。三．判断题（每题 1 分，共 10 分，正确的选 t，错误的选 f） 1. 将一棵树转换成二叉树后，根结点无右子树。（） 2. 归并排序是不稳定的排序方法。（） 3. 在一个有向图的邻接表中，如果某个顶点的链表为空，则该顶点的出度一定为零。（） 4. 在二叉树的第 6 层上至多有 31 个结点。（） 5. B-树和 B+树都能有效地支持随机检索。( ) 6. 图 G 的最小生成树的代价一定不大于其他生成树的代价。 ( ) 7. 一个无序的元素序列可以通过构造一棵二叉排序树而变成一个有序的元素序列。（） 8. 图的多重邻接表表示法中，表中结点的数目是图中边的条数。（） 9. 对特殊矩阵压缩可以降低运算的时间复杂度。 ( ) 10. 无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵。（）四. 简答题（45 分） 1. 利用拓扑排序的方法求出图 1 所示有向图的所有拓扑序列。对于有向无环图，还可使用什么方法获得拓扑序列？（10 分）图 1 2. 一棵二叉树，若根结点的左右子树均有三个结点，其左子树的先序序列与中序序列相同，右子树的中序序列与后子序序列相同，试构造该二叉树。（7 分）

3. 已知序列(12,18,4,3,6,13,2,9,19,8)。请给出采用希尔排序对该序列作升序排序的每一趟结果（步长分别为 5,3,2,1）。（8 分） 4. 设有一组关键字(33,41,20,24,30,13,01,67), 采用散列函数 H(key)=(3*key) %11, 采用线性探测再散列解决冲突, Hi=(H(key)+di)%11,其中 di=1,2,…,10. 试在 0～10 的散列地址空间中对该关键字序列（按从左到右的次序）构造散列表，并计算在查找概率相等的前提下，查找成功时的平均查找长度。（10 分） 5. 已知图 2 所示的有向图。设其顶点 a,b,c,d,e 表示一个乡的 5 个村庄，弧上的权值表示为两村之间的距离。乡内要建立一所学校，问学校设在哪个村庄才能使从各村出发到学校的距离总和最小。（要求回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果）。（10 分）五、算法填空（共 2 小题，每空 2 分，共 20 分）图 2 1. 已知一个顺序存储线性表的元素递增有序排列。下面的算法实现删除该表中值相同的元素。请在__________处填上适当内容，使其成为一个完整算法。 typedef struct { ElemType *elem; int int length ; listsize ;

} SqList; void dele(SqList &L) { int i=0, j=1; while ( (1) ) { if ( L.elem[j]!=L.elem[i]) L.elem[++i]= (2) ； (3) ; } L.length= (4) ; } 2. 下面算法是用 Dijkstra 算法求有向网 G 的 v0 顶点到其余顶点 v 的最短路径 P[v]及其带权长度 D[v]。若 P[v][w]为 TRUE，则 w 是从 v0 到 v 当前求得最短路径上的顶点。final[v] 为 TRUE 当且仅当 v∈S（S 为已求得最短路径的终点的集合）, 即已经求得从 v0 到 v 的最短路径。请在__________处填上适当内容，使其成为一个完整算法。 typedef struct ArcCell{ VRType adj; InfoType *info; //该弧相关信息的指针 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]； tpyedef struct{ VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph; void ShortestPath_DIJ( MGraph G, int v0, PathMatrix &P, ShortPathTable &D) { for (v=0; v

if (D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; } } D[v0] = 0; (7) ; for (i=1; i

资料库

2018年广东暨南大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料