2017年西南民族大学计算机导论之数据结构(C语言版)考研复试核心题库
● 摘要
一、应用题
1． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。
【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。
2． 用单链表保存m 个整数，节点的结构为（data , link ）, 且点而删除其余绝对值相等的节点。
例如若给定的单链表head 如下
删除节点后的head 为
要求
（1）给出算法的基本思想 （2）使用c 或
语言，给出单链表节点的数据类型定义。
语言描述算法，关键之处给出注释。
（3）根据设计思想，采用c 或【答案】（1）算法思想：
定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。
（2）节点的数据结构定义如下：
第 2 页，共 41 页
（n 为正整数）。现要求
设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节
（4）说明所涉及算法的时间复杂度和空间复杂度。
（3）
则删除该节点
全局数组标志节点的绝对值是否出现过
如果此绝对值已经在节点值的绝对值中出现过
否则，将flag 中对应的位置置为true ，并将指针指向下一个元素
，申请大小（4）只遍历一次链表，所以时间复杂度为0 （m ） （m 为单链表中元素的个数）
为n 的数组，所以空间复杂度为0 （n ） （n 为节点绝对值的最大值）。
3． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：
（1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。 （2）当n=7时，给出一个最好情况的初始排序的实例。 （3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。 （4）当n=7时，给出一个最坏情况的初始排序的实例。
【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为以此类推，
总共进行需2次，共10次即可。
（2）在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。
（3）在最坏情况下，若每次用来划分的记录的关键字具有最大（或最小）值，那么只能得到左（或右）子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递増次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为n=7时，最坏情况下的比较次数为21次。
（4）在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递増排序。
第 3 页，共 41 页
的子文件，第二趟划分得到4个长度均为的子文件，
趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，
在最好情况下，第一趟需比较6次，第二趟分别对两个子文件（长度均为3，k=2）进行排序，各
所以当
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． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B , 数据Cache 采用直接映射方式。现有两个功能相同的程序A 和B , 其伪代码如下所本：程序A :程序B :
假定int 类型数据用32位补码表示，程序编译时i , j , sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。
（1）若不考虑用于Cache —致性维护和替换算法的控制位，则数据Cache 的总容量为多少？ （2）数组数据号从0开始）？
（3）程序A 和B 的数据访问命中率各是多少? 哪个程序的执行时间更短？
【答案】（1）每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位。由主存空间大小为256M 可知地址总长度为28位，其中块内地址为log264=6位，Cache
第 4 页，共 41 页
和各自所在的主存块对应的Cache 行号分别是多少（Cache 行
相关内容
相关标签