数据结构与原理分析01343

发布日期:2013-11-12 点击次数:3051

联系人 许老师 QQ530515000  电话15543529056 QQ 530515000

数据结构原理内部资料 严禁外泄

1.什么是增长树？答：当二叉树中结点没有左子树形或没有右子树形时，增加特殊的结点，由此生成的二叉树称为增长的二叉树，简称增长树。

2.什么是线性表？答：一个线性表是由零个或多个具有相同类型的结点组成的有序集合。

3.什么是一维数组？答：一维数组是若干个元素的一个有限序列，每个元素都通过一个下标来指定，所有的数组元素都具有相同的数据类型，占据相同大小的存储空间.

4.什么是森林？答：一个森林就是一组（0个或多个）不相交的树形（通常诸树形间还有次序）。

5.什么是强连通图？答：若G为有向图，且对于V(G)中任意两个不同的顶点和，与连通，与也连通，则称G为强连通图。

6.什么是图中两点的简单路径？答：如果一条路径上除了起点和终点可以相同外，再无相同的顶点，则称此路径为简单路径。

7.设单链表中存放着n个字符，设计算法判断字符串是否中心对称，如xyzzyx即为中心对称的字符串。

答：将全部字符进栈，然后将栈中的字符逐个与链表中的字符比较

队列的定义是什么？答：队列是一种操作受限的线性表，它只允许在表的一端进行插入，在表的另一端进行删除。

8. 字符串的定义是什么？答：字符串是由零个或多个字符（字母、数字及其它一些符号）组成的有限连续序列，简称为串。

9. 二叉树的定义是什么？答：二叉树是结点的有限集合，它必须满足下面的一个条件：它是空集。

它由一个根结点和根结点的左右子树构成，且其左右子树满足二叉树定义。

10. 有向图的定义是什么？答：图G由两个集合V和E组成，记为G = (V , E) . 其中V是顶点的有限集合，E是连接V中两个不同顶点（顶点对）的边的有限集合。如果E中的顶点对是有序的，即E中的每条边都是有方向的，则称G为有向图。

11. AOV网的定义是什么？答：用顶点表示活动，有向边表示活动之间先后关系的有向图简称为AOV网。

12.设计一个算法，求出无向无权连通图中距离顶点v的最短路径长度为k的所有顶点，路径长度以变数为单位计算。

答：算法中须用从顶点v出发广度优先遍历的层次特性来求解，因此，访问顶点时要知道一个顶点相对于v的层数，而每个顶点的层数是由其前驱顶点决定的。

可以从顶点v开始，每访问到一个顶点就根据其前驱的层数计算该顶点的层数，并将层数值与顶点编号一起入队和出队。算法中可以使用两个队列，一个记录入队的顶点编号，另一个记录该顶点的层数，并保持二者的同步。

13. 两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。

1) 给出算法的基本设计思想 (4分)；

2) 用算法描述语言描述算法，并要求对算法中的关键步骤给出注释。

答：1）本题实质上是一个模式匹配问题，这里匹配的元素是整数而不是字符。因两整数序列已存入两个链表中，操作从两链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则A链表从上次开始比较结点的后继开始，B链表仍从第一结点开始比较，直到B链表到尾表示匹配成功。A链表到尾B链表未到尾表示失败。操作中应记住A链表每次的开始结点，以便下趟匹配时好从其后继开始。

2）int  Pattern（LinkedList A，B）

∥A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列。如是，返回1；否则，返回0表示失败。

{p=A；   ∥p为A链表的工作指针，本题假定A和B均无头结点。

 pre=p； ∥pre记住每趟比较中A链表的开始结点。

 q=B；   ∥q是B链表的工作指针。

 while（p && q）

   if（p->data==q->data） {p=p->next；q=q->next；}

   else{pre=pre->next；p=pre； ∥A链表新的开始比较结点。

        q=B；}                 ∥q从B链表第一结点开始。

if（q==null）return（1）；   ∥B是A的子序列。

else   return（0）；          ∥B不是A的子序列。

}∥算法结束。

14.设一棵二叉树的先序、中序遍历序列分别为：

先序遍历序列： A B D F C E G H 

中序遍历序列： B F D A G E H C

请画出这棵二叉树。

15.编写一个将二叉树中每个结点的左右孩子交换的算法。

(1) 给出算法的基本设计思想；

(2) 用算法描述语言描述算法，并要求对算法中的关键步骤给出注释。

答：（1）用前根遍历的递归算法交换二叉树中各结点的左、右子树。

（2）算法的C++实现：

BintreeNode *swap(BintreeNode *b)

{

      BintreeNode *t, *t1, *t2;         //t为交换后的二叉树

      if (b = = NULL)  t=NULL;

      else  {

      t= new BintreeNode ;  //复制一个根节点

      t->data = b->data;

      t1 = swap (b->left);

      t2 = swap (b->right);

      t->left = t2;

      t->right = t1;}

return (t);}

