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

(完整word版)2015年韩山师范学院本科插班生《数据结构》试卷(完整word版)2015年韩山师范学院本科插班生《数据结构》试卷(完整word版)2015年韩山师范学院本科插班生《数据结构》试卷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。用一维数组存储二叉树，总是以先序遍历的顺序存储各结点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分)一个算法的时间复杂度为（n3+n2log2n+14n）/n2，其数量级表示为________。假定一棵树的广义表表示为A(C，D（E,F，G），H（I,J）),则该树的深度为___________，树的度为_________。后缀算式923+—102/-的值为__________。中缀算式（3+4X）—2Y/3对应的后缀算式为_______________________________。若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针.在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________________个指针是空指针。5.有如下递归函数：voidf(intw）｛inti；staticintj=1;if（w>0）｛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．满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树.（）5．已知一棵二叉树的先序序列和后序序列，则能够唯一确定该二叉树的形状.（）