2018年长江大学软件工程408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。
【答案】算法如下:
在用邻接表方式存储的无向图g 中，删除边(i,
j)
删顶点i 的边结点(i, j) , pre 是前驱指针
释放空间
沿链表继续査找
删顶点j 的边结点(j,
i)
释放空间
沿链表继续査找
2． 编程:假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue)，插入(enqueue)和删除(dequeue)元素的操作。
【答案】定义队列:
//循环队列占m 个存储单元
//rear指向队尾元素，length 为元素个数
(1)设cq 是seQueue 类型变量，则当(2)队列的初始化:
//cq为循环队列，本算法进行队列初始化
//算法结束
第 2 页，共 37 页
时队列空，当 时队列满。
(3)队列的插入:
//cq是已如上定义的循环队列，本算法将元素x 入队
//队满
.
//计算插入元素位置
//将元素x 入队列
//修改队列长度
//算法结束
(4)队列的删除:
//cq是已如上定义的循环队列，本算法是出队算法，且返回出队元素
//队空
；//出队元素位置
//修改队列长度
//返回队头元素
//算法结束
3． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 第 3 页，共 37 页 4． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数， 当 时，将 入栈；当 时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给 出相应的信息。 【答案】算法如下 : 栈空间容量 //s是元素为整数的栈，本算法进行入栈和出栈操作 //top为栈顶指针，定义top ＝0时为栈空 //n个整数序列进行处理 //从键盘读入整数序列 //读入的整数不等于﹣1时人栈 //读入的整数等于﹣1时出栈 //算法结束。 5． 写出按后序序列遍历中序线索树的算法。 【答案】算法如下: 求结点t 最左子孙的左线索 沿左分支向下 求结点t 最右子孙的右线索 沿右分支向下 若t 是 后序遍历中序线索二叉树 bt 沿左分支向下 左孩子为线索，右孩子为链，相当从左返回 P 为叶子, 相当从右返回 第 4 页，共 37 页 的右孩子，返回1, 否则返回
相关内容
相关标签