16．假定整型数组A[n]中有多个零元素，试设计一个算法将A中所有非零元素依次移到A的前端。(1) 给出算法的基本设计思想；(2) 用算法描述语言描述算法，并要求对算法中的关键步骤给出注释。

答：（1）方法1：因为数组是一种根据元素下标可以直接存取的数据结构，设置一个辅助变量pos，表示当前可存放非零整数的数组元素下标，开始指向数组中第一个元素，从前向后依次检测A中元素，当在A中检测到一个非零元素A[j]时，则置A[pos]A[j]，pospos+1 .方法2：设置两个指针j和pos，首先用pos指向从前向后找到的第一个零元素，用j指向从前向后找到的第一个非零元素，然后A[pos]A[j] ，重复上述过程。

（2）ADL描述：方法1：

算法MoveFront( A,,int n.A)

//* 算法MoveFront将一维数组A中所有非零元素依次移到A的前端 *//

 F1.  [初始化]

pos1 .

 F2.  FOR  j=1  TO  n  DO

  IF(A[j]0 ) THEN

  ( IF(j=pos)  THEN   pospos+1.

   IF ( jpos)  THEN

   (    A[pos] A[j] .

        pospos+1.

A[j] 0.)

       )

ADL描述：方法2：

算法MoveFront( A,,int n.A)

//* 算法MoveFront将一维数组A中所有非零元素依次移到A的前端 *//

F1.  [初始化]

 j1.

F2.  L:  IF  j>n THEN RETURN.

        IF  A[j]=0  THEN ( posj.  ipos+1. GoTo M.)

        jj+1.

        GoTo  L.

M:  IF A[i]=0  THEN (ii+1. GoTo  M)

        ELSE  A[pos]A[i].

        jpos+1.

        GoTo L.

 

17.画出后缀表达式 ab+cde+*-f-gh+* 对应的二叉表达式树。

答：

18.用序列(46,88,45,39,70,58,101,10,66,34)建立一棵二叉查找树，画出该树。

答：

 

 

 

 

 

 

 

 

 

 

19.已知一颗树的后根遍历次序和节点次数序列如下，请画出这棵树，并给出其先根遍历次序。

后根遍历次序：B D E F C G J K I L H A

    节点次数序列：0 0 0  0 3 0 0 0 2 0 2 4

答： 树形如下：

 

   先根遍历次序：ABCDEFGHIJKL     

 

 

20. 具有n个结点的二叉树采用链接结构存储，链表中存放NULL指针域的个数为（n+1）。

21．串是（任意有限个字符构成的序列）。

22．在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（2   ）。

23．某二叉树的前序和后序序列正好相反，则该二叉树一定是什么二叉树(高度等于其结点数)。

24. 对于栈操作数据的原则是（后进先出  ）。

25．若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中数据元素的个数是（n-i ）。

26. 线性表的基本存储结构有哪两种？它们关于空间使用情况和各种操作（包括删除、插入和随机存取）的优缺点各是什么？

答： 有线性存储和链接存储2种。

      ①内存空间的占用情况：因链表多了一个指针域，故较浪费空间，因此，在空间占用方面，数组优于链表。

② 插入与删除操作：由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改变一些指针的链接，因此，链表比数组易于实现数据的插入和删除操作。

③ 数据的存取操作：访问链表中的结点必须从表头开始，是顺序的存取方式，而数组元素的访问是通过数组下标来实现的，是随机存取方式，因此，在数据存取方面，数组优于链表。

27.什么是权图？答：设G = (V，E)是图，若将图中的每条边L都赋上一个实数w(L)作为边的权值，则称G为权图。

28. 在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该(只有左子树上的所有结点  )。

29. 排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为(  插入排序  )。

30. 若一棵二叉树具有45个度为2的结点，6个度为1的结点，则度为0的结点个数是（46  ）。

31.某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树(空或只有一个结点)。

32. 在一个有向图中，所有顶点的入度之和等于所有边数（ 4  ）倍。

33．串是（任意有限个字符构成的序列  ）。

34．对于栈操作数据的原则是（后进先出  ）

35. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是(D,A,B,C )。

36. 结点前序为xyz的不同二叉树，所具有的不同形态为(5 )。

37. 一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的起始地址为100，则该数组的首地址是（70）。

38．在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(2h  )。

39. 在一个无向图中，所有顶点的度数之和等于所有边数（  2 ）倍。

40.因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 (d ).

41. 一般情况下，将递归算法转换成等价的非递归算法应该设置（堆栈）。

42. 对于一棵满二叉树，m个树叶，n个结点，深度为h,则(n=2h＋1-1  )。

43. 线性表的长度是指（表中的元素个数）。

44. 用邻接表表示图进行深度优先遍历时，通常用来实现算法的辅助结构是(栈  )。

45. 堆的形状是一棵(完全二叉树   )。

46. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ cabdef）。

