2018年温州医科大学第一临床医学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 2． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f( 【答案】算法如下: 第 2 页，共 37 页 ) 小元素。 在后半部分继续进行划分 在前半部分继续进行划分 3． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。 【答案】找的定乂: 两栈共享顺序存储空间所能达到的最多元素数 //假设元素类型为整型 ； //栈空间 //top为两个栈顶指针 //S是如上定义的结构类型变量，为全局变量 (1)入栈操作: //入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回 (2)出栈操作 //出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣ 1 为了尽量利用 空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找 //算法结束 第 3 页，共 37 页 4． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。 【答案】算法如下: //A是的矩阵，本算法求矩阵A 中的马鞍点 //max数组存放各列最大值元素的行号，初始化为行号 //min数组存放各行最小值元素的列号，初始化为列号 0 //选各行最小值元素和各列最大值元素 //修改第j 列最大元素的 行号 " 修改第i 行最小元素的 列号 //第i 行最小元素的列号 是马鞍点， 元素值是 是马鞍点 5． 设排序二叉树中结点的结构为下述三个域构成: Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。 【答案】算法如下: 非递归删除以r 为根的二叉排序树 栈，容量足够大，栈中元素是二叉排序树结点的指针 沿左分枝向下 出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间 在二叉排序树T 中删除所有小于等于x 第 4 页，共 37 页 //
相关内容
相关标签