【精选资料】数据结构期中试题及答案

第1页共6页命题人：审核人：试卷分类（A卷或B卷）五邑大学试卷参考答案及评分标准学期：至学年度第学期课程：数据结构课程代号：006A1060使用班级：一、单项选择题(15小题，每小题1分，共15分)1．顺序存储结构中数据元素之间的逻辑关系是由（C）表示的。A．线性结构B．非线性结构C．存储位置D．指针2．用数组r存储静态链表，结点的next域指向后继，工作指针j指向链表中某结点，则j后移的操作语句为（A）。A．j=r[j].next;B．j=j+1;C．j=j-next;D．j=r[j]-next;3．若一个栈的输入序列是1,2,3，…，n，其输出序列是p1,p2,…，pn，若p1=3，则p2的值（C）。A．一定是2B．一定是1C．不可能是1D．以上都不对4．设有两个字符串p和q，求q在p中首次出现的位置的运算称作（B）。A．连接B．模式匹配C．求子串D．求串长5．下述编码中（B）不是前缀编码。A．(00,01,10,11)B．(0,1,00,11)C．(0,10,110,111)D．(1,01,000,001)6．设森林中有4棵树，树中结点的个数依次为n1,n2,n3和n4，则把森林转换成二叉树后，其根结点的右子树上有（D）结点。A．n1-1B．n1C．n1+n2+n3D．n2+n3+n47．设有如下图所示的AOV网，不可能的拓扑排序结果是（C）。8．设哈夫曼编码的长度不超过4，若已经对两个字符编码为1和01，则最多还可以为（C）个字符编码。A．2B．3C．4D．59．对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（D）。A．nB．(n-1)2C．n-1D．n210．堆的形状是一棵（C）。A．二叉排序树B．判定树C．完全二叉树D．满二叉树11．对如图所示的无向连通网图，从顶点v0开始用Prim算法构造最小生成树，在构造过程中加入最小生成树的前4条边依次是（A）。试卷编号A．C1C2C3C4C5C6C7B．C2C1C3C4C5C6C7C．C1C2C6C4C3C5C7D．C1C2C4C6C3C5C7A．(v0,v5)(v5,v2)(v2,v3)(v5,v4)B．(v0,v1)(v5,v2)(v2,v3)(v5,v4)C．(v0,v2)(v5,v2)(v2,v3)(v5,v4)D．(v0,v5)(v5,v2)(v2,v3)(v3,v5)第2页共6页12．数据序列{8,9,10,4,5,6,20,1,2}只能是（C）的两趟排序后的结果。A．选择排序B．起泡排序C．插入排序D．堆排序13．在平衡二叉树中插入一个结点后造成了不平衡，设最低不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1（左－右），则应作（B）型调整以使其平衡。A．RRB．RLC．LLD．LR14．假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可操作的序列为合法序列，否则称为非法序列。下面序列中（C）是非法的。A．IOIIOIOOB．IIIOOIOOC．IOOIOIIOD．IIIIOOOO15．一个队列的入队顺序是1,2,3,4，则队列的输出顺序是（D）。A．4,3,2,1B．3,2,4,1C．1,3,2,4D．1,2,3,4二、判断正误题(涂黑所选择答案后的符号○。10小题，每小题1分，共10分)1．（正确●/错误○）算法的时间复杂度是由算法中的基本语句的执行次数的数量级确定。2．（正确○/错误●）线性表的基本特征：每个元素有且仅有一个直接前驱和一个直接后继。3．（正确●/错误○）假定二叉树的根结点的层次是1，则第i层上的结点数不会大于2i-1。4．（正确●/错误○）稀疏矩阵压缩存储后，必会失去随机存取功能。5．（正确○/错误●）使用双链表存储线性表具有提高检索速度的优势。6．（正确○/错误●）如果某种排序算法是不稳定的，则该排序方法没有实际应用价值。7．（正确○/错误●）在线索二叉树中，任一结点均有指向其前驱和后继的线索。8．（正确●/错误○）在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中不一定存在弧a，b。9．（正确○/错误●）散列技术中的冲突指的是数据元素过多。10．（正确○/错误●）若二叉排序树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。三、填空题(10小题，每空1分，共15分)1．从逻辑关系上讲，数据结构主要分为集合、线性表、（树）和（图）。2．设有一个空栈，栈顶指针为1000H，每个元素需要一个单位的存储空间，则执行push,push,pop,push,pop,push,push后，栈顶指针为（1003H）。3．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（12）个叶子结点。4．对n个待排序记录序列进行快速排序，所能得到的最好时间是（O(nlog2n)），最坏时间是（O(n2)）5．中缀表达式3×(x+2)-5所对应的后缀表达式为（3x2+×5-）；后缀表达式（#为数字间的分隔符，无需处理）5#2×6#4＋－的值为（0）。6．G是一个非连通无向图，共有28条边，则该图至少有(30)顶点。7．设有如下图所示的AOE网，则事件v7的最早发生时间是（14），最迟发生时间是（14），该AOE网的关键路径有（2）条。第3页共6页8．如果T′是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T′中结点的（前序）序列。9．利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（n-1）。10．对于数列{25,30,8,5,1,27,24,10,20,21,9,28,7,13,15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均次数为（8）。四、应用题(8小题，每小题6分，共48分)1．已知二叉树的中序遍历序列为a+b*c%d-e/f，前序遍历序列为-+a*b%cd/ef，构造该二叉树。评分：方法：4分；结果：2分2．试用“左孩子-右兄弟”方法，将下面的森林转化成一棵二叉树。评分：方法：4分；结果：2分3．有A、T、C、S四个字符，它们的权值分别为{7,5,2,4}，请构造相应的哈夫曼树，并给出这四个字符的哈夫曼编码（左分支赋0，右分支赋1）。评分：哈夫曼树：4分；哈夫曼编码：2分A：0T：10C：110S：1114．假设给出一组表项，它们的关键码为Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly。采用的哈希函数是：取其第一个字母在字母表中的位置。第4页共6页Hash(x)=ord(x)-ord(‘A’)//ord()是求字符内码的函数用线性探测法处理冲突，请填写下面的散列表，并计算平均查找长度ASLsucc。评分：散列表：4分；ASL：2分AttleeBurkeBroadBlumEkersAltonEderlyHecht11231631ASLsucc=（4+2+2*3+6）/8=18/85．设有关键码序列{16,3,7,11,9,}，构造平衡二叉树。评分：双旋转4分；单旋转：2分6．有一个完全二叉树按层次顺序存放在一维数组中，如下所示：请画出该二叉树；如果该树中存在i结点（非根），则i结点的双亲如何找？评分：完全二叉树4分；i结点双亲：2分解答：二叉树省略。i的双亲结点为：i/27．若输入序列是{53,17,78,9,45,65,87,23}，试画出由此序列构造的小根堆。评分：(a)~(e)每个步骤1分；结果：1分8．有一无向连通图如下所示。试给出图的邻接矩阵存储示意图，若从顶点V0出发对该图进行遍历，分别给出基于存储结构的深度优先遍历和广度优先遍历的顶点序列。评分：存储结构4分；遍历：2分第5页共6页五、算法设计题(2小题，每小题6分，共12分)1．在开散列表中进行动态查找的算法用伪代码描述如下：（1）计算散列地址j;（2）在第j个同义词子表中顺序查找；（3）若查找成功，则返回结点的地址；否则，将待查记录插在第j个同义词子表的表头。设散列表表长为m，散列表为ht[m]，k待查记录，请用C++描述完成上述算法。Nodeint*HashSearch(Nodeint*ht[],intm,intk){j=H(k);p=ht[j];以上1分while(p!=NULL&&p-data!=k)p=p-next;以上2分if(p-data==k)returnp;else{q=newNodeint;q-data=k;q-next=ht[j];ht[j]=q;}以上3分}2．用C++描述给出二叉树中序遍历递归算法。voidBiTreechar::InOrder(BiNodechar*bt){if(bt==NULL)return;//递归调用的结束条件以上2分else{InOrder(bt-lchild);//中序递归遍历bt的左子树coutbt-data;//访问根结点bt的数据域InOrder(bt-rchild);//中序递归遍历bt的右子树}以上4分}深度优先遍历的顶点序列：v0,v1,v2,v3广度优先遍历的顶点序列：v0,v1,v3,v2第6页共6页-高氯酸对阿胶进行湿法消化后,用导数火焰原子吸收光谱技术测定阿胶中的铜、“中药三大宝,人参、鹿茸和阿胶。”阿胶的药用已有两千多年的悠久历史,历代宫①马作峰.论疲劳源于肝脏[J].广西中医药,2008,31(1):31.①史丽萍,马东明,解丽芳等.力竭性运动对小鼠肝脏超微结构及肝糖原、肌糖元含量的影响[J].辽宁中医杂志,①王辉武,吴行明,邓开蓉.《内经》“肝者罢极之本”的临床价值[J].成都中医药大学学报,1997,20(2):9.①杨维益,陈家旭,王天芳等.运动性疲劳与中医肝脏的关系[J].北京中医药大学学报.1996,19(1):8.1运动性疲劳与肝脏①张俊明.“高效强力饮”增强运动机能的临床[J]．中国运动医学杂志，1989，8（2）：10117种水解蛋白氨基酸。总含量在56.73%～82.03%。霍光华②采用硝酸-硫酸消化法和18（4）：372-374.1995,206．2②林华,吕国枫,官德正等.衰竭运动小鼠肝损伤的实验性[J].天津体育学院党报,1994,9(4):9-11.②凌家杰.肝与运动性疲劳关系浅谈[J].湖南中医学院学报.2003，2（6）31.②凌家杰.肝与运动性疲劳关系浅谈[J].湖南中医学院学报.2003，23（6）：31.②谢敏豪等.训练结合用中药补剂强力宝对小鼠游泳耐力与肌肉和肝Gn,LDH和MDH的影响[J]．中国运动医学杂②杨维益,陈家旭,王天芳等.运动性疲劳与中医肝脏的关系[J].北京中医药大学学报.1996,19(1):8.2.1中药复方2.2单味药33阿胶和复方阿胶浆③常世和等.参宝片对机体机能影响的[J].中国运动医学杂志，1991，10（1）：49.③聂晓莉，李晓勇等.慢性疲劳大鼠模型的建立及其对肝功能的影响[J].热带医学杂志，2007,7(4)：323-325.3.1概述3.2关于阿胶和复方阿胶浆医疗保健作用的3.2.1营养成分和评价3.2.2阿胶的药理作用3.2.3阿胶的临床应用4④XieMH,etal．EffectsofHongjingtianshe1uonreproductiveaxisfunctionandexercisecapacitiesinmen.The5⑤周志宏等．补肾益元方对运动小鼠抗疲劳能力的影响[J].中国运动医学杂志，2001，20（1）：83-84202-204.5`InternationalCourseandConferenceonPhysiologicalChemistryandNatritionofexerciseandtraining(Abstract)6⑥杨维益等．中药复方“体复康”对运动性疲劳大鼠血乳酸、p一内啡肤、亮氨酸及强啡肤Al-13影响的实验研⑥。仙灵口服液可提高机体运动能力，加速运动后血乳酸的消除。F3口服液能调整PC