$N^{2}logNN^2\; logN$和$Nlog{N}^{2}N\; logN^2$具有相同的增长速度。

$(NlogN)\mathrm{/}1000(NlogN)/1000$是$O(N)O(N)$的。

斐波那契数列$F_{N}F\_N$的定义为：$F_0=0F\_0=0$, $F_1=1F\_1=1$, $F_N=F_{N-1}+F_{N-2}F\_N=F\_\{N-1\}+F\_\{N-2\}$, $NN$=2, 3, …。用递归函数计算$F_{N}F\_N$的时间复杂度是$O(F_N)O(F\_N)$。

算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

算法可以没有输入，但是必须有输出。

时间复杂度是根据算法写成的程序在执行时耗费时间的长度，往往与输入数据的规模有关。

空间复杂度是根据算法写成的程序在执行时占用存储单元的长度，往往与输入数据的规模有关。

递归程序往往简洁易懂，但占用较大空间。递归层数过大会造成系统堆栈溢出。

选择排序的时间复杂度是O($N^{2}N^2$)。

在长度为$NN$的顺序表中查找最大元素，平均时间复杂度是$O(N)O(N)$。

顺序存储方式只能用于存储线性结构。

在顺序表中取出第i个元素所花费的时间与i成正比。

顺序存储的线性表可以随机存取。

顺序存储结构的主要缺点是不利于插入或删除操作。

顺序表中逻辑上相邻的元素，其物理位置也一定相邻。

顺序存储的线性表可以随机存取。

顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。

链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。

在顺序表中，逻辑上相邻的元素，其物理位置必定相邻。

顺序存储设计时，存储单元的地址一定连续。

若用链表来表示一个线性表，则表中元素的地址一定是连续的。

将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。

取线性表的第i个元素的时间同i的大小有关。

链表的每个结点都恰好有一个指针。

线性表的顺序存储表示优于链式存储表示。

在具有头结点的链式存储结构中，头指针指向链表中的第一个元素结点。

循环链表不是线性表。

带头结点的单循环链表中，任一结点的后继结点的指针域均不空。

在单链表中，逻辑上相邻的元素，其物理位置必定相邻。

对单链表来说，只有从头结点开始才能访问到表中所有结点。

栈是一种对进栈、出栈操作总次数做了限制的线性表。

栈是先进先出的线性表。

栈是一种特殊的线性表，它的插入和删除操作都是在表的同一端进行。 ~@

栈结构不会出现溢出现象。 ~@

序列{1,2,3,4,5}依次入栈，则不可能得到{3,4,1,2,5}的出栈序列。

栈是一种先进先出的线性表。

栈结构不会出现溢出现象。

链栈的插入在栈顶，删除在栈底。

若元素x,y,z依次入栈，出栈可任意，则不可能出现x,y,z的出栈顺序。

堆栈适合解决处理顺序与输入顺序相反的问题。

队列结构的顺序存储会产生假溢出现象。

队列中允许插入的一端叫队头，允许删除的一端叫队尾。

可以通过少用一个存储空间的方法解决循环队列假溢出现象。

循环队列也存在空间溢出的问题。

队列的特性

队列是后进先出的线性表。

队列适合解决处理顺序与输入顺序相反的问题。

队列适合解决处理顺序与输入顺序相同的问题。

不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。

队列中允许插入的一端叫队头，允许删除的一端叫队尾。 ~@

队列结构的顺序存储会产生假溢出现象。 ~@

将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点是兄弟。

完全二叉树中，若一个结点没有左孩子，则它必是树叶。

完全二叉树的存储结构通常采用顺序存储结构。

一棵有9层结点的完全二叉树（层次从1开始计数），至少有255个结点。

一棵有9层结点的完全二叉树（层次从1开始计数），至少有256个结点。

一棵有9层结点的完全二叉树（层次从1开始计数），至少有512个结点。

完全二叉树一定存在度为1的结点。

完全二叉树中，若一个结点没有左孩子，则它必是树叶。

完全二叉树存储在数组A中，A[1..10]的元素值为{1,11,21,31,41,51,61,71,81,91}，则元素51的双亲是21。

从形态上看，AVL树是完全二叉树。

若一个有向图无环，则它一定有唯一的拓扑序列。

连通分量是无向图中的极小连通子图。

关于图的遍历

图的广度优先遍历相当于二叉树的先序遍历。

邻接矩阵作为有向图的存储结构，则某顶点的度就是该顶点所在列的非零元素的个数。

有50个顶点的无向图，其最小生成树有51条边。

图是表示一对一关系的数据结构。

图是表示多对多关系的数据结构。

若无向图G有n个顶点(n > 1)和n-1条边但不是树，则G必定不是连通图。

若无向图G有n个顶点(n > 1)和n-1条边但不是树，则G必定有环。

图的广度优先遍历需要借助的数据结构是堆栈

在散列中，函数“插入”和“查找”具有同样的时间复杂度。

