修改后的习题

本文格式为Word版，下载可任意编辑——修改后的习题

数据结构习题

习题一

一、选择题

1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。

A．结构B．关系C．运算D．算法2、在数据结构中，从规律上可以把数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．规律结构和存储结构

3、线性表的规律顺序和存储顺序总是一致的，这种说法（）。

A．正确B．不正确C．无法确定D．以上答案都不对

4、算法分析的目的是（）。

A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题

1、_______是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。

2、数据元素是数据的______，有些状况下也称为元素、结点、顶点、记录等。

3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。

4、简而言之，数据结构是数据之间的________，即数据的________。

5、数据的规律结构是指数据之间的________。规律结构是从________上描述数据，它与具体存储无关，是独立于计算机的。因此规律结构可以看作是从具体问题抽象出来的______________。6、数据的________指数据元素及其关系在计算机存储器内的表示。_________是规律结构在计算机里的实现，也称之为映像。

7、__________是指对数据施加的操作。它定义在数据的规律结构之上，每种规律结构都有一个____________。常用的有：查找、排序、插人、删除、更新等操作。8、数据规律结构可以分为四种基本的类型，_______结构中的元素除了仅仅只是同属于一个_________________，不存在什么关系。

9、数据规律结构的四种基本类型中，________中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。

10、数据规律结构的四种基本类型中，____________中的元素是一种一对多的关系。11、图型结构或图状结构是一种________的关系。在这种规律结构中，所有结点均可以有多个前驱和多个后继。

12、有时也可将树型结构、集合和图型结构称为__________，这样数据的规律结构就可以分为__________和________两大类。13、____________方式是指规律上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。

14、_______方式是种存储方法，不要求规律上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。

1

15、索引存储方式又可以分为______和________。若每个结点在索引表中都有一个索引项，则该种索引存储方式称为__________；若一组结点在索引表中只对应一个索引项，则索引存储方式称为________。在一中，索引项的地址指示结点所在的位置，而一中，索引项的地址指示一组结点的起始位置。

16、_________方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。

17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。

18、算法的_______性是指算法必需能够在执行有限个步骤之后终止，并且每个步骤都必需在有穷的时间内完成。

19、算法的________性是指算法中的每一个步骤必需是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是一致的就只能得到____________的输出结果。20、算法的____________性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行_________次来实现，即算法的__________应当能够被计算机执行。21、判断一个算法的好坏主要以下几个标准：________、________、________、_________。22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机_________的长短和___________________的大小。

23、空间繁杂度（SPaceComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_____________的大小。三、判断题

1、顺序存储方式只能用于存储线性结构。（）2、数据元素是数据的最小单位。（）

3、算法可以用不同的语言描述，假使用C语言或PASCAL语言等高级语言描述，则算法实际上就是程序了。（）

4、数据结构是带有结构的数据元素的集合。（）

5、数据的规律结构是指各元素之间的规律关系，是用户根据需要而建立的。（）6、数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（）

7、数据的物理结构是指数据在计算机中实际的存储形式。（）

8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（）四、综合题

1、用大O形式表示下面算法的时间繁杂度：for（i=0；i＜m；i十十）for（j=0；j＜n；j＋＋）A[i][j]=i*j；

2、写出下面算法的时间繁杂度：i＝0；s=0；

