2017年新疆师范大学计算机应用基础之数据结构(C语言版)考研复试核心题库
● 摘要
一、应用题
1． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。
图1
【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示：
图2 图3
2． 某16位计算机中，带符号整数用补码表示，数据Cache 和指令Cache 分离。题表给出了指令系统中部分指令格式，其中Rs 和Rd 表示寄存器，mem 表示存储单元地址，（X ）表示寄存器X 或存储单元X 的内容。
表 指令系统中部分指令格式
该计算机采用5段流水方式执行指令，各流水段分别是取指（IF ）、译码/读寄存器（ID ）、执行/计算有效地址（EX ）、访问存储器（M ）和结果写回寄存器（WB ）, 流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。
（1）若int 型变量x 的值为-513, 存放在寄存器R1中，则执行指令“SHR R1”后，R1的内容是多少？（用十六进制表示）
（2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，
则执行这4条指令所需的时钟周期数为多少？
（3）若高级语言程序中某赋值语句为
址分别表示为和b 均为int 型变量，它们的存储单元地该语句对应的指令序列及其在指令流水线中的执行过程如题图所示。则这4条指令执行过程中，的ID 段和的IF 段被阻塞的原因各是什么？
图 指令序列及其执行过程示意图
（4）若高级语言程序中某赋值语句为
储单元地址分别表示为
【答案】
（1）x 的机器码为
1110 1111 1111B, 即指令执行后
（2）至少需要即指令执行前（Rl ） =FDFFH, 右移lwei 后为1111 个时钟周期数。 x 和a 均为unsigned int 类型变量，它们的存则执行这条语句至少需要多少个时钟周期? 要求模仿题图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。
（3）的ID 段被阻塞的原因：因为
与和都存在数据相关，需等到和将结果写回寄存器后，才能读寄存器内容，所以的ID 段被阻塞。
的IF 段被阻塞的原因：因为14的前一条指令在ID 段被阻塞，所以，的IF 段被阻塞。
（4）对应的指令序列为：
这5条指令在流水线中的执行过程如下图所示，执行 语句最少需要17个时钟周期。
3． KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？
【答案】朴素的模式匹配度达到时间复杂度是KMP 算法有一定改进，时间复杂
主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出。
4． 将关键字序列（7, 8, 30，11，18, 9，14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是：
列法，要求装填（载）因子为0.7。
（1）请画出所构造的散列表。
（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。
【答案】（1）要求装填因子为0.7, 数组的长度应该为7/0.7=10, 数组下标为0〜9。各关键字的散列函数值如下表：
采用线性探测法再散列法处理冲突，所构造的散列表为：
（2）查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示：
故查找成功的平均查找长度为（1+1+1+1+3+3+2）/7=12/7。
在不成功的情况下，由于任意关键字key , H （key ）的值只能是0〜6之间，H （key ）为0需要比较3次，H （key ）为1需要比较2次，H （key ）为2需要比较1次，H （key ）为3需要比较2次，H （key ）为4需要比较1次，H （key ）为5需要比较5次，H （key ）为6需要比较4次，共7种情况，如下表所示：
所以，在等概率下，查找失败的平均查找长度为：（3+2+1+2+1+5+4）/7=18/7。
5． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？
【答案】（1）最高位优先（MSD ）法 先对最高位关键字进行排序，将序列分成若干子序列，
每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字进行排序，按值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序
处理冲突采用线性探测再散