已选分类
工学
问答题表插入排序的基本思想是在结点中设一指针字段，插入Ri时Rl到Ri一1已经用指针按排序码不减次序链接起来，这时采用顺序比较的方法找到Ri应插入的位置，做链表插入。如此反复，直到把Rn插入为止。【山东工业大学2000五(16分)】【山东大学1998五】(1)(6分)请完成下列表插入的算法； ①R[0]LINK←(1))；R IN]．LINl←(2)； ②循环，I以一1为步长，从(3)到(4)执行A.p←R[0]．LINK; Q←0B.循环，当P>0且(5) 时，反复执行 Q←P； P←(6)C.R[Q]．LINK←I； R[I]LINK←p (2)(2分)表插入排序的最大比较次数是(7) ； (3)(2分)表插入排序的最小比较次数是(8) ； (4)(2分)记录移动的次数是(9)； (5)(2分)需要附加的存储空间是(10)； (6)(2分)该排序算法是否是稳定的(11)。
问答题检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按__________检索，也可以按__________检索；按__________检索又可以有__________检索和__________检索。【山东大学1999一、1(5分)】
问答题以下程序输出的结果是:
#include "stdio.h"
void main()
{
char s[]="\"hello\"";
printf("%s",s);
｝
问答题对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。
typedef struct node
{int data； struct node*next；
}linknode，*link；
voidInsertsort(1ink L)
{link P，q，r，u；
p=L一>next;(1)；
while((2) )
{r=L; q=n->next;
while((3) ＆&q一>datadata){r=q； q=q一>next；}
u=p一>nextj (4)；(5)；p=u；
}
}【北京科技大学2001二(10分)】
问答题试写出把图的邻接矩阵表示转换为邻接表表示的算法。【哈尔滨工业大学2002七(8分)】【中山大学1998五、2(10分)】【南开大学2000三、3】【北京邮电大学2006五、3(10分)】
问答题请写一非递归算法，该算法在按值严格递增排序的顺序表A【1…n】中采用折半查找法查找值不小于item的最小元素。若表中存在这样的元素，则算法给出该最小元素在表中的位置，否则，给出信息0。【北京航空航天大学2007年】
问答题每次使两个有序表合并成一个有序表，这种排序方法叫做__________排序。【哈尔滨工业大学2005一、6(1分)】
问答题设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data(数据)和next(后继指针)域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L，x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增(递减)的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学1997二(10分)】【苏州大学2004四(15分)】【江苏大学2006四、2(13分)】
问答题设二维数组a[1一m，1.n]含有m*n个整数。(1)写出算法(Pascal过程或c函数)：判断a中所有元素是否互不相同，输出相关信息(yes／no)；(2)试分析算法的时间复杂度。【华中理工大学1999五(10分)】
问答题已知两个各包含N和M个记录的排好序的文件能在O(N+M)时间内合并为一个包含N+M个记录的排好序的文件。当有多于两个排好序的文件要被合并在一起时，只需重复成对地合并便可完成。合并的步骤不同，所需花费的记录移动次数也不同。现有文件F1，F2，F3，F4，F5，各有记录数为20，30，10，5和30，试找出记录移动次数最少的合并步骤。【重庆大学2000二、3】
问答题线性表有两种存储结构：一是顺序表，二是链表。试问：
问答题已知在一棵含有n个结点的树中，只有度七的分支结点和度为0的叶子结点，求该树含有的叶子结点数。【大连理工大学2005二、2(20／4分)】【江苏大学2004三、5(6分)】
问答题解答下面的问题：
问答题设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为__________。【重庆大学2000一、4】
问答题已知由n一1个关键字组成的序列(K
1
,K
2
,K
3
…K
n-1
)是大顶堆，现在再增加一个关键字K
n
，要求将关键字序列(K
1
,K
2
,K
3
,…，K
n-1
，K
n
)重新调整为大顶堆。请完成以下要求：
(1)编写满足上述要求的算法。
(2)简述你所编写的算法的基本思想。
(3)分析你所编写的算法的时间复杂度。
【南京航空航天大学2006 7(5分)】【江苏大学2006四、1(12分)】
问答题假设二维数组A的维界为[一2…7,3…6]，当它在内存中按行存放和按列存放时，分别写出数组元素A[i，j]的地址计算公式(设每个元素占两个存储单元)。
问答题设输入序列为a，b，c，d，试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。【北京科技大学2001一、4(2分)】
问答题以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。【华南师范大学1999四(10分)】
问答题假设数据段的定义如下： P1 DW? P2 DB 32 DUP(?) PLENTH EQU S-P1试问PLENTH的值为多少?它表示什么意义?
问答题若CS=8000H，试说明现行代码段可寻址的存储空间的范围。