华中农业大学2021年《数据结构与算法》考研真题.pdfVIP

华中农业大学 2021 年《数据结构与算法》考研真题 一、名词解释 1、算法及算法的特性 2、树的度及深度 3、完全二叉树 4、索引文件 5、强连通性 二、选择题 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 算法进行匹配，第一次出现失配s[i]!=t[i]时， 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.3