while(s＜n）｛i++;s+=i;｝

2

3、写出以下算法的时间繁杂度：for（i＝0;i＜m;i＋＋）

for（j＝0;j＜t;j＋＋）c[i][j]=0；

for（i=0；i＜m；i＋＋）

for（j=o;j=0）个数据元素的________。其中n为数据元素的个数，定义为线性表的__________。当n为零时的表称为_________。

4．所谓顺序表（SequentialLISt）是线性表的__________，它是将线性表中的结点按其____________依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在____________的存储单元中。

5．单链表不要求规律上相邻的存储单元在物理上也一定要相邻。它是分派一些_______的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的_________的位置上，它们在物理上可以是一片连续的存储单元，也可以是__________的。因此在表示线性表这种数据结构时，必需在存储线性表元素的同时，也存储线性表的。

6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_________；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为________或____________。

7．线性链表的规律关系是通过每个结点指针域中的指针来表示的。其规律顺序和物理存储顺序不再一致，而是一种_________存储结构，又称为__________。

8．假使将单链表最终一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了______________。

9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了___________。

10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p_______。11．在单链表中，删除指针P所指结点的后继结点的语句是____________。

12．在双循环链表中，删除指针P所指结点的语句序列是P->prior->next＝p->next及__________。

13．单链表是___________的链接存储表示。14．可以使用___________表示树形结构。

15．向一个长度为n的向量的第i个元素(l≤i≤n+1）之前插人一个元素时，需向后移动__________个元素。

16．删除一个长度为n的向量的第i个元素（l≤i≤n）时，需向前移动_______个元素。17．在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是__________。18．在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句_______。19．取出广义表A＝（（x，（a，b，c，d））中原子c的函数是_________。

20．在一个具有n个结点的有序单链表中插人一个新结点并使之依旧有序的时间繁杂度为_______________。

21．写出带头结点的双向循环链表L为空表的条件________________。22．线性表、栈和队列都是_________________结构。

23．向栈中插人元素的操作是先移动栈_____________针，再存人元素。三、判断题

1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。()3．顺序存储的线性表不可以随机存取。（）4．单链表不是一种随机存储结构。（）

5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。()

5

top！＝0B．S->top==0C．S->top!=nD．S->top==n4．判定一个栈S（最多有n个元素）为满的条件是（）。

A．S->top!=0B．S->top==0C．S->top!=nD．S->top==n

5．向一个栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（）。A．top->next=S；B．S->next=top；top=S；

C．S->next＝top->next；top->next＝S；D．S->next＝top；top＝S->next；

6．向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（）。

A．top->next=S；B．S->next=top；top=S；

C．S->next=top->next；top->next=S；D．S->next=top；top=S->next；7．判定一个队列Q（最多有n个元素）为空的条件是（）。A．Q->rear-Q->front==nB．Q->rear-Q->front+1==nC．Q->rear==Q->frontD．Q->rear+1==Q->front8．判定一个队列Q（最多有n个元素）为满的条件是（）。

A．Q->rear-Q->front==nB．Q->rear-Q->front+1==nC．Q->rear==Q->frontD．Q->rear+1==Q->front9．判定一个循环队列Q（最多有n个元素）为空的条件是（）。A．Q->rear==Q->frontB．Q->rear==Q->front＋lC．Q->front==(Q->rear+1)％nD．Q->front==(Q->rear-1)％n10．判定一个循环队列Q（最多有n个元素）为满的条件是（）。A．Q->rear==Q->frontB．Q->rear==Q->front＋lC．Q->front==(Q->rear+1)％nD．Q->front==(Q->rear-1)％n

11．在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（）。

A．front＝front->nextB．S->next=rear；rear=SC．rear->next=S；rear=SD．S->next=front；front＝S

12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（）。

A．front=front->nextB．rear=rear->nextC．rear->next=frontD．front->next＝rear13．栈与队列都是（）。

A．链式存储的线性结构B．链式存储的非线性结构C．限制存取点的线性结构D．限制存取点的非线性结构14．若进栈序列为l，2，3，4，则（）不可能是一个出栈序列。

A．3，2，4，1B．l，2，3，4C．4，2，3，1D．4，3，2，l15．在解决计算机主机与打印机之间速度不匹配问题时寻常设置一个打印数据缓冲

7

区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应当是一个（）结构。

A．堆栈B．队列C．数组D．线性表二、填空回

1．栈（stack）是限定在________一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__________，而另一端称为_________。不含元素的栈称为_______。

2．在栈的运算中，栈的插人操作称为________或________，栈的删除操作称为_________或__________。

3．根据栈的定义，每一次进栈的元素都在原___________之上，并成为新的__________；每一次出栈的元素总是当前的_____________，因此最终进栈的元素总是__________，所以栈也称为___________线性表，简称为____________表。

4．栈是一种操作受到限制的线性表，是一种特别的线性表，因此栈也有__________和_________________两种存储结构，分别称为______________和____________。

5．当栈满的时候，再进行人栈操作就会产生____________，这种状况的溢出称为___________；当栈空的时候，假使再进行出栈操作，也会_____________，这种状况下的溢出称为__________________。

6．栈的链式存储结构简称为____________，是一种__________________。

7．人们日常计算用到的表达式都被称为____________，这是由于这种算术表达式的运算符被置于两个操作数中间。

8．计算机中寻常使用___________，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为__________________。

9．队列（Queue）也是一种___________，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_________，允许删除的一端称为_______________。

10．队列的特点是_________，因此队列又被称为_______________．的线性表，或称为_________________表。

11．队列的_________又称为__________，是用一组地址连续的存储单元依次存放队列中的元素。

12．由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向__________和__________，这两个指针又称为__________和_____________。

13．循环顺序队列（CircularSequenceQueue）经常简称为___________，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的_________________来实现的。

14．在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为，也称为____________。函数直接调用自己，则称为__________；当一个函数通过另一个函数来调用自己则称为_________________。

15．在循环队列中规定：当Q->rear==Q->front的时候循环队列为___________，当（Q->rear+1）％MAXSIZE＝front的时候循环队列为____________________。

16．用链表方式表示的队列称为____________________。

17．已知栈的输人序列为1，2，3，?，n，输出序列为a1，a2，?，an，符合a2==n的输出序列共有__________________。

18．一个栈的输人序列是12345，则栈的输出序列为43512是________（填是否可能）。19．一个栈的输人序列是12345，则栈的输出序列为12345是_________（填是否可能）。

8

20．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是______________。

21．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，假使把栈顶元素弹出并送到X中，则需执行语句______________。

22．栈的特性是__________________。

23．对栈进行退栈时的操作是先取出元素，后移动_________。24．设s[1．．max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是____。25．设链栈的栈顶指针为top，则栈非空的条件是___________。

26．已知循环队列用数组data[1...n]存储元素值，用f，r分别作为头尾指针，则当前元素个数为____________。

27．在一个循环队列中，队首指针指向队首元素的________位置。（前一个或后一个）28．队列中允许进行删除的一端称为_______________。

29．链队列实际上是一个同时带有头指针和尾指针的单链表（1．．n），尾指针指向该单链表的第___________个元素。

30．设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是____________。

31．从循环队列中删除一个元素，其操作是先取出一个元素，后移动______________。32．队列中允许进行插入的一端称为_________。三、判断题

1．栈和队列都是限制存取点的线性结构。（）2．不同的人栈和出栈组合可能得到一致输出序列。（）3．消除递归一定要用栈。（）4．循环队列是顺序存储结构。（）5．循环队列不会产生溢出。（）6．循环队列满的时候rear==front。（）

7．在对链队列（带头结点）做出队操作时不会改变front指针的值。（）四、综合题

1．设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。2．输入n个10以内的数，每输入k（0＜=k＜=9），就把它插人到第k号队列中。最终把10个队列中的非空队列按队列序号以从小到大的顺序串接成一条链，并输出该链中的所有元素。

3．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本操作算法如下：

(l)初始化队列initqueue(Q)：建立一个新的空队列Q。(2)人队列enqueue(Q，x)：将元素x插人到队列Q中。(3)出队列delqueue(Q)：从队列Q中退出一个元素。(4)取队首元素gethead(Q)：返回当前队首元素。(5)判断队列是否为空：emptyqueue(Q)。(6)显示队列中元素：dispqueue(Q)。4．“回文〞是指一个字符串从头读到尾和从尾读到头都一样。假设字符串是从输人设备一次一个字节的读人，并且读到字符“＃〞的时候表示终止。请用栈和队列编写一个算法判断一个字符串是否回文。

5．假设表达式中有三种括号：圆括号“（）〞、方括号“[]〞和花括号“{}〞用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以〞#〞终止。

9

6．用C语言编写背包问题的算法。背包问题的描述是：假设有n件质量分别为w1，w2，?，wn的物品和一个最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装人背包，并且使被选物品的总质量恰好等于背包所能装载的最大质量，即Wxl＋Wx2＋?Wxk＝T。若能，则背包问题有解，否则背包问题无解。

7．划分子集问题的求解。划分子集问题的实际例子好多，如：某个运动会设立n个比赛项目，每个运动员可以参与一到三个项目，考虑到同一运动员参与的项目不能够在同一时间内进行，则如何安排比赛日程才能使总的日程最短。又如：学校开设m科课程，不同的同学可能选修多门不同的课程，在学期末要进行考试，则如何安排这m科课程的考试才能使考试时间最短而又不冲突。

8．写出汉诺塔问题的递归和非递归算法。

汉诺塔问题描述为：有X、Y和Z三个柱子，n个大小不等且都能套进柱子的圆盘（编号为l、2、?、n），这n个圆盘已经依照自上至下、由小到大的顺序在其中的一根柱子X上，要求将这些圆盘依照如下规则由X柱子移动到Z柱子：

(1)每次只能移动柱子最上面的一个圆盘。(2)任何圆盘都不能放在比它小的圆盘之上。(3)圆盘只能在X、Y和Z三根柱子之上放置。

10

习题四

一、选择项

l．空串与空格串（）。

A．一致B．不一致C．可能一致D．无法确定

2．设有两个申S1与S2，求串S2在S1中首次出现位置的运算称作（）。A．连接B．求子串C．模式匹配D．判子串

3．串与普通的线性表相比较，它的特别性表达在（）。A．顺序的存储结构B．链接的存储结构C．数据元素是一个字符D．数据元素可以任意4．设有串S=‘Computer’，则其子串的数目是（）。

A．36B．37C．8D．9二、境空题

1．串是由零个或多个字符组成的____________。寻常记作：s＝“c1，c2，?，cn〞(n=>0)，其中，S称为________；串中的Ci（1l，则其双亲Parent(i)的序号是结点_______________；假使2i≤n，则结点i的左孩子Lchild(BT,，i）是_________，否则结点i无左孩子(结点i必为叶子结点)；假使2i＋l≤n，则结点i的右孩子RChild（BT，i）的序号是____________；否则该结点无右孩子。27．二叉树的顺序存储结构是用_________________存储二叉树的数据元素。28．____________是指依照某条探寻路径访问树中的某个结点，使得树中每个结点均被访问一次，而且仅被访问一次。

29．先序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：访问二叉树____________；先序遍历二叉树____________；先序遍历二叉树_________。30．中序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：中序遍历二叉树__________；访问二又树__________；中序遍历二又树____________。31．后序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树___________；后序遍历二叉树_________；访问二叉树_____________。32．线索二叉树（ThreadedBinaryTree）是充分利用二义链表的n+1个空的指针域作为线索来标志每一个结点的________和__________信息。当某个结点有左孩子的时候，使其___________指向其左孩子，无左孩子的时候，使其左指针域指向该结点的___________；当某个结点有有孩子的时候，使其右指针域指向该结点的__________，无右孩子的时候，使其有指针域指向该结点的_____________。

33．线索二叉树的线索链表中，指向结点前驱和后继的指针称为___________；加上线索的二叉树称为_____________；对二叉树以某种次序进行遍历使其成为线索二叉树的过程称为_______________________。

34．树的存储结构常见的有____________、____________和________________。35．树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则：访问树的＿；依次先序遍历树的＿。

36．树的后序遍历过程为：若树为空，则进行空操作；若树非空，则：依次后序遍历__________；访问_________________。

15

37．森林的先序遍历过程为：若森林非空，则：（1）访问森林中第一棵树的___________。（2）先序遍历第一棵树中_____________。（3）先序遍历_______________________。

38．森林的后序遍历过程为：若森林非空，则：（l）后序遍历森林中第一棵树的_______________。（2）访问第一棵树的_________________________。（3）后序遍历_______________________________。

39．从树中一个结点到另一个结点之间的_________称为这两个结点的路径。40．路径上的分支数目称为______________。

41．树的路径长度是指从树根到每一结点的__________________。

42．将树中的结点赋上一个有着某种意义的实数，称此实数为该结点的____________。43．树的带权路径长度为树中所有叶子结点的____________。

44．哈夫曼树（HuffmanTree）又称___________。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL__________________。

45，所谓前缀编码是指在所有对字符的编码中，任何一个字符都不是____________。

46．已知完全二叉树的第八层有8个结点，则其叶子结点数是__________________。47．在有n个叶子结点的哈夫曼树中，总结点数是___________。

48．已知完全二又树的第7层有10个叶子结点，则整个二又树的结点数最多是___。49．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为___。50．一棵树T采用二叉链表BT存储，假使树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定满足___________________。

51．在二叉链表中，判断某指针P所指结点为叶子结点的条件是______________。52．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。

53．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______________。54．3个结点可构成___________________棵不同形态的树。

55．已知完全二叉树的第七层有8个结点，则其叶子结点数是______________.

56．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____________。

57．若要对某二叉排序树进行遍历，保证输出的所有结点序列按键值递增次序排列，应对该二叉树采用_______________遍历法。三、判断题

1．完全二叉树的某个结点若无左孩子，则它必然是叶结点。（）2．存在这样一种二叉树，对它采用任何次序的遍历结果一致。（）3．度为二的树称为二叉树。（）4．二叉树中不存在度大于2的结点。（）

5．当二叉树中某个结点只有一棵子树的时候，无左右子树之分。（）6．任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。（）7．哈夫曼编码是一种前缀编码，不允许出现两个字符编码一致的状况。（）8．完全二叉树某结点有右子树，则必然有左子树。（）9．前序遍历一棵二叉树的结点就可以得到排好序的结点序列。（）10．将一棵拥有子树的树转换为二叉树后，根结点可能没有左子树。（）11．根据二叉树的前序遍历和中序遍历可以得到二又树的后序遍历。（）

16

12．哈夫曼树是带权路径长度最短的树。（）13．哈夫曼树的路径上权值较大的结点离根较远。（）

14．后序遍历森林与后序遍历与森林相对应的二叉树结果一致。（）

15．在二叉树中，具有一个孩子的结点，在中序遍历序列中，没有后继子女结点。

（）

16．前序遍历与森林相对应的二叉树结果不同。（）

17．若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。（）18．二叉树只能采用二叉链表来存储。（）19．给定结点数的平衡二叉树的高度是惟一的。（）四、综合题

1．一棵树表达成如下形式：

D＝{A，B，C，D，E，F，G，H，I，J，K，L，M，N，O}

R=＜A，B＞，＜A，C＞，＜A，D＞，＜B，E＞，＜B，F＞，＜C，G＞，＜D，H＞，＜D，I＞，＜D，J＞，＜K，F＞，＜K，L＞，＜F，M＞，＜I，N＞，＜I，O＞｝

其中D为结点集合，R为边的集合。请根据以上内容回复以下问题：(1)画出这棵树。

(2)该树的根结点是哪一个？(3)哪些是叶子结点？(4)F结点的双亲是谁？(5)F结点的祖先是哪些？(6)F结点的孩子是哪些？(7)F结点的兄弟是哪些？(8)F结点的堂兄弟是哪些？(9)F结点的度是多少？(10)F结点的层次是多少？(11)D结点的子孙有哪些？

(12)以结点D为根的子树度是多少？(13)以结点D为根的子树层是多少？(14)该树的层是多少？(15)该树的度是多少？

2．画出图6-1中树的二叉树表示形式。

（a）（b）（c）图6-l

3．已知某二叉树的先序遍历的结果是：A，B，D，QC，E，H，L，I，K，M，F和J，它的中序遍历的结果是：QD，B，A，L，H，E，K，LM，C，F和J，请画出这棵二叉树，并且写出该二叉树后序通历的结果。

4．写一个将一棵二叉树复制给另一棵二又树的算法。

5．已知—个二叉树用二叉链表表示，其根指针为t，请写一个算法，从根结点开始按

17

层次通历该二叉树，同层的结点接从左到右的次序进行访问。

6．已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列和中序遍历序列构造一棵二叉树的算法。

7．假设一棵哈夫曼树共有n0个叶子结点，试证明树中共有2no-l个结点。

8．假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I构成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请用这9个字母出现得频率作为权值求：

（l）设计一棵哈夫曼树。

（2）计算其带权路径长度WPL值。（3）写出每个字符的哈夫曼编码。

18

习题七

一、选择题

1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的（）倍。A．l/2B．1C．2D．4

2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A．l/2B．1C．2D．43．一个具有n个顶点的无向图包含（）条边。

A．nB．n＋1C．n-1D．n/24．一个具有n个顶点的无向完全图包含（）条边。

A．n(n-l)B．n(n+l)C．n(n-l)/2D．n(n-l)/25一个具有n个顶点的有向完全图包含（）条边。

A．n(n-1)B．n(n+l)C．n(n-l)/2D．n(n+l)/2

6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）。A．nB．n2C．n-1D．(n-l)2

7．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（）。

A．nB．eC．2nD．2e

8．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。

A．nB．eC．2nD．2e

9．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。A．入边B．出边

C．入边和出边D．不是入边也不是出边

10．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。A．入边B．出边

C．入边和出边D．不是人边也不是出边11．以下说法中不正确的是（）。

A．无向图中的极大连通子图称为连通分量

B．连通图的广度优先探寻中一般要采用队列来暂存刚访问过的顶点C．图的深度优先探寻中一般要采用栈来暂存刚访问过的顶点D．有向图的遍历不可采用广度优先探寻方法

12．设无向图G=(V,E)和G’=(V’,E’)，假使G’为G的生成树，则以下说法中不正确的是（）。

A．G’为G的连通分量B．G’为G的无环子图

C．G’为G的子图D．G’为G的微小连通子图且V’＝V

13．假使无向图G必需进行二次广度优先探寻才能访问其所有顶点，则以下说法中不正确的是（）。

A．G确定不是完全图B．G一定不是连通图C．G中一定有回路D．G有二个连通分量14．邻接表是图的一种（）。

A．顺序存储结构B．链式存储结构C．索引存储结构D．散列存储结构15．假使从无向图的任一顶点出发进行一次深度优先探寻即可访问所有顶点，则该图一

19

定是（）。

A．完全图B．连通图C．有回路D．一棵树16．以下有关图遍历的说法不正确的是（）。A．连通图的深度优先探寻是一个递归过程

B．图的广度优先探寻中邻接点的寻觅具有“先进先出〞的特征C．非连通图不能用深度优先探寻法

D．图的遍历要求每一顶点仅被访问一次

17．一个无向连通图的生成树是含有该连通图的全部顶点的（）。A．微小连通子图B．微小子图C．极大连通子图D．极大子图18．无向图的邻接矩阵是一个（）。

A．对称矩阵B．零矩阵C．上三角矩阵D．对角矩阵二、填空题

1．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种________________的关系。

2．在图G中，假使代表边的顶点偶对是_____________，则称G为无向图。3．在图G中，假使代表边的顶点偶对是_____________，则称G为有向图。

4．在图G中，＜vi，vj＞表示从vi到vj的一条边，在有向图中又称为一条____，且称vi为______或_________，称vj为_________或__________。显然在有一向图中代表的是_______________。

5．具有n(n-1)/2条边的无向图称为__________，简称为_________，其中n表示无向图中顶点的个数，n(n-1)/2是具有n个顶点无向图所拥有边的___________。

6．具有n个定点的有向图，假使它同时具有n(n-1)条狐，则称该图为____________，其中n(n-1)是具有n个顶点有向图所拥有弧的___________________。

7．有很少条边或弧（如边数少于nlogn）的图称为________________。8．假使图中的边或弧带有权，则称这种图为_______________。

9．假使有两个网G=(V,E)，G’=(V’,E’)，若满足V(G’)V(G)，并且E(G’)E(G)，则称图G’为图G的__________。

10．在无向图中，若存在一条边(v,w)，则称v和w这两个端点互为___________，同时称边(v,w)__________顶点v和w，或者说边(v,w)和顶点v和w_______________。

11．在有向图中，若存在一条弧，则称顶点v_________顶点w，称弧和顶点v,w________________________。

12．顶点v的度定义为_________________的数目，记为D(v)。

13．在有向图中，顶点v的度又分为_____________和_________，__________是以顶点v为头的弧的数目，或者说是以该顶点为终点的边的数目，记为ID(v)；____________是以顶点v为尾的弧的数目，或者说是以顶点为起点的边的数目，记为OD(v)；顶点v的度是它的___________和__________之和，即D(v)=ID(v)＋OD(v)。14．____________是指一条路径上所经过的边或弧的数目。

15．若一条路径上除开始结点和终止结点外(开始结点和终止结点也可以为不同顶点），其余顶点均不一致，则称该路径为_____________。

16．若一条路径上的开始结点和终止结点为同一个顶点，则称该路径为________或_______。同时除了第一个顶点和最终一个顶点之外，其余顶点不重复出现的回路称_________或__________。

17．在无向图G中，假使从顶点v到顶点v’有路径，则称v和v’是______________的。

20

6．基数排序的设计思想是依照对单个关键字值的比较来实施的。（）

7．用希尔（Shell）排序方法进行排序的时候，关键字越是有序效率越高，关键字越是杂乱则排序效率越低。（）

8．减少初始归并数量，可以使外部排序的时间缩短。（）9．直接插入排序是一种稳定的排序算法。（）10．希尔排序是一种稳定的排序算法。（）11．冒泡排序是一种稳定的排序算法。（）12．冒泡排序算法的时间繁杂度最正确状况下为O(n2)。（）13．快速排序是一种稳定的排序算法。（）14．直接选择排序是一种稳定的排序算法。（）15．堆排序是一种稳定的排序算法。（）16．快速排序、堆排序和归并排序平均时间繁杂度为O(nlog2n)。（）17．归并排序是一种稳定的排序算法。（）18．基数排序是一种稳定的排序算法。（）19．目前归并排序在内部排序和外部排序中都广为使用。（）20．当排序的记录数量好多，可能出现正序或逆序状况的时候，可以选择堆排序，假使进一步要求排序方法稳定的时候，则要选择归并排序。（）

21．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）

22．二路归并排序的核心操作是将两个有序序列归并为一个有序序列。（）四、综合题

1．已知一组记录的关键字序列为{41，60，39，72，25，44，90，31}，请写出直接插入排序的每一趟过程。

2．已知一组记录的关键字序列为{36，55，31，28，79，66，12，07，89}，请写出进行冒泡排序的每一趟过程。

3．已知一组记录的关键字序列为{35，27，60，72，50，40，17，81，29，69，30}，请写出以第一个记录为基准记录，一趟快速排序时记录的移动状况。

4．已知一组记录的关键字序列为{76，98，23，65，40，39，52，65，87，11}，请写出直接选择排序的每一趟过程。

5．已知一组记录的关键字序列为{22，96，15，37，10，68，44，85，70，20，11}，请写出用归并排序进行排序的每一趟过程。

6．设计一个函数，实现冒泡排序的双向排序，即每一趟通过每两个相邻的关键字进行比较，产生最小和最大的关键字值的元素。

7．用递归的方法实现一趟归并排序，并写出完整的归并算法。

8．有一种算法称为奇偶转换排序，它的思路是：第一趟对所有的奇数i将a[i]和a[i+l]进行比较，其次趟对所有的偶数的i将a[i]和a[i+l]进行比较，每次比较时，若a[i]＞a［i＋l］，则将二者进行交换，直至所有记录关键字有序。试写出此算法。

31

假使对于图中任意两个顶点v和v’都是连通的，则称图G是________，否则称为__________。无向图中，极大的连通子图称为___________________。

18．在有向图中，若任意两个顶点vi，vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称该图是____________。有向图中的极大强连通子图称为有向同的___________。19．一个连通图的生成树是一个__________，它含有图中全部以点，但只有构成一棵树的__________条边。假使在一棵生成树添加一条边，必定构成一个___________，由于新添加的这条边使得依附在它两端的两个顶点有了____________。

20．假使有一个有向图恰有一个顶点的人度_______，其余以顶点的人度均________，则该有向图是一棵有向树。一个有向图的___________由若干棵有向树构成，含有图中全部顶点，但只有构成若干棵不相交的有向树的弧。

21．图的邻接矩阵（AdjacencyMatrix）表示法是用一个________来表示图中顶点之间的相邻关系。

22．邻接表(AdjacencyList)是图的一种_______存储结构。在邻接表中，对图中每个顶点建立一个_________，第i个单链表中的结点表示依附于顶点vi的边(对无向图)或弧（对有向图）。23．逆邻接表只有______图才具有。是为了便于确定有向图中顶点的_______而建立的。24．一个图的邻接矩阵的表示是_________，但是图的邻接表的表示并_____________。这是由于邻接表中各边结点的连接次序取决于建立邻接表时输入的次序，由于输入的时候是随机的，所以图的邻接表建立的结果也有可能____________。

25．从邻接表的定义可以看到，若无向图有n个结点和e条边，则它的邻接表需要________个头结点和______________个表结点。

26．图的遍历(TraversingGraph)是从图的某一顶点出发访问图中___________，并且使每一个顶点___________________的过程。

27．图的深度优先探寻的基本思想是：从中某个顶点v出发，首先访问_________，然后访问_________顶点w，接着访问一个_____________的顶点，依此类推，直到图中所有和v有路径相通的顶点都被访问到；若此时图中仍有顶点未被访问，则选择图中未被访问的顶点作为___________，重复上述过程，直到图中所有顶点_______________为止。28．图的深度优先探寻遍历类似于树的__________________遍历。

29．图的广度优先探寻的基本思想是：从某个顶点v出发，首先访问此顶点，然后按广度优先探寻依次访问所有v的__________，接着从这些___________出发依旧进行广度优先探寻依次访问其他结点，直至图中所有已被访问的顶点的_________全部被访问到。若此时图中仍旧有未被访问的顶点。则另选一个图中____________作为起始点，重复上述过程，直到图中所有顶点___________为止。

30．图的广度优先探寻类似于树的_______________遍历。

31．假使连通图是一个网络，生成树的_______称为这棵生成树的代价，则称该网络中所有生成树中权值最小的生成树为____________，简称为__________。

32．构造一棵最小生成树往往都要利用最小生成树的一种简称为MST的性质。常见的构造最小生成树的______________算法和___________算法都利用了MST性质。

33．路径上的第一个顶点称为____________，最终一个顶点称为____________。34．迪杰斯特拉算法是求____________的最短路径，弗洛伊德（Floyd）算法是求_________的最短路径。

35．一个____________称为有向无环图，简称为DAG图。

36．DAG图比有向树更一般，由于在有向树中不允许出现____________的结点，而在DAG图中则可以；另外DAG图不允许_____________，因此又是一种特别的图。

21

37．用顶点表示_________，用弧表示活动之间________的有向图，称为顶点表示活动的网（ActivityOnVertexNetwork），简称AOV网。

38．在AOV网中不可以出现有向环或回路，假使出现环或回路，这意味着某项活动是_________，这样的工程无法进行，对于计算机中的程序流程图来说就是_____________，也相当于操作系统中的______________。

39．检测AOV网是否有回路的方法是构造_________。从构造拓扑序列过程中可以发现是否有______________。

40．拓扑排序是对AOV网构造一个__________，使得所有结点的________在序列中得以表达，即在序列中某个结点的前驱必需在后继之前。拓扑排序的序列__________。41．假使用数学上的术语进行描述，拓扑排序是由某个集合上的一个__________关系得到该集合上的一个__________的操作。42．构造拓扑有序序列的过程可以发现有向图中________，同时构造拓扑有序序列的过程就是利用拓扑排序算法进行________________的过程。

43．拓扑排序的结果使得当前图中_________全部被输出，但依旧有结点未被输出，这说明有向图中存在_______________。

44．假使含n个顶点的图形成一个环，则它有___________棵生成树。45．有n个结点的无向图的边数最多为____________。

46．有n个顶点的强连通有向图G至少有___________条边。

47．用邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i的_________。48．设有向图G的邻接矩阵为A，图中i和j之间不存在弧，则A[i,j］的值为______。

49．有n个顶点的连通图的边数至少为____________。

50．在有n个顶点的有向图中，每个顶点的度最大可达___________。51．在无向图G的邻接矩阵A中，若(vi,vj)属于图G的边集，则对应元素A[i,j]为______，否则等于_____________（用逗号分开）。

52．已知一个有向图用邻接矩阵表示，计算第i个结点的人入度的方法是__________。53．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为________________，所有邻接表中的结点总数是________________。三、判断题

1．有n个结点的无向图中，若边数大于n-1，则该图是连通的。（）2．若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）3．AOV网拓扑排序的结果是惟一的。（）4．图的广度优先探寻序列是惟一的。（）5．具有n个顶点的无向图采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。（）6．若连通图上各边权值均不一致，则该图的最小生成树是惟一的。（）7．无向图的邻接矩阵一定是对称的。（）8．有向图的邻接矩阵一定是非对称的。（）

9．用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有关。（）

10．图的连通分量是无向图的微小连通子图。（）11．图的强连通分量是无向图的极大连通子图。（）12．对任意一个图从它的某个顶点出发进行一次深度优先或广度优先探寻遍历可访问到该图的每个顶点。（）

22

13．一个有向图的邻接表和逆邻接表中的节点个数一定相等。（）

14．有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非无穷的元素个数。（）

15．图G的某一最小生成树的代价一定小于其他生成树的代价。（）四、综合题

l．请写出如图7-1所示无向图的邻接矩阵和邻接表两种存储结构。

2．依据无向图7-1，请写出：

（1）从顶点1出发图的深度优先探寻序列。（2）从顶点回出发图广度优先探寻的序列。（3）写出图的深度优先探寻算法。（4）写出图的广度优先探寻算法。

3．使用Prim算法，依据无向图7-2做以下问题；

图7-2

（l）写出构造该图的最小生成树的过程。(2)写出相应的构造最小生成树算法。

4．使用Kruskal算法，依据无向图7-2做以下问题：（l）写出构造该图的最小生成树的过程。

(2)写出相应的构造最小生成树算法的形式描述。

5．假设图采用邻接表表示，写出一个从顶点v0对图按深度优先探寻遍历的非递归算法。

6．有一个无向图采用邻接表的存储结构，请编写算法，以遍历的形式输出从顶点v到顶点w的路径中长度为len的简单路径。

7．以邻接表作为存储结构，编写一个算法，利用深度优先探寻法，求出在无向图中通过给定点w的简单回路的算法。

23

习题八

一、选择题

1.顺序查找方法适合于存储结构为（）的线性表

A.散列存储B.索引存储C.散列存储或索引存储D.顺序存储或链接存储2.对线性表进行二分查找的时候，要求线性表必需（）。

A.以顺序存储方式B.以链接存储方式

C.以顺序存储方式，且数据元素有序D.以链接存储方式，且数据元素有序3.假使要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用（）查找方法。A.顺序B.分块C.折半D.散列

4.对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的规律关系，则应当()。

A.以顺序存储方式B.以链接存储方式C.以索引存储方式