吉林省数据结构专升本习题

1、概论1、评价一个算法时间性能的主要标准是(算法的时间复杂度)。 2、算法的时间复杂度与问题的规模有关外，还与输入实例的(初始状态)有关。3、一般，将算法求解问题的输入量称为(问题的规模)。4、在选择算法时，除首先考虑正确性外，还应考虑哪三点?答：选用的算法首先应该是正确的。此外，主要考虑如下三点： 执行算法所耗费的时间； 执行算法所耗费的存储空间，其中主要考虑辅助存储空间； 算法应易于理解，易于编码，易于调试等等。6、下列四种排序方法中，不稳定的方法是(D ) A、直接插入排序B、冒泡排序C、归并排序D、直接选择排序7、按增长率由小至大的顺序排列下列各函数：2100, (3/2)n，(2/3)

2、n，nn ,n0.5 , n! ，2n ，lgn ,nlgn, n3/2 答：常见的时间复杂度按数量级递增排列,依次为: 常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。先将题中的函数分成如下几类：常数阶：2100对数阶：lgnK次方阶：n0.5、n3/2指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn注意：(2/3)n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。根据以上分析

3、按增长率由小至大的顺序可排列如下：(2/3)n 2100 lgn n0.5 n3/2 nlgn (3/2)n 2n n! nn 8、常用的存储表示方法有哪几种? 常用的存储表示方法：顺序存储方法、链接存储方法、索引存储方法、散列存储方法。9、设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要（15）。二、线性表1、以下关于线性表的说法不正确的是(C )。 A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。D、存在这样的线性表：表中各结点都没有直接前

4、趋和直接后继。2、线性表是一种典型的(线性)结构。3、线性表的逻辑结构特征是什么?答：对于非空的线性表: 有且仅有一个开始结点A1，没有直接前趋，有且仅有一个直接后继A2； 有且仅有一个终结结点AN，没有直接后继，有且仅有一个直接前趋AN-1； 其余的内部结点AI（2IN-1）都有且仅有一个直接前趋AI-1和一个AI+1。4、线性表的顺序存储结构是一种(随机存取)的存储结构。5、在顺序表中，只要知道(基地址和结点大小)，就可在相同时间内求出任一结点的存储地址。 6、在等概率情况下，顺序表的插入操作要移动(一半)结点。 7、在一个长度为n的顺序表中删除第i个元素，要移动( n-i)个元素8、如果

5、要在第i个元素前插入一个元素，要后移(n-i+1 )个元素。9、采用(顺序)存储结构的线性表叫顺序表。10、 顺序表中逻辑上相邻的元素的物理位置(相邻 )。11、在(C )运算中，使用顺序表比链表好。 A、插入 B、删除 C、根据序号查找D、根据元素值查找12、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(O(n) )。 13、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在(前趋)结点的next域中。14、在(循环)链表中，从任何一结点出发都能访问到表中的所有结点。15、(双向 )链表适合从指点结点开始，寻找直接前趋的运算。16、顺序表

6、相对于链表的优点有节省存储和随机存取。17、在链表的开始结点前设置头结点的优点是什么？答：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:（1）、由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;（2）、无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。18、(双向链表 )适合作为经常在首尾两端操作线性表的存储结构。19、如果线性表的存储空间变化较大，则适合用(链)表。20、当线性表的数据变化不大，主要用于查询时，用(顺序)表比较好。21、在链表中，每个

7、结点中含8个字符，1个指针域。其中每个字符占1个字节，每个指针占4个字节。则该结点的存储密度是(2/3)。 (1+1+4)/(8+1)=2/3 存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）22、链表相对于顺序表的优点有插入和删除操作方便。23、在n个结点的顺序表中插入一个结点需平均移动n/2个结点，具体任务的移动次数取决于表长n和插入位置i。24、在n个结点的顺序表中删除一个结点需平均移动（n1）/2个结点，具体任务的移动次数取决于表长n和删除位置i。25、尾指针是指向终端结点的指针查找时间都是O(1)，用头指针来表示该链表，则查找终端结点的时间为O(n)。补充：1、 顺