47. 若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该

是（ C. 1≤i≤n）。

48．在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（2 ）。

49. 若某线性表中最常用的操作是取第i个元素和删除最后一个元素，则采用什么存储方

式最节省时间（顺序表）。

50．一组记录的关键字为{45, 80, 55, 40, 42, 85}，则利用堆排序的方法建立的初始堆为（85, 80, 55, 40, 42, 45 ）。

51. 如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2中结点的（先根序列）。

52.简述堆栈与队列的相同与不同之处。答：相同之处：都是线性表；不同之处：操作受限的条件不同。

53. 对于一棵满二叉树，m个树叶，n个结点，深度为h,则(n=2h＋1-1 )。

54.具有n个顶点的有向图最多可包含的有向边的条数是(n(n-1) )。

55．设有6000个无序的元素,希望用最快的速度挑选出其中前5个最大的元

素,最好选用(堆排序)法。

56.任何一个无向连通图的最小生成树(有一棵或多棵  )。

57. 排序方法中，从未排序序列中挑选元素，将其放入已排序序列的一端的方法，称为(选择排序)。

58. 对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（R[6]，R[2]，R[4]，R[3]      ）。

59. 因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 (d  )。

60.深度为h且有多少个结点的二叉树称为满二叉树(2h+1-1       )。

61．某二叉树的前序和后序序列正好相反，则该二叉树一定是的二叉树为(高度等于其结点数)。

62. 带头结点的单链表head为空的判断条件是(head->next==NULL)。

63．栈和队列的主要区别在于（插入删除运算的限定不一样）

64. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为(2h-1   )。

65．在一个单链表中，若删除(*p)结点的后继结点，则执行(p->next=p->next->next)。

66.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（n+1       ）

67.若一棵二叉树有11个度为2的结点，则该二叉树的叶结点的个数是（12  ）。

68. 对有n个记录的表按记录键值有序建立二叉查找树，在这种情况下，其平均查找长度的量级为（O(n)  ）。

69. 有向图中，以顶点v为终点的边的数目，称为顶点v的（入度）。

70. 链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况)。

71. 若频繁地对线性表进行插入和删除操作，该线性表应该采用的存储结构是（链式）。

72. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（3 2 1 5 4）。

73.设森林F中有三棵树，第一、第二和第三棵的结点个数分别为m1,m2和m3,则森林F对应的二叉树根结点上的右子树上结点个数是 (  m2+m3  )。

74. 有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉查找树，若希望高度最小，则应选择下面输入序列是（ 37,24,12,30,53,45,96）。

75.什么是串的长度？答：串包含的字符总数被称为串的长度。

76.什么是线性表的链接存储？答：线性表的链接存储是指线性表中的结点在内存中任意存放，相邻结点间用指针链接。

77．若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向(各自的尾结点   )。

78. 试给出二叉树的自下而上、自右而左的层次遍历算法。

1) 给出算法的基本设计思想；

2) 用算法描述语言描述算法，并要求对算法中的关键步骤给出注释。

答：1）借助栈，最后弹出栈中元素实现对二叉树按自下至上，自右至左的层次遍历。

2）void InvertLevel(biTree bt)  // 对二叉树按自下至上，自右至左的进行层次遍历

{if(bt!=null)

 {StackInit(s); //栈初始化，栈中存放二叉树结点的指针

  QueueInit(Q); //队列初始化。队列中存放二叉树结点的指针

 QueueIn(Q,bt);

while(!QueueEmpty(Q))    //从上而下层次遍历

{p=QueueOut(Q); push(s,p);   //出队, 入栈

if(p->lchild) QueueIn(Q,p->lchild);  //若左子女不空，则入队列

if(p->rchild) QueueIn(Q,p->rchild);} //若右子女不空,则入队列

while(!StackEmpty(s)) {p=pop(s); printf(p->data);} //自下而上,从右到左的层次遍历

}//if(bt!=null)

} //结束InvertLevel

79. 二叉树的第I层上最多含有结点数为（2I ）。

80.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（     2h-1  ）。

已知一个带有表头结点的单链表，结点结构为（data, link）。假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找出链表中倒数第k（k为正整数）个位置上的结点。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：

(1) 描述算法的基本设计思想；

(2) 用算法描述语言描述算法；

(3) 给出算法的时间复杂性分析。

解答：算法的基本思想如下：

定义两个指针变量p和q，初始时均指向头结点的下一个结点。P指针沿链表移动，当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，q指针所指元素为倒数第k个结点。

      以上过程对链表仅进行一遍扫描。时间复杂度为O(n)。

      算法的详细步骤：

count=0，p和q指向链表表头结点的下一个结点；

若p为空，转5)；

若count等于k则q指向下一个结点，否则count=count+1；

p指向下一个结点，转2);

若count等于k，则查找成功，输出该结点的data域的值，返回1；否则查找失败，返回0。

