东北师范《数据结构》》21秋学期在线作业1答卷

admin

数据结构19春在线作业1-0001
试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 60 分)
1.数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是 ( )
A.线性表
B.广义表
C.树形结构
D.图结构
正确资料:

2.插入、删除只能在同一端进行的线性表，称为 ( )。
A.队列
B.循环队列
C.栈
D.循环栈
正确资料

3.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。
A.不发生改变
B.发生改变
C.稍有改变
D.不能确定
正确资料:

4.在k叉树中，度为0的结点称为 ( )。
A.根
B.叶
C.祖先
D.子孙
正确资料:

5.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
A.直接插入排序
B.冒泡排序
C.快速排序
D.直接选择排序
正确资料来自谋学网（www.mouxue.com）

6.下面哪些方法可以判断出一个有向图是否有环（回路）? ()
A.广(宽)度优先遍历
B.拓扑排序
C.求最短路径
D.求关键路径
正确资料:

7.串是一种特殊的线性表，其特殊性体现在 ( )。
A.可以顺序存储
B.数据元素是一个字符
C.可以链接存储
D.数据元素可以是多个字符
正确资料:

8.head指向的带表头结点的单链表为空的判定条件是 ( )。
A.head = = NULL
B.head->next = = head
C.head ! = NULL
D.head->next = = NULL
正确资料来自谋学网（www.mouxue.com）

9.二叉树在线索化后，仍不能有效求解的问题是 ( )。
A.前序线索二叉树中求前序后继
B.中序线索二叉树中求中序前驱
C.中序线索二叉树中求中序后继
D.后序线索二叉树中求后序后继
正确资料来自谋学网（www.mouxue.com）

10.算法分析的两个主要方面是 ( )。
A.正确性与健壮性
B.可读性与可用性
C.时间复杂度与空间复杂度
D.数据复杂性与程序复杂性
正确资料

11.下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。( )
A.二叉排序树
B.哈夫曼树
C.AVL树
D.堆
正确资料来自谋学网（www.mouxue.com）

12.设有100个关键字，用折半查找法进行查找时，最大比较次数为 ()。
A.6
B.7
C.25
D.50
正确资料:

13.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左子女
D.任一结点无右子女
正确资料:

14.n个结点的线索二叉树上含有的线索数为 ( )。
A.n-1
B.n
C.n +1
D.2n
正确资料

15.广义表 (( a , b , c , d ) ) 的表头是 ()。
A.a
B.( )
C.( a , b , c , d )
D.( b , c , d )
正确资料

16.将一个A [1..100, 1..100] 的三对角矩阵，按行优先次序存入一维数组B[1..298] 中，A中元素A [66, 65] 在数组B中的位置K为 () 。
A.193
B.195
C.197
D.199
正确资料:

17.在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是 ( )。
A.r = f->next;
B.r = r->next;
C.f = f->next;
D.f = r->next;
正确资料

18.求图的最小(代价)生成树问题，考虑的是下面的哪一种图 ()。
A.无向图
B.有向图
C.带权的无向图
D.带权的有向图
正确资料

19.一个队列的入队序列是a、b、c、d，则队列的输出序列是 ( )。
A.abcd
B.dcba
C.adcb
D.cbda
正确资料:

20.一个有向无环图的拓扑排序序列 () 是唯一的。
A.一定
B.不一定
C.可能
D.三者均不对
正确资料:

二、资料来源：谋学网（www.mouxue.com） (共 20 道试题,共 40 分)
21.数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。
资料:正确

22.AOV网的含义是以顶点表示活动的网。
资料:正确

23.在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
资料:正确

24.循环链表不是线性表。
资料:错误

25.分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。
资料:正确

26.最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
资料:正确

27.完全二叉树一定存在度为1的结点。
资料:错误

28.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
资料:错误

29.链表中的表头指针与表头结点起到相同的作用。
资料:错误

30.链接存储结构属动态存储方式。
资料:正确

31.取顺序表的第i个元素的时间与i的大小无关。
资料:正确

32.在指定结点之前插入新结点时，双链表比单链表更方便。
资料:正确

33.若哈希表(散列表)的负载因子α < l，则可避免冲突的产生。
资料:错误

34.二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。
资料:正确

35.若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列3, 2, 5, 6, 4, 1。
资料:正确

36.数据的逻辑结构是指数据的各数据项之间的逻辑关系。
资料:错误

37.一个有向图的邻接表和逆邻接表中结点的个数可能不等。
资料:错误

38.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
资料:正确

39.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
资料:错误

40.任何一个递归过程都可以转换成非递归过程。
资料:正确