8、序表上实现的基本运算：表的初始化、求表长、取表中第i个结点三种运算的时间复杂度都为O(1)。2、顺序表插入操作算法分析 问题的规模 表的长度L-length（设值为n）是问题的规模。 移动结点的次数由表长n和插入位置i决定 算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。 当i=n+1：移动结点次数为0，即算法在最好时间复杂度是0(1) 当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是0(n) 移动结点的平均次数Eis(n) 其中： 在表中第i个位置插入一个结点的移动次数为n-i+1 pi表示在表中第i个位置上插入一个结点的概率。不失一般性，假设在表中

9、任何合法位置（1in+1）上的插入结点的机会是均等的，则 p1=p2=pn+1=1/(n+1) 因此，在等概率插入的情况下， 即在顺序表上进行插入运算，平均要移动一半结点。3、顺序表删除操作算法分析结点的移动次数由表长n和位置i决定： i=n时，结点的移动次数为0，即为0(1) i=1时，结点的移动次数为n-1，算法时间复杂度分别是0(n)移动结点的平均次数EDE(n) 其中：删除表中第i个位置结点的移动次数为n-i pi表示删除表中第i个位置上结点的概率。不失一般性，假设在表中任何合法位置（1in）上的删除结点的机会是均等的，则 p1=p2=pn=1/n 因此，在等概率插入的情况下， 顺序表

10、上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。4、单链表的运算：头插法建表、尾插法建表、尾插法建带头结点的单链表三个算法的时间复杂度均为0(n)。5、单链表的查找运算：按序号查找、按值查找其平均时间复杂度为O(n)。6、单链表的插入运算：算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O(n)。7、单链表的删除运算：算法的时间复杂度也是O（n）。8、循环链表：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其

11、执行时间是O(1)。9、双向链表的前插和删除本结点操作：两个算法的时间复杂度均为O(1)。10、结点ai 的存储地址 不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址（简称为基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算：LOC（ai）= LOC（a1）+（i-1）*c 1in顺序表 链表基于空间考虑分配方式静态分配。程序执行之前必须明确规定存储规模。若线性表长度n变化较大，则存储规模难于预先确定估计过大将造成空间浪费，估计太

12、小又将使空间溢出机会增多。动态分配只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。存储密度为1。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。top=maxsize-1 )。5、向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行(S-next=HS-next;HS=s; )。 6、若已知一个栈的入栈序列是1，2，3，n，其输出序列是p1,p2,p3，pn，若p1=n，则pi=(n-i+1 )。 7、在栈中，可进行插入和删除操作的一端称(栈顶 )。8、在栈的出栈操作中，

13、要先判断栈是否空，否则会产生(下溢 )现象。9、当程序中同时使用(2 )个栈时，让它们共享同一向量空间可减少上溢的发生。10、栈的特点是(后进先出 )。当问题满足(先进后出)原则时可使用队列作数据结构。当问题满足(后进先出)原则时可使用栈作数据结构。11、由于链栈的操作只在链表头部进行，所以没有必要设置(头 )结点。12、若内存空间充足，(链 )栈可不定义栈满运算。13、一个队列的入列序列是1 2 3 4，则队列的输出序列是(1 2 3 4)。 14、队列与一般的线性表的区别在于(运算是否受限制 )。15、“假上溢”现象会出现在(顺序队列 )中。16、在一个链队中，假设F和R分别是队首和队尾指

14、针，则删除一个结点的运算是(F=F-next; )。 17、假设以数组sequm存放循环队列，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含的元素个数，则判别队满的条件是(quelen=m )。18、为了克服“假上溢”，一般可用(循环 )向量存储队列中的元素。19、在顺序队列中，若队列非空，(队头 )指针指向队头元素,队尾指针指向队尾元素的下一位置。20、循环队列采用的是(顺序)存储结构。21、设F和R是循环队列的队头指针和队尾指针，则判断队空的条件是(F=R )。22、在(队列中只有一个元素 )情况下，链队列的出队操作需要修改尾指针。23、说出解决循环队列中，判断队空

