《数据构造试卷及答案压缩版.docx》由会员分享，可在线阅读，更多相关《数据构造试卷及答案压缩版.docx（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据构造试卷及答案压缩版（数据构造）试卷及答案1算法分析的目的是()。A.找出数据构造的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改良D.分析算法的易懂性和文档性2是具有一样特性数据元素的集合，是数据的子集。A.数据符号B.数据对象C.数据D.数据构造3用链表表示线性表的优点是()。A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序一样4输入序列为A,B,C,D不可能的输出有。A.(A,B,C,D)B.(D,C,B,A)C.(A,C,D,B)D.(C,A,B,D)5在数组表示的循环队列中，front、rear分别为队列的头、尾指针，m
2、axSize为数组的最大长度，队满的条件是()。A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeD.rear=front6设有串t=Iamagoodstudent，那么Substr(t,6,6)=。A.studentB.agoodsC.goodD.agood7设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为。A.23B.33C.18D.408已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算。A.Gethead(Ge
3、thead(LS)B.Gettail(Gethead(LS)C.Gethead(Gethead(Gettail(LS)D.Gethead(Gettail(LS)9若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为()A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE10下列存储形式中，()不是树的存储形式。A.双亲表示法B.左子女右兄弟表示法C.广义表表示法D.顺序表示法11对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是()。A.直接选择排序B.直接
4、插入排序C.快速排序D.起泡排序12采用折半查找方法进行查找，数据文件应为，且限于。A.有序表顺序存储构造B.有序表链式存储构造C.随机表顺序存储构造D.随机表链式存储构造13就平均查找速度而言，下列几种查找速度从慢至快的关系是A.顺序折半哈希分块B.顺序分块折半哈希C.分块折半哈希顺序D.顺序哈希分块折半14执行下面程序段时，执行S语句的次数为for(intI=1;I1算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是_、_、_、有零或多个输入和有一或多个输出。2算法优劣的五个标准是正确性、可使用性、_、_、_。3有n个球队参加的足球联赛按主
5、客场制进行比赛，共需进行_场比赛。4设有串t=Iamastudent，s=good，那么Concat(t,s)=Iamastudentgood，Substr(t,8,7)=_。5在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个_构造，其主要特点是_。6广义表(a),a)的表头是_，表尾是_。三、判定题对的打“，错的打“。每题1分，共10分;答案填在下表内1数据的逻辑构造与数据元素本身的内容和形式无关。2三个结点的二叉树和三个结点的树一样，都具有三种不同的形态。3中序序列和后序序列一样的二
6、叉树为：空树和缺右子树的单支树。4对于两棵具有一样关键字集合而形状不同的二叉排序树，中序遍历后得到的关键字排列顺序一样。5序列30，40，50，15，25，35，38，10是堆。6对于无向图的生成树，从同一顶点出发所得的生成树一样。7若设哈希表长m=14，哈希函数H(key)=key%11，表中已有4个结点。addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是9。8一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号则，则编号最小的叶子的序号是2k-2+1；编号
7、是i的结点所在的层次号是log2i|+1。log2i|表示向上取整根所在的层次号规定为1层。9在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。10算法能够没有输入，但是必须有输出。四、画出树的孩子兄弟表示法示意的树或森林。4分设关键字的输入序列为4，5，7，2，1，3，618分从空树开场构造平衡二叉树，画出每参加一个新结点时二叉树的形态，若发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。2.4分上面的数据作为待排序的数据，写出用快速排序进行一趟划分后的数据序列六、按要求做题本大题共2小题，共12分5分七、算法分析设计题本大题共5小题，共30分1写出程序段的功能,并给出一个测试用
8、例一个输入数据和一个输出结果(5分)。voidconversion()Stacks;intn;SElemTypee;initstack(s);printf(Pleaseinputnumber:);scanf(“%d,while(n)push(s,n%8);n=n/8;while(!stackempty(s)pop(s,e);printf(“%d,e);2.下面是一个使用栈stack实现对二叉树进行非递归先根遍历的函数,请在标号处填写适宜的语句。(每空1分，共5分)程序:Voidpreorder(bitree*T)bitree*stackm;inttop;if(T!=NULL)top=1;sta
9、cktop=(1);while(2)p=stacktop;top-;printf(“%d,p-data);if(p-rchild!=NULL)(3);stacktop=p-rchild;if(4)top+;(5);3.请在标号处填写适宜的语句。完成下列程序。(每空1分，共5分)intBinary_Search(S_TBLtbl，KEYkx)/*在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则，返回0*/intmid，flag=0；low=1；high=length；while(&!flag)/*非空，进行比拟测试*/mid=；if(kxtbl.elemmid.key)
10、；elseflag=；break；returnflag;4.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写适宜的语句。(每空1分，共5分)程序：Voidseletesort(intAn,intn)inti,j,t,minval,minidx;for(i=1;i (3)top+(4)p-lchild!=NULL(5)stacktop=p-lchild35分，每空1分1lowAj(3)minval=Aj(4)i!=j(5)Ai+1=Aminidx510分，不同答案，酌情得分输入顶点和弧信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序排序经过中求顶点的Vei将得到的拓扑序列进栈
11、按逆拓扑序列求顶点的Vli计算每条弧的ei和li,找出ei=li的关键活动第2学期数据构造试卷A一、选择题本大题共15小题，每题2分，共30分；答案填在下表内1.从一个长度为100的顺序表中删除第30个元素时需向前移动个元素A、70B、71C、69D、302.在一个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为_。A、top不变B、top=0C、top=top-1D、top=top+13.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功情况下,则平均比拟_个结点。A、nB、n/2C、(n-1)/2D、(n+1)/2
12、4.在一个单链表中,若要删除p指针所指结点的后继结点,则执行A、p-next;p-next=p-next-next;B、p-next=p-next-next;C、p=p-next;D、p=p-next-next;5.在一个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行_。A、front-next=s；front=s；B、s-next=rear;rear=s；C、rear-next=s;rear=s；D、s-next=front;front=s；6.在一棵度为3的树中度为3的结点数为3个,度为2的结点数为1个,度为1的结点数为1个,那么度为0的结点数为_个
13、A、6B、7C、8D、97.假定一棵二叉树的结点数为33个,则它的最小高度为_,最大高度为_A、4,33B、5,33C、6,33D、6,328.在一棵完全二叉树中,若编号为i的结点有右孩子,则该结点的右孩子编号为_。A、2iB、2i+1C、2i-1D、i/29.在一个有向图中,所有顶点的入度之和等于所有弧数和_倍。A、1B、2C、3D、410.对于一个具有N个顶点的图,若用邻接矩阵表示,则该矩阵的大小为_。A、NB、(N-1)2C、(N+1)2D、N211.已知一个图如下图，在该图的最小生成树中各边上数值之和为_。A、21B、26C、28D、3312.已知一个图如下图，由该图行到的一种拓朴序列
14、为A、v1v4v6v2v5v3B、v1v2v3v4v5v6C、v1v4v2v3v6v5D、v1v2v4v6v3v513.二维数组M的元素是4个字符每个字符占一个存储单元组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M24的起始地址与M按列存储时元素的起始地址一样。A、m24B、M42C、M31D、M3114.具有6个结点的无向图至少应有条边才能保证是连通图。A、5B、6C、7D、815.采用邻接表存储的图的深度优先遍历类似于二叉树的。A先序遍历B中序遍历C.后序遍历D.按层遍历二、填空题本大题共5小题，每空1分，共8分；答案填在下表内根据数据元素之间关系的不同特性，
15、通常有下列四类基本构造：集合、线性构造、1和2。2.评价算法的标准很多，通常是以执行算法所需要的3和所占用的4来判别一个算法的优劣。3.线性表的顺序存储构造特点是表中逻辑关系相邻的元素在机器内的5也是相邻的。4.空格串的长度为串中所包含6字符的个数，空串的长度为75.加上表示指向前驱和8的线索的二叉数称为线索二叉树。三、判定题对的打“，错的打“。每题1分，共10分1.线性表的唯一存储形式是链表。2.已知指针P指向键表L中的某结点，执行语句P=P-next不会删除该链表中的结点。3.在链队列中，即便不设置尾指针也能进行入队操作。4.假如一个串中的所有字符均在另一串中出现，则讲前者是后者的子串。5
16、.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。6.快速排序是不稳定排序。7.任一AOE网中至少有一条关键途径，且是从源点到汇点的途径中最短的一条。8.若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条其中n为G的顶点数。9.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。10.基数排序是多关键字排序。从最低位关键字起进行排序。四、应用题。共44分1.画出该图的邻接矩阵和邻接表。根据邻接表从A开场求DFS和BFS序列。12分2.假设用于通信的电子由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中
17、出现的概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10画出哈夫曼树，并为这8个字母设计哈夫曼编码。8分3.已知序列70，73，69，23，93，18,11，68请给出直接插入排序作升序排序每一趟的结果和快速排序作升序排序时一趟的结果。10分4.设有一组关键字关键码集为47，7，29，11，16，92，22，8，3，哈希表表长为11，Hash(key)=keymod11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL。8分5.二叉树的先序遍历序列为ABCDEFGHI，中序遍历序列为BCAEDGHFI，画出这棵二叉树。(6分)五、算法设计题8分定义有序表抽象数据类型，并据此类型设计折半查找算法。2学期数据构造试卷A参考答案及评分标准一、选择题本大题共15小题，每题2分，共30分