数据结构填空

2．数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序              存储方式、   链式         存储方式、索引存方式和散列方式。

3．数组采用顺序存储方式表示是因为通常不对数组进行__         插入删除      _______操作。

4．队列的修改是按______      先进先出        __的原则进行的；栈的修改是按先进后出                        的原则进行的。

5. 数据的逻辑结构在计算机存储器内的表示，称为数据的___   存储结构        _________。

6．设某双链表的结点形式为prior  data  next，若要在指针q所指结点(中间结点)的后面插入一个新结点s，则需执行下述语句段：

        s->prior=q                         ；s->next=q->next；q->next->prior=s；        q->next=s                 ；

7. 串S=″I□am□a□worker″(注: □为一个空格)的长度是_                         __13_。

8．数据的逻辑结构分为有四种，分别是集合结构、____线性结构      _______、  树状结构             和      网状结构           。

9. 下列程序段的时间复杂度为______O(n^2)__________。

　　product = 1;

　　for (i = n;i>0; i--)

　　　for (j = i+1; j　　　　product *=j;

10. 产生冲突现象的两个关键字称为该散列函数的__同义词                   ______。

11．在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为__                  O(n)_。

12. 已知链栈的结点结构为                ，栈顶指针为top，则实指针p所指结点插入栈顶的语句依次为____    p->next=top   ____和___    top=p    _____。

13、一个算法的效率可分为         时间          效率和        空间          效率。

15．线性表的元素长度为4，LOC(a1)=1000，则LOC(a5)=    1016          。

17. 删除双向循环链表中*p的前驱结点(存在)应执行的语句是___p->prior->prior->next=p; p->prior=p->prior->prior;__                                         ______。

18．已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的_____直接前驱______结点。

         q=p;

     while(q->next!=p)     q=q->next;

19．若有一棵二叉排序树，则按照中序遍历顺序将产生一个       按关键字有序          序列。

20．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是_________                                  删除p的直接后继结点     _______。

21. 假设一个6阶的下三角矩阵B按列优先顺序压缩存储在一维数组A中，其中A［0］存储矩阵的第一个元素b11,则A［14］存储的元素是___ b63___。

22．栈的操作是按           先进后出             的原则进行的。

23. 空串的长度是_____     0         ___；空格串的长度是____                                           空格的个数__。

24．如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为_           41    _____。

25．若一棵满三叉树中含有121个结点，则该树的深度为_____       5______。

26．假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为_____                     _SXSSXXSSXSSXXX_____。

27．对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二

28. 栈下溢是指在__    栈空            __________时进行出栈操作。

  29、某二叉树的先根遍历序列是ABDGCEFH ；中根遍历序列是DGBAECHF；则其后根遍历序列是         GDBEHFCA                     。

30．链栈s在进行出栈操作时首先要判断 栈是否为空                   。

31．图的存储结构包括有        邻接矩阵            和            邻接表            。

32. 在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是____2            ____。

33．将一个n阶对称矩阵的下三角各元素(包括对角线上的元素)存储在一维数组v中，则v至少有     (n+1)n/2       个元素。

34、任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点数         n-2m+1        个。

35．结点数为20的二叉树可能达到的最大高度为___20______。

26、在单链表中，若在p所指结点 前 插入一个新结点，时间复杂度为           O(n)        。

37、引起循环队列队头位置发生变化的操作是　(Q.front+1)%MAXQSIZE　　　　　　。

38．树中结点的最大层次称为树的      高度         。

39．对n个元素进行起泡排序时，最少的比较次数是  n-1              。

叉树的     左子树             上继续查找。

40．在n个结点的顺序表中删除一个结点需平均移动         （n-1）/2              个结点。

41．在n个结点的顺序表中插入一个结点需平均移动          n/2             个结点。

42．若二叉树中度为2的结点有n个，则度为0的结点个数为   n+1            。

43. 已知完全二叉树T的第5层只有7个结点，则该树共有_11____          _______个叶子结点。

44．结点数为20的二叉树可能达到的最大高度为_______20__。

45．两个串相等的充分必要条件是两个串的长度相等且_每个位置的字符都相等___                                        _____。

46．若二叉树中度为2的结点有n个，则度为0的结点个数为    n+1           。

47. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。

若s=”ABCDEFGHIJK”,t=”ABCD”,执行运算substr(s,strlen(t), strlen(t))后的返回值为______     “DEFG”             ______。

48. 去除广义表LS=(a1,a2,a3,……，an)中第1个元素，由其余元素构成的广义表称为LS的_____     表尾        _______。

49．对关键字序列(50，34，92，19，11，68，56，41，79)进行直接插入排序，当将第7个关键字56插入到当前的有序子表中时，

为寻找插入位置需进行___        3     ___次关键字之间的比较。

50．在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的___                    __字串定位______运算。

51．若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的_______ vi为起点的个数  _________。

52．已知广义表LS为空表，则其深度为__    1         ____。

53．假设以行优先顺序存储三维数组A[5][6]，其中元素A[0][0]的地址为1100，且每个元素占2个存储单元，则A[4][3]的地址是___  1154   ___。

54．已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则它的后序序列为_                  ___CBDA__。

55．在n个结点的顺序表中插入一个结点需平均移动     n/2                  个结点。

56．在含n个顶点的连通图中，任意两个不同顶点之间的一条简单路径最多包含___                   __n-1_条边。

57. 在有向图中，以顶点v为终点的边的数目称为v的___                        __入度_______。

58．若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的_______ vi为起点的个数      _________。

59、一个算法的效率可分为   时间                效率和     空间             效率。

60．图的遍历包括深度优先遍历和     广度优先遍历                          。

61．假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为___       5n-6   ___。

62．在含100个结点的完全二叉树中，叶子结点的个数为___50________。

63. 广义表LS=(a1,a2,a3,……，an)中第1个元素, 称为LS的____表头_             _______。

．将有序表中n个元素依次插入到一棵空的二叉排序树中，则在等概率查找的情况下，

该二叉排序树在查找成功时的平均查找长度是_     (n+1)/2         _____。

65. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。

若s=”ABCDEFGHI”,t=”AB”,执行运算substr(s,strlen(t), strlen(t))后的返回值为______                  ___” DEFG”___。

66. 在有向图中，以顶点v为起点的弧的数目称为v的___                        ______出度___。

67. 对长度为20的有序表进行二分查找的判定树的高度为____ 5                 ____。

68. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为______n-(n-1)/k______。

69. 在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，

它们依次是__   _s->next->next=p->next_                          __和p->next=s _                               __。

70. 假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为__ 55                 ___。

71．在无向图中，若从顶点a到顶点b存在____  路径        _______，则称a与b之间是连通的。

72. 已知完全二叉树T的第4层只有3个结点，则该树共有_____          5_______个叶子结点。

73. 在有向图中，以顶点v为起点的弧的数目称为v的___                        ______出度___。

74. 设S1="good",S2="  ",S3="book"，则S1，S2和S3依次联接后的结果是__” good  book “__________。

75. 在n个结点的线索二叉链表中，有___    n+1                 __个线索指针。

76．对关键字序列(50，34，92，19，11，68，56，41，79)进行直接插入排序，当将第8个关键字41插入到当前的有序子表中时，

为寻找插入位置需进行___         5    ___次关键字之间的比较。

77、一个算法的效率可分为        时间           效率和        空间          效率。

78. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。

若s=”ABCDEFGHI”,t=”AB”,执行运算substr(s,strlen(t), strlen(t))后的返回值为______                  __” BC”____。

79. 已知完全二叉树T的第4层只有3个结点，则该树共有_____    5      _______个叶子结点。

80．对n个元素进行起泡排序时，最少的比较次数是    n-1            。

81. 在队列中，允许进行插入操作的一端称为___        队尾______，允许进行删除操作的一端称为___队头__           __。

82、一个算法的效率可分为    时间               效率和       空间           效率。

5. 利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为____                                     __(_75 66 48 29 31 37 )_  )。

83．对n个元素进行起泡排序时，最少的比较次数是    n-1            。

84．对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的                  左子树     上继续查找。

85. 对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为①【48 44】52 【63 80 91】

②【44】48 52 63【80 91】

③ 44 48 52 63 80【91】

86. 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，

得到的输出序列为_    bceda                        __。

87. 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需___                          _向前移动___一个位置。

88. 如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用__        堆排序              ____较为适当。

. 对长度为20的有序表进行二分查找的判定树的高度为5               ____。

90. 由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到__      50005000        ___。

91．对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的            左子树           上继续查找。

92. 已知完全二叉树T的第5层只有7个结点, 则该树共有          11        个叶子结点.

93. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为_O(nlogn)__                     __。

94. 若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为_       O(n^2)     ___。

95．树中结点的最大层数称为树的     高度          。