已选分类
工学
问答题一个长度为L(L≥1)的升序序列S，处在第[L／2]个位置的数称为S的中位数。例如列S1=(11，13，15，17，19)，则S1中的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若92=(2，4，6，8，20)，则．S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度【2011年全国试题42(15)分】
问答题请列出80386的段寄存器。实地址方式下的80386同时可对多少个段进行操作?
问答题设计一个算法，将x插入到一个有序(从小到大排序)的线性表(顺序存储结构)的适当位置上，以保持线性表的有序性。
问答题二叉树按某种顺序线索化后，任一结点均有指向前驱和后继的线索，这种说法是正确的么?__________【南京理工大学2005二、9(1分)】
问答题阅读下列算法，说明程序功能，并用图示输出执行后的结果。
#include
#include
#define n 7
typedef struct Node{char data；struct Node*Lc，*Rc；)Node，*BiNode；
void unknowm(BiNode t，int i，char*a)
{t=(Node*)malloc(sizeof(Node))；
t一>data=a[i]；
if(2*iLc，2*i，a)；
else t一>Lc=NULL；
if(2*i+1Rc， 2*i+1， a)；
else t一>Rc=NULL；
)
void main()
{char a[7]; a[1]．‘a’；a[2]=。b’；a[3]="c"; a[4]=‘d’;a[5]="e"；a[6]=‘f’；
BiNode P；int j=1；
unknown(p，J，a);
}
【北京交通大学2005六、2(8分)】
问答题线性表中元素存放在向量A(1，…，n)中，元素是整型数。试写出递归算法求出A中的最大和最小元素。【北京邮电大学1994八(10分)】
问答题对于正整数n，输出其和等于n且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列，如n=4，程序输出为； 4=4 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1 test是实现该功能的C程序段，请将未完成的部分补足，使之完整。test函数为一递归函数，参数n为被分解和式的数，k为当前的分解深度。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a[]中。当其中一个分解已不再需要进一步进行时，即找到一个解，将存于a[]中的一个完整和式的和数输出。当还需要进一步分解的数及分解时，以要进一步分解的数及分解深度为参数，递归调用test函数。 #define MAXN 100 int a[MAXN]；test(Int n， lnt K] {int i，j； for(j= (1) i j>：1 j j一一) (3分) (a[k]=j； if( (2)) ) (3分) {printf(”％d=％d”? a[0]， a[1])； for(i=2；i<=k；i++) prin七f(“+％d”， a[i])； printf(“＼n”)； } else test((3);k+1)； (4分) } } main()( test(4， 1)； )【中国科学技术大学1997三、1(10分)】
问答题在一棵表示有序集S的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1，b∈S2，c∈S3是否总有a≤b≤c?为什么?【清华大学2000四(10分)】【武汉大学2000三、3】
问答题按照数据的实际情况，调整表的行高与列宽。
问答题将表达式a+b)*c+d-(e+g)*h改写成后缀表达式。 【吉林大学2007二、4(3分)】
问答题已知一图如下图所示：(1)写出全部拓扑排序；(2)以V1为源点，以V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求V1结点到各点的最短距离。【北京邮电大学2000五(15分)】
问答题设计一个算法，求出无向图G的连通分量个数，假设图中顶点标号从0到g.vexnum-1。
问答题写一个程序测试一下，存实地址方式下如果偏移超过64KB会得到什么结果?
问答题计算以t为根的二叉树中各结点中的最大元素的值，假设数据类型为float型。
问答题给定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分)】
问答题求解下面有向图的有关问题：(1)判断此有向图是否有强连通分量?若有请画出。(2)画出此有向图的十字链表存储结构；其顶点表结点结构为(data，firstin，firstout)，其中data，是顶点的有关信息；firstin是指向以该顶点为弧头的第一条边的指针；firstout是指向以该顶点为弧尾的第一条边的指针。其表结点的结构为(tailvex，headvex，weight，hlink，tlink)，其中tailvex、headvex分别为弧尾和弧头在图中的序号；weight是弧上的权值，hlink、tlink分别为指向弧头相同和弧尾相同的下一条边的指针。"(3)设其顶点a，b，c，d,e表示一个乡的5个村庄，弧上的权值表示为两村之间的距离。①求每个村庄到其他村庄的最短距离；②乡内要建立一所医院，问医院设在哪个村庄才能使各村离医院的距离较近。【北京邮电大学1997五(15分)】"
问答题如果只想在一个有n个元素的任意序列中得到其中最小的第k(k＜＜n)个元素之前的部分排序序列，那么最好采用什么排序方法?为什么?例如有这样一个序列{57，40，38，11，13，34，48，75，6，19，9，7}，要得到其第4个元素之前的部分有序序列{6，7，9，11}，用所选择的算法实现时，要执行多少次比较?
问答题VSAM(虚拟存储存取方法)文件的优点是：动态地__________，不需要文件进行__________，并能较快地__________进行查找。【山东大学2001三、4(2分)】
问答题设T是一棵高度平衡树(又称平衡树)，给定关键词K，如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在T中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。【吉林大学1996四、2(7分)】
问答题试设计一个Heaplnsert(r，key)算法，将关键字key插入到堆R中去，并保证插入后R仍是堆。并分析你的算法的时间复杂性。【哈尔滨工业大学2005五、1(15分)】