复杂度专项练习

下面算法的时间复杂度是多少？

int f ( unsigned int n ) {
    if (n == 0 || n==1) 
        return 1;
    else 
        return n * f(n-1);
}

以下哪个数据结构不是多型数据类型()

判断一包含n个整数a[]中是否存在i、j、k满足a[i] + a[j] = a[k]的时间复杂度为（）

若用数组S[0…n]作为两个栈S1和S2的存储结构，对任何一个栈只有当S全满时才不能做入栈操作。为这两个栈分配空间的最佳方案是

有种数据结构叫跳跃列表（Skip List），它是一种基于并联的链表的随机化数据结构，其效率可比拟于二叉查找树（对于大于数操作需要O(log

n)平均时间）。它是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速跑道”，这里在层i中的元素按概率l/p出现在层i+1中。平均起来，每个元素都在p/(p-1)个列表中出现，而最高层的元素（通常是在跳跃列表前段的一个特殊的头元素）在O(logp n)个列表中出现。调节p的大小可以在内存消耗和时间消耗上进行折中。试分析在该数据结构中查找一个元素的平均时间复杂度。

若用数组S[0. .n-1]做为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（ ）。

长为N的字符串中匹配长度为M的子串的算法复杂度是多少？

当很频繁地对序列中部进行插入和删除操作时，应该选择使用的容器是（）

写出a*(b-c*d)+e-f/g*(h+i*j-k)的逆波兰表达式。

如入栈序列为1,2,3,4,5,则可能得到的出栈序列为()

在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为()

一个栈的入栈序列式ABCDE则不可能的出栈序列是:

给定一个m行n列的整数矩阵（如图），每行从左到右和每列从上到下都是有序的。判断一个整数k是否在矩阵中出现的最优算法，在最坏情况下的时间复杂度是________。

任何二叉树的后序线索树进行后序遍历时都必须用栈()

现有一个循环队列，其队头指针为 front，队尾指针为 rear，循环队列的总长度为 N，问怎么判断循环队列满了？

设输入序列是1,3,5....m,经过栈的作用后输出序列的第一个元素是m,则输出序列中第i个输出元素是()

执行完下列语句段后,i值为()

int f(int x){ 
    return ((x>0)?x*f(x-1):2) 
} 
int i; 
i=f(f(2));

入栈序列是：a1,

a3, a5, a2, a4, a6，出栈序列是：a5, a4, a2, a6, a3, a1，则栈的容量最小是多少（）

下面哪些属于算法的基本特征？

下列说法错误的是 ()