c语言数据结构总结

数据结构大全

一、概论

二、线性表

三、栈和队列

四、串

五、多维数组和广义表

十、文件

六、树

七、图

八、排序

九、查找

一、概论

1、　评价一个算法时间性能的主要标准是(　算法的时间复杂度　)。  
2、　算法的时间复杂度与问题的规模有关外，还与输入实例的(　初始状态　)有关。

3、　一般，将算法求解问题的输入量称为(　问题的规模　)。

4、　在选择算法时，除首先考虑正确性外，还应考虑哪三点?

答：选用的算法首先应该是"正确"的。此外，主要考虑如下三点：① 执行算法所耗费的时间；② 执行算法所耗费的存储空间，其中主要考虑辅助存储空间；③ 算法应易于理解，易于编码，易于调试等等。

6、　下列四种排序方法中，不稳定的方法是(　D )  
A、直接插入排序　B、冒泡排序　C、归并排序　D、直接选择排序

7、　按增长率由小至大的顺序排列下列各函数：
　　2100, (3/2)n，(2/3)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
对数阶：lgn
K次方阶：n0.5、n3/2

指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn
注意：(2/3)n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 
根据以上分析按增长率由小至大的顺序可排列如下：

(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、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

2、　线性表是一种典型的(　线性　)结构。

3、　线性表的逻辑结构特征是什么?

答：对于非空的线性表:① 有且仅有一个开始结点A1，没有直接前趋，有且仅有一个直接后继A2；② 有且仅有一个终结结点AN，没有直接后继，有且仅有一个直接前趋AN-1；③ 其余的内部结点AI（2≤I≤N-1）都有且仅有一个直接前趋AI-1和一个AI+1。

4、　线性表的顺序存储结构是一种(　随机存取　)的存储结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续

5、　在顺序表中，只要知道(　基地址和结点大小　)，就可在相同时间内求出任一结点的存储地址。  

6、　在等概率情况下，顺序表的插入操作要移动(　一半　)结点。  

7、　在一个长度为n的顺序表中删除第i个元素，要移动( 　n-i　)个元素

8、　如果要在第i个元素前插入一个元素，要后移(　n-i+1 )个元素。

9、　采用(　顺序　)存储结构的线性表叫顺序表。

10、  顺序表中逻辑上相邻的元素的物理位置(　相邻 )。

11、　在(　C )运算中，使用顺序表比链表好。  
A、插入  　B、删除 　　C、根据序号查找　　D、根据元素值查找

12、　在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(　O(n) )。  

13、　在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在(　前趋)结点的next域中。

14、　在(　循环　)链表中，从任何一结点出发都能访问到表中的所有结点。

15、　(　双向 )链表适合从指点结点开始，寻找直接前趋的运算。

16、　顺序表相对于链表的优点有节省存储和随机存取。

17、　在链表的开始结点前设置头结点的优点是什么？

答：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:（1）、由于开始结点的位置被,所以在链表的第一个存放在头结点的指针域中位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;（2）、无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。

18、　(　双向链表 )适合作为经常在首尾两端操作线性表的存储结构。

19、　如果线性表的存储空间变化较大，则适合用(　链　)表。

20、　当线性表的数据变化不大，主要用于查询时，用(　顺序　)表比较好。

21、　在链表中，每个结点中含8个字符，1个指针域。其中每个字符占1个字节，每个指针占4个字节。则该结点的存储密度是(　2/3　)。 (1+1+4)/(8+1)=2/3　  存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）

22、　链表相对于顺序表的优点有插入和删除操作方便。

23、　在n个结点的顺序表中插入一个结点需平均移动n/2个结点，具体任务的移动次数取决于表长n和插入位置i。

24、　在n个结点的顺序表中删除一个结点需平均移动（n－1）/2个结点，具体任务的移动次数取决于表长n和删除位置i。

25、　尾指针是指向终端结点的指针查找时间都是O(1)，用头指针来表示该链表，则查找终端结点的时间为O(n)。

补充：

1、  顺序表上实现的基本运算：表的初始化、求表长、取表中第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个位置上插入一个结点的概率。不失一般性，假设在表中任何合法位置（1≤i≤n+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个位置上结点的概率。不失一般性，假设在表中任何合法位置（1≤i≤n）上的删除结点的机会是均等的，则  p1=p2=…=pn=1/n    　因此，在等概率插入的情况下，
       
 　　顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。

4、　单链表的运算：头插法建表、尾插法建表、尾插法建带头结点的单链表三个算法的时间复杂度均为0(n)。

5、　单链表的查找运算：按序号查找、按值查找其平均时间复杂度为O(n)。

6、　单链表的插入运算：算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O(n)。

7、　单链表的删除运算：算法的时间复杂度也是O（n）。

8、　循环链表：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。

9、　双向链表的前插和删除本结点操作：两个算法的时间复杂度均为O(1)。

10、　结点ai 的存储地址
    　不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址（简称为基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算：          LOC（ai）= LOC（a1）+（i-1）*c   1≤i≤n

三、栈和队列

1、　栈与一般的线性表的区别在于(　运算是否受限制　)。  

2、　一个栈的入栈序列是abcde，则栈的不可能的输出序列是 （　C　）。  
A、Edcba　 B、 decba　 C、 dceab 　D、 abcde

3、　在对栈的操作中，能改变栈的结构的是(　InitStack(S)　 )。  

4、　顺序栈的类型定义如下：  
typedef maxsize 64;  
typedef struct {  
int data[maxsize];  
int top;}seqstack;  
seqstack *s;  
顺序栈s栈满条件是(　s->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、　在栈的出栈操作中，要先判断栈是否空，否则会产生(　下溢 )现象。

9、　当程序中同时使用(　2 　)个栈时，让它们共享同一向量空间可减少上溢的发生。

10、　栈的特点是(　后进先出 )。当问题满足(　先进后出　)原则时可使用队列作数据结构。当问题满足(　后进先出　)原则时可使用栈作数据结构。

11、　由于链栈的操作只在链表头部进行，所以没有必要设置(　头 )结点。

12、　若内存空间充足，(　链 )栈可不定义栈满运算。

13、　一个队列的入列序列是1 2 3 4，则队列的输出序列是(　1 2 3 4　)。  

14、　队列与一般的线性表的区别在于(　运算是否受限制　 )。

15、　“假上溢”现象会出现在(　顺序队列 )中。

16、　在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是(　F=F->next;   )。  

17、　假设以数组sequ[m]存放循环队列，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含的元素个数，则判别队满的条件是(　quelen==m 　)。

18、　为了克服“假上溢”，一般可用(　循环 )向量存储队列中的元素。

19、　在顺序队列中，若队列非空，(　队头 )指针指向队头元素,队尾指针指向队尾元素的下一位置。

20、　循环队列采用的是(　顺序　)存储结构。

21、　设F和R是循环队列的队头指针和队尾指针，则判断队空的条件是(　F==R 　)。

22、　在(　队列中只有一个元素 )情况下，链队列的出队操作需要修改尾指针。

23、　说出解决循环队列中，判断队空和队满情况的三种方法。

答：① 另设一布尔变量以区别队列的空和满；② 少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：REAR所指的单元始终为空）；③ 使用一个计数器记录队列中元素的总数（实际上是队列长度）。

24、　设计一个判别表达式中左、右括号是否配对出现的算法，采用(　线性表的顺序存储结构　)数据结构最佳。

25、　在计算递归函数时，如不使用递归过程，则一般情况下必须借助于(　栈  )数据结构。

26、　计算机在运行递归程序时，要用到(　系统　)提供的栈。

27、　什么是递归算法?设计递归算法要分哪两个步骤？

答：所谓递归是指：若在一个函数、过程或者数据结构定义的内部又直接（或间接）出现有定义本身的应用，则称它们是递归的，或者是递归定义的。

递归算法的设计步骤第一步骤（递归步骤）：将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题；第二步骤：确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件）。

28、　在栈结构中，允许插入、删除的这一端为栈顶（　Top　），另一端称为栈底（　Bottom　）。

29、　在有n个元素的栈中，进栈和退栈操作的时间复杂度为O(1)和O(1)。

30、　在队列结构中，允许插入的一端称为队尾，允许删除的一端称为队头。

31、　设长度为n的链队列用单循环链表，若只设头指针，则入队和出队操作的时间复杂度分别为O(n)和O(1)；若只设尾指针，则入队和出队操作的时间复杂度分别为O(1)和O(1)。

32、　设循环向量有m个元素，循环向量中有一个循环队列。在循环队列中，设头指针front指向队头元素，队尾指针指向队尾元素后的一个空闲元素。

　（1）在循环队列中，队空标志为front==rear；队满标志为front==(rear+1)%QueueSize。

　（2）当rear>=front时，队列长度为rear-front；当rear<front；队列长度是rear+Queue-front；

33、　设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： 
　　(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),Pop()。这样，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,4312

34、　指出下述程序段的功能是什么? 
(1) void Demo1(SeqStack *S){
　　　　int i; arr[64] ; n=0 ;
　　　　while ( StackEmpty(S)) arr[n++]=Pop(S);
　　　　for (i=0, i< n; i++) Push(S, arr[i]);
　　　} //Demo1

答：程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。


(2) SeqStack S1, S2, tmp;
　　DataType x;
　　...//假设栈tmp和S2已做过初始化
　　while ( ! StackEmpty (&S1))
　　　{
　　　　x=Pop(&S1) ;
　　　　Push(&tmp,x);
　　　}
　　while ( ! StackEmpty (&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，将一个非空栈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 , 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-＞data[0]是栈底元素。
（1） 进栈操作
    　进栈时，需要将S-＞top加1
  注意：　    ①S-＞top==StackSize-1表示栈满
　　②"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。
      上溢是一种出错状态，应设法避免。
（2） 退栈操作
    　退栈时，需将S-＞top减1
  注意：①S-＞top<0表示空栈
    　   ②"下溢"现象——当栈空时，做退栈运算产生的溢出现象。   下溢是正常现象，常用作程序控制转移的条件。

2、　顺序队列中的溢出现象
　　① "下溢"现象    当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
　　② "真上溢"现象   当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
　　③ "假上溢"现象　由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

为充分利用向量空间，克服"假上溢"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。

四、串

1、　串是一种特殊的线性表，其特殊性体现在(　数据元素是一个字符  )。  

2、　有两个串P和Q，求P和Q中首此出现的位置的运算称 (　求子串 )。  

3、　设串s1='ABCDEFG',s2='PQRST',函数con(x,y)返回x和y串的连接串，subs(s,I,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2)))的结果串是( 　D　)。

A、BCDEF 　B、BCDEFG　 C、BCPQRST 　D、BCDEFEF

4、　在空串和空格串中，长度不为0的是(　空格串 )。

5、　在串的模式匹配中，一般(　有效位移的个数小于合法位移的个数  )。  

6、　在顺序串中，根据空间分配方式的不同，可分为(　静态分配和动态分配 )。  

7、　按存储结构不同，串可分为(　顺序串和链串 )。通常在程序中使用的串可分为：串变量和串常量。

8、　在C语言中，以字符(　\0 　)表示串值的终结。

9、　在链串中，为了提高存储密度，应该增大(　结点的大小 ).

10、　假设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占(　 4　)个字节。

11、　顺序串上的子串定位运算算法分析：  　该算法最坏情况下的时间复杂度为O((n-m+1)m)。
  分析：当目标串和模式串分别是"an-1b"和"am-1b"时，对所有n-m+1个合法的位移，均要比较m个字符才能确定该位移是否为有效位移，因此所需比较字符的总次数为（n-m+1）m。

12、　串（String）是零个或多个字符组成的有限序列。一般记为 S="a1a2……an"。

13、　长度为零的串称为空串（Empty String），它不包含任何字符。  仅由一个或多个空格组成的串称为空白串（Blank String）。

14、　子串定位运算又称串的模式匹配或串匹配。在串匹配中，一般将被匹配的主串称为目标（串），子串称为模式（串）。

15、　朴素的串匹配算法最坏情况下需比较字符的总次数为（n-m+1）m。n为主串长，m为子串长。

16、 　串匹配就是对于合法的位置（又称合法的位移）0≤i≤n-m，依次将目标串中的子串"titi+1…ti+m-1"和模式串"p0p1p2…pm-1"进行比较：
　　①若"titi+1…ti+m-1"＝"p0p1p2…pm-1"，则称从位置i开始的匹配成功，或称i为有效位移。
　　②若"titi+1…ti+m-1"≠"p0p1p2…pm-1"，则称从位置i开始的匹配失败，或称i为无效位移。
　　因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。

17、　朴素模式算法在最好的情况下的运行时间是（　M　）（为一次内循环为单位）。

18、　设T[0..n-1]="adaabaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。
解：所有的有效位移i的值为：2，5，9。算法NaveStrMatch(T,P)的返回值是第一个有效位移，因此是2。

19、　假设有如下的串说明：char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;
　(1)在执行如下的每个语句后p的值是什么?
　　p=stchr(s1,'t');  p=strchr(s2,'9');  p=strchr(s2,'6');

答：stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。
　因此:　执行p=stchr(s1,'t');后p的值是指向第一个字符t的位置, 也就是p==&s1[1]。
　　执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。
` 　执行p=strchr(s2,'6');之后，p的返回值是NULL。


　(2)在执行下列语句后，s3的值是什么?
　　strcpy(s3,s1);  strcat(s3,",");  strcat(s3,s2);

答：strcpy函数功能是串拷贝，strcat函数的功能是串联接。所以:
在执行strcpy(s3,s1); 后，s3的值是"Stocktom,CA"
在执行strcat(s3,","); 后，s3的值变成"Stocktom,Ca,"
在执行完strcat(s3,s2);后，s3的值就成了"Stocktom,Ca,March 5,1999"

　(3)调用函数strcmp(s1,s2)的返回值是什么?

答：函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的)


　(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?

答：首先，我们要知道&s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp( &s1[5],"ton")中，前一个字符串值是"tom,CA",用它和"ton"比较，应该是后者更大，所以返回值是小于0的数。


　(5)调用函数stlen(strcat(s1,s2))的返回值是什么?

答：strlen是求串长的函数，我们先将s1,s2联接起来，值是"Stocktom,CAMarch 5,1999",数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。

五、多维数组和广义表

1、　n维数组中的每个元素都最多有(　n　 )个直接前趋。

2、　对于一个一维数组A[12]，若一个数据元素占用字节数为S，首地址为1，则A[i](i>=0)的存储地址为( A )，若首地址为D，则A[i]的存储地址为( B )。答：A-(1+S*I) B-(D+S*I)

3、　已知二维数组A[m][n]采用行优先顺序存储，每个元素占k个存储单元，并且第一个元素的存储地址LOC（A[0][0]），则A[i][j]的地址是(　1+(n*i+j)*k　 )。

4、　在多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，数组是一种(　随机 )存取结构。

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+j

7、　在稀疏矩阵的三元组表表示法中，每个三元组表示(　矩阵中非零元素的行号、列号和值 )。  

8、　对稀疏矩阵进行压缩存储是为了(　节约存储空间   )。  

9、　矩阵的压缩存储就是为多个相同的非零元素分配(　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、广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。

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+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))))=(b)

补充：

1、数组元素的地址计算公式
（1）按行优先顺序存储的二维数组Amn地址计算公式
        LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d
    其中：
　　①LOC(a11)是开始结点的存放地址（即基地址）
　　②d为每个元素所占的存储单元数
　　③由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。
（2）按列优先顺序存储的二维数组Amn地址计算公式
          LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d

（3）按行优先顺序存储的三维数组Amnp地址计算公式
      LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d

（4）下界不为1的二维数组的地址计算公式
　　①二维数组A[c1..d1,c2..d2]的地址计算公式：
      LOC(aij)=LOC(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d
 　②下界为0的二维数组的地址计算公式（C语言中使用）
      LOC(aij)=LOC(a00)+[i×(d2+1)+j]×d

2、对称矩阵的地址计算公式
  LOC(aij)=LOC(sa[k])=LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)／2+J]×d
    通过下标变换公式，能立即找到矩阵元素aij在其压缩存储表示sa中的对应位置k。因此是随机存取结构。
  【例】a21和a12均存储在sa[4]中，这是因为           k=I×(I+1)／2+J=2×(2+1)／2+1=4

3、三角矩阵的压缩存储  (三角矩阵的压缩存储结构是随机存取结构。)

三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)／2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)／2]中，其中c存放在向量的最后一个分量中。

①  上三角矩阵中aij和sa[k]之间的对应关系

          i×(2n-i+1)／2+j-i  当i≤j
 　k=
            n×(n+1)/2      当i＞j

②下三角矩阵中aij和sa[k]之间的对应关系
  　         i×(i+1)／2+j  当i≥j
    k=
 　         n×(n+1)/2    当i＜j

十、文件

1、　通常，磁带只适合用于存储(　顺序　)文件。

2、　性质相同的记录的集合称(　文件 )。

3、　文件的逻辑结构是一种(　线性 )结构。

4、　对于存储在磁盘上的顺序文件的记录进行直接存取是根据(　逻辑记录号  )。

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、她的中文含义是索引顺序存储方法  ；B、专为磁盘存取文件设计；

　　C、采用静态索引结构；  D、删除记录操作比插入记录操作复杂。

10、　为什么索引顺序文件是最常用的文件组织。

答：因为：(1)索引顺序文件的主文件按关键字有序，所以适合随机存取和顺序存取。 (2)索引顺序文件的索引是稀疏索引，所以占空间较少。

11、　对于散列文件，只能作(　直接　)存取。

补充：

1、　文件分类
（1）　文件可以按照记录中关键字的多少，分成：
　　① 单关键字文件：文件中的记录只有一个惟一标识记录的主关键字。
　　② 多关键字文件：文件中的记录除了含有一个主关键字外，还含有若干个次关键字的文件。

（2）文件分成定长文件和不定长文件
　　① 由定长记录组成的文件称做定长文件，含有的信息长度相同的记录称定长记录。
　　② 文件中记录含有的信息长度不等，则称其为不定长文件。

2、　文件上的操作主要有两类：检索和维护。

（1）   检索即在文件中查找满足给定条件的记录。它既可以按记录的逻辑号(即记录存入文件时的顺序编号)查找，也可以按关键字查找。按检索条件的不同，可将检索分为四种询问：
　①简单询问：只询问单个关键字等于给定值的记录。 　②范围询问：只询问单个关键字属于某个范围内的所有记录。　③函数询问：规定单个关键字的某个函数，询问该函数的某个值。 　④布尔询问：以上三种询问用布尔运算(与、或、非)组合起来的询问。

（2）维护操作主要是指：
　　① 对文件进行记录的插入、删除及修改等更新操作。
　　② 为提高文件的效率，进行再组织操作，
　　③ 文件被破坏后的恢复操作，以及文件中数据的安全保护等。
（3） 文件操作的处理方式    　文件上的检索和更新操作，都可有实时和批量两种不同的处理方式。
　　① 实时处理：响应时间要求严格，要求在接受询问后几秒种内完成检索和更新。
　　② 批量处理：响应时间要求宽松一些，不同的文件系统有不同的要求。

3、　文件的存储结构
    　文件的存储结构是指文件在外存上的组织方式。  文件在外存上的基本的组织方式有四种：顺序组织，索引组织，散列组织和链组织；对应的的文件名称分别为：顺序文件、索引文件、散列文件和多关键字文件。

4．　文件组织方式的选择

常用外存设备有：  ① 磁带是顺序存取设备，只适用于存储顺序文件
    　             ② 磁盘是直接存取设备，适用于存储顺序文件、索引文件、散列文件和多关键字文件等

5、    评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。通常文件组织的主要目的，是为了能高效、方便地对文件进行操作，而检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。

6、    顺序文件分类
（1） 顺序有序文件： 记录按其主关键字有序的顺序文件为顺序有序文件。
（2） 顺序无序文件： 记录未按其主关键字有序排列的顺序文件为顺序有序文件。

7、    顺序文件主要优点是连续存取的速度较快；顺序文件多用于磁带。

8、    索引文件由主文件和索引表构成。

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

10、 索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主文件。

11、 树表结构选择：　　① 当数据文件的记录数不很多，内存容量足以容纳整个索引表时，可采用二叉排序树(或AVL树)作索引；　　② 当文件很大时，索引表(树表)本身也在外存，查找索引时访问外存的次数恰为查找路径上的结点数。采用m阶B-树(或其变型)作为索引表为宜（m的选择取决于索引项的多少和缓冲区的大小）。

12、 由于访问外存的时间比内存中查找的时间大得多，所以外存的索引表的查找性能主要着眼于访问外存的次数，即索引表的深度。

13、 ISAM为Indexed Sequential Access Methed(索引顺序存取方法)的缩写，它是一种专为磁盘存取文件设计的文件组织方式，采用静态索引结构。ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。磁道索引中的每一个索引项，都由两个子索引项组成：基本索引和溢出索引项。

14、 VSAM是Virtual Storage Access Method(虚拟存储存取方法)的缩写，它也是一种索引顺序文件的组织方式，采用B+树作为动态索引结构。对B+树可进行两种查找运算：一种是从最小关键字起进行顺序查找；另一种是从根结点开始进行随机查找。VSAM文件的结构由三部分组成：索引集，顺序集和数据集。和ISAM文件相比，基于B+树的VSAM文件有如下优点：能保持较高的查找效率，查找一个后插入记录和查找一个原有记录具有相同的速度；动态地分配和释放存储空间，可以保持平均75％的存储利用率；而且永远不必对文件进行再组织。因而基于B+树的VSAM文件，通常被作为大型索引顺序文件的标准组织。

15、 散列文件是利用散列存储方式组织的文件，亦称直接存取文件。即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上。

16、 散列文件的特点： 散列文件的优点（1） 文件随机存放，记录不需进行排序。（2） 插入、删除方便。（3） 存取速度快；不需要索引区，节省存储空间。散列文件的缺点（1） 不能进行顺序存取，只能按关键字随机存取（2） 询问方式限于简单询问（3） 在经过多次插入、删除后，可能造成文件结构不合理，需要重新组织文件。

17、   多重表文件是将索引方法和链接方法相结合的一种组织方式。 

18、 多关键字文件和其他文件的区别

六、树

1、　在树中，互为堂兄弟的结点拥有相同的(　祖先 )。  

2、　树最适合用来表示（　元素之间具有分支层次关系的数据　）

3、　在树中，度为(　0　 )的结点称为叶子。

4、　在树中，除跟结点外，其他结点都有且只有一个(　双亲(或前趋) 　)结点。

5、　有100个结点的树有(　99 　)条边。

6、　若将树中的每个结点的各子树看成从左到右有次序，则该树为(　有序　)树。

7、　说出树的四种表示方法：树形表示法、嵌套集合表示方法、广义表表示法、凹入表表示法。

8、　在一棵高度为h的满四叉树中，结点总数为(　4h-1  )。

9、　若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是(　11 　)。  n0=n2+1

10、　按二叉树的定义，具有3个结点的二叉树有( 　5　) 种。

11、　一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有(　33 　)个。

12、　深度为K的完全二叉树至少有2^(k-1)个结点，至多有2^(k-1)-2个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是(　2^(K-2)+1 　)。

13、　一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt[1..50]中，这棵二叉树最下面一层上最左边一个结点存储在数组元素(　33　 )中。

14、　有n个结点的二叉链表中，其中空的指针域为n+1.指向孩子的指针个数为(　n-1　 )。

15、　在二叉链表的顺序存储结构中，结点之间的关系通过(　编号 )来表示.完全二叉树的存储效率最高。

16、　说出树和二叉树的差别：树和二叉树是两种不同的数据结构。对于二叉树来说，每个结点最多只有两个孩子，分别叫左孩子和右孩子；如果只有一个孩子，则该孩子还是有左右之分的。而树则不然。

17、              　已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...nm个度为m的结点，问该树中有多少片叶子?

设该树中的叶子数为N0个。该树中的总结点数为N个，则有： &NBSP;
N=N0+N1+N2+…+NM (1) &NBSP;
又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为： &NBSP;
N-1=0*N0+1*N1+2*N2+…+M*NM (2) &NBSP;
联立(1)(2)方程组可得： &NBSP;
叶子数为：N0=1+0*N1+1*N2+2*N3+...+(M-1)*NM

18、              　在一非空二叉树的中序遍历序列中，根结点的右边(　只有右子树上的所有结点 )。  

19、              　已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(　A 　)。  
A、acbed B、deabc C、decab D、cedba

20、　在二叉树的中序遍历递归算法中，顺着搜索路径，在第(　 2　)次经过结点时作访问操作。

21、　现有按中序遍历二叉树的结构是ABC，有(　 3　)种不同形态的二叉树可以得到这一遍历序列。

23、　在线索化二叉树中，结点*P没有左子树的充要条件是(　P->ltag==1　)。  

24、　在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是(　右子树的最左下结点　)。

25、　在寻找前趋或后继结点中，可能要用到双亲结点指针的是(　寻找前序线索二叉树的前序前趋 )。  

26、　在二叉链表中，利用空指针域，存放指定结点的某种遍历的前趋和后继结点指针。这种指针叫(　线索 )。

27、　若对一棵二叉树要经常遍历，或找结点在指定次序下的前趋和后继，则应采用(　线索链表　)作为存储结构。

28、　树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论(　树的先根遍历序列与其对应的二叉树的先序遍历序列相同  )是正确的。  

29、　由森林转化成的二叉树(　没有右子树  )。

30、　在树的(　双亲链表 )表示法中，求指定结点的双亲或祖先十分方便，但是求指定结点的孩子或其他后代可能要遍历整个数组。在树的(　双亲孩子链表　)表示法中，即方便求指定结点的双亲，又方便求指定结点的孩子。

31、　已知树的先根次序访问序列为GFKDAIEBCHJ，后根次序访问序列为DIAEKFCJHBG。则该树有( 　5　)个叶子。

32、　已知森林的先序访问序列为ABCDEFGHIJKL；中序访问序列为CBEFDGAJIKLH。则该森林有(　2　 )棵树。

33、　Huffman树的形态是(　不唯一 )。  

34、　由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为(　67　 )。

35、　一棵哈夫曼树有19个结点，则其叶子结点的个数(　9　 )。

36、　当对字符集进行编码时，字符集中任一字符的编码都不是其他字符的编码的前缀，这种编码称(　前缀码 )。

37、　在具有n个结点的k叉树(k>=2)的k叉链表表示中，有多少个空指针?
解：n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1;

38、　试找出分别满足下面条件的所有二叉树：
　(1)前序序列和中序序列相同； (2)中序序列和后序序列相同；
　(3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。
答：　(1) 前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。
　    (2) 中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。
　    (3) 前序序列和后序序列相同的二叉树是：空二叉树或只有根的二叉树。
    　(4) 前序、中序、后序序列均相同的二叉树：空树或只有根结点的二叉树。

39、　高度为h的严格二叉树至少有多少个结点?至多有多少个结点? 
答：   所谓严格二叉树是指该树中没有度数为1的分支结点的二叉树。
    所以：高度为h的的严格二叉树至少有2h-1个结点；至多有2h-1个结点(即满二叉树)。

40、　在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。

七、图

1、  　设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V2包含V1，E2包含E1，则称(　G2是G1的子图　)。  

设G=(V，E)是一个图，若V'是V的子集，E'是E的子集，且E'中的边所关联的顶点均在V'中，则G'=(V'，E')也是一个图，并称其为G的子图。

2、　设有6个结点的无向图，该图至少应有( 　5　)条边才能确保是一个连通图。

3、　具有n个顶点的有向图最多有(　n(n-1)　 )条边。说出无向图中边数e和顶点数n的关系是（　0≤e≤n(n-1)/2　）。

图G的顶点数n和边数e的关系
（1）若G是无向图，则0≤e≤n(n-1)/2    　恰有n(n-1)/2条边的无向图称无向完全图

（2）若G是有向图，则0≤e≤n(n-1)。    　恰有n(n-1)条边的有向图称为有向完全图

  注意：    　完全图具有最多的边数。任意一对顶点间均有边相连。

4、　具有n个顶点的强连通图最少有(　n 　)条边。

5、　下面关于图的存储的叙述中，哪一个是正确的。 (　A　 )  
A．用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,与边数无关  
B．用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,与结点个数无关  
C．用邻接表存储图，占用的存储空间数只与图中结点个数有关，与边数无关  
D．用邻接表存储图，占用的存储空间数只与图中边数有关，与结点个数无关

6、　无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系：   

    

7、　邻接矩阵表示法的空间复杂度S(n)=0(n2)。

8、　建立无向网的邻接矩阵表示：　该算法的执行时间是0(n+n2+e)。由于e<n2，算法的时间复杂度是0(n2)。

建立无向图的邻接表算法：该算法的时间复杂度是O(n+e)。

9、　在图的表示法中，表示形式唯一的是(　邻接矩阵表示法　)。

10、　n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。

   n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点

11、　(　稀疏图　 )适合用邻接表表示。

12、　对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为(　n　 ).

13、　有向图的邻接表表示适于求顶点的(　出度 )。

14、　有向图的邻接矩阵表示中，第i(　列　)上非零元素的个数为顶点vi的入度。

15、　采用邻接表存储的图的深度优先遍历算法类似于二叉树的(　先序遍历 )。广度优先遍历类似于树的按（　层次遍历）。  

16、　对有向图进行深度优先搜索时，若该图不是(　强连通图  )，可得到一个深度优先搜索生辰森林。

17、　当对用(　邻接矩阵　)表示法表示的图，从某指定顶点作为初始点进行广度优先搜索，得到的广度优先搜索序列唯一。

18、　一般，图的DFS生成树的高度(　大于 )BFS生成树的高度。

19、　对于无向图，生成树是(　极小 )连通子图。

20、　PRIM算法与图的边数无关，适合求解(　稠密图 )的最小生成树。

21、              　Dijkstra算法是一种路径长度(　递增 )的求解单源点到其他各终点最短路径的方法。

22、　要得到一个无回路有向图的拓扑序列，可以利用(　深度优先遍历的算法 )。  

23、　　在一个无环有向图G中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是(　I在前，J在后 )。

24、　在拓扑排序中，拓扑序列的第一个顶点必定是(　入度 )为0的顶点。

25、　对于含有(　回路或环　)的有向图不能得到拓扑序列。

26、　一个图的DFS序列不一定惟一，（　源点和存储结构的内容　）均已确定的图的DFS序列惟一。

27、　邻接表作为给定图的存储结构时，其表示不惟一。因为邻接表上边表里的邻接点域的内容与建表时的输入次序相关。

28、　对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。所以，DFSTraverse的时间复杂度为0(n+e)（调用DFS）或O(n2) （调用DFSM）。

29、　对于具有n个顶点和e条边的无向图或有向图，每个顶点均入队一次。广度优先遍历(BFSTraverse)图的时间复杂度和DFSTraverse算法相同。    　当图是连通图时，BFSTraverse算法只需调用一次BFS或BFSM即可完成遍历操作，此时BFS（邻接表）和BFSM（邻接矩阵）的时间复杂度分别为O(n+e)和0(n2)。

30、　Prim算法：　该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。

31、　Kruskal算法：该算法的时间复杂度为O(elge)。  Kruskal算法的时间主要取决于边数。它较适合于稀疏图。

32、　对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题?
 (1) 图中有多少条边?  (2)任意两个顶点i和j是否有边相连?  (3) 任意一个顶点的度是多少?
答： 对于n个顶点的无向图和有向图，用邻接矩阵表示时：
 　(1)设m为矩阵中非零元素的个数 ：无向图的边数=m/2；有向图的边数=m
　(2)无论是有向图还是无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。
　(3)对于无向图，任一顶点i的度为第i行中非零元素的个数。
　　对于有向图，任一顶点i的入度为第i列中非零元素的个数，出度为第i行中非零元素的个数，度为入度出度之和。
　　当用邻接表表示时：
　(1)对于无向图，图中的边数=边表中结点总数的一半。对于有向图，图中的边数=边表中结点总数。
　(2)对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。对于有向图，则表示有出边相连。
　(3)对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)

33、n个顶点的连通图至少有n-1条边，强连通图至少有2(n-1)条边。

34、DFS遍历采用栈来暂存顶点。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。

35、当候选轻边集中的轻边数始终等于1条时，其最小生成树是唯一的。用Prim和Kruskal求最小生成树的时间复杂度分别为O(n2)和O(elge),前者适合于稠密图，后者适合于稀疏图。

36、什么样的DAG的拓扑序列是唯一的? 

答：确定了排序的源点，DAG图中无前趋顶点只有一个且从该点到终点只有一条路径时，它的拓扑序列才是唯一的。

八、排序

1、　内部排序和外部排序的区别不在于(　C　 )。  
A、待排序文件的大小  B、有无内外存的交换  C、是否在内存中排序  D、可采用的排序策略

2、　评价排序算法好坏的标准主要是(　执行时间和所需的辅助空间　)。

评价排序算法好坏的标准主要有两条：① 执行时间和所需的辅助空间    　② 算法本身的复杂程度

3、　若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序。非就地排序一般要求的辅助空间为O(n)。

4、　若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变。则这种排序方法是(　稳定　)的排序方法。

5、　内部排序方法可分成哪5类？答：(1)插入排序 (2)选择排序 (3)交换排序 (4)归并排序 (5)分配排序

6、　一个待排序文件的关键字如下：  265 301 751 129 937 863 742 694 076 438  
经过(　C　 )趟直接插入排序后可得到如下序列：  129 265 301 751 937 863 742 694 076 438  
　　A、 1  B、 2  C、 3  D、 4

7、　当增量为1时，该趟希尔排序与(　直接插入 　)排序基本一致。

8、　最坏情况，在第i趟直接插入排序中，要进行(　i-1 　)次关键字的比较。

9、　简述在直接插入排序中监视哨的主要作用。

答：可免去在查找循环中检测是否查找到文件头（或尾）作的检测，从而提高效率。

10、　若用冒泡排序对关键字序列{18，16，14，12，10，8}进行从小到大的排序，所要进行的关键字比较总次数为(　B　 )。  
A、10  B、15　C、21  D、34

11、　用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，结点序列的变化情况如下：  
（1）25 84 21 47 15 27 68 35 20  （2）20 15 21 25 47 27 68 35 84  
（3）15 20 21 25 35 27 47 68 84  （4）15 20 21 25 27 35 47 68 84  
那么，所采用的排序方法是( 　D　)。  
　A、直接插入排序 B、希尔排序 C、冒泡排序 D、快速排序

12　、以下排序方法中，稳定的排序方法是(　B　 )。  
A、直接插入排序和希尔排序  B、直接插入排序和冒泡排序  C、希尔排序和快速排序  D、冒泡排序和快速排序

13、　在快速排序中，每次划分选择的基准元素为该区间的(　中间值　 )时，得到的两个子区间是均匀的。

14、　快速排序在最坏情况下的时间复杂度是(　O(n2)　 )。  

15、　快速排序方法在(　被排序数据已基本有序　 )情况下最不利于发挥其长处。  

16、　两个序列如下：  L1={25，57，48，37，92，86，12，33}  L2={25，37，33，12，48，57，86，92}  
用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列(　L2　 )。

17、　设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键码值递增顺序），请给出一趟扫描后的结果。答：[170 275 154 503] 512 [765 612 897 677 908]

18、　堆排序在最坏情况下的时间复杂度是(　O(nlgn)　 )。  堆是(　完全二叉树　)。  

19、　有10万个无序且互不相等的正整数序列，采用顺序存储方式组织，希望能最快地找出前10个最大正整数，采用(　C　 ) 方法比较好。  A、快速排序 B、希尔排序 C、堆排序 D、归并排序

20、　在(　大根 )堆中，所有双亲结点的关键字的值大于它们孩子的关键字的值。

21、　直接选择排序的总的关键字比较次数与(　文件的初始状态 　)无关。

22、　对n个记录的文件进行二路归并排序，总的时间代价为（　O(nlgn)　）

23、　下面四种内排序方法中，要求容量最大的是(　D　 )。  A、插入排序 B、选择排序 C、快速排序 D、归并排序

24、　已知一个文件的初始关键字序列为：265 301 751 129 937 863 742 694 076 438。写出建成大根堆后的序列和第一次堆排序后重建大根堆的序列。

答：建立初始堆： [937 694 863 265 438 751 742 129 075 301]

第一次排序重建堆：[863 694 751 765 438 301 742 129 075] 937

25、　关于归并排序，说法不正确的是(C)。 A、稳定的排序  B、可使用链式存储结构  C、就地排序  D、可用于外部排序

26、　将两个长度分别m和n（m>n）的排好序的表归并成一个排好序的表，至少要进行(　n　 )次键值比较。

27、　若有文件的关键字序列为：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]，给出二路归并排序过程。

答：第一趟：[265 301] [129 751] [863 937] [694 742] [076 438]
第二趟：[129 265 301 751] [694 742 863 937] [076 438]
第三趟：[129 265 301 694 742 751 863 937] [076 438]
第四趟：[076 129 265 301 438 694 742 751 863 937]

28、　分配排序和其他排序方法的区别在于(　无需关键字的比较　 )。  

29、　对n个记录的文件进行分配排序，总的时间代价为  （　O（n）　）

30、　在箱排序中，箱子的个数取决于( 　关键字的取值范围　)。  

31、　分配排序的两个基本过程是(　分配和收集　 )。

32、　在单关键字的基数排序中，所需的箱子数就是(　基数　 )。

33、　下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？（　D ）  
A. 直接插入排序  B. 起泡排序 　C. 快速排序　　D. 直接选择排序

34、　设有字符序列{Q、H、C、Y、P、A、M、S、R、D、F、X}，向新序列{F、H、C、D、P、A、M、Q、R、S、Y、X}是下列哪个排序算法一趟扫描的结果。(　D　 )  
　A、起泡排序  B、初始步长为4的shell的排序  C、二路归并排序  D、以第一个元素为分界元素的快速排序

35、　有序数组是堆。因为有序数组中的关键字序列满足堆的性质。若数组为降序，则此堆为大根堆，反之为小根堆。

36、　若文件初态是反序的，且要求输入稳定，则在直接插入、直接选择、冒泡和快速排序中就选选哪种方法为宜?
答：这四种排序算法中，直接选择、快速排序均是不稳定的，因此先予以排除，剩下两种算法中，由于直接插入算法所费时间比冒泡法更少(见上题分析)，因此选择直接排序算法为宜。

37、　.高度为h的堆中，最多有多少个元素?最少有多少个元素?在大根堆中，关键字最小的元素可能存放在堆的哪些地方? 
答：高度为h的堆实际上为一棵高度为h的完全二叉树，因此根据二叉树的性质可以算出，它最少应有2h-1个元素；最多可有2h-1个元素(注意一个有括号，一个没有)。在大根堆中，关键字最小的元素可能存放在堆的任一叶子结点上。

38、　若关键字是非负整数，则基数排序最快；若要求辅助空间为O(1)，则应选堆排序；若要求排序是稳定的，且关键字是实数，则应选归并排序，因为基数排序不适用于实数，虽然它也是稳定的。

39、　排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

40、       内排序适用于记录个数不很多的小文件 ；外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。

41、　有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。

42、　大多数排序算法都有两个基本的操作：(1) 比较两个关键字的大小；(2) 改变指向记录的指针或移动记录本身。 第(2)种基本操作的实现依赖于待排序记录的存储方式。

43、　待排文件的常用存储方式：（1） 以顺序表(或直接用向量)作为存储结构 ； （2） 以链表作为存储结构；（3） 用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表)。

44、　插入排序方法：直接插入排序和希尔排序。

交换排序的主要排序方法有：冒泡排序和快速排序。

常用的选择排序方法有：直接选择排序和堆排序。

分配排序：箱排序和基数排序（是对箱排序的改进和推广）。

45、　直接插入排序算法的时间性能分析 ： 对于具有n个记录的文件，要进行n-1趟排序。 各种状态下的时间复杂度：

46、直接插入排序是稳定的排序方法；希尔排序是不稳定的。归并排序不是就地排序。冒泡排序是就地排序，且它是稳定的。

47、　直接插入排序算法所需的辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1)。是一个就地排序。

48、　Shell排序中当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。

49、　快速排序在系统内部需要一个栈来实现递归。快速排序是非稳定的。

50、　堆排序定义：   n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
    　(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

51、　由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)， 它是不稳定的排序方法。

52、　按平均时间将排序分为四类：
（1）平方阶(O(n2))排序：  一般称为简单排序，例如直接插入、直接选择和冒泡排序；
（2）线性对数阶(O(nlgn))排序：  如快速、堆和归并排序；
（3）O(n1+￡)阶排序： ￡是介于0和1之间的常数，即0<￡<1，如希尔排序；
（4）线性阶(O(n))排序：如桶、箱和基数排序。

53、　 简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

54、　不同条件下，排序方法的选择
(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
    　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
    　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
    　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
    　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的  排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

55、　直接插入排序、冒泡排序、直接选择排序、基数排序和归并排序等方法易于在链表上实现。

56、　排序方法总结表

57、　.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。
　(1) 直接插入排序 (2)希尔排序 (3)冒泡排序 (4)快速排序　(5) 直接选择排序 (6) 堆排序 (7) 归并排序 (8)基数排序
　　上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。
答：　(1)直接插入排序:(方括号表示无序区)
　　初始态: 265[301 751 129 937 863 742 694 076 438]
　　第一趟：265 301[751 129 937 863 742 694 076 438]
　　第二趟：265 301 751[129 937 863 742 694 076 438]
　　第三趟：129 265 301 751[937 863 742 694 076 438]
　　第四趟：129 265 301 751 937[863 742 694 076 438]
　　第五趟：129 265 301 751 863 937[742 694 076 438]
　　第六趟：129 265 301 742 751 863 937[694 076 438]
　　第七趟：129 265 301 694 742 751 863 937[076 438]
　　第八趟：076 129 265 301 694 742 751 863 937[438]
　　第九趟：076 129 265 301 438 694 742 751 863 937 

　(2)希尔排序(增量为5，3，1)
　　初始态: 265 301 751 129 937 863 742 694 076 438
　　第一趟：265 301 694 076 438 863 742 751 129 937 
　　第二趟：076 301 129 265 438 694 742 751 863 937 
　　第三趟：076 129 265 301 438 694 742 751 863 937 

　(3)冒泡排序(方括号为无序区)
　　初始态 [265 301 751 129 937 863 742 694 076 438]
　　第一趟： 076 [265 301 751 129 937 863 742 694 438]
　　第二趟： 076 129 [265 301 751 438 937 863 742 694]
　　第三趟： 076 129 265 [301 438 694 751 937 863 742]
　　第四趟： 076 129 265 301 [438 694 742 751 937 863]
　　第五趟： 076 129 265 301 438 [694 742 751 863 937]
　　第六趟： 076 129 265 301 438 694 742 751 863 937

　(4)快速排序：（方括号表示无序区，层表示对应的递归树的层数）
    初始态： [265 301 751 129 937 863 742 694 076 438]
　　第二层： [076 129] 265 [751 937 863 742 694 301 438]
　　第三层： 076 [129] 265 [438 301 694 742] 751 [863 937]
　　第四层： 076 129 265 [301] 438 [694 742] 751 863 [937]
　　第五层： 076 129 265 301 438 694 [742] 751 863 937
　　第六层： 076 129 265 301 438 694 742 751 863 937

　(5)直接选择排序：(方括号为无序区)
　　初始态 　[265 301 751 129 937 863 742 694 076 438]
　　第一趟： 076 [301 751 129 937 863 742 694 265 438]
　　第二趟： 076 129 [751 301 937 863 742 694 265 438]
　　第三趟： 076 129 265[ 301 937 863 742 694 751 438]
　　第四趟： 076 129 265 301 [937 863 742 694 751 438]
　　第五趟： 076 129 265 301 438 [863 742 694 751 937]
　　第六趟： 076 129 265 301 438 694 [742 751 863 937]
　　第七趟： 076 129 265 301 438 694 742 [751 863 937]
　　第八趟： 076 129 265 301 438 694 742 751 [937 863]
　　第九趟： 076 129 265 301 438 694 742 751 863 937

　(6)堆排序：（通过画二叉树可以一步步得出排序结果）
　　    初始态 　　　[265 301 751 129 937 863 742 694 076 438]
　　　　建立初始堆： [937 694 863 265 438 751 742 129 075 301]
　第一次排序重建堆：[863 694 751 765 438 301 742 129 075] 937
　第二次排序重建堆：[751 694 742 265 438 301 075 129] 863 937
　第三次排序重建堆：[742 694 301 265 438 129 075] 751 863 937
　第四次排序重建堆：[694 438 301 265 075 129] 742 751 863 937
　第五次排序重建堆：[438 265 301 129 075] 694 742 751 863 937
　第六次排序重建堆：[301 265 075 129] 438 694 742 751 863 937
　第七次排序重建堆：[265 129 075] 301 438 694 742 751 863 937
　第八次排序重建堆：[129 075]265 301 438 694 742 751 863 937
　第九次排序重建堆：075 129 265 301 438 694 742 751 863 937

　(7)归并排序（为了表示方便，采用自底向上的归并，方括号为有序区）
  　　初始态：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]
　　第一趟：[265 301] [129 751] [863 937] [694 742] [076 438]
　　第二趟：[129 265 301 751] [694 742 863 937] [076 438]
　　第三趟：[129 265 301 694 742 751 863 937] [076 438]
　　第四趟：[076 129 265 301 438 694 742 751 863 937]

　(8)基数排序（方括号内表示一个箱子共有10个箱子，箱号从0到9）
    　初始态：265 301 751 129 937 863 742 694 076 438
   　 第一趟：[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129]
　　第二趟：[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694]
　　第三趟：[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937] 
　　在上面的排序方法中，直接插入排序、冒泡排序、归并排序和基数排序是稳定的，其他排序算法均是不稳定的，现举实例如下：以带*号的表示区别。希尔排序：[8,1,10,5,6,*8]　快速排序：[2,*2,1]　直接选择排序：[2,*2,1]　堆排序：[2,*2,1]

补充：

1、　插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

2、　交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

3、　选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

4、　归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

5、　分配排序的基本思想：排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。

九、查找

1、　通常把查找过程中对关键字需要执行的(　ASL  )作为衡量一个查找算法效率优劣的标准。

2、　若在查找的同时对表作修改，则相应的表称(　动态查找表　 )。

3、　用二分法在有序表{3，4，10，13，33，42，46，63，76，78，95，96，120}中查找95时，要进行的比较次数为(　4　 )。  

4、　线性表必须是( 　用向量存储的有序表　),才能进行二分查找。

5、　二分查找过程可以用(1)树描述，该树的形态只与(2)有关。  （　C　）
A、 1-二叉查找树 2-表中元素个数  　B 、1-二叉判定树 2-表中元素关键字的取值  
C 、1-二叉比较树 2-表中元素个数  　D 、1-二叉树 2-表中元素关键字的取值

6、　长度为12的按关键字有序的查找表采用顺序组织方式，若用二分查找方法，则在等概率情况下，查找不成功的平均查找长度是(　49/13　 )。  

7、　在表长是N的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数(　n+1　 )。

8、　对表长为n的链表进行顺序查找，等概率情况下，查找成功的平均查找长度是(　(n+1)/2　 )。

9、　对表长为n的顺序表进行分块查找，若以顺序查找确定块且每块长度为s，则在等概率查找的情况下，查找成功时的平均查找长度为(　(s2+2s+n)/(2s)　 )。

10、　一个线性表中共有625个元素，假定每个元素的查找概率相同，如果采用分块查找，则对这些元素共分为(  25  )个索引块为最佳（基本查找方法都采用顺序查找）。

11、　在分块查找方法中，首先查找索引表,然后再用顺序查找方法查找相应的(　块　 )。

12、　顺序查找中监视哨的作用是什么？答案：其作用主要有两个： (1)防止下标越界 (2)减少比较次数，提高查找效率

13、　一棵二叉排序树T，用(　中根遍历　)方法进行遍历，可以得到各结点键值的递增序列。  

14、　以下，关于B-树的说法，不正确的是(　B　 )。  
A、B-树是多路平衡查找树  　B、B-树适合在磁带等顺序存储设备上组织动态查找表  
C、B-树中，叶子的层数为树的高度  　D、7阶B-树的内部结点最少有4棵子树。

15、　当二叉排序树为(　平衡的二叉排序树　)时，其平均查找长度最好。

16、　二叉排序树的形态与( 　关键字的输入序列　)有关。

17、　对一棵高度为h的B-树进行查找，若查找成功，则最坏要进行(　h　 )次外查找

18、　设a1、a2、a3是不同的关键字，且a1>a2>a3,可组成六种不同的输入序列。问其中哪几种输入序列所构造的二叉排序树的高度为3？答：(1)A1 A2 A3　 (2)A1 A3 A2 　(3)A3 A1 A2 　(4)A3 A2 A1

19、　从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。

20、　在散列函数H（k）=k %m中，一般来讲，m应取(　素数 )。   

21、　在散列表技术中，冲突是不可避免的。它的频繁程度和(　散列函数和装填因子　)有关

22、　设散列表长m=14，哈希函数H（key）=key% 11。表中已有4个结点。  
Addr(15)=4; 　addr(38)=5;　addr(61)=6;　addr(84)=7  
其余地址为空。  如果用二次探查法处理冲突，关键字为49的结点的地址是(　D　 )。  

A、5　 B、6　 C、4 　D、9

23、　散列函数的选取原则是(　简单和均匀　 )。

24、　两个不同关键字的散列函数值相同的现象称(　冲突或碰撞　 )。

25、　在开放地址法解决冲突时，同义词间及不同地址的结点争夺同一个后继散列地址的现象称(　聚集或堆积　 )。

26、　设散列函数H（k）=k % 7,散列表的地址空间是0~6，对关键字序列（32，13，49，55，22，38，21），  
采用拉链法处理冲突，试画出链表结构，并计算出该表的成功查找的ASL。ASL=（1*5+2*2）/7=9/7

27、　设散列函数H（k）=k % 7,散列表的地址空间是0~6，对关键字序列（32，13，49，55，22，38，21），画出按线性探查法解决冲突产生的散列表。求出用散列法查找各关键字所需要进行的比较次数。

28、　对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较? 
答：设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，一路比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。

29、.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：
　(1)查找不成功，即表中无关键字等于给定值K的记录；
　(2)查找成功，即表中有关键字等于给定值K的记录。
答：查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。
　　查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。

补充：

1、       查找表的数据结构表示
（1）　动态查找表和静态查找表： 若在查找的同时对表做修改操作(如插入和删除)，则相应的表称之为动态查找表。否则称之为静态查找表。
（2）　内查找和外查找： 和排序类似，查找也有内查找和外查找之分。若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。

2、　顺序查找的基本思想 ：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。

3、　顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构

4、　顺序查找中查找成功时的平均比较次数约为表长的一半。 若K值不在表中，则须进行n+1次比较之后才能确定查找失败。

5、     顺序查找的优点： 算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。顺序查找的缺点：查找效率低，因此，当n较大时不宜采用顺序查找。

6、　二分查找又称折半查找，它是一种效率较高的查找方法。
    　二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。

7、　判定树的形态只与表结点个数n相关，而与输入实例中R[1..n].keys的取值无关。

8、　二分查找成功时的平均查找长度为：    ASLbn≈lg(n+1)-1

二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：     

9、　二分查找的优点和缺点
　　虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。
　　二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
　　对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。

10、　分块查找(Blocking Search)又称索引顺序查找。　二分查找表由"分块有序"的线性表和索引表组成。

11、分块查找的基本思想是：
（1）　首先查找索引表：索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。
（2）　然后在已确定的块中进行顺序查找：由于块内无序，只能用顺序查找。

12、　分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。分块查找算法的效率介于顺序查找和二分查找之间。

13、　分块查找的优点是：
　　①在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。
　　②因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。
　　分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。

14、　当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表里动态查找表，则应选择二叉排序树作为其存储结构。

15、　输入序列决定了二叉排序树的形态。二叉排序树的平均执行时间亦为O(nlgn)。

16、　在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：
　　①在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，亦是(n+1)/2。
　　②在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是lgn。
　　③插入、删除和查找算法的时间复杂度均为O(lgn)。

17、　AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树度高约为lgn，AVL树是接近最优的。　

18、　B-树的多路平衡查找树适合在磁盘等直接存取设备上组织动态的查找表。

19、　B-树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成。

20、　　散列方法不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为O(1)。

21、　两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。

22、　散列函数的选择有两条标准：简单和均匀。

23、　常用散列函数：

（1）平方取中法    　具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。

（2）除余法    　该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=key％m　（m最好为素数）

（3）相乘取整法    　该方法包括两个步骤：首先用关键字key乘上某个常数A(0<A<1)，并抽取出key.A的小数部分；然后用m乘以该小数后取整。即：         
    　该方法最大的优点是选取m不再像除余法那样关键。

（4）随机数法    　选择一个随机函数，取关键字的随机函数值为它的散列地址，即    h(key)=random(key)
  　其中random为伪随机函数，但要保证函数值是在0到m-1之间。

24、　处理冲突的方法通常有两类方法处理冲突：开放定址法和拉链法。

25、　开放定址法的一般形式为： hi=(h(key)+di)％m 　1≤i≤m-1 
其中：
   　 ①h(key)为散列函数，di为增量序列，m为表长。
    　②h(key)是初始的探查位置，后续的探查位置依次是hl，h2，…，hm-1，即h(key)，hl，h2，…，hm-1形成了一个探查序列。
   　 ③若令开放地址一般形式的i从0开始，并令d0=0，则h0=h(key)，则有：
          hi=(h(key)+di)％m 0≤i≤m-1 
       探查序列可简记为hi(0≤i≤m-1)。

26、　开放定址法要求散列表的装填因子α≤l，实用中取α为0.5到0.9之间的某个值为宜。

27、　按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

28、       利用开放地址法的一般形式，线性探查法的探查序列为：       

hi=(h(key)+i)％m 0≤i≤m-1 //即di=i

29、　把这种散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积

30、　二次探查法的探查序列是：    hi=(h(key)+i*i)％m 　0≤i≤m-1 //即di=i2
　　 即探查序列为d=h(key)，d+12，d+22，…，等。 该方法的缺陷是不易探查到整个散列空间。

31、　双重散列法   该方法是开放定址法中最好的方法之一，它的探查序列是：
       hi=(h(key)+i*h1(key))％m　 0≤i≤m-1 //即di=i*h1(key)
    　即探查序列为： d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。
  　该方法使用了两个散列函数h(key)和h1(key)，故也称为双散列函数探查法。

32、　拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。

33、　在拉链法中，装填因子α可以大于1，但一般均取α≤1。

相关推荐

专栏推荐