![[奥鹏]22年春北交《数据结构》在线作业一[答案]](/uploads/allimg/240109/7dde259a89d7d7e8ab66753dd7d3c08a.jpg)
正确答案:-----
正确答案:-----
试卷总分:100 得分:100
一、单选题 (共 38 道试题,共 95 分)
1.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序.
A.插入
B.交换
C.选择
D.归并
正确答案:-----
2.线性链表不具有的特点是（）。
A.随机访问
B.不必事先估计所需存储空间大小
C.插入与删除时不必移动元素
D.所需空间与线性表长度成正比
正确答案:-----
3.下列那种排序需要的附加存储开销最大（）。
A.快速排序
B.堆排序
C.归并排序
D.插入排序
正确答案:-----
4.线索化二叉树中某结点D，没有左孩子的主要条件是（）。
正确答案:-----
A.D->Lchild=Null
正确答案:-----
B.D->ltag=1
正确答案:-----
C.D->Rchild=Null
正确答案:-----
D.D->ltag=0
正确答案:-----
5.顺序表中逻辑上相邻的节点其物理位置也（ ）。
A.一定相邻
B.不必相邻
C.按某种规律排列
D.无要求
正确答案:-----
6.图的深度优先遍历类似于二叉树的（ ）。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
正确答案:-----
7.广义表（（a）,a）的表头是（）。
A.a
B.b
C.(a)
D.((a))
正确答案:-----
8.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。
A.e
B.2e
C.n*n－e
D.n*n－2e
正确答案:-----
9.无向图的邻接矩阵是一个 ( )。
A.对称矩阵
B.零矩阵
C.上三角矩阵
D.对角矩阵
正确答案:-----
10.下列数据结构中，能用折半查找的是( )。
A.顺序存储的有序线性表
B.线性链表
C.二叉链表
D.有序线性链表
正确答案:-----
11.从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。
A.原树高度加1
B.原树高度减1
C.原树高度
D.不确定
正确答案:-----
12.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。
A.O（nlog2e）
B.O（n+e）
C.O(n*e)
D.O(n*n)
正确答案:-----
13.若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用( )存储方式最节省时间。
A.顺序表
B.单链表
C.双链表
D.单循环链表
正确答案:-----
14.关于有向图的邻接表和逆邻接表表示法，下列结论正确的是 （）。
A.用邻接表表示法计算入度比较方便
B.用邻接表表示法计算入度和出度都方便
C.用逆邻接表表示法计算入度和出度都不方便
D.用逆邻接表表示法计算入度比计算出度方便
正确答案:-----
15.如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。下列选项中，（）就是不稳定的排序方法。
A.起泡排序
B.归并排序
C.直接插入法排序
D.简单选择排序
正确答案:-----
16.判定一个顺序栈（最多元素为m个）为空的条件是（ ）。
A.top＝＝0
B.top＝＝m
C.top!＝0
D.top!＝m
正确答案:-----
17.下列数据组织形式中，（ ）的各个结点可以任意邻接。
A.集合
B.树形结构
C.线性结构
D.图状结构
正确答案:-----
21.具有2000个节点的二叉树，其高度至少为（）。
A.9
B.10
C.11
D.12
正确答案:-----
19.队列的插入操作是在（ ）进行。
A.队首
B.队尾
C.队前
D.队后
正确答案:-----
20.如果一个树中，结点A有3个兄弟，而且B为A的双亲，南开在线作业答案，则B的度为（ ）。
正确答案:-----
A.1
B.3
C.4
D.5
正确答案:-----
21.下列关于栈的叙述正确的是（ ）。
A.栈是非线性结构
B.栈是一种树状结构
C.栈具有先进先出的特征
D.栈具有后进先出的特征
正确答案:-----
22.对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。
A.O(log2n)
B.O(n*n)
C.O(ne)
D.O(elog2e)
正确答案:-----
23.在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（）。
A.n/m
B.m/n
C.n/(n+m)
D.m/(n+m)
正确答案:-----
24.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A.空或只有一个结点高度等于其结点数
B.任一结点无左孩子
C.任一结点无右孩子
25.设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（）。
A.3，2，5，6，4，1
B.1，5，4，6，2，3
C.2，4，3，5，1，6
D.4，5，3，6，2，1
正确答案:-----
26.对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）。
正确答案:-----
A.DBFEAC
正确答案:-----
B.DFEBCA
正确答案:-----
C.BDFECA
正确答案:-----
D.BDEFAC
正确答案:-----
27.非空的循环单链表head的尾节点（由p所指向）满足（ ）。
正确答案:-----
A.p->next=NULL
B.p=NULL
C.p->next=head
D.p=head
正确答案:-----
28.计算机的算法必须具备输入，输出和（ ）五个特性。
A.可行性，可移植性和可扩充性
B.可行性，确定性和有穷性
C.确定性，有穷性和稳定性
D.易读性，稳定性和安全性
正确答案:-----
29.树最适合用来表示（ ）。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
正确答案:-----
30.顺序查找法适合于存储结构为（）的线性表。
A.散列表
B.顺序存储或链接存储
C.压缩存储
D.索引存储
正确答案:-----
31.设有1000个元素，用折半查找时，最大比较次数是（）。
A.1
B.7
C.10
D.25
正确答案:-----
32.若从二叉树的任一节点出发到根的路径上所经过的节点序列按其关键字有序，则该二叉树是（ ）。
A.二叉排序树
B.哈夫曼树
C.堆
D.AVL树
正确答案:-----
