下载文档原格式
计算机专业基础综合数据结构（排序）历年真题试卷汇编3(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：36.00)1.下面给出的四种排序法中，( )排序法是不稳定性排序法。
【北京航空航天大学1999一、10(2分)】A.插入B.冒泡C.二路归并D.堆√2.下列排序算法中，其中( )是稳定的。
【福州大学1998一、3(2分)】A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序√3.稳定的排序方法是( )。
【北方交通大学2000二、3(2分)】A.直接插入排序和快速排序B.折半插入排序和起泡排序√C.简单选择排序和四路归并排序D.树形选择排序和Shell排序4.下列排序方法中，哪一个是稳定的排序方法?( )。
【北方交通大学2001一、8(2分)】A.直接选择排序B.二分法插入排序√C.希尔排序D.快速排序5.下列排序算法中，( )是稳定排序。
【北京理工大学2007一、10(1分)】A.希尔排序B.快速排序C.堆排序D.直接插入排序√6.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。
( )就是不稳定的排序方法。
【清华大学1998一、3(2分)】A.起泡排序B.归并排序C.Shell排序√D.直接插入排序E.简单选择排序√7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。
【中科院计算所2000一、5(2分)】A.直接插入√B.直接选择C.堆D.快速E.基数8.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。
【中国科技大学1998二、4(2分)】【中科院计算所1998二、4(2分)】A.快速排序B.堆排序C.归并排序√D.直接插入排序9.下面的排序算法中，不稳定的是( )。
【北京工业大学1999一、2(2分)】A.起泡排序B.折半插入排序C.简单选择排序√D.希尔排序√E.基数排序下列内部排序算法中：【北京工业大学2000一、1(10分每问2分)】A．快速排序B．直接插入排序C．二路归并排序D．简单选择排序E．起泡排序（分数：8.00）(1).其比较次数与序列初态无关的算法是( )A.B.C. √D. √E.(2).不稳定的排序算法是( )A. √B.C.D. √E.(3).在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k<A.B. √C.D.E.(4).排序的平均时间复杂度为O(n*10gn)的算法是( )，为O(n*n)的算法是( )A. √B. √C. √D. √E. √10.排序趟数与序列的原始状态有关的排序方法是( )排序法。
《数据结构-C语言版》第一章绪论单项选择题1．在数据结构中，数据的基本单位是_____ ____。
A. 数据项B. 数据类型C. 数据元素D. 数据变量2．数据结构中数据元素之间的逻辑关系被称为__ ____。
A. 数据的存储结构B. 数据的基本操作C. 程序的算法D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。
A. 存储结构B. 逻辑和物理结构C. 逻辑结构D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。
A. 数据在内存的相对位置B. 指示数据元素的指针C. 数据的存储地址D. 指针5．计算算法的时间复杂度是属于一种____ ___。
A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。
A. n2B. nlognC. nD. logn7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。
A. O(1)B. O(n)C. O(200n)D. O(nlog2n)CDCBBDD第二章线性表单项选择题1．链表不具有的特点是____ ____。
A. 可随机访问任一元素B. 插入和删除时不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表的长度正比2．设顺序表的每个元素占8个存储单元。
第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。
A. 139B. 140C. 147D. 1483．在线性链表存储结构下，插入操作算法。
A. 需要判断是否表满B. 需要判断是否表空C. 不需要判断表满D. 需要判断是否表空和表满4．在一个单链表中，若删除p所指结点的后继结点，则执行。
A. p->next = p->next->next;B. p->next = p->next;C. p = p->next->next;D. p = p->next; p->next = p->next->next;5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。
计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编4(总分：60.00，做题时间：90分钟)一、综合题(总题数：13，分数：26.00)1.简述广义表属于线性结构的理由。
【西北大学2000一、5(3分)】（分数：2.00）__________________________________________________________________________________________ 2.数组、广义表与线性表之间有什么样的关系?【西北工业大学1998一、2(4分)】（分数：2.00）__________________________________________________________________________________________ 3.什么是广义表?请简述广义表和线性表的主要区别。
【北京大学1997二、2(5分)】（分数：2.00）__________________________________________________________________________________________4.求下列广义表的运算结果。
【南京航空航天大学1998三(10分)】(1)CAR(CDR(((a，b)，(c，d，(e，f)))(2)CDR(CAR(((a，6b)，(c，d，(e，f)))(3)CAR(CDR[(CAR(((a，b)，(e，f))))(4)CDR(CAR(CDR(((a，b)，(e，f))))(5)CDR(CDR(CAR(((a，b)，(e，f))))注：CAR运算相当于有些教材中的Head运算，CDR运算相当于Tail运算。
（分数：2.00）__________________________________________________________________________________________ 5.画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。
计算机专业基础综合数据结构（集合）历年真题试卷汇编3(总分：60.00，做题时间：90分钟)一、填空题(总题数：9，分数：18.00)1.一棵含有15个关键字的4阶B树，其非叶结点数最少不能少于__________个，最多可以为__________个。
【中国科学技术大学1997二、4(4分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：5，15(最多结点数相当于平衡二叉树，每个结点只一个关键字的两棵子树))解析：2.对于m=4(4阶)的B一树，如果根的层次为第1层，则高度为2的B一树最少要存储__________个关键字，最多可以保存__________个关键字。
【北京理工大学2005二、4(2分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：3，15。
4阶B树的每个结点(除去根结点)至少有2棵子树，至多有4棵子树。
根结点最低有2棵子树，结点内关键字个数比子树数少1。
)解析：3.具有n个关键字的B树的查找路径长度不会大于__________。
【中科院计算机1999二、2(1分)】（分数：2.00）__________________________________________________________________________________________正确答案：()解析：4.127阶B一树中每个结点最多有(1)个关键字；除根结点外所有非终端结点至少有(2)棵子树；65阶B+树中除根结点外所有结点至少有(3)个关键字；最多有(4)棵子树；【北方交通大学1999二、5(4分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)126 (2)64 (3)33 (4)65)解析：5.设高为h的m阶B一树上共有k个关键字，则其叶子结点有__________个。
![[考研类试卷]计算机专业基础综合数据结构(数组和广义表)历年真题试卷汇编2.doc](https://img.taocdn.com/s1/m/0c5d476bdd36a32d72758128.png)
[考研类试卷]计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编2一、单项选择题1 对n阶对称矩阵作压缩存储时，需要表长为( )的顺序表。
【华中科技大学2006一、2(2分)】（A）n／2（B）n2／2（C）n(n+1)／2（D）n(n-1)／22 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是( )。
【南京理工大学1999二、8(2分)】（A）60（B）66（C）18000（D）333 数组A[0．．4，一1．-3，5．．7]中含有元素的个数( )。
【中山大学1998二、5(2分)】（A）55（B）45（C）36（D）164 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为( )。
【南京理工大学2001一、1 6(1．5分)】（A）j=r[f]．next（B）j=1+1（C）j=f一>next（D）j=r[j]一>next5 一个非空广义表的表尾( )。
【北京交通大学2004一、2(2分)】（A）不能是子表（B）只能是子表（C）只能是原子（D）是原子或子表6 广义表(((a))，((b，(c)，(e(e，f)))，o)的深度是( )。
【华中科技大学2007一、7(2分)】（A）2（B）3（C）4（D）57 广义表(a，((b，(c，d(e，f)))，g)的深度为( )。
【北京邮电大学2005一、4(2分)】（A）3（B）4（C）5（D）68 广义表((a，b)，c，(d，(e))的表尾是( )。
【华中科技大学2006一、4(2分)】（A）(d，(e))（B）((d(e)))（C）e（D）(c，(d(e)))9 已知广义表(O，(a)，(b，c，(d，((d,f)))，则以下说法正确的是( )。
【华南理工大学2006一、7(2分)1（A）表长为3，表头为空表，表尾为((a)，(b，c，(d)，((d,f))))（B）表长为3，表头为空表，表尾为(b，c，(d，((d,f)))（C）表长为4，表头为空表，表尾为((d,f))（D）表长为3，表头为(O)，表尾为((a)，(b，C，(d)，((d,f))))10 已知广义表LS=((a，b，c)，(d,e，f)，运用head和tail函数取出LS中原子e的运算是( )。
计算机专业基础综合历年真题试卷汇编3(题后含答案及解析)题型有：1. 单项选择题 2. 综合应用题单项选择题1-40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
1．若无向图G=(V，E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是_______。
A．6B．15C．16D．21正确答案：C解析：要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意6个结点构成完全连通子图G1，需n(n-1)／2=6×(6-1)／2=15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。
知识模块：数据结构2．下列关于图的叙述中，正确的是_______。
Ⅰ．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路A．仅ⅡB．仅Ⅰ、ⅡC．仅ⅢD．仅Ⅰ、Ⅲ正确答案：C解析：第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，故Ⅰ错误；稀疏图是边比较少的情况，此时用邻接矩阵的空间复杂度为O(n2)，必将浪费大量的空间，而邻接表的空间复杂度为O(n+e)，应该选用邻接表，故Ⅱ错误。
存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，故Ⅲ正确。
知识模块：数据结构3．设图的邻接矩阵A如下所示。
各顶点的度依次是_______。
A．1，2，1，2B．2，2，1，1C．3，4，2，3D．4，4，2，2正确答案：C解析：邻接矩阵A为非对称矩阵，说明图是有向图，度为入度加出度之和。
各顶点的度是矩阵中此结点对应的行(对应出度)和列(对应入度)的非零元素之和。
知识模块：数据结构4．对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是_______。
计算机专业基础综合历年真题试卷汇编2(题后含答案及解析)题型有：1. 单项选择题 2. 综合应用题单项选择题1-40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
1．先序序列为a，b，c，d的不同二叉树的个数是_______。
A．13B．14C．15D．16正确答案：B解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。
因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个不同元素进栈，出栈序列的个数为C2nn=14。
知识模块：数据结构2．假设栈初始为空，将中缀表达式a／b+(c*d-e*f)／g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是_______。
A．+(*-B．+(-*C．／+(*-*D．／+-*正确答案：B解析：将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式；遇到数字时，加入后缀表达式；遇到运算符时：a．若为‘(’，入栈；b．若为‘)’，则依次把栈中的的运算符加入后缀表达式中，直到出现‘(’，从栈中删除‘(’；c．若为除括号外的其他运算符，当其优先级高于除‘(’以外的栈顶运算符时，直接入栈。
否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。
当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。
知识模块：数据结构3．在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是_______。
A．41B．82C．113D．122正确答案：B解析：设树中度为i(i=0，1，2，3，4)的结点数分别为Ni，树中结点总数为N，则树中各结点的度之和等于N-1，即N=1+N1+2N2+3N3+4N4=N0+N1+N2+N3+N4，根据题设中的数据，即可得到N0=82，即树T的叶结点的个数是82。
习题五数组和广义表一、单项选择题1．常对数组进行的两种基本操作是（）A.建立与删除B. 索引与修改C. 查找与修改D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*kB.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*kC.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*kD.Loc[i,j]=[(n+1)*i+j]*k3．稀疏矩阵的压缩存储方法是只存储 ( )A.非零元素B. 三元祖（i,j, aij）C. aijD. i,j4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
A. 1175B. 1180C. 1205D. 12105. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。
A. i（i-1）/2+jB. j（j-1）/2+iC. i（j-i）/2+1D. j（i-1）/2+16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。
A. j=r[j].nextB. j=j+1C. j=j->nextD. j=r[j]-> next7. 对稀疏矩阵进行压缩存储目的是（）。
A．便于进行矩阵运算 B．便于输入和输出C．节省存储空间 D．降低运算的时间复杂度8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。
A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))9. 广义表（（a,b,c,d））的表头是（），表尾是（）。
计算机专业基础综合数据结构（集合）历年真题试卷汇编2(总分64, 做题时间90分钟)2. 填空题1.对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________。
【北方交通大学2001二、8】SSS_TEXT_QUSTI分值: 2答案:正确答案：14计算过程如下：144／8=18块，索引表顺序查找，故(18+1)／2+(8+1)／2=14。
2.有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分成 (2) 块最为理想，平均查找长度是 (3) 。
【中国矿业大学2000一、6(3分)】SSS_TEXT_QUSTI分值: 2答案:正确答案：(1)45 (2)45 (3)46(索引表顺序查找)3.分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好；若分成25块，其平均查找长度为__________。
【北京工业大学1999一、5(2分)】SSS_TEXT_QUSTI分值: 2答案:正确答案：30，31．5(索引表顺序查找)4.执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表的存储方式是(4)。
【山东大学1998一、1(3分)】SSS_TEXT_QUSTI分值: 2正确答案：(1)顺序存储或链式存储 (2)顺序存储且有序(3)块内顺序存储，块间有序 (4)散列存储5.查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和(3)查找。
处理哈希冲突的方法有(4)、(5)、(6)和(7)。
【华北计算机系统工程研究所1999一(5分)】SSS_TEXT_QUSTI分值: 2答案:正确答案：(1)静态查找表 (2)动态查找表 (3)哈希表 (4)开放定址方法(5)链地址方法 (6)再哈希 (7)建立公共溢出区6.如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。
计算机专业基础综合数据结构（集合）历年真题试卷汇编3(总分60,考试时间90分钟)2. 填空题1. 一棵含有15个关键字的4阶B树，其非叶结点数最少不能少于__________个，最多可以为__________个。
【中国科学技术大学1997二、4(4分)】2. 对于m=4(4阶)的B一树，如果根的层次为第1层，则高度为2的B一树最少要存储__________个关键字，最多可以保存__________个关键字。
【北京理工大学2005二、4(2分)】3. 具有n个关键字的B树的查找路径长度不会大于__________。
【中科院计算机1999二、2(1分)】4. 127阶B一树中每个结点最多有(1)个关键字；除根结点外所有非终端结点至少有(2)棵子树；65阶B+树中除根结点外所有结点至少有(3)个关键字；最多有(4)棵子树；【北方交通大学1999二、5(4分)】5. 设高为h的m阶B一树上共有k个关键字，则其叶子结点有__________个。
【北京交通大学2006二、8(2分)】6. 高度为h的2-3树中叶子结点的数目至多为__________。
【西安电子科技大学1999软件一、6(2分)】7. 哈希表用__________确定记录的存储位置。
【北京理工大学2005二、5(2分)】8. 在哈希造表中，不同的关键字产生同一哈希地址的现象，称为__________。
【北京理工大学2006十、6(1分)】9. 设已知n个关键字具有相同的散列函数值，并且采用线性探测再散列方法处理冲突，将这n个关键字散列到初始为空的地址空间中，一共发生了__________次散列冲突。
【北京航空航天大学2006一、9(1分)】【西安电子科技大学2001软件一、7(2分)】6. 综合题1. 设有n个值不同的元素存于顺序结构中，试问：你能否用比(2n一3)少的比较次数选出这n个元素中的最大值和最小值?若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。
计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编3(总分66, 做题时间90分钟)6. 综合题1.数组A[1．．8，一2．．6，0．．6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4，2，3]的存储首地址。
【厦门大学1998五、1(5分)】SSS_TEXT_QUSTI2.数组A中，每个元素A[i，f]的长度均为32个二进位，行下标从一1到9，列下标从1到11，从首地址S开始连续存放在主存储器中，主存储器字长为16位。
求：(1)存放该数组所需多少单元?(2)存放数组第4列所有元素至少需多少单元?(3)数组按行存放时，元素A[7，4]的起始地址是多少?(4)数组按列存放时，元素A[4，7]的起始地址是多少?【大连海事大学1996四、1(6分)】SSS_TEXT_QUSTI3.假设按低下标优先存储整型数组A(一3：8，3：5，一4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占4字节，问A(0，4，一2，5)的存储地址是什么? 【清华大学1996三】SSS_TEXT_QUSTI4.设有五对角矩阵A=(aij )20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15，16]的存储位置。
【东北大学1999一、2(4分)】SSS_TEXT_QUSTI5.数组A[0．8，1．．10】的元素是6个字符组成的串，则存放A至少需要多少字节?A的第8列和第5行共占多少字节?若A按行优先方式存储，元素A[8，5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致?【厦门大学2000五、3(14％／3分)】SSS_TEXT_QUSTI6.设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[t+1)，1．．3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义?【北京航空航天大学1998一、5(4分)】SSS_TEXT_QUSTI设有三对角矩阵(aij )n×n将其三条对角线上的元素逐行地存于数组B(1：3n一2)中，使得s[k]=ai，j，求：SSS_TEXT_QUSTI7.用i，j表示k的下标变换公式；SSS_TEXT_QUSTI8.若n=10 3，每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元?【西安电子科技大学1996二、4(5分)】9.已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构(二维数组和三元组表)完成求运算的优缺点。
【西安电子科技大学1996二、6(5分)】SSS_TEXT_QUSTI10.特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能?为什么? 【北京邮电大学2001三、1(5分)】SSS_TEXT_QUSTI11.试叙述一维数组与有序表的异同。
【西安电子科技大学1999计算机应用一、2(5分)】SSS_TEXT_QUSTI12.给出数组A：ARRAY[3．．8，2．．6]OF INTEGER；当它在内存中按行存放和按列存放时，分别写出数组元素A[f，j]地址计算公式(设每个元素占两个存储单元)。
【南开大学1998一(8分)】SSS_TEXT_QUSTI13.已知n阶下三角矩阵A(即当i＜j时，有ao=0)，按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素aij的存放位置的公式。
【北京航空航天大学1999二(10分)】【中山大学1999三、2(5分)】SSS_TEXT_QUSTI设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1：3n一2)中，使得B[k]=aij，求：SSS_TEXT_QUSTI14.用i、j表示七的下标变换公式；SSS_TEXT_QUSTI15.用k表示i，j的下标变化公式。
【东北大学2002一(4分)】【北京工业大学2000二、1(9分)】【南京航空航天大学2000四】【山东科技大学2001一、6(6分)】【长沙铁道学院1997五、1(10分)】16.上三角阵A(N*N)按行主序压缩存放在数组B中，其中A[i，j]=B[k]。
写出用i、j表示的k。
【北京工业大学2001二、1(5分)】SSS_TEXT_QUSTI17.设有上三角矩阵(aij )n*n将其上三角中的元素按先行后列的顺序存于数组B(1：m)中，使得B[k]=aij且k=f1(i)+f2(j)+c，请推导出函数f1、f2和常数c，要求f1和f2中不含常数项。
【中科院自动化所1999】【山东科技大学2002— 5 (6分)SSS_TEXT_QUSTISSS_TEXT_QUSTI18.若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素aij(0≤i，j<4)；SSS_TEXT_QUSTI19.若将A视为稀疏矩阵，画出A的十字链表结构。
【北京科技大学1997三(10分)】设对角线矩阵SSS_TEXT_QUSTI20.若将矩阵A压缩存储到数组S中：试求出A中已存储之元素的行列下标(i，j)与S中元素的下标K之间的关系。
SSS_TEXT_QUSTI21.若将A视为稀疏矩阵时，请画出其行逻辑链接顺序表。
【北京科技大学2000三(10分)】22.假定有下列n×n矩阵(n为奇数) 如果用一维数组B按行主次序存储A的非零元素，问： (1)A中非零元素的行下标与列下标的关系； (2)给出A中非零元素aij的下标(i，j与B中的下标R的关系； (3)假定矩阵中每个元素占一个存储单元且B的起始地址为A0，给出利用aij的下标(i，j)定位在B中的位置公式。
【上海交通大学1998三(12分)】SSS_TEXT_QUSTI23.对于一个对称矩阵采用压缩存储，只存放它的上三角部分，并按列存放。
例如对于一个n*n的对称矩阵A(如右图)，用一个一维数组B来存放它的上三角部分：B=[A11 ,A12，A22，A13，A23，A33，A14，…，A1n，A2n，…，Ann]同时有两个函数：MAX(i，j)和MIN(i，j)，分别计算下标i和j中的大者与小者。
试利用它们给出求任意一个Aij在B中存放位置的公式。
(若式中没有MAX(i，j)和MIN(i，j)则不给分。
)【清华大学1997五(10分)】SSS_TEXT_QUSTI24.用三元数组表示稀疏矩阵的转置矩阵，并简要写出解题步骤。
【山东工业大学1995五(10分)】SSS_TEXT_QUSTI7. 设计题1.设有大小不等的n个数据组(n个数据组中数据的总数为m)，顺序存放在空间区D内，每个数据占一个存储单元，数据组的首地址由数组S给出(如右图所示)，试编写将新数据x插入第i个数据组的末尾且属于第i个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。
【东北大学2000六(15分)】SSS_TEXT_QUSTI2.以三元组表存储的稀疏矩阵A、B非零元个数分别为m和n。
试用类Pascal语言编写时间复杂度为O(m+n)的算法将矩阵B加到矩阵A上去。
A的空间足够大，不另加辅助空间。
要求描述所用结构。
【北京工业大学1997三(10分)】SSS_TEXT_QUSTI3.设整数x1，x2，…，xn已存放在数组A中，编写一Pascal递归过程，输出从这n个数中取出所有k个数的所有组合(k≤n)。
例：若A中存放的数是1，2，3，4，5，k为3，则输出结果应为：543，542，541，532，531，52l，432，431，421，321。
【东南大学2001三(10分)】SSS_TEXT_QUSTI4.编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。
【中科院软件所1996】SSS_TEXT_QUSTI5.请编写完整的程序。
如果矩阵A中存在这样的一个元素A[i，j]满足条件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。
请编程计算出m*n的矩阵a的所有马鞍点。
【上海大学2000三(20分)】【中科院自动化所1997】SSS_TEXT_QUSTI6.给定一个整数数组b[0．N-1]，6中连续的相等元素构成的子序列称为平台。
试设计算法，求出b中最长平台的长度。
【中科院计算所1999五、2(20分)】SSS_TEXT_QUSTI7.给定n×m矩阵A[a..b，c一d，并设A[i,j]≤A[i，j+1](a≤i≤b，c≤j≤d-1)和A[i,j]≤A[i+1，f] (a≤i≤b一1，c≤j≤d)。
设计一算法判定x的值是否在A中，要求时间复杂度为O(m+n)。
【东南大学2005四(10分)2001六(13分) 1994三(17分)】【清华大学1998六(10分)】SSS_TEXT_QUSTI8.编写算法，将自然数1～n 2按“蛇形”填入n×n矩阵中。
例(1～4 2 )如图所示(用程序实现)。
【南京航空航天大学1997八(12分)】【中科院计算所1996】SSS_TEXT_QUSTI9.设二维数组a[1一m，1.n]含有m*n个整数。
(1)写出算法(Pascal过程或c函数)：判断a中所有元素是否互不相同，输出相关信息(yes／no)；(2)试分析算法的时间复杂度。
【华中理工大学1999五(10分)】SSS_TEXT_QUSTI1。
