东师数据结构17春在线作业答案
东师数据结构17春在线作业2一、单选题：
1.采用邻接表存储的图的广度优先遍历类似于二叉树的( )。 (满分:3)
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
2.若一组记录的排序码为 { 46,79,56,38,40,84 }，则利用堆排序的方法建立的初始堆为( )。 (满分:3)
A. 79
46
56
38
40
84
B. 84
79
56
38
40
46
C. 84
79
56
46
40
38
D. 84
56
79
40
46
38
3.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？( ) (满分:3)
A. k-1次
B. k次
C. k+1次
D. k(k+1)/2次
4.空串与空格串是相同的，这种说法( ) 。 (满分:3)
A. 正确
B. 可能正确
C. 不正确
D. 可能不正确
5.广义表(( a , b , c , d ) ) 的表头是( )。 (满分:3)
A. a
B.( )
C.( a
b
c
d )
D.( b
c
d )
6.AVL树中任一结点的平衡因子的绝对值都应小于等于( )。 (满分:3)
A. 0
B. 1
C. 2
D. 3
7.下列四个序列中，哪一个是堆( ) 。 (满分:3)
A. 75
65
30
15
25
45
20
10
B. 75
65
45
10
30
25
20
15
C. 75
45
65
30
15
25
20
10
D. 75
45
65
10
25
30
20
15
8.n个结点的线索二叉树上含有的线索数为( )。 (满分:3)
A. n-1
B. n
C. n +1
D. 2n
9.存放在外存中的数据的组织结构是( )。 (满分:3)
A. 数组
B. 表
C. 文件
D. 链表
10.下面说法不正确的是( )。 (满分:3)
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表常采用链接存储结构
D. 广义表可以是一个多层次的结构
11.B+ 树应用在( ) 文件系统中。 (满分:3)
A. ISAM
B. VSAM
C. 顺序
D. 散列
12.ISAM文件和VSAM文件属于( )。 (满分:3)
A. 索引非顺序文件
B. 索引顺序文件
C. 顺序文件
D. 散列文件
13.如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是( )。 (满分:3)
A. 顺序查找
B. 折半查找
C. 分块查找
D. 基于属性的查找
14.平衡的二叉排序树(AVL树)属于( )的数据结构。 (满分:3)
A. 动态
B. 静态
C. 线性
D. 无结构
15.一个有n个结点的图，连通分量的个数最多为( )。 (满分:3)
A. 0
B. 1
C. n-1
D. n
16.线索二叉树是一种( ) 结构。 (满分:3)
A. 逻辑
B. 物理
C. 逻辑和存储
D. 线性
17.设s1 = "abc" ，则strlen(s1) = ( )。 (满分:3)
A. 0
B. 1
C. 2
D. 3
18.线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 (满分:3)
A. 必须是连续的
B. 部分地址必须是连续的
C. 一定是不连续的
D. 连续或不连续都可以
19.下面的排序方法中，辅助空间为O( n ) 的是( )。 (满分:3)
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
20.四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是( )。 (满分:3)
A. U
B. V
C. X
D. Y
三、判断题：
1.通常使用队列来处理函数或过程的调用。 (满分:2)
A. 错误
B. 正确
2.数组是同类型值的集合。 (满分:2)
A. 错误
B. 正确
3.堆是满二叉树。 (满分:2)
A. 错误
B. 正确
4.将一棵树转成二叉树，根结点没有左子树。 (满分:2)
A. 错误
B. 正确
5.对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。 (满分:2)
A. 错误
B. 正确
6.哈夫曼树的结点个数不能是偶数。 (满分:2)
A. 错误
B. 正确
7.对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。 (满分:2)
A. 错误
B. 正确
8.二叉树的中序遍历序列中，任意一个结点均处在其左子女结点( 若存在 )的后面。 (满分:2)
A. 错误
B. 正确
9.哈希表(散列表)的结点中只包含数据元素自身的信息，不包含任何指针。 (满分:2)
A. 错误
B. 正确
10.链表中的表头结点仅起到标识的作用。 (满分:2)
A. 错误
B. 正确
11.数据的逻辑结构是指数据的各数据项之间的逻辑关系。 (满分:2)
A. 错误
B. 正确
12.二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。 (满分:2)
A. 错误
B. 正确
13.结点(数据元素)是数据的最小单位。 (满分:2)
A. 错误
B. 正确
14.二叉树的后序遍历序列中，任意一个结点均处在其子女结点( 若存在)的后面。 (满分:2)
A. 错误
B. 正确
15.树与二叉树是两种不同的树形结构。 (满分:2)
A. 错误
B. 正确
16.负载因子（装填因子）是哈希表(散列表)的一个重要参数，它反映哈希表的填满程度。 (满分:2)
A. 错误
B. 正确
17.在完全二叉树中，若一个结点没有左子女，则它必是树叶。 (满分:2)
A. 错误
B. 正确
18.消除递归不一定需要使用栈。 (满分:2)
A. 错误
B. 正确
19.二维以上的数组其实是一种特殊的广义表。 (满分:2)
A. 错误
B. 正确
20.两个栈共用静态存储空间，对接使用方式减少了空间溢出的可能性。 (满分:2)
A. 错误
B. 正确
数据结构17春在线作业1
一、单选题：
1.算法分析的两个主要方面是( )。 (满分:3)
A. 正确性与健壮性
B. 可读性与可用性
C. 时间复杂度与空间复杂度
D. 数据复杂性与程序复杂性
2.数组A 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A 的地址是( )。 (满分:3)
A. 1165
B. 1170
C. 1175
D. 1180
3.一个栈的入栈序列是a、b、c，则栈的不可能的输出序列是( )。 (满分:3)
A. acb
B. abc
C. bca
D. cab
4.一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。 (满分:3)
A. 不确定
B. 0
C. 1
D. 2
5.在具有n个结点的完全二叉树中，若设根结点的编号为1，则编号为i(i>1)的结点的双亲结点的编号是( )。 (满分:3)
A. 2i
B. 2i+1
C. ?i/2?
D. 不存在
6.下述文件中适合于磁带存储的是( )。 (满分:3)
A. 顺序文件
B. 索引文件
C. 散列文件
D. 多关键字文件
7.设有100个关键字，用折半查找法进行查找时，最大比较次数为( )。 (满分:3)
A. 6
B. 7
C. 25
D. 50
8.在线索二叉树中，p所指结点没有右子树的充要条件是( )。 (满分:3)
A. p->rchild = = NULL
B. p->rtag = = 1
C. p->rtag = = 1且p->rchild = = NULL
D. p->rtag = = 0
9.对于3个结点a、b、c，可构成二叉树的不同形态数为( )。 (满分:3)
A. 3
B. 4
C. 5
D. 6
10.有n个顶点的无向图的边数最多为( )。 (满分:3)
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
11.最佳二叉排序树属于( )的数据结构。 (满分:3)
A. 动态
B. 静态
C. 线性
D. 无结构
12.在一个单链表中，在p所指结点之后插入s所指结点，则执行( )。 (满分:3)
A. s->next = p; p->next = s;
B. s->next = p->next; p->next = s;
C. s->next = p->next; p = s;
D. p->next = s; s->next = p->next;
13.判断线索二叉树中某结点p有右子女的条件是( )。 (满分:3)
A. p->rtag = = 0
B. p->rtag = = 1
C. p ! = NULL
D. p->lchild ! = NULL
14.有n个顶点的无向图的边数最少为( )。 (满分:3)
A. 0
B. 1
C. n-1
D. n
15.广义表A=(a, b,( c, d ) ,(e，( f , g ) ) )，则式子head( tail( head( tail( tail( A ) ) ) ) )的值为( )。 (满分:3)
A.( g )
B.( d )
C. c
D. d
16.n个结点的线索二叉树上含有的线索数为( )。 (满分:3)
A. n-1
B. n
C. n +1
D. 2n
17.从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行( )。 (满分:3)
A. x = top; top = top->next;
B. top = top->next; x = top->data;
C. x = top->data;
D. x = top->data; top = top->next;
18.一个有n个结点的图，连通分量的个数最多为( )。 (满分:3)
A. 0
B. 1
C. n-1
D. n
19.下面说法不正确的是( )。 (满分:3)
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表常采用链接存储结构
D. 广义表可以是一个多层次的结构
20.某二叉树结点的中序序列为DGBAECHF，后序序列为GDBEHFCA，则该二叉树结点的前序序列为( )。 (满分:3)
A. AHFECGDB
B. AHFCEBDG
C. ABDGCEFH
D. BDGAECHF
三、判断题：
1.对n个记录的文件进行直接插入排序，最好情况下的执行时间是O(n)。 (满分:2)
A. 错误
B. 正确
2.栈是实现过程和函数等子程序所必需的结构。 (满分:2)
A. 错误
B. 正确
3.所谓取广义表的表尾就是返回广义表中最后一个元素。 (满分:2)
A. 错误
B. 正确
4.AOV网的含义是以顶点表示活动的网。 (满分:2)
A. 错误
B. 正确
5.非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。 (满分:2)
A. 错误
B. 正确
6.顺序存储方式只能用于存储线性结构。 (满分:2)
A. 错误
B. 正确
7.归并排序的辅助存储空间代价为O(1 )。 (满分:2)
A. 错误
B. 正确
8.采用二叉链表作为存储结构，树的先根遍历和其相应的二叉树的前序遍历的结果是一样的。 (满分:2)
A. 错误
B. 正确
9.必须把一般的树转换成二叉树后才能进行存储。 (满分:2)
A. 错误
B. 正确
10.二叉树的前序遍历序列中，任意一个结点均处在其子女结点( 若存在 )的前面。 (满分:2)
A. 错误
B. 正确
11.中序遍历二叉链表存储的二叉树时，一般要用堆栈；中序遍历中序线索二叉树时，也必须使用堆栈。 (满分:2)
A. 错误
B. 正确
12.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 (满分:2)
A. 错误
B. 正确
13.在指定结点之前插入新结点时，双链表比单链表更方便。 (满分:2)
A. 错误
B. 正确
14.链表中的表头指针与表头结点起到相同的作用。 (满分:2)
A. 错误
B. 正确
15.完全二叉树的存储结构通常采用顺序存储结构。 (满分:2)
A. 错误
B. 正确
16.对一棵二叉排序树按中序方法遍历得到的结点序列是从小到大的序列。 (满分:2)
A. 错误
B. 正确
17.归并排序在任何情况下都比所有简单的排序方法速度快。 (满分:2)
A. 错误
B. 正确
18.连通图的各边权值均不相同，则该图的最小生成树是唯一的。 (满分:2)
A. 错误
B. 正确
19.当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。 (满分:2)
A. 错误
B. 正确
20.无向图的邻接矩阵可用一维数组存储。 (满分:2)
A. 错误
B. 正确
页:
[1]