《数据结构与算法》复习

数据结构是一门研究计算机的操作对象以及操作对象之间的关系和对操作对象实施的典型操作的学科第一局部概述研究数据结构从三个方面进行：〔1〕逻辑结构〔2〕存储结构〔3〕操作〔运算〕：对数据进行的处理，定义在数据的逻辑结构上具体实现于数据的存储结构描述数据逻辑结构描述数据物理结构ADT由三元组构成：〔D，S，P〕D数据对象S关系P操作集关系的表示方法顺序映象非顺序映象顺序存储结构链式存储结构四种根本的数据结构及其特点算法的特征及评价方法集合线性表树图数据元素数据项数据对象时间复杂度空间复杂度第二局部表、栈、队列线性表的逻辑结构线性表的物理结构顺序表单向链表循环链表双向链表静态链表有序性均匀性位序操作及算法的分析〔顺序表、单链表〕插入删除查找建表合并集合运算顺序表与线性链表的比照1.静态结构与动态结构(大小)2.数据关系的表示方法3.操作(插入/删除、查找)带头结点与不带头结点的比照1.空表与非空表一致性2.不同位置插入、删除操作的一致性栈和队列栈和队列的特点：操作受限制栈和队列的操作〔建立、入/出〕栈/队列的空、满条件顺序链栈和队列的物理结构栈和队列的应用特征串的判断进制转换括号匹配逆波兰表达式求值∥–––––线性表的动态分配顺序存储结构–––––#defineLIST_INIT_SIZE100∥线性表存储空间的初始分配#defineLISTINCREMENT10∥线性表存储空间的分配增量typedefstruct{ElemType*elem;∥存储空间基址

intlength;∥当前长度

intlistsize;∥当前分配的存储容量}SqList;∥–––––栈的顺序存储表示–––––#defineSTACK_INIT_SIZE100∥存储空间初始分配#defineSTACKINCREMENT10∥存储空间分配增量typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;∥–––––循环队列──队列的顺序存储结构–––––#defineMAXQSIZE100∥最大队列长度typedefstruct{QElemType*base;∥初始化的动态分配存储空间intfront;∥头指针,假设队列不空,指向队列头元素intrear;∥尾指针,假设队列不空,指向队列尾元素的下一个位置}SqQueue;//线性链表存储结构typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListL;∥–––––队列的链式存储结构–––––typedefstructQNode{QElemTypedata;StructQNode*next;}QNode,*QueuePtr;//链栈存储结构typedefstructSNode{SElemTypedata;structSNode*next;}SNode,*StackLink;StackLinkS;typedefstruct{QueuePtrfront;∥队头指针

QueuePtrrear;∥队尾指针}LinkQueue第三局部串、数组什么是串空串串长串的物理结构StrAssign(&T,chats)初始化一个串StrCopy(&T,S)串复制StrEmpty(S)判断串是否空串的根本操作StrLength(S)求串长StrCompare(S,T)串的比较Concat(&T,S1,S2)串联接Substring(&sub,S,pos,len)求子串StrInsert(&S,pos,T)插入子串StrDelete(&S,pos,len)删除子串Index(S,T,pos)求子串出现的位置Replace(&S,T,V)串替换数组的定义数组元素地址计算特殊矩阵的压缩存储稀疏矩阵的转置运算第四局部树、图树的定义度、叶子结点、终端结点、非终端结点、分支结点、内部结点孩子、祖先、双亲、子孙、兄弟、层次、高度〔深度〕满二叉树完全二叉树二叉树的定义、形态、性质证明:(1)设n1为T中度为1的结点数由于二叉树中所有结点的度均小于等于2那么结点总数为n=n0+n1+n2(2)设B为分支总数除根外，所有结点都有一个分支进入故：n=B+1(3)所有分支是由度为1或2的结点射出因此：B=n1+n2*2(4)n0+n1+n2=n1+n2*2+1n0=n2+1二叉树的存储结构二叉树的遍历及遍历的利用二叉树的建立线索二叉树typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;森林、树与二叉树的转换树和森林的遍历，与二叉树遍历的对应关系Huffman树的构造，WPL图的定义有向图和无向图完全图子图度路径简单路径简单回路连通图强连通图图的存储结构数组表示法邻接表连通分量生成树生成森林图的遍历深度优先搜索广度优先搜索最小生成树普里姆算法〔表〕克鲁斯卡尔算法拓扑排序(拓扑次序)关键路径〔表〕最短路径动态查找表第五局部查找、排序顺序查找算法平均比较长度ASL折半查找二叉排序树平衡二叉树B-树静态查找表哈希表除数留余法线性探测再散列二次探测再散列链地址法内部排序直接插入排序折半插入排序希尔排序起泡排序快速排序简单项选择择排序堆排序归并排序比较:稳定性各种情况下的时间复杂性辅助空间的多少关键字比较的次数与记录的初始排列次序每趟排序至少能将一个元素放到其最终位置上1.假设线性表最常用的操作是存取第i个元素及其前驱的值，那么采用

