搜索
第1页共5页华东交通大学2012—2013学年第一学期考试卷试卷编号：（A）卷数据结构课程课程类别：必开卷（仅限教材）：考试日期：题号一二三四五六七八九十总分累分人签名题分2030103010×××××100得分×××××考生注意事项：1、本试卷共5页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、选择题(每题2分，共20分)1、在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为()(A)f-next=c；f=s(B)r-next=s；r=s(C)s-next=r；r=s(D)s-next=f；f=s2、下面程序的时间复杂度为（）for(i=0;im;i++)for(j=0;jn;j++)A[i][j]=i*j;(A)O(M2)(B)O(N2)(C)O(M*N)(D)O(M+N)3、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：()(A)2h(B)2h-1(C)2h+1(D)h+14、设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。(A)q=p-next；p-data=q-data；p-next=q-next；free(q)；(B)q=p-next；q-data=p-data；p-next=q-next；free(q)；(C)q=p-next；p-next=q-next；free(q)；(D)q=p-next；p-data=q-data；free(q)；5、含N个顶点的连通图中的任意一条简单路径，其长度不可能超过()(A)1(B)N/2(C)N-1(D)N6、设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。得分评阅人承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：第2页共5页(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，217、若在线性表中采用折半查找法查找元素，该线性表应该()。(A)元素按值有序(B)采用顺序存储结构(C)元素按值有序，且采用顺序存储结构(D)元素按值有序，且采用链式存储结构8、．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是()。(A)in(B)2*i=n(C)2*i+1n(D)2*in9、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用()方法最快。(A)起泡排序(B)快速排序(C)堆排序(D)直接选择排序10、对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（）个，(A)1(B)2(C)3(D)4二、填空题(每空2分，共30分)1、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为（1），在表尾插入元素的时间复杂度为（2）。2、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较__（3）_____次就可以断定数据元素X是否在查找表中3、若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为__（4）_______。4、若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为M，则左、右子树皆非空的结点个数为_（5）__。5、设数组data［0..m］作为循环队列SQ的存储空间(判断队列满，少用一个元素空间)，front为队头指针，rear为队尾指针，则执行出队操作的语句为(（6）)。6、设哈夫曼树中共有n个结点，则该哈夫曼树中有__（7）____个度数为1的结点。7、设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为__（8）。8、队列的插入操作在_（9）___进行，删除操作在（10）____进行。9、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*lchild;____(11)____;}bitree;voidcreatebitree(bitree*&bt){scanf(“%c”,&ch);if(ch=='#')（12;得分评阅人第3页共5页else{bt=(bitree*)malloc(sizeof(bitree));bt-data=ch;___（13）_____;createbitree(bt-rchild);}}10、下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*next;}linklist;voidlinklistcreate(____(14)______*&head){for(i=1;i=n;i++){p=(linklist*)malloc(sizeof(linklist));scanf(“%d”,&(p-data));p-next=0;if(i==1)head=q=p;else{q-next=p;____(15)_______;}}}三、判断题(每题1分，共10分，对的打“√”，错的打“×”)1、有向图的邻接表和逆邻接表中表结点的个数不一定相等。()2、对链表进行插入和删除操作时不必移动链表中结点。()3、子串“ABC”在主串“AABCABCD”中的位置为2。()4、若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。()5、希尔排序算法的时间复杂度为O(n2)。()6、用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。()7、中序遍历一棵二叉排序树可以得到一个有序的序列。()8、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。()9、顺序表查找指的是在顺序存储结构上进行查找。()10、堆是完全二叉树，完全二叉树不一定是堆。()四、应用题（每小题6分，共30分）得分评阅人第4页共5页1、已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ,中序遍历的结果是KBCDAFHIGJ,写出后序遍历结果，并画出这棵二叉树。2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4、设给定一个权值集合W=(3，5，7，9，11)要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL5、设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉排序树。五、编程题(每题10分，共10分)1、统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL，ElemTypex)答案写在答题卡上，写在试卷上无效得分评阅人得分评阅人第页共4页华东交通大学2012—2013学年第一学期考试卷答题纸(A卷)数据结构课程课程类别：必开卷（仅限两本教材）：考试日期：题号一二三四五六七八九十总分累分人签名题分2030103010×××××100得分×××××考生注意事项：1、本答题纸共2页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、选择题(每题2分，共20分)得分阅卷人12345678910二、填空题(每空2分，共30分)得分阅卷人(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：第页共4页三、判断题(每题1分，共10分)得分阅卷人12345678910四、应用题（每小题6分，共30分）得分阅卷人12第页共4页345第页共4页五、编程题(每题10分，共10分)得分阅卷人1第3页共4页华东交通大学2012—2013学年第一学期考试卷参考答案(A卷)数据结构课程课程类别：必开卷（仅限两本教材）：考试日期：题号一二三四五六七八九十总分累分人签名题分2030103010×××××100得分×××××考生注意事项：1、本答题纸共2页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、选择题(每题2分，共20分)得分阅卷人12345678910BCCACACDDD二、填空题(每空2分，共30分)得分阅卷人(1)O(n)(2)O(1)(3)7(4)2m(5)M-1(6)front:＝(front+1)mod(m+1)(7)0(8)(49，13，27，50，76，38，65，97)(9)队尾(10)队头(11)structnode*rchild(12)bt=0(13)createbitree(bt-lchild)(14)linklist(15)q=p承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：第3页共4页三、判断题(每题1分，共10分)得分阅卷人12345678910×√√√××√√×√四、应用题（每小题6分，共30分）得分阅卷人1二叉树为：中序遍历结果：KDCBIHJGFA2012345678910111278150357452031233612查找成功的平均查找长度：ASLSUCC=14/10=1.4第3页共4页3依次得到的各条边：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204WPL=785第3页共4页五、编程题(每题10分，共10分)得分阅卷人1intCountX(LNode*HL，ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P-data==x)i++;p=p-next;}returni;}