大学MOOC 数据结构与算法(浙江海洋大学)1452094235 最新慕课完整章节测试答案

单元测验1

1、单选题：
‏n个整数，采用选择排序算法进行排序的时间复杂度是：‏
选项：
A: O()
B: O()
C: O()
D: O(n)
答案: 【 O()】

2、单选题：
‍以下程序的时间复杂度为：‎‍void prime(int n)
{    int i=2;
     while((n%i)!=0&&i*0.1<=sqrt(n))
         i++;
     if(i*1.0>sqrt(n))
         printf("%d is a prime.n",n);
     else
         printf("%d is not a prime.n",n);
}‎
选项：
A: O(n)
B: O()
C: O(n/2)
D: O()
答案: 【 O()】

3、判断题：

‍和具有相同的增长速度

‏选项：
A: 正确
B: 错误
答案: 【 错误】

4、填空题：
‌衡量、比较算法优劣的主要指标有：空间复杂度和‏
答案: 【 时间复杂度】

单元测验2

1、单选题：
‏对于线性表，在顺序存储结构和链式存储结构中查找第k个元素，其时间复杂性分别是多少？‌
选项：
A: 都是O(1)
B: 都是O(k)
C: O(1)和O(k)
D: O(k)和O(1)
答案: 【 O(1)和O(k)】

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--
答案: 【 j=Ptrl->Last; j>=i; j--】

3、单选题：
‌设1、2、…、n–1、n共n个数按顺序入栈，若第一个出栈的元素是n，则第三个出栈的元素是：​
选项：
A: 3
B: n-2
C: n-3
D: 任何元素均可能
答案: 【 n-2】

4、单选题：
‎若用单向链表实现一个堆栈，当前链表状态为：1->2->3。当对该堆栈执行pop()、push(4)操作后，链表状态变成怎样？‎‎                 （1）4->2->3    (2)  1->2->4‎
选项：
A: 只能是（1）
B: 只能是（2）
C: （1）和（2）都可能
D: （1）和（2）都不可能
答案: 【 只能是（1）】

5、单选题：
​如果一堆栈的输入序列是aAbBc，输出为 abcBA，那么该堆栈所进行的操作序列是什么？ 设P代表入栈，O代表出栈。‌
选项：
A: PPPOOPOPOO
B: POOPPPOPOO
C: POPPOPPOOO
D: PPOPPOOOPO
答案: 【 POPPOPPOOO】

6、单选题：
‌现采用大小为10的数组实现一个循环队列。设在某一时刻，队列为空且此时front和rear值均为5。经过若干操作后，front为8，rear为2，问：此时队列中有多少个元素？‏
选项：
A: 4
B: 5
C: 6
D: 7
答案: 【 4】

7、单选题：
‍在一个链表表示的队列中， 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;
答案: 【 r->next=s; r=s;】

8、单选题：
‌借助堆栈将中缀表达式A-(B-C/D)*E转换为后缀表达式，则该堆栈的大小至少为：‏
选项：
A: 2
B: 3
C: 4
D: 5
答案: 【 4】

9、判断题：
‏下列函数试图求链式存储的线性表的表长，是否正确？‎‏int  Length ( List  *PtrL )
{    List  *p = PtrL;
     int  j = 0;
     while ( p ) 
     {     p++;
           j++;
     }
     return  j;
}‎
选项：
A: 正确
B: 错误
答案: 【 错误】

单元测验3

1、单选题：
​在顺序查找中,如果把下列程序中的循环条件"i>0"去掉，会发生什么后果？‌int SequentialSearch(List Tbl,ElementType K)‌{                 /*在表Element[1]~Element[n]中查找关键字为K的数据元素*/‌   int i;‌   for(i = Tbl->Length; i>0 && Tbl->Element[i] != K;  i--);‌   return i;   /*查找成功返回所在单元下标；不成功返回0*/‌}‌
选项：
A: 没有影响，结果一样。
B: 要查找的元素存在时，找不到
C: 要查找的元素不存在时，发生数组越界（i指向小于0的位置）
D: 要查找的元素不存在时，函数返回0
答案: 【 要查找的元素不存在时，发生数组越界（i指向小于0的位置）】

2、单选题：
​有一个m棵树的集合（也叫森林）共有k条边，问这m颗树共有多少个结点？‏
选项：
A: k+m-1
B: k+m
C: k+m+1
D: 不确定，要看具体树结构
答案: 【 k+m】

3、单选题：
‍在用“儿子-兄弟”法表示的树中，如果从根结点开始访问其“次子”的“次子”，所经过的结点数与下面哪种情况一样？(注意:比较的是结点数,而不是路径)‏
选项：
A: 从根结点开始，访问其“长子”的“长子”
B: 从根结点开始，访问其“长子”的“兄弟”的“兄弟”
C: 从根结点开始，访问其“长子”的“兄弟”的“长子”的“兄弟”
D: 不能确定，要看整体树结构
答案: 【 从根结点开始，访问其“长子”的“兄弟”的“长子”的“兄弟”】

4、单选题：
‍在分量1~11的数组中按从小到大顺序存放11个元素，如果用顺序查找和二分查找分别查找这11个元素，哪个位置的元素在这两种方法的查找中总次数最少？‍
选项：
A: 1
B: 2
C: 3
D: 6
答案: 【 1】

5、单选题：
‌在分量1~11的数组中按从小到大顺序存放11个元素，如果进行二分查找，查找次数最少的元素位于什么位置？‌
选项：
A: 1
B: 5
C: 6
D: 11
答案: 【 6】

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

7、单选题：
‌有一颗二叉树，其两个儿子的结点个数为15个，一个儿子的结点个数为32个，问该二叉树的叶结点个数是多少？‎
选项：
A: 15
B: 16
C: 17
D: 32
答案: 【 16】

8、单选题：
‍如果一个完全二叉树最底下一层为第六层（根为第一层）且该层共有8个叶结点，那么该完全二叉树共有多少个结点‏
选项：
A: 31
B: 39
C: 63
D: 71
答案: 【 39】

9、单选题：
‌设深度为d（只有一个根结点时，d为1）的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为2d-1‏
选项：
A: 对
B: 错
C: 有的时候对，有的时候错
D: 不知道
答案: 【 对】

10、单选题：
‍若有一二叉树的总结点数为98，只有一个儿子的结点数为48，则该树的叶结点数是多少？‏
选项：
A: 25
B: 50
C: 不确定
D: 这样的树不存在
答案: 【 这样的树不存在】

11、单选题：

‏非递归方法中序遍历下面这颗二叉树，其堆栈操作序列（P代表为push,O代表为pop)是什么？

​

‏

​选项：
A: PPOOPOPPOO
B: PPPPPOOOOO
C: PPPOOOPPOO
D: PPOPOOPPOO
答案: 【 PPOPOOPPOO】

12、单选题：
‎已知有颗5个结点的二叉树，其前序遍历序列是a????，中序遍历序列是a????，可以断定：​
选项：
A: 该树根结点是a，且没有左子树
B: 该树根结点是a，且没有右子树
C: 该树最左边的结点是a