奥鹏[东北大学]20春学期《数据结构Ⅱ》在线平时作业2

20春学期《数据结构Ⅱ》在线平时作业2
试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 100 分)
1.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是
A.O(nlogn)
B.O(n2)
C.O(n)
D.O(1)
答案:C

2.下列程序段 for(i=1;i<=n;i++) A[I,j]=0; 的时间复杂度是
A.O(n)
B.O(1+n)
C.O(1)
D.O(0)
答案:A

3.可有效提高次关键字查找效率的文件是
A.顺序文件
B.散列文件
C.倒排文件
D.VSAM文件
答案:C

4.for（i=0；i<m；i++）
for（j=0；j<t；j++）
c［i］［j］=0；
for（i=0；i<m；i++）
for（j=0；j<t；j++）
for（k=0；k<n；k++）
c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
上列程序的时间复杂度为
A.O（m×t+n）
B.O（m×n×t）
C.O（m+n×t）
D.O（m+n+t）
答案:B

5.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A.都相同
B.都不相同
C.互为逆序
D.不一定相同
答案:A

6.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
A.树的后根遍历与其对应的二叉树的后根遍历相同
B.树的后根遍历与其对应的二叉树的中根遍历相同
C.树的先根遍历与其对应的二叉树的中根遍历相同
D.以上都不对
答案:B

7.要求具有同一逻辑结构的数据元素具有相同的特性，其含义为
A.每个数据元素都一样
B.数据元素具有同一的特点
C.仅需要数据元素包含的数据项的个数相同
D.不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致
答案:D

8.当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为
A.左子树的叶子结点
B.左子树的分支结点
C.右子树的叶子结点
D.右子树的分支结点
答案:A

9.下面关于数据结构正确的说法是
A.相互之间存在一种或多种特定关系的数据元素的集合
B.数据的存储结构
C.一组性质相同的数据元素的集合
D.一种数据类型
答案:A

10.在下列各种文件中，不能进行顺序查找的文件是
A.顺序文件
B.索引文件
C.散列文件
D.多重表文件
答案:C

11.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是
A.V1,V3,V4,V6,V2,V5,V7
B.V1,V3,V4,V5,V2,V6,V7
C.V1,V3,V2,V6,V4,V5,V7
D.V1,V2,V5,V3,V4,V6,V7
答案:A

12.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是
A.队列
B.线性表
C.栈
D.有序表
答案:A

13.某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A.高度等于其结点数
B.空或只有一个结点
C.任一结点无左孩子
D.任一结点无右孩子
答案:A

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

15.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为
A.55/15
B.51/15
C.49/15
D.39/15
答案:C

16.在计算机内实现递归算法时所需的辅助数据结构是
A.队列
B.树
C.栈
D.图
答案:C

17.按排序过程中依据的原则分类，快速排序属于
A.选择类的排序方法
B.插入类的排序方法
C.归并类的排序方法
D.交换类的排序方法
答案:D

18.顺序存储设计时，存储单元的地址
A.部分连续，部分不连续
B.不一定连续
C.一定连续
D.一定不连续
答案:C

19.从逻辑上可以把数据结构分为两大类，即
A.顺序结构、链式结构
B.线性结构、非线性结构
C.动态结构、静态结构
D.初等结构、构造型结构
答案:B

20.在一个单链表中，若删除*p结点的后继结点，则执行操作
A.q=p->next;p->next=q->next;free(q);
B.p=p->next;p->next=p->next->next;free(p);
C.p=p->next->next;free(p->next);
D.p->next=q->next;free(p->next);
答案:A

AI创作