（5、1）2.A和B是长度为n的两个数组。设计一个算法，该算法输出长度为n的数组C，要求：（1）数组C中的每一个元素C[i] = || {A[j]| A[j]≤B[i], 1≤j≤n} ||, 其中||S||表示集合S中的元素个数。例如：下表给出了长度为4的两个数组A和B，以及满足要求的数组C；（2）所设计算法尽可能高效。

(1) 描述算法的基本设计思想；

(2) 用算法描述语言描述算法。

(3) 给出算法的时间复杂性分析。

解答：算法的基本思想如下：

   第一步：采用一个时间复杂性为O(nlogn)的算法对数组A进行排序； 

   第二步：对B中的每个元素B[i]执行

   采用对半查找法一个位置k，使得当 j<=k时，A[j]<=B[i]，当 j>k时，A[j]>B[i]

    C[i]=k

   该算法第一步需要O(nlogn)时间进行排序；第二步执行n次循环，每次循环对半查找算法执行了O(logn)次比较；因此，算法的时间复杂性为O(nlogn)。

81.如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2中结点的（先根序列  ）。

82. 用分划交换排序方法对包含有n个关键的序列进行排序，最坏情况下执

行的时间杂度为(O(n2))。

83. 有n个叶子的哈夫曼树的结点总数为（2n-1   ）。

84. 稀疏矩阵一般采用的压缩存储方法为(三元组表)。

85. 若二叉树中度为2的结点有15个，度为1 的结点有10个，则叶子结点的个数为（16   ）。

86. 若某完全二叉树的深度为h，则该完全二叉树中具有的结点数至少是(2h－1 )。

87. 任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置(肯定不发生变化)。

88.初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为(  n-1)。

89. 对有n个记录的有序表采用二分查找，其平均查找长度的量级为(O(log2n))。

90.用冒泡排序法对序列{18,16,14,12,10,8}从小到大进行排序，需要进行的比较次数是(15 )。

91.在一个有向图中，所有顶点的出度之和等于所有边数的倍数是（ 1 ）。

92.有n个顶点的图采用邻接矩阵表示，则该矩阵的大小为（n*n  ）。

93.6个顶点的无向图成为一个连通图至少应有边的条数是（5  ）。

94. 对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（R[6]，R[4]，R[2]，R[3]）。

95. 串是（任意有限个字符构成的序列）。

96.个无向图中，所有顶点的度数之和等于所有边数（1     ）倍。

97.单链表表示的链式队列的队头在链表的什么位置（链头    ）。

98. 一组记录的关键字为{45, 80, 55, 40, 42, 85}，则利用堆排序的方法建立的初始堆为（85, 80, 55, 40, 42, 45 ）。

99. 对于一棵满二叉树，m个树叶，n个结点，深度为h,则(n=2h＋1-1)

100.某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树(空或只有一个结点)。

101.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（n+1 ）。

102. 若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动表中元素的个数是（n-i+1）。

103. 树中所有结点的度等于所有结点数加（-1   ）。

什么是队列的顺序存储？答：队列的顺序存储是指利用一组地址连续的存储单元依次存放自队头到队尾的数据元素。

104.什么是数组？答：数组通常被定义为具有相同数据类型的元素的集合。

105.什么是满二叉树？答：一棵高度为的满二叉树，是具有个结点且高度为的二叉树

106.什么是连通图？答：设G是无向图，若从顶点到顶点有路径，则称与连通。若G为无向图，且V(G)中任意两顶点都连通，则称G为连通图。

107.什么是拓扑排序？答：拓扑序列把AOV网中的所有顶点排成一个线性序列，该序列满足如下条件：若AOV网中存在边 ，则在该序列中，必位于之前。构造AOV网的拓扑序列的操作被称为拓扑排序。

108.设二叉树根结点的层次为0，一棵高度为h 的满二叉树中的结点个数是(2h+1-1   )。

109. 将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点(有左孩子，无右孩子)。

110. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(  BA+180  )。

111.在一个具有n个顶点的完全无向图的边数为 (n(n-1)/2 )。

112．设森林F中有三棵树，第一、第二和第三棵的结点个数分别为m1,m2和m3,则森林F对应的二叉树根结点上的右子树上结点个数是 (m2+m3  )。

113.对于键值序列{72,73,71,23,94,16,5,68,76,103}用筛选法建堆，开始结点的键值必须为(94 )。

114.树（或树形）的定义是什么？答：一个树（或树形）就是一个有限非空的结点集合T，其中有一个特别标出的称为该树之根root（T）的结点；其余（除根外）的结点划分成个不相交集合,而且这些集合的每一个又都是树。

115. 在图形结构中，每个结点的前驱结点数和后续结点数可以有(任意多个  )。

116.什么是树的路径长度？答：树的路径长度是指从根结点到树中每个叶结点的路径长度之和。

117.对有n个记录的有序表采用二分查找，其平均查找长度的量级为(O(log2n)  )。

118. 用孩子兄弟链表表示一棵树，若要找到结点x的第5个孩子，只要先找到x的第一个孩子，然后(从兄弟域指针连续扫描4个结点即可)。

119．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功的比较次数是（4  ）。.

120. 当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为(n-1 )。

121.深度为h的满二叉树具有的结点个数为（2h+1-1     ）。

122. 二维数组A[5][6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为3000的连续的内存单元中，则元素A[4][5]的存储地址为（3145）。

123.一个具有n个顶点e条边的无向图中，采用邻接表表示，则所有顶点的邻接表的结点总数为（2e   ）。

124. 一个具有n个顶点的图采用邻接矩阵表示，则该矩阵的大小为（n*n）。

125. 一个具有n个顶点e条边的无向图中，采用邻接表表示，则所有顶点的邻接表的结点总数为（ 2e ）。

126. 若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向(  各自的尾结点)。

127．在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(2h  )。

128. 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用比较次数最少的方法是（直接插入排序）。

129. 有n个叶子的哈夫曼树的结点总数为（2n-1 ）。

130.二分查找法要求查找表中各元素的键值必须是(递增或递减  )。

131. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂性为（）。

132.链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况  )。

133. 将长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为(O(n) )。

134.若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（直接插入排序）方法比较次数最少。

135. 若字符串“1234567”采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节，则该字符串的存储密度为（33.3﹪）。

136.用分划交换排序方法对包含有n个关键的序列进行排序，最坏情况下执

行的时间杂度为(O(n2) )。

137. 若在一棵非空树中，某结点A有3个兄弟结点（包括A自身），B是A的双亲结点，则B的度为（3）。

138. 单链表中，增加头结点的目的是为了（方便运算的实现）。

139. 深度为h的满二叉树所具有的结点个数是（2h+1-1 ）。

140．按照二叉树的定义,具有3个结点的二叉树有多少种(5 )。

141. 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为(O(n) )。

142．树中所有结点的度等于所有结点数加（-1   ）。

143. 树中所有结点的度等于所有结点数加（  -1     ）

144. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是(ZXY )。

145. 用邻接表表示图进行深度优先遍历时，通常采用的辅助存储结构是(栈)。

146. 对有18个元素的有序表作二分（折半）查找，则查找A 3的比较序列的下标为（9、4、2、3）。

147. 在含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为（ n2-2e）。

148. 树形结构的特点是：一个结点可以有 (  多个直接后继)。

149. 使具有30个顶点的无向图成为一个连通图至少应有边的条数是（29）。

150. 按照二叉树的定义,具有3个结点的二叉树具有的种类为(5 )。

151. 使具有9个顶点的无向图成为一个连通图至少应有边的条数是（8  ）。

152. 在顺序表（n足够大）中进行顺序查找，其查找不成功的平均长度是（n+1 ）。

153. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1  则T中的叶子数为（ 8   ）。

154. 栈的插入和删除操作进行的位置在（栈顶）。

155.什么是满树？答：一棵树，如果它的所有分支结点具有相同的度（或曰次数），并且它的所有叶结点都位于同一层上，则我们称该树为满树。

156. 某二叉树的前序和后序序列正好相同，则该二叉树一定是的二叉树为(空或只有一个结点)。

157. 链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况)。

158. 对稀疏矩阵进行压缩存储是为了（节省存储空间）。

159. 结点前序为xyz的不同二叉树，所具有的不同形态为(5 )。

160. 若一棵二叉树具有20个度为2的结点，6个度为1的结点，则度为0的结点个数是（21 ）。

161. 一棵线索二叉树的线索个数比链接个数多（ 2 ）个。

162. 若一棵二叉树有10个叶结点，则该二叉树中度为2的结点个数为9。

163．在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2。

164.对于一棵二叉树，设叶子结点数为n0,次数为2的结点数为n2,则n0和n2的关系是n0= n2＋1。

165.什么是子串？答：一个串的子串系指该串中的任意一个连续子序列

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

167. 普里姆(Prim)算法适用于边稠密图。

168.深度为h且有2k-1个结点的二叉树称为满二叉树。(设根结点处在第1层)。

169.图的深度优先搜索方法类似于二叉树的先序遍历 。

170.哈夫曼树是带权路径长度最小的二叉树。

171. 二叉树的存储结构有顺序存储结构和链式存储结构。

172. 哈夫曼树是带权路径长度最小 的二叉树。

173.一般树的存储结构有双亲表示法、孩子兄弟表示法和孩子链表表示法。

174. 将数据元素2,4,6,8,10,12,14,16,18,20依次存于一个一维数组中，然后采用折半查找元素12，被比较过的数组元素的下标依次为5，7，6  。。

175. 图的深度优先遍历序列不是唯一的。

176. 下面程序段的时间复杂度是 O（mn） 。

for (int i=1;i<=n;i++)

  for (int j=1;j<=m;j++)

        a[i][j]=0;

