《汇编选集四川大学《数据结构2264》19春在线作业2(100分)》由会员分享,可在线阅读,更多相关《汇编选集四川大学《数据结构2264》19春在线作业2(100分)(12页珍藏版)》请在金锄头文库上搜索。
1、汇编选集四川大学数据结构226419春在线作业2(100分)试卷名称:数据结构226418春在线作业2-00011.若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G,后序遍历的序列为B、D、C、A、F、G、E。则该二叉树结点的前序遍历的序列为( )。A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B答案:-2.AOV网是一种( )。A.有向图B.无向图C.无向无环图D.有向无环图答案:-3.队列的特点是( )。A.先进后出B.先进先出C.任意位置进出D.前面都不正确答案:-4.设森林F对应的二叉树为B,它有m个结点
2、,B的根为p,p的右子树上的结点个数为n,森林F中第一棵树的结点个数是( )。A.m-n-1B.n+1C.m-n+1D.m-n答案:-5.从L=( ),( ))中,取出banana元素的表达式为( )。A.head(tail(L)B.head(head(tail(L)C.tail(head(tail(L)D.head(tail(head(tail(L)答案:-6.带有头结点的单循环链表的头指针为head,则该链表为空的判定条件是( )。A.head= =NULB.head-next= =NULLC.head!=NULLD.head-next= =head答案:-7.以下数据结构中哪一个是非线性
3、结构?( )A.队列B.栈C.线性表D.二叉树答案:-8.在数据结构中,数据元素可由( )。A.实体B.域C.数据项D.字段答案:-9.在对n个关键字进行直接选择排序的过程中,每一趟都要从无序区选出最小关键字元素,则在进行第i趟排序之前,无序区中元素的个数为( )。A.iB.i+1C.n-iD.n-i+1答案:-10.已知一个图的顶点集V=1,2,3,4,5,6,7;边集E=( )3, ( )5, ( )8, ( )10, ( )6, ( )15, ( )12, ( )9, ( )4, ( )20, ( )18, ( )25,用克鲁斯卡尔算法得到最小生成树,则在最小生成树中依次得到的各条边为(
4、 )。A.(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20B.(1,2)3,(4,6)4,(1,3)5,(2,3)6,(1,4)8,(3,6)9C.(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)20D.(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层( )二叉树的结点总数最多为( )。A.2k
5、-1B.2K+1C.2K-1D.2k-1答案:-13.设有一个二维数组Amn ( ),假设A00存放位置在600,A33存放位置在678,每个元素占一个空间,则A23的存放位置是( )。A.658B.648C.633D.653答案:-14.设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。A.5B.6C.7D.8答案:-15.采用开放定址法处理散列表的冲突时,其平均查找长度( )。A.低于链接法处理冲突B.高于链接法处理冲突C.与链接法处理冲突相同D.高于二分查找答案:-16.假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行( )次探测。A.K-
6、1次B.K次C.Kl次D.K(K+1)/2次答案:-17.若有18个元素的有序表存放在一维数组A19中,第一个元素放A1中,现进行二分查找,则查找A3的比较序列的下标依次为( )。A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,3答案:-18.对线性表,在下列哪种情况下应当采用链表表示?( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变答案:-19.树最适合用来表示( )。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据答案:-20.如表r有100000个元素,前99
7、999个元素递增有序,则采用( )方法比较次数较少。A.直接插入排序B.快速排序C.归并排序D.选择排序答案:-21.一散列表长度m为100,采用除留余数法构造散列函数,即H( )=K%P ( ),,为使散列函数具有较好的性能,P的选择应是( )。A.99B.100C.97D.93答案:-22.从一个长度为n的顺序表中删除第i个元素( )时,需向前移动的元素个数是( )。A.n-iB.n-i+1C.n-i-1D.i答案:-23.在一个单链表HL中,若要在当前由指针p指向的结点后面插入一个由q指向的结点,则执行如下( )语句序列。A.p=q; p-next=q;B.p-next=q; q-nex
8、t=p;C.p-next=q-next; p=q;D.q-next=p-next; p-next=q;答案:-24.对一棵有100个结点的完全二叉树按层编号,根结点编号为1,则编号为49的结点的父结点的编号为( )。A.24B.5C.98D.99答案:-25.从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。A.O(n)B.O(1)C.O(log2n)D.O(n2)答案:-1.以下哪些是队列的基本运算?( )A.在队列第i个元素之后插入一个元素B.从队头删除一个元素C.判断一个队列是否为空D.读取队头元素的值E.将队列中的元素排序答案:-2.以下数据结构中哪一个是线性结构?( )A.有向
9、图B.队列C.线索二叉树D.线性表E.栈答案:-3.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列为( )。A.3,2,6,1,4,5B.3,4,2,1,6,5C.1,2,5,3,4,6D.5,6,4,2,3,1E.6,5,4,3,2,1答案:-4.对一个算法的评价,主要包括如下( )方面的内容。A.健壮性和可读性B.并行性C.正确性D.时空复杂度E.界面友好性答案:-1.在用循环单链表表示的链式队列中,可以不设队头指针,仅在链尾设置队尾指针。A.错误B.正确答案:-2.为度量一个搜索算法的效率,需要在时间和空间两个方面进行分析。A.错误B.正确答案:-3
10、.线性表若采用链式存储表示, 在删除时不需要移动元素。A.错误B.正确答案:-4.一个广义表的表头总是一个广义表。A.错误B.正确答案:-5.在顺序表中,逻辑上相邻的元素在物理位置上不一定相邻。A.错误B.正确答案:-6.若一棵二叉树的任一非叶子结点的度为2,则该二叉树为满二叉树。A.错误B.正确答案:-7.快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。A.错误B.正确答案:-8.图G的某一最小生成树的代价一定小于其他生成树的代价。A.错误B.正确答案:-9.进行折半搜索的表必须是顺序存储的有序表。A.错误B.正确答案:-10.数据的逻辑结构是指各数据元素之间的逻辑关系,是用户根据应用需要建立的。A.错误B.正确答案:-11.线性表若采用链式存储表示时,其存储结点的地址可连续也可不连续。A.错误B.正确答案:-12.线性表的长度是线性表所占用的存储空间的大小。A.错误B.正确答案:-13.在采用线性探测法处理冲突的哈希表中,所有同义词在表中相邻。A.错误B.正确答案:-14.顺序表用一维数组作为存储结构,因此顺序表是一维数组。A.错误B.正确答案:-15.有回路的有向图不能完成拓扑排序。A.错误B.正确答案:-