东北师范大学《数据结构》22春在线作业1-0004
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 60 分)
1.数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
A.直接选择排序
B.冒泡排序
C.直接插入排序
D.堆排序
答案:C
2.下面关于算法说法错误的是（）。
A.算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C.算法的可行性是指指令不能有二义性
D.以上几个都是错误的
答案:D
3.判断线索二叉树中某结点p有左子女的条件是 ( )。
A.p ! = NULL
B.p->lchild ! = NULL
C.p->ltag = = 0
D.p->ltag = = 1
答案:C
4.采用邻接表存储的图的深度优先遍历类似于二叉树的 ()。
A.前序遍历
B.中序遍历
C.后序遍历
D.层次遍历
答案:A
5.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。
A.不发生改变
B.发生改变
C.稍有改变
D.不能确定
答案:A
6.对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是 ()。
A.直接插入排序
B.冒泡排序
C.快速排序
D.归并排序
答案:D
7.有n个顶点的无向连通图的边数最少为 ()。
A.n/2
B.n-1
C.n
D.n+1
8.设二叉树有n个结点且根结点的层数为0，则二叉树的高度为 ( )。
A.n-1
B.élog2(n+1)ù -1
C.?log2n?
D.不确定
9.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
A.直接插入排序
B.冒泡排序
C.快速排序
D.直接选择排序
10.“堆积”问题是由于()引起的。
A.同义词之间发生冲突
B.散列函数
C.不同的同义词子表结合在一起
D.散列表“溢出”
11.数组A[6,7] 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5] 的地址是 ()。
A.1165
B.1170
C.1175
D.1180
12.下列说法不正确的是 ()。
A.图的遍历是从给定的源点出发每个顶点仅被访问一次
B.遍历的基本方法有两种：深度优先遍历和广度优先遍历
C.图的深度优先遍历不适用于有向图
D.图的深度优先遍历是一个递归过程
13.下述文件中适合于磁带存储的是 ()。
A.顺序文件
B.索引文件
C.散列文件
D.多关键字文件
14.递归过程的实现需用到 ( )。
A.线性表
B.链表
C.栈
D.队列
15.存放在外存中的数据的组织结构是 ()。
A.数组
B.表
C.文件
D.链表
16.从一个栈顶指针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;
17.若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列()。
A.存在
B.不存在
C.不一定存在
D.可能不存在
18.若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为 ( )。
A.10
B.16
C.31
D.32
19.AVL树中任一结点的平衡因子的绝对值都应小于等于 ()。
A.0
B.1
C.2
D.3
20.对于二维数组A[4][4]，数组的起始位置LOC(A[0][0])=1000，元素长度为2，则LOC(A[3][3])为()。
A.1000
B.1010
C.1008
D.1020
二、判断题 (共 20 道试题,共 40 分)
21.完全二叉树的存储结构通常采用顺序存储结构。
22.对n个记录的文件进行直接插入排序，最好情况下的执行时间是O(n)。
23.在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
24.在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下面。
25.对磁带机而言，ISAM是一种方便的文件组织方法。
26.文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。
27.二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
28.任何无向图都存在生成树。
29.广义表的取表尾运算，其结果仍是一个广义表。
30.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
31.最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
32.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
33.程序一定是算法。
34.堆是满二叉树。
35.负载因子（装填因子）是哈希表(散列表)的一个重要参数，它反映哈希表的填满程度。
36.两个栈共用静态存储空间，对接使用方式也存在空间溢出问题。
37.数据的逻辑结构是指数据的各数据项之间的逻辑关系。
38.带权的连通无向图的最小(代价)生成树必是唯一的。
39.将森树转成二叉树，根结点没有左子树。
40.哈希函数越复杂越好，因为这样随机性好，冲突概率小。
数据结构》22春在线作业2-0003
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 60 分)
1.从一个栈顶指针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;
答案:D
2.在下述几种排序方法中，不稳定的排序方法是 ()。
A.直接插入排序
B.冒泡排序
C.直接选择排序
D.归并排序
答案:C
3.在队列中存取数据的原则是 ( )。
A.先进先出
B.后进先出
C.先进后出
D.随意进出
答案:A
4.“堆积”问题是由于()引起的。
A.同义词之间发生冲突
B.散列函数
C.不同的同义词子表结合在一起
D.散列表“溢出”
答案:C
5.将一个A [1..100, 1..100] 的三对角矩阵，按行优先次序存入一维数组B[1..298] 中，A中元素A [66, 65] 在数组B中的位置K为 () 。
A.193
B.195
C.197
D.199
答案:B
6.head指向的带表头结点的单链表为空的判定条件是 ( )。
A.head = = NULL
B.head->next = = head
C.head ! = NULL
D.head->next = = NULL
答案:D
7.有n个顶点的有向图的边数最多为 ()。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
8.对于3个结点a、b、c，可构成不同的二叉树的棵数为 ( )。
A.24
B.28
C.30
D.32
9.设F是一个森林， B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有 ( ) 个。
A.n-1
B.n
C.n +1
D.n+2
10.若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为 ( )。
A.10
B.16
C.31
D.32
11.顺序存储结构的优点是( )。
A.存储密度大
B.插入运算方便
C.删除运算方便
D.结构可动态变化
12.数组A[6,7] 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5] 的地址是 ()。
A.1165
B.1170
C.1175
D.1180
13.一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。
A.不确定
B.0
C.1
D.2
14.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A.附加文件
B.按关键字大小排序
C.按记录输入先后排序
D.连续排序
15.有n个顶点的无向图的边数最少为 ()。
A.0
B.1
C.n-1
D.n
16.在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。
A.希尔排序
B.插入排序
C.归并排序
D.选择排序
17.采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A.前序遍历
B.中序遍历
C.后序遍历
D.层次遍历
18.最佳二叉排序树属于()的数据结构。
A.动态
B.静态
C.线性
D.无结构
19.有m个叶结点的哈夫曼树所具有的结点数为 ( )。
A.m
B.m+1
C.2m-1
D.2m
20.在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是 ()。
A.直接插入排序
B.快速排序
C.直接选择排序
D.归并排序
二、判断题 (共 20 道试题,共 40 分)
21.N个结点的二叉排序树有多种，其中树的高度为最小的二叉排序树是最佳的。
22.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插人、删除等操作。
23.二叉树中每个结点至多有两个子结点，而对一般的树则无此限制。因此，二叉树是树的特殊情形。
24.在中序线索二叉树中，每一非空的线索均指向其祖先结点。
25.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。
26.循环队列通常用指针来实现队列的头尾相接。
27.完全二叉树的存储结构通常采用顺序存储结构。
28.内部排序要求数据一定要以顺序方式进行存储。
29.结点(数据元素)是数据的最小单位。
30.在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
31.存放在磁盘、磁带上的文件，既可以是顺序文件，也可以是索引结构或其他结构类型的文件。
32.数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。
33.哈希表(散列表)的平均查找长度与处理冲突的方法无关。
34.一棵哈夫曼树的带权 ( 外部 ) 路径长度等于其中所有分支结点的权值之和。
35.需要借助于一个队列来实现DFS算法。
36.连通图的各边权值均不相同，则该图的最小生成树是唯一的。
37.串只能按顺序存储方式进行存储。
38.倒排文件是对次关键字建立索引。
39.对一棵二叉树进行层次次序遍历时，应借助于一个栈。
40.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
