2017年辽宁工业大学电子与信息工程学院917数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）（3）（4）（5）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
2． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
3． 设数组储，则元素为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
4． 建立索引文件的目的是_____。
【答案】提高查找速度
5． 在单链表中设置头结点的作用是_____。
【答案】方便运算
第 2 页，共 51 页
的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存
的存储地址为_____；若以列序为主序顺序存储，则元素
的存储地址
6． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
7． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
8． 在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
9． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
10．设二维数组A 的行和列的下标范围分别为和每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为
【答案】时，则i=2，j=3。
当其值为
处的元素为_____。
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
二、算法设计题
11．已知非空双向链表由d 指出，结点结构为（llink ，data , rlink ），请设计算法将链表中数据域值最大（假定唯一）的那个结点移至链表的最前面。要求：不得额外申请新的双链表结点。
【答案】算法如下：
第 3 页，共 51 页
12．有n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法（注：双向起泡排序即相邻两趟排序向相反方向起泡。
【答案】算法如下：
13．设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C ，其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点（链表A 的元素类型为整型，要求B 、C 表利用A 表的结点）。
【答案】算法如下：
第 4 页，共 51 页