搜索
第1页共9页院、部班级姓名学号………………………………………………密………………………线………………………………………………河南农业大学2013—2014学年第二学期《数据结构》考试试卷（A卷）（信管专业适用）题号一二三总分分数得分评卷人一、判断题(每题1分，共10分，对的打√，错的打×，请将答案填在表格中)123456789101.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。2.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。3.线性表的逻辑顺序与存储顺序总是一致的。4.栈和链表是两种不同的数据结构。5.一个栈的输入序列是12345，则栈的输出序列不可能是12345。6二叉树中每个结点有两棵非空子树或有两棵空子树。7.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。8.对于一棵二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。9.任意图都是其自身的子图。10．一个图具有生成树的必要条件是该图必须是连通图。第2页共9页得分评卷人二、选择题（每题2分，共40分）1.算法指的是（）。A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址（）。A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。A．O（1）B．O（n）C．O（m）D．O（m+n）4.线性表L在（）情况下适用于使用链式结构实现。A.需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.L中含有大量的结点D.L中结点结构复杂5.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?（）。A．s一1ink=p一1ink；p一1ink＝sB．q一1ink＝s；s一link=pC．p一link＝s一1ink；s一1ink＝pD．p一1ink＝s；s一1ink＝q6.由两个栈共享一个向量空间的好处是：（）。A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率7.如下陈述中正确的是（）。A．串是一种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串8.一个非空广义表的表头（）。A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子9.一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）。A.较快B.较慢C.相同D.不一定10.树中所有结点的度等于所有结点数加（）。A.0B.1C.一1D.211.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.nB.n一1C.n+1D.2*n第3页共9页12.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或只有一个结点。B.高度等于其结点数。C.任一结点无左孩子。D.任一结点无右孩子。13.n个结点的二叉树，若用二叉链表存贮则非空闲的左、右孩子链域为（）。A.nB.2nC.n-1D.n+114.已知二叉树叶子数为50，仅有一个孩子的结点数为30，则总结点数为（）。A.130B.129C.131D.不确定15.在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为（）。A．4B．5C．6D．716.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（）。A．O(n)B．O(e)C．O(n+e)D．O(n*e)17.在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个（）。A、顶点序列B、边序列C、权值总和D、边的条数18.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）。A．选择排序B．希尔排序C．归并排序D．快速排序19.适于对动态查找表进行高效率查找的组织结构是（）。A．有序表B．分块有序表C．三叉排序树D．线性链表20.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。A、起泡排序B、快速排序C、堆排序D、直接选择排序第4页共9页得分评卷人三、操作题（共50分）1.若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，试画出二叉树。（10分）2．已知某字符串s中共有8种字符(a,b,c,d,e,f,g,h)，各种字符分别出现2次，1次，4次，5次，7次，3次，4次和9次，对该字符串用{0，1}进行前缀编码，问该字符串的编码至少有多少位(提示:画出哈夫曼树并求出WPL值)？（10分）第5页共9页3.如下图所示的网络计划图（15分）（1）写出该图的所有拓扑序列。（2）列出各事件的最早、最迟发生时间（以顶点为事件）（3）找出该AOE图中的关键路径，并回答完成该工程需要的最短时间。530084.5246.5acdefg27.28b第6页共9页4．设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝KMOD16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：（15分）1)画出哈希表的示意图；2)若查找关键字63，需要依次与哪些关键字进行比较？3)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。01234567891011121314151617第7页共9页13-14-2数据结构a评分标准一、判断题（每题1分，共10分）二、选择题（每题2分，共40分）1-5DBCBB6-10BADBC11-15CBCBC16-20CADCD三、操作题（共50分）1．2．画出树5分，写成字符编码3分，求出wpl值2分。ABCDEFGH0000000001100001110001101012134478156535201193第8页共9页wpl=5×2+5×1+4×3+3×5+2×9+3×4+3×4+2×7＝98该字符串编码长度至少为98位。3、（1）所有的拓扑序列如下：a，b，c，d，e，f，ga，b，c，d，f，e，ga，c，b，d，e，f，ga，c，b，d，f，e，g（2）最早发生时间最迟发生时间ve[a]=0vl[g]=19ve[b]=3vl[f]=12.5ve[c]=4.5vl[e]=11ve[d]=6.5vl[d]=8.5ve[e]=8vl[c]=4.5ve[f]=12.5vl[b]=6ve[g]=19vl[a]=0（3）关键路径为：a，c，f，g第9页共9页所需最短时间为：L=4.5+6.5+8=19第1小题4分；第2小题7分；第3小题4分4、（1）哈希表如下:012345678910111213141516173217634924401030314647（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,No!;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）32，17，24，10，30，31各比较1次；63比较6次；49，46,47比较3次；40比较2次；所以ASL=（6×1＋2×1＋3×3+6×1）/11＝23/11≈2.1第1小题7分；第2、3小题各4分