北外考研网

北外考研培训辅导班有哪些



2017年计算机考研408数据结构真题(客观题)_2017年考研408真题-CSD…(2017年计算机的什么量子计算机在我国诞生)

1、下列函数的时间复杂度是。

int func ( int n){
int i0, sum0;
while(sum< n) sum i;
return i;
}

a、o(log n) b、o(n^1/2) c、o(n) d、o(nlog n)

答案b 解析

2、下列关于栈的叙述中。

ⅰ采用非递归方式重写递归程序时必须使用栈 ⅱ系统要用栈保存必要的信息 ⅲ即可确定出栈次序 ⅳ允许在其两端进行操作

a、仅ⅰ b、仅ⅰ、ⅱ、ⅲ c、仅ⅰ、ⅲ、ⅳ d、仅ⅱ、ⅲ、ⅳ

答案c 解析只允许在一端进行操作。因此ii正确。

3、适用于压缩存储稀疏矩阵的两种存储结构是。

a、三元组表和十字链表 b、三元组表和邻接矩阵 c、十字链表和二叉链表 d、邻接矩阵和十字链表

答案a 解析可用于表示树或森林。因此选项a正确。

4、要使一棵非空二叉树的先序序列与中序序列相同。

a、只有左子树 b、只有右子树 c、结点的度均为1 d、结点的度均为2

答案b 解析因此选项b正确。

5、已知一棵二叉树的树形如下图所示。

ac bd cf dg

答案b 解析b正确。

6、已知字符集{a。

a、a c g a b f h b、a d b a g b b c、a f b e a g d d、a f e e f g d

答案d 解析选项d正确。

7、已知无向图g含有16条边。

a、10 b、11 c、13 d、15

答案b 解析可列出方程43 3411,选项b正确。

8、下列二叉树中。

答案a 解析符合折半查找规则的树即是所求。 b选项因此正确。

9、下列应用中。

a、编译器中的词法分析 b、关系数据库系统中的索引 c、网络中的路由表快速查找 d、操作系统的磁盘空闲块管理

答案b 解析查询效率更加稳定。编译器中的词法分析使用有穷自动机和语法树。
2017年计算机考研408数据结构真题(客观题)_2017年考研408真题-CSD…(2017年计算机的什么量子计算机在我国诞生)插图
网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一般使 用空闲空间链表管理磁盘空闲块。故选项b正确。

10、在内部排序时。

ⅰ归并排序的程序代码更短 ⅱ归并排序的占用空间更少 ⅲ归并排序的运行效率更高

a、仅ⅱ b、仅ⅲ c、仅ⅰ、ⅱ d、仅ⅰ、ⅲ

答案b 解析前者空间复杂度是o(n),后者是0(1)。但是前者时间复杂度是o(nlogn), 后者是o(n^2)。 所以选项b正确。

11、下列排序方法中。

ⅰ. 插入排序 ⅱ选择排序 ⅲ起泡排序 ⅳ希尔排序 ⅴ堆排序

a、仅ⅰ、ⅱ b、仅ⅱ、ⅲ c、仅ⅲ、ⅳ d、仅ⅳ、ⅴ

答案d 解析因此选d。

LEAVE A RESPONSE

您的电子邮箱地址不会被公开。 必填项已用 * 标注

Related Posts

|京ICP备18012533号-326