177. 基于关键词比较的排序算法的下界是什么？请指明直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、两路合并排序算法中，哪些算法的时间复杂度达到了排序下界，并简单分析其能够达到下界的原因。

 答：O(nlogn).

快速排序，堆排序，合并排序达到下界。主要原因分别是，快速排序的分划方法一次消除多个反序对，堆排序采用基于树形的最大元查找策略，合并排序采用分治法。

178. 图的遍历是指从图中某一顶点出发访问图中全部顶点且使每一顶点仅被   访问一次。

179. 在一个图中，所有顶点的度数之和等于所有边的数目的2倍 。

180. 由一棵二叉树的后序序列和中序序列可唯一确定这棵二叉树 。

181. 在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2。

182. 若二叉树的一个叶子结点是某子树的中根遍历序列中的第一个结点，则它必是该子树的后跟遍历中的第一 个结点。

183.在直接插入排序、直接选择排序、分划交换排序、堆排序中稳定的排序方法有直接插入排序。

184.具有100个结点的完全二叉树的叶子结点数为50。

185.普里姆(Prim)算法适用于边稠密图。

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

187.将一棵树转换成一棵二叉树后，二叉树根结点没有右子树。

188.循环队列的引入，目的是为了克服  假溢出    。

189.若连通网络上各边的权值均不相同，则该图的最小生成树有1棵 。

190．在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2 。

191.栈和队列的共同特点是插入和删除均在端点处进行。

192. 二叉树的遍历方式有三种：先序遍历、中序遍历、后序遍历。

193. 若连通图的顶点个数为n，则该图的生成树的边数为n-1。

194.图的存储结构最常用的有邻接矩阵和邻接表。

195. 若一棵二叉树有15个叶结点，则该二叉树中度为2的结的点个数为14。

196．队列中允许进行插入的一端称为队尾。

197.拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在环。

198.在有序表(15,23,24,45,48,62,85)中二分查找关键词23时所需进行的关键词比较次数为2。

199. 则高度为k的二叉树具有的结点数目，最少为k，最多为2k-1。

200. 若连通网络上各边的权值均不相同，则该图的最小生成树有1棵 。

201. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是3 1 2。

202. 设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为    3     。

203. 对于一棵二叉树，设叶子结点数为n0,次数为2的结点数为n2,则n0和n2的关系是     n0= n2＋1    。

204. 设某二叉树的后序遍历序列为ABKCBPM，则可知该二叉树的根为 M 。

205. 数据结构的三个方面：数据的   逻辑结构、物理结构、  运算。

206. 每个结点只有  一个  链接域的链表叫做单链表。

207. 设无向图G的顶点数为n，则要使G连通最少有 n-1条边。

208. 组成串的数据元素只能是字符。

209．图的存储结构最常用的有邻接表  和邻接矩阵。

210. 由一棵二叉树的后序序列和中序序列 可唯一确定这棵二叉树。

211. 队列中允许进行插入的一端称为队尾。

212.对于一个队列，如果输入项序列由1,2,3,4所组成，试给出全部可能的输出序列。答：1,2,3,4。

213. 已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。

中序序列：c，b，d，e，a，g，i，h，j，f

前序序列：a，b，c，d，e，f，g，h，i，j

答：该二叉树的后序序列为：c,e,d,b,i,j,h,g,f,a

214. 为什么说树是一种非线性结构？

答：树中的每个结点除了根结点外，其余每个结点有一个直接前驱，但有多个直接后继，所以说树是一种非线性结构。

215.什么是单向循环链表？答：单向循环链表系指将单链表中表尾结点的next域指向表头结点，而不是存放空指针NULL，形成一个环形链表。

216．将算术表达式a+b*（c+d/e）转为后缀表达式。

答：  B．abcde/+*+   

217. 找出所有这样的二叉树形，其结点在先根次序遍历和中根次序遍历下的排列是一样的。

答： 为空树，或为任一结点至多只有右子树的二叉树。

218.有个顶点的无向连通图至少有多少条边？有个顶点的有向连通图至少有多少条边？

答：有个顶点的无向连通图至少有n-1条边，有个顶点的有向连通图至少有n条边。

219．下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问，哪些排序方法是稳定的？

答：起泡排序, 直接插入排序，归并排序是稳定的。
220. 完全二叉树用什么数据结构实现最合适，为什么？

答：完全二叉树用一维数组实现最合适。因为完全二叉树保存在一维数组中时，数组内没有空洞，不存在空间浪费问题；另外，顺序存储方式下，父子结点之间的关系可用公式描述，即已知父（或子）结点寻找子（或父）结点只需计算一个公式，访问结点方便。但采用链表存储时就存在空间浪费问题，因为每个结点要另外保存两个链接域，并且寻找结点也不容易。

221．线性表有两种存储结构：一是顺序表，二是链表。试问：如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？

答：选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。

222．试述顺序存储和链式存储的区别及各自的优缺点。

