第一讲 基本概念(1:15:26)[陈越]

1.2 什么是算法(3节共22:41)随堂测验

1、下列函数中,哪个函数具有最快的增长速度:
    A、
    B、
    C、
    D、

2、下面一段代码的时间复杂度是?if ( A > B ) { for ( i=0; i i; j-- ) A += B; } else { for ( i=0; i i; j-- ) A += B; }
    A、
    B、
    C、
    D、



第二讲 线性结构(2:19:00)[何钦铭]

2.1 线性表及其实现(6小节共45:04)随堂测验

1、对于线性表,在顺序存储结构和链式存储结构中查找第k个元素,其时间复杂性分别是多少?
    A、都是O(1)
    B、都是O(k)
    C、O(1)和O(k)
    D、O(k)和O(1)



2、在顺序结构表示的线性表中,删除第i个元素(数组下标为i-1),需要把后面的所有元素都往前挪一位,相应的语句是: for (___________ ) PtrL->Data[j-1]=PtrL->Data[j]; 其中空缺部分的内容应该是
    A、j = i; j< = PtrL->Last; j++
    B、j =PtrL->Last; j>= i; j--
    C、j = i-1; j< = PtrL->Last; j++
    D、j =PtrL->Last; j>= i-1; j--



3、下列函数试图求链式存储的线性表的表长,是否正确? int Length ( List *PtrL ) { List *p = PtrL; int j = 0; while ( p ) { p++; j++; } return j; }



2.2 堆栈(4小节共39:51)随堂测验

1、借助堆栈将中缀表达式A-(B-C/D)*E转换为后缀表达式,则该堆栈的大小至少为:
    A、2
    B、3
    C、4
    D、5



2、设1、2、…、n–1、n共n个数按顺序入栈,若第一个出栈的元素是n,则第三个出栈的元素是:
    A、3
    B、n-2
    C、n-3
    D、任何元素均可能



3、若用单向链表实现一个堆栈,当前链表状态为:1->2->3。当对该堆栈执行pop()、push(4)操作后,链表状态变成怎样? (1)4->2->3 (2) 1->2->4
    A、只能是(1)
    B、只能是(2)
    C、(1)和(2)都有可能
    D、(1)和(2)都不可能



4、如果一堆栈的输入序列是aAbBc,输出为 abcBA,那么该堆栈所进行的操作序列是什么? 设P代表入栈,O代表出栈。
    A、PPPOOPOPOO
    B、POOPPPOPOO
    C、POPPOPPOOO
    D、PPOPPOOOPO



2.3 队列(2小节共15:45)随堂测验

1、在一个链表表示的队列中, f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中:
    A、f->next=s; f=s;
    B、r->next=s; r=s;
    C、s->next=r; r=s;
    D、s->next=f; f=s;



2、现采用大小为10的数组实现一个循环队列。设在某一时刻,队列为空且此时front和rear值均为5。经过若干操作后,front为8,rear为2,问:此时队列中有多少个元素?
    A、4
    B、5
    C、6
    D、7



第三讲 树(上) (1:50:08)[何钦铭]

3.1 树与树的表示(5小节共38:54)随堂测验

1、在分量1~11的数组中按从小到大顺序存放11个元素,如果用顺序查找和二分查找分别查找这11个元素,哪个位置的元素在这两种方法的查找中总次数最少?
    A、1
    B、2
    C、3
    D、6



2、在分量1~11的数组中按从小到大顺序存放11个元素,如果进行二分查找,查找次数最少的元素位于什么位置?
    A、1
    B、5
    C、6
    D、11



3、一棵度为 m的树有n个节点。若每个节点直接用m个链指向相应的儿子,则表示这个树所需要的总空间是n*(m+1) (假定每个链以及表示节点的数据域都是一个单位空间).。当采用儿子/兄弟(First Child/Next Sibling)表示法时,所需的总空间是:
    A、3n
    B、2n
    C、n*m
    D、n*(m-1)



