算法与数据结构智慧树知到课后章节答案2023年下兰州理工大学

算法与数据结构智慧树知到课后章节答案2023年下兰州理工大学兰州理工大学

第一章测试

只要算法是正确的，就一定会得到问题的解。（

）

A:对B:错

答案:错

算法既独立于数据的存储，又与数据的存储有一定的联系。（

）

A:对B:错

答案:对

算法是独立于计算机程序设计语言的。（

）

A:错B:对

答案:对

按照数据结构的逻辑关系进行分类，数据结构可以分为（

）。

A:线性结构B:非线性结构C:链式结构D:存储结构

答案:线性结构;非线性结构

将一个幻方的求解问题交由计算机来进行，就要关注哪两个方面（

）。

A:选择合适的数据结构及设计求解算法B:设计求解算法C:设计数据结构D:使用程序语言编程

答案:选择合适的数据结构及设计求解算法

一个算法可以使用什么样的方式进行描述（

）

A:流程图B:类语言C:自然语言D:计算机高级语言

答案:流程图;类语言;自然语言;计算机高级语言

第二章测试

下面关于线性表的叙述中，错误的是哪一个（

）

A:线性表采用顺序存储，必须占用一片连续的存储单元。B:线性表采用链接存储，不必占用一片连续的存储单元。C:线性表采用链接存储，便于插入和删除操作。D:线性表采用顺序存储，便于进行插入和删除操作。

答案:线性表采用顺序存储，便于进行插入和删除操作。

设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（

）。

A:O(n)B:O(1)C:O(n2)D:O(log2n)

答案:O(n)

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

）

A:对B:错

答案:错

单循环链表H的尾结点p的特点是（

）。

A:p->next==

H->next

B:p==H

->next

C:p==H

D:p->next==H

答案:p->next==H

在顺序表中插入和删除一个结点需平均移动多少个结点?

A:(n-1)/2

B:(n+1)/2C:(2n-1)/2D:n/2

答案:n/2

第三章测试

栈可以应用在哪里（

）。

A:A，Ｂ，ＣB:子程序调用

C:表达式求值

D:递归调用

答案:A，Ｂ，Ｃ

设计一个判别表达式中左，右括号是否配对出现的算法，采用哪种数据结构最佳（

）。

A:线性表的链式存储结构

B:栈C:队列

D:线性表的顺序存储结构

答案:栈

循环队列存储在数组A[0..m]中，则入队时的操作为（

）。

A:rear=(rear+1)

%

(m-1)B:rear=rear+1

C:rear=(rear+1)%(m+1)D:rear=(rear+1)

%

m

答案:rear=(rear+1)%(m+1)

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

）

A:错B:对

答案:对

通常使用队列来处理函数或过程的调用。（

）

A:对B:错

答案:错

设用链表作为栈的存储结构则退栈操作（

）。

A:必须判别栈是否为满B:对栈不作任何判别C:必须判别栈是否为空D:判别栈元素的类型

答案:必须判别栈是否为空

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

）

A:错B:对

答案:对

第四章测试

设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8

，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（

）。

A:BA+141

B:BA+225C:BA+222

D:BA+180

答案:BA+180

将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A66

65（即该元素下标i=66，j=65），在B数组中的位置K为（

）。

A:195

B:196C:198

D:197

答案:195

若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的关系为(

)。

A:j*(j-1)/2+i

B:i*(i-1)/2+j

C:i*(i+1)/2+j

D:j*(j+1)/2+i

答案:j*(j-1)/2+i

设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(

)。

A:i(i-l)/2+j

B:i(i-l)/2+j-1C:j(j-l)/2+i-1

D:j(j-l)/2+i

答案:j(j-l)/2+i

从逻辑结构上看，n维数组的每个元素均属于n个向量。（

）

A:错B:对

答案:对

设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（

）。

A:O(n)B:O(1)C:O(nlog2n)D:O(n2)

答案:O(1)

稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（

）

A:错B:对

答案:对

数组A[0..4,-1..-3,5..7]中含有元素的个数（

）。

A:55

B:45C:16D:36

答案:45

