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

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

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 –1

正确答案:-----

正确答案:-----

B.2k-1 –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≤i≤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.便于删除操作

正确答案:-----

 

21.对长度为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

正确答案:-----

 

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

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

试卷总分:100  得分:100

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

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

A.n-1

B.n

C.n+l

D.2n

 

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

A.先序序列

B.中序序列

C.后序序列

D.层序序列

 

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

A.8

B.3

C.5

D.9

 

4.倒排文件的主要优点是

A.便于进行插入和删除运算

B.便于进行文件的恢复

C.便于进行多关键字查询

D.节省存储空间

 

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

  head,则

A.p指向头结点

B.p指向尾结点

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

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

 

6.连通图是指图中任意两个顶点之间

A.都连通的无向图

B.都不连通的无向图

C.都连通的有向图

D.都不连通的有向图

 

7.一棵具有 n个结点的完全二叉树的树高度（深度）是

A.ëlognû+1

B.logn+1

C.ëlognû

D.logn-1

 

8.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为

A.4

B.5

C.6

D.7

 

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

A.Q.front==NULL

B.Q.rear==NULL

C.Q.front==Q.rear

D.Q.front!=Q.rear

 

10.下列数据结构中，属于非线性数据结构的是

A.栈

B.队列

C.完全二叉树

D.堆

 

11.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为

A.i

B.i+1

C.n-i

D.n-i+1

 

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

A.ABCDEF

B.ABCEFD

C.ABFCDE

D.ABCDFE

 

13.从广义表LS＝（(p, q), r, s）中分解出原子q的运算是

A.tail (head (LS))

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

C.head (tail (LS))

D.tail (tail (head (LS)))

 

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

A.X的双亲

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

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

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

 

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

A.分块查找

B.顺序查找

C.二分查找

D.散列查找

 

16.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是

A.0

B.1

C.2

D.3

 

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

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

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

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

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

 

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

A.插入操作更加方便

B.删除操作更加方便

C.不会出现下溢的情况

D.不会出现上溢的情况

 

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

A.先进先出

B.后进先出

C.进优于出

D.出优于进

 

20.稠密索引是在索引表中

A.为每个记录建立一个索引项

B.为每个页块建立一个索引项

C.为每组记录建立一个索引项

D.为每个字段建立一个索引项