3.2 二叉树及存储结构(2小节共16:43)随堂测验

1、如果一个完全二叉树最底下一层为第六层(根为第一层)且该层共有8个叶结点,那么该完全二叉树共有多少个结点?
    A、31
    B、39
    C、63
    D、71



2、若有一二叉树的总结点数为98,只有一个儿子的结点数为48,则该树的叶结点数是多少?
    A、25
    B、50
    C、不确定
    D、这样的树不存在



3、设深度为d(只有一个根结点时,d为1)的二叉树只有度为0和2的结点,则此类二叉树的结点数至少为2d-1



3.3 二叉树的遍历(4小节共37:02)随堂测验

1、假定只有四个结点A、B、C、D的二叉树,其前序遍历序列为ABCD,则下面哪个序列是不可能的中序遍历序列?
    A、ABCD
    B、ACDB
    C、DCBA
    D、DABC



2、对于二叉树,如果其中序遍历结果与前序遍历结果一样,那么可以断定该二叉树________
    A、是完全二叉树
    B、所有结点都没有左儿子
    C、所有结点都没有右儿子
    D、这样的树不存在



3、已知一二叉树的后序和中序遍历的结果分别是FDEBGCA 和FDBEACG,那么该二叉树的前序遍历结果是什么?
    A、ABDFECG
    B、ABDEFCG
    C、ABDFEGC
    D、ABCDEFG



第四讲 树(中)(1:06:31)[何钦铭]

4.1 二叉搜索树(3小节共20:57)随堂测验

1、已知一棵由1、2、3、4、5、6、7共7个结点组成的二叉搜索树(查找树),其结构如图所示,问:根结点是什么?
    A、1
    B、4
    C、5
    D、不能确定



2、在上题的搜索树中删除结点1,那么删除后该搜索树的后序遍历结果是:
    A、243765
    B、432765
    C、234567
    D、765432



3、若一搜索树(查找树)是一个有n个结点的完全二叉树,则该树的最大值一定在叶结点上



4、若一搜索树(查找树)是一个有n个结点的完全二叉树,则该树的最小值一定在叶结点上



4.2 平衡二叉树(2小节共22:53)随堂测验

1、将1、2、3、4、5、6顺序插入初始为空的AVL树中,当完成这6个元素的插入后,该AVL树共有多少层?
    A、2
    B、3
    C、4
    D、5



2、若一AVL树的结点数是21,则该树的高度至多是多少?注:只有一个根节点的树高度为0
    A、4
    B、5
    C、6
    D、7



第五讲 树(下)(1:53:28)[何钦铭]

5.1 堆(4小节共30:05)随堂测验

1、下列序列中哪个是最小堆?
    A、2, 55, 52, 72, 28, 98, 71
    B、2, 28, 71, 72, 55, 98, 52
    C、2, 28, 52, 72, 55, 98, 71
    D、28, 2, 71, 72, 55, 98, 52



2、在最大堆 {97,76,65,50,49,13,27}中插入83后,该最大堆为:
    A、{97,76,65,83,49,13,27,50}
    B、{97,83,65,76,49,13,27,50}
    C、{97,83,65,76,50,13,27,49}
    D、{97,83,65,76,49,50,13,27}



3、对由同样的n个整数构成的二叉搜索树(查找树)和最小堆,下面哪个说法是不正确的:
    A、二叉搜索树(查找树)高度大于等于最小堆高度
    B、对该二叉搜索树(查找树)进行中序遍历可得到从小到大的序列
    C、从最小堆根节点到其任何叶结点的路径上的结点值构成从小到大的序列
    D、对该最小堆进行按层序(level order)遍历可得到从小到大的序列



5.2 哈夫曼树与哈夫曼编码(3小节共19:52)随堂测验

1、如果哈夫曼树有67个结点,则可知叶结点总数为:
    A、22
    B、33
    C、34
    D、不确定