哈希函数的选取平方取中法最好。

哈希表的结点中只包含数据元素自身的信息，不包含任何指针。

在散列表中，所谓同义词就是具有相同散列地址的两个元素。

即使把2个元素散列到有100个单元的表中，仍然有可能发生冲突。

采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。

在散列检索中，“比较”操作一般也是不可避免的。

若散列表的负载因子α<1，则可避免碰撞的产生。

当采用线性探测冲突解决策略时，非空且有空闲空间的散列表中无论有多少元素，不成功情况下的期望查找次数总是大于成功情况下的期望查找次数。

将 10 个元素散列到 100 000 个单元的哈希表中，一定不会产生冲突。

如果一个问题可以用动态规划算法解决，则总是可以在多项式时间内解决的。

只有当局部最优跟全局最优解一致的时候，贪心法才能给出正确的解。

任何一个递归过程都可以转换成非递归过程。

在活动选择问题（Activity Selection Problem）中，令 S 为活动的集合。以“每次收集最迟开始的活动”为贪心原则，可以正确找到 S 中相互兼容活动的最大规模的子集合。

用贪心法求解部分背包问题，不能肯定得到最优解，有时可以得到近似最优解。

递归实现可以看成是一个先自上而下，后自下而上的过程； 而迭代实现可以看成是一个纯粹自下而上的过程。

长度为$nn$的序列有$n^{2}n^2$个子序列。（依次任意取舍元素所构成的序列称为子序列）

对n皇后问题，若n为偶数，那么可行解的个数也是偶数。

为提高求解效率，使用回溯法时可同时用约束函数和上界函数来剪去一部分子树。

0-1背包问题的解空间树是一颗排列树。

希尔排序是稳定的算法。

插入排序算法在每一趟都能选取出一个元素放在其最终的位置上。

直接插入排序是不稳定的排序方法。

对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。

由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。

起泡排序的排序趟数与参加排序的序列原始状态有关。

对于n个记录的集合进行冒泡排序，在最坏情况下需要的时间是$O(n^2)O(n^\{2\})$。

直接选择排序的时间复杂度为$O(n^2)O(n^\{2\})$，不受数据初始排列的影响。

内排序的快速排序方法，在任何情况下均可得到最快的排序效果。

当所需排列数据基本有序时，使用快速排序能更快完成排序。

下面的程序段违反了算法的（）原则。

执行下面程序段时，执行S语句的频度为（）。

下列程序的时间复杂度为（）。

求整数n(n>=0)的阶乘的算法如下，其时间复杂度为（ ）。

设 $nn$ 是描述问题规模的非负整数，下列程序段的时间复杂度是：

下面算法所执行的加法次数（ ）。

输入：$nn$，其中$n=2^{t}n\; =\; 2^t$，$tt$为正整数

输出：$kk$

算法P1和P2时间复杂度的递推方程分别为：

P1：T($nn$) = T($nn$/2) + 1, T(1)=1

P2：T($nn$) = 2T($nn$/2) + 1, T(1)=1

则下列关于P1和P2两个算法时间复杂度的结论中正确的是（ ）。

T(n)表示当输入规模为n时的算法效率，以下算法中效率最优的是( )。

下面算法的空间复杂度为 ▁▁▁▁▁。

下列对顺序存储的有序表（长度为 $nn$）实现给定操作的算法中，平均时间复杂度为 $O(1)O(1)$ 的是：

在包含 $nn$ 个数据元素的顺序表中，▁▁▁▁▁ 的时间复杂度为 $O(1)O(1)$。

线性表L=（a1, a2 ,……，a100 ）用一维数组存储。在元素a50之后插入一个新的元素，需要移动元素的个数是（ ）。

在VC环境下，下面数组定义正确的是（ ）。

这是一个单选题的样例,分值为1分。
1、从一个长度为n的顺序表中删除第i个元素（1≦i≦n）时，需向前移动（ ）个元素。

线性表有元素50个，存储在数组A【1..100】中，在第25个元素之后插入一个元素，需要移动元素（    ）个。

在N个元素的顺序表中，算法的时间复杂度为O(1)的是（        ）。

1.顺序查找长度为n的线性表的平均查找长度为（C）。

关于表结构说法正确的是（）。

顺序查找长度为n的线性表的平均成功的查找长度为_____。

在长度为n的顺序表任意位置插入元素，平均需要移动（      ）个元素

已知指针ha和hb分别是两个单链表的头指针，下列算法将这两个链表首尾相连在一起，并形成一个循环链表（即ha的最后一个结点链接hb的第一个结点，hb的最后一个结点指向ha），返回ha作为该循环链表的头指针。请将该算法补充完整。

在单链表中，将 s 所指新结点插入到 p 所指结点之后，其语句应该为 ▁▁▁▁▁ 。

在双链表中，将 s 所指新结点插入到 p 所指结点之后，其语句应该为 ▁▁▁▁▁ 。

已知头指针 h 指向一个带头结点的非空单循环链表，结点结构为 data | next，其中 next 是指向直接后继结点的指针，p 是尾指针，q 是临时指针。现要删除该链表的第一个元素，正确的语句序列是：

线性表在 ▁▁▁▁▁ 情况下适合采用链式存储结构。

假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是（ ）

在包含 $nn$ 个数据元素的单链表中，▁▁▁▁▁ 的时间复杂度不为 $O(n)O(n)$。

若某线性表最常用的操作是在表头进行插入和删除，则利用哪种存储方式最合适？

现有非空双向链表 $LL$，其结点结构为：
，prev 是指向直接前驱结点的指针，next 是指向直接后继结点的指针。若要在 $LL$ 中指针 p 所指向的结点（非尾结点）之后插入指针 s 指向的新结点，则在执行了语句序列 s->next = p->next; p->next = s; 后，下列语句序列中还需要执行的是：

已知带头结点的非空单链表 L 的头指针为 h，结点结构为 data | next，其中 next 是指向直接后继结点的指针。现有指针 p 和 q，若 p 指向 L 中非首且非尾的任意一个结点，则执行语句序列 q = p->next; p->next = q->next; q->next = h->next; h->next = q; 的结果是

在作进栈运算时，应先判别栈是否(① )；在作退栈运算时应先判别栈是否(② )。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为(③ )。

①: A. 空 B. 满 C. 上溢 D. 下溢
②: A. 空 B. 满 C. 上溢 D. 下溢
③: A. n-1 B. n C. n+1 D. n/2

若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶元素所在的下标，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。

在作进栈运算时，应先判别栈是否(① )；在作退栈运算时应先判别栈是否(② )。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为(③ )。

①: A. 空 B. 满 C. 上溢 D. 下溢

②: A. 空 B. 满 C. 上溢 D. 下溢

③: A. n-1 B. n C. n+1 D. n/2

若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶（该位置不存储对应栈数据），栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。

设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是( )。

元素A,B,C,D依次入栈，出栈无限制，则以下（ ）是可能的出栈序列。

用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为( )。

给定有限符号集 S , in 和 out 均为 S 中所有元素的任意排列。 对于初始为空的栈 ST, 下列叙述中，正确的是：

检查表达式中的括号是否匹配的问题需要借助________来解决。

设栈S和队列Q的初始状态为空，元素1、2、3、4、5和6依次通过S，每个元素出栈后即进入Q，若6个元素出队的序列是2、6、5、4、3和1，则栈S的容量至少应该是（ ）

为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？

若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是：

在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是( )。

最不适合用作链队的链表是（）。

现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：

栈和队列的共同点是（ ）。

已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1、2、3、4、5，则不能得到的出队序列是：

若用大小为6的数组来实现循环队列，且当前front和rear的值分别为1和4。当从队列中删除两个元素，再加入三个元素后，front和rear的值分别为（ ）。

队列的插入在 ▁▁▁▁▁ 进行，删除在 ▁▁▁▁▁ 进行。

完全二叉树顺序存储，结点X的编号为42，则其右孩子结点的编号是( )

完全二叉树顺序存储，结点X的编号为37，则其右孩子结点的编号是( )

完全二叉树顺序存储，结点X的编号为47，则其右孩子结点的编号是( )

完全二叉树顺序存储，结点X的编号为35，则其右孩子结点的编号是( )

完全二叉树顺序存储，结点X的编号为39，则其右孩子结点的编号是( )

完全二叉树顺序存储，结点X的编号为46，则其右孩子结点的编号是( )

完全二叉树顺序存储，结点X的编号为44，则其右孩子结点的编号是( )

完全二叉树顺序存储，结点X的编号为33，则其右孩子结点的编号是( )

深度为k的完全二叉树的第k层至少有（ ）个结点。

完全二叉树存储在数组A【1..10】中，其元素值为{10,20,30,40,50,60,70,80,90,100},则元素50的双亲是（     ）。

有18个叶子的哈夫曼树的结点总数为 ( ).

有17个叶子的哈夫曼树的结点总数为 ( ).

有14个叶子的哈夫曼树的结点总数为 ( ).

有21个叶子的哈夫曼树的结点总数为 ( ).

有24个叶子的哈夫曼树的结点总数为 ( ).

若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（WPL）是：

在由 6 个字符组成的字符集 $SS$ 中，各字符出现的频次分别为 3，4，5，6，8，10，为 $SS$ 构造的哈夫曼编码的加权平均长度为：

一颗哈夫曼树共有101个元素，则度为2的结点有（      ）个。

由元素{3  5  4  2  7}为叶子结点构成的哈夫曼树的带权路径长度WPL为（     ）。

字母ABCDE的不等长编码不可能是_____。

图的广度优先遍历需要借助的数据结构是

有向图采用邻接矩阵存储，则每列的非零元素个数表示的是

有向图的邻接链表如下，则顶点C的入度为