资源描述：
《2011期中考试答案-评分标准.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数据结构》期中考一、填空题（25%）(第1~10题每题2分，第11题5分)1.一个栈的进栈序列是A、B、C，写出所有可能的出栈序列______________________________________________。答案：ABC，ACB，BAC，BCA，CBA评分标准：少写或填错不给分，只有全对才给2分。2.广义表GL=((a,b,c),(d,e,f))，假设求表头操作为Head，求表尾操作为Tail，则f=__________________。答案：head[tail[tail[head[tail[GL]]]]]3.具有4个节点的不同二叉树共有______棵
2、。答案：14或者是14*4！=3364.已知数组A[1…10,1…10]为对称矩阵，期中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续内存单元中，则元素A[5][6]对应的地址为_____答案：10955.算术表达式(x+y)/10+a*b/c-(x-y)*(a-b)转为后缀表达式后为。答案：xy+10/ab*c/+xy-ab-*-6.如果表示静态链表的数组elem[1].link=3,elem[1].data=1,elem[2].link=3,elem[2].data=2,elem[3].link=4,elem[3].data=5,则在
3、静态链表中elem[1]指向的下一个元素的值是_____.答案：57.设栈s和队列q的初始状态为空，元素a,b,c,d,e和f依次通过栈s，一个元素出栈后即进入队列q，若6个元素出队的序列是bdcfea，则栈s的容量至少应该存放____个元素。答案：38.树的后序遍历和它通过左孩子右兄弟方法转换的二叉树的_______遍历是等价的。答案：中序9.试判断下面的关键码序列中哪一个是堆____________。①{94,31,53,23,16,72}②{16,31,23,94,53,72}③{16,53,23,94,31,72}④{94,53,31,72,16,23}⑤{16
4、,72,31,23,94,53}答案：210.已知一棵二叉树是以二叉链表的形式存储的，其结点结构说明如下：structnode{intdata;structnode*left;structnode*right;}请在下面的_____处进行填空，空成题目要求的功能。注意：每空只能填一个语句，多填为0分。求出以T为根的二叉树或子树的结点个数intsize(structnode*T){if(____________)return0;else___________}答案：T==NULL,return(1+size(T‐>left)+size(T‐>right));评分标准：每空
5、1分。共2分。11.高度为h的满二叉树(，其结点总数n可以用h表示为，而h可以用n表示为____________，若该树的结点从零开始按中序遍历顺序编号，则树根的编号用h表示为_______________，树根的左孩子的编号用h表示为_________，树根的右孩子的编号用h表示为_________。答案：2h+1-1,loghh-1h+1h-12(n+1)-1,2-1,2-1,2-2-1评分标准：每空1分，共5分。二、问答题（35%，每题7分）1.一棵二叉树的前序、中序和后序遍历序列分别如下，其中有一部分未显示出来（每个空白均只有一个节点），请补全下列空白并画出该二
6、叉树。（7分）先序序列：_B_F_ICEH_G;中序序列：D_KFIA_EJC_;后序序列：_K_FBHJ_G_A;答案：先序序列：ABDFKICEHJG中序序列:DBKFIAHEJCG后序序列：DKIFBHJEGCA评分标准：先序2分，每一个空格0.5分中序2分，只对1个给1分，对2个给1.5分，对3个给2分。后序2分，每一个空格0.5分二叉树1分，画错不给分，全对给1分。2.已知目标串T=”abcabbabcabaaa”，模式串P=”abcabaa”。（7分）a)请按照KMP算法的要求计算模式串P的next[]数组包括next数组定义方法和优化方法。b)请画出利用a
7、)生成的next数组，KMP算法进行模式匹配时的每一趟匹配过程。评分标准：a部分4分，每一空给0.5分。全对给4分。刘鹏b部分3分，对1个给1分，对2个给1.5分，对3个给2分，全对给3分。定义0123456ABCABAA-1000121优化：01234567ABCABAA-100-10211(1)定义匹配过程:abcabbabcabaaa
8、
9、
10、
11、
12、Xabcabaaabcabbabcabaaa
13、
14、XabcabaaabcabbabcabaaaXabcabaaabcabbabcabaaa
15、
16、
17、
18、
19、
20、
21、abcabaa(2)优化匹配过程abcab
