2005年南邮考研数据结构考研试卷

南京邮电学院2005年攻读硕士学位研究生入学考试数据结构试题一、单选题（每题3分，共30分）1.设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000则该算法的渐进时间复杂度为。A.O(1)B.O(n)C.O(200n)D.O(nlog2n)2.设顺序表的长度为n，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是。A.(n－1)/2B.n/2C.n(n－1)/2D.n(n＋1)/23.如果只保存一个n阶对称矩阵a的下三角元素（含对角线元素），并采用行主序存储在一维数组b中，a[i][j]（或a[i,j]）存于b[k]，则对ij，下标k与i，j的关系是。设一维数组和矩阵元素的行列下标取值均从0开始。A.(1)2iij++B.(1)2jji++C.(1)2iij−+D.(1)2jji−+4.一棵三叉树中，已知度为3的结点个数等于度为2的节点数，且树中结点的数目为13，则度为2的结点数目为。A.4B.2C.3D.55.在基于关键字比较的排序算法中，算法在最坏情况下的时间复杂度不高于O（nlog2n）。A.冒泡排序B.合并排序C.希尔排序D.快速排序6.已知一棵由关键字集合{18，43，27，77，44，36，39}所构造的二叉搜索树（也称为二叉排序树），对该树进行中序遍历得到的节点序列为。A.树形未定B.18，43，27，77，44，36，99C.18，27，36，39，43，44，77D.77，44，43，39，36，27，187.一个索引文件，如果经常需要插入和删除元素，宜采用做索引。A.二叉排序树B.二叉平衡树C.B-树D.B+树8.均匀的散列函数应当使关键字集合中的元素，经过散列函数映射到散列表中任何位置的概率。A.相等B.最小C.最大D.一定19.关键路径是指AOE（ActivityOnEdge）网中。A.二叉排序树B.二叉平衡树C.B-树D.B+树10.堆可以是最大堆，也可以是最小堆。下列序列中，既不是最大堆，也不是最小堆。A.（90，85，78，67，56，42，35，24，18）B.（18，35，56，24，42，78，67，85，90）C.（90，78，85，56，67，35，42，18，24）D.（18，35，24，56，42，78，67，85，90）二、填空题（每题6分，共42分）1.设有n个顶点的有向图采用邻接矩阵表示，并保存在二维数组a中，则求第i个顶点的入度和出度的计算公式分别是⑴和⑵。2.设有20个元素构造二叉平衡树，其最大和最小高度分别是⑶和⑷。3.某二叉树结点的中序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树的先序序列为⑸，该二叉树对应的森林中包括⑹棵树。4.对一个有向图进行拓扑排序，输出的拓扑序列不能包括图中全部顶点，表明此图⑺。如果此图代表一个工程之间的领先关系，当算法执行出现上述情况时，应当检查⑻。5.设对主串“bcdbcdcabcdbcdbac”和模式串“bcdbcbd”进行KMP模式匹配。第1趟匹配失败后，若使用非改进的Next函数，则下一趟将由主串的第⑼字符与模式串的第⑽字符开始比较。若采用改进的Next函数，则下一趟匹配将由主串的第⑾字符与模式串的第⑿字符开始比较。字符串中字符从1开始编号。6.假定散列表使用除留余数法散列函数H，key为关键字，模为M，则该散列函数的形式为⒀。若采用移位折叠法散列函数，散列地址取3位，设key=43256789654，则所得的散列函数值为⒁。7.在将中缀表达式转换为后缀表达式和计算后缀表达式的算法中，都需要使用堆栈。对于前者，进入堆栈的元素为表达式中的⒂，而对于后者，进入堆栈的元素为⒃。中缀表达式(a+b)/c-(f-d/e)所对应的后缀表达式是⒄。三、解答题（每题8分，共48分）1.已知有向图如图1所示，并已建成该图的邻接表。使用该邻接表对此图进行深度优先遍历时，结点被访问的次序是：1，3，2，5，6，4；对其进行广度优先遍历时，结点被访问的次序是：1，3，2，4，6，5。⑴画出产生上述遍历结果的邻接表；⑵分别画出产生上述遍历结果的深度优先生成树和广度优先生成树。21图12.设无向图如图2所示，现采用克鲁斯卡尔算法求最小代价生成树。再加入一条新边时，为了判定是否会因此形成回路，可以使用并查集（该数据结构也用于求等价关系问题）。⑴画出所生成的最小代价生成树；⑵给出在算法执行中，当生成树上有5条边时的并查集的状态。图23.设有数据元素的有序序列（22，32，35，44，48，51，57，60），⑴现采用对半查找方法查找60，请按比较的次序，列出与60做比较的表中元素；⑵对半查找方法要求元素序列采用何种存储表示方法。4.关于图3所示的4阶B-树，回答下列问题：⑴依次插入关键字70和85，画出插入后的B树。⑵依次删除关键字14和16，画出删除后的B树（仍从原图３中删除）。⑶你认为用于存储B-树中每个结点的存储块的大小是否应相同，为什么？401449585164253606372图35.使用快速排序算法对元素序列（23，43，36，30，20，54，76，28）进行排序。⑴写出对上述序列进行第一趟排序后的结果；⑵待排序的元素序列处于什么状态时快速排序所需时间最长？⑶采用什么措施可改善快速排序的最坏情况时间性能？6.设二叉搜索树如图4所示，⑴在该树上插入元素35，画出插入后的二叉搜索树；53246125437643752748383⑵从⑴所生成的树上删除25，画出删除后的二叉搜索树。25204329553732图4四、算法设计题（共30分）1.(12分)设计一个算法，按元素值的“非增”次序，打印一棵二叉搜索树（也称二叉排序树）的元素。设二叉搜索树采用二叉链表存储，每个结点有三个域：lchild,rchild,data。算法中，除二叉链表中原有的结点空间外，只允许使用若干指针变量，不允许使用额外的元素空间。2.（18分）已知无向图采用邻接矩阵表示，但该邻接矩阵不使用二维数组存储，而今使用一维数组g保存邻接矩阵的下三角部分元素（不含对角线元素）。请设计一个或多个函数（或过程），求无向图的各连通分量的顶点集。4