第一讲 基本概念(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; ii; 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
猜你喜欢
- 2022-12-05 21:30
- 2022-12-05 21:00
- 2022-12-05 20:18
- 2022-12-05 20:18
- 2022-12-05 20:17
- 2022-12-05 20:16
- 2022-12-05 20:14
- 2022-12-05 20:14
- 2022-12-05 19:29
- 2022-12-05 19:09