四川大学《数据结构2264》18春在线作业2含答案

易百网

《数据结构2264》18春在线作业2
四川大学作业完整答案

一、单选题：
1.（单选题）若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。\n则该二叉树结点的前序遍历的序列为（）。          (满分:)
    AE、G、F、A、C、D、B
    BE、A、G、C、F、B、D
    CE、A、C、B、D、G、F
    DE、G、A、C、D、F、B
    正确答案:——C——
2.（单选题）AOV网是一种（）。          (满分:)
    A有向图
    B无向图
    C无向无环图
    D有向无环图
    正确答案:——D——
3.（单选题）队列的特点是（）。          (满分:)
    A先进后出
    B先进先出
    C任意位置进出
    D前面都不正确
    正确答案:——B——
4.（单选题）设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（）。          (满分:)
    Am-n-1
    Bn+1
    Cm-n+1
    Dm-n
    正确答案:————
5.（单选题）从L=（）,（）)中，取出banana元素的表达式为（）。          (满分:)
    Ahead(tail(L))
    Bhead(head(tail(L)))
    Ctail(head(tail(L)))
    Dhead(tail(head(tail(L))))
    正确答案:————
6.（单选题）带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（）。          (满分:)
    Ahead==NUL
    Bhead->next==NULL
    Chead!=NULL
    Dhead->next==head
    正确答案:————
7.（单选题）以下数据结构中哪一个是非线性结构？（）          (满分:)
    A队列
    B栈
    C线性表
    D二叉树
    正确答案:————
8.（单选题）在数据结构中，数据元素可由（）。          (满分:)
    A实体
    B域
    C数据项
    D字段
    正确答案:————
9.（单选题）在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（）。          (满分:)
    Ai
    Bi+1
    Cn-i
    Dn-i+1
    正确答案:————
