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