《2017年南京工业大学数据结构(同等学力加试)考研复试核心题库.doc》由会员分享，可在线阅读，更多相关《2017年南京工业大学数据结构(同等学力加试)考研复试核心题库.doc（3页珍藏版）》请在金锄头文库上搜索。
1、2017年南京工业大学数据结构(同等学力加试)考研复试核心题库一、应用题1 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。 图1【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示： 图2 图3 2 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到1
2、35426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。3 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）于表示栈号，x 为入栈值。，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）共享数组为SMAX，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用
3、C 语言写的入栈操作push （i ，x ）如下： 4 已知图的邻接矩阵为： 当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出： （1）以顶点V1为出发点的唯一的深度优先遍历序列； （2）以顶点V1为出发点的唯一的广度优先遍历序列； （3）该图唯一的拓扑有序序列。1）V1，V4，V9, V10，V7, V6, V8，V3，V2, V5 【答案】（2） V1, V4, V3, V2, V9, V7, V6, Y5, V10, V8 （3） V1, V2, V5, V3, V4, V6, V8, V7, V9, VIO 5 设将n （n l ）个整数存放到一维数组R 中。试设计一
4、个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P （0P n ）个位置，即将R 中的数据由变换为（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或或JA V A 语言描述算法，关键之处给出注释。原地逆置，得到（3）说明你所设计算法的时间复杂度和空间复杂度。 【答案】（1）算法的基本设计思想：先将n个数据由然后再将数组R 中的前， （2）用C 语言算法描述如下： 要求：个数和后P 个数分别原地逆置，最终得到结果 （3）说明算法的复杂性：上述算法中3个Reverse 函数的的时间复杂度分别为为O故算法的时间复杂度为，算法的空间复杂度为0（1）。 6 下面程序段的时间
5、复杂度是什么？ 【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。7 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：（1）归并排序，每归并一次书写一个次序。 （2）快速排序，每划分一次书写一个次序。（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 【答案】（1）2路归并第一趟：18，29，25，47，12，58，10，51: 第二趟：18，25，29， 47，10，12，51，58; 第三趟：10，12，18，25，29，47，51，58（2）快速排序第一趟：10，18，25，12，29，58，51，47; 第二趟：10，18，25，12，29，47，51，88; 第三趟：10，12，18，25，29，47，51，88 （3）堆排序建大堆：58，47，51，29，18，12，25，10; 51，47，25，29，18，12，10，58; 47，29，25，10，18，12，51，58; 29，18，25，10，12，47，51，58; 25，18，12，10，29，47，51，58;一、应用题考研试题
