解放军信息工程大学820数据结构2016年考研真题考研专业课真题
● 摘要
820数据结构
（共十一题，满分150分）
一、填空题（20分，每空2分）
1. 数据的存储结构可用四种基本的存储方法表示，它们分别是 、 、 和 。
2. 算法是指 。
3. 在n 个结点的单链表中要删除已知结点*p，需找到它的 ，其时间复杂度为 。
4. 设串s1=‘ABCDEFG ’，s2=‘PQRST ’，
则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2)) 的结果串是 。
5. 设数组a[1…100]的基地址为128，每个元素占2个存储单元，采用顺序存储方式存储，则元素a[52]的存储地址为 。
6. 一个广义表为L= ((a,b),(c,d),(e,f))，则 GetHead ( GetTail ( GetTail (L))) 为 。
二、选择题（20分，每题2分）
1. 设某棵二叉树的先序遍历序列为ABCDE ，中序遍历序列为BADCE ，则后序遍历该二叉树得到序列为（ ）。
(A)BCDEA (B) BDECA (C) ACDEB (D) BADEC
2. 设一组初始记录关键字序列(54，29，62，30，86) ，以第一个记录关键字54为基准进行一趟快速排序的结果为（ ）。
(A) 29，30，54，86，62 (B) 30，29，54，86，62
(C) 29，30，62，54，86 (D) 30，29，54，62，86
3．最坏情况下，在二叉排序树中插入一个结点的时间复杂度为（ ）。
(A) O(1) (B) O(n2) (C) O(log2n) (D) O(n)
4．下列四种排序中，（ ）的空间复杂度最大。
(A) 快速排序 (B) 冒泡排序 (C) 归并排序 (D) 希尔排序
5. 设一采用顺序存储的一组元素，其关键字序列为 (2,8,21,37,51,78,89,92,99)，则用二分查找方法查找关键字为68的元素时关键字比较次数为（ ）。
第1页 共5页
相关内容
相关标签