|
北京工业大学 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 分）
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
