资源简介：北京工业大学数据结构1996年考研真题硕士研究生入学考试试题    

        下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载

 

北京工业大学 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 分）

 

说明：本站提供的《北京工业大学数据结构1996年考研真题硕士研究生入学考试试题 》源自权威渠道，为历年考过（被使用过）的真题试卷，除标注有“回忆版”字样的试题外，其余均为原版扫描，权威可靠；回忆版试题由当年参加全国硕士、博士研究生入学考试考生回忆，内容完整。