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

20202020 年考研计算机数据结构模拟试题及答案年考研计算机数据结构模拟试题及答案 三三 一、选择题30 分 1. 1. 字符串的长度是指 。 A 串中不同字符的个数 B 串中不同字母的个数 C 串中所含字符的个数 D 串中不同数字的个数 2. 2. 建立一个长度为 n 的有序单链表的时间复杂度为 A On B O1 C On2 D Olog2n 3. 3. 两个字符串相等的充要条件是 。 A 两个字符串的长度相等 B 两个字符串中对应位置上的字符 相等 C 同时具备A和B两个条件 D 以上答案都不对 4. 4. 设某散列表的长度为 100，散列函数 Hkk P，则 P 通 常情况下选择 。 A 99 B 97 C 91 D 93 5. 5. 在二叉排序树中插入一个关键字值的平均时间复杂度为 。 A On B O1og2n C Onlog2n D On2 6. 6. 设一个顺序有序表 A[114]中有 14 个元素，则采用二分法 查找元素 A[4]的过程中比较元素的顺序为 。 A A[1]，A[2]，A[3]，A[4] B A[1]，A[14]，A[7]，A[4] C A[7]，A[3]，A[5]，A[4] D A[7]，A[5] ，A[3]，A[4] 7. 7. 设一棵完全二叉树中有 65 个结点，则该完全二叉树的深度 为 。 A 8 B 7 C 6 D 5 8. 8. 设一棵三叉树中有 2 个度数为 1 的结点，2 个度数为 2 的结 点，2 个度数为 3 的结点，则该三叉链权中有 个度数为 0 的结点。 A 5 B 6 C 7 D 8 9. 9. 设无向图 G 中的边的集合 E{a，b，a，e，a，c，b， e，e，d，d，f，f，c}，则从顶点 a 出发实行深度优先遍历能 够得到的一种顶点序列为 。 A aedfcb B acfebd C aebcfd D aedfbc 10. 10. 队列是一种 的线性表。 A 先进先出 B 先进后出 C 只能插入 D 只能删除 二、判断题20 分 1. 1. 如果两个关键字的值不等但哈希函数值相等，则称这两个 关键字为同义词。 2. 2. 设初始记录关键字基本有序，则快速排序算法的时间复杂 度为 Onlog2n。 3. 3. 分块查找的基本思想是首先在索引表中实行查找，以便确 定给定的关键字可能存有的块号，然后再在相对应的块内实行顺序查 找。 4. 4. 二维数组和多维数组均不是特殊的线性结构。 5. 5. 向二叉排序树中插入一个结点需要比较的次数可能大于该 二叉树的高度。 6. 6. 如果某个有向图的邻接表中第 i 条单链表为空，则第 i 个 顶点的出度为零。 7. 7. 非空的双向循环链表中任何结点的前驱指针均不为空。 8. 8. 不论线性表采用顺序存储结构还是链式存储结构，删除值 为 X 的结点的时间复杂度均为 On。 9. 9. 图的深度优先遍历算法中需要设置一个标志数组，以便区 分图中的每个顶点是否被访问过。 10. 10. 稀疏矩阵的压缩存储能够用一个三元组表来表示稀疏矩 阵中的非 0 元素。 三、填空题30 分 1. 1. 设一组初始记录关键字序列为49，38，65，97，76，13， 27，50，则以 d4 为增量的一趟希尔排序结束后的结果为 _____________________________。 2. 2. 下面程序段的功能是实现在二叉排序树中插入一个新结点， 请在下划线处填上准确的内容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree; void bstinsertbitree *t-datak;t- lchildt-rchild0;} else if t-datak bstinsertt- lchild,k;else__________________________; } 3. 3. 设指针变量 p 指向单链表中结点 A，指针变量 s 指向被插入 的结点 X，则在结点 A 的后面插入结点 X 需要执行的语句序列s- nextp-next; _________________;。 4. 4. 设指针变量 head 指向双向链表中的头结点，指针变量p 指 向双向链表中的第一个结点，则指针变量p 和指针变量 head 之间的关 系是 p_________和 head__________设结点中的两个指针域分别为 llink 和 rlink。 5. 5. 设某棵二叉树的中序遍历序列为 ABCD，后序遍历序列为 BADC，则其前序遍历序列为__________。 6. 6. 完全二叉树中第 5 层上最少有__________个结点，最多有 _________个结点。 7. 7. 设有向图中不存有有向边，则其对应的邻接矩阵A 中的数 组元素 A[i][j]的值等于____________。 8. 8. 设一组初始记录关键字序列为49，38，65，97，76，13， 27，50，则第 4 趟直接选择排序结束后的结果为 _____________________________。 9. 9. 设连通图 G 中有 n 个顶点 e 条边，则对应的最小生成树上 有___________条边。 10. 10. 设有一组初始记录关键字序列为50，16，23，68，94， 70，73，则将它们调整成初始堆只需把 16 与___________相互交换即 可。 四、算法设计题20 分 1. 1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。 2. 2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 答案 一、选择题 1.C 2.C 3.C 4.B 5.B 6.C 7.B 8.C 9.A 10.A 二、判断题 1.对 2.错 3.对 4.错 5.错 6.对 7.对 8.对 9.对 10.对 三、填空题 1. 1. 49，13，27，50，76，38，65，97 2. 2. tbitree *mallocsizeofbitree，bstinsertt- rchild,k 3. 3. p-nexts 4. 4. head-rlink，p-llink 5. 5. CABD 6. 6. 1，16 7. 7. 0 8. 8. 13，27，38，50，76，49，65，97 9. 9. n-1 10. 10. 50 四、算法设计题 1. 1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。 void countnodebitree *bt,int countnodebt-lchil