1、（填空题） 16.在长度为n的顺序表L中将所有值为x的元素替换成y，该算法的时间复杂度为_____

2、（填空题） 31.设栈S和队列Q的初始状态都为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列，若6个元素出队序列是bedfca,则栈S的容量至少应有能够存放_____个元素的空间。

3、（填空题） 30.为了解决队列的假溢出现象，应采用____队列。

4、（填空题） 29._____又称为先进先出的线性表。

5、（填空题） 28.以下运算实现在链栈上的初始化，请在空白处用请适当句子予以填充。 typedef struct Node{DataType data; struct Node *next; }StackNode,*LStackTp; void InitStack(LStackTp &ls){_____;}。

6、（填空题） 27.后缀式(postfix expression，也叫逆波兰式，reverse Polish notation)123456-+/*+的值是:_____(如果结果不是整数，四舍五入保留一位小数。如结果为正数，不需要添加+号。请使用半角阿拉伯数字、小数点和负号如-012345.6789填写，不要添加空格等其它字符)

7、（填空题） 26.设栈S和队列Q的初始状态均为空，元素{1,2,3,4,5,6,7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是(2,6,5,4,7,3,1}，则栈S的容量至少是:_____

8、（填空题） 25.栈的运算遵循_____的原则。

9、（填空题） 24.某个含有n个元素的线性表可以采用单链表或双链表存储结构，但要求快速删除指定位置的结点，应采用_____.

10、（填空题） 23.有一个含有n个元素的线性表，可以采用单链表或双链表存储，其主要的操作是插入和删除第一个元素，最好选择_____作为存储结构。

11、（填空题） 22.有一个长度为n的循环单链表L，在p所指的结点之前插入一个新结点，其时间复杂度为______

12、（填空题） 21.对于一个具有n(n≥1)个结点的单链表，插入一个尾结点的时间复杂度是______

13、（填空题） 20.链接存储的特点是利用_____来表示数据元素之间的逻辑关系.

14、（填空题） 19.在有n个元素的顺序表中的任意位置插入一个元素所需移动元素的平均次数为_____

15、（填空题） 18.在有n个元素的顺序表中删除任意一个元素所需移动元素的平均次数为______

16、（填空题） 17.在长度为n的循环单链表L中查找值最大的结点，其时间复杂度为_____

17、（填空题） 32.以下运算实现在链栈上的退栈，请在空白处用请适当句子予以填充。 int pop(LStackTp &ls,DataType &x){ LStackTp p; if(Ls!=NULL){ p=ls; x=_____; Ls=ls->next; _____

18、（填空题） 15.假设顺序表第1个元素的内存地址是 100，每个元素占用2字节内存空间，则第5个元素的内存地址是_____

19、（填空题） 14.基本术语 _____是性质相同的数据元素的集合，是______的一个子集。

20、（填空题） 13.基本术语 _____是数据的基本单位，______是数据的不可分割最小单位。其中:前者在计算机中通常作为一个整体进行考虑和处理，它可以由一个或多个后者组成。

21、（填空题） 12.存储结构的分类 在计算机中，数据元素之间的关系有两种基本表示方法: _______,其特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系; _______,其特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。 请填:顺序映像/非顺序映像或顺序存储结构/链式存储结构。

22、（填空题） 11.逻辑结构的分类 数据结构可以从逻辑上分为两大类:_____和_____,其中后者包括集合结构、树状结构和图状结构。 请填:动态结构、静态结构、紧凑结构、非紧凑结构、线性结构、非线性结构、内部结构、外部结构。

23、（填空题） 10.数据结构的数学定义为一个二元组: DS =(D,R) 其中:DS 是数据结构，D是_______的有限集，R是D上_____的有限集.

24、（填空题） 9.关于抽象数据类型 抽象数据类型将使用与设计分离，实现封装和信息隐蔽，将抽象数据类型的声明与具体的实现分离开来. 在模块的_____使用抽象的数据和抽象的操作, 在模块的_____使用抽象的表示和操作的细节.

25、（填空题） 8.算法的量度 (1)算法所需执行时间的量度称为_____ (2)算法所需存储空间的量度称为_____

26、（填空题） 7.数据结构中评价算法的两个重要指标是_____和_____.

27、（填空题） 6.基本数据 ______是一组的值的集合，以及定义在这个值的集合之上的一组操作的总称.

28、（填空题） 5.基本术语 ______一般指由用户定义的、表示应用问题的数学模型，以及定义在该模型上的一组操作的总称。

29、（填空题） 4.基本术语 ______一般指由用户定义的、表示应用问题的数学模型，以及定义在该模型上的一组操作的总称。

30、（填空题） 3.基本术语 ______是指数据元素之间的关系.

31、（填空题） 2.基本术语 _______是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称.

32、（填空题） 1.基本术语 ________是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

33、（填空题） 53.在有n个顶点的有向图中，每个顶点的度最大可达_____.

34、（填空题） 69.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是_____的，否则称为_____ 的。(直接填写答案，前后不要留空格)

35、（填空题） 68.对包含10个记录的表r[1..10]进行简单选择排序，所需进行的关键字间的比较次数为_____。(直接填写答案，前后不要留空格)

36、（填空题） 67.直接插入排序可以通过设置_____来避免在寻找插入位置的过程中数组下标越界。(直接填写答案，前后不要留空格)

37、（填空题） 66.时间复杂度为O(nlogn)的排序算法有归并排序、堆排序和_____排序。

38、（填空题） 65.已知哈希表长度为 8，哈希函数为 H(k)=k mod 7，采用线性探测法处理冲突。将下列关键字依次插入到哈希表中， 20，14，27，21，34 请写出存入数据后的哈希表。 注:空白处填“_”。 若各关键字的检索概率相同，则平均查找长度为_____(保留1位小数，未位四舍五入)。

39、（填空题） 64.已知哈希表长度为 8，哈希函数为 H(k)=k mod 7，采用线性探测法处理冲突。将下列关键字依次插入到哈希表中, 34，36，20，16，41 请写出存入数据后的哈希表。 注:空白处填“_”。 若各关键字的检索概率相等，则平均查找长度为_____(保留1位小数，未位四舍五入)。

40、（填空题） 63.已知哈希表长度为 8，哈希函数为 H(k)=k mod 7，采用线性探测法处理冲突。将下列关键字依次插入到哈希表中， 34，37，20，16，13 请写出存入数据后的哈希表。 注:空白处填“-” 若各关键字的检索概率相等，则平均查找长度为____(保留1位小数，末位四舍五入)。

41、（填空题） 62.假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做______次插入和探测操作。

42、（填空题） 61.关于二分查找算法 在下面的有序表中 (15，24，32，47，50，58，62，79，83，96) 若采用二分查找算法，假设各元素的检索概率相同，则平均查找长度为_____

43、（填空题） 60.在下面的线性表中, (15，24，32，47，50，58，62，79，83，96) 若采用顺序搜索算法，则最大查找长度为_____.

44、（填空题） 59.关于二分查找算法 在下面的有序表中 (15，24，32，47，50，58，62，79，83，96) 若采用二分查找算法，则最大查找长度为_____.

45、（填空题） 58.在下面的线性表中 (15，24，32，47，50，58，62，79，83，96) 若采用顺序搜索算法，则查找元素 58 时，需要比较____次。

46、（填空题） 57.在下面的线性表中 (15，24，32，47，50，58，62，79，83，96) 若采用顺序搜索算法，假设各元素的检索概率相同，则平均查找长度为_____.

47、（填空题） 56.关于二分查找算法 在下面的有序表中 (15，24，32，47，50，58，62，79，83，96) 若采用二分查找算法，则查找元素 58时，需要比较_____次。

48、（填空题） 55.如图所示的AOE-网，求这个工程最早可能在什么时间结束?_____ B F E a C G I D H

49、（填空题） 70.按照排序过程涉及的存储设备的不同，排序可分为_____排序和_____排序。(直接填写答案，前后不要留空格)

50、（填空题） 52.如果含n个顶点的图形形成一个环，则它有_____棵生成树。

51、（填空题） 51.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_____条弧.

52、（填空题） 50.图的深度优先搜索(DFS)使用了一种数据结构，这种数据结构是_____.

53、（填空题） 49.假设二叉树的存储结构为二叉链表，在具有n个结点的二叉链表中(n>0)，左孩子指针域和右孩子指针域的个数为_____,空指针域的个数为_____.

54、（填空题） 47.已知一棵完全二叉树的第5层(设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多是:_____

55、（填空题） 45.在一棵度为4的树T中，10个度为1的结点，1个度为2的结点，10个度为3的结点，20个度为4的结点，则树T的叶结点个数是:_____

56、（填空题） 44.在含有n个结点的树中，边数只能是_____

57、（填空题） 42.若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______.

58、（填空题） 41.如果一棵二叉树有20个度为2的结点，则它的结点数量为:_____个。(填写半角阿拉伯数字如1234567890，不要添加空格等字符)

59、（填空题） 38.广义表(1,(2,3,(4,(5)),6),((7),8,9))的长度为_____，深度为_____

60、（填空题） 37.数组A中，每个元素的长度为3个字节，行下标i从1到8、列下标i以1到10、从首地址SA开始连续存放的存储器内、该数组按行存放、元素A[8[5]的起始地址为_____.

61、（填空题） 36.设二维数组a[10][20]，每个数组元素占用1个存储单元，若按列优先顺序存放数组元素，a[0][0]的存储地址为200、则a[6][2]的存储地址是多少?_____

62、（填空题） 35.字符串I LOVE GUANGZHOU!的长度是_____ (请以阿拉伯数字填写，前后不要有空格)

63、（填空题） 34.若n为主串长度，m为模式串长度，采用BF(Brute Force)模式匹配算法，在最好情况下需要的字符比较次数为_____.

64、（填空题） 33.设目标串text=“abccdcdccbaa”，模式串pattern=“cdcc”，若采用BF(Brute Force)算法,则在第_____趟匹配成功。