【期末高分题集】[东北师范大学]《数据结构（高起专）》考核必备47

奥鹏期末考核

108381–《数据结构（高起专）》2022年东北师范大学期末复习题集

单选题：
（1）内排序方法的稳定性是指 ()。
A.该排序算法不允许有相同的关键字记录
B.该排序算法允许有相同的关键字记录
C.平均时间为O(nlog2n ) 的排序方法
D.以上都不对
答案问询微信：424329

（2）顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A.附加文件
B.按关键字大小排序
C.按记录输入先后排序
D.连续排序
答案问询微信：424329

（3）在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
A.O(log2n )
B.O( 1 )
C.O(n )
D.O(nlog2n )
答案问询微信：424329

（4）在n个结点的线索二叉树中线索的数目为 ( )。
A.n-1
B.n
C.n+1
D.2n
答案问询微信：424329

（5）在下述几种排序方法中，不稳定的排序方法是 ()。
A.直接插入排序
B.冒泡排序
C.直接选择排序
D.归并排序
答案问询微信：424329

（6）ISAM文件和VSAM文件属于 ()。
A.索引非顺序文件
B.索引顺序文件
C.顺序文件
D.散列文件
答案问询微信：424329

（7）AVL树中任一结点的平衡因子的绝对值都应小于等于 ()。
A.0
B.1
C.2
D.3
答案问询微信：424329

（8）求图的最小(代价)生成树问题，考虑的是下面的哪一种图 ()。
A.无向图
B.有向图
C.带权的无向图
D.带权的有向图
答案问询微信：424329

（9）在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
A.直接插入排序
B.冒泡排序
C.快速排序
D.直接选择排序
答案问询微信：424329

（10）采用邻接表存储的图的深度优先遍历类似于二叉树的 ()。
A.前序遍历
B.中序遍历
C.后序遍历
D.层次遍历
答案问询微信：424329

（11）采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A.前序遍历
B.中序遍历
C.后序遍历
D.层次遍历
答案问询微信：424329

（12）设F是一个森林， B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有 ( ) 个。
A.n-1
B.n
C.n +1
D.n+2
答案问询微信：424329

（13）一个顺序栈一旦被说明，其占用空间的大小 ( )。
A.可以改变
B.不能固定
C.已固定
D.动态变化
答案问询微信：424329

（14）在k叉树中，度为0的结点称为 ( )。
A.根
B.叶
C.祖先
D.子孙
答案问询微信：424329

（15）在线索二叉树中，p所指结点没有左子树的充要条件是 ( )。
A.p-lchild = = NULL
B.p-ltag = = 1
C.p-ltag = = 1且p-lchild = = NULL
D.p-ltag = = 0
答案问询微信：424329

（16）将一棵有100个结点的完全二叉树从上到下、从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右子女编号为 ( )。
A.48
B.50
C.98
D.99
答案问询微信：424329

（17）在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A.1/2
B.1
C.2
D.4
答案问询微信：424329

（18）下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是 ()。
A.直接插入排序
B.快速排序
C.直接选择排序
D.堆排序
答案问询微信：424329

（19）若X是中序线索二叉树中一个有右子女的结点，且X不为根，则X的中序后继为 ( )。
A.X的双亲
B.X的右子树中最左下的结点
C.X的左子树中最右下的结点
D.X的右子树中最左下的叶结点
答案问询微信：424329

（20）顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A.散列存储
B.顺序存储或链接存储
C.压缩存储
D.索引存储
答案问询微信：424329

（21）广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是 ()。
A.( c , d )
B.c , d
C.( ( c , d ) )
D.d
答案问询微信：424329

（22）head指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。
A.p-next = = NULL
B.p = = NULL
C.p-next 奥鹏期末考核= = head
D.p = = head
答案问询微信：424329

（23）广义表 (( a , b , c , d ) ) 的表头是 ()。
A.a
B.( )
C.( a , b , c , d )
D.( b , c , d )
答案问询微信：424329

（24）在栈中存取数据的原则是 ( )。
A.先进先出
B.后进先出
C.后进后出
D.随意进出
答案问询微信：424329

（25）如果BT是由有序树T转换而来的二叉树，那么T中结点的后根序列就是BT中结点的 ( ) 序列。
A.前序
B.中序
C.后序
D.层次次序
答案问询微信：424329

（26）设s1 = "abc" ，则strlen(s1) = ( )。
A.0
B.1
C.2
D.3
答案问询微信：424329

（27）已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
A.LOC(a0)+(i-1)*c
B.LOC(a0)+i*c
C.LOC(a0)-i*c
D.LOC(a0)+(i+1)*c
答案问询微信：424329

（28）在k叉树中，无父母的结点称为 ( )。
A.根
B.叶
C.祖先
D.子孙
答案问询微信：424329

（29）设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左子女
D.任一结点无右子女
答案问询微信：424329

（30）从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行 ( )。
A.x = top; top = top-next;
B.top = top-next; x = top-data;
C.x = top-data;
D.x = top-data; top = top-next;
答案问询微信：424329

（31）下面的排序方法中，辅助空间为O( n ) 的是 ()。
A.希尔排序
B.堆排序
C.选择排序
D.归并排序
答案问询微信：424329

（32）( ) 的遍历仍需要栈的支持。
A.前序线索二叉树
B.中序线索二叉树
C.后序线索二叉树
D.前三种均需要
答案问询微信：424329

（33）二叉树在线索化后，仍不能有效求解的问题是 ( )。
A.前序线索二叉树中求前序后继
B.中序线索二叉树中求中序前驱
C.中序线索二叉树中求中序后继
D.后序线索二叉树中求后序后继
答案问询微信：424329

