东大21秋学期学期《数据结构Ⅱ》在线平时作业1[答案]

东大21秋学期学期《数据结构Ⅱ》在线平时作业1[答案]答案

《数据结构Ⅱ》在线平时作业1

试卷总分:100 得分:100

一、单选题 (共 20 道试题,共 100 分)

1.判定“带头结点的链队列为空”的条件是

正确答案:-----

A.Q.front==NULL

B.Q.rear==NULL

C.Q.front==Q.rear

D.Q.front!=Q.rear

正确答案:-----

2.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为

A.O(n) O(n)

B.O(n) O(1)

C.O(1) O(n)

D.O(1) O(1)

正确答案:-----

3.由同一关键字集合构造的各棵二叉排序树

A.其形态不一定相同，但平均查找长度相同

B.其形态不一定相同，平均查找长度也不一定相同

C.其形态均相同，但平均查找长度不一定相同

D.其形态均相同，平均查找长度也都相同

正确答案:-----

4.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为

A.(19，23，56，34，78，67，88，92)

B.(23，56，78，66，88，92，19，34)

C.(19，23，34，56，67，78，88，92)

D.(19，23，67，56，34，78，92，88)

正确答案:-----

5.可有效提高次关键字查找效率的文件是

A.顺序文件

B.倒排文件

C.散列文件

D.VSAM文件

正确答案:-----

6.数据结构中所定义的数据元素，是用于表示数据的

A.最小单位

B.最大单位

C.基本单位

D.不可分割的单位

正确答案:-----

7.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为

A.O(0)

B.O(1)

C.O(n)

D.O(n2)

正确答案:-----

8.若是有向图的一条边，则称

A.vi邻接于vj

B.vj邻接于vi

C.vi和vj相互邻接

D.vi与vj­不相邻接

正确答案:-----

9.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为

正确答案:-----

A.f,c,b

B.f,d,b

正确答案:-----

C.g,c,b

D.g,d,b

正确答案:-----

10.高度为5的完全二叉树中含有的结点数至少为

A.16

B.17

C.31

D.32

正确答案:-----

11.含n个关键字的二叉排序树的平均查找长度主要取决于

A.关键字的个数

B.树的形态

C.关键字的取值范围

D.关键字的数据类型

正确答案:-----

12.队列和栈的主要区别是

A.逻辑结构不同

B.存储结构不同

C.所包含的运算个数不同

D.限定插入和删除的位置不同

正确答案:-----

13.已知散列表的存储空间为T[0..21]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是

A.T[2]

B.T[4]

C.T[8]

D.T[10]

正确答案:-----

14.根据数据元素的关键字直接计算出该元素存储地址的存储方法是

A.顺序存储方法

B.链式存储方法

C.索引存储方法

D.散列存储方法

正确答案:-----

15.下列关键字序列中，构成小根堆的是

A.{84，46，62，41，28，58，15，37}

B.{84，62，58，46，41，37，28，15}

C.{15，28，46，37，84，41，58，62}

D.{15，28，46，37，84，58，62，41}

正确答案:-----

16.ISAM文件和VSAM文件的区别之一是

A.前者是索引顺序文件，后者是索引非顺序文件

B.前者只能进行顺序存取，后者只能进行随机存取

C.前者建立静态索引结构，后者建立动态索引结构

D.前者的存储介质是磁盘，后者的存储介质不是磁盘

正确答案:-----

17.适宜进行批量处理的文件类型是

A.顺序文件

B.索引顺序文件

C.散列文件

D.多关键字文件

正确答案:-----

21.下面关于线性表的叙述中，错误的是

A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链接存储，不必占用一片连续的存储单元。

D.线性表采用链接存储，便于插入和删除操作。

正确答案:-----

19.某带头结点的单链表的头指针为head，判定该链表为非空的条件是

正确答案:-----

A.head==NULL

正确答案:-----

B.head->next==NULL

正确答案:-----

C.head!=NULL

正确答案:-----

D.head->next!=NULL

正确答案:-----

20.计算机识别、存储和加工处理的对象被统称为

A.数据

B.数据元素

C.数据结构

D.数据类型

正确答案:-----

东大21秋学期学期《数据结构Ⅱ》在线平时作业1[答案]历年参考题目如下：

19秋学期《数据结构Ⅱ》在线平时作业1

试卷总分:100 得分:100

一、单选题 (共 20 道试题,共 100 分)

1.高度为5的完全二叉树中含有的结点数至少为

A.32

B.31

C.17

D.16

2.通常将链串的结点大小设置为大于1是为了

A.提高存储密度

B.提高串匹配效率

C.便于插入操作

D.便于删除操作

3.在VSAM文件的控制区间中，记录的存储方式为

A.有序顺序

B.有序链接

C.无序顺序

D.无序链接

4.在一棵高度为k的满二叉树中，结点总数为

A.2k-1

B.2k-1

C.2k

D.ëlog2kû+1

5.已知广义表的表头为a，表尾为(b,c)，则此广义表为

A..(a,b,c)

B..(a,(b,c))

C..((a,b,c))

D..((a),b,c)

6.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为

A.8

B.5

C.18

D.11

7.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为

A.插入排序

B.归并排序

C.堆排序

D.冒泡排序

8.栈是一种操作受限的线性结构，其操作的主要特征是

A.进优于出

B.后进先出

C.出优于进

D.先进先出

9.下面的叙述不正确的是

A.线性表在顺序存储时，查找第i个元素的时间同i的值无关

B.线性表在顺序存储时，查找第i个元素的时间同i 的值成反比

C.线性表在链式存储时，查找第i个元素的时间同i的值无关

D.线性表在链式存储时，查找第i个元素的时间同i的值成正比

10.n个顶点的有向完全图中含有向边的数目最多为

A.n(n-1)/2

B.n(n-1)

C.n-1

D.n

11.采用ISAM或VSAM组织的文件是

A.顺序文件

B.索引顺序文件

C.索引非顺序文件

D.散列文件

12.除第一层外，满二叉树中每一层结点个数是上一层结点个数的

A.3倍

B.2倍

C.1倍

D.1/2倍

13.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是

A.队列

B.树

C.栈

D.图

14.若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为

A.én/(m-1)ù-1

B.ën/mû-1

C.é(n-1)/(m-1)ù

D.n-1

15.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是

A.tail(head(LS))

B.head(tail(tail(head(LS))))

C.head(tail(head(tail(LS))))

D.head(tail(LS))

16.算法的时间复杂度主要取决于

A.难度

B.问题的规模

C.待处理数据的初态

D.A和B

17.已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有

A.以上答案都不对

B.dacb

C.cadb

D.bdac

18.设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是

A.D，C，B，A

B.D，A，B，C

C.A，C，D，B

D.A，B，C，D

19.假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为

A.n+l

B.n+2

C.n-1

D.n

20.n个顶点的强连通图中至少含有

A.n条有向边

B.n(n-1)条有向边

C.n(n-1)/2条有向边

D.n-1条有向边