在线网课学习课堂《数据结构(云南大学）》单元测试考核答案

注：不含主观题
第1题
数据结构研究的内容涉及()
A 数据如何组织
B 数据如何存储
C 数据的运算如何实现
D 算法用什么语言来描述
测试题
第1题
数据元素是数据的最小单位（ ）
测试题
第1题
在数据结构中，从逻辑上可以将之分为()
A 动态结构和静态结构
B 紧凑结构和非紧凑结构
C 内部结构和外部结构
D 线性结构和非线性结构
第2题
数据结构中数据元素之间的逻辑关系被称为()
A 数据的存储结构
B 数据的基本操作
C 程序的算法
D 数据的逻辑结构
测试题
第1题
可以用()定义一个完整的数据结构
A 数据元素
B 数据对象
C 数据关系
D 抽象数据类型
测试题
第1题
算法的时间复杂度是属于一种()
A 事前统计的方法
B 事前分析估算的方法
C 事后统计的方法
D 事后分析估算的方法
第2题
算法分析的目的是（ ）
A 找出数据结构的合理性
B 研究算法中的输入和输出的关系
C 分析算法的效率以求改进
D 分析算法的易懂性和文档性
第3题
计算机算法必须具备输入、输出和()等5个特性。
A 可行性、可移植性和可扩充性
B 可行性、确定性和有穷性
C 确定性、有穷性和稳定性
D 易读性、稳定性和安全性
第4题
算法即程序（ ）
第5题
健壮的程序不会因非法的输入数据而出现莫名其妙的状态。( )
测试题
第1题
程序段 for(i:=n-1;i>=1;i–)
for(j:=1;j<=i;j++)
if(A[j]>A[j+1])
A[j]←→A[j+1]；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）
A O（n）
B O(nlogn)
C O(n3)
D O(n2)
测试题
第1题
线性表是具有n个（ ）的有限序列。
A 表元素
B 字符
C 数据元素
D 数据项
测试题
第1题
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
A O(0)
B O(1)
C O(n)
D O(n2)
第2题
顺序存储的线性表是一种非随机存储结构()
第3题
下述哪一条是顺序存储结构的优点？（ ）
A 插入运算方便
B 可方便地用于各种逻辑结构的存储表示
C 存储密度大
D 删除运算方便
测试题
第1题
在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A p->next=s;s->next=p->next;
B s->next=p->next;p->next=s;
C p->next=s;p->next=s->next;
D p->next=s->next;p->next=s;
第2题
链表不具有的特点是（ ）
A 插入、删除不需要移动元素
B 可随机访问任一元素
C 不必事先估计存储空间
D 所需空间与线性长度成正比
第3题
对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
A head==NULL
B head→next==NULL
C head→next==head
D head!=NULL
第4题
线性表的逻辑顺序与存储顺序总是一致的。（ ）
测试题
第1题
静态链表中指针表示的是（ ）
A 内存地址
B 数组下标
C 下一元素下标
D 左、右孩子地址
测试题
第1题
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A 单链表
B 仅有头指针的单循环链表
C 双链表
D 仅有尾指针的单循环链表
第2题
下面关于线性表的叙述中，错误的是哪一个？（ ）
A 线性表采用顺序存储，必须占用一片连续的存储单元。
B 线性表采用顺序存储，便于进行插入和删除操作。
C 线性表采用链接存储，不必占用一片连续的存储单元
D 线性表采用链接存储，便于插入和删除操作。
第3题
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A 顺序表
B 双链表
C 带头结点的双循环链表
D 单循环链表
测试题
第1题
对于栈,操作数据的原则是（）。
A 先进先出
B 后进先出
C 后进后出
D 不分顺序
第2题
有六个元素6，5，4，3，2，1顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A 5 4 3 6 1 2
B 4 5 3 1 2 6
C 3 4 6 5 2 1
D 2 3 4 1 5 6
第3题
如进栈序列是1，2，3，4，5。 可能得到的出栈序列为()
A 1,2,5,3,4
B 3,1,2,5,4
C 3,2,5,4,1
D 1,4,2,3,5
第4题
一个栈的入栈序列为A,B,C,D,E，则栈的不可能的出栈序列是()。
A ABCDE
B EDCBA
C DECBA
D DCEAB
测试题
第1题
栈和链表是两种不同的数据结构。 ( )
第2题
两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。( )
测试题
第1题
4个园盘的Hahoi塔，总的移动次数为()
A 7
B 8
C 15
D 16
测试题
第1题
用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时()
A 仅修改队头指针
B 仅修改队尾指针
C 队头，队尾指针都可能要修改
D 队头，队尾指针都要修改
第2题
栈和队列是一种非线性数据结构。( )
测试题
第1题
对于循环队列()。
A 无法判断队列是否为空
B 无法判断队列是否为满
C 队列不可能满
D 以上说法都不是
第2题
循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。
A (rear-front+m)%m
B rear-front+1
C rear-front-1
D rear-front
测试题
第1题
若串S=’software’,其子串的数目是( )。
A 8
B 37
C 36
D 9
第2题
串是一种特殊的线性表，其特殊性体现在()。
A 数据元素是一个字符
B 可以顺序存储
C 数据元素可以是多个字符
D 可以链接存储
第3题
空串与空格串是相同的。（ ）
第4题
两个字符串相等的充分必要条件是长度相等，并且各个对应位置上的字符都相等()
第5题
下面关于串的的叙述中，哪一个是不正确的？（ ）
A 串是字符的有限序列
B 空串是由空格构成的串
C 模式匹配是串的一种重要运算
D 串既可以采用顺序存储，也可以采用链式存储
测试题
第1题
数组通常具有的两种基本操作是( )。
A 查找和修改
B 查找和索引
C 索引和修改
D 建立和删除
第2题
若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是(  )。
A 1040
B 1042
C 1026
D A，B，C都不对
第3题
数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
测试题
第1题
对矩阵压缩存储是为了()。
A 方便运算
B 方便存储
C 提高运算速度
D 减少存储空间
第2题
设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为( )。
A 13
B 33
C 18
D 40
测试题
第1题
设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A 5
B 6
C 7
D 8
第2题
对于有N个结点的二叉树，其高度为log2n。（）
第3题
完全二叉树中，若一个结点没有左孩子，则它必是树叶。（ ）
第4题
若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（  ）
A 9
B 11
C 15
D 不确定
第5题
已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。
A 311
B 312
C 313
D 314
第6题
一个具有1025个结点的二叉树的高h为（ ）
A 11
B 10
C 11至1025之间
D 10至1024之间
第7题
有n（n> 0）个分支结点的满二叉树的深度是()。
A n2-1
B log2(n+1)+1
C log(2*(n+1))
D log2(n-1)
第8题
将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ ）
A 4
B 5
C 6
D 7
测试题

第1题
二叉树只能用二叉链表表示。（）
测试题
第1题
一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
A 所有的结点均无左孩子
B 所有的结点均无右孩子
C 只有一个叶子结点
D 是任意一棵二叉树
第2题
二叉树的遍历结果不是唯一的.（ ）
第3题
一棵二叉树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）
第4题
用二叉树的前序遍历和中序遍历可以导出树的后序遍历。（）
第5题
某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA,则该二叉树对应的森林包括()棵树。
A 1
B 2
C 3
D 4
第6题
在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）
A 都不相同
B 完全相同
C 先序和中序相同，而与后序不同
D 中序和后序相同，而与先序不同
第7题
若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A 先序
B 中序
C 后序
D 层序
测试题
第1题
引入二叉线索树的目的是（ ）
A 加快查找结点的前驱或后继的速度
B 为了能在二叉树中方便的进行插入与删除
C 为了能方便的找到双亲
D 使二叉树的遍历结果唯一
第2题
（ ）的遍历仍需要栈的支持.
A 先序线索树
B 中序线索树
C 后序线索树
第3题
一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )
A 不确定
B 1
C 2
第4题
后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。（）
测试题
第1题
设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
A n-1
B n
C n+1
D n+2
第2题
一棵二叉树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）
第3题
设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A M1
B M1+M2
C M3
D M2+M3
第4题
树的后根遍历序列等同于该树对应的二叉树的()
A 先序序列
B 中序序列
C 后序序列
测试题
第1题
下述编码中哪一个不是前缀码（）。
A 00，01，10，11
B 0，1，00，11
C 0，10，110，111
D 1，01，000，001
第2题
一棵Huffman树共有215个结点，对其进行Huffman编码，共能得到()个不同的码字
A 107
B 108
C 214
D 215
第3题
设给定权值总数有n 个，其哈夫曼树的结点总数为( )
A 不确定
B 2n
C 2n+1
D 2n-1
测试题
第1题
树中的结点和图中的顶点都是指数据结构中的数据元素。（ ）
第2题
在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）
第3题
有e条边的无向图，在邻接表中有e个结点。（ ）
第4题
连通分量指的是有向图中的极大连通子图。（ ）
第5题
图中有关路径的定义是（ ）。
A 由顶点和相邻顶点序偶构成的边所形成的序列
B 由不同顶点所形成的序列
C 由不同边所形成的序列
D 上述定义都不是
第6题
具有4个顶点的无向完全图有( )条边。
A 6
B 12
C 16
D 20
第7题
图G是n个顶点的无向完全图， 则下列说法正确的有：（ ）
A G的邻接多重表需要n(n-1)个边结点和n个顶点结点；
B G的连通分量个数最少
C G为连通图
D G所有顶点的度的总和为n(n-1)
第8题
要连通具有n个顶点的有向图，至少需要（ ）条边。
A n-1
B n
C n+1
D 2n
第9题
一个n个顶点的连通无向图，其边的个数至少为（ ）。
A n-1
B n
C n+1
D nlogn
测试题
第1题
有e条边的无向图，在邻接表中有e个结点。（ ）
第2题
用数组表示法存储一个图所需的存储单元数目与图的边数有关。（ ）
第3题
一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ）
第4题
在有向图的邻接表存储结构中，顶点v在链表中出现的次数是()。
A 顶点v的度
B 顶点v的出度
C 顶点v的入度
D 依附于顶点v的边数
第5题
n个顶点的无向图的邻接表最多有( )个表结点。
A n2
B n(n-1)
C n(n+1)
D n(n-1)/2
第6题
下列哪一种图的邻接矩阵是对称矩阵？（ ）
A 有向图
B 无向图
C AOV网
D AOE网
测试题
第1题
广度优先遍历类似于二叉树的( )
A 先序遍历
B 中序遍历
C 后序遍历
D 层次遍历
测试题
第1题
图的BFS生成树的树高比DFS生成树的树高().
A .小或相等
B 小
C 大或相等
D 大
第2题
连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
第3题
在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
A O(n)
B O(n+e)
C O(n2)
D O(n3)
测试题
第1题
已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（  ）。
A V1,V3,V4,V6,V2,V5,V7
B V1,V3,V2,V6,V4,V5,V7
C V1,V3,V4,V5,V2,V6,V7
D V1,V2,V5,V3,V4,V6,V7
第2题
无环有向图才能进行拓扑排序。（ ）
第3题
若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（ ）
第4题
在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
A G中有弧
B G中有一条从Vi到Vj的路径
C G中没有弧
D G中有一条从Vj到Vi的路径
第5题
下列关于AOE网的叙述中，不正确的是（ ）。
A 关键活动不按期完成就会影响整个工程的完成时间
B 任何一个关键活动提前完成，那么整个工程将会提前完成
C 所有的关键活动提前完成，那么整个工程将会提前完成
D 某些关键活动若提前完成，那么整个工程将会提前完成
测试题
第1题
当各边上的权值(  )时，BFS算法可用来解决单源最短路径问题。
A 均相等
B 均互不相等
C 不一定相等
第2题
求解最短路径的Floyd算法的时间复杂度为()
A O（n）
B O（n+c）
C O（n*n）
D O（n*n*n）
测试题
第1题
采用顺序查找方法查找长度为n的线性表，每个元素的平均查找长度为()。
A n
B n/2
C (n+1)/2
D (n-1)/2
第2题
在一个有N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为()
A O(1)
B O(N)
C O（N2）
D O(NlogN)
测试题
第1题
查找相同结点的效率折半查找总比顺序查找高。（ ）
第2题
有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当用二分法查找值为82的结点时（
）次比较后查找成功
A 1
B 2
C 4
D 8
第3题
对线性表进行二分查找时，要求线性表必须（）
A 以顺序方式存储
B 以顺序方式存储,且数据元素有序
C 以链接方式存储
D 以链接方式存储,且数据元素有序
测试题
第1题
对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。（ ）
第2题
N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。（）
第3题
设二叉排序中关键字由1到1000的鳖数构成,现要查找关健字为363的结点,下述关键字序列中,不可能是在二叉排序树上查找的序列的是( )。
A 2,252.401,398,330,344,397,363
B 924,220,911,244,898,258,363
C 925,202,911,240,912,245,363
D 2,399,387,219,266,382,381,278,363
测试题
第1题
设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1必定相同。（ ）
第2题
下列二叉排序树中查找效率最高的是( )
A 平衡二叉树
B 二叉查找树
C 没有左子树的二叉排序树
D 没有右子树的二叉排序树
第3题
在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
A LL
B LR
C RL
D RR
第4题
在平衡二叉树中,进行查找的效率与( )有关。
A 二叉树的深度
B 二叉排序树的结点的个数
C 后序线索树
D 所有线索树
测试题
第1题
下面关于哈希(Hash，杂凑)查找的说法正确的是( )
A 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B 除留余数法是所有哈希函数中最好的
C 不存在特别好与坏的哈希函数，要视情况而定
D 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
第2题
设哈希表长M=14，哈希函数H(KEY)=KEY  MOD 11。表中已有4个结点：ADDR(15)=4， ADDR(38)=5，ADDR(61)=6，ADDR(84)=7，其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是( )。
A 8
B 3
C 5
D 9
第3题
将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。
A 一定会
B 一定不会
C 仍可能会
第4题
假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )
A k-1次
B k次
C k+1次
D k（k+1）/2次
第5题
Hash表的平均查找长度与处理冲突的方法无关。（ ）
测试题
第1题
一个排序算法的时间复杂度与()有关。
A 排序算法的稳定性
B 所需比较关键字的次数
C 所采用的存诸结构
D 所需辅助存诸空间的大小
第2题
排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
第3题
用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ ）。
A 94,32,40,90,80,46,21,69
B 32,40,21,46,69,94,90,80
C 21,32,46,40,80,69,90,94
D 90,69,80,46,21,32,94,40
第4题
直接插入排序在最好情况下的时间复杂度为（ ）
A O(logn)
B O(n)
C O(n*logn)
D O(n2)
测试题
第1题
在排序记录序列“基本有序”或记录序列较短的情况下，最佳内部排序方法是（ ）。
A 直接插入排序
B 起泡排序
C 简单选择排序
第2题
对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是  ( )
A 1
B 4
C 3
D 2
测试题
第1题
对ｎ个不同的排序码进行冒泡排序，最终序列自小到大，在下列（ ）情况下比较的次数最多。
A 从小到大排列好的
B 从大到小排列好的
C 元素无序
D 元素基本有序
第2题
一组记录的关键字为（46，79，56，38，40，84），则利用快速排序方法，以第一个记录的关键字为分割点，得到的一次划分结果为（）
A 38，40，46，56，79，84
B 40，38，46，79，56，84
C 40，38，46，56，79，84
D 40，38，46，84，56，79
第3题
快速排序在下列（）情况下最易发挥其长处。
A 被排序的数据中含有多个相同排序码
B 被排序的数据已基本有序
C 被排序的数据完全无序
D 被排序的数据中的最大值和最小值相差悬殊
第4题
快速排序在最坏情况下的时间复杂度是O(n2),比()的性能差。
A 起泡排序
B 选择排序
C 堆排序
测试题
第1题
下面给出的四种排序方法中，排序过程中的比较次数与初始序列无关的是。( )
A 选择排序
B 插入排序
C 快速排序
D 堆排序
测试题
第1题
以下序列不是堆的是（）
A 100，85，98，77，80，60，82，40，20，10，66
B 100，98，85，82，80，77，66，60，40，20，10
C 10，20，40，60，66，77，80，82，85，98，100
D 100，85，40，77，80，60，66，98，82，10，20
第2题
在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（）
A O(log2n)
B O(1)
C O(n)
D O(nlog2n)
第3题
数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的(
)的两趟排序后的结果。
A 选择排序
B 冒泡排序
C 插入排序
D 堆排序
测试题
第1题
归并排序中，归并的趟数是(  )
A O（n）
B O(logn)
C O(nlogn)
D O(n*n)
第2题
下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A 选择
B 冒泡
C 归并
D 堆
第3题
若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A 快速排序
B 堆排序
C 直接插入排序
D 归并排序
测试题
第1题
给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),采用链式基数排序算法从小到大排序时，第一趟结束时的序列是( )
A 12,2,10,20,6,18,4,16,30,8,28
B 6,2,10,4,8,12,28,30,20,16,18
C 30,10,20,12,2,4,16,6,8,28,18
D 2,4,6,8,10,12,16,18,20,28,30

AI创作