数据结构看题？ 数据结构考试题及答案
《数据结构》考试复习
数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的（关系）和运算等等的学科。
数据：客观对象的符号表示。
数据结构：带有结构和操作的数据元素集合
结构：数据元素之间的关系；
操作：对数据的加工处理 ；
数据结构的表示
1 图示表示
2 二元组表示
图示表示：由顶点和边构成的图，其中顶点表示数据 ，边表示数据之间的结构关系；
二元组表示：用一个二元组（D，S）表示数据结构，其中 D 是数据元素集合，S 是 D 上关系的集合。
算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。
数据的逻辑结构 ：数据之间的结构关系，是具体关系的抽象。
四种逻辑结构：
（1）集合 结构中的元素之间除了“同属一个集合”的关系之外，别无其他的关系。
（2）线性结构 结构中的元素存在一个对一个的关系。
（3）树状结构 结构中的元素存在一对多的关系。
（4）网状结构 结构中的元素存在多对多的关系。
两种存取结构：
（1）顺序存储结构 顺序存储借助元素的相对位置来表示元素之间的逻辑关系。
用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系；
(2) 链式存储结构 链式存储借助指示元素的指针表示数据元素之间的逻辑关系。
用任意一组存储单元存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。
数据的存储结构：
数据结构在计算机内存中的表示。
语句频度是指该语句在一个算法中重复执行的次数。
好的算法包括 正确性、可读性、健壮性、效率与低存储量需求。
线性表有两种基本的存储结构：
顺序存储结构和链式存储结构。
线性表的逻辑结构：
除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。
线性表的链式存储结构
用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了相关元素的存储位置。
每个存储结点都包含两部分：数据域和 指针域(链域)
在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。
链表不具备的特点是 可随机访问任一节点 。
具备 插入删除不须要移动元素 ③不必事先估计存储空间 ④所需空间与其长度成正比
带头结点的单链表head为空的判定条件是 ___head->next==NULL____
如果最常用的操作是取第i个结点及其前驱，则采用__顺序表___存储方式最节省时间。
向一个长度为n的顺序表中的第i个元素（0≤i≤n-1）之前插入一个元素时，需向后移动__n-i+1_ 个元素。
在单链表中，要删除某一指定的结点，必须找到该结点的 __直接前驱__ 结点。
访问单链表中的结点，必须沿着___指针____ 一次进行。
在一个单链表中p所指结点之后插入一个s所指结点时，应执行两个____s->next=p->next和p->next=S__的操作。
栈的特点是 ___先进后出_ 队列的特点是__先进先出__
栈和队列的共同特点是__只允许在端点处插入和删除元素__。
一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 dceab
若已知一个栈的进栈序列是p1，p2，p3， … ，pn 。其输出序列为1，2，3，…，n ，若p3=1，则p1为___不可能是2__
设有一个空栈，栈顶指针为1000H（十六进制，下同），现有输入序列为1、2、3、4、5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是_____2、3 _____ 栈顶指针是___1003H ___
一个队列的入对序列是若1，2，3，4，则队列的输出序列是______1，2，3，4__ 。
若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是____2和4 ___。
1栈是限定仅能在表尾一端进行插入、删除操作的线性表；
2 表尾称为栈顶，表头称为栈底；
3 栈的具有后进先出的特点；
4 栈顶元素的位置由一个栈顶指针指示；
5 进栈、出栈操作要修改栈顶指针；
6 一个栈的输入序列为a,b,c，则所有可能的出栈序列为： abc,acb,bac,bca,cba
空串与空白串是相同的，这种说法 ____不正确 ____。
串是一种特殊的线性表，其特殊性体现在___数据元素可以是多个字符 __。
__”21AB”__是C语言中”abcd321ABCD”的子串。
两个串相等的充分必要条件是__两个串的长度相等且对应位置的字符相同 ___ 。
空串是零个字符的串 ，其长度等于零 。
空白串是由一个或多个空格字符组成的串 其长度等于其包含的空格个数 。
模式串t=‘abaabcac”的next函数值序列为 -1 0 0 1 1 2 0 1 ，nextval函数值序列为 -1，0，-1，1，0，2，-1，1 。
由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 错误
某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 完全二叉树
深度为5的二叉树至多有 31 个结点。
根据使用频率为5个字符设计的哈夫曼编码不可能是 001，000，01，11，10
树和二叉树的主要差别是(1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；) (2. 树的结点无左、右之分，而二叉树的结点有左、右之分。)
深度为k的完全二叉树至少有 ___(2的K-1次方)_ 个结点，至多有（2的k次方）-1 个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是 （2的k-2次方）+1 _________。
一棵二叉树的第i(i³1)层最多有 (2的i-1次方) 个结点；一棵有n（n>0）个结点的满二叉树共有(2的logn次方) 个叶子结点和 （2的logn次方）-1 个非叶子结点。
1 二叉树的顺序结构:通过二叉树结点的相对位置，表示结点之间结构关系
2二叉链表：通过保存每个结点的左、右孩子结点的存储位置，表示结点之间的结构关系。
3 遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。
4二叉树的遍历方法:先序遍历 DLR、中序遍历LDR、后序遍历 LRD
5设p是指向二叉链表某结点的指针，请写出将左孩子结点数据赋值给变量e的主要操作语句：q=p-lchild;.e=q->data;
6 加上结点前趋后继信息的二叉树称为线索二叉树
7 在线索链表中左右指针域或指向孩子结点或指向前趋后继结点
一个n个顶点的无向图最多有___n(n-1)/2 ___条边。
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 ___1____ 倍。
关键路径是事件结点网络中 __从源点到汇点的最长路径 ___ 。
下面不正确的说法是 __任何一个关键活动提前完成，将使整个工程提前完成__，正确的是 关键活动不按期完成就会影响整个工程的完成时间 所有关键活动都提前，则整个工程提前完成 某些关键活动若提前完成，将使整个工程提前完成。
一个图的____邻接矩阵___ 表示法是惟一的 邻接表表示法是不惟一的。
在有n个顶点的有向图中，每个顶点的度最大可达___2(n-1)_ 。
采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为__(n+1)/2 _
在一个长度为12的有序表，按折半查找法对改表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为___37/12 ___
查找效率最高的二叉排序树是 ___平衡二叉树 ___
以下说法错误的是___散列表的结点中只包含数据元素自身的信息，不包含任何指针__ 。正确的是 散列法存储的基本思想是由关键码值决定数据的存储地址 装填因子是散列法的一个重要参数，它反映了散列表的装填程度 散列表的查找效率主要取决于散列表造表时选取的散列函数何处理冲突的方法
散列表的平均查找长度___与处理冲突方法有关与表长无关___ 。
设线性表（a1，a2，…，a500）元素的值由小到大排列，对一个给定的k值用折半法查找线性表，在查找不成功的情况下至多需比较____9___ 次。
一个无序序列可以通过构造一棵___二叉排序___树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
在散列存储中，装填因子a的值越大，则存取元素时___发生冲突的可能性就越大___ ；a的值越小，则存取元素时____发生冲突的可能性就越小__
排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为___插入排序 _
在文件“局部有序”或文件长度较小的情况下，最佳内排序方法是__直接选择排序___
对给出的一组关键字{14，5，19，20，11，19}。若按关键字非递减排序，第一趟排序结果为{14，5，19，20，11，19}，问采用的排序算法是_希尔排序___
在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是__选择排序 ___
在对一组记录{54，38，96，23，15，72，60，45，83}进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 ___5____ 次。
每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做_____交换__ 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 ___二路归并__ 排序。
____快速___ 排序方法采用的是二分法的思想 ____堆____ 排序方法其数据的组织采用完全二叉树结构。
稳定的：直接插入排序，折半插入排序， 归并排序，基数排序，冒泡
不稳定的：希尔排序，快速排序，简单选择排序，堆排序
1、分别用直接插入、快速和基数排序算法对整数序列75, 17,12, 8, 70,89, 3, 65, 77,9进行升序排序，写出第一趟的排序结果。
答：
直接插入排序：17，75，12，8，70，89，3，65，77，9
快速排序：｛9，17，12，8，70，65，3｝75｛77，89｝
基数排序：1.用LSD：70，12，3，75，65，17，77，8，89，9
2.用MSD：8，3，9，17，12，65，75，70，77，89
2、 分别写出三种排序算法的时间复杂度、空间复杂度及稳定性。
答：
直接插入排序：
时间复杂度O(n^2)，空间复杂度O(1),稳定
快速排序：
时间复杂度:
最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)
最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)
空间复杂度：
最坏情况：S(n)=O(n)
一般情况：S(n)=O(log2n)
排序不稳定
基数排序：
时间复杂度为：O (mn)
空间复杂度：O(n)
稳定性：稳定
排序方法 平均时间 最坏情况 辅助存储 稳定排序 适合情况
插入排序 O(n2) O(n2) O(1) 稳定 记录数较少
希尔排序 O(n(log2n)2) O(n2) O(1) 不稳定 不太多
快速排序 O(nlog2n) O(n2) O(log2n) 不稳定 较多
堆排序 O(nlog2n) O(nlog2n) O(1) 不稳定 多
归并排序 O(nlog2n) O(nlog2n) O(n) 稳定 都可以
基数排序 O(d(n+rd)) O(d(n+rd)) O(rd) 稳定 关键字位数少
寻一份《数据结构》试题及答案
《数据结构》试题
一、选择题（每小题2分，共30分）
1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A、单链表 B、双链表 C、单向循环 D、顺序表
2． 串是任意有限个（ ）
A、符号构成的序列 B、符号构成的集合
C、字符构成的序列 D、字符构成的集合
3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：
aij≠0(i≥j, l≤i, j≤ 10)
aij=0 (i<j, l≤i, j≤ 10)
现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为
A、2340 B、2336 C、2164 D、2160
4． 如果以链表作为栈的存储结构，则退栈操作时（ ）
A、 必须判别栈是否满
B、 对栈不作任何判别
C、 必须判别栈是否空
D、 判别栈元素的类型
5． 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）
A、front=front+1 B、front=(front+1)% m
C、rear=(rear+1)%m D、front=(front+1)%(m+1)
6． 深度为6（根的层次为1）的二叉树至多有（ ）结点。
A、 64 B、32 C、31 D、63
7． 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ）
A、24 B、25 C、23 D、无法确定
8． 设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ）
A、G’为G 的子图 B、G’为G 的边通分量
C、G’为G的极小连通子图且V’=V D、G’为G的一个无环子图
9． 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）
A、 一定都是同义词 B、一定都不是同义词
C、都相同 D、不一定都是同义词
10． 二分查找要求被查找的表是（ ）
A、 键值有序的链接表 B、链接表但键值不一定有序
C、 键值有序的顺序表 D、顺序表但键值不一定有序
11． 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）
A、n2 B、nlog2n C、log2n D、n-1
12． 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( )
A、ki≤k2i≤k2i+1 B、ki<k2i+1<k2i
C、ki≤k2i且ki≤k2i+1(2i+1≤n) D、ki≤k2i 或ki≤k2i+1(2i+1≤n)
13．一个具有n个顶点的无向完全图的边数为（ ）
A、n(n+1)/2 B、n(n-1)/2 C、n(n-1) D、n(n+1)
14．在索引顺序表中查找一个元素，可用的且最快的方法是（ ）
A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找
B、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找
C、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找
D、用二分查找法确定元素所在块，再用二分查找法在相应块中查找
15．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ ）存储方式最节省运算时间。
A、 单链表 B、双链表
C、带头结点的双循环链表 D、容量足够大的顺序表
二、判断题（每小题1分，共10分）
1．双链表中至多只有一个结点的后继指针为空。（ ）
2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ）
3．对链表进行插入和删除操作时，不必移动结点。（ ）
4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ）
5．在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。( )i
6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( )
7．“顺序查找法”是指在顺序表上进行查找的方法。（ ）
8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）
9．键值序列{A，C，D，E，F，E，F}是一个堆。
10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（）
三、填空题（每小题2分，共20分）
1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；
2．有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。
3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。
4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是＿＿＿＿＿＿。
5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。
6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。
7．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。
8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。
9．设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。
void printword(keytype HT[m])
{ for(i=1;i<=26;i++)
{ j=i;
while(____________________)
{ if (____________________) printf(“datatype”,HT[j]);
j=(j+1)% m;
}
}
}
10．设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：
malloc(p)；p->data=x; p->next=NULL；
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；
四、简答题：（每小题4分，共20分）
1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？
2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？
3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？
4. 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数值。
5. 中序遍历的递归算法平均空间复杂度为多少？
五、 算法设计题（每小题10分，共20分）
1. 试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。
2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。
参考答案
一、选择题
1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C
13、B 14、C 15、D
二、判断题
1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. ×
三、填空题
1．U=L - > next
2．4。
3．n-1、n(n-1)/2。
4．p - > prior = NULL。
5．连通
6．回路或环
7．28-1 = 27 = 128
8．24
9．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I
10．rear - > next = p、rear = p
四、简答题：
1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。
2.答：是：ABDEGCFH
3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，
时间效率为O(nlog2n)； 即O（1000log21000）=O(10000)
锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089
堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089
若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）
4. 答： 0112112343
5. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n)
五、 算法设计题
1.解：提示：堆的定义是：ki<k2i和K2i＋1
void SortA(sqlist &A, int n)
{ if(n==0) return(0); //空表
if (a[1]<a[2])
{ for( i=1; i<=n/2; i++) if (a[i]>a[2*i]|| a[i]>a[2*i+1])return(-1);
return(minleap)
};
else
{ for( i=1; i<=n/2; i++) if (a[i]<a[2*i]|| a[i]<a[2*i+1])return(-1);
return(“maxleap”)
};
}
2. 要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每一层的结点个数之后,再从计数器中挑出最大值。
typedef struct {
BTNode node; int layer;
//layer是结点所在层数
} BTNRecord, r ;
int Width(Bitree T ){ //求树宽
int count[ ]; //增开count向量，存放各层对应的结点数
InitQueue(Q); //队列初始化，Q的元素为BTNRecord类型
EnQueue(Q,{T, 0}); //根结点入队, 0 表示count[0]，下标值
while(!QueueEmpty(Q))
{ DeQueue(Q, r); //结点出队
count[r.layer]++; //出队时再把结点对应层的计数器加
if(r.node->lchild) EnQueue(Q,{r.node->lchild, r.layer+1});
if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1});
} //按层序入队时要随时标注结点所在层号
h=r.layer; //最后一个队列元素所在层就是树的高度
for(maxn=count[0], i=1; h; i++)
if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多
return (h*
maxn)} // Width
《数据结构》复习题（三）(1)
1.X.数据是计算机接收,识别,存储,加工处理的对象的全体.
2.√.最后不知道要不要加上一个"运算及实现"
3.√
4.X.先进后出.
5.X
6.√
7.X.最多有2^h -1个结点
8.X
9.√
10.X
二,
1.数据结构.
2.线性结构和非线性结构.
3.顺序表.
4.队列.
5.2^h -1.
6.顺序表.
7.排序.
8.
三.
1.A
2.A.先进先出.
3.没有学.
4.C.
5.B.一串下去.
几个数据结构判断题： 1：数据的逻辑结构说明数据元素之间的顺序关系...
1：数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构
答：错.
说明：逻辑结构可用不同的存储结构实现，“它依赖于计算机的存储结构”完全说不通。
2：算法的运行时间涉及到加，减，乘，除，转移，存取等基本运算。要想准确的计算总运行时间是不可行的。
答：对。
说明：软硬件环境都是千差万别的。也没必要去准确计算。算法分析只是为了比较不同算法的优劣。
3：在顺序存储结构中，有时也存储数据结构中元素之间的关系。（这个我觉得静态链表在存储结构上是顺序存储，可是其中不也存储了节点之间的关系的么？）
答：错。
说明：“顺序存储结构”必须体现元素之间的关系，不是“有时”。
“链式存储结构”并不是“顺序存储结构”，后者称“顺序表”或“邻接表”。
有些书用“链表是顺序存取”说法，但并不是指“链表是顺序存储结构”。