东大19秋学期《数据结构Ⅱ》在线平时作业【满分答案】

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条有向边

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

试卷总分:100  得分:100

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

1.数据的四种基本存储结构是指

A.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构

B.顺序存储结构、链式存储结构、树型存储结构、图型存储结构

C.顺序存储结构、索引存储结构、链式存储结构、散列存储结构

D.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构

2.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是

A.4，3，2，1，5，6

B.3，2，4，1，6，5

C.2，4，3，1，5，6

D.2，3，5，1，6，4

3.有关二叉树下列说法正确的是

A.二叉树的度为2

B.二叉树中至少有一个结点的度为2

C.二叉树中任何一个结点的度都为2

D.一棵二叉树的度可以小于2

4.算法分析的目的是

A.鉴别算法的可读性

B.辨别数据结构的合理性

C.评价算法的效率

D.研究算法中输入与输出的关系

5.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为

A.X的左子树中最右结点

B.X的左子树中最右叶结点

C.X的右子树中最左的结点

D.X的双亲

6.在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作

A.s->next=p; q->next=s

B.s->next=p->next;p->next=s;

C.q->next=s;s->next=p;

D.p->next=s;s->next=q;

7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为

A.49

B.48

C.1

D.0

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

A.g,d,b

B.g,c,b

C.f,d,b

D.f,c,b

9.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为

A.O(n logn)

B.O(n)

C.O(logn)

D.O(1)

10.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是

A.4231

B.4213

C.4132

D.1234

11.树的先根序列等同于与该树对应的二叉树的

A.层序序列

B.后序序列

C.先序序列

D.中序序列

12.若<vi, vj>是有向图的一条边，则称

A.vj邻接于vi

B.vi邻接于vj

C.vi和vj相互邻接

D.vi与vj&shy;不相邻接

13.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为

A.6

B.5

C.17

D.16

14.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为

A.O(n+e)

B.O(n2)

C.O(n)

D.O(e)

15.导致栈上溢的操作是

A.栈空时执行的出栈

B.栈空时执行的入栈

C.栈满时执行的出栈

D.栈满时执行的入栈

16.在下列存储形式中，哪一个不是树的存储形式

A.顺序存储表示法

B.孩子链表表示法

C.孩子兄弟表示法

D.双亲表示法

17.文件中，主关键字能唯一标识

A.一组记录

B.一个记录

C.一个类型

D.一个文件

18.下面的说法中正确的是

(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。

(2)按二叉树定义，具有三个节点的二叉树共有6种。

A.(1)，(2)都错

B.(1)，(2)

C.(2)

D.(1)

19.设给定权值总数有n 个，其哈夫曼树的结点总数为

A.不确定

B.2n-1

C.2n+1

D.2n

20.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t  到s。若字符串S=&Prime;SCIENCESTUDY&Prime;，则调用函数Scopy(P,Sub(S,1,7))后得到

A.S=&Prime;STUDY&Prime;

B.S=&Prime;SCIENCE&Prime;

C.P=&Prime;STUDY&Prime;

D.P=&Prime;SCIENCE&Prime;

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

试卷总分:100  得分:100

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

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

A.顺序存储方法

B.链式存储方法

C.索引存储方法

D.散列存储方法

2.数据元素及其关系在计算机存储器内的表示，称为数据的

A.非线性结构

B.逻辑结构

C.线性结构

D.存储结构

3.下面哪一方法可以判断出一个有向图是否有回路

A.深度优先遍历

B.求最短路径

C.求关键路径

D.A和C

4.BFS算法可用来解决单源最短路径问题的条件是当各边上的权值

A.均相等

B.均互不相等

C.任意值

D.不一定相等

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

A.数据结构

B.数据类型

C.数据元素

D.数据

6.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1  则T中的叶子数为

A.8

B.7

C.6

D.5

7.一棵完全二叉树上有1001个结点，其中叶子结点的个数是

A.以上答案都不对

B.500

C.254

D.250

8.设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是

s -> next = p -> next;    p -> next = s;

t = p -> data;     p -> data = s -> data;    s ->data = t;

A.结点p与结点s的数据域互换

B.在结点p之前插入结点s

C.在p所指结点的元素之后插入元素

D.在p所指结点的元素之前插入元素

9.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是

A.(rear-front)%m= =m-1

B.(rear-front)%m= =1

C.front= =(rear+1)%m

D.front= =rear

10.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为

A.62

B.41

C.23

D.21

11.下列说法正确的是

(1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索

(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前

(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值

A.前面的可选答案都不对

B.(1)(3)

C.(1)(2)(3)

D.(1)(2)

12.下列序列中，不构成堆的是

A.（1，2，5，3，4，6，7，8，9，10）

B.（1，2，3，4，10，9，8，7，6，5）

C.（10，9，8，7，3，5，4，6，2）

D.（10，5，8，4，2，6，7，1，3）

13.以下说法不正确的是

A.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

B.有向图的遍历不可采用广度优先搜索

C.无向图中的极大连通子图称为连通分量

D.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

14.无向图中一个顶点的度是指图中

A.通过该顶点的简单路径数

B.通过该顶点的回路数

C.与该顶点连通的顶点数

D.与该顶点相邻接的顶点数

15.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为

A.(rear-front+n)％n

B.(rear-front)％n

C.(rear-front-1)％n

D.(front-rear+1)％n

16.十字链表的三元组表是稀疏矩阵的一种

A.顺序存储结构

B.链式存储结构

C.索引存储结构

D.散列存储结构

17.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为

A.O(n logn)

B.O(n)

C.O(logn)

D.O(1)

18.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为

A.(rear-length+m-1)％m

B.(rear-length+m+1)％m

C.(rear-length+m)％m

D.(rear-length)％m

19.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为

A.数组的元素必须从左到右顺序排列

B.数组的元素处在行和列两个关系中

C.数组的元素之间存在次序关系

D.数组是多维结构，内存是一维结构

20.在分块索引的在顺序表中查找，算法中采用的最佳技术是

A.贪心法

B.穷举法

C.分治法

D.分支限界法