21秋东北大学《数据结构ⅡX》在线平时作业123【标准答案】

《数据结构Ⅱ》在线平时作业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.若<vi, vj>是有向图的一条边，则称

A.vi邻接于vj

B.vj邻接于vi

C.vi和vj相互邻接

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

答案:

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..18]，散列函数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.散列文件奥鹏东大答案请进：opzy.net或请联系微信：1095258436

D.多关键字文件

答案:

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

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.数据类型

答案:

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

试卷总分:100  得分:100

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

1.判断两个串大小的基本准则是

A.两个串长度的大小

B.两个串中首字符的大小

C.两个串中大写字母的多少

D.对应的第一个不等字符的大小

答案:

2.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为

A.ABCDEF

B.ABCEFD

C.ABFCDE

D.ABCDFE

答案:

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

A.索引非顺序文件

B.顺序文件

C.索引顺序文件

D.散列文件

答案:

4.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用

A.深度优先搜索算法

B.广度优先搜索算法

C.求最小生成树的prim算法

D.拓扑排序算法

答案:

5.链栈与顺序栈相比，比较明显的优点是

A.插入操作更加方便

B.删除操作更加方便

C.不会出现下溢的情况

D.不会出现上溢的情况

答案:

6.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为

A.n-1

B.n

C.n+l

D.2n

答案:

7.一棵树高为K的完全二叉树至少的结点是

A.2k &ndash;1

B.2k-1 &ndash;1

C.2k-1

D.2k

答案:

8.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是

A.2

B.3

C.5

D.6

答案:

9.当采用分快查找时，数据的组织方式为

A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D.数据分成若干块，每块（除最后一块外）中数据个数需相同

答案:

10.抽象数据类型的三个组成部分分别为

A.数据对象、数据关系和基本操作

B.数据元素、逻辑结构和存储结构

C.数据项、数据元素和数据类型

D.数据元素、数据结构和数据类型

答案:

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

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

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

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

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

答案:

12.设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是

A.8

B.3

C.5

D.9

答案:

13.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是

A.G中有弧<Vi，Vj>

B.G中有一条从Vi到Vj的路径

C.G中没有弧<Vi,Vj>

D.G中有一条从Vj到Vi的路径

答案:

14.在待排关键字序列基本有序的前提下，效率最高的排序方法是

A.直接插入排序

B.快速排序

C.直接选择排序

D.归并排序

答案:

15.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是

A.树的后根遍历与其对应的二叉树的后根遍历相同

B.树的后根遍历与其对应的二叉树的中根遍历相同

C.树的先根遍历与其对应的二叉树的中根遍历相同

D.以上都不对

答案:

16.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为

A.4

B.5

C.8

D.9

答案:

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

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

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

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

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

答案:

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

A.n-1

B.&euml;n/m&ucirc;-1

C.&eacute;(n-1)/(m-1)&ugrave;

D.&eacute;n/(m-1)&ugrave;-1

答案:

19.在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是

A.LL型

B.LR型

C.RL型

D.RR型

答案:

20.二叉树中第5层上的结点个数最多为

A.8

B.15

C.16

D.32

答案:

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

试卷总分:100  得分:100

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

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

A.O(n)

B.O(e)

C.O(n+e)

D.O(n2)

答案:

2.索引非顺序文件的特点是

A.主文件无序，索引表有序

B.主文件有序，索引表无序

C.主文件有序，索引表有序

D.主文件无序，索引表无序

答案:

3.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为

A.470

B.471

C.472

D.473

答案:

4.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是

A.p=p->next;

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

C.p->next=p;

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

答案:

5.引入二叉线索树的目的是

A.加快查找结点的前驱或后继的速度

B.为了能在二叉树中方便的进行插入与删除

C.为了能方便的找到双亲

D.使二叉树的遍历结果唯一

答案:

6.一棵树高为K的完全二叉树至少的结点是

A.2k &ndash;1

B.2k-1 &ndash;1

C.2k-1

D.2k

答案:

7.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是

A.分块查找

B.顺序查找

C.二分查找

D.散列查找

答案:

8.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是

A.1

B.2

C.3

D.4

答案:

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

A.5

B.6

C.16

D.17

答案:

10.在长度为n的顺序表中删除第i个元素(1&le;i&le;n)时，元素移动的次数为

A.n-i+1

B.i

C.i+1

D.n-i

答案:

11.从逻辑上可以把数据结构分为两大类，即

A.动态结构、静态结构

B.顺序结构、链式结构

C.线性结构、非线性结构

D.初等结构、构造型结构

答案:

12.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用

A.深度优先搜索算法

B.广度优先搜索算法

C.求最小生成树的prim算法

D.拓扑排序算法

答案:

13.为便于判别有向图中是否存在回路，可借助于

A.广度优先搜索算法

B.最小生成树算法

C.最短路径算法

D.拓扑排序算法

答案:

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

A.逻辑结构不同

B.存储结构不同

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

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

答案:

15.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=

head,则

A.p指向头结点

B.p指向尾结点

C.p的直接后继是头结点

D.P的直接后继是尾结点

答案:

16.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上

A.操作的有限集合

B.映象的有限集合

C.类型的有限集合

D.关系的有限集合

答案:

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

A.提高串匹配效率

B.提高存储密度

C.便于插入操作

D.便于删除操作

答案:

18.对长度为n的关键字序列进行堆排序的空间复杂度为

A.O（log2n）

B.O（1）

C.O（n）

D.O（n*log2n）

答案:

19.在一个带权连通图G中，权值最小的边一定包含在G的

A.最小生成树中

B.深度优先生成树中

C.广度优先生成树中

D.深度优先生成森林中

答案:

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

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

B.(rear-length+m)％m

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

D.(rear-length)％m

答案: