一、全面复习所要求的课程内容和所做过的作业题

（以下是题型示例。要掌握各种结构的基本概念和基本原理，学会各种结构的灵活应用）

二、填空

1、连通图是指 任意两个结点之间都有路径的图       。    

2、对于栈只能在  栈顶   插入和删除元素；对于队列只能在  队尾   插入元素，在  队头       删除元素。

3、线性表中数据元素的个数称为线性表的      长度       。

4、删除带头结点的单链表L中的第一个元素结点的语句是 head->next=head->next->next; 。

5、有向图G用邻接矩阵A[ n ][ n ]存储，结点i的入度是  矩阵A[][]中第i列权值在0~MaxWeight之间的元素个数的和              。

6、所有结点的前驱和后继的个数都没有的数据结构是   图       结构。

7、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是___0~n(n-1)/2_______条。

8、具有10个结点的无向图边的总数最多为    45    。

9、在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head = = p->next->next                           。

10、栈顶的位置是随着   出栈               操作而变化的。

11、从任何一个结点开始都能成功查找其他结点的单链表是   循环单链     表。

12、满二叉树里，分支结点（非树叶结点）个数等于树叶的个数    减1    。

13、任何包括n个结点的二叉树的二叉链存储表示中，    2n    个指针中只有   n-1     个用来指示结点的左右孩子，而另外    n+1    个为空指针。

14、一个不带权的无向图采用邻接矩阵存储方法，其邻接矩阵是一个____对称______矩阵。

15、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着

     一对一     、    一对多     和  多对多         的关系。

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

17、一棵哈夫曼树有19个结点，则其叶子结点的个数是_____10_______。

18、设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳___4__个元素。

19、假设以S和X分别表示进、出栈操作，则对输入序列a、b、c、d、e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为    bceda                 。

20、无向图中的极大连通子图称为该无向图的   连通分量   。

三、选择

1、判定一个循环队列QU（最多元素为m）为满队列的条件是  B  。

A、QU.front = = QU.rear            B、QU.front = = (QU.rear + 1) % m

C、QU.front != QU.rear             D、QU.front != (QU.rear + 1) % m

2、在数据结构中，从逻辑上可以把数据结构分成 C   。

        A、动态结构和静态结构           B、紧凑结构和非紧凑结构

C、线性结构和非线性结构         D、内部结构和外部结构

3、带头结点的单链表head为空的判定条件是   B   。

A、head = = NULL                B、head -> next = = NULL

C、head != NULL                 D、head -> next != NULL

4、有n个结点的二叉树采用二叉链表存储结构，该链表有  D  个指针域用于链接孩子结点。

A、n             B、2n            C、n+1            D、n-1

5、一个有n个结点的无向图最多有   A    条边。

A、n(n-1)/2       B、n(n-1)         C、2n              D、n

6、在一非空二叉树的中序遍历序列中，根结点的左边  D    。

A、只有右子树上的部分结点           B、只有左子树上的部分结点

C、只有右子树上的所有结点           D、只有左子树上的所有结点

7、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front的值为   D   。

A、front = front + 1                   B、front = ( fron + 1 ) % ( m – 1 )    

C、front = (front - 1 ) % m             D、front = ( front + 1 ) % m

8、在含n个结点和e条边的无向图邻接矩阵中，零元素的个数为  D    。

A、e           B、2e              C、n2 - e            D、n2 - 2e

9、若入栈序列的元素顺序为A、B、C、D、E，判断下列哪一个出栈序列是不可能的(3)

①A、B、C、D、E         ②B、C、D、E、A      

③E、A、B、C、D         ④D、C、B、A、E

10、与链表不相适宜的叙述是    D    。

       A、动态存储分配              B、可表示任何类型的数据结构

       C、插入和删除操作灵活        D、查找速度快

11、若长度为n的线性表采用顺序存储结构，删除它的第i个数据元素需要依次向前移动__A____个数据元素。

       A、n - i          B、n + i          C、n - i - 1          D、n - i + 1

12、在一个单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行  D   。

        A、q -> next = p-> next ; p -> next = q ;      B、p -> next = q -> next ; q = p ;

C、q -> next = p -> next ; p -> next = q ;      D、p -> next = q -> next ; q -> next = p ;

13、链式栈与顺序栈相比，一个比较明显的优点是   B   。

        A、插入操作更加方便                B、通常不会出现栈满的情况

        C、不会出现栈空的情况              D、删除操作更加方便

14、下列有关线性表的叙述中，正确的是   A   。

A、线性表中的元素之间是线性关系   B、线性表中任何一个元素有且仅有一个直接前趋

