东北师范大学《数据结构（高起专）》期末考试必备题集

奥鹏期末考核

108381–东北师范大学《数据结构（高起专）》奥鹏期末考试题库合集

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

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

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

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

（10）由3个结点可以构造出多少种不同形态的有向树？( )
A.2
B.3
C.4
D.5
答案问询微信：424329

（11）平衡的二叉排序树(AVL树)属于()的数据结构。
A.动态
B.静态
C.线性
D.无结构
答案问询微信：424329

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

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

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

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

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

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

（18）设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为 ()。
A.1和1
B.1和3
C.1和2
D.2和3
答案问询微信：424329

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

（20）在查找过程中，若同时还要做增、删工作，这种查找则称为 ()。
A.静态查找
B.动态查找
C.内查找
D.外查找
答案问询微信：424329

（21）对于二维数组A[4][4]，数组的起始位置LOC(A[0][0])=1000，元素长度为2，则LOC(A[3][3])为()。
A.1000
B.1010
C.1008
D.1020
答案问询微信：424329

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

（23）B+ 树应用在 () 文件系统中。
A.ISAM
B.VSAM
C.顺序
D.散列
答案问询微信：424329

（24）设有n个结点的最佳二叉排序树，对于成功的查找，最少的比较次数为()。
A.( 1 )
B.(log2n)
C.(n)
D.(nlog2n)
答案问询微信：424329

（25）有m个叶结点的哈夫曼树所具有的结点数为 ( )。
A.m
B.m+1
C.2m-1
D.2m
答案问询微信：424329

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

（27）在下列情况中，可称为二叉树的是 ( )。
A.每个结点至多有两棵子树的树
B.哈夫曼树
C.每个结点至多有两棵子树的有序树
D.每个结点只有一棵右子树
答案问询微信：424329

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

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

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

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

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

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

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

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

（36）在下面的叙述中，正确的是 ( )。
A.树的先根遍历序列与其对应的二叉树的前序遍历序列相同
B.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的后序遍历序列相同
D.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
答案问询微信：424329

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

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

（39）线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( )。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
答案问询微信：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）在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是 ( )。
A.r = f-next;
B.r = r-next;
C.f = f-next;
D.f = r-next;
答案问询微信：424329

（44）最佳二叉排序树属于()的数据结构。
A.动态
B.静态
C.线性
D.无结构
答案问询微信：424329

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

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

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

（48）对关键码序列 28 , 16 , 32, 12, 60, 2, 5, 72 快速排序 ( 从小到大序 ) , 一次划分的结果为 ()。
A.( 2 , 5 , 12 , 16 ) 28 ( 60 , 32 , 72 )
B.( 5 , 16 , 2 , 12 ) 28 ( 60 , 32 , 72 )
C.( 2 , 16 , 12 , 5 ) 28 ( 60 , 32 , 72 )
D.( 5 , 16 , 2 , 12 ) 28 ( 32 , 60 , 72 )
答案问询微信：424329

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

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

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

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

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

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

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

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

（9）文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。
答案问询微信：424329

（10）为了方便的插入和删除数据，可以使用双向链表来存放数据。
答案问询微信：424329

（11）数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。
答案问询微信：424329

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

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

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

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

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

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

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

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

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

（21）文件系统采用索引结构是为了节省存储空间。
答案问询微信：424329

（22）栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
答案问询微信：424329

（23）给定一棵树，可以找到唯一的一棵二叉树与之对应。
答案问询微信：424329

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

（25）树与二叉树是两种不同的树形结构。
答案问询微信：424329

（26）最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
答案问询微信：424329

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

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

（29）N个结点的二叉排序树有多种，其中树的高度为最小的二叉排序树是最佳的。
答案问询微信：424329

（30）将森树转成二叉树，根结点没有左子树。
答案问询微信：424329

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

（32）归并排序的辅助存储空间代价为O(1 )。
答案问询微信：424329