2018年湖北华中农业大学数据结构与算法考研真题.doc

发布时间：2023-11-16 发布人：admin 分类：说明书资料大小：0.19M 资料格式：doc 举报版权申诉

第1页 / 共4页

2018年湖北华中农业大学数据结构与算法考研真题.doc.pdf-第2页.jpg

第2页 / 共4页

2018年湖北华中农业大学数据结构与算法考研真题.doc.pdf-第3页.jpg

第3页 / 共4页

2018年湖北华中农业大学数据结构与算法考研真题.doc.pdf-第4页.jpg

第4页 / 共4页

文本预览

2018 年湖北华中农业大学数据结构与算法考研真题一、名词解释（共 20 分，每题 4 分） 1、算法及算法的特性 2、树的度及深度 3、完全二叉树 4、索引文件 5、强连通性二、选择题（共 30 分，每题 2 分） 1、设栈 S 和队列 Q 的初始状态均为空，元素 ABCDEFG 依次进栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素的出队顺序是 BDCFEAG，则栈 S 的容量至少是∶ A.1 B.2 C.3 D.4 2、已知一棵完全二叉树的第六层（根为第一层）有 8 个叶子结点，则完全二叉树的结点个数最多是∶ A.39 B.52 C.111 D.119 3、下列叙述中不符合 m 阶 B 树定义要求的是∶ A.根结点最多有 m 棵子树 B.所有叶结点在同一层上 C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接 4、若无向图中含有 7 个顶点，则保证图在任何情况下都是连通的，需要的边数最少是∶ A.6 B.15 C.16 D.21 5、对一组数据（7，17，21，93，10，16）进行排序，若前三趟排序结果如下，则采用的排序方法是∶ 第一趟∶7，17，21，10，16，93 第二趟∶7，17，10，16，21，93 第三趟∶7，10，16，17，21，93 A.冒泡排序 B.希尔排序 C.归并排序 D.基数排序 6、已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是∶

A.115 B.116 C.18955 D.1896 7、已知字符串 S 为"abaabaabacacaabaabcc".模式串 t 为"abaabc"，采用 KMP 算法进行匹配，第一次出现"失配" 时，i=j=5，则下次开始匹配时，i 和 j 的值分别是∶ A.i=1;j=0; B.i=5;j=0; C.i=5;j=2; D.i=6;j=2; 8、用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是∶ A.存储效率 B.数列函数 C.装填（装载）因子 D.平均查找长度 9、循环队列放在一维数组 A[O·M-1]中，endl 指向队头元素，end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1 个元素。初始时为空。下列判断队空和队满的条件中，正确的是∶ A.队空∶end1 == end2;队满∶endl ==（end2+1）mod M B.队空∶ end1 == end2;队满∶end2 ==（endl+1）mod （M-1） C.队空∶end2 ==（end1+1）mod M;队满∶ end1 ==（end2+1）mod M D.队空∶end1==（end2+1）mod M;队满∶ end2 ==（endl+1）mod（M-1） 10、非空的循环单链表 head 的尾结点（由 p 所指向）满足∶ A. p->next==NULL; B. p==NUL; C. p->next==head; D. p==head 11、查找效率最高的二叉排序树是∶ A.所有结点的左子树都为空的二叉排序树 B.所有结点的右子树都为空的二叉排序树 C.平衡二叉树 D.没有左子树的二叉排序树 12、下面关于求关键路径的说法不正确的是; A. 求关键路径是以拓扑排序为基础的 B.关键活动一定位于关键路径上 C.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 D. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 13、在一个单链表中，若 q 结点是 p 结点的前驱结点，若在 q 和 p 之间插入结点 s，则执行∶ A. p->next=s->next; s->next=p;

B. s->next=p->next;p->next=s; C. p->next=s;s->next=q; D. q->next=S; s->next=p; 14、设有一个对称矩阵 A，采用压缩存储方式，以行序为主序存储，al1 为第一个元素，其存储地址为 1，每个元素占一个地址空间，则 a85 地址为∶ A.23 B.33 C.18 D.40 15、就平均查找速度而言，下列几种查找速度从慢至快的关系是∶ A.顺序折半哈希分块 B.分块折半哈希顺序 C.顺序分块折半哈希 D.顺序哈希分块折半三、填空题（共 20 分，每题 2 分） 1、广义表 A=（x，（a，b，c，d））的表尾是____。 2、在双循环链表中，删除指针 p 所指结点的语句序列是____和____。 3、快速排序是____排序改进后的结果。 4、求解一个图的单源和多源最短路径的算法分别是____和 Floyd 算法。 5、通常称表示前驱和后继的指针叫做___，而这种使树中结点的空指针成员存放前驱或后继信息的过程叫做 6、图的______优先搜索类似于树的层次遍历。 7、设给定权值总数有 n 个，其哈夫曼树的结点总数为 ________ 8、希尔排序、快速排序和冒泡排序中____是稳定的排序方法。其二是调整堆。 9、堆排序的两个重要步骤其一是________ 10、KMP 算法中，串'ababaaababaa'的 next 数组为________。四、应用题（共 50 分，第 1-6 题每题 7 分，第 7 题 8 分） 1、给定二叉树的两种遍历序列，分别是∶ 前序遍历序列∶EBIDGCAHF; 中序遍历序列∶EIGDCBHFA，（1）试画出二叉树; （2）并给出二叉树的后序遍历序列。 2、下图是一个无向带权图，请按照 Prim 算法从 A 节点出发构造一棵最小生成树，并画出其生成过程。

3、给定一组数列（10，18，16，25，6，9，16）分别代表字符 A，B，C，D，E，F，G 出现的频率，试画出哈夫曼树的构造过程，并给出各字符的编码值。 4、已知长度为 12 的表（jan，feb，mar，apr，may，june，july，aug，sep，oct，nov， dec），请按表中元素顺序构造一棵二叉平衡树，并简单的画出构造过程。其中，无旋转的调整可以直接画在一张图上，有旋转的调整请单独画图并备注清楚。 5、给定关键字序列∶15.38.11.84.49.20.7.33.14.29.36。请写出以下 3 种排序方法的第一趟排序结果（1）选择排序（2）快速排序（3）增量为 4 的希尔排序;请写出建好一个大根堆的结果;请写出第一趟堆排序以后的结果。 6、设散列表的长度为 13，散列函数为 H（k）=k ，给定的关键码序列为 19.13.22，02， 68.15.84.26。试画出用线性探测法解决冲突时所构成的散列表，并求出平均查找长度 ASL。 7、用迪杰斯特拉（Dijkstra）算法求下图中 V1 顶点到其他个顶点的最短距离和最短路径，请根据下表补充完整的求解过程。提示∶Vj 为每次新并入的顶点，S 为已求得最短路径的顶点的集合。五、程序设计题（共 30 分，每题 10 分） 1、设计一个求二叉树的宽度的算法。 2、已知一个带表头结点的线性链表，试写出用直接插入排序方法将其结点按递增顺序排序的算法，算法中要尽可能少用辅助存储空间。 3、请设计深度遍历图的非递归算法。

分享到：

赞收藏

资料库

2018年湖北华中农业大学数据结构与算法考研真题.doc

相关推荐

考研

热门标签

最新资料