10.（单选题）已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（）3,（）5,（）8,（）10,（）6,（）15,（）12,（）9,（）4,（）20,（）18,（）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（）。          (满分:)
    A(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20
    B(1,2)3,(4,6)4,(1,3)5,(2,3)6,(1,4)8,(3,6)9
    C(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)20
    D(1,2)3,(1,3)5,(1,4)8,(2,5)10,(4,6)4,(4,7)20
    正确答案:————
11.（单选题）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（）          (满分:)
    A都不相同
    B完全相同
    C先序和中序相同，而与后序不同
    D中序和后序相同，而与先序不同
    正确答案:————
12.（单选题）k层（）二叉树的结点总数最多为（）。          (满分:)
    A2k-1
    B2K+1
    C2K-1
    D2k-1
    正确答案:————
13.（单选题）设有一个二维数组A[m][n]（），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（）。          (满分:)
    A658
    B648
    C633
    D653
    正确答案:————
14.（单选题）设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。          (满分:)
    A5
    B6
    C7
    D8
    正确答案:————
15.（单选题）采用开放定址法处理散列表的冲突时，其平均查找长度（）。          (满分:)
    A低于链接法处理冲突
    B高于链接法处理冲突
    C与链接法处理冲突相同
    D高于二分查找
    正确答案:————
16.（单选题）假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（）次探测。          (满分:)
    AK-1次
    BK次
    CK＋l次
    DK(K+1)/2次
    正确答案:————
17.（单选题）若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（）。          (满分:)
    A1，2，3
    B9，5，2，3
    C9，5，3
    D9，4，2，3
    正确答案:————
18.（单选题）对线性表，在下列哪种情况下应当采用链表表示？（）          (满分:)
    A经常需要随机地存取元素
    B经常需要进行插入和删除操作
    C表中元素需要占据一片连续的存储空间
    D表中元素的个数不变
    正确答案:————
19.（单选题）树最适合用来表示（）。          (满分:)
    A有序数据元素
    B无序数据元素
    C元素之间具有分支层次关系的数据
    D元素之间无联系的数据
    正确答案:————
20.（单选题）如表r有100000个元素，前99999个元素递增有序，则采用（）方法比较次数较少。          (满分:)
    A直接插入排序
    B快速排序
    C归并排序
    D选择排序
    正确答案:————
21.（单选题）一散列表长度m为100，采用除留余数法构造散列函数，即H（）=K%P（）,，为使散列函数具有较好的性能，P的选择应是（）。          (满分:)
    A99
    B100
    C97
    D93
    正确答案:————
22.（单选题）从一个长度为n的顺序表中删除第i个元素（）时，需向前移动的元素个数是（）。          (满分:)
    An-i
    Bn-i+1
    Cn-i-1
    Di
    正确答案:————
23.（单选题）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（）语句序列。          (满分:)
    Ap=q;p->next=q;
    Bp->next=q;q->next=p;
    Cp->next=q->next;p=q;
    Dq->next=p->next;p->next=q;
    正确答案:————
24.（单选题）对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（）。          (满分:)
    A24
    B5
    C98
    D99
    正确答案:————
25.（单选题）从二叉搜索树中查找一个元素时，其时间复杂度大致为（）。          (满分:)
    AO(n)
    BO(1)
    CO(log2n)
    DO(n2)
    正确答案:————
二、多选题：
26.（多选题）以下哪些是队列的基本运算？（）          (满分:)
    A在队列第i个元素之后插入一个元素
    B从队头删除一个元素
    C判断一个队列是否为空
    D读取队头元素的值
    E将队列中的元素排序
    正确答案:————
27.（多选题）以下数据结构中哪一个是线性结构？（）          (满分:)
    A有向图
    B队列
    C线索二叉树
    D线性表
    E栈
    正确答案:————
28.（多选题）若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为（）。          (满分:)
    A3，2，6，1，4，5
    B3，4，2，1，6，5
    C1，2，5，3，4，6
    D5，6，4，2，3，1
    E6，5，4，3，2，1
    正确答案:————
29.（多选题）对一个算法的评价，主要包括如下（）方面的内容。          (满分:)
    A健壮性和可读性
    B并行性
    C正确性
    D时空复杂度
    E界面友好性
    正确答案:————
三、判断题：
30.（判断题）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。          (满分:)
    A错误
    B正确
    正确答案:————
31.（判断题）为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。          (满分:)
    A错误
    B正确
    正确答案:————
32.（判断题）线性表若采用链式存储表示,在删除时不需要移动元素。          (满分:)
    A错误
    B正确
    正确答案:————
33.（判断题）一个广义表的表头总是一个广义表。          (满分:)
    A错误
    B正确
    正确答案:————
34.（判断题）在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。          (满分:)
    A错误
    B正确
    正确答案:————
35.（判断题）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。          (满分:)
    A错误
    B正确
    正确答案:————
36.（判断题）快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。          (满分:)
    A错误
    B正确
    正确答案:————
37.（判断题）图G的某一最小生成树的代价一定小于其他生成树的代价。          (满分:)
    A错误
    B正确
    正确答案:————
38.（判断题）进行折半搜索的表必须是顺序存储的有序表。          (满分:)
    A错误
    B正确
    正确答案:————
39.（判断题）数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。          (满分:)
    A错误
    B正确
    正确答案:————
40.（判断题）线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。          (满分:)
    A错误
    B正确
    正确答案:————
41.（判断题）线性表的长度是线性表所占用的存储空间的大小。          (满分:)
    A错误
    B正确
    正确答案:————
42.（判断题）在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。          (满分:)
    A错误
    B正确
    正确答案:————
43.（判断题）顺序表用一维数组作为存储结构，因此顺序表是一维数组。          (满分:)
    A错误
    B正确
    正确答案:————
44.（判断题）有回路的有向图不能完成拓扑排序。          (满分:)
    A错误
    B正确
    正确答案:————
更多学习资料请登录www.openhelp100.com