2018年北京大学软件与微电子学院831计算机基础综合[专业硕士]之数据结构考研核心题库
● 摘要
一、算法设计题
1． 己知L 为链表的头结点地址，表中共有m(m＞3) 个结点，从表中第i 个结点(l＜i ＜m) 起到第m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。
【答案】算法如下:
//L是有m 个结点的链表的头结点的指针。表中从第个结点到第m 个结点构成循环部分链表//本算法将这部分循环链表倒置
//p是工作指针，初始指向第二结点(已假定i ＞
l)
//pre是前驱结点指针，最终指向第i ﹣i 个结点
//计数器
//查找第i 个结点
//査找结束，P 指向第i 个结点
//暂存第i 个结点的指针
//p指向第i ＋l 个结点，准备逆置
//上面while 循环结束时，j ＝i ﹣1现从第i ＋1结点开始逆置
//暂存P 的后继结点
+
//逆置P 结点
//P恢复为当前待逆置结点
//计数器增
1
//将原第i 个结点的后继指针指向原第m 个结点
2． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。
【答案】算法如下:
（ ）
//统计输入字符串中数字字符和字母字符的个数
//初始化
//’#’表示输入字符串结束
'//数字字符
//字母字符
//输出数字字符的个数
("数字％d 的个数＝
//求出字母字符的个数
("字母字符％c 的个数＝
//算法结束。
3． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。
(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。
(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。
【答案】(1)算法如下:
按关键字第一个字母在字母表中的顺序输出各关键字
哈希地址
1~26
设哈希表初始值为
null
取关键字第一字母在字母表中的序号
(2)算法如下:
求链地址解决冲突的哈希表査找不成功时平均査找长度
记査找不成功的总的次数
按我们约定，査找不成功指到空指针为止
) ；
) ；
-
4． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。
【答案】算法如下:
在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回
确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情况
返回第一邻接点， 和中必有一个等于
i 取第一个边结点
5． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。
要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。
(1)试就以上图形说明:此问题有解的条件是什么？
(2)设图中的顶点数为n ，试用C 或PASCAL 语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。
【答案】(1)只有所有的顶点的度都是偶数，才能有解。
(2)算法如下:
图中顶点的最大个数
弧(边) 结点
是邻接点在顶点向量中的下标，num 是边的编号
指向下一邻接点的指针
与弧(或边) 相关的信息指针
顶点结点
顶点信息及指向第一邻接点
的指针