C、线性表中至少有一个元素         D、线性表中任何一个元素有且仅有一个直接后继

15、以数组Q[m]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是  D    。

A、( rear – qulen ) % m        B、( rear - qulen + m ) % m    

C、( m – qulen ) % m          D、1 + ( rear + m – qulen ) % m

16、设结点x和结点y是二叉树T中的任意两个结点，若在前序遍历序列中x在y之前，而在后序遍历序列中x在y之后，则x和y的关系是  C    。

A、x是y的左兄弟    B、x是y的右兄弟    C、x是y的祖先    D、x是y的后代

17、已知某二叉树的前序遍历序列是ABDC，中序遍历序列是DBAC，它的后序遍历序列是  (2)    。

        ① ABCD        ②DBCA        ③BCAD        ④CABD

18、对线性表L适合于使用链式存储结构的是  B    。

        A、L中含有大量结点          B、需不断对L进行插入删除    

C、需经常修改L中结点值      D、需经常访问L中数据元素

19、一棵满二叉树同时又是一棵   C   。

        A、无序树      B、哈夫曼树      C、完全二叉树      D、度为2的树

20、按照二叉树的定义，具有3个结点的二叉树有  B    种不同形状。

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

四、简要回答下列问题

1、在顺序表上如何进行插入、删除操作？在单链表上又如何进行？

2、循环单链表有何特点？

3、线性表的两种存储结构——顺序结构和链式结构各有哪些优缺点？

4、为什么队列又称为先进先出表？堆栈？

5、为什么在顺序队列中可能会出现假溢出现象？

6、分别简述顺序堆栈和链式堆栈元素进栈、出栈的基本步骤。

7、分别简述顺序队列和链式队列元素进队、出队的基本步骤。

8、为了区分顺序循环队列的队空和队满情况，通常可以采用哪些方法？怎样区分？

9、什么是树中结点的度、树的度？

10、如果用双亲表示法存储一棵树，如何找到编号为i的结点的双亲和孩子结点？孩子表示法？

11、什么叫满二叉树？什么叫完全二叉树？

12、将一棵有n个结点的完全二叉树按层次顺序对所有结点从0开始编号，如何求编号为i的结点的双亲、左右孩子？若是一棵一般二叉树情况又怎样？

13、简述层序遍历二叉树的算法基本步骤。

14、简述非递归的二叉树前序遍历算法的基本步骤。

15、如何构造哈夫曼树？

16、如果图用邻接矩阵存储怎样判断两点是否为邻接点？用邻接矩阵存储又怎样？

17、如果有向图G用邻接矩阵、邻接表存储，分别如何求得结点i的出度和入度？无向图？

18、为什么说图的遍历比树的遍历复杂？

19、分别简述图的深度和广度优先遍历算法的基本思想。

20、从初始结点出发一定能遍历全图吗？为什么？

五、应用题

1、根据问题写相关的几个语句（如：在一个链式队列中，队首和队尾指针分别为front和rear，现要插入由s所指向的结点，给出应该执行的几步操作。分别对无头结点和有头结点的情况解答。）

2、画结构图（如某树的双亲表示法、孩子表示法等对应的结构图。）

3、完成相应的操作

（如：（1）某二叉树的结点数据采用顺序存储表示如下：

画出该二叉树的图形表示；写出该二叉树的前序、中序和后序遍历结点序列；将此二叉树看作森林的二叉树表示，试将它还原为森林。

（2）若对某二叉树前序遍历结点序列为ABDGCEFH，中序遍历的结点访问顺序是DGBAECHF，画出该二叉树的图形表示，画出它的顺序存储结构图、二叉链存储结构图、仿真二叉链存储结构图。

（3）根据给定的权集合设计哈夫曼树和哈夫曼编码。

（4）对应某图（有向、无向）写出它的邻接链表（邻接矩阵），据此给出由某点起始的深度优先遍历序列和广度优先遍历序列。对应某无向连通网写出它的邻接矩阵（邻接表），给出利用Kruskal算法、Prim算法生成最小生成树的过程。）

    4、作业中的题型

六、算法设计题

1、关于单链表的基本操作（如：已知一带头结点的单链表头指针为head，设计一算法求出该单链表中结点的个数）。

2、关于链式堆栈的基本操作

3、关于链式队列的基本操作

4、关于二叉树的遍历操作

（假设结点结构都为              ，其data域为整型，要求:定义所用结构、用程序设计语言描述算法。）

上述各问题要分清带头结点和不带头结点的结构在设计算法时的不同。下载本文