2、为五个使用频率不同的字符设计哈夫曼编码,下列方案中哪个不可能是哈夫曼编码?
    A、00,100,101,110,111
    B、000,001,01,10,11
    C、0000,0001,001,01,1
    D、000,001,010,011,1



3、一段文本中包含对象{a,b,c,d,e},其出现次数相应为{3,2,4,2,1},则经过哈夫曼编码后,该文本所占总位数为:
    A、12
    B、27
    C、36
    D、其它都不是



5.3 集合及运算(2小节共12:57)随堂测验

1、已知a、b两个元素均是所在集合的根结点,且分别位于数组分量3和2位置上,其parent值分别为-3,-2。问:将这两个集合按集合大小合并后,a和b的parent值分别是多少?
    A、-5,2
    B、-5,3
    C、-3,3
    D、2,-2



第六讲 图(上)(1:29:32)[陈越]

6.1 什么是图(3小节共24:02)随堂测验

1、有 个顶点的无向完全图有多少条边?
    A、
    B、
    C、
    D、



2、给定有向图的邻接矩阵如下: 顶点2(编号从0开始)的出度和入度分别是:
    A、3, 1
    B、1, 3
    C、0, 2
    D、2, 0



3、有向图的邻接矩阵一定是不对称的



4、用一维数组G[ ]存储有4个顶点的无向图如下: G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 } 则顶点2和顶点0之间是有边的。



6.1 什么是图(3小节共24:02)随堂测验

1、用邻接表表示有 个顶点、 条边的图,则遍历图中所有边的时间复杂度为:
    A、
    B、
    C、
    D、



6.2 图的遍历(4小节共22:22)随堂测验

1、已知一个图如下图所示,从顶点a出发按深度优先搜索法进行遍历,则可能得到的一种顶点序列为
    A、a,e,b,c,f,d
    B、a,b,e,c,d,f
    C、a,c,f,e,b,d
    D、a,e,d,f,c,b



6.2 图的遍历(4小节共22:22)随堂测验

1、已知一个图如下图所示,从顶点a出发按广度优先搜索法进行遍历,则可能得到的一种顶点序列为
    A、a,b,c,e,d,f
    B、a,b,c,e,f,d
    C、a,e,b,c,f,d
    D、a,c,f,d,e,b



6.2 图的遍历(4小节共22:22)随堂测验

1、具有 个顶点的无向图至多有多少个连通分量
    A、0
    B、1
    C、
    D、



2、如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点,则该图一定是
    A、有回路的图
    B、完全图
    C、连通图
    D、一棵树



3、具有 个顶点的无向图至少有多少个连通分量
    A、0
    B、1
    C、
    D、



第八讲 图(下)(57:02)[陈越]

8.1 最小生成树问题(2小节共20:16)随堂测验

1、给定下图,其最小生成树的总权重是
    A、21
    B、30
    C、34
    D、35



2、连通图的最小生成树一定是唯一的



8.2 拓扑排序(2小节共27:57)随堂测验

1、拓扑序一定是唯一的。



8.2 拓扑排序(2小节共27:57)随堂测验

1、下图给定了一个项目的AOE。整个项目最早完工需要的时间是
    A、17
    B、19
    C、20
    D、23



2、在上图中,如果<0,2>组能加快进度,整个项目就能提前完工。



第十一讲 散列查找(1:43:39)[何钦铭]

11.3 冲突处理方法(6小节共36:26)随堂测验

1、设有一组记录的关键字为 {19,14,23,1,68,20,84,27,55,11,10,79},用分离链接法构造散列表,散列函数为H(key)= key mod 13。问:散列地址为1的链中有几个记录?
    A、1
    B、2
    C、3
    D、4



2、设一个散列表的大小是11, 散列函数是H(key)=key mod 11. 若采用平方探测( )冲突解决方法,将4个元素{14,38,61,86}顺序插入散列表中。如果再插入元素49,则该元素将被放在什么位置?
    A、4
    B、6
    C、9
    D、10



