搜索
第1页共12页考试科目名称数据结构（A1卷）1、填空题。（每小题2分，本题满分20分）(1)C++语言中，数组是按行优先顺序存储的，假设定义了一个二维数组A[20][30]，每个元素占两个字节，其起始地址为2140，则二维数组A的最后一个数据元素的地址为2140+2*(30*20-1)=3338(3338,3339)。(2)若A，B是两个单链表，链表长度分别为n和m，其元素值递增有序，将A和B归并成一个按元素值递增有序的单链表，并要求辅助空间为O(1)，则实现该功能的算法的时间复杂度为O(m+n)。(3)快速排序的平均时间复杂度是____n*lgn___________。(4)假设有一个包含9个元素的最小堆，存放在数组A中，则一定比A[3]大的元素有__2(A[7],A[8])____个；一定比A[3]小的元素有__2(A[0],A[1])____个。（元素从第0个位置开始存放）(5)广义表(((A)),(B,C),D,((A),((E,F))))的长度是4，深度是4。(6)有10个元素的有序表，采用折半查找，需要比较4次才可找到的元素个数为____3_____。(7）当两个栈共享一存储区时，栈利用一维数组A[n]表示，两栈顶指针为top[0]与top[1]，则栈满时的判断条件为___top[0]+1=top[1]_或者top[0]=top[1]+1___。(8)假设计算斐波那契数的函数Fib(longn)定义如下：longFib(longn){if(n=1)returnn;elsereturnFib(n-1)+Fib(n-2)}计算Fib(5)时的递归调用树（即指明函数调用关系的树）的高度是___4_____。假设叶子结点所在的高度为0。(9)完全二叉树按照层次次序，自顶向下，同层从左到右顺序从0开始编号时，编号为i的结点的左子结点的编号为___2*i+1______。(10)假设用子女—兄弟链表方式表示森林，对应的二叉树的根结点是p，那么森林的第三棵树的根结点在二叉树中对应的结点是：___p-rightchild-rightchild____________。假设二叉树的结点结构为：2、选择题。（每小题2分，本题满分20分）(1)如果能够在只知道指针p指向链表中任一结点，不知道头指针的情况下，将结点*p从链表中删除，则这个链表结构应该是：(B,C)（多选题）A.单链表B.循环链表C.双向链表D.带头结点的单链表(2)以下哪种矩阵压缩存储后会失去随机存取的功能?(A)A.稀疏矩阵B.对称矩阵C.对角矩阵D.上三角矩阵(3)下面哪一方法可以判断出一个有向图是否有环（回路）：(B)(选A，B也对)A.广度优先遍历B.拓扑排序C.求最短路径D.求关键路径(4)n个结点的线索二叉树(没有头结点)上含有的线索数为（B）得分得分leftchilddatarightchild第2页共12页A.2nB.n－lC.n＋lD.n(5)循环队列存储在数组A[0..m]中，则入队时队尾指针rear的操作为（D）A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)(6)使用加权规则得到改进的Union操作WeightedUnion，其目的是：(B)A.提高Union操作的时间性能B.提高Find操作的时间性能C.减少Union操作的空间存储D.减少Find操作的空间存储(7)使用Kruscal算法求解最小生成树时，为了设计效率较高的算法,数据结构方面可以选择：(A)A.利用最小堆存储边B.利用栈存储结点C.利用二维数组存储结点D.利用并查集存储边(8)已知一算术表达式的后缀形式为ABC*+DE/-，其前缀形式为：(D)A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE(9)n个关键码排序，如果选用直接插入排序方法，则元素的移动次数在最坏情况下可以达到(B)。A.n*n/2B.n*(n-1)/2C.n/2D.(n-1)/2(10)关键路径是AOE网络中AC。（多选）A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.所有活动都是关键活动的路径D.最短回路３、简答题。（每小题5分，本题满分20分）(1)对如下无向图，按照Dijkstra算法，写出从顶点1到其它各个顶点的最短路径和最短路径长度。135246结点编号123456路径长度0117121415最短路径11-21-31-3-41-3-51-3-6(2）请画出在如下图所示的5阶B树中插入一个关键码360后得到的B树。1002003004002040150180240260310320350370420430得分7105869117第3页共12页3001002003504002040150180240260310320360370420430(3)假设有权值集合{16,40,15,4,25}，给出相应的huffman树。假设某类信息由符号a,b,c,d,e,组成，而上面的权值分别是符号a,b,c,d,e的出现频率。请给出各个符号的Huffman编码。Huffman编码：a:001b:1c:0001d:0000e:01注意：因为左右子树不同，所以编码可以有多种，但是只要其长度分别是3，1，4，4，2；且相互之间不形成前缀关系就是正确的。(4)在AVL树的插入操作中，假设插入一个结点后，当前节点p的平衡因子是-2，其左子结点的平衡因子是+1，左子结点的右子结点的平衡因子是-1。如图所示，请给出旋转调整之后的结构。415191635256040100ABCt1t2t3t4-2+1-1pACBt1t2t3t40+1-1第4页共12页4、已知输入关键码序列为（10,90,20,60,78,35,42,31,15），地址区间为0～11。(1)请设计一个散列函数，把上述关键码散到0～11中。画出散列表，冲突用线性探测法解决。（5分）散列函数为：f(x)=x%12允许其它的散列函数0123456789101160/131/715/190/178/220/142/410/135/1(2)搜索元素31需要比较的次数是多少？（2分）7(7--8-9-10-11-0-1(成功））(3)计算在等概率情况下查找成功的平均查找长度ASLsucc。（3分）(1+7+1+1+2+1+4+1+1)/9=19/95、程序设计题。（每小题15分，本题满分30分）1.设计一个算法，根据一棵二叉树的前序序列和中序序列，构造出这棵二叉树。二叉树的结点都用字符表示。前序序列和中序序列都是字符串。二叉树的结点定义如下：structbinTreeNode{chardata;binTreeNode*leftChild,*rightChild;}解：TreeNode*tree(char*preorder,*midorder){returnTreeRecursive(preorder,0,strlen(preorder)-1,midorder,0,strlen(midorder)-1);}TreeNode*TreeREcursive(char*pre,intpreSt,intpreEnd,char*mid,intmidSt,intmidEnd){if(preEndpreSt)returnNULL;charrt=pre[preSt];for(intj=midSt;j=midEnd;j++)if(mid[j]==rt)break;if(jmidEnd){coutWronginput;returnNULL;}TreeNoderoot=newbinTreeNode();root-data=rt;intlLen=j-midSt;root-leftChild=treeRecursive(pre,preSt+1,preSt+lLen-1,得分得分第5页共12页mid,midSt,midSt+lLen-1);root-rightChild=treeRecursive(pre,preSt+lLen+1,preEnd,mid,midSt+lLen+1,midEnd);returnroot;}要点在于根据preOrder的第一个字符，在midOrder中找到左右子树的分界；然后递归调用生成左右子树；做到这一点，就可以给出大部分分数。可能有很多细节上不一样的地方，比如这里的preEnd指向的字符在相应的树中；但是有些人可能是preEnd指向下一个位置。或者传递参数时直接使用字符串传递。都是可以的。如果使用别的办法，参考其效率，酌情给分。只要效率过得去，也可以得满分。但是纯粹枚举则得分不高。2.设计非递归算法实现图的深度优先遍历。（图用邻接表表示，已经定义了一个顺序栈stack[top]，top为栈顶指针，使用visit(node)来表示对顶点node的访问。）图的邻接表结构定义如下：structEdge{intdest;Edge*link;//下一条边链指针}structVertex{intdata;Edge*adj;//边链表的头指针}classGraph{private:Vertex*Nodetable;//顶点表intcnt｝解：Graph::DFS(intv)//从v开始搜索；{boolvisited[MAXVert];EdgenextEdge[MAXVert];stack[0]=v;nextEdge[0]=graph.Nodetable[v].adj;top=0;visited(stack[top]);第6页共12页visited[stack[top]]=true;while(top=0){while(nextEdge[top]&&visited[nextEdge[top]-dest])//寻找下一个尚未访问的邻接节点nextEdge[top]=nextEdge[top]-link;if(nextEdge[top]!=NULL){intnextVert=nextEdge[top]-dest;visite(nextVert);//访问下一个邻接结点；保证了被压入栈中的顶点都被访问；visited[nextVert]=true;stack[top+1]=nextVert;//压栈，进入下一个结点；nextEdge[top+1]=Nodetable[nextVert].adj;nextEdge[top]=nextEdge[top]-link;top++;}elsetop--;}}另一个数据结构试卷1、填空题。（每小题2分，本题满分20分）(1)假设用一个一维数组B来按行存放一个对称矩阵A的下三角部分，那么访问A的第i行第j列元素的语句是：_________________________________。(下标都从0开始)(2)在单链表指针P所指结点后插入指针为s的结点操作是：。(3)线性表L=(a0,a1,a2,…an-1)用数组表示，假设删除表中任一元素的概率相同，则删除一个元素所需的平均移动次数为。(4)在指针L指向一带头结点的双向循环链表，则判断该表中只有一个元素结点的条件是：(设结点结构为.)(5）使用邻接矩阵表示图时，遍历一个顶点的所有相邻顶点的时间复杂度是：_____________。(假设图的顶点个数为n,边的个数为e)(6)已知带权有向图如下，使用Dijkstra算法求解从顶点1到达各顶点的最短距离时，该算法将按照_______________________（列出顶点顺序）的顺序给出各个顶点的距离。1202303104811146912353618788(7)假设一组关键码为（20，41，22，17，19，56，35），则用堆排序的方法建立的初始最得分lLinkdatarLink第7页共12页大堆为。(8)KMP模式匹配算法的时间复杂度是：___________________________。(9)设循环队列存放在数组A[0..m-1]中，若用牺牲一个