数据结构复习题汇总
- 格式：pdf
- 大小：194.03 KB
- 文档页数：13
数据结构复习题汇总
黄⽼师：
题型结构如下：
单项选择题，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 = 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）每个元素都有⼀个直接前驱和直接后继
（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, 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 ）为标准进⾏操作。
（A）条件判断（B）结点移动（C）算法表达式（D）赋值
语句12、深度为6的⼆叉树最多有（ B ）个结点
（A）64 （B）63 （C）32 （D）3113、在⼀个单链表中，已知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、在解决计算机主机与打印机之间速度不匹配问题时通常设置⼀个打印数据
缓冲区，主机将要输出的数据依次写⼊该缓冲区，⽽打印机则依相同次序从该缓冲区中取出数据打印。该缓冲区作为数据结构是⼀个（B）结构。A. 栈
B.队列
C.表（Table）
D.线性表
23、下⾯四棵树中，数字表⽰相应叶⼦结点的权值，则（ D ）是哈夫曼树（Huffman Tree）。
24、栈和队列的共同点是（C ）。
A. 都是先进先出B. 都是先进后出
C. 只允许在端点处插⼊和删除元素
D. 没有共同点
25、串是⼀种特殊的线性表，其特殊性体现在（B ）。
A. 可以顺序存储
B. 数据元素是⼀个字符
C. 可以链接存储
D. 数据元素可以是多个字符
26 带头节点的单链表head为空的判定条件是(A).
A. head->next==NULL
B. head==NULL
C. head->next==head
D. head!=NULL
27 对于⼀个具有n个顶点的⽆向图，若采⽤邻接矩阵表⽰，该矩阵的⼤⼩是（D）
A. n
B. (n-1)2
C. n-1
D. n2
28 设有两个串p和q，求q在p中⾸次出现的位置的运算称作（ B ）。
A. 连接
B. 模式匹配
C. 求⼦串
D. 求串长
29 下列排序⽅法中，（ C ）不易于在单链表上实现。
A 直接插⼊排序B冒泡排序 C 快速排序 D 简单选择排序
30 下⾯关于图的存储的叙述中，哪⼀个是正确的。（A）
A．⽤邻接矩阵法存储图,占⽤的存储空间数只与图中结点个数有关,⽽与边数⽆关
B．⽤邻接矩阵法存储图,占⽤的存储空间数只与图中边数有关,⽽与结点个数⽆关
C．⽤邻接表法存储图，占⽤的存储空间数只与图中结点个数有关，⽽与边数
⽆关D．⽤邻接表法存储图，占⽤的存储空间数只与图中边数有关，⽽与结点个数⽆关
31.排序⽅法中，从未排序序列中挑选元素，并将其依次与已排序序列（初始时为空）中的元素进⾏⽐较，将其放⼊已排序序列的正确位置上的⽅法，称为（ C ）A.快速排序
B. 起泡排序C插⼊排序 D. 选择排序
32.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，⽤⼆分法查找关键码12需做多少次关键码⽐较。（D）A.2
B.3
C. 5
D. 4
33.给定下列有向图和初始结点V1, 按深度优先遍历的结点序列为(B)
A、V1，V3，V4，V5，V2
B、V1，V2，V4，V5，V3
C、V1，V2，V5，V3，V4
D、V1，V2，V3，V4，V5
34 顺序查找法适合于存储结构为（ B ）的线性表。
A散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储
35 对线性表进⾏⼆分存储时，要求线性表必须（ C ）。
A 以顺序⽅式存储B以链接⽅式存储
C 以顺序⽅式存储，且节点按关键字有序排序
D 以链接⽅式存储，且节点按关键字有序排序
⼆．填空题1.若⼀个算法的基本语句的执⾏次数为(n3+n2log2n+14n)/n2，则该算法的时间复
杂度为__ O(n)______。2. 6.设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f将依次⼊栈S，
⼀个元素出栈后即进⼊队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量⾄少应该是 3 ，上述过程才不会出错。
3.设有⼀空队列Q，经Q.EnQueue(1)，Q.DeQueue ()，Q.EnQueue (2)，
Q.EnQueue (3)，Q.EnQueue(4)，Q.DeQueue ()；Q.EnQueue (5)⼀系列操作后。队列中从队⾸到队尾的元素依次是__ _3 45
4.空字符串与空格串的区别在于空格串是⼀个字符串，由若⼲空格组成；
空字符串中没有字符。5.7．已知某⼆叉树的后序遍历序列是BDECA, 中序
遍历序列是BADCE，那么它的前序遍历序列是ABCDE 。
6.写出右图所⽰⼆叉树按后序遍历的结果
17,23,45,65,78,09,31,53,87 。
7.写出右图所⽰⼆叉树度为1的内部结点的值09 。
8.⼆叉树的第k层的结点数最多为____2k-1____。
