奥鹏远程教育中心助学服务部
httpwwwope
comc

福师12秋《数据结构概论》辅导课件知识点和例题整理第一讲1知识点1树：二叉树概念，性质，遍历算法。2知识点2图：邻接矩阵，邻接表存储方法，生成树，最小生成树。3知识点3排序：堆排序，快速排序，冒泡排序，直接插入，直接选择。4知识点4队列，栈，线性表：链式存储结构。1例题1设
为正整数下列程序段中前置以的语句的频度为（A）。i1k0Whilei
1k10iiA
1B
C
1D
22例题2高度为K的二叉树最大的结点数为（C）。kk1kA2B2C21D2k113例题3以下数据结构中，哪一个是线性结构（D）？A广义表B二叉树C稀疏矩阵D串4例题4若进栈序列为abc，则通过入出栈操作可能得到的abc的不同排列个数为：BA4B5C6D71
C2
答案解析：
1abcacbbacbcacabcba红色为合格的排列5例题5若一组记录的关键码为467956384084则利用快速排序的方法分别写出以第一个记录为基准得到的前三次划分结果。
心系天下求学人
Page1of5
专业专注周到细致
f奥鹏远程教育中心助学服务部
httpwwwope
comc

6例题6已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif请画出该二叉树
第二讲1例题1设串s1’ABCDEFG’，s2’PQRST’，函数co
xy返回x和y串的连接串，subssij返回串s的从序号i开始的j个字符组成的子串，le
s返回串s的长度，则co
subss12le
s2subss1le
s22的结果串是：DＡ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF2例题2向栈中压入元素的操作是先移动栈顶指针，后存入元素。3例题3线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（错）答案解析：线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。4例题4向一个长度为
的向量的第i个元素1≤i≤
1之前插入一个元素时，需向后移动
i1个元素。5例题5图的深度优先遍历：
心系天下求学人
Page2of5
专业专注周到细致
f奥鹏远程教育中心助学服务部
httpwwwope
comc

v0v1v3v7v4v2v5v66例题6下列关键字序列中D是堆aA167231239453bB942331721653cC165323943172dD1623533194727例题7将5个不同的数据进行排序至多需要比较D次A8B9C10D25
8例题8试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
答：DLR：ABDFJGKCEHILMLDRBFJDGKACHELIMLRD：JFKGDBHLMIECA9r