2015年韩山师范学院本科插班生《数据结构》试卷

（A卷）第1页共6页2015年韩山师范学院本科插班生考试试卷计算机科学与技术专业数据结构试卷（A卷）一、单项选择题（每题2分，共30分）1.栈和队列的共同特点是()。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时()。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？()A.队列B.栈C.线性表D.二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？A．688B．678C．692D．6965.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为()。A．2k-1B.2K+1C.2K-1D.2k-17.设有向无环图G中的有向边集合E={1，2，2，3，3，4，1，4}，则下列属于该有向图G的一种拓扑排序序列的是（）。A.1,2,3,4B.2,3,4,1C.1,4,2,3D.1,2,4,38.下列关于数据结构的叙述中，正确的是（）。A.数组是同类型值的集合B.树是一种线性结构C.一般情况下递归算法的程序结构更为精炼、效率更高D.用一维数组存储二叉树，总是以先序遍历的顺序存储各结点（A卷）第2页共6页9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个。A．1B．2C．3D．410.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.811.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行()。A.p-next=HL-next;HL-next=p;B.p-next=HL;HL=p;C.p-next=HL;p=HL;D.HL=p;p-next=HL;12.线性表采用链式存储时，结点的存储地址（）。A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续13.任何一个无向连通图的最小生成树（）。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在14.设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。A.p-next=p-next-nextB.p=p-nextC.p=p-next-nextD.p-next=p15.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。A.BCDAB.BADCC.CDABD.CBDA二、填空题（每空2分，共20分）1.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。2.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则该树的深度为___________，树的度为_________。3.后缀算式923+-102/-的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。（A卷）第3页共6页4.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________________个指针是空指针。5.有如下递归函数：voidf(intw){inti;staticintj=1;if(w0){printf(“%d:”,j++);for(i=1;i=w;i++)printf(“%d，”,w);printf(“\n”);f(w−1);}}调用语句f(3)的结果是______________________________。6.已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是______________，BFS遍历的输出序列是________________。三、判断题（对的划√，错的划×。每小题1分，共10分）（）1．调用一次深度优先遍历可以访问到图中的所有顶点。（）2．哈夫曼树上只有树叶或者双支结点。（）3．冒泡排序在初始关键字序列为递减有序的情况下执行的交换次数最多。（）4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。得分评卷人（A卷）第4页共6页（）5．已知一棵二叉树的先序序列和后序序列，则能够唯一确定该二叉树的形状。（）6．层次遍历二叉树需要用到堆栈作为辅助结构。（）7．一棵树按孩子兄弟法转化成二叉树，该二叉树中一定没有右子树。（）8．线性表的顺序存储结构比链式存储结构更好。（）9．可以在有序单链表中实现二分查找算法。（）10.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。四、程序填空题（每个空2分，共10分）1.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。#defineM100typedefstruct{ints[M];inttop;}sqstack;voidpush(sqstack*stack,intx){if(stack-top==M-1)printf(“overflow”);else{______________________;_____________________;}}2．下面算法是求二叉树双支个数的算法。请完成填空。structTreeNode{intdata;structTreeNode*left,*right;};intfnGetLeaf(TreeNode*T){if(____________________)return0;if(T-left!=NULL&&T-right!=NULL)return(____________________________________________);得分评卷人（A卷）第5页共6页elsereturn(___________________________________________);}五、分析简答题（10分）1．（4分）试写出如图所示的二叉树分别按中序、后序遍历时得到的结点序列。2.（6分）用序列（46，68，45，139，70，58，101，10，88，94）建立一个二叉排序树，画出该树，并求在等概率情况下查找成功的平均查找长度。得分评卷人（A卷）第6页共6页六、算法设计题（20分）1、（8分）删除顺序表前i个元素。已知顺序表的数据结构如下：#defineMaxSize100typedefstruct{intdata[MaxSize];intlast;}SeqList;使用如下函数原型：boolfnDelete(SeqList*L,inti);//成功删除则返回true，否则返回false2、(12分)假设二叉树采用左右孩子指针存储结构，即其结点数据类型描述为：structTreeNode{intdata;//数据域structTreeNode*left,*right;//指向其左右孩子结点};试编写一个函数，要在一棵树Tree中，找出最大值。函数原型如下：boolfnGetMax(structTreeNode*Tree,int*max);//找到最大值则返回true，否则返回false;得分评卷人