2022年8月东北大学 《数据结构IIX》在线平时作业2

《数据结构Ⅱ》在线平时作业2  
一、单选题(共20道试题共100分)  
1.计算机识别、存储和加工处理的对象被统称为  
A.数据  
B.数据元素  
C.数据结构  
D.数据类型  
2.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+n×t）  
B.O（m+n+t）  
C.O（m×n×t）  
D.O（m×t+n）  
3.对关键字序列(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)  
4.在线性表的下列运算中，不改变数据元素之间结构关系的运算是  
A.插入  
B.删除  
C.排序  
D.查找  
5.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为  
A.4，4，3  
B.4，3，3  
C.3，4，4  
D.．3，3，4  
6.某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是  
A.空或只有一个结点  
B.高度等于其结点数  
C.任一结点无左孩子  
D.任一结点无右孩子  
7.数据的四种基本存储结构是指  
A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构  
B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构  
C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构  
D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构  
8.在下列存储形式中，哪一个不是树的存储形式  
A.双亲表示法  
B.孩子链表表示法  
C.孩子兄弟表示法  
D.顺序存储表示法  
9.用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为  
A.5  
B.6  
C.8  
D.9  
10.数据结构中所定义的数据元素，是用于表示数据的  
A.最小单位  
B.最大单位  
C.基本单位  
D.不可分割的单位  
11.在分块索引的在顺序表中查找，算法中采用的最佳技术是  
A.穷举法  
B.贪心法  
C.分治法  
D.分支限界法  
12.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是  
A.不确定  
B.0  
C.1  
D.2  
13.n个顶点的有向完全图中含有向边的数目最多为  
A.n-1  
B.n  
C.n(n-1)/2  
D.n(n-1)  
14.下列序列中，不构成堆的是  
A.（1，2，5，3，4，6，7，8，9，10）  
B.（10，5，8，4，2，6，7，1，3）  
C.（10，9，8，7，3，5，4，6，2）  
D.（1，2，3，4，10，9，8，7，6，5）  
15.倒排文件的主要优点是  
A.便于进行插入和删除运算  
B.便于进行文件的恢复  
C.便于进行多关键字查询  
D.节省存储空间  
16.下列陈述中正确的是  
A.二叉树是度为2的有序树  
B.二叉树中结点只有一个孩子时无左右之分  
C.二叉树中必有度为2的结点  
D.二叉树中最多只有两棵子树，并且有左右之分  
17.从广义表LS＝（(pq)rs）中分解出原子q的运算是  
A.tail(head(LS))  
B.head(tail(head(LS)))  
C.head(tail(LS))  
D.tail(tail(head(LS)))  
18.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是  
A.树的后根遍历与其对应的二叉树的后根遍历相同  
B.树的后根遍历与其对应的二叉树的中根遍历相同  
C.树的先根遍历与其对应的二叉树的中根遍历相同  
D.以上都不对  
19.在计算机内实现递归算法时所需的辅助数据结构是  
A.栈  
B.队列  
C.树  
D.图  
20.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的  
A.层次遍历算法  
B.前序遍历算法  
C.中序遍历算法  
D.后序遍历算法