搜索
南京邮电学院2004年攻读硕士学位研究生入学考试数据结构试题说明：1.本试卷有五类题型：单选、填空、简答、解答、和算法设计题。2,试卷共4页。所有答题均写在答题纸上（包括单选题和填空题），请务必准确标明所答题的题号。3.算法设计题使用Pascal或C/C++语言描述，但每位考生只能选用其中一种语言描述。在同一试卷中不允许混用Pascal和C/C++两种语言描述算法，你所使用的描述语言是___________（请考生填写）。4,算法（程序）中需调用其它函数或过程，必须另行编写，不允许直接调用教材上已实现的过程或函数。一、单选题（每题3分，共15分）1、从堆中删除一个元素的时间复杂度为__________。A.O(1)B.O(log2n)C.O(n)D.O(nlog2n)2、下面关于二叉树的结论正确的是__________。A.二叉树中，度为0的节点个数等于2的结点个数加1B.二叉树中结点个数必大于0C.完全二叉树中，任何一个结点的度或者为0，或者为2D.二叉树的度是2。3、对人以一棵树，设它有n个结点，这n个结点的度数之和为__________。A.nB.n-2C.n-1D.n+14、设X是树T的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是__________。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右边兄弟C.在树T中，X一定是叶子结点D.在树T中，X一定是左边兄弟5、连通的无向图G有n个顶点，则图G的最小生成树的边数为__________。A.nB.n-1C.n*(n-1)/2D.n/2二、填空题：（每题5分，共40分）1、设a=6，b=4，c=2，d=3，e=2，则后缀表达式abc-/de*+的值为____________。2、设有元素序列的入栈次序为：（a1，a2，…an），其出栈的次序为：（ap1，ap2，…apn），现已知p1=n，则p1=___________。3、设对一棵二叉树进行三种次序的遍历（结点的值为字母，大小按字母顺序），已知其中序和后序遍历的结果分别dbeafcg和debfgca，则先序遍历次序是___________。4、在有序表（22，29，33，39，42，47，50，65，68）中以对半查找方法查找元素39，40，则元素间的比较次数分别为___________和___________。5、简单选择算法的最好和最坏情况时间复杂度分别为___________和___________。6、设有一个二维数组A[m][n]（二维下标为[0..m-1，0..n-1]）。假定每个元素占一个空间，元素A[0][0]和A[2][2]的存储位置分别为644和676（十进制数），则元素A[3][3]的存储位置为___________。7、一个无向图中，存在一条从顶点u到顶点v的边，则该图的邻接矩阵A中代表该边的元素有______________________。若该图中有e条边，则图中所有顶点的度之和是___________。8、T是一个散列表，H为散列（哈希）函数，若对于关键字集合中的任意一个关键字，经散列函数H映像到地址集合中的任意一个地址的概率相等的。则称此散列函数是___________。对两个不同的关键码21kk≠，若H（k1）=H（k2）这种现象称为___________。三、简答题（每题8分，共40分）1、设元素大小按字母顺序对待，请从空树开始，通过依次插入元素（V，A，X，C，M，P）来构造一棵二叉平衡树。画出二叉平衡树的构造过程。2、图1表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能够同每个城市且总是代价最省的n-1条线路，画出所有可能的选择13254612135259871015图113、设有向图如图2所示。⑴画出其邻接矩阵⑵画出起邻接表结构⑶该图是否是强连通图4、请采用佛洛伊德（Floyd）算法求图2所示的有向图的每对顶点之间的最短路径。写出在算法执行的每一步上，保存最短路径长度的二维数组的值。5、快速排序被认为在已知的排序算法中速度较快的算法。⑴是否在所有情况下快速排序都优于直接插入排序？为什么？⑵快速排序的最坏和平均情况时间复杂度各是多少？⑶为什么说采用三者取中法选择划分（主）元素（即选择被划分的集合的最左，最右和位于（left+right）/2处的三个元素的中间值作为划分元素）可改进快速排序的性能？四、解答题（每题12分，共24分）1、设一个散列表的长度M=7，其下标从0到6。现采用线性探查法解决冲突。⑴请从空散列表开始，通过依次将下列元素插入散列表中的方式建立散列表。散列函数采用除留余数法（取余运算）。13，22，31，55，26，63⑵对于除留余数法散列函数的模M，一般应如何选择。⑶给出一种从上述散列表肿删除元素的可行且有效的方法，并说明理由。2、如图3所示的哈夫曼树可得字母F，G，H，I和J的编码。⑴设某字母串经编码后为“011101011101”，译出原串。⑵说明哈夫曼编码和ASCII编码的不同。⑶为什么采用哈夫曼编码？01321064图2210100110FCHIJ五、算法设计题（13分）设有序表以带表头结点的单链表存储。请设计一个函数（或过程），实现在该表中插入一个新元素的操作。要求插入新元素后仍未有序表。假定每个结点有两个域：element(元素)和link（指针），element为整型，link具有指向后继结点的指针类型。要求使用类型说明定义单链表结构，并实现函数（或过程）。六、算法设计题（18分）已知一棵完全二叉树中结点按层次自上而下、自左向右存储在一维整型数组A[1：n]中（设结点的值为整数）。请设计两个函数（或过程），分别实现下列功能。⑴按层次依次打印完全二叉树中所有元素，要求对每个元素以一个偶对显示（X，i），X为元素值，i为该元素在树中的层次。如元素X在完全二叉树中的层次为2，则该元素应显示为（X，2）要求设计为非递归算法。⑵按中序便利次序打印完全二叉树中各元素。每个元素仍以上述元素值和层次的偶对显示，要求设计为递归算法。