存储方式最节省运算时间。A.单链表

B.双链表

C.单循环链表

D.顺序表2.在有n个叶子结点的哈夫曼树中结点总数为

。A.不确定

B.2n-1

C.2n

D.2n+13.折半查找法要求查找表中各元素的关键字值必须是

。A.递增或递减

B.递增

C.递减

D.无序4.对于关键字值序列〔11，13，18，60，15，7，19，25，12，80〕，用筛选法建堆，必须从键值为

的结点开始。A.80

B.12

C.60

D.155.设图G用邻接表存储，那么求每个顶点入度的时间复杂度为

。A.O(n)

B.O(n+e)

C.

O(n*n)

D.O(n*e)6.链表不具有的特点是__________。A.不必事先估计存储空间

B.可随机访问任一元素C.插入删除不需要移动元素

D.所需空间与线性表长度成正比7.设输入序列为1、2、3、4，那么借助栈所得到的输出序列不可能是________。A.1、2、3、4

B.4、3、2、1C.1、3、4、2

D.4、1、2、38.在具有n个结点的二叉链表中，非空的链域个数为_____。A.n-1

B.2n-1

C.n+1

D.2n+19.在有n个结点的二叉排序树中查找一个键值，其最坏比较次数的数量级为___________。A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)10.以下序列中，____是执行第一趟快速排序后得到的序列A.[da,ax,eb,cd,bb]ff[ha,gc]

B.[cd,eb,ax,da]ff[ha,gc,bb]C.[gc,ax,eb,cd,bb]ff[da,ha]

D.[ax,bb,cd,da]ff[eb,gc,ha]11、

对具有n个元素的有序查找表采用折半查找算法查找一个键值，其最坏比较次数的数量级为

。A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)12、

以下排序算法中，

算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。。A.直接选择排序

B.冒泡排序

C.归并排序

D.堆排序13、

队列的操作原那么是

。A.先进后出

B.先进先出

C.只能进行插入

D.只能进行删除14、在以下两种求图的最小生成树的算法中，算法适合于求边稀疏的网的最小生成树。〔A〕PRIM〔B〕KRUSKAL判断以下各题是否正确，假设正确，在题前的括号内填“T”，否那么填“F”。1.对于循环队列，在队满情况下不能作入队处理，否那么，将产生“上溢”。2．完全二叉树的某结点假设无左孩子，那么它必是叶结点。3.一个有向图的邻接表和逆邻接表中的边结点个数不一定相等。4.假设一棵二叉树的任一非叶子结点度为2，那么该二叉树为满二叉树。5.在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。6.在栈为空的情况下不能作出栈处理，否那么，将产生下溢出。7.如果有向图G=(V,E)的拓扑序列唯一，那么图中必定仅有一个顶点的入度为0、一个顶点的出度为0。8.在大根堆中,必定满足每个结点的键值大于其左右子树中所有结点的键值。9.中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。1.

完全二叉树的第5层有8个结点(根结点在1层)，那么其叶子结点有_

个。2.

在单链表中，删除指针P所指结点的后继结点的语句是：

。3.

有向图G用邻接矩阵A[1..n，1..n]存储，其第i行的所有非零元素之个数等于顶点i的

。4.

平衡二叉树中每个结点的平衡因子定义为

。5.通常象交通、道路问题的数学模型是一种称为

的数据结构。6.

对于单链表，假设要在指针P所指结点之后插入由指针S所指结点，那么需要执行的语句序列为：

。7.在线性表的顺序存储结构中，假设每一个元素占h个存储单元，那么第I个元素ai的存储位置为

LOC(ai)=LOC(a1)+

。8.

设有数据结构〔D,R〕,其中D是数据元素的有限集，R是

的有限集。9.深度为k的二叉树其结点数至多有

个。10.

栈是一种特殊的线性表，它允许在表的一端进行

操作。11.

哈希表是一种查找表，可以根据哈希函数直接获得

。1.设哈希函数为H(K)=Kmod11，地址空间为0..12，用线性探测法解决冲突。请画出依