南京邮电大学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.一定1更多南京邮电大学考研资料尽在（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。⑴画出产生上述遍历结果的邻接表；⑵分别画出产生上述遍历结果的深度优先生成树和广度优先生成树。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