|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
北京工业大学 1996 年硕士研究生入学考试试题
考试科目：数据结构
要求说明
1．要求书写算法的题目可用类 Pascal 语言描述，为表达你的设防意图，请扼要的说明算法
思想并适当加注说明语句。
2．
试题：
3．试卷与答题必须分开，不能在试卷上答题。
进行快速排序，写出排序过程中每一趟的数据变化情况。
如下一组关键字表
4．共五道题，满分 100 分。
一．（共 30 分，每小题 6 分）
（1）（6 分） 如下一组关键字表
25，67，18，24，38，64，55，22，15，48，31．
进行快速排列，写出排序过程中每一趟的数据变化情况。
（2）（6 分）对如图的邻接表，从顶点 V2 开始进行深度优先搜索，写出 dfs
遍历时访问顶点的顺序。
（3）（6 分） 画出具有共享结构广义表（（（b,c）,d）,(a),((a),((b,c),d)),e,()）的存贮表。
（4）（6 分） 用一维存放的一棵完全二叉树如下图示：
A B C D E F G H I J K L
写出后序遍历该二叉树时访问结点的顺序。
（5）（6 分） 两个字符串 S1 和 S2 的长度分别为 m 和 n。求这两个字符串最大共同字
串算法的时间复杂度为 T(m,n)，估量最优的 T(m,n)，并简要说明理由。
二 .（15 分） 一个无向连通图的存贮结构以邻接表的形式给定，设计算法删除该图中的一
条边(i,j)。
三.（15 分） 在一个递增有序的线性表中标，有数值相同的元素存在。若存贮方式为单链
表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：
（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分
析算法的复杂度。
四．（20 分）
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