15、和队满情况的三种方法。答： 另设一布尔变量以区别队列的空和满； 少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：REAR所指的单元始终为空）； 使用一个计数器记录队列中元素的总数（实际上是队列长度）。24、设计一个判别表达式中左、右括号是否配对出现的算法，采用(线性表的顺序存储结构)数据结构最佳。25、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于(栈 )数据结构。26、计算机在运行递归程序时，要用到(系统)提供的栈。27、什么是递归算法?设计递归算法要分哪两个步骤？答：所谓递归是指：若在一个函数、过程或者数据结构定义的内部又直接

16、（或间接）出现有定义本身的应用，则称它们是递归的，或者是递归定义的。递归算法的设计步骤第一步骤（递归步骤）：将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题；第二步骤：确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件）。28、在栈结构中，允许插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。29、在有n个元素的栈中，进栈和退栈操作的时间复杂度为O(1)和O(1)。30、在队列结构中，允许插入的一端称为队尾，允许删除的一端称为队头。31、设长度为n的链队列用

17、单循环链表，若只设头指针，则入队和出队操作的时间复杂度分别为O(n)和O(1)；若只设尾指针，则入队和出队操作的时间复杂度分别为O(1)和O(1)。32、设循环向量有m个元素，循环向量中有一个循环队列。在循环队列中，设头指针front指向队头元素，队尾指针指向队尾元素后的一个空闲元素。（1）在循环队列中，队空标志为front=rear；队满标志为front=(rear+1)%QueueSize。（2）当rear=front时，队列长度为rear-front；当rearfront；队列长度是rear+Queue-front；33、设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作

18、按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Po

19、p()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,431234、指出下述程序段的功能是什么?(1) void

20、 Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i n; i+) Push(S, arri); /Demo1答：程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。(2) SeqStack S1, S2, tmp;DataType x;./假设栈tmp和S2已做过初始化while ( ! StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( ! StackE

21、mpty (&tmp) )x=Pop( &tmp);Push( &S1,x);Push( &S2, x);答：程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。(3) void Demo2( SeqStack *S, int m) / 设DataType 为int 型SeqStack T; int i;InitStack (&T);while (! StackEmpty( S)if( i=Pop(S) !=m) Push( &T,i);while (! StackEmpty( &T)i=Pop(&T); Push(S,i);答：程序段的功能是利用栈T，将一个非空

22、栈S中值等于m的元素全部删去。(4)void Demo3( CirQueue *Q) / 设DataType 为int 型int x; SeqStack S;InitStack( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x );/ Demo3答：程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。(5) CirQueue Q1, Q2; / 设DataType 为int 型int x, i

23、 , n= 0;. / 设Q1已有内容， Q2已初始化过while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n+;for (i=0; i n; i+) x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2, x);答：这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。补充：1、 顺序栈的基本操作 前提条件： 设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S-data0是

24、栈底元素。（1） 进栈操作 进栈时，需要将S-top加1 注意： S-top=StackSize-1表示栈满上溢现象-当栈满时，再做进栈运算产生空间溢出的现象。 上溢是一种出错状态，应设法避免。（2） 退栈操作 退栈时，需将S-top减1 注意：S-top=0)的存储地址为( A )，若首地址为D，则Ai的存储地址为( B )。答：A-(1+S*I) B-(D+S*I)3、已知二维数组Amn采用行优先顺序存储，每个元素占k个存储单元，并且第一个元素的存储地址LOC（A00），则Aij的地址是(1+(n*i+j)*k )。4、在多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，数

25、组是一种(随机 )存取结构。5、稀疏矩阵的一般的压缩方法有(三元组表)。6、设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分按行优先存放在一维数组B中。对下三角矩阵中任一元素aij(设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分按行优先存放在一维数组B中，对下三角矩阵中任一元素aij(i=j)，在一维数组B中下标K的值是(D )。 A、i(i-1)/2+j-1 B、i(i-1)/2+j C、i(i+1)/2+j-1 D、i(i+1)/2+j7、在稀疏矩阵的三元组表表示法中，每个三元组表示(矩阵中非零元素的行号、列号和值 )。 8、对稀疏矩阵进行压缩存储是为了(节约存储空间 )。 9、

26、矩阵的压缩存储就是为多个相同的非零元素分配(1 )个存储空间，不为零元素分配空间。10、一般，特殊矩阵按规律压缩存储到一个向量中后，能(随机 )存取。11、广义表是线性表的推广，它们之间的区别在于(能否使用子表)。12、在广义表中，限制了表中成分递归，但没有限制共享的是(再入表 )。13、广义表(a),(b),c),(d)的表头是(a )。广义表(a),(b),c),(d)的表尾是(b),c),(d) )。广义表(a),(b),c),(d)的深度是(4 ) 。广义表(a),(b),c),(d)的长度是(3 )。14、递归表、再人表、纯表、线性表之间的关系满足： 15、广义表是线性表的推广，线性