设二维数组A[1..

m，1..

n]（即m行n列）按行存储在数组B[1..

m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为(

)。

A:（i-1）*n+j

B:i*（j-1）

C:（i-1）*n+j-1

D:j*m+i-1

答案:（i-1）*n+j

数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是(

)。

A:1205

B:1180

C:1175

D:1210

答案:1175

第五章测试

设树T的度为4，其中度为1、2、3和4的结点个数分别为4,2,1,1，则T中的叶子结点数为

（

）

A:8B:5

C:7

D:6

答案:8

按二叉树的定义，具有3个结点的二叉树有几种（

）

A:5B:3C:6D:4

答案:5

一棵完全二叉树上有1001个结点，其中叶子结点的个数是（

）。

A:500

B:505

C:都不对D:250

E:254

答案:都不对

一个具有1025个结点的二叉树的高h为（

）

A:11至1025之间

B:11

C:10

D:10至1024之间

答案:11至1025之间

深度为h的满m叉树的第k层的结点结点个数有多少，(1=<k=<h)

（

）。

A:mk+1

B:mh+1C:mk-1

D:mh-1

答案:mk-1

将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（

）

A:6

B:7C:5

D:4

答案:6

某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E

则前序序列是（

）

A:上面的都不对B:E,G,F,A,C,D,B

C:E,A,C,B,D,G,F

D:E,A,G,C,F,B,D

答案:E,A,C,B,D,G,F

下面几个符号串编码集合中，不是前缀编码的是（

）。

A:{01,10,11,00}

B:{11,10,001,101,0001}

C:{00,010,0110,1000}D:{0,10,110,1111}

答案:{11,10,001,101,0001}

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

）

A:错B:对

答案:错

第六章测试

如果一个有向图中，任意两个顶点之间都有有向路径相通，那么这个有向图就是强连通的。（

）

A:对B:错

答案:对

当图是稠密图时，即边数|E|很接近顶点的平方|V|2。（

）

A:对B:错

答案:对

对图的每一个顶点访问一次且只访问一次的过程称为图的遍历。（

）

A:错B:对

答案:对

生成树就是将n个顶点连接在一起，且无环的一棵树。（

）

A:对B:错

答案:对

将n个顶点连在一起最多需要n-2条边。（

）

A:错B:对

答案:错

在拓扑排序过程中，要利用一个辅助的数据结构来进行排序，这个结构是什么（

）

A:栈B:树C:图D:队列

答案:队列

贪婪算法的特点。（

）

A:在算法的每一步，必须做出若干可能的选择中的一个。B:这种策略通常是不能保证找到所求解问题的全局最优解。C:可以得到局部最优解。D:贪婪策略主张所做的选择在当时是最好的选择。

答案:在算法的每一步，必须做出若干可能的选择中的一个。;这种策略通常是不能保证找到所求解问题的全局最优解。;可以得到局部最优解。;贪婪策略主张所做的选择在当时是最好的选择。

第七章测试

计算机中的查找方法是与数据的组织方式有着密切的关系。（

）

A:错B:对

答案:对

二分查找的前提是线性表有序。（

）

A:对B:错

答案:对

对于长度为n的有序表，二分查找算法的时间复杂度为O(log2n)（

）

A:对B:错

答案:对

拉链法中，同义词结点通常链接成一个单链表，链表的头指针被放置于散列表T[0..m-1]中。（

）

A:对B:错

答案:对

散列过程中，可以安全的避免冲突就必须满足哪些条件（

）

A:表无限大B:选择合适的散列函数。C:|U|≤m；D:占满整个空间

答案:选择合适的散列函数。;|U|≤m；

常见的散列函数的有（

）

A:舍入乘法B:随机数法C:除基取余法D:平方取中法

答案:舍入乘法;除基取余法;平方取中法

第八章测试

设有关键字初始序列(Q，H，C，Y，P，A，M，S，R，D，F，X)，新序列(F，H，C，D，P，A，M，Q，R，S，Y，X}是采用(

)方法对初始序列进行第一趟扫描的结果。

A:基数排序B:直接插入排序C:以第一元素为界值元素的快速排序D:二路归并排序

答案:以第一元素为界值元素的快速排序

在待排序文件已基本有序的前提下，下述排序方法中效率最高的是(

)。

A:归并排序B:直接选择排序C:直接插入排序D:快速排序

答案:快速排序

对整数序列(179，208，93，306，55，859，984，9，271，33)使用基数排序，一趟分配收集之后的结果是(

)。

A:(208，306，9，33，55，859，179，271，984，93)B:（271，93，33，984，55，306，208，179，859，9)C:(93，55，9，33，179，208，271，306，859，984)D:（9，33，55，93，179，208，271，306，859，984)

答案:（271，93，33，984，55，306，208，179，859，9)

一个排序算法的时间复杂度与(

)有关。

A:排序算法的稳定性

B:所需辅助存储空间的大小C:所采用的存储结构

D:所需比较关键字的次数

答案:所需比较关键字的次数

将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数为(

)。

A:n

B:n-1C:2n

D:2n-1

答案:n

设有一个小顶堆，其元素个数为n，顺序存储在数组A[1…n]中，则其具有最大值的元素可能在(

)位置。

A:A[1]

B:A[(n+1)/2...n]

C:A[1...n/2]

D:A[1...(n+1)/2]

答案:A[(n+1)/2...n]

对一组数据(84，47，25，15，21)排序，数据的排序次序在排序的过程中的变化为：

84

47

25

15

21，

15

47

25

84

21，

15

21

25

84

47，

15

21

25

47

84，则采用的排序方法是(

)。

A:冒泡排序B:快速排序C:插入排序D:简单选择排序

答案:简单选择排序

若用冒泡排序方法对序列（10，14，26，29，41，52）从大到小排序，需进行(

)次比较。