【答案】《算法设计与问题求解》(西安交通大学)章节期末中国大学慕课答案

1.绪论本章练习1.单选题：下面语句片段的时间复杂度为x=1;for(i=1;i＜=n;i++)for(j=1;j＜=i;j++)for(k=1;k＜=j;k++)x++;

选项：

A、O(n^2)

B、O(n^3)

C、O(n)

D、O(logn)

答案：【O(n^3)】2.单选题：下面那个标识符是纯C语言的标示符

选项：

A、cin

B、cout

C、string

D、scanf

答案：【scanf】3.单选题：重载函数之间，下面描述错误的是：

选项：

A、不同函数的参数类型可以不同

B、不同函数的参数个数可以不同

C、函数名必然相同

D、函数返回值类型必然相同

答案：【函数返回值类型必然相同】4.单选题：c++语言的string类对象可以自动调节空间

选项：

A、正确

B、错误

答案：【正确】5.单选题：C++语言完全兼容C语言

选项：

A、正确

B、错误

答案：【正确】6.单选题：C语言也有函数重载的能力

选项：

A、正确

B、错误

答案：【错误】2.若干数学问题的编程单元测验1.单选题：同一个问题，牛顿插值公式和拉格朗日插值公式等价

选项：

A、正确

B、错误

答案：【正确】2.单选题：判断数字N是否是质数，必判断所有2~N-1的数字有没有N的因子

选项：

A、正确

B、错误

答案：【错误】3.n阶差分可以由阶差分作减法得到

