数据结构复习提纲

《数据结构复习提纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、1．数据元素是数据的基本单位。2．在一个单链表中，若删除p所指结点的后继结点，则执行p->next=p->next->next;3．在循环双链表的p所指结点之后插入s所指结点的操作是s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;4．若希望从链表中快速确定一个结点的前驱，则链表最好采用双向链表方式。5．设有50行的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为43

2、76。6．广义表(a,b,(c,(d)))的表尾是(b,(c,(d)))。7．队列的特点是先进先出。8．设计一个判别表达式中左、右括号是否配对出现的算法,采用栈数据结构最佳.9．判定一个循环队列QU(maxsize=m0)为满队列的条件是QU->front==(QU->rear+1)%m0。10．树最适合用来表示元素之间具有分支层次关系的数据。11．在二叉树的第i层上至多有2i-1个结点(i≥1)。12．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为h

3、或h+1。13．如图所示二叉树的中序遍历序列是dfebagc。14．已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的先序遍历序列是cedba。15．在线索二叉树中，一个结点是叶子结点的充要条件为它的左、右线索标志均为1。16．若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是5。17．由权值分别为3、8、6、2、5的叶子结点生成一棵哈夫曼树，它的带权路径长度为55。18．无向图的邻接矩阵是一个对称矩阵。19具有n个顶点的无向图最多有n(n-1

4、)/2条边。20．具有5个顶点的无向图至少应有4条边才能确保是一个连通图。21．下列命题正确的是一个图的邻接矩阵表示是唯一的，邻接表表示不唯一。22．已知一有向图的邻接表存储结构如下：从顶点V1出发，进行深度优先遍历，所得的顶点序列是V1V3V4V5V2。23．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是选择排序。24．快速排序方法在要排序的数据已基本有序情况下蜕化为起泡排序。25．内部排序的方法有许多种，选择排序方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最

5、终位置上。26．一组记录的关键字为{46，79，56，38，40，84}，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为40，38，46，56，79，84。27．递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是堆栈。28．对线性表进行二分查找时,线性表必须顺序存储并有序。29．按中序遍历二叉排序树得到的序列是一个有序序列。30．在图G中求两个结点之间的最短路径可以采用的算法是迪杰斯特拉（Dijkstra）算法。31．线性表是具有n个数据元素的有限序列。32．。在一个长度为

6、n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时需向后移动n-i+1个元素。33．若进栈序列为1、2、3、4，进栈过程中可以出栈，则1423不可能是一个出栈序列。34．由三个结点构成的二叉树，共有5种不同的结构。35．先序遍历和中序遍历结果相同的二叉树是所有结点只有右子树的二叉树。36．在一棵具有五层的满二叉树中，结点总数为31。37．由分别带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为44。38．在一个无向图中，所有顶点的度数之和等于

7、所有边数的2倍。39．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点的所有入边邻接点。40．对线性表进行折半查找时，要求线性表必须以顺序方式存储，且数据元素有序。41．一组记录的关键字为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为(40,38,46,56,79,84)。42．从长度为n的采用顺序存储结构的线性表中删除第i个元素（1≤i≤n）,需向前移动n-i个元素。43．从邻接矩阵A=可以看出，该图共有3个顶点。44．排序趟数与序列的原始状

8、态有关的排序方法是冒泡排序。45．在一个具有n个单元的采用顺序存储结构的栈中，假定以地址低端（即下标为1的单元）作为栈底，以top作为栈顶指针，则当作出栈处理时，top变化为top=top-1;。46．在具有N个结点有序单链表中插入一个新结点并仍然有序的时间复杂度为O(N)。47．在一棵二叉树中，第五层上的结点数最多为16个。48．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为6个。49．已知8个数据元素为（34，76，4