东师数据结构17春在线作业1答案
东师数据结构17春在线作业1一、单选题:【20道,总分:60分】
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
二、判断题:【20道,总分:40分】
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]