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

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

）

A:对

B:错

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

）

A:错

B:对

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

）

A:错

B:对

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

）。

A:链式结构

B:非线性结构

C:存储结构

D:线性结构

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

）。

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

B:设计数据结构

C:使用程序语言编程

D:设计求解算法

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

）

A:类语言

B:计算机高级语言

C:自然语言

D:流程图

答案:ABCD第二章测试下面关于线性表的叙述中，错误的是哪一个（

）

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

B:线性表采用链接存储，便于插入和删除操作。

C:线性表采用顺序存储，必须占用一片连续的存储单元。

D:线性表采用链接存储，不必占用一片连续的存储单元。

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

）。

A:O(n)

B:O(1)

C:O(log2n)

D:O(n2)

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

）

A:错

B:对

答案:A单循环链表H的尾结点p的特点是（

）。

A:p==H

B:p->next==

H->next

C:p->next==H

D:p==H

->next

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

A:n/2

B:(2n-1)/2

C:(n+1)/2

D:(n-1)/2

答案:A第三章测试栈可以应用在哪里（

）。

A:表达式求值

B:A，Ｂ，Ｃ

C:递归调用

D:子程序调用

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

）。

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

B:栈

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

D:队列

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

）。

A:rear=(rear+1)

%

m

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

C:rear=(rear+1)

%

(m-1)

D:rear=rear+1

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

）

A:错

B:对

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

）

A:错

B:对

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

）。

A:对栈不作任何判别

B:判别栈元素的类型

C:必须判别栈是否为空

D:必须判别栈是否为满

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

）

A:对

B:错

答案:A第四章测试设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8

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

）。

A:BA+222

B:BA+225

C:BA+141

D:BA+180

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

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

）。

A:195

B:196

C:197

D:198

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

)。

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

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

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

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

答案:D设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:j(j-l)/2+i-1

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

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

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

）

A:错

B:对

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

）。

A:O(n)

B:O(nlog2n)

C:O(1)

D:O(n2)

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

）

A:错

B:对

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

）。

A:16

B:36

C:45

D:55

答案:C设二维数组A[1..

m，1..

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

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

)。

A:jm+i-1

B:i（j-1）

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

D:（i-1）n+j

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

)。

A:1210

B:1175

C:1180

D:1205

答案:B第五章测试设树T的度为4，其中度为1、2、3和4的结点个数分别为4,2,1,1，则T中的叶子结点数为

（

）

A:6

B:8

C:7

D:5

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

）

A:6

B:4

C:5

D:3

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

）。

A:500

B:254

C:都不对

D:505

E:250

答案:C一个具有1025个结点的二叉树的高h为（

）

A:11

B:10至1024之间

C:11至1025之间

D:10

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

（

）。

A:mk+1

B:mk-1

C:mh+1

D:mh-1

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

）

A:4

B:5

C:7

D:6

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

则前序序列是（

）

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

B:上面的都不对

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

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

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

）。

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

B:{00,010,0110,1000}

C:{01,10,11,00}

D:{0,10,110,1111}

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

）

A:对

B:错

答案:B第六章测试如果一个有向图中，任意两个顶点之间都有有向路径相通，那么这个有向图就是强连通的。（

）

A:错

B:对

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

）

A:对

B:错

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

）

A:对

B:错

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

）

A:错

B:对

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

）

A:错

B:对

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

）

A:队列

B:栈

C:图

D:树

答案:A贪婪算法的特点。（

）

A:这种策略通常是不能保证找到所求解问题的全局最优解。

B:贪婪策略主张所做的选择在当时是最好的选择。

C:可以得到局部最优解。

D:在算法的每一步，必须做出若干可能的选择中的一个。

答案:ABCD第七章测试计算机中的查找方法是与数据的组织方式有着密切的关系。（

）

A:错

B:对

答案:B二分查找的前提是线性表有序。（

）

A:对

B:错

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

）

A:错

B:对

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

）

A:对

B:错

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

）

A:表无限大

B:|U|≤m；

C:占满整个空间

D:选择合适的散列函数。

答案:BD常见的散列函数的有（

）

A:随机数法

B:舍入乘法

C:平方取中法

D:除基取余法

答案:BCD第八章测试设有关键字初始序列(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在待排序文件已基本有序的前提下，下述排序方法中效率最高的是(

)。

A:直接选择排序

B:直接插入排序

C:归并排序

D:快速排序

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

)。

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

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

C:(208，306，9，33，55，859，179，271，984，93)

D:(93，55，9，33，179，208，271，306，859，984)

答案:B一个排序算法的时间复杂度与(

)有关。

A:排序算法的稳定性

B:所采用的存储结构

C:所需辅助存储空间的大小

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

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

)。

A:n

B:2n

C:2n-1

D:n-1

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

)位置。

A:A[1…n/2]

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

C:A[1…(n+1)/2]

D:A[1]

答案:B对一组数据(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:简单选择排序

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

)次比较。

A:10