智慧树知到《数据结构与算法》章节测试答案

智慧树知到《数据结构与算法》章节测试答案
第一章
1、在数据结构中，从逻辑上可以把数据结构分成（ ）。
A:紧凑结构和非紧凑结构
B:线性结构和非线性结构
C:内部结构和外部结构
D:动态结构和静态结构
正确答案：线性结构和非线性结构
2、在数据结构中，从存储结构上可以将之分为（ ）。
A:动态结构和静态结构
B:顺序存储和非顺序存储
C:紧凑结构和非紧凑结构
D:线性结构和非线性结构
正确答案：顺序存储和非顺序存储
3、某算法的时间复杂度是O(n^2)，表明该算法的（ ）。
A:执行时间与n^2成正比
B:问题规模是n^2
C:执行时间等于n^2
D:问题规模与n^2成正比
正确答案：执行时间与n^2成正比
4、在下面的程序段中，x=x+1;的语句频度为（ ）。for( i=1;i<=n;i++) for( j=1;j<=n;j++) x=x+1;
A:O(2n)
B:O(n)
C:O(n^2)
D:O(log2n)
正确答案：O(n^2)
5、以下数据结构中，（ ）是非线性数据结构。
A:树
B:字符串
C:队
D:栈
正确答案：树
6、顺序存储，存储单元的地址（ ）。
A:一定连续
B:一定不连续
C:不一定连续
D:部分连续，部分不连续
正确答案：一定连续
7、评价一个算法性能好坏的重要标准是( )。
A:算法的正确性
B:算法易于调试
C:算法的时间和空间复杂度
D:算法易于理解
正确答案：算法的时间和空间复杂度
8、若需要利用形式参数直接访问修改实参值，则应将形参说明为（ ）参数。
A:值参数
B:实地址
C:指针
D:地址参数
正确答案：指针
9、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A:对
B:错
正确答案：错
10、数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。
A:对
B:错
正确答案：对
第二章
1、下述哪一条是顺序存储结构的优点（）。
A:可方便地用于各种逻辑结构的存储表示
B:插入运算方便
C:删除运算方便
D:存储密度大
正确答案：存储密度大
3、设某顺序表中第一个元素的地址是se（下标从1开始），每个结点占m个单元，则第i个结点的地址为（）。
A:se+(i-1)×m
B:se+(i+1)×m
C:se+i×m
D:se-i×m
正确答案：se+(i-1)×m
4、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A:单链表
B:仅有尾指针的单循环链表C:仅有头指针的单循环链表
D:双链表
正确答案：仅有尾指针的单循环链表
5、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）。
A:O(n)
B:O(0)
C:O(1)
D:O(n^2)
正确答案：O(n)
6、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）。
A:s->next=p->next;p->next=s;
B:p->next=s;s->next=p->next;
C:p->next=s;p->next=s->next;
D:p->next=s->next;p->next=s;
正确答案：s->next=p->next;p->next=s;
7、 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。
A:head→next==NULL;
B:head==NULL;
C:head→next==he;
D:head!=NULL;
正确答案：head→next==NULL;
8、 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
A:对
B:错
正确答案：对
9、 顺序表适宜于顺序存取，而链表适宜于随机存取。
A:对
B:错
正确答案：错
10、线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
A:对
B:错
正确答案：对
第三章
1、栈和队列都是（ ）。
A:限制存取点的非线性结构
B:顺序存储的线性结构
C:链式存储的非线性结构
D:限制存取点的线性结构
正确答案：限制存取点的非线性结构
2、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后随即进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。
A:3
B:6
C:4
D:2
正确答案：A
3、设计一个判别表达式中括号是否匹配出现的算法，采用（ ）的数据结构最佳。
A:栈
B:顺序表
C:队列
D:单链表
正确答案：A
4、表达式a*(b+c)-d的后缀表达式是( )。
A:abc+d-
B:cb+ad-
C:abc+*d-
D:abcd+-
正确答案：abc+*d-
5、递归过程或函数调用时，处理参数及返回地址需要用一种（ ）的数据结构。
A:栈
B:队列
C:多维数组
D:线性表
正确答案：A
6、最大容量为n的循环队列，队尾指针为rear，队头指针为front，则队空的条件是（ ）。
A:rear==front
B:(rear+1)%n==front
C:rear+1==front
D:(rear-l)%n==front
正确答案：rear==front
7、用带头结点的单链表表示队长大于1的队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ ）。
A:仅修改队头指针
B:仅修改队尾指针
C:队头、队尾指针都要修改
D:队头,队尾指针都可能要修改
正确答案：仅修改队头指针
8、对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（ ）。
A:O(1),O(n)
B:O(n),O(n)
C:O(1),O(1)
D:O(n),O(1)
正确答案：A
9、两顺序栈共享空间，也存在空间溢出问题。
A:对
B:错
正确答案：A
10、在对不带头结点的链队列作出队操作时，不会改变头指针的值。
A:对
B:错
正确答案：B
第四章
1、串是一种特殊的线性表，其特殊性体现在（ ）。
A:数据元素是单个字符
B:顺序存储
C:链式存储
D:逻辑结构是线性结构
正确答案：数据元素是单个字符
2、若串S= ‘software’，其前缀真子串的数目是( )。
A:7
B:10
C:9
D:8
正确答案：A
3、设有两个串p和q ，其中q是p的子串，求q在p中首次出现的位置的算法称为( )。
A:串的模式匹配
B:求子串
C:串联接
D:求串长
正确答案：A
4、已知串 S=‘aaab’，其next函数值为（ ）。
A:0123
B:1123
C:1231
D:1211
正确答案：A
5、函数strcmp(‘stcabuc’,’stbabuc’)的返回值是（ ）。
A:0
B:-1
C:2
D:1
正确答案：D
6、KMP算法的特点是在模式匹配时指示主串的指针不会回溯。
A:对
B:错
正确答案：A
7、模式串 P=‘abaabcac’的next函数值序列为01122312。
A:对
B:错
正确答案：A
8、串的存储结构有顺序串、堆串和块链串三种。
A:对
B:错
正确答案：A
9、子串的定位运算称为串的模式匹配。
A:对
B:错
正确答案：A
10、串’student’和’Student’相等。
A:对
B:错
正确答案：B
第五章
1、假设以行序为主序存储二维数组A=array[1…100，1…100]，设每个数组元素占2个存储单元，基地址为10，则LOC[5，5]=( )。
A:818
B:808
C:1010
D:1020
正确答案：A
2、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1…(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的计算公式为（ ）。
A:j(j-1)/2+i
B: j*(j-1)/2+i
C: i(i+1)/2+j
D: j(j+1)/2+i
正确答案：j*(j-1)/2+i
3、设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
A:1和2
B:1和1
C:1和3
D:2和3
正确答案：A
4、在稀疏矩阵的三元组顺序表中，每个三元组表示（ ）。
A:矩阵中数据元素的行号、列号和数据值
B: 矩阵中非零元素的数据值
C: 矩阵中数据元素的行号和列号
D: 矩阵中非零元素的行号、列号和数据值
正确答案：B
5、 多维数组可以看作是一种特殊的线性表。
A:对
B:错
正确答案：A
6、一个稀疏矩阵A[m,n]采用三元组顺序表形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了A[m,n]的转置运算。
A:对
B:错
正确答案：B
7、广义表B = (a, B) = (a, (a, (a,…, ) ) ) 的长度为无穷大。
A:对
B:错
正确答案：A
8、一个广义表可以为其它广义表所共享。
A:对
B:错
正确答案：A
9、稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。
A:对
B:错
正确答案：A
10、tail（head（（（a,b,c,d,e））））=(a,b,c,d,e)。
A:对
B:错
正确答案：B
第六章
1、树最适合用来表示的结构是（ ）。
A:元素间具有分支及层次关系的结构
B:元素间的有序结构
C:元素间的无序结构
D:元素间无联系的结构
正确答案：A
2、任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置( )。
A:肯定发生变化
B:肯定不发生变化
C:有时发生变化
D:无法确定
正确答案：B
3、判断线索二叉树中某结点P有左孩子的条件是（ ）。
A:p->LTag==1
B:p!=NULL
C:p->lchild!=NULL
D:p->LTag==0
正确答案：D
4、设森林T中有4棵树，其结点个数分别为n1,n2,n3,n4，那么当森林T转换成一棵二叉树后，则根结点的右子树上有（ ）个结点。
A:n2+n3+n4
B: n1-1
C:n1
D:n1+n2+n3
正确答案：A
5、以数据集{4，5，6，7，10，12，18}为叶结点权值所构造的哈夫曼树，其带权路径长度为（ ）。
A:155
B:160
C:165
D:170
正确答案：C
6、以下属于前缀编码的是（ ）。
A:{0,1101,1110,1100,1111}
B:{0,1,01,010,110}
C:{00,01,10,11,101}
D:{01,00,10,001,110,101}
正确答案：A
7、一棵具有N个结点的二叉树采用二叉链表进行存储，其中空指针域有( )个。
A:N+1
B:N
C:N-1
D:不确定
正确答案：A
8、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有（ ）个叶子结点。
A:10
B:11
C:12
D:13
正确答案：C
9、满二叉树一定完全是二叉树。
A:对
B:错
正确答案：A
10、二叉树的遍历结果不是唯一的。
A:对
B:错
正确答案：A
第七章
1、一个具有n个顶点的无向图最多有（ ）边。
A:n(n-1)/2
B:n(n-1)
C:n
D:2n
正确答案：A
2、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则占用的存储空间为（ ）。
A:n+e
B:e
C:2e
D:n+2e
正确答案：D
3、如果含有n个顶点的图形成一个环，则它有（ ）棵生成树。
A:n
B:n-1
C:n+1
D:不确定
正确答案：A
4、任何一个无向连通网的最小生成树（ ）。
A:有一棵或多棵
B:只有1棵
C:一定有多棵
D:可能不存在
正确答案：A
5、判断一个有向图是否存在回路，可以用（ ）。
A:广度优先遍历算法
B:求关键路径的方法
C:Dijkstra方法
D:深度优先遍历算法
正确答案：D
6、关键路径是事件结点网络中（ ）。
A:从源点到汇点的最长路径
B:最长回路
C:从源点到汇点的最短路径
D:最短回路
正确答案：A
7、深度优先遍历类似于二叉树的（ ）。
A:先序遍历
B:中序遍历
C:后序遍历
D:层次遍历
正确答案：A
8、广度优先遍历类似于二叉树的( )。
A:先序遍历
B:中序遍历
C:后序遍历
D:层次遍历
正确答案：D
9、迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。
A:对
B:错
正确答案：A
10、任何一个有向图都一定存在拓扑序列。
A:对
B:错
正确答案：B
第八章
1、具有12个关键字的有序表，折半查找的平均查找长度( )。
A:‘10/12
B:25
C:’25/12
D:‘37/12
正确答案：D
2、如果要求用线性表既能较快地查找，又能适应动态变化的要求，则可采用（ ）查找方法。
A:分块查找
B:顺序查找
C:折半查找
D:基于属性
正确答案：A
3、已知一如下10个记录的表，其关键字序列为（2，15，19，25，30，34，44，55，58，80），用折半查找法查找关键字为55的记录，比较次数是（ ）。
A:1次
B: 2次
C:3次
D:4次
正确答案：B
4、如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，在等概率情况下查找成功时的平均查找长度ASL为( ）。
A:50
B:48
C:45
D:47
正确答案：A
5、对包含n个元素的散列表进行查找，平均查找长度为（ ）。
A:不直接依赖于n
B:O(n2)
C:O(log2n)
D:O(n)
正确答案：A
6、 衡量查找算法效率的主要标准是（ ）。
A:平均查找长度
B:元素个数
C:所需的存储量
D:算法难易程度
正确答案：A
7、Hash表的平均查找长度与处理冲突的方法无关。
A:对
B:错
正确答案：B
8、在二叉树排序树中插入一个新结点，总是插入到叶结点下面。
A:对
B:错
正确答案：A
9、哈希表是一种将关键字转换为存储地址的存储方法。
A:对
B:错
正确答案：A
10、在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。
A:对
B:错
正确答案：B
第九章
1、 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始小根堆为( )。
A:-1，4，7，8，20，15，7，9
B:-1，4，8，9，20，7，15，7
C:-1，7，15，7，4，8，20，9
D: A，B，C均不对。
正确答案：A
2、一组记录的关键字为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A:（40, 38, 46, 56, 79, 84）
B:（38, 40, 46, 56, 79, 84）
C:（40, 38, 46, 79, 56, 84）
D:（40, 38, 46, 84, 56, 79）
正确答案：A
3、对下列整数序列使用基数排序，一趟分配收集之后的结果是( )。（179，208，93，306，55，859，984，9，271，33）
A:{271,93,33,984,55,306,208,179,859,9}
B:{93,55,9,33,179,208,271,306,859,984}
C:{208,306,9,33,55,859,179,271,984,93}
D:{9,33,55,93,179,208,271,306,859,984}
正确答案：A
4、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{9，15，7，8，20，-1，4}，则采用的排序方法是（ ）。
A:直接插入排序
B:选择排序
C:堆排序
D:希尔排序
正确答案：A
5、评价排序算法好坏的标准主要是（ ）。
A:执行时间和所需的辅助空间
B:执行时间
C:辅助空间
D:算法本身的复杂度
正确答案：A
6、对ｎ个不同的排序码进行冒泡（递增）排序，在下列（ ）情况比较的次数最多。
A:从大到小排列好的
B:从小到大排列好的
C:元素无序
D:元素基本有序
正确答案：A
7、简单选择排序和堆排序性能都受初始序列顺序的影响。
A:对
B:错
正确答案：B
8、 快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。
A:对
B:错
正确答案：A
9、堆排序所需的时间与待排序的记录个数无关。
A:对
B:错
正确答案：B
10、采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。
A:对
B:错
正确答案：A