2018年北京师范大学教育学部408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，
试写出判断表达式中括号
是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:
//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配
//s是一维数组，容量足够大，是用于存放括号的栈
//top用作栈顶指针
//'#先入栈，用于和表达式结束符号'#'匹配
//字符数组E 的工作指针
//逐字符处理字符表达式的数组
//读人其他字符，不进行处理
2． 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设
用
表示辅助地址表。初始时
减序) 算法的语句序列。
【答案】算法如下:
第 2 页，共 36 页
表示n 个结点的值，用
，在排序中，凡需对结点交换就用它的地址
来进行。例如当n=3时，对K(31，11，19) 则有T(2，3，1) 。试编写实现辅助地址表排序(按非递
一趟排序无交换发生，结束
3． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 4． 编程:假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue)，插入(enqueue)和删除(dequeue)元素的操作。 【答案】定义队列: //循环队列占m 个存储单元 //rear指向队尾元素，length 为元素个数 (1)设cq 是seQueue 类型变量，则当(2)队列的初始化: //cq为循环队列，本算法进行队列初始化 //算法结束 (3)队列的插入: 第 3 页，共 36 页 时队列空，当 时队列满。 //cq是已如上定义的循环队列，本算法将元素x 入队 //队满 . //计算插入元素位置 //将元素x 入队列 //修改队列长度 //算法结束 //cq是已如上定义的循环队列，本算法是出队算法，且返回出队元素 //队空 ；//出队元素位置 //修改队列长度 //返回队头元素 //算法结束 5． 己知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 的后继结点+ 第 4 页，共 36 页 (4)队列的删除:
相关内容
相关标签