3、假设一散列表的大小是11,散列函数是H(key)=key mod 11,用线性探测法解决冲突。先将4个元素{14,38,61,86}按顺序插入初始为空的散列表中。如果再插入元素49,则该元素被插入到表中哪个位置(下标)?
    A、4
    B、5
    C、6
    D、7



11.4 散列表的性能分析(1小节10:26)随堂测验

1、一个大小为11的散列表,散列函数为H(key)=key mod 11,采用线性探测冲突解决策略。如果现有散列表中仅有的5个元素均位于下标为奇数的位置,问:该散列表的平均不成功查找次数是多少?
    A、6/11
    B、1
    C、16/11
    D、不确定



2、在一个大小为K的空散列表中,按照线性探测冲突解决策略连续插入散列值相同的N个元素(N
    A、不确定
    B、K/N
    C、(N+1)/2
    D、1



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



第九讲 排序(上)(1:11:44)[陈越]

9.1 简单排序(冒泡、插入)(4小节共23:26)随堂测验

1、对于7个数进行冒泡排序,最坏情况下需要进行的比较次数为
    A、7
    B、14
    C、21
    D、49



9.1 简单排序(冒泡、插入)(4小节共23:26)随堂测验

1、对一组包含10个元素的非递减有序序列,采用插入排序排成非递增序列,其可能的比较次数和移动次数分别是
    A、45, 44
    B、54, 63
    C、100, 54
    D、100, 100



9.2 希尔排序(1小节共9:29)随堂测验

1、希尔排序是稳定的。



9.3 堆排序(2小节共10:27)随堂测验

1、对N个记录进行堆排序,最坏的情况下时间复杂度是
    A、
    B、
    C、
    D、



2、有一组记录(46,77,55,38,41,85),用堆排序建立的初始堆为
    A、38,77,55,46,41,85
    B、38,41,46,77,55,85
    C、85,55,77,38,41,46
    D、85,77,55,38,41,46



3、堆排序是稳定的。



第十讲 排序(下)(54:20)[陈越]

10.1 快速排序(4小节共25:25)随堂测验

1、快速排序是稳定的算法。



10.2 表排序(2小节共12:41)随堂测验

1、给定A[]={46, 23, 8, 99, 31, 12, 85},调用非递归的归并排序加表排序执行第1趟后,表元素的结果是:
    A、0, 1, 2, 3, 4, 5, 6
    B、1, 0, 3, 2, 6, 5, 4
    C、1, 0, 2, 3, 5, 4, 6
    D、0, 2, 1, 4, 3, 5, 6



2、给定A[]={23, 46, 8, 99, 31, 12, 85},调用表排序后,表元素的结果是:
    A、1, 2, 3, 4, 5, 6, 7
    B、2, 0, 3, 5, 1, 4, 6
    C、3, 6, 1, 5, 2, 7, 4
    D、2, 5, 0, 4, 1, 6, 3



10.3 基数排序(3小节共12:13)随堂测验

1、基数排序是稳定的算法。



10.4 排序算法的比较(1小节共4:01)随堂测验

1、请选择下面四种排序算法中最快又是稳定的排序算法:
    A、希尔排序
    B、堆排序
    C、归并排序
    D、快速排序



2、下列排序算法中,哪种算法可能出现:在最后一趟开始之前,所有的元素都不在其最终的位置上
    A、堆排序
    B、插入排序
    C、冒泡排序
    D、快速排序



3、当待排序列已经基本有序时,下面哪个排序算法效率最差
    A、快速排序
    B、直接插入
    C、选择排序
    D、堆排序



4、数据序列(3,2,4,9,8,11,6,20)只能是下列哪种排序算法的两趟排序结果
    A、冒泡排序
    B、插入排序
    C、选择排序
    D、快速排序