2018年同济大学电子与信息工程学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
2． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。
【答案】算法如下:
L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符
//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表
//建立三个链表的头结点
//置三个循环链表为空表
//分解原链表
//L指向待处理结点的后继
//处理字母字符
第 2 页，共 36 页
满足下述性质
:
当且仅当存在某个顶点
且
22
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
//处理数字字符
//处理其他符号
//结束while(L!＝
null) //算法结束
3． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
算法结束
第 3 页，共 36 页
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
4． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。
【答案】算法如下:
//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前
//用类C 语言编写，数组下标从0开始
//交换A[i]与
A[j]
//算法Arrange 结束
5． 假设以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 均后移
//算法结束
二、应用题
6． 快速排序的最大递归深度是多少? 最小递归深度是多少？
【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为
第 4 页，共 36 页
，最大递归深度
相关内容
相关标签