答案：【n-1】4.voidinput(y[],intm){inti;for(i=0;iscanf("%f",&y[i]);}

答案：【float】5.以下程序利用筛选法得到质数表voidPrimeTable(intM){inti,j;for(i=2;i＜=M;i++)isprime[i]=1;for(i=2;i＜M;i++){if(isprime[i])for(j=i+i;j＜=M;j+=)isprime[j]=0;}}

答案：【i】6.将多项式对应的系数存储在数组的下标为0,1,…,n的位置中，这样数组的数据就是系数，而下标的值就是指数。数组A[]，B[]存储两个多项式，两者相乘的结果放在数组C[]，则A[i]*B[j]是结果数组中的一部分

答案：【C[i+j]/C[j+i]】7.下面程序计算上述表达式在xx处的值Lk=1;for(j=0;j＜=n;j++)if()Lk*=(xx-x[j])/(x[i]-x[j]);

答案：【j!=k】3.若干数学问题的编程-续单元测验1.单选题：已知N阶方阵A,则高斯消去法时间复杂度为()

选项：

A、N*N

B、N

C、logN

D、N*N*N

答案：【N*N*N】2.单选题：二分法求解一元方程的根,要求方程是()

选项：

A、连续

B、一阶导数连续

C、二阶导数连续

D、不连续

答案：【连续】3.单选题：Newton法求解一元方程的根,要求方程是()

选项：

A、连续

B、一阶导数连续

C、二阶导数连续

D、不连续

答案：【二阶导数连续】4.单选题：AX=b有唯一解,A是m行n列矩阵,则必有m>=n

选项：

A、正确

B、错误

答案：【正确】5.单选题：只要只要AX=b有解,Jacobi迭代法就一定可以求出答案

选项：

A、正确

B、错误

答案：【错误】6.单选题：如果用Jacobi迭代法求AX=b的解,要求A阵对焦元素均不为零

选项：

A、正确

B、错误

答案：【正确】7.单选题：对于同一个问题二分法的求解速度比Newton法快

选项：

A、正确

B、错误

答案：【错误】8.单选题：用一种迭代法可以求解方程的根,则任何迭代格式都收敛

选项：

A、正确

B、错误

答案：【错误】9.单选题：只要AX=b有解,列主元高斯消去就一定可以求出答案

选项：

A、正确

B、错误

答案：【正确】4线性数据结构（1）单元测验1.单选题：从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较________个结点

选项：

A、n

B、n/2

C、(n-1)/2

D、(n+1)/2

答案：【(n+1)/2】2.单选题：给定有n个元素的向量，建立一个有序单链表的时间复杂度是()

选项：

A、O(1)

B、O(n)

C、O(n^2)

D、O(n*log2n)

答案：【O(n^2)】3.单选题：在单链表{a1,a2,a3,a4,……}中，p为指向a2的指针，则指向a4的指针可以写作

选项：

A、p->next->next

B、p.next

C、p->next

D、(&p)->next

答案：【p->next->next】4.单选题：下面关于线性表的叙述错误的是（）。

选项：

A、线性表采用顺序存储必须占用一片连续的存储空间

B、线性表采用链式存储必须占用一片连续的存储空间

C、线性表采用链式存储便于插入和删除操作的实现

D、线性表采用顺序存储不适合插入和删除操作的实现

答案：【线性表采用链式存储必须占用一片连续的存储空间】5.单选题：关于单链表，下面描述错误的是（）

选项：

A、转化为单循环链表时整个空间大小不变

B、头指针一般不会改动

C、头结点中数据为空

D、删除最后一个结点时所有元素指针不变

答案：【删除最后一个结点时所有元素指针不变】6.单选题：不带头结点的单链表head为空的判定条件是

选项：

A、head==NUL

B、head->next==NULL

C、head->next==head

D、head!=NULL

答案：【head==NUL】7.单选题：在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行

选项：

A、s->next=p->next;p->next=s;

B、q->next=s;s->next=p;

C、p->next=s;s->next=q;

D、p->next=s->next;s->next=p;

答案：【q->next=s;s->next=p;】8.单选题：在一个单链表中，若删除p所指结点的后续结点，则执行

选项：

A、p->next=p->next->next;

B、p=p->next;p->next=p->next->next;

C、p->next=p->next;

D、p=p->next->next;

答案：【p->next=p->next->next;】9.单选题：在一个单链表中，若删除p所指向结点的后续结点，则执行（）

选项：

A、p->next=p->next->next

B、p=p->next

C、p=p->next;p->next=p->next->next

D、p=p->next->next

答案：【p->next=p->next->next】10.单选题：关于循环队列，下面描述错误的是（）

选项：

A、元素存放在顺序形式的结构中

B、有头指针和尾指针

C、删除一个元素，其他元素要移动

D、所谓循环是利用数学方法实现的

答案：【删除一个元素，其他元素要移动】11.单选题：线性表的逻辑顺序与存储顺序总是一致的。

选项：

A、正确

B、错误

答案：【错误】12.单选题：数据逻辑结构包括线性结构、树形结构、图形结构三种类型。

选项：

A、正确

B、错误

答案：【正确】13.单选题：在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

选项：

A、正确

B、错误

答案：【正确】5线性数据结构（2）单元测验1.单选题：判定一个循环队列Q（最多元素为m0）为空的条件是____

选项：

A、rear-front==m0

B、rear-front-1==m0

C、front==rear

D、front==rear+1

答案：【front==rear】2.单选题：判定一个循环队列Q（最多元素为m0,m0==Maxsize-1）为满队列的条件是_______

选项：

A、(rear+1)%Maxsize==front

B、rear-front-1==m0

C、front==rear

D、front==rear+1

答案：【(rear+1)%Maxsize==front】3.单选题：判定一个顺序栈（存储空间长度Maxsize）为空的条件是______

选项：

A、top!=-1

B、top==-1

C、top!=Maxsize

D、top==Maxsize-1

答案：【top==-1】4.单选题：判定一个顺序栈（存储空间长度Maxsize）为栈满的条件是______

选项：

A、top!=-1

B、top==-1

C、top!=Maxsize

D、top==Maxsize-1

答案：【top==Maxsize-1】5.单选题：一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是。

选项：

A、edcba

B、decba

C、dceab

D、abcde

答案：【dceab】6.单选题：一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____

选项：

A、4，3，2，1

B、1，2，3，4

C、1，4，3，2

D、3，2，4，1

答案：【1，2，3，4】7.单选题：栈和队列的共同点是____

选项：

A、都是先进后出

B、都是先进先出

C、只允许在端点处插入和删除元素

D、没有共同点

答案：【只允许在端点处插入和删除元素】8.单选题：在单链表中增加一个元素时，需要大量移动元素（）

选项：

A、正确

B、错误

答案：【错误】9.单选题：堆栈是特殊形式的线性表（）

选项：

A、正确

B、错误

答案：【正确】10.单选题：线性表可采用顺序存储形式或链式存储形式（）

选项：

A、正确

B、错误

答案：【正确】6树与二叉树单元测验1.单选题：深度为5的二叉树至多有_____个结点

选项：

A、16

B、32

C、31

D、10

答案：【31】2.单选题：某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是______。

选项：

A、bdgcefha

B、gdbecfha

C、bdgaechf

D、gdbehfca

答案：【gdbehfca】3.单选题：如图所示的4棵二叉树，____不是完全二叉树

选项：

A、a

B、b

C、c

D、d

答案：【c】4.单选题：关于哈夫曼树，下面描述错误的是（）

选项：

A、哈夫曼树是二叉树

B、生成该树是一种贪心策略

C、生成的哈夫曼树必定唯一

D、产生的哈夫曼编码有多种

答案：【生成的哈夫曼树必定唯一】5.单选题：对于满二叉树，任何一个结点的孩子结点的个数不可能是()

选项：

A、0

B、1

C、2

D、以上都不对

答案：【1】6.单选题：对下面二叉树进行中序遍历，其序列是（）

选项：

A、ABDEGJKCFHLI

B、DBJGKEACHLFI

C、ABCDEFGHIJKL

D、DJKGEBLHIFCA

答案：【DBJGKEACHLFI】7.单选题：设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）

选项：

A、8

B、9

C、10

D、11

答案：【11】8.单选题：二叉树后序遍历，最后一个访问的是（）

选项：

A、最深一层的结点

B、根

C、最右下方结点

D、最左下方结点

答案：【根】9.单选题：设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的右孩子结点的编号为（）。

选项：

A、2i+1

B、i

C、i/2

D、2i-1

答案：【2i+1】10.单选题：存储二叉树一般使用链式存储结构，此时二叉树的每个结点需要（）个指针域

选项：

A、1

B、2

C、3

D、4

答案：【2】11.单选题：在树形结构中，树根结点没有前驱结点

选项：

A、正确

B、错误

答案：【正确】12.单选题：在树形结构中，每个结点有且只有2个直接前驱结点

选项：

A、正确

B、错误

答案：【错误】13.单选题：在树形结构中，叶子结点没有后继结点。

选项：

A、正确

B、错误

答案：【正确】考试算法设计与问题求解考试1.单选题：任何一个无向连通图的最小生成树（）

选项：

A、只有一棵

B、有一棵或多棵

C、一定有多棵

D、可能不存在

答案：【有一棵或多棵】2.单选题：在下面有权图中找出最小生成树，其权值之和为（）

选项：

A、19

B、18

C、16

D、17

答案：【17】3.单选题：已知图结构如下，从顶点B出发按广度优先搜索进行遍历，可能得到的遍历序列为（）

选项：

A、B,C,D,A,E,F

B、B,D,C,F,E,A

C、B,C,A,E,D,F

D、B,D,C,A,F,E

答案：【B,D,C,F,E,A】4.单选题：对下面二叉树进行中序遍历，其序列是（）

选项：

A、ABDEGJKCFHLI

B、DBJGKEACHLFI

C、ABCDEFGHIJKL

D、DJKGEBLHIFCA

答案：【DBJGKEACHLFI】5.单选题：关于循环队列，下面描述错误的是（）

选项：

A、元素存放在顺序形式的结构中

B、有头指针和尾指针

C、删除一个元素，其他元素要移动

D、所谓循环是利用数学方法实现的

答案：【删除一个元素，其他元素要移动】6.单选题：关于哈夫曼树，下面描述错误的是（）

选项：

A、哈夫曼树是二叉树

B、生成该树是一种贪心策略

C、生成的哈夫曼树必定唯一

D、产生的哈夫曼编码有多种

答案：【生成的哈夫曼树必定唯一】7.单选题：关于最小生成树，下面描述错误的是（）

选项：

A、是和图有关的概念

B、边数加顶点数是奇数

C、又称为哈夫曼树

D、最小生成树可能不唯一

答案：【又称为哈夫曼树】8.单选题：下面关于线性表的叙述错误的是（）

选项：

A、线性表采用顺序存储必须占用一片连续的存储空间

B、线性表采用链式存储必须占用一片连续的存储空间

C、线性表采用链式存储便于插入和删除操作的实现

D、线性表采用顺序存储不适合插入和删除操作的实现

答案：【线性表采用链式存储必须占用一片连续的存储空间】9.单选题：存储二叉树一般使用链式存储结构，此时二叉树的每个结点需要（）个指针域

选项：

A、1

B、2

C、3

D、4

答案：【2】10.单选题：设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的右孩子结点的编号为（）

选项：

A、2i+1

B、i

C、i/2

D、2i-1

答案：【2i+1】11.单选题：遗传算法中适应度的高低反映了个体在下一代被选中的概率高低

选项：

A、正确

B、错误

答案：【正确】12.单选题：贪心算法有时无法找到最优解

选项：

A、正确

B、错误

答案：【正确】13.单选题：马踏棋盘问题可以完全使用递归搜索（去掉贪心策略）实现

选项：

A、正确

B、错误

答案：【正确】14.单选题：马踏棋盘问题的贪心策略是：在选择下一跳的位置时,总是先选择出口少的那个位置

选项：

A、正确

B、错误

答案：【正确】15.单选题：遗传算法中的变异可以表现为一个二进制数某个位的取反

选项：

A、正确

B、错误

答案：【正确】16.单选题：遗传算法中的交叉可以表现为两个二进制数某些位的交换

选项：

A、正确

B、错误

答案：【正确】17.单选题：动态规划法能够找到问题的最优解

选项：

A、正确

B、错误

答案：【正确】18.单选题：堆栈是特殊形式的线性表

选项：

A、正确

B、错误

答案：【正确】19.单选题：图的邻接表中有一部分是链式存储形式

选项：

A、正确

B、错误

答案：【正确】20.单选题：下面函数比较整数x和y的大小，返回两者中较大的数，该函数正确吗（）intfunc(intx,inty){if(xelse