《河南农业大学13-14-2数据结构试卷(a)-有答案(共9页)》由会员分享，可在线阅读，更多相关《河南农业大学13-14-2数据结构试卷(a)-有答案(共9页)（9页珍藏版）》请在装配图网上搜索。
1、精选优质文档-倾情为你奉上河南农业大学20132014学年第二学期数据结构考试试卷（A卷）（信管专业适用）题号一二三总分分数 得分评卷人一、判断题(每题1分，共10分，对的打，错的打，请将答案填在表格中)123456789101. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。2. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。3. 线性表的逻辑顺序与存储顺序总是一致的。4. 栈和链表是两种不同的数据结构。5. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 6二叉树中每个结点有两棵非空子树或有两棵空子树。7.用二叉链表法（link-rli
2、nk）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。8.对于一棵二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。9.任意图都是其自身的子图。10一个图具有生成树的必要条件是该图必须是连通图。 院、部 班 级 姓名 学号 密线得分评卷人二、选择题（每题2分，共40分）1. 算法指的是（ ）。A计算机程序 B解决问题的计算方法C排序算法 D解决问题的有限运算序列2. 线性表采用链式存储时，结点的存储地址（ ）。A必须是不连续的 B连续与否均可C必须是连续的 D和头结点的存储地址相连续3. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）
3、。AO（1） BO（n）CO（m） DO（m+n）4. 线性表L在（ ）情况下适用于使用链式结构实现。A.需经常修改中的结点值 B.需不断对进行删除插入C.L中含有大量的结点 D.L中结点结构复杂5. 设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作? （ ）。As一1ink=p一1ink；p一1inksBq一1inks；s一link=pCp一links一1ink；s一1inkpDp一1inks；s一1inkq6. 由两个栈共享一个向量空间的好处是：（ ）。A减少存取时间，降低下溢发生的机率B节省
4、存储空间，降低上溢发生的机率C减少存取时间，降低上溢发生的机率D节省存储空间，降低下溢发生的机率7. 如下陈述中正确的是（ ）。A串是一种特殊的线性表B串的长度必须大于零C串中元素只能是字母D空串就是空白串8. 一个非空广义表的表头（ ）。A不可能是子表B只能是子表C只能是原子D可以是子表或原子9. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（ ）。A.较快 B.较慢 C.相同 D.不一定10. 树中所有结点的度等于所有结点数加（ ）。A.0 B.1 C.一1 D.211. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）
5、。A.n B.n一1 C.n+1 D.2*n12. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A.空或只有一个结点。 B.高度等于其结点数。C.任一结点无左孩子。 D.任一结点无右孩子。13. n个结点的二叉树，若用二叉链表存贮则非空闲的左、右孩子链域为（ ）。A.n B.2n C.n-1 D.n+114. 已知二叉树叶子数为50，仅有一个孩子的结点数为30，则总结点数为（ ）。A.130 B. 129 C.131 D.不确定15. 在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为（ ）。A4 B5C6D716. 假设一个有n个
6、顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（ ）。AO(n)BO(e) CO(n+e) DO(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归
7、并排序D快速排序19. 适于对动态查找表进行高效率查找的组织结构是（ ）。A有序表B分块有序表 C三叉排序树D线性链表20. 如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（ ）方法最快。A、起泡排序 B、快速排序 C、堆排序 D、直接选择排序得分评卷人三、操作题（共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进行前缀编码，问该字符串的编码至少有多少位(提示:画出哈夫曼树
8、并求出WPL值)？（10分）3. 如下图所示的网络计划图（15分）（1）写出该图的所有拓扑序列。（2）列出各事件的最早、最迟发生时间（以顶点为事件）（3）找出该AOE图中的关键路径，并回答完成该工程需要的最短时间。eb 57.22 3 0 0 8dga 4.5 2 4 6.5f8c 4设哈希（Hash）表的地址范围为017，哈希函数为：H（K）K MOD 16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：（15分）1) 画出哈希表的示意图；2) 若查找关键字63，需要依次与哪些关
9、键字进行比较？3) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。0123456789101112131415161713-14-2数据结构 a 评分标准一、判断题（每题1分，共10分）二、选择题（每题2分，共40分）1-5 DBCBB 6-10 BADBC 11-15 CBCBC 16-20 CADCD三、操作题（共50分）12画出树5分，写成字符编码3分，求出wpl值2分。ABCDEFGH0000000001100001110001101012134478156535201193wpl=52+51+43+35+29+34+34+2798该字符串编码长度至少为98位。3、（1）所
10、有的拓扑序列如下：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） 最早发生时间 最迟发生时间 vea=0 vlg=19 veb=3 vlf=12.5 vec=4.5 vle=11 ved=6.5 vld=8.5 vee=8 vlc=4.5 vef=12.5 vlb=6 veg=19 vla=0（3） 关键路径为：a，c，f，g 所需最短时间为： L=4.5+6.5+8=19第1小题4分；第2小题7分；第3小题4分4、（1）哈希表如下:012345678910111213141516173217634924401030314647（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,No! ; 然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）32，17，24，10，30，31各比较1次；63比较6次；49，46,47比较3次；40比较2次； 所以ASL=（612133+61）/1123/112.1第1小题7分；第2、3小题各4分专心-专注-专业
河南农业大学13-14-2数据结构试卷(a)-有答案(共9页)
