当前位置:问答库>考研试题

2018年复旦大学软件学院408计算机学科专业基础综合之数据结构考研核心题库

  摘要

一、算法设计题

1. 已知递增有序的单链表A ,B 分别存储了一个集合,请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ,并以同样的形式存储,同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表,本算法求两集合的差集,*n是结果集合中元素个数,初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B链表中当前结点指针后移

//处理A , B 中元素值相同的结点,

应刪除 //删除结点

2. 编写算法,将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。

【答案】算法如下:

//将自然数

,按" 蛇形M 填入n 阶方阵A 中

//i,j 是矩阵元素的下标,k 是要填入的自然数

//从右上向左下填数

//副对角线及以上部分的新i ,j 坐标

//副对角线以下的新的i ,j 坐标

//从左下向右上

//最外层

while

3. 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空,入桟和出找的操作序列可表示为仅由I 和0组成的序列,称可以操作的序列为合法序列,否则称为非法序列。

(1)下面所示的序列中哪些是合法的?

A.

B.

C.

D.

(2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true ,否则返回false(假定被判定的操作序列已存入一维数组中) 。

【答案】(1)A和D 是合法序列,B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中,算法如下:

//判断字符数组A 中的输入输出序列是否是合法序列。

//i为下标

//j和k 分别为I 和字母O 的个数

//入栈次数增

1

//不论A[i]是’I'或’〇' ,指针i 均后移

//算法结束

4. 写算法将单链表11拆成二个链表,其中以11为头的链表保持原来向后的链接,另一个链表的头为12,其链接方向与11相反,11包含原链表的奇数序号的结点,12包含原链表的偶数序号的结点。

【答案】算法如下:

//本算法将链表L1拆成L1和L2两个链表,L2链接方向与L1相反

//空链表

//奇数序号结点在L1中

//偶数序号

结点逆置插入到L2中

//置L1表尾

5. 结点类型和存储结构如下:

试设计一个排序算法,要求不移动结点的存储位置,只在结点的count 字段记录结点在排序中的序号,并将排序结果按升序输出。

【答案】算法如下:

对存储在数组R 中的记录进行排序

初始化

设R[0]作监视哨,Max 是该类型最大元

初始假定第一个元素有序

前驱

第一个元素

査找第i 个元素的序号

将笫i 个元素链入静态链表

二、应用题