《数据结构》复习题汇总

《《数据结构》复习题汇总》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、老师：       题型结构如下：      单项选择题，15小题，30分；      填空题，5小题，10分；      综合应用题，50分（树、图、查找）      算法设计与分析，2选1,10分（线性结构）试卷中一些算法只给英文名称；考查范围(黑体字为建议的重点考查内容；红字为备注；蓝字为拟纳入的考研大纲内容)一、绪论（一）算法、数据结构基本概念（二）算法分析中O（f（n））符号的含义（三）时间复杂度简单分析表示二、线性表（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储2.链式存储3.线性表的应用 三、栈、队列（一）栈和队列的基

2、本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用四、树与二叉树（一）树的概念（二）二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历及应用（三）树、森林1.森林与二叉树的转换2.树的存储结构；3.树和森林的遍历4.线索二叉树的基本概念和构造（四）二叉树的应用1.哈夫曼（Huffman）树和哈夫曼编码 2.二叉排序树五、 图（一）   图的基本概念（二）   图的存储及基本操作1.     邻接矩阵法2.     邻接表法（三）   图的遍历1.     深度优先搜索2.  

3、   广度优先搜索（四）   图的基本应用1.     最小（代价）生成树2.     最短路径3.     拓扑排序4.     关键路径六、  查找（一）   查找的基本概念（二）   顺序查找法（三）   折半查找法（四）  二叉查找树及其基本操作（只考察基本概念）（五）平衡二叉树（只考察基本概念）（六）   散列（Hash）表（七）   查找算法的分析及应用 七、      排序（一）   排序的基本概念（二）   直接插入排序（三）   气泡排序（bubblesort）（四）   简单选择排序（五）   希尔排序（shellsort）

4、（六）   快速排序（七）   堆排序（八）   二路归并排序（mergesort）（九）  各种排序算法的比较（十）  排序算法的应用 选择题1、顺序队列的出队操作，正确修改队首指针的是（B）（A）sq.front=(sq.front+1)%maxsize;（B）sq.front=sq.front+1;（C）sq.rear=(sq.rear+1)%maxsize;（D）sq.rear=sq.rear+1;2、非空的循环单链表head的尾结点（由指针p指）满足（C）（A）p->next=NULL（B）p=NULL（C）p->next=head（

5、D）p=head3、在单键表中，删除p所指结点的直接后继，其中指针修改为（A）（A）p->next=p->next->next;（B）p=p->next;p->next=p->next->next;（C）p->next=p->next;（D）p=p->next->next;4、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（B）（A）数据元素具有同一特点（B）不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型也要一致（C）每个数据元素都一样（D）数据元素所包含的数据项的个数要相等5、关于线性表，下列说法正确的是（D）（A

6、）每个元素都有一个直接前驱和直接后继（B）线性表中至少要有一个元素（C）表中诸元素的排列顺序必须是由小到大或由大到小的（D）除第一元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继6、带头结点的单链表，其表头指针为head，则该单链表为空的判断条件是（B）（A）head==NULL（B）head->next==NULL（C）head->next==head（D）head!==NULL7、含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（C）（A）1（B）n/2（C）n-1（D）n8、设有一个顺序栈S，元素S1,S2,

7、S3,S4,S5,S6依次进栈，如果6个元素出栈的顺序是S2,S3,S4,S6,S5,S1，则栈的容量至少应该是（B）（A）2（B）3（C）5（D）69、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点的总数最少为（C）个（A）k+1（B）2k（C）2k-1（D）2k+110、从具有n个结点的单链表中查找指定结点时，若查找每个结点的概率相等，在查找成功的情况下，平均需要比较（D）个结点。（A）n（B）n/2（C）(n-1)/2（D）(n+1)/211、从对顺序表上的插入、删除算法的时间复杂度分析来说，通常以（B）为标准进行操

8、作。（A）条件判断（B）结点移动（C）算法表达式（D）赋值语句12、深度为6的二叉树最多有（B）个结点（A）64（B）63（C）32（D）3113、在