数据结构与算法-考研(北京工业大学 2012 基本概念)

/ 知识库 / 试卷库

单项选择题（2012北京工业大学）

从问题空间中抽象出来的数学模型是指数据的【】

A、逻辑结构

B、存储结构

C、物理结构

D、逻辑结构和存储结构

答案解析

A

【解析】

关键词

存储；算法；绪论；基本概念；逻辑；数据结构；空间；抽象；数学模型；

北京工业大学

算法的时间复杂度是指【】

数据结构在计算机内存中的表示是指【】

假设线性表的长度为n，且采用顺序存储结构存储。当在线性表的任何位置上插入一个数据元素的概率相同时，插入一个数据元素需要移动元素的平均个数为【】。

在含有n个元素的顺序表中，算法时间复杂度为O(1)的操作是【】

将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为__________。

线性表选用顺序存储结构表示的适用场合是____________________。

双向链表的优势是____________________。

试写出在双向链表da中的插入操作算法，算法中插入位置的获取可直接引入getnodep(da,i)，其中参数da为双向链表，i是要插入的数据，要求算法中含有双向链表da的结点结构描述。

算术表达式(a+b)*(c-d/e)的后缀表达式为【】

如果入栈序列为ABCD，不可能出现的出栈序列是【】

基本概念

数据元素是数据的最小单位。

算法的空间复杂度是指【】

从逻辑上可以把数据结构分为【】两大类。

下面说法错误的是【】（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低

下面关于算法说法错误的是【】

一个算法应该是【】

算法必须具备【】这三个特性。

计算机算法指的是【】

算法的时间复杂度取决于【】

算法的计算量的大小称为计算的【】

单项选择题

线性表是具有n个【】的有限序列。

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为【】。（1≤i≤n+1）

线性表的静态链表存储结构与顺序存储结构相比优点是【】

算法分析的主要内容是【】

将下图所示的s所指点加到p所指点之后，其语句应为【】

设栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若存在1≤k≤n使得 ak=n，则当k≤i≤n时，ai 为【】

设栈的输入序列是（1，2，3，4），则【】不可能是其出栈序列。

按照“后进先出”原则组织数据的数据结构是【】

下列描述中，正确的是【】

在深度为7的满二叉树中，叶子结点的个数为【】