2016年计算机学科专业基础综合试题参考答案一、单项选择题I.D2.9.B10.17.C18.25:C26.33.C34.I.解析：根据存储状态，单链表的结构如下图所示。DABAC.....l97531l23CDBBD4.12.20.28.36.BCADB5.13.21.29.37.CDAAB6.14.22.30.38.DAACD7.15.23.31.39.BCADC8.16.24.32.40.BCBAC1008H1000H1010H101411三二其中“链接地址”是指结点next所指的内存地址。当结点f插入后，a指向f,f指向e,e指向b。显然a、e和f的“链接地址”分别是f、b和e的内存地址，即1014H、1004H和1010H。2.解析：此类题的解题思路万变不离其宗，无论是链表的插入还是删除都必须保证不断链。3.解析：在确保队列先进先出原则的前提下。根据题意具体分析：入队顺序为8,4,2,5,3,9,1,6,7,出队顺序为1~9。入口和出口之间有多个队列(n条轨道），且每个队列（轨道）可容纳多个元素（多列列车）。如此分析：显然先入队的元素必须小千后入队的元素（如果8和4入同一队列，8在前4在后，那么出队时只能是8在前4在后），这样8入队列1,4入队列2,2入队列3,5入队列2(按照前面的原则“大的元素在小的元素后面”也可以将5入队列3,但这时剩下的元素3就必须放到一个新的队列里面，无法确保”至少“，本应该是将5入队列2,再将3入队列3,不增加新队列的情况下，可以满足题意“至少”的要求），3入队列3,9入队列1,这时共占了3个队列，后面还有元素1,直接再占用一个新的队列4,1从队列4出队后，剩下的元素6和7或者入队到队列2或者入队到队列3(为简单起见我们不妨设n个队列的序号分别为1,2,…,n),这样就可以满足题目的要求。综上，共占用了4个队列。当然还有其他的入队出队的情况，请考生们自己推演。但要确保满足：O队列中后面的元素大千前面的元素；＠确保占用最少（即满足题目中的“至少")的队列。4.解析：三对角矩阵如下图所示。01,1a1,2a2,Ia2.2a2,3。aJ,2a3,303,4。an-1,n-2an-l,n-1an一l,nan,n-1an,n采用压缩存储，将3条对角线上的元素按行优先方式存放在一维数组B中，且a1,1存放于B[O]中，其存储形式如下所示：I01.1I。1;1.I02,1I02,2I02,3I"'•Ian-1,nI0n.n-lI0n,nI可以计算矩阵A中3条对角线上的元素a;jCl�i,j�n,li-jl�l)在一维数组B中存放的下标为k=2i+j-3。解法一：针对该题，仅需将数字逐一代入公式里面即可：k=2x30+30-3=87,结果为87。解法二：观察上图的三对角矩阵不难发现，第一行有两个元素，剩下的在元素m30,Jo所在行之前的28行（注意下标l�i�lOO、1冬;�100)中每行都有3个元素，而m30,Jo之前仅有一个元素m30,29,那么不难发现元素m30,30在数组N中的下标是：2+28x3+2-1=87。【注意】矩阵和数组的下标是从0或1开始的（如矩阵可能从ao,o或a1,1开始，数组可能从B[O]或B[l]开始），这时就需要适时调整计算方法（这个方法无非是针对上面提到的公式k=2xi+j-3多计算1或少计算1的问题）。5.解析：解法一：树有一个很重要的性质：在n个结点的树中有n-1条边，“那么对千每棵树，其结点数比边数多1"。题中的森林中的结点数比边数多10(即25-15=10),显然共有10棵树。解法二：若考生再仔细分析可发现，此题也是考察图的某些方面的性质：生成树和生成森林。此时对于图的生成树有一个重要的性质：若图中顶点数为n,则它的生成树含有n一1条边。对比解法一中树的性质，不难发现两种解法都利用到了“树中结点数比边数多1"的性质，接下来的分析如解法一。6.解析：对于本题，只需按深度优先遍历的策略进行遍历即可。对千选项A:先访问Vi,然后访问与V1邻接且未被访问的任一顶点（满足的有V2、V3和Vs),此时访问Vs,然后从Vs出发，访问与Vs邻接且未被访问的任一顶点（满足的只有V4),然后从V4出发，访问与V4邻接且未被访问的任一顶点（满足的只有V立然后从V3出发，访问与V3邻接且未被访问的任一顶点（满足的只有V2),结束遍历。选项B和C的分析方法与选项A相同，不再赘述。对千选项D,首先访问Vi,然后从V1出发，访问与V1邻接且未被访问的任一顶点（满足的有V2、V3和Vs),然后从巧出发，访问与V2邻接且未被访问的任一顶点（满足的只有Vs),按规则本应该访问Vs,但选项D却访问V3,因此D错误。7.解析：根据拓扑排序的规则，输出每个顶点的同时还要删除以它为起点的边，这...
