数据构造专升本模拟题及参考答案讲课教案.docx

《数据构造专升本模拟题及参考答案讲课教案.docx》由会员分享，可在线阅读，更多相关《数据构造专升本模拟题及参考答案讲课教案.docx（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造专升本模拟题及参考答案讲课教案、单项选择题A.2B.3C.4D.65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是()。A.98B.100C.102D.1066、判疋一个栈s(取多兀素为m0)为空的条件是()。A.s-top!=0B.s-top=0C.s-top!=m0D.s-top=m07、循环队列用数组Am(下标从0到m-1)存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是()。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front8、设有两

2、个串S1与S2,求串S2在S1中初次出现位置的运算称作()A.连接B?求子串C.形式匹配D.判子串9、设串S1=ABCDEFG；S2=PQRST，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开场的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2),subs(S1,len(S2),2)的结果是()。作业题(一)1.从逻辑上能够把数据构造分为(A.动态构造、静态构造BC.线性构造、非线性构造D2.链表不具有的特点是()A插入、删除不需要移动元素C.不必事先估计存储空间D.3.下面程序段的时间复杂度的量级为(Fo

3、r(i=1;iB.BCDEFGC.BCPQRSTD.BCDEFEF10、数组常用的两种基本操作是。A.建立与查找B.删除与查找C.插入与索引D.查找与修改二、填空题1.所谓稀疏矩阵指的是_且分布没有规律。2.队列是_的线性表，其运算遵循_的原则。3._空格串是4.简单项选择择排序和起泡排序中比拟次数与序列初态无关的算法有_。5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为_，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为_，图的深度或广度优先搜索遍历时的空间复杂度均为_。6、一个图的_表示法是唯一的，而_表示法是不唯一的。三、算法设

4、二叉树采用二叉链表构造，试设计一个算法统计给定二叉树中的一度结点数目。四、应用题1、对关键字无序序列36,25,48,12,65,43,20,58进行直接选择排序，请写出每一趟排序的结果。10分2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。10分3、已知记录关键字集合为53,17,19,61,98,75,79,63,46,49要求散列到地址区间100,101,102,103,104,105,106,107,108,109内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；构成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。设等概率情况4、设被查找文件有40

5、95个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比拟次数为多少？A.BCDEF作业题二、单项选择题1.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？A.543612B.453126C.346521D.2341562.栈和队都是A.顺序存储的线性构造B.链式存储的非线性构造C.限制存取点的线性构造D.限制存取点的非线性构造3、顺序查找法合适于存储构造为的线形表。A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储4、分别下面列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是。A100，80，90，60，120，110，130)B(1

6、00，120，110，130，80，60，90)C100，60，80，90，120，110，130)D(100，80，60，90，120，130，110)5、折半查找的平均比拟次数为。AnBn/2Clog2nDlog2(n+1)6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，可以用顺序查找，但前者比后者的查找速度A.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减7、已知一有向图的邻接表存储构造如下列图如示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是。A.AECDBFGC.ACEDBGF、填空题1.设no为哈夫曼树的叶子结点数目则该哈夫曼树共有

7、_个结点。2.有数据WG=719,2,6,32,3,21,10，则所建Huffman树的树高是_，带权途径长度WPL为_3.设一棵完全二叉树叶子结点数为k,最后一层结点数2,则该二叉树的高度为_4.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率一样，假设采用顺序查找来确定结点所在的块时，每块应分_个结点最佳。5.设G为具有N个顶点的无向连通图，贝UG中至少有条边。6.哈夫曼树HuffmanTree又称_。它是n个带权叶子结点构成的所有二叉树中，带权途径长度WPL_7.树的先序遍历经过如下：若树为空，则进行空操作；若树非空，则访问树的_;依次先序遍历树的_A.v1,v2,v3,v

8、5,v4C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v28、为了方便地对图状构造的数据进行存取操作，则其中数据存储构造宜采用A.顺序存储B.链式存储C.索引存储D.散列存储9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s,则所有顶点的入度之和为A.sB.s-1C.s+1D.n10、如下图，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列是B.v1,v2,v3,v4,v5B.AGBFDEC当前位置：文档视界数据构造专升本模拟题及参考答案讲课教案数据构造专升本模拟题及参考答案讲课教案2、对关键字序列10，6，3，2，5，4，构造一棵平衡二叉排序

9、树并画图要求画出建树经过3、设有一个有序文件，其中各记录的关键字为1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，当用折半查找算法查找关键字为3，8，19时，其比拟次数分别为多少？4、对有五个结点A,B,C,D,E的图的邻接矩阵，0100301060020105001画出逻辑图；2画出图的十字链表存储；3基于邻接矩阵写出图的深度、广度优先遍历序列；4计算图的关键途径。2?设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,数组从内存首一、单项选择题1串的长度是指A.串中所含不同字母的个数C.串中所含不同字符的个数作业题三B串中所含非空格字符的

10、个数D串中所含字符的个数地址BA开场顺序存放，当用以列为主存放时,元素A5，8的存储首地址为。A.BA+141B.BA+180C.BA+222D.BA+2253算法分析的两个主要方面是。A.空间复杂性和时间复杂性正确性和简明性C.可读性和文档性数据复杂性和程序复杂性4算法分析的目的是。9.一个顺序存储线性表的第一个元素的存储地址是90,每个元素的长度是2,则第6个元素的存储地址是()A.98B.100C.102D.106C.单循环链表D二、填空题1.高度为2的二叉树的结点数至少有2.在顺序表(8,11,15,19,25,26,30,33,42,48,50)中，用折半查找关键字值20,需做的关键

11、字比拟次数为_3.在有n个顶点的无向图中，每个顶点的度最大可达_4.已知广义表A=(a,b,c),(d,e,f),则广义表运算head(tail(tail(A)=_5._数组(Array)是n(n1)个_的有序组合，数组中的数据是按顺序存储在一块_的存储单元中。6.采用顺序存储构造表示三元组表(TripleTable),来实现对稀疏矩阵的一种压缩存储形式，就称精品文档A.找出数据构造的合理性BC.分析算法的效率以求改良D5.下面程序段的时间复杂性的量极为(Intfun(intn)inti=1,s=1;While(snext=LD8.在一个长度为n的线性表中，删除值为A.(n+1)/2BC.nD

12、.O(lbn).O().一个有限序列，不能为空?一个无限序列，不能为空).L-next=NULL.L!=NULLx的元素时需要比拟元素和移动元素的总次数为.n/2.n+110.假如某链表中最常用的操作是取第i个结点及其前驱，则采用()存储方式最节省时间。A.单链表B.双向链表.顺序表_个，高度为3的二叉树的结点数至少有_个。7.带头结点的单链表L为空的断定条件是(当前位置：文档视界数据构造专升本模拟题及参考答案讲课教案数据构造专升本模拟题及参考答案讲课教案当前位置：文档视界数据构造专升本模拟题及参考答案讲课教案数据构造专升本模拟题及参考答案讲课教案当前位置：文档视界数据构造专升本模拟题及参考答

13、案讲课教案数据构造专升本模拟题及参考答案讲课教案B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)9.广义表知足Head(A)=Tail(A)，则A为(A.()B.()C.(),()D.(),(),()10.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为()个。A.3B.4C.5D.6二、填空题1.在一个循环队列中，队首指针指向队首元素的_2.数组中每一个数据通常称为_,_用下标区分，其中下标的个数由数组的决定。3.一个图的_表示法是唯一的，而_表示法是不唯

14、一的。4.在一个10阶的B-树上，每个数根结点中所含的关键字数目最多允许_1.2.3.4.A.C.5.A.C.6.A.C.7.、单项选择题作业题(四)将两个各有n个元素的有序表归并成一个有序表，其最少得比拟次数是(A.nC.2n.2n-1.n-1一个有n个顶点的无向连通图，它所包含的连通分量个数为(A.0C.n数据文件的基本操作中最重要的操作是(A.插入C.修改对关键码序列28,16,32,12,60,2,(2,5,12,16)26(60,32,72)(2,16,12,5)28(60,32,72)假如只想得到1000个元素组成的序列中第堆排序插入排序算法分析的目的是(找出数据构造的合理性分析算法的效率以求改良二叉树的第I层上最多含有结点数为(A.2I2I-1-1C.2I-1B.1D.n+1B.删除D.检索5,72快速排序，从小到大一次划分结果为(B.(5,16,2,12)28(60,32,72)D.(5,16,2,12)28(32,60,72)5个最小元素之前的部分排序的序列，用(B.快速排序D.归并排序.研究算法中的输入和输出的关系.分析算法的易懂性和文档性D.2I-1)方法最快。循环队列存储在数组A中，长度为m则入队时的操作为(A.rear=rear+1