答：数组占用连续的内存空间，链表不要求结点的空间连续。                  

1）插入与删除操作：由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改变一些指针的链接，因此，链表比数组易于实现数据的插入和删除操作。

2）内存空间的占用情况：因链表多了一个指针域，故较浪费空间，因此，在空间占用方面，数组优于链表。

3）数据的存取操作：访问链表中的结点必须从表头开始，是顺序的存取方式，而数组元素的访问是通过数组下标来实现的，是随机存取方式，因此，在数据存取方面，数组优于链表。

数据的合并与分离：链表优于数组，因为只需要改变指针的指向

223. 将表达式((a+b)-c*(d+e)-f)*(g+h)改写成后缀表达式。

答：后缀表达式为：ab+cde+*-f-gh+*

224.写出中缀表达式A-(B+C/D)*E的后缀形式。

答：中缀表达式A-(B+C/D)*E的后缀形式是：ABCD/+E*-。

225． 为什么用二叉树表示一般树？

答：树的最直观表示是为树中结点设置指向子结点的指针域，对k叉树而言，每个结点除data域外，还有k个链接域。这样，对一个有n个结点的k叉树来说，共有n*k个指针域，其中n-1个不空，另外n(k-1)+1个指针域为空，因此，空链接域的比例约为（k-1）/k ，于是导致大量的空间浪费。然而，如果采用二叉树表示一棵n个结点的树，则树中共有2n个链接域，其中未用到的有n+1个，占所有指针域的比例约为1/2，空间浪费少很多。

另外，因为任何树型结构都可以转换成二叉树，因此，通常用二叉树表示树型结构。

226．已知数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出冒泡排序每趟的结果。

答： 初始键值序列12  5   9   20  6   31  24

第一趟排序 [5   9  12   6  20  24]  31  

    第二趟排序 [5   9   6   12  20]  24  31

第三趟排序 [5   9   6   12] 20   24  31

第四趟排序  5   6   9   12  20   24  31

227．试找出前序序列和中序序列相同的所有二叉树。

解答：空树或缺左子树的单支树。

228．完全二叉树用什么数据结构实现最合适，为什么？

答：完全二叉树用一维数组实现最合适。因为完全二叉树保存在一维数组中时，数组内没有空洞，不存在空间浪费问题；另外，顺序存储方式下，父子结点之间的关系可用公式描述，即已知父（或子）结点寻找子（或父）结点只需计算一个公式，访问结点方便。但采用链表存储时就存在空间浪费问题，因为每个结点要另外保存两个链接域，并且寻找结点也不容易。

229．我们已经知道，树的先根序列与其对应的二叉树的先根序列相同，树的后根序列与其对应的二叉树的中根序列相同。那么利用树的先根遍历次序与后根遍历次序，能否唯一确定一棵树？请说明理由。

答：能。因为树的先根序列与其对应的二叉树的先根序列相同，树的后根序列与其对应的二叉树的中根序列相同，而二叉树的先根序列与二叉树的中根序列能唯一确定一棵二叉树，所以利用树的先根遍历次序与后根遍历次序，能唯一确定一棵树。

230．已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。

中序序列：c，b，d，e，a，g，i，h，j，f

前序序列：a，b，c，d，e，f，g，h，i，j

答：该二叉树的后序序列为：c,e,d,b,i,j,h,g,f,a

231． 对半查找是否适合于以链接结构组织的表？

答：对半查找不适合于以链接结构组织的表。。

232. 请指出中序遍历二叉查找树的结点可以得到什么样的结点序列。

答：中序遍历二叉查找树的结点就可以得到从小到大排序的结点序列。

233．已知数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出归并排序每趟的结果。

解答：

 初始键值序列12  5   9   20  6   31  24

第一趟排序 [5   12]  [9   20]  [6  31]  [24]

 第二趟排序 [5   9   12    20]  [6   24   31]

第三趟排序  5   6    9    12   20   24   31（）

234.一组记录的关键字为(52, 56, 26, 12, 69, 85, 33, 48, 70)，给出快速排序的过程。

解答：解：52, 56, 26, 12, 69, 85, 33, 48, 70

第一趟排序    33, 48, 26, 12, 52, 85, 69, 56, 70             

第二趟排序    26, 12, 33, 48, 52, 69, 56, 70, 85             

第三趟排序    12, 26, 33, 48, 52, 56, 70, 69, 85             

第四趟排序    12, 26, 33, 48, 52, 56, 70, 69, 85             

第五趟排序    12, 26, 33, 48, 52, 56, 70, 69, 85             

235．下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问，哪些排序方法是稳定的？

起泡排序, 直接插入排序，归并排序是稳定的。

236．已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。

前序序列：A, B, C, D, E, F, G, H, I, J

中序序列：C, B, A, F, E, D, I, H, J, G

答：后序序列为：C, B, F, E, I, J, H, G, D, A

