搜索
2011年数据结构期末试卷1．算法分析的目的是(C)。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分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是()。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(Gethead(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.直接插入排序C.快速排序D.起泡排序12．采用折半查找方法进行查找，数据文件应为（），且限于（）。A.有序表顺序存储结构B.有序表链式存储结构C.随机表顺序存储结构D.随机表链式存储结构13．就平均查找速度而言，下列几种查找速度从慢至快的关系是（）A.顺序折半哈希分块B.顺序分块折半哈希C.分块折半哈希顺序D.顺序哈希分块折半14．执行下面程序段时，执行S语句的次数为（）for(intI=1;I=n;I++)for(intj=1;j=I;j++)S;A.n2B.n2/2C.n(n+1)D.n(n+1)/215．串是一种特殊的线性表，其特殊性体现在（）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符16．树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论()是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对17．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为()。A.60B.66C.67D.5018．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有()个A.33B.34C.32D.3019．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时，（）次比较后查找成功。A.1B.2C.4D.820．若有文件的关键字序列为：[265][301][751][129][937][863][742][694][076][438]，以下为二路归并排序过程。第二趟为:A.[265301][129751][863937][694742][076438]B.[076129265301438694742751863937]C.[129265301694742751863937][076438]D.[129265301751][694742863937][076438]二、填空题（本大题共6小题，每空2分，共12分；答案填在下表内）1算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是_______、______、________、有零或多个输入和有一或多个输出。2算法优劣的五个标准是正确性、可使用性、______、______、_____。3有n个球队参加的足球联赛按主客场制进行比赛，共需进行_________场比赛。4设有串t='Iamastudent'，s='good'，那么Concat(t,s)='Iamastudentgood'，Substr(t,8,7)=__________。5在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个_________结构，其主要特点是__________。6广义表((a),a)的表头是_______，表尾是_______。三、判断题（对的打“√”，错的打“×”。每小题1分，共10分;答案填在下表内）1数据的逻辑结构与数据元素本身的内容和形式无关。2三个结点的二叉树和三个结点的树一样，都具有三种不同的形态。3中序序列和后序序列相同的二叉树为：空树和缺右子树的单支树。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；编号是i的结点所在的层次号是「log2i|+1。（「log2i|表示向上取整」（根所在的层次号规定为1层）。9在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。10算法可以没有输入，但是必须有输出。四、画出树的孩子兄弟表示法示意的树或森林。（4分）A∧B∧∧CD∧H∧∧F∧EG∧∧I∧五、要求题（本大题共2小题，共12分）设关键字的输入序列为{4，5，7，2，1，3，6}1．（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。1．（4分）上面的数据作为待排序的数据，写出用快速排序进行一趟划分后的数据序列六、按要求做题（本大题共2小题，共12分）1画出无向图G的邻接表存储结构，根据邻接表存储结构写出深度优先和广度优先遍历序列。（7分）V1V2V3V4V5V6V7V82用prim算法求下图的最小生成树，写出最小生成树的生成过程。（5分）V7V4V3V5V5V7V1V3V7V2V4V5V645425265506030705040V1V250V6V2V6V1V3V4七、算法分析设计题（本大题共5小题，共30分）1．写出程序段的功能,并给出一个测试用例（一个输入数据和一个输出结果）(5分)。voidconversion(){Stacks;intn;SElemTypee;initstack(s);printf(Pleaseinputnumber:);scanf(“%d”,&n);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*stack[m];inttop;if(T!=NULL){top=1;stack[top]=(1);while((2)){p=stack[top];top--;printf(“%d”,p-data);if(p-rchild!=NULL){(3);stack[top]=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.elem[mid].key)⑶；elseif(kxtbl.elem[mid].key)⑷；else{flag=⑸；break；}}returnflag;}⑴⑵⑶⑷⑸4.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写合适的语句。(每空1分，共5分)程序：Voidseletesort(intA[n],intn){inti,j,t,minval,minidx;for(i=1;i=n-1;i++){minval=A[i+1];(1)for(j=i+2;j=n;j++)if((2)){(3);minidx=j;}if((4)){t=A[i+1];(5)A[minidx]=t;}}}⑴⑵⑶⑷⑸5试写出求有向无环图的关键路径算法的设计思路（10分）数据结构试卷A答案选择题（本大题共20小题，每题1分，共20分；答案填在下表内）12345678910CB:C:D:B:D:B:C:A:C11121314151617181920:CA:B:D:B:A:C:ACD二、填空题（本大题共5小题，每空1分，共12分；答案填在下表内）1有穷性确定性可行性2可读性健壮性效率3n(n-1)4'student'5队列先进先出6(a)(a)三、判断题（对的打“√”，错的打“×”。每小题1分，共10分）1）true;2）flase;3）true;4）true;5）flase;6）flase;7）true;8）true;9）flase;10）true四、画出树的孩子兄弟表示法示意的树或森林。（4分）ABCDEFGHI其他形式的树形结构酌情给分。五、要求题（本大题共2小题，共12分）1.4574574572142571256143324517324517632461752.一趟划分后的数据序列3124756六、按要求做题（12分）1DFS遍历序列v1v2v4v8v5v3v6v7(或12485367)BFS遍历序列v1v2v3v4v5v6v7v8(或12345678)邻接点的顺序可以不同，可以有不同的深度优先和广度优先遍历序列。（5分，如有错误酌情扣分。）2V3V7V7V6V5V4V2504050V4V2V6V530504050V2V54050V6V4V7V1V3V1V3V1V6V5V2V7V4V6V7V2V4V5V3V3V1V1七、算法设计题（30分）1.将十进制转化成八进制数（5分）测试用例：输入10输出122（5分，每空1分）（1）T(2)top0(3)top++(4)p-lchild!=NULL(5)stack[top]=p-lchild3（5分，每空1分）（1）low=high(2)(low+high)/2(3)high=mid-1(4)low=mid+1(5)14.（5分，每空1分）（1）min