2020年考研计算机数据结构模拟试题及答案二

20202020 年考研计算机数据结构模拟试题及答案年考研计算机数据结构模拟试题及答案 二二 一、选择题30 分 1.下列程序段的时间复杂度为 。 fori0; i A Om*n*t B Omnt C Omn*t D Om*tn 2.设顺序线性表中有 n 个数据元素，则删除表中第 i 个元素需要 移动 个元素。 A n-i B nl -i C n-1-i D i 3.设 F 是由 T1、T2 和 T3 三棵树组成的森林，与 F 对应的二叉树 为 B，T1、T2 和 T3 的结点数分别为 N1、N2 和 N3，则二叉树 B 的根结 点的左子树的结点数为 。 A N1-1 B N2-1 C N2N3 D N1N3 4.利用直接插入排序法的思想建立一个有序线性表的时间复杂度 为 。 A On B Onlog2n C On2 D O1og2n 5.设指针变量 p 指向双向链表中结点 A，指针变量 s 指向被插入的 结点 X，则在结点 A 的后面插入结点 X 的操作序列为 。 A p-rights; s-leftp; p-right-lefts; s-rightp- right; B s-leftp;s-rightp-right;p-rights; p-right- lefts; C p-rights; p-right-lefts; s-leftp; s-rightp- right; D s-leftp;s-rightp-right;p-right-lefts; p- rights; 6.下列各种排序算法中平均时间复杂度为On2是 。 A 快速排序 B 堆排序 C 归并排序 D 冒泡排序 7.设输入序列 1、2、3、、n 经过栈作用后，输出序列中的第一 个元素是 n，则输出序列中的第 i 个输出元素是 。 A n-i B n-1-i C nl -i D 不能确定 8.设散列表中有 m 个存储单元，散列函数 Hkey key p，则 p 选择 。 A 小于等于 m 的奇数 B 小于等于 m 的素数 C 小于等于 m 的偶数 D 小于等于 m 的合数 9.设在一棵度数为 3 的树中，度数为 3 的结点数有 2 个，度数为 2 的结点数有 1 个，度数为 1 的结点数有 2 个，那么度数为 0 的结点数 有 个。 A 4 B 5 C 6 D 7 10.设完全无向图中有 n 个顶点，则该完全无向图中有 条边。 A nn-1/2 B nn-1 C nn1/2 D n-1/2 11.设顺序表的长度为 n，则顺序查找的平均比较次数为 。 A n B n/2 C n1/2 D n-1/2 12.设有序表中的元素为13，18，24，35，47，50，62，则在其 中利用二分法查找值为 24 的元素需要经过 次比较。 A 1 B 2 C 3 D 4 13.设顺序线性表的长度为 30，分成 5 块，每块 6 个元素，如果采 用分块查找，则其平均查找长度为 。 A 6 B 11 C 5 D 6.5 14.设有向无环图 G 中的有向边集合 E{，，，}，则下列属于该有 向图 G 的一种拓扑排序序列的是 。 A 1，2，3，4 B 2，3，4，1 C 1，4，2，3 D 1，2，4， 3 15.设有一组初始记录关键字序列为34，76，45，18，26，54， 92，则由这组记录关键字生成的二叉排序树的深度为 。 A 4 B 5 C 6 D 7 二、填空题30 分 1. 1. 设指针 p 指向单链表中结点 A，指针 s 指向被插入的结点 X， 则在结点 A 的前面插入结点 X 时的操作序列为 1 s-next___________;2 p-nexts;3 tp-data; 4 p-data___________;5 s-datat; 2. 2. 设某棵完全二叉树中有 100 个结点，则该二叉树中有 ______________个叶子结点。 3. 3. 设某顺序循环队列中有 m 个元素，且规定队头指针 F 指向 队头元素的前一个位置，队尾指针 R 指向队尾元素的当前位置，则该 循环队列中最多存储_______队列元素。 4. 4. 对一组初始关键字序列40，50，95，20，15，70，60，45， 10实行冒泡排序，则第一趟需要实行相邻记录的比较的次数为 __________，在整个排序过程中最多需要实行__________趟排序才能 够完成。 5. 5. 在堆排序和快速排序中，如果从平均情况下排序的速度最 快的角度来考虑应选择_________排序，如果从节省存储空间的角度来 考虑则选择________排序。 6. 6. 设一组初始记录关键字序列为20，12，42，31，18，14， 28，则根据这些记录关键字构造的二叉排序树的平均查找长度是 _______________________________。 7. 7. 设一棵二叉树的中序遍历序列为 BDCA，后序遍历序列为 DBAC，则这棵二叉树的前序序列为____________________。 8. 8. 设用于通信的电文仅由 8 个字母组成，字母在电文中出现 的频率分别为 7、19、2、6、32、3、21、10，根据这些频率作为权值 构造哈夫曼树，则这棵哈夫曼树的高度为________________。 9. 9. 设一组记录关键字序列为 80，70，33，65，24，56，48， 则用筛选法建成的初始堆为_______________________。 10. 10. 设无向图 G如右图所示，则其最小生成树上所有边的权 值之和为_________________。 三、判断题20 分 1. 1. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。 2. 2. 对链表实行插入和删除操作时不必移动链表中结点。 3. 3. 子串“ABC”在主串“AABCABCD”中的位置为 2。 4. 4. 若一个叶子结点是某二叉树的中序遍历序列的最后一个结 点，则它必是该二叉树的先序遍历序列中的最后一个结点。 5. 5. 希尔排序算法的时间复杂度为 On2。 6. 6. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间 与图中顶点数无关而与图中边数相关。 7. 7. 中序遍历一棵二叉排序树能够得到一个有序的序列。 8. 8. 入栈操作和入队列操作在链式存储结构上实现时不需要考 虑栈溢出的情况。 9. 9. 顺序表查找指的是在顺序存储结构上实行查找。 10.10.堆是完全二叉树，完全二叉树不一定是堆。 四、算法设计题20 分