237. 设记录的关键字集合key={51,28,38,86,70,90,7,30,40,25}，试写出对key进行渐减增量排序（增量d = 5，3，1）时，各趟排序结束后的结果。

解答：各趟排序结束后的结果。

初始状态：51  28  38  86  70  90   7  30  40  25

第一趟排序(d=5):  51  7   30  40  25  90  28  38  86  70

第二趟排序(d=3):  28  7   30  40  25  86  51  38  90  70

第三趟排序(d=1):  7   25  28  30  38  40  51  70  86  90）

238.写出计算单链表head（head为单链表的表头）中数据域data值为m的结点个数的算法。

int count (Node *head)

//计算单链表head中数据域data值为m的结点个数

{ Node *p=head->next;

int n=0;

while (p!=NULL)

{if (p->data==m)

n++；

   p=p->next; }

return  n;

}// count

239.已知非空单链表head，试设计一个算法，交换p所指结点与其后继结点在链表中的位置。

   解答：

int revers(listnode *head, listnode *p)

/*交换p所指结点与其后继结点在链表中的位置*/

{ if (p->next==NULL) return 0 ;

listnode *q=head;

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

{r=p->next；q->next=r;

 p->next =r ->next ; r->next=p;

return 1;}// revers

240.线性表用带头结点的单向链表示，试写出删除表中所有data域为零的元素的算法。

解答：

解：  int DeleteItem(Node * head)

 

   { Node  *p=head;

           //声明指针p，并令其指向链表头结点 

     while (p->nextNode()!=NULL)

      { 

         if (p->nextNode()->data==0)

              p->next=p->nextNode()->next.

          else p=p->nextNode(); //指针下移}}

241．试设计一算法，计算带头结点的单链表head(head指向表头)的结点个数。

解答：

  int Length( )

   //计算带表头结点的单链表head的长度

   { Node *p=head->next;

     int count=1;

 while (p->next!=NULL)

      {p=p->next; count ++;}

     return count;}

242．判断单链表head(head指向表头)是否是递增的。

解答：

int  order(Node *head)

{ Node *p=head;

while(p->next!=NULL)

if(p->data<p->next->data)

p=p->next;

else

break;

if(p->next==NULL)

return 1;

else

return 0; }

243. 设计一个算法，在一个单链表head中找出值最小的元素。

解答：int Min(Node * head )

 //在单链表head中找出值最小的元素

  {Node *p=head;

int min=p->data;                                   

     while (p->next!=NULL)

阿     { if(p->next->data<min)  min=p->next->data;

      p=p->next;}

return min;  }

244.设有两个单链表L和L1,其结点结构为                 ,试   编写算法判断链表L1中的各元素是否都是单链表L中的元素。

解答：

int  SubLnk(Node *L, Node *L1){

Node *p1=L1;

while(p1!=NULL)

{Node *p=L;

while((p!=NULL)&&(p1->data!=p->data))

{p=p->next;

if (p==NULL) return 0;

else p1=p1->next; }

return 1; }}

245.设一棵二叉树以二叉链表为存储结构，设计一个算法交换二叉树中每个结点的左子女和右子女。

解答：

void exchange(BinTreeNode * t)

   {if (t!=NULL)  

     BinTreeNode * temp;

   if((t->lchild!=NULL)||(t->rchild!=NULL))

          {temp= t->lchild;

           t->lchild= t->rchild;

      t->rchild= temp;

 exchange(t->lchild);

exchange(t->rchild); }}

246.设有一个正整数序列组成带头结点的单链表head，试编写算法确定在序列中比正整数x 大的数有几个。（8分）

解答：

int  count（Node * head，int x）

∥在带头结点的单链表head中，确定序列中比正整数x大的数有几个

{Node *p=head->next;   

     int count=0;

     while (p!=NULL)

      { if (p->data>x) count ++; 

p=p->next; }

    return count;  }∥算法count结束

247.设一棵二叉树以二叉链表为存储结构，试设计一个算法计算二叉树中叶子结点的个数。

解答：void countleaf(BinTreeNode * t,int &count)

   { if(t!=NULL)

        {if((t->lchild= =NULL)&&(t->rchild= =NULL))

       count++;

     countleaf(t->lchild,count);

     countleaf(t->rchild ,count); }}

248. 设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上度为2的结点个数。

解答：

void  count2(bitreptr t，int count)

{if (t!=NULL)

{if ((t-> lchild != NULL) && (t-> rchild != NULL))

  count++;

count2 (t->lchild,count)；

count2 (t->rchild,count)； }}// count2

249.设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树中最大值（元）。

解答：

void  maxnode(bitreptr t，int max)

{if (t!=NULL)

{if (t-> data>max) max=t->data;

  max= maxnode (t->lchild,max)；

max= maxnode (t->rchild,max)；

}return max; }// maxnode

 

 

 

 

上一条：算法设计与分析01375
下一条：计算机专业英语07757