文档介绍：****题一
1. 简述下列术语:数据、数据元素、数据对象、数据结构、逻辑结构、存储结构、基本运算、运算实现和数据类型。
2. 设有数据结构(D, R),其中D={d1,d2,d3,d4},R={r},r={ (d1, d2 ) , (d2, d3 ) , (d3, d4 ) }. 试按图论中图的画法惯例画出其逻辑结构图。
3. 函数f(M,n)按下式定义(m,n为≥0的整数):
f (m,n)=﹛m+n+1 当m*n=0时f(m-1,(m,n-1)) 当 m*n≠0 时
(1)试写出计算该函数的递归过程;
(2)写出递归过程转换成非递归过程的转换规则。
4. 把数组 A[1…n]按递减顺序排序,并分析其最坏情况时间复杂性量级。
5. 为了用计算机实现学生档案管理, 需要经过哪些主要步骤?每个步骤的主要工作是什么?试用本章讲到的从“具体到抽象”、再“从抽象到具体”的观点加以分析。
6. 试设定若干n值,比较两函数n2和50nlog2n的增长趋势,并确定n在什么范围内,函数n2值大于50nlog2n 的值。<br****题二
设线性表存于a(1:n)的前elenum个分量中,且递增有序。试写一算法,将X插入到线性表的适当位置上,以保持线性表的有序性。
写一个逆置线性表的算法。即由A[1:n]产生B[1:n],使得 B[1]=A[n],B[2]=A[n-1] , … B[n]=A[1]。要求用最少的附加空间。
设有编号为 1,2,3,4 的四辆列车,顺序进入一个栈式结构的站台,试写出这四辆列车开出车站的所有可能顺序。
设有六辆火车编号为1,2,3,4,5,6 利用栈,将它们重新编成3,2,5,6,4,1的顺序。请写出操作序列,设X表示将一列火车从栈中开出;S表示将一列火车从输入端开入栈中。
假设栈中每个数据项占K个空间位置,试改写入栈和出栈的算法。
假设有两个栈如图所示共享空间[1..m]。试写一个对任一栈作入栈 push(s,x,i)和出栈pop(s,i)。( i = 1,2 )的算法,只有在整个[1…m]空间均满时才产生溢出。
6 题图两个栈共享一个数组示意图
按照四则运算加、减、乘、除和幂运算优先关系的惯例,画出对下列算术表达式求值时操作数栈和运算符栈的变化过程。
A-BXC/D+E↑F
假设以数组 cycque(0…m-1)存放循环队列的元素,同时设变量 rear和quelen分别表示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条件。并写出相应的入队列和出队列算法。(在出队列的算法中要返回队头元素)。
已知 Ackerman 函数的定义如下:
(1)试写出递归算法并画出 m,n 取值时工作栈状态变化情况。
(2)写出非递归算法
10. 联系现实生活理解限制存取点的线性表。限制存取点的线性表有
(1)栈和队列:本章中巳介绍.
(2)双端队列:对所有的插入和删除都限定在表的两端进行的线性表。
10题图(1)双端队列
(3 〉双栈: 规定从端 1 插入的元素只能从端 1 端删除, 而从端2 插入的元素只能从端 2 端删除。它是一种加限制的双端队列。好象两个底部相连的栈。
10题图(2) 双栈<br****题三
描述以下三个概念的区别:头指针、头结点、首元结点。
试编写在无头结点的单链表上实现线性表基本运算 LOCATE(L,X)、INSERT (L、X、i)和DELETE
(L、i)的算法,并和在带头结点的单链表上实现相同运算的算法进行比较。
试写出在不带头结点的单链表上实现线性表基本运算LENGTU(L)的算法。
试写出一个把不带头结点的单链表逆转的算法。即将链表X=(a1,a2,…,an)变成(an,an-1, … a2,a1), 且将原来指向a1 的头指针改为指向an 。(要求用修改指针的方法来实现)。
假设两个按元素值递增有序排列的线性表 A 和 B, A 和 B 表归并成一个按元素值递减有序〈允许值相同〉排列的线性表 C, 并要求利用原表〈 EP A 和 B 表〉结点空间存放表C。
设有两个线性表 x=(x1,x2, …,xm) 和 y= 〈y1, y2, …,yn 〉.均以单链表为存储结构。写出一个将 x,y 合并为线性表 z 〈也是用链表方式存储〉的算法, 使得
Z={(x1,y1,x2,y2,…xmymym+1,…yn) 当m≤n; (x1,y1,x2,y2,…xnynxn+1,…xm) 当m>n
要求: z 表利用单链表 x,y 的结点空间
已知单链表 L 中的结点是按值非递减有序排列的, 试写一算法将值为 x 的结点插入表 L 中, 使得 L 仍然有序
假设分别以两个元素值递增有序