27、表是广义表的特例。当广义表中的元素都是原子时，即为线性表。16、设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?解： (1)因含5*6=30个元素，因此A共占30*4=120个字节。 (2)a45的起始地址为： Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116 (3)按行优先顺序排列时， a25=1000+(2*6+5)*4=1068 (4)按列优先顺序排列时：(二维数组可用行列下标互换来计算) a25=1000+(5*5+

28、2)*4=1108 17、 求下列广义表运算的结果：(1)head (p,h,w); (2)tail(b,k,p,h); (3) head (a,b),(c,d);(4)tail(a,b),(c,d); (5)head(tail(a,b),(c,d);(6)tailhead)(a,b),(c,d).答：(1)head (p,h,w)=p;(2)tail(b,k,p,h)=(k,p,h);(3)head (a,b),(c,d)=(a,b);(4)tail(a,b),(c,d)=(c,d);(5)head(tail(a,b),(c,d)=(c,d);(6)tail(head(a,b),(c,d)=

29、(b) 补充：1、数组元素的地址计算公式（1）按行优先顺序存储的二维数组Amn地址计算公式 LOC(aij)=LOC(a11)+(i-1)n+j-1d 其中：LOC(a11)是开始结点的存放地址（即基地址）d为每个元素所占的存储单元数由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。（2）按列优先顺序存储的二维数组Amn地址计算公式 LOC(aij)=LOC(a11)+(j-1)m+i-1d（3）按行优先顺序存储的三维数组Amnp地址计算公式 LOC(aijk)=LOC(a111)+(i-1)np+(j-1)p+k-1d（4）下界不为1的二维数组

30、的地址计算公式二维数组Ac1.d1,c2.d2的地址计算公式： LOC(aij)=LOC(ac1c2)+(i-c1)(d2-c2+1)+j-c2d下界为0的二维数组的地址计算公式（C语言中使用） LOC(aij)=LOC(a00)+i(d2+1)+jd2、对称矩阵的地址计算公式 LOC(aij)=LOC(sak)=LOC(sa0)+kd=LOC(sa0)+I(I+1)2+Jd 通过下标变换公式，能立即找到矩阵元素aij在其压缩存储表示sa中的对应位置k。因此是随机存取结构。 【例】a21和a12均存储在sa4中，这是因为 k=I(I+1)2+J=2(2+1)2+1=43、三角矩阵的压缩存储 (

31、三角矩阵的压缩存储结构是随机存取结构。)三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)2个，因此，三角矩阵可压缩存储到向量sa0n(n+1)2中，其中c存放在向量的最后一个分量中。 上三角矩阵中aij和sak之间的对应关系 i(2n-i+1)2+j-i 当ijk= n(n+1)/2 当ij下三角矩阵中aij和sak之间的对应关系 i(i+1)2+j 当ij k= n(n+1)/2 当ij十、文件1、通常，磁带只适合用于存储(顺序)文件。2、性质相同的记录的集合称(文件 )。3、文件的逻辑结构是一种(线性 )结构。4、对于存储在磁盘上的顺序文件的记录进行直接存取是根据(逻

32、辑记录号 )。5、存储在磁带上的顺序文件的查找只能用(顺序查找)。6、索引文件的索引表很大时，可建静态索引，即建立索引的索引查找表,其中最多可建(4 )级。7、在索引文件中，若记录要经常变动，则应采用(动态 )索引。当文件中记录数不多时，可用二叉排序树比较好。当文件中记录数较多时，用B树比较好。8、下面关于B树和B+树的叙述中，不正确的是( C)A. B树和B+树都是平衡的多分树； B. B树和B+树都是可用于文件的索引结构；C. B树和B+树都能有效地支持顺序检索 ；D. B树和B+树都能有效地支持随机检索。9、以下关于ISAM文件的说法中，错误的是(D)。 A、她的中文含义是索引顺序存储方

33、法 ；B、专为磁盘存取文件设计；C、采用静态索引结构； D、删除记录操作比插入记录操作复杂。10、为什么索引顺序文件是最常用的文件组织。答：因为：(1)索引顺序文件的主文件按关键字有序，所以适合随机存取和顺序存取。 (2)索引顺序文件的索引是稀疏索引，所以占空间较少。11、对于散列文件，只能作(直接)存取。补充：1、文件分类 （1）文件可以按照记录中关键字的多少，分成： 单关键字文件：文件中的记录只有一个惟一标识记录的主关键字。 多关键字文件：文件中的记录除了含有一个主关键字外，还含有若干个次关键字的文件。（2）文件分成定长文件和不定长文件 由定长记录组成的文件称做定长文件，含有的信息长度相同

34、的记录称定长记录。 文件中记录含有的信息长度不等，则称其为不定长文件。2、文件上的操作主要有两类：检索和维护。（1）检索即在文件中查找满足给定条件的记录。它既可以按记录的逻辑号(即记录存入文件时的顺序编号)查找，也可以按关键字查找。按检索条件的不同，可将检索分为四种询问：简单询问：只询问单个关键字等于给定值的记录。范围询问：只询问单个关键字属于某个范围内的所有记录。函数询问：规定单个关键字的某个函数，询问该函数的某个值。布尔询问：以上三种询问用布尔运算(与、或、非)组合起来的询问。（2）维护操作主要是指： 对文件进行记录的插入、删除及修改等更新操作。 为提高文件的效率，进行再组织操作， 文件被

35、破坏后的恢复操作，以及文件中数据的安全保护等。（3） 文件操作的处理方式 文件上的检索和更新操作，都可有实时和批量两种不同的处理方式。 实时处理：响应时间要求严格，要求在接受询问后几秒种内完成检索和更新。 批量处理：响应时间要求宽松一些，不同的文件系统有不同的要求。3、文件的存储结构 文件的存储结构是指文件在外存上的组织方式。文件在外存上的基本的组织方式有四种：顺序组织，索引组织，散列组织和链组织；对应的的文件名称分别为：顺序文件、索引文件、散列文件和多关键字文件。4文件组织方式的选择常用外存设备有： 磁带是顺序存取设备，只适用于存储顺序文件 磁盘是直接存取设备，适用于存储顺序文件、索引文件、

36、散列文件和多关键字文件等5、 评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。通常文件组织的主要目的，是为了能高效、方便地对文件进行操作，而检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。6、 顺序文件分类（1） 顺序有序文件：记录按其主关键字有序的顺序文件为顺序有序文件。（2） 顺序无序文件：记录未按其主关键字有序排列的顺序文件为顺序有序文件。7、 顺序文件主要优点是连续存取的速度较快；顺序文件多用于磁带。8、 索引文件由主文件和索引表构成。9、 索引顺序文件和索引非顺序文件（1）索引顺序文件(Indexed Sequential File) 主文件按主

37、关键字有序的文件称索引顺序文件。 在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。（2）索引非顺序文件(Indexed NonSequentail File) 主文件按主关键字无序得文件称索引非顺序文件。 在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索引表称为稠密索引。 注意： 通常将索引非顺序文件简称为索引文件。 索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。 索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。 索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。 最常用的索引顺序文

38、件：ISAM文件和VSAM文件。10、 索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主文件。11、 树表结构选择： 当数据文件的记录数不很多，内存容量足以容纳整个索引表时，可采用二叉排序树(或AVL树)作索引； 当文件很大时，索引表(树表)本身也在外存，查找索引时访问外存的次数恰为查找路径上的结点数。采用m阶B-树(或其变型)作为索引表为宜（m的选择取决于索引项的多少和缓冲区的大小）。12、 由于访问外存的时间比内存中查找的时间大得多，所以外存的索引表的查找性能主要着眼于访问外存的次数，即索引表的深度。13、 ISAM为Indexed Sequential Acc

39、ess Methed(索引顺序存取方法)的缩写，它是一种专为磁盘存取文件设计的文件组织方式，采用静态索引结构。ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。磁道索引中的每一个索引项，都由两个子索引项组成：基本索引和溢出索引项。14、 VSAM是Virtual Storage Access Method(虚拟存储存取方法)的缩写，它也是一种索引顺序文件的组织方式，采用B+树作为动态索引结构。对B+树可进行两种查找运算：一种是从最小关键字起进行顺序查找；另一种是从根结点开始进行随机查找。VSAM文件的结构由三部分组成：索引集，顺序集和数据集。和ISAM文件相比，基于B+树的VSAM文件

40、有如下优点：能保持较高的查找效率，查找一个后插入记录和查找一个原有记录具有相同的速度；动态地分配和释放存储空间，可以保持平均75的存储利用率；而且永远不必对文件进行再组织。因而基于B+树的VSAM文件，通常被作为大型索引顺序文件的标准组织。15、 散列文件是利用散列存储方式组织的文件，亦称直接存取文件。即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上。比较项目散列表散列文件存储单位若干记录为一组桶处理冲突办法开放地址法、拉链法拉链法16、 散列文件的特点： 散列文件的优点（1） 文件随机存放，记录不需进行排序。（2） 插入、删除方便。（3） 存取速度快；不需要

41、索引区，节省存储空间。散列文件的缺点（1） 不能进行顺序存取，只能按关键字随机存取（2） 询问方式限于简单询问（3） 在经过多次插入、删除后，可能造成文件结构不合理，需要重新组织文件。17、 多重表文件是将索引方法和链接方法相结合的一种组织方式。 18、 多关键字文件和其他文件的区别多关键字文件其他文件包含的关键字主关键字外还有多个次关键字只含一个主关键字索引建立的索引建立主关键字索引和多个次关键字索引只有（没有）主关键字索引查询查询对主关键字索引或次关键字索引查询只能顺序存取主文件记录进行比较，效率低文件组织方式四种基本组织方法都可以四种组织方法都可以六、树1、在树中，互为堂兄弟的结点拥有相

42、同的(祖先 )。 2、树最适合用来表示（元素之间具有分支层次关系的数据）3、在树中，度为(0 )的结点称为叶子。4、在树中，除跟结点外，其他结点都有且只有一个(双亲(或前趋) )结点。5、有100个结点的树有(99 )条边。6、若将树中的每个结点的各子树看成从左到右有次序，则该树为(有序)树。7、说出树的四种表示方法：树形表示法、嵌套集合表示方法、广义表表示法、凹入表表示法。8、在一棵高度为h的满四叉树中，结点总数为(4h-1 )。9、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是(11 )。 n0=n2+110、按二叉树的定义，具有3个结点的二叉树有( 5) 种。11、一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有(33 )个。12、深度为K的完全二叉树至少有2(k-1)个结点，至多有2(k-1)-2个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是(2(K-2)+1 )。13、一棵有50个结点的完全