（34）算法分析的两个主要方面是 ( )。
A.正确性与健壮性
B.可读性与可用性
C.时间复杂度与空间复杂度
D.数据复杂性与程序复杂性
答案问询微信：424329

（35）串是一种特殊的线性表，其特殊性体现在 ( )。
A.可以顺序存储
B.数据元素是一个字符
C.可以链接存储
D.数据元素可以是多个字符
答案问询微信：424329

（36）引入线索二叉树的目的是 ( )。
A.加快查找结点的前驱或后继的速度
B.为了能方便地找到双亲
C.为了能在二叉树中方便地进行插入与删除
D.使二叉树的遍历结果唯一
答案问询微信：424329

（37）相对于顺序存储而言，链接存储的优点是 ( )。
A.随机存取
B.节省空间
C.插入、删除操作方便
D.结点间关系简单
答案问询微信：424329

（38）判断线索二叉树中某结点p有右子女的条件是 ( )。
A.p-rtag = = 0
B.p-rtag = = 1
C.p ! = NULL
D.p-lchild ! = NULL
答案问询微信：424329

（39）一个有n个结点的图，连通分量的个数最多为 ()。
A.0
B.1
C.n-1
D.n
答案问询微信：424329

（40）在索引顺序文件中， ()。
A.主文件是无序的
B.主文件是有序的
C.不适宜随机查找
D.索引是稠密索引
答案问询微信：424329

（41）在具有n个结点的完全二叉树中，若设根结点的编号为1，则编号为i(i1)的结点的双亲结点的编号是 ( )。
A.2i
B.2i+1
C.?i/2?
D.不存在
答案问询微信：424329

（42）下面哪些方法可以判断出一个有向图是否有环（回路）? ()
A.广(宽)度优先遍历
B.拓扑排序
C.求最短路径
D.求关键路径
答案问询微信：424329

（43）一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是：( )。
A.不确定
B.0
C.1
D.2
答案问询微信：424329

（44）假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
A.k-1次
B.k次
C.k+1次
D.k(k+1)/2次
答案问询微信：424329

（45）顺序表中逻辑上相邻的结点其物理位置也 ( )。
A.一定相邻
B.不必相邻
C.按某种规律排列
D.无要求
答案问询微信：424329

（46）在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。
A.希尔排序
B.插入排序
C.归并排序
D.选择排序
答案问询微信：424329

（47）下面关于算法说法错误的是（）。
A.算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C.算法的可行性是指指令不能有二义性
D.以上几个都是错误的
答案问询微信：424329

（48）有n个顶点的有向图的边数最多为 ()。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
答案问询微信：424329

（49）一个栈的入栈序列是a、b、c、d，则栈的不可能的输出序列是 ( )。
A.acbd
B.abcd
C.dbca
D.adcb
答案问询微信：424329

判断题：
（1）采用二叉链表作为存储结构，树的先根遍历和其相应的二叉树的前序遍历的结果是一样的。
答案问询微信：424329

（2）树（森林）的结点的先根遍历和后根遍历分别与它相应二又树的结点前序遍历和后序遍历是一致的。
答案问询微信：424329

（3）哈希表(散列表)的结点中只包含数据元素自身的信息，不包含任何指针。
答案问询微信：424329

（4）在有向图中，度为0的顶点称为终端顶点(或叶子)。
答案问询微信：424329

（5）倒排文件的优点是维护简单。
答案问询微信：424329

（6）二叉树的中序遍历序列中，任意一个结点均处在其右子女结点( 若存在 )的前面。
答案问询微信：424329

（7）中序线索二叉树的优点是便于在中序下查找前驱结点和后继结点。
答案问询微信：424329

（8）无向图的邻接矩阵可用一维数组存储。
答案问询微信：424329

（9）数组不适合作为任何二叉树的存储结构。
答案问询微信：424329

（10）拓扑排序算法仅适用于有向无环图。
答案问询微信：424329

（11）对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
答案问询微信：424329

（12）空串与空格串是相同的。
答案问询微信：424329

（13）通常使用队列来处理函数或过程的调用。
答案问询微信：424329

（14）栈和队列都是限制存取点的线性结构。
答案问询微信：424329

（15）AOV网的含义是以顶点表示活动的网。
答案问询微信：424329

（16）顺序存储方式只能用于存储线性结构。
答案问询微信：424329

（17）( 101, 88, 46, 70, 34, 39, 45, 58, 66, 10）是堆。
答案问询微信：424329

（18）两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。
答案问询微信：424329

（19）消除递归不一定需要使用栈。
答案问询微信：424329

（20）二叉树的遍历结果不是唯一的。
答案问询微信：424329

（21）二叉树中每个结点至多有两个子结点，而对一般的树则无此限制。因此，二叉树是树的特殊情形。
答案问询微信：424329

（22）在中序线索二叉树中，每一非空的线索均指向其祖先结点。
答案问询微信：424329

（23）完全二叉树肯定是平衡二叉排序树。
答案问询微信：424329

（24）将一棵树转成二叉树，根结点没有右子树。
答案问询微信：424329

（25）任何一个递归过程都可以转换成非递归过程。
答案问询微信：424329

（26）哈希表(散列表)的平均查找长度与处理冲突的方法无关。
答案问询微信：424329

（27）堆是完全二叉树。
答案问询微信：424329

（28）快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n )。
答案问询微信：424329

（29）哈希法(散列法)的平均查找长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
答案问询微信：424329

（30）无向图的邻接矩阵是对称的。
答案问询微信：424329

（31）非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
答案问询微信：424329

（32）在待排数据基本有序的情况下，快速排序效果最好。
答案问询微信：424329

（33）堆是满二叉树。
答案问询微信：424329