《数据结构》复习提纲
第一章
数据结构的概念及基本结构，数据结构在计算机中的表示方法及其存储结构 算法的特性，会计算时间复杂度
第二章
线性表的顺序存储表示，掌握插入和删除操作，
线性表的链式存储表示，掌握单链表的插入和删除操作
第三章
栈的定义及特点，栈的顺序存储表示
队列的定义及特点，链队列的插入和删除，循环队列的判空判满条件
第四章
串的概念及常用操作，掌握模式串next函数的求法
第五章
特殊矩阵的存储表示，稀疏矩阵的三元组表示， 会求广义表的头部和尾部
第六章
树的定义和基本概念，二叉树的性质，二叉树的链式存储结构――二叉链表 二叉树的先序，中序，后序, 层次遍历操作 会对二叉树进行先序，中序，后序线索化操作 树的存储结构――－孩子兄弟表示法
树，森林，二叉树三者之间的转换方法，以及它们遍历的对应关系 掌握哈夫曼树的构造，会求树的带权路径长度WPL
第七章
图的定义和术语，图的邻接矩阵表示法，邻接表，逆邻接表 掌握图的深度优先搜索算法，广度优先搜索算法 最小生成树――普里姆算法和克鲁斯卡尔算法， 会对AOV网进行拓扑排序
会求AOE网的关键路径，关键活动
第九章
顺序查找表，有序表的折半查找，索引查找表及其平均查找长度ASL 二叉排序树的建立和删除操作，会计算其平均查找长度ASL 掌握将二叉排序树转换成平衡二叉树的旋转处理方法， 哈希表的概念，掌握哈希函数的构造方法――除留余数法
掌握处理冲突的方法――线性探测再散列及平均查找长度ASL
――二次探测再散列及平均查找长度ASL
第十章
直接插入排序，希尔排序，快速排序，简单选择排序，堆排序，归并排序
会写上述排序算法每趟排序的结果，并对其进行排序性能分析（稳定性，时间复杂度等）
期末考试题型：选择题，填空题，综合题
练习题
一、单选题
1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（c） A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1
2.下列排序方法中，关键字的比较次数与记录的初始排列状态无关？（ c ） A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接选择排序
3.对n个记录的文件进行二路归并排序，总的时间代价为（ d）
2
A. O（nlogn） B. O（n） C. O（logn） D. O（n）
4.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（b ） A. 9 B. 11 C. 12 D. 不确定
5．在一个单链表HL中，若要在指针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；
6.广义表A=（a,b,(c,d),(e,(f,g))）,则式子Head(Tail(Head(Tail(Tail(A)))))的值为 d ； A．（g） B.(d) C.c D.d
7. 直接插入排序在最好情况下的时间复杂度为 （d）。
2
A. O(logn) B. O(n) C. O(n*logn) D(n) 8．数据结构是（ b ）
A．一种数据类型 B．数据的存储结构
C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 9．算法分析的目的是（ ）
A．辨别数据结构的合理性 B．评价算法的效率
C．研究算法中输入与输出的关系 D．鉴别算法的可读性
10．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ） A．插入 B．删除 C．排序 D．定位
11．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址
为1153，则数组元素A[6][7]的存储地址为（ ） A．1207 B．1209 C．1211 D．1213
12．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ） A．队列 B．栈 C．线性表 D．有序表
13．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ） A．不一定相同 B．都相同 C．都不相同 D．互为逆序
14．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ c ） A．层次遍历 B．前序遍历 C．中序遍历 D．后序遍历
15．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ） A．图中每个顶点的入度 B．图中每个顶点的出度 C．图中弧的条数 D．图中连通分量的数目 16．图的邻接矩阵表示法适用于表示（ ） A．无向图 B．有向图 C．稠密图 D．稀疏图
17．在对n个关键字进行简单选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（ ） A．i B．i+1 C．n-i D．n-i+1
18．下列排序算法中，其时间复杂度和记录的初始排列无关的是（ c ） A．插入排序 B．堆排序 C．快速排序 D．冒泡排序 19、冒泡排序是（ a ）的排序方法
A、稳定 B、不稳定 C、外部 D、选择
20．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ b ）
A．f,c,b B．f,d,b C．g,c,b D．g,d,b
21.主串S=\，若对子串T=\执行定位操作Index(S,T,9)，则操作的结果是__d_。 A)2 B)3 C)4 D)10
22.设有一个10阶的对称矩阵A，采有压缩存储方式，以行序为存储主序，若a(1,1)为第一个元素，其存储地址为1，且每个元素占用1个地址空间，则a(8,5)元素的地址为___。
A)13 B)33 C)18 D)40
二、填空题
1.从逻辑结构看，线性表是典型的 线性结构 ，树是典型的 树形结构 。 2.一棵含999个结点的完全二叉树的深度为____10_ __。 3．含n个顶点的无向连通图中至少含有______条边。
4.若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为____ __。 5．数据的逻辑结构被分为______集合_____、___线性结构___、_ 树形结构和____图形结构__四种。 6．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的____行号_、_列号_和_元素值__三项。
7．在一棵二叉树中，第5层上的结点数最多为_________。
8．以折半查找方法查找一个线性表时，此线性表必须是___________存储的________表。
9．快速排序在平均情况下的时间复杂度为_______________，在最坏情况下的时间复杂度为______。 10.假定一组记录的排序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序的过程中，第三趟归并后的结果为：____________________。 11.对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为_______，所有边链表中边结点的总数为____________。 12.采用邻接表存储的图的深度优先遍历算法类似于树的________________。 13.采用邻接表存储的图的广度优先遍历算法类似于树的________________。 三、综合题
1.设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一个元素为枢轴进行快速排序（按关键码值递增顺序），请给出每趟排序的结果。 2. 从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。 （1）画出该二叉排序树；
（2）画出从（1）所得树中删除关键字为37的结点之后的二叉排序树。
3．设散列表的长度为13；散列函数为H(Key)=Key mod p,给定的关键码序列为
19,14,23,01,68,20,84,27,55,11,试画出用线性探测再散列法解决冲突时所构造的散列表，并求出在等概率的情况下查找成功时的平均查找长度ASL。 4.画出在一个初始为空的AVL树中依次插入关键字3,1,4,6,9,8,5,7时AVL树的形态。 5.写出串S的next函数值。
S= a b c a b a a next[i]=
6.已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。 （1）画出该二叉树；
（2）画出与（1）求得的二叉树对应的森林。
7．某通讯系统只可能有A,B,C,D,E,F 这6种字符，其出现的概率分别是
0.1,0.4,0.04,0.16,0.19,0.11 ,试画出相应的哈夫曼树，设计哈夫曼编码。 8.设s=\求以下表达式的结果。 (1) Replace(s, \
(2) Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))
9.写出以下程序段的输出结果（队列中的元素类型QElemType 为char）。（4分） void main( ){
Queue Q; InitQueue(Q); char x=‘e’, y=‘c’;
EnQueue(Q, ‘h’); EnQueue(Q, ‘r’); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x);
DeQueue(Q, x); EnQueue(Q, ‘a’); while ( !QueueEmpty(Q) ){ DeQueue(Q, y); printf(y); }
printf(x); }
输出结果为
10.程序填空：对有序表R[1]至R[n]进行二分查找，成功时返回记录在表中的位置，失败时返回0。（6
分）
struct sqlist { keytype key; };
int binsrch(sqlist R[ ],keytype k) //在表R中查找关键字k { int low, high, mid; low=1; high=n;
while( ) mid=(low+high)/2;
if (k==R[mid].key) return mid;
else if( k return 0; } 11.求下列无向带权图的最小生成树。 9 b 5 4 a 5 3 5 c 5 e 7 3 f 2 g h 6 d 4 6 5 12. 阅读下列函数F，并回答问题： (1)如图所示的二叉树以二叉链表结构存储，rt为指向根结点的指针。写出调用函数F(rt)的输出结果。 (2)说明函数F的功能。 void F(BinTree T) { Stack S; if(T) { InitStack(&S); Push(&S,NULL); while(T) { printf(\ if(T->rchild) Push(&S,T->rchild); if(T->lchild) T=T->lchild; else T=Pop(&S); } } }