11-12-数据结构试卷-A+答案

2011～2012学年第1学期期末考试试卷（A卷）课程名称：数据结构任课教师姓名：卷面总分：100分考试时长：100分钟考试类别：闭卷院（系）：专业：年级：2010姓名：学号：题号第一题第二题第三题第四题总分得分阅卷教师（签字）：一、单项选择题（每题2分，共10题20分）题号12345678910答案ABBBBDDCCA1．以下那一个术语与数据的存储结构无关？。A．栈B．哈希表C．线索树D．双向链表2．链表不具有的特点是。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性表长度成正比3．算术表达式a+b*（c+d/e）转为后缀表达式后为。A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++4．二维数组A[10][20]采用列优先的存储方法,若每个元素占2个存储单元，设A[0][0]的地址为100，则元素A[7][6]的存储地址为。A．232B．234C．390D．392装订线5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是B。A．9B．11C．15D．不确定6．一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为D。A.ABCDEFB.EFCDBAC.FECDABD.EFCDAB7．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是D。A．G中有弧Vi，VjB．G中有一条从Vi到Vj的路径C．G中没有弧Vi,VjD．G中有一条从Vj到Vi的路径8．对于二叉排序树，下面的说法C是正确的。A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合(不用移动元素的树)B．对二叉排序树进行层序遍历可得到有序序列（应该是中序遍历）C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2（取决于二叉排序树的形状）9．一组记录的关键字为{47、75、55、30、42、90}，则用快速排序方法并以第一个记录为支点得到的第一次划分结果是。A.30,42,47,55,75,90B.42,30,47,75,55,90C.42,30,47,55,75,90D.42,30,47,90,55,7510．下述文件中适合于磁带存储的是。A.顺序文件B.索引文件C.散列文件D.多关键字文件顺序文件：原理是顺序表查找法索引文件：原理是线性索引查找(如最大关键码和次关键码)EFCABD多关键字文件：散列文件：原理是散列函数（哈希函数）二、判断（每题1分，共10题10分）题号12345678910答案×√√××√×√×√1．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。----()（如果插入和删除次数较少时顺序存储方式为首选）2．KMP算法的特点是在模式匹配时指示主串的指针不会变小。------------()（主串在匹配过程中是不会移动的，只有匹配的串在移动，所以其指针不会动）3．若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1.---()4．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。---------------------------------------------------------()数组不能进行插入删除等操作5．若一个广义表的表头为空表，则此广义表亦为空表。-------------------()6．完全二叉树中，若一个结点没有左孩子，则它必是树叶。---------------()完全二叉树的关键之一就是：元素又是有序排列的，顺序不可间断7．一个有向图的邻接表和逆邻接表中结点的个数可能不等。---------------()必须相等8．AOE网一定是有向无环图。-----------------------------------------()AOE网的特征和定义9．对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。---()应该是中序排列10．倒排文件与多重表文件的次关键字索引结构是不同的。-------------()三、填空题（每题2分，共10题20分）1．带头结点的双循环链表L中只有一个元素结点的条件是：L-next-next==L。下一个元素的后继恒为自身2．已知链队列的头尾指针分别是f和r，则将s指向的结点入队的操作是r-next=s；r=s。将插入元素赋值给原队尾指针的后继3．广义表A(((),(a,(b),c)))，head(tail(head(tail(head(A))))等于(b)。HeadA=((),(a,(b),c))tail(head(A))=(a,(b),c)head(tail(head(A))=（a,(b)）tail(head(tail(head(A)))=（(b)）head(tail(head(tail(head(A))))=(b)4．高度为5的完全二叉树至少有8个叶子结点5．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为1+2*1+3*2+4*3=21。6．求图的最小生成树有两种算法中，prim算法适合于求稠密图的最小生成树。7．具有10个关键字的有序表，折半查找的平均查找长度2.9。8．高度为7的平衡二叉树的结点数至少有33个。用斐波那契序数进行计算9．在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是m-1。B-树是一种多路查找树。M阶的B树具有如下特性：每一个分支结点都有k-1个元素和k个孩子。？10．对n个记录进行简单选择排序，所需进行的关键字间的比较次数为1+2+3+…+(n-1)=n(n-1)/2。四、简答题（每题5分，共10题50分）1．画出广义表（a，（b，c，d），e）的存储结构图（采用头尾指针的链表结构，标志1表示表结点，标志0表示原子结点）广义表的注意点：同一个括号内的横向表示。2．画出下列由三棵树组成的森林转换为二叉树。森林转化为二叉树的要点：先将每一棵树都转化为二叉树，再进行组合。3．给定一组叶子的权值分别为：8、6、3、2、7、24，填写下表构造一棵赫夫曼树，并画出该赫夫曼树(同一层的左子树根权值小于右子树根权值)HT：weightparentlchildrchild18900268003370042700579006241100758438111078915105110261189abcdefghijkl1111110a0b0c0d0eabcdefghijkl6243278511152650115006104．已知某图的邻接表（1）．画出此邻接表对应的图；（2）．写出由v1开始的深度优先遍历的序列；（3）．画出由v1开始的深度优先的生成树；v1开始深度优先遍历的序列:v1-v2-v5-v3-v4-v6V1V2V3V4V5V6生成树V1V2V3V4V5V6图5．画出带权无向图的一棵最小生成树。6．按Dijkstra算法计算从顶点A到其它各个顶点的最短路径和最短路径长度。（写出每一步计算得到的最短路径和相应的路径长度）源点AV(i)路径终点BCDEi=1路径路径长度AB3AC20AE45BABi=2路径路径长度ABC18ABE43CABCi=2路径路径长度ABCD38ABE43DABCDi=4路径路径长度ABE43EABE12453618161156124361611561236165612316512161124536331814191621118567．由字符序列(t,d,e,s,u,g,)建立一棵平衡的二叉排序树(画出主要过程)。最后一步：因为在右子树上的左子树上进行插入所以首先对大右子树进行向右旋转，整体树再向左旋转，最后整体调节一下平衡。8．已知散列表的地址空间为A[0..11]，散列函数H（k）=kmod11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。关键字251638477982513989151231哈希值35532576180哈希地址01234567891011关键字231897925471638825139151比较次数11112123243等概率情况下查找成功时的平均查找长度：（1+1+1+1+2+1+2+3+2+4+3）/11=21/11平均查找长度的算法。就是对差值进行求和再取平均。ttdtdetdetdestdesutdesugtdesug9．已知序列{101，51，19，61，3，71，31，17，18，100，55，20，9，30，50，6}，请采用希尔排序对该序列作升序排序，给出每一趟排序结果（设：d[1]=5，d[2]=3，d[3]=1）第1趟:6，20，9，18，3，55，31，17，30，50，71，51，19，61，100，101第2趟:6，3，9，18，17，30，19，20，51，31，61，55，50，71，100，101第3趟:3，6，9，17，18，19，20，30，31，51，55，50，61，71，100，101关键在于找到关键字10．进行置换-选择排序时得到归并段长度分别为9，4，7，3，8，6，15，试画出3路平衡最佳归并树并求出总的读/写次数。最佳归并树:总的读/写次数：=（（3+4+6+7+8+9）*2+15）*2=17894378615132452