发布时间 : 星期一 文章数据结构复习题汇总更新完毕开始阅读63b051366d175f0e7cd184254b35eefdc8d31534
黄老师：
题型结构如下：
单项选择题，15小题，30分； 填空题，5小题，10分；
综合应用题，50分（树、图、查找） 算法设计与分析，2选1,10分（线性结构） 试卷中一些算法只给英文名称；
考查范围 (黑体字为建议的重点考查内容；红字为备注；蓝字为拟纳入的考研大纲内容)
一、 绪论
（一） 算法、数据结构基本概念
（二） 算法分析中O（f（n））符号的含义 （三） 时间复杂度简单分析表示
二、线性表
（一）线性表的定义和基本操作 （二）线性表的实现
1.顺序存储 2.链式存储 3.线性表的应用
三、栈、队列
（一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用
四、树与二叉树 （一）树的概念 （二）二叉树
1.二叉树的定义及其主要特征
2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历及应用 （三）树、森林
1. 森林与二叉树的转换 2. 树的存储结构； 3.树和森林的遍历
4.线索二叉树的基本概念和构造 （四）二叉树的应用
1.哈夫曼（Huffman）树和哈夫曼编码
2.二叉排序树 五、 图
（一） 图的基本概念 （二） 图的存储及基本操作
1. 邻接矩阵法 2. 邻接表法 （三） 图的遍历
1. 深度优先搜索 2. 广度优先搜索 （四） 图的基本应用
1. 最小（代价）生成树 2. 最短路径 3. 拓扑排序 4. 关键路径
六、 查找
（一） 查找的基本概念 （二） 顺序查找法 （三） 折半查找法
（四） 二叉查找树及其基本操作（只考察基本概念） （五） 平衡二叉树（只考察基本概念） （六） 散列（Hash）表 （七） 查找算法的分析及应用
七、 排序
（一） 排序的基本概念 （二） 直接插入排序
（三） 气泡排序（bubble sort） （四） 简单选择排序
（五） 希尔排序（shell sort） （六） 快速排序 （七） 堆排序
（八） 二路归并排序（merge sort） （九） 各种排序算法的比较 （十） 排序算法的应用
选择题
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 （D）p = head
3、在单键表中，删除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）每个元素都有一个直接前驱和直接后继 （B）线性表中至少要有一个元素
（C）表中诸元素的排列顺序必须是由小到大或由大到小的
（D）除第一元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继
6、带头结点的单链表，其表头指针为head，则该单链表为空的判断条件是（ B ）
（A）head == NULL （B）head->next == NULL （C）head->next == head （D）head !== NULL
7、含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（C ） （A）1 （B）n/2 （C）n-1 （D）n
8、设有一个顺序栈S，元素S1, S2, S3, S4, S5, S6依次进栈，如果6个元素出栈的顺序是S2, S3, S4, S6, S5, S1，则栈的容量至少应该是（ B ） （A）2 （B）3 （C）5 （D）6
9、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点的总数最少为（ C ）个
（A）k+1 （B）2k （C）2k -1 （D）2k +1
10、从具有n个结点的单链表中查找指定结点时，若查找每个结点的概率相等，在查找成功的情况下，平均需要比较（ D ）个结点。
（A）n （B）n/2 （C）(n-1)/2 （D）(n+1)/2
11、从对顺序表上的插入、删除算法的时间复杂度分析来说，通常以（ B ）为标准进行操作。
（A）条件判断 （B）结点移动 （C）算法表达式 （D）赋值
语句
12、深度为6的二叉树最多有（ B ）个结点
（A）64 （B）63 （C）32 （D）31
13、在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在p,q之间插入s结点，则执行（ B ）操作。
（A）s->next = p->next; p->next = s; （B）q->next = s; s->next = p; （C）p->next = s->next; s->next = p; （D）p->next = s; s->next = q;
14、在线性表的下列存储结构中，读取元素花费时间最少的是（ D ） （A）单链表 （B）双链表 （C）循环链表 （D）顺序表 15、以下关于哈夫曼树的说法，错误的是（ D ）
（A）一般在哈夫曼树中，权值越大的叶子结点离根结点越近 （B）哈夫曼 树中没有度数为1的分支结点
（C）若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点 （D）若初始森林中共有n棵二叉树，需要进行2n-1次合并后才能剩下一棵最终的哈夫曼树
16.计算机算法指的是解决问题的有限运算序列，它必须具备输入、输出和（ B ）等5个特性。
A. 可执行性、可移植性和可扩充性 B. 可行性、确定性和有穷性
C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性
17.线性表采用链表存储地址时（ D ）。 A. 必须是连续的。
B. 部分地址必须是连续的。 C. 一定是不连续的。 D. 连续不连续都可以。
18.设循环队列中数组的下标范围是0．．n－1，其头指针front指向队首元素，rear指向队尾元素，则队列的长度为（D）。
A．rear－front B．rear－front＋1 C． （rear－front＋1）％（n＋1） D．（rear－front＋n＋1）％n
19．线性表的链式存储结构与顺序（连续）存储结构相比优点是（C ） A．所有的操作/运算 算法简单 B．便于随机存取 C． 便于插入和删除 D．便于查找
20.一个栈的输入序列为A，B，C，D，E，则下列序列中不可能是栈的输出序列的是（ B ）。
A．B C D A E B．E D A C B C． B C A D E D．A E D C B
22、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据