数据结构模拟试题一
一、判断题（每小题1 分，共15分）
1.计算机程序处理的对象可分为数据和非数据两大类。
2.全体自然数按大小关系排成的序列是一个线性表。
3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。
4.顺序栈是一种规定了存储方法的栈。
5.树形结构中的每个结点都有一个前驱。
6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。
7.若某顶点是有向图的根，则该顶点的入度一定是零。
8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。
9.用一维数组表示矩阵可以节省存储空间。
10.广义表的长度与广义表中含有多少个原子元素有关。
11.分块查找的效率与线性表被分成多少块有关。
12.散列表的负载因子等于存入散列表中的结点个数。
13.在起泡排序过程中，某些元素可能会向相反的方向移动。
14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。
15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。
二、填空题（每空1分，共15分）
1.顺序表是一种_____________线性表。
2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。
3.栈和队列的区别在于________的不同。
4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。
5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域
为空的结点。
6.n个顶点的有根有向图中至少有___条边，至多有___条边。
7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。
8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是
_____。
9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。
10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。
三、选择题（每题2分，共30分）
1.计算机所处理的数据一般具有某种内在联系性，这是指________。
A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系
C．元素内部具有某种结构D．数据项和数据项之间存在某种关系
2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。
A．会产生运行错误B．R[1]~R[6]不构成一个顺序表
C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率
D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦
3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等
C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等
4. 栈的定义不涉及数据的__________。
A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构
5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。
A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5
6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。
A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在
7.对于一棵具有n个结点，度为3的树来说，____________。
A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓
D．至少在某一层上正好有3个结点
8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。
A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点
D．是一个有根有向图
9. 特殊矩阵用行优先顺序表表示，_____________
A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素
C．无法根据行列号计算矩阵元素的存储地址D．可以节省存储空间
10. 对一个非空的广义表来说，______________。
A．可能不含任何原子元素B．至少含一个原子元素
C．其长度不小于其中任何一个子表的长度D．至少含一个非空的子表元素
11.在有序表（2,4,6,8,10,12,14,16,18,20）上用折半查找方法查找13，依次被比较的是___________。
A．10,16,12,14 B．10,16,12 C．12,16,14 D．10,16,12,13
12.含14个结点的平衡二叉排序树，其最大深度是____。
A．4 B．5 C．6 D．7
13．如果元素R1和R2有相同的排序码，并且进行归并排序前，R1在R2的前面，则当排序结束后，___________。
A．R1有可能在R2的后面B．R1一定在R2的后面
C．R1一定在R2的前面D．选择R1或R2中的一个留在线性表中
14.下面4个序列中，只有___满足堆的定义。
A．13,27,49,76,76,38,85,97 B．76,38,27,49,76,85,13,97
C．13,76,49,76,27,38,85,97 D．13,27,38,76,49,85,76,97
15．下面4种排序方法中，属于不稳定的排序方法是_________排序和_________排序。
A．快速B．归并C．简单选择D．折半插入
四、图表题
1.已知树结点的前序序列是abcdefgh ，后序序列是cdebfhga，请画出这棵树的逻辑结构图。
2.采用基数排序法，对排序码序列572,586,413,15,724,529,525,608,37,119按从小到大的次序排序，请写出每趟收集后的线
性表。
五、算法填空题
假设G是n个顶点的连通无向图的邻接矩阵。下面的算法可用于对无向图进行深度遍历。请在空内填入适当内容，将算法补充完整。
Const n=10;
Int G[n][n];
V oid trav(int i){
Int j,t;
Int M[n],S[n];
Cout< M[i]=1;//做已访问标记 T=1;s[t]=I;//进栈 Do { (1)_______________ While (2)_______________ I++; If (i>n) (3)_______ Else { Cout < (4)_______ S[++t]=I; } } while(t) } 六、算法设计题（每小题12分，共24分） 1.假设长度为n的线性表已存放在R[1]~R[n]中，元素类型为整型。请写一个算法，给每个元素加上一个常数x，若相加后该元素为0，则将该元素从线性表中删除。 2.在一个m行n列的矩阵中，由相邻的并且取值相同的元素所构成的集合称为区域。例如，在图1所示矩阵中存在5个区域。设计算法setcolor(x,y,c)，算法的功能中将x行y列元素所在区域的所有元素的值改为c。例如，对图1所示矩阵执行算法调用setcolor(4,3,1)，应得结果如图2所示。 3 0 2 2 0 3 1 2 2 1 0 0 2 0 0 1 1 2 1 1 3 0 3 3 0 3 1 3 3 1 3 0 0 3 0 3 1 1 3 1 3 3 0 0 0 3 3 1 1 1 图1 图2 数据结构模拟试题二 一．判断题（每小题1 分，共15分） 1.构成数据的最小单位是数据项。 2.空线性表的一个特性是线性表中各结点尚未赋值。 3.非循环单向链表一定要有表头指针。 4.顺序栈的栈顶指针是一个指针类型的变量。 5.在表示树的双亲数组中，找结点的双亲要比找结点的孩子容易。 6.哈夫曼树中不存在度为1的结点。 7.在图中，与V i相邻的顶点其序号一定是i+1或i-1。 8.如果是不连通的无向图，则在相应的邻接表中一定有空链表。 9.矩阵的行数和列数可以不相等。 10.广义表的深度与广义表中含有多少个子表元素有关。 11.折半查找可以在有序的双向链表上进行。 12.散列查找过程中，关键字的比较次数和散列表中关键字的个数直接相关。 13.对n个元素执行简单选择排序，排序码的比较次数总是n(n-1)/2次。 14.物理记录的大小与逻辑记录的大小成正比。 15.对索引文件，索引表是建立在内存的，数据区是建立在外存的。 二．填空题（每空1分，共15分） 1.在程序中，描述顺序表的存储空间一般用________变量。 2.若用Q[0]~Q[100]作为循环顺序队列的存储空间，用“队首指针f的值等于队尾指针r的值”作为队空的标志，则创建一 个空队列所要执行的操作是___________。 3.栈和顺序栈的区别仅在于________。 4.n个结点的二叉树最大高度是___，最小高度是___。 5.树的存储方法主要有_____、_____和_____三种。 6.n个顶点的强连通图中至少有___条边。 7.10行20列矩阵若用列优先顺序表来表示，则矩阵中第7行第6列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，在含有14个元素的平衡二叉排序树上查找其中一个元素，元素间的平均比较次数至少 是_____次，至多是______次。 9.对n个元素执行快速排序，在进行第一次分组时，元素的移动次数至多是____次，至少是___次。 10.在B-树中，若某结点有i个孩子，则该结点中一定有___个关键字。 三．选择题（每题2分，共30分） 1.数据结构的研究内容不涉及________。 A．算法用什么语言来描述B．数据如何存储 C．数据的运算如何实现D．数据如何组织 2. 若H1是动态单向链表的表头指针，H2是动态双向链表的表头指针，则________。 A．H1和H2占用同样多的内存空间B．H1和H2是同类型的变量 C．H2要比H1占用更多的内存空间 D．双向链表要比单向链表占用更多的内存空间 3. 对于K个带头结点的静态单向链表来说，若各结点类型相同，则K个链表一般可共用_________。 A．同一个数组B．某些数组元素C．同一个表头结点D同一个表头指针 4.最不适合用作链接栈的链表是_____________。 A．只有表头指针没有表尾指针的循环双向链表 B．只有表尾指针没有表头指针的循环双向链表 C．只有表尾指针没有表头指针的循环单向链表 D．只有表头指针没有表尾指针的循环单向链表 5.栈和队列的共同点在于_____________。 A．都对存储方法作了限制B．都是只能进行插入、删除运算C．都对插入、删除的位置作了限制D．都对插入、删除两种操作的先后顺序作了限制 6.如果5个元素的出栈的顺序是1,2,3,4,5，则进栈的顺序可能是_____________。 A．3,5,4,1,2 B.1,4,5,3,2 C.2,4,3,1,5 D.5,1,3,2,4 7.若某棵二叉树结点的后序序列和层次序列正好相反，则该二叉树_____________。 A．每个结点都没有右孩子B．不存在度为2的结点C．每个结点都没有左孩子D．不存在 8.对于一棵具有n个结点，度为3的树来说，树的高度至少是____________。 A．┏log32n┓B．┏log3(3n-1)┓C．┏log3(3n+1)┓D．┏log3(2n+1)┓ 9．对n个顶点的带权连通图来说，它的最小生成树是指图中任意一个由n-1条__________。 A．权值最小的边构成的子图B．权值之和最小的边构成的子图C．权值之和最小的边构成的连通子图D．权值之和最小的边构成的无环子图 10. 所谓特殊矩阵是指_____________比较特殊。 A．矩阵元素之间的关系B．矩阵的处理方法 C．矩阵元素的取值D．矩阵的存储方法 11.若长度为n且有n种不同原子的广义表用链接方法存储，则时间复杂度为O（n）的运算是___________。 A．复制一个广义表B．求广义表的长度C．查找某个子表D．查找某个原子 12. 待查找元素关键字的值依次是47，且已存入变量k中，如果在查找过程中，和K进行比较的关键字值依次是47,32,46,25,47,则采用的查找方法____。 A．是一种错误的查找方法B．可能是分块查找C．可能是顺序查找D．可能是折半查找 13．如果元素R1和R2有相同的排序码，并且进行堆排序前，R1在R2的前面，则当排序结束后，___________。 A．R1一定在R2的前面B．R1一定在R2的后面 C．R1有可能在R2的后面D．选择R1或R2中的一个留在线性表中 14.下面4种排序方法中，属于稳定的排序方法是_________排序和_________排序。 A．堆B．基数 C. 快速 D. 起泡 15．在线性表中元素很多，且各元素已有序排列的情况下，执行_______排序或_________排序，排序码比较次数最多。A．简单选择B．堆C．归并D．堆 四．图表题（每小题4分，共8分） 1.已知5个叶子结点的权值分别为2，5，5，6，9，13 请画出相应的哈夫曼树。 2.对图1所示无向网络，画出从顶点V6开始用普里姆方法构造的最小生成树。 五．算法填空题（每空2分，共8分） 假设待排序的n个元素已存放在顺序表R[1]~R[n]中，排序码字段名是key。下面的算法用于对顺序表进行归并排序，请在空内填入适当内容，将算法补充完整。 V oid mergesort(list R, list S, int i, int j){ Int a,b,c,k; If (I { K=(i+j)/2; mergesort(R,S,i,k); mergesort(R,S,k+1,j); (1)____________________________ While ((a<=k)&&(b<=j)) { If (R[a].key<=R[b].key) { S[c]=R[a]; a++; } Else { (2)____________________________ } c++; } (3)____________________________ While (b<=j) { S[c]=R[b]; b++; c++; } (4)____________________________ } } 六．算法设计题（每小题12分，共24分） 1.假设head是某个带头结点单链表的表头指针，每个结点数值字段的类型为整型。写一个算法，从该链表中删除一个值最 大的结点，并将该结点的值存入表头结点的数值字段。 2.如果一个十进制正整数首位数字不为零，而且从左往右读和从右往读都一样，则称其为回文数。对一个n位的正整数x，反复执行下列操作，有可能得到一个回文数： （1）生成一个位数和x相同的正整数y，其中y i=x n-i+1,i=1,2,3…; （2）将y累加到x中。 如对于正整数87，按上述方法重复4次后，将得到回文数4884： 87+78=165 165+561=726 726+627=1353 1353+3531=4884 写一个按上述方法求回文数的算法。要求：x的初始值从键盘输入，其位数最多允许10位。如果得到回文数，就输出这个数，并输出上述步骤重复执行的次数，如果上述步骤重复了30次还得不到回文数，则放弃。 数据结构模拟试题三 一．判断题（每小题1 分，共10分） 1.逻辑结构不同的数据，要采用不同的存储方法来存储。 2.单链表中的结点只有后继，没有前驱。 3.栈和队列具有相同的逻辑特性。 4.二叉树中结点之间的相互关系不能用二元组来表示。 5.关键路径是由权值最大的边构成的。 6.在表示矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小无关。 7.在广义表中，每个原子必须是单个字符。 8.在平衡二叉排序树中，每个结点的平衡因子值是相等的。 9.只有在线性表的初始状态为逆序排列的情况下，起泡排序过程中，元素的移动次数才会达到最大值。 10.在B+树上可以进行顺序查找。 二．填空题（每空1分，共10分） 1.若用不带表头结点的单链表来表示链接队列，则只有在________情况下，插入操作既要修改队尾指针的值，也要修改队 头指针的值;只有在________情况下，删除操作仅需修改队首指针的值，不需修改队尾指针的值。 2.无向图中边的数目等于邻接矩阵中___________。 3.在各元素查找概率相等的情况下，在含有12个元素的二叉排序树上查找其中一个元素，元素间的平均比较次数至少是 ____次，至多是____次。 4.对12个元素进行快速排序，排序码的比较次数最多是___次。 5.对B+树来说，若某个非根分支结点中有6个关键字，则在它的某个孩子结点中至少有_____个关键字，至多有_____个关 键字。 6.如果在根结点中要查到要找的关键字，则对于B-树来说，下一步应该_________，而对于B+树来说，下一步应该_________。三．单选题（每题2分，共20分） 1.线性结构采用链式存储，________。 A．对插入、删除结点的操作较为有利B．不利于进行顺序访问 C．逻辑上相邻的结点在存储器中也相邻D．可以用一些不连续的存储区域来存放一个结点 2. 某算法的时间复杂度为O（2n），表明该算法的________。 A．执行时间与2n成正比B．执行时间等于2n C．问题规模是2n D．问题规模与2n成正比 3. 在长度为n的_________上，删除最后一个元素，其算法的时间复杂度是O(n)。 A．只有表头指针的循环双向链表B．只有表头指针的非循环双向链表 C．只有表尾指针的非循环双向链表D . 只有表尾指针的循环双向链表 4. 在4个元素的进栈序列给定以后，由这4个元素构成的可能出栈序列共有________种。 A．14 B.16 C.17 D.24 5. 在任何一棵二叉树中，如果结点a有左孩子b、右孩子c，则在结点的前序序列、中序序列、后序序列中，_____________。A．结点b一定在a的前面B．结点a一定在结点c的前面C．结点b一定在结点c的前面D．结点a一定在结点b的前面 6.若二叉树中结点的中序序列是abcdef，则结点的前序序列不可能是_____________。 A．dbacef B. acbedf C.efbacd D. bafdce 7. 对稀疏矩阵采用压缩存储，其优点之一是可以_____________。 A．减少非零元素的存储空间B．不减少访问非零元素所需时间 C．减少矩阵的存储空间D．降低非零元素间逻辑关系的复杂程度 8. 设待查找元素关键字的值是47，且已存入变量k中，如果在查找过程中，和k进行比较的关键字值依次是82,72,36,84,47，则所采用的查找方法可能是____________。 A．顺序查找B．分块查找C．折半查找D．平衡二叉排序树查找 9．在线性表中元素很多且各元素逆序排列的情况下，执行_______排序，元素的移动次数最少。 A ．直接插入 B ．起泡 C ．简单选择 D ．折半插入 10. 8阶方阵，每个元素占1个单元，按行优先顺序存储，起始地址为100，存储地址为135的那个元素是矩阵中每5行第___列的元素。 A ．2 B ．3 C. 4 D. 5 四．图表题（每小题4分，共8分） 1.用h(x)=x mod 7作为散列函数，用线性探测法处理冲突，所建立的散列表如下图所示，请将关键字17，27依次填入表中。 2.二叉树的表态二叉链表存储结构如下图所示。请给这棵二叉树加上中序线索。 1 Root 五．算法填表题（10分） 在下面的表格中给出一些语句，每个语句都有编号。要求利用这些语句设计一个完整的算法，该算法可对顺序表R[1]~R[n] 六．算法设计题（24分） 1.在一个字符序列中，由相同字符构成的子序列称为平台。写一个算法，其功能是，输入一个以句号结尾，长度任意的字符序列，分别统计由字符’A’所构成的平台的最大长度值，和由字符’B’所构成的最大长度值。如对于字符序列’ABCDANBBCBAJKBCAAABA’。’A’平台的最大长度是3，’B’平台的最大长度是2 。 数据结构模拟试题四 一、( 共30分，每题2分)单项选择题 1．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别为front 和rear ，则当前元素个数为（） A ．(rear-front+m) mod m B ．rear-front+1 C ．rear-front-1 D ．rear-front E ．以上答案都不对 2．数据结构中，与所使用的计算机无关的是数据的（） A．存储结构 B．物理结构 C．逻辑结构 D．物理结构和存储结构E．以上答案都不对 3．在具有n个结点的单链表中，实现（）的操作，其算法的时间复杂度都是O(n)。 A．遍历链表和求链表的第i个结点 B．在地址为p的结点之后插入一个结点 C．删除开始结点 D．删除地址为p 的结点的后继结点 E．以上答案都不对 4．某二叉树的前序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列为（） A．JLKMNOI B．LKNJOMI C．LKJNOMI D．LKNOJMI E．以上答案都不对 5．设n阶方阵是一个上三角矩阵，则需存储的元素个数为（） A．n B．n*n C．n*n/2 D．n(n+1)/2 E．以上答案都不对 6．串的“模式匹配”是指（） A．判两个串是否相等 B．对两个串进行大小比较 C．找某字符在串中第一次出现位置 D．找某子串在主串中第一次出现的位置 E．以上答案都不对 7．有n个结点的无向图的边数最多为（） A．n+1 B．n(n-1)/2 C．n(n+1) D．2n(n+1) E．以上答案都不对 8．多关键字文件是指（） A．有多个主关键字 B．有多个次关键字 C．有一个主关键字多个次关键字 D．有多个主关键字和多个次关键字 E．以上答案都不对 9．某顺序存储的表格中有90000个元素，已按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为（） A．25000 B．30000 C．45000 D．90000 E．以上答案都不对 10．对于序列(49,38,65,97,76,13,27,50)按由小到大进行排序，（）是初始步长d=4的希尔排序法第一趟的结果。 A. 49,76,65,13,27,50,97,38 B. 13,27,38,49,50,65,76,97 C. 97,76,65,50,49,38,27,13 D. 49,13,27,50,76,38,65,97 E. 以上答案都不对 11．下列排序算法中，第一趟排序完毕后，其最大或最小元素一定在其最终位置的算法是（） A．归并排序 B．直接插入排序 C．快速排序 D．冒泡排序 E．以上答案都不对 12．关于树和二叉树的有序性，正确的结论是（） A. 树和二叉树都是有序的 B．树和二叉树都可能是有序的 C．树和二叉树都是无序的 D．二叉树是有序的，树可能是有序的，也可能是无序的 E．以上答案都不对 13．在一个图中，所有顶点的度数之和与图的边数的比是（） A．1:2 B．1:1 C．2:1 D．4:1 E．以上答案都不对 14．若一组纪录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个纪录为基准得到的一次划分结果为（） A．38，40，46，56，79，84 B．40，38，46，79，56，84 C．40，38，46，56，79，84 D．40，38，46，84，56，79 E．以上答案都不对 15．从理论上讲，将数据以（）结构存放，则查找一个数据所用时间不依赖于数据个数n。 A．二叉查找树 B．链表 C．二叉树 D．哈希表 E．以上答案都不对 二、（共40分，每空2分）填空题 1．二分查找算法的时间复杂度为（） 2．在单链表中，申请到新结点p，将p指向的结点后插到s所指结点的操作，其一是p->next=s->next，其二是（）。3．对一般树和森林的后序遍历序列的次序与对应的二叉树的（）遍历次序相同。 4．设二维数组A[10..20,5..10]按行优先存储，每个元素占4个单元，A[10,5]的地址为160，则A[15,10]的地址为（）。5．线性结构反映结点间的逻辑关系是（）的，非线性结构反映结点间的逻辑关系是（）的。 6．赫夫曼树是带权路径长度（）的二叉树。 7．前序为abc且后序为cba的二叉树共有（）棵。 8．已知完全二叉树的高度为8，第7层有10个叶子结点，则二叉树的总结点数至少是（）。 9．已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为（）。 10．具有m个叶子结点的赫夫曼树共有（）个结点。 11．从一棵二叉树的前序序列和（）可唯一确定这棵二叉树。设某二叉树的后序遍历为ABKCBPM，则可知该二叉树的根为（）。 12．设广义表C=((x,(a,b)),((x,(a,b)),y)),则C的长度为（），深度为（）。 13．设有一稠密图G，则G采用（）存储较省空间。 14．在插入和选择排序中，若初始数据基本正序，则选用（）；若初始数据基本反序，则选用（）。 15．有n结点的二叉链表中，空指针域有（）个；利用这些空指针域，存放指向结点在中序次序下的前趋或后继的指针，这种附加的指针称为（）。 三、（10分）已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，……Nm个度为m的结点，问该树中有多少个叶子结点。请写出推导过程。 四、（15分）给定字母a,b,c,d,e的使用频率为0.09,0.17,0.2,0.23, 0.31。设计以该权值为基础的赫夫曼树，并给出赫夫曼编码。 五、（15分）设散列表的长度为13，散列函数为H(K)=K%13，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出用线性探测再散列解决冲突时所构成的散列表。并求等概率情况下这种方法查找成功和查找不成功时的平均查找长度。 六、（15分）已知奇偶交换排序如下所述：第一趟对序列中所有奇数项i扫描，将a[i]和a[i+1]进行比较；第二趟对序列中所有偶数项i扫描，将a[i]和a[i+1]进行比较。每次比较时若 a[i]>a[i+1]，则将两者交换。第三趟对所有奇数项，第四趟对所有偶数项……，如此重复，直至整个序列有序。 1)写出奇偶交换排序算法，设待排序的n个元素存放在数组a[1..n] 中。 2)说明你的排序方法的结束条件 3)若待排序的初始序列已按关键字从小到大有序，则关键字的比较次数是多少？ 七、（10分）已知长度为n的线性表A采用顺序存储结构，并且元素按值大小非递减排列，下面的算法删除线性表中多余的值相同的元素。请在算法中空白处填入适当内容，使之能够正常工作。 void DEL(int A[n]) // 设A[1]~A[n]存放着n个元素 { int i=1; while (1) do if (A[i]!=A[i+1]) i++; else //查找满足条件的元素 { for (2) A[j-1]=A[j];//删除第i+1个元素（满足条件的元素） (3) //修改线性表的长度 } } 八、（15分）设计算法，已知一棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，编写算法求从根结点到p所指结点之间的路径（要求输出该路径上每个结点的数据）。 数据结构模拟试题五 一、( 共34分，每题2分)单项选择题 1、在非空循环双链表中q所指的结点前插入一个由p所指结点的过程依次为：p->next=q；p->prior=q->prior；q->prior=p；（）； A．q->next=p B．q->prior->next=p C．p->prior->next=p D．p->next->prior=p E．以上答案都不对 2、已知有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6,v7}，E={ A．v1,v3,v4,v6,v2,v5,v7 B．v1,v3,v2,v6,v4,v5,v7 C．v1,v3,v4,v5,v2,v6,v7 D．v1,v2,v5,v3,v4,v6,v7 E．以上答案都不对 3、每个存储结点只含有一个数据元素，存储结点均匀地存放在连续的存储空间，使用函数值对应结点的存储位置，该存储方式是（）存储方式 A．顺序 B．链接 C．索引 D．散列 E．以上答案都不对 4、对于单链表形式的队列，队空的条件是（） A．F＝R＝nil B．F＝R C．F≠nil且R＝nil D．R－F＝1 E．以上答案都不对 5、采用邻接表存储的图的深度优先遍历算法类似于树的（）。 A．中根遍历 B．先根遍历 C．后根遍历 D．按层次遍历 E．以上答案都不对 6、对于序列(49,38,65,97,76,13,27,50)按由小到大进行排序，（）是初始步长d=4的希尔排序法第一趟的结果。A．49,76,65,13,27,50,97,38 B．13,27,38,49,50,65,76,97 C．97,76,65,50,49,38,27,13 D．49,13,27,50,76,38,65,97 E．以上答案都不对 7、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A．O（n）B．O（1） C．O（n2）D．O（log2n） E．以上答案都不对 8、设n阶方阵是一个上三角矩阵，则需存储的元素个数为（）。 A．n B．n*n C．n*n/2 D．n(n+1)/2 E．以上答案都不对 9、树中所有结点的度等于所有结点数加（）。 A．0 B．1 C．－1 D．2 E．以上答案都不对 10、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。 A．起泡排序 B．快速排序 C．堆排序D．直接选择排序 E．以上答案都不对 11、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（）。A．(rear-front+m) mod m B．rear-front+1 C．rear-front-1 D．rear-front E．以上答案都不对12、若线性表最常用的运算是查找第i个元素及其前驱的值，则采用（）存储方式节省时间。 A．单链表 B．双链表 C．单循环连表 D．顺序表 E．以上答案都不对 13、树最适合用来表示（） A．有序数据元素 B．无序数据元素 C．元素之间无联系的数据 D．元素之间有分支层次关系 E．以上答案都不对 14、多关键字文件是指（） A．有多个主关键字 B．有多个次关键字 C．有一个主关键字多个次关键字 D．有多个主关键字和多个次关键字 E．以上答案都不对 15、有m个叶子结点的赫夫曼树所具有的结点数为（） A．m B．m+1 C．2m D．2m-1 E．以上答案都不对 16、有n个结点的有向完全图的边数为（） A．n*n B．2n C．n(n-1) D．2n(n+1) E．以上答案都不对 17、判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（）。 A．求关键路径的方法 B．求最短路径的DIJKSTRA方法 C．深度优先遍历算法 D．广度优先遍历算法 E．以上答案都不对 二、（共30分，每空2分）填空题 1、在进行直接插入排序时, 其数据比较次数与数据的初始排列（）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（）关。 2、对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则顶点表的大小为（），所有边链表中边结点的总数为（）。 3、数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是( )，R是( )。 4、链表适用于（）查找。 5、通常程序在调用另一个程序时，都需要使用一个（）来保存被调用程度内分配的局部变量、形式参数的存储空间以及返回地址。 6、对一般树和森林的后序遍历序列的次序与对应的二叉树的（）遍历次序相同。 7、前序为abc且后序为cba的二叉树共有（）棵。 8、设广义表C=((x,(a,b)),((x,(a,b)),y)),则C的长度为（），深度为（）。 9、快速排序的平均时间复杂度是（）。 10、有n结点的二叉链表中，空指针域有（）个；利用这些空指针域，存放指向结点在中序次序下的前趋或后继的指针，这种附加的指针称为（）。 三：（共11分,每题1分）判断题(下列各题，你认为正确的，请打“√”，错的打“×”) 1、线性表采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（） 2、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。（） 3、二叉排序树或者是一颗空二叉树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其左孩子的值。( ) 4、凡是递归定义的数据结构都可以用递归算法来实现它的操作。（） 5、当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。（） 6、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。（） 7、在散列法中采取开散列（链地址）法来解决冲突时，其装载因子的取值一定在（0，1）之间。（） 8、执行某个排序算法过程中，最初相邻的结点排序后也相邻，则算法是稳定的。( ) 9、对具有n个顶点的连通图进行深度优先遍历，所得定点序列是唯一的。( ) 10、由于在线性表的链接存储表示中增加了指针字段，所以它比线性表的顺序表示更浪费空间。( ) 11、无向图的邻接矩阵一定是对称的，有向图的邻接矩阵则一定是非对称矩阵。( ) 四、（10分）已知待排序文件各记录的排序码顺序如下 72 73 71 23 94 16 05 68 请列出快速排序过程中每一趟的排序结果。 五、（10分）对于一个n×n的矩阵A的任一元素A[i][j]，按行存储时和按列存储时的地址之差是多少。（若设两种存储的开始存储地址LOC（0，0）及元素所占存储单元数d相同） 六、（10分）给定字母a,b,c,d,e的使用频率为0.09,0.17,0.2,0.23,0.31。设计以该权值为基础的赫夫曼树，并给出赫夫曼编码。 七、（15分）已知num为无符号十进制整数，请写一非递归算法，该算法输出num对应的r进制的各位数字。要求算法中用到的栈采用线性链表存储结构（1 八、（15分）试写一递归算法写出用二叉链表表示的给定二叉树的叶结点总数。 九、（15分）设计一个算法将单循环链表L分解为两个具有相同结构的链表A、B，其中，A表中结点是L表中值为奇数的结点，而B表中结点是L表中值为偶数的结点（要求利用原表结点）。 数据结构模拟题一参考答案 一.判断题 1、× 2、× 3、× 4、√ 5、× 6、√ 7、×. 8、√ 9、× 10、× 11、√12、× 13、√ 14、×. 15、×二．填空题 1.用顺序方法存储的 2.m 3.运算方法定义 4.h 2h-1 5.m n+1 6.n-1 n(n-1) 7. 147 8. 6.5 9.m 2m-1 10. 5 35 三.选择题 1.A 2.B 3.D 4.B 5.C 6.B 7.B 8.A 9.D 10.A 11.A 12.B 13.C 14.D 15.A C 四.图表题 1. 2.第一趟：572，413，724，15，525，586，37，608，529，119 第二趟：608，413，15，119，724，525，529，37，572，586 第三趟：15，37，119，413，525，529，572，586，608，724 五.算法填空题： (1) j=S[t]; i=1; (2) ((i<=n)&&((G[j][i]==0||M[i]==1))) (3) t=t-1; (4) M[i]=1; 六.算法设计题 1.const n0=100; int R[n0+1]; int n; void add(){ int i, j; j=1; for (i=1; i<=n; i++) if (R[i]!=x){ R[j]=R[i]+x; J=j+1; } n=j-1; } 2. const m=10, n=10, d[4][2]={{1,0},{0,-1},{-1,0},{0,1}}; int G[m+1][n+1]; int c0; void paint(int x, int y, int c){ int i , u, v; G[x][y]=c; for (i=0; i<=3; i++){ u=x+d[i][0]; v=y+d[i][1]; if ((u>=1)&&(u<=m)&&(v>=1)&&(v<=n)&&(G[u][v]==c0)) paint(u,v,c); } } 数据结构模拟题二参考答案 一.判断题 1、× 2、× 3、√ 4、× 5、√ 6、√ 7、×. 8、× 9、√ 10、× 11、×12、× 13、√ 14、×. 15、×二．填空题 1.数组 2.给f 和r 赋同一个值x,0≤x ≤100 3.前者没有指定存储方法,后者指定存储方法 4.n ┏log 2(n+1)┐ 5.双亲数组 孩子链表 左孩子和右兄弟链表 6.n 7. 57 8.1445 1447 9.n+1 2 10.i-1 三.选择题 1.A 2.A 3.A 4.D 5.C 6.D 7.B 8.D 9.D 10.C 11.B 12.B 13.C 14.BD 15.AB 四.图表题 1. 2.有两种可能,如下图所示 五.(1) a=i; b=k+1; c=i; (2)S[c]=R[b]; b++; (3)while (a<=k) {S[c]=R[a]; a++; c++;} (4)for(k=i; k<=j; k++) R[k]=S[k]; 六.算法设计题 1.Struct node{ int data; node* next; } typedef node* pointer; pointer head; void del(){ pointer p,q,r,s; q=head; p=q->next; s=q; r=p; while (r!=Null){ if (r->data>p->data){ q=s; p=r; } s=r; r=r->next; } q->next=p->next; p->next=head; head=p; } 2.const maxlength=40,maxtimes=30; struct list{ int v[maxlength+1]; int s; } int count, result; void test(list &A){ int i ,j; i=A.s; j=maxlength; while((i if (i for(i=A.s; i<=maxlength; i++) cout< void add(list &A, list &B){ int i, j, x; i=A.s; x=0; for (j=maxlength; j>=A.s j--) { x=A.v[j]+A.v[i]+x; B.v[j]=x%10; x=x/10; i++; } B.s=A.s; if(x>0){ B.s--; B.v[B.x]=x; } count++; } void revers(list &A, list &B) { test(A); if((result==0)&&(count 数据结构模拟题三参考答案 一.判断题 1、× 2、× 3、√ 4、√ 5、× 6、√ 7、×. 8、× 9、√ 10、√ 二．填空题 1、队列为空 队列中有2个或2个以上元素 2、非零元素个数的一半 3、 1237 6.5 4、 66 5、3 12 6、根据记录指针从数据区中读记录 继续沿指针向下一直查到该关键字所在树叶 三.单选题 1.A 2.A 3.B 4.A 5.C 6.C 7.C 8.A 9.C 10.C 四.图表题 1． 0 1 2 3 4 5 6 2 五 （1，17，4，16，15，9，8，14，6，16，11，12，17，2，17，17） 六.算法设计题 1..char s; int na=0,nb=0; void count(char t, int &n){ int i; i=0; do{ i++; cin>>s; } while (s==t); if (i>n) n=i ; } void main(){ cin>>s; while (s!=’’){ switch(s) { case ‘A’: count(‘A’,na); break; case ‘B’: count(‘B’,nb); } if ((s!=’A’)&&(s!=’B’)) cin>>s; } cout<<”A平台的最大值是：”< cout<<”B平台的最大值是：”< } 数据结构模拟试题五参考答案 一、( 共34分，每题2分)单项选择题 1、C 2、A 3、D 4、A 5、B 6、D 7、B 8、D 9、C 10、D 11、A 12、D 13、D 14、C 15、D 16、C 17、C 二、（共30分，每空2分）填空题 1、答：有、无 2、答：N、2E 3、答：结点的有穷集合、K上关系的有穷集合 4、答：顺序 5、答：栈 6、答：中 7、答：4 8、答：2, 4 9、答：O(nlog2n) 10、答：n+1, 线索 三：（共11分，每题1分）判断题 1、√ 2、× 3、× 4、√ 5、√ 6、√ 7、× 8、× 9、×10、×11、× 四、（10分）各趟结果如下： [68 05 71 23 16] 72 [94 73] [16 05 23] 68 [71] 72 [94 73] [05] 16 [23] 68 [71] 72 [94 73] 05 16 [23] 68 [71] 72 [94 73] 05 16 23 68 71 72 [94 73] 05 16 23 68 71 72 [73] 94 05 16 23 68 71 72 73 94 五、（10分）按行存储时与按列存储时，计算A[i][j]地址的公式分别为 LOC（i，j）=LOC（0，0）+（I*n＋j）*d 及 LOC'（i，j）=LOC（0，0）＋（j*n＋i）*d 两者相减，得 LOC（i，j）－LOC'（i，j）=LOC（0，0）＋（i*n＋j）*d－LOC（0，0）－（j*n＋i）*d =（i－j）*n*d＋（j－i）*d或： =（i－j）*（n－1）*d c(00) d(01) a(100) b(101) e(11) 七、（15分）解： typedef struct node{ int data; struct node *next; }link; void trans(int num,int r) { link *head=NULL,*s; int n; while (num>0){ n=num%r; s=(link *)malloc(sizeof(link)); s->data=n; s->next=head; head=s; num=num/r; } printf(“输出r进制的各位数字：”)； s=head; while (s!=NULL){ printf(“%d”,s->data); s=s->next; } } 八、（15分）解： int GetLeaves( BinTree root) { //求叶结点总数 static int leaf=0;//此l用于记叶结点数，注意用静态变量if(root) { //递归计算叶结点数 if(!(root->lchild||root->rchild)) leaf++; //如果该结点无左右孩子，则叶子数加1 GetLeaves(root->lchild);//算左子数的叶结点数 GetLeaves(root->rchild);//算右子树的叶结点数 } return leaf; //返回结果 } 九、（15分）解： Void split(ListNode *L, ListNode *&A, ListNode *&B) { ListNode *p=L->next; A=(ListNode *)malloc(sizeof(ListNode ));A->next=A; B=(ListNode *)malloc(sizeof(ListNode ));B->next=B; while (p!=L){ if (p->data%2==1){ q=p; p=p->next; q->next=A->next; A->next=q; } else { q=p; p=p->next; q->next=B->next; B->next=q; } } } 数据结构模拟试题四参考答案 一、( 共30分，每题2分)单项选择题 1A 2C 3A 4C 5D 6D 7B 8C 9C 10D 11D 12D 13C 14C 15 D 二、（共40分，每空2分）填空题 1、log2n 2、s->next=p 3、中序 4、300 5、一对一的，一对多或多对多的 6、最小 7、4 8、235 9、129 10、2m-1 11、中序，M 12、2，4 13、邻接矩阵 14、插入排序，选择排序 15、n+1,线索 三、（10分） 解：设N 为总结点数，N0为叶子结点数则：N=N0+N1+N2+……+Nm 又有：N-1=度的总数，则：N-1=N1*1+N2*2+……Nm*m 则有：N0=1+N2+2N3+……+(m -1)Nm 四、（15分） c(00) d(01) a(100) b(101) e(11) 五、（15分） 线性探测再散列的散列表： 查找成功的平均长度为ASL=1/12（1*6+2*1+3*3+4*1+9）=2.5 查找不成功的平均长度为ASL=1/13（1+2+3+4…….+13）=7 六（15分） （1） void oesort ( int a[n]) { int i,flag; do{ flag=0; for (i=1;i if (a[i]>a[i+1]){ flag=1 ; t=a[i+1]; a[i+1]=a[i]; a[i]=t; } for (i=2;i if (a[i]>a[i+1]){ flag=1; t=a[i+1]; a[i+1]=a[i]; a[i]=t; } } while (flag); （2）两趟排序无交换出现 （3） n-1次 } 七（10分）（1）i<=n （2）(j=i+1;j<=n;j++)（3）n-- 八（15分） void path(T,p) Bintree T,p; {Bintree stack[max],q; int tag[max],top=0,find=0; q=T; while ((q||top)&& find==0) {while (q) {stack[top]=q; tag[top++]=0; q=q->lchild; } if (top>0) {q=stack[top-1]; if (tag[top-1]==1) {if (q==p) {for (i=0;i find=1; } else top--; } if (top>0&&!find) {q=q->rchild; tag[top-1]=1; } } 计算机专业基础综合数据结构（排序）模拟试卷2(题后含答案及解 析) 题型有：1. 单项选择题 2. 综合应用题 单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。 1．采用简单选择排序，比较次数与移动次数分别为( )。 A．O(n)，O(log2n) B．O(log2n)，O(n2) C．O(n2)，O(n) D．O(nlog2n)，O(n) 正确答案：C 解析：简单选择排序的关键字比较次数KCN与对象的初始排列无关。第i 趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。因此，总的关键字比较次数为：最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n一1)。知识模块：数据结构 2．就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。 A．堆排序＜快速排序＜归并排序 B．堆排序＜归并排序＜快速排序 C．堆排序＞归并排序＞快速排序 D．堆排序＞快速排序＞归并排序 正确答案：A 解析：此题考查的知识点为排序的空间复杂性。堆排序辅助空间为O(1)，快速排序为O(log2n)，归并排序为O(n)。应选A。知识模块：数据结构 3．一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。 A．16，25，35，48，23，40，79，82，36，72 B．16，25，35，48，79，82，23，36，40，72 C．16，25，48，35，79，82，23，36，40，72 D．16，25，35，48，79，23，36，40，72，82 正确答案：A 解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。(79，82)和(23，40)归并后的结果为(23，40， 数据结构模拟题及答案 一、填空题（每小题 1 分，共 20 分）： 1、栈是一种 _____________的线性表，队列是一种_____________的线性表(要求填特性)。 2、___________________是数据的基本单位，可由若干个_______________ 组成，______________是数据的最小单位。 3、具有 354个结点的完全二叉树深度为 ________________，树中度为1的结点数为______________。 4、数组的运算有______________________________________ 和____________________________。 5、稀疏矩阵的压缩存储一般采用_____________________________存储方式。 6、广义表运算：tail ((( a, b ), ( c , ( d, e )))) = _______________________ 。 7、数据结构中评价算法的两个重要指标是__________ 、__________ 。 8、一个算法具有 5个特性: 、、，有零个或多个输入、有一个或多个输出。 9、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是: 。 10、Prim（普里姆）算法适用于求______ 的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求 ______ 的网的最小生成树。 11、 N个顶点的连通图的生成树含有 ______ 条边。 12、顺序查找 n个元素的顺序表，若查找成功，则比较关键字的次数最多为 __ __ 次；当使用监视哨时，若查找失败，则比较关键字的次数为_ _ __ 。 13、若不考虑基数排序，则在内排序过程中，主要进行的两种基本操作是关键字的 __________ 和记录的 _________ 。 14、直接插入排序用监视哨的作用是 ___________________。 15、一个字符串中 ________________ 称为该串的子串。 16 . 广义表(a,(a,b),d,e,((i,j),k))的长度是 _ ，深度是 _ 。 17. 在二叉树中，指针p所指结点为叶子结点的条件是 ______ 。 18. 有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是 _ __ ，带权路径长度WPL为 _ __ 。 19. 求图的最小生成树有两种算法，______ 算法适合于求稀疏图的最小生成树。 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 数据结构试题(A05) 一、选择题(共10小题，每小题1分，共10分) 1.下面程序段的时间复杂度是( ) m=0; for(i=1;i<=n;i++) for(j=1;j< = n;j++) m=m+1； A. O(n2) B.O(m + n + 1) C.O(m + n) D. O(n) 2.在单链表中，指针p指向元素为x的结点，实现〃删除x的后继〃的语句是() A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在长度为n的顺序表，当在任何位置上删除一个元素的概率相等时，删除一个 元素需要移动的元素的平均个数为( ) A.n/2 B.(n-1)/ 2 C.(n + 1)/2 D.(n+2)/2 4.一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是 () A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 6.设循环队列中数组的下标范围是1~n,其头尾指针分别为f和「，则其元素个数为( ) A.r-f C. (r-f) mod n + 1 B.r-f+1 D. (r-f+n) mod n 7.以下序列不是堆的是( )。 A.( 100 ,85,98,77,80,60,82,40,20,10,66) B.( 100 ,98,85,82,80,77,66,60,40,20,10) C.( 100 ,85,40,77,80,60,66,98,82,10,20 ) D.( 10,20,40,60,66,77,80,82,85,98, 100 ) 8 .在有序表( 12,24,36,48,60,72,84)中折半查找关键字72时所需进行的关键字比较次数为( )。 A. 3 B. 4 C. 5 D. 2 9.在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 A.选择排序 B.冒泡排序 C.快速排序口.插入排序 二、填空题(共20小题，每小题1分，共20分) 1、在单链表中，删除指针P所指结点的后继结点的语句 是。 2、线性表的两种存储结构分别是和。 3、己知完全二叉树的第4层有5个结点，则其叶子结点数是。 4、将下三角矩阵A[1….8,1….8]的下三角部分逐行地存储到起始地址为1000 的内存单元中，已知每个元素占4个单元，则A[7 , 5]的地址是。 5、有n个结点的强连通有向图G至少有条弧。 7、在有序表A[1….20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较的元素的下标依次为。 8、直接选择排序算法所执行的元素交换次数最多为。 9、在带有头结点的单链表L中，第一个元素结点的指针 数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 数据结构习题答案全真模拟题试题 第一章概论 一、名词解释 数据表示2.数据处理3.数据4.数据元素5.逻辑关系6.逻辑结构7.结构 8.运算9.基本运算10.存储结构11.顺序存储结构12.链式存储结构 13.索引存储结构 14.散列存储结构 15.算法 16.运行终止的程序可执行部分 17.伪语言算法 18.非形式算法 19.时空性能 20.时间复杂性 21.数据结构 二、填空题 1.计算机专业人员必须完成的两项基本任务是：_________和__________。 2.数据在计算机存储器中的存在形式称为_________。 3.概括地说，数据结构课程的主要内容包括: 数据的__________、定义在_________、数据的__________的实现。此外，该课程还要考虑各种结构和实现方法的__________。 4.由一种__________结构和一组__________构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。 5.存储结构是逻辑结构的__________实现。 6.数据表示任务是逐步完成的，即数据表示形式的变化过程是__________->__________->__________。 7.数据处理任务也是逐步完成的，即转化过程是__________->__________->__________。 8.从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即__________、__________和__________。 9.根据需要，数据元素又被称为__________、__________、__________或__________。 《数据结构》模拟试题3 一、单项选择题 1．带头结点的单向链表为空的判断条件是（）（设头指针为head）。 A．head = =NULL B．head!=NULL C．head->next= =head D．head->next= =NULL 2．非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。 A．p->next = =NULL B．p= =NULL C．p= =head D．p->next= =head 3．算法的时间复杂度与（）有关。 A．所使用的计算机 B．计算机的操作系统 C．算法本身 D．数据结构 4．设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（）。 A．n-i+1 B．n-i C．n-i-1 D．i 5．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。 A．p=s→next B．p→next=s→next; C．s→next=p→next; p→next=s; D．p→next= s; s→next= p→next 6．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。 A．r=f→next; B．r=r→next; C．f=f→next; D．f=r→next; 7．元素1，3，5，7按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。 A．7，5，3，1 B．7，5，1，3 C．3，1，7，5 D．1，3，5，7 8．在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。 A．4 B．3 C．6 D．12 9．在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）。 A．2i B．2i-1 C．2i+1 D．2i+2 10．一棵具有35个结点的完全二叉树，最后一层有（）个结点。 A．4 B．6 C．16 D．8 11．在一个无向图中，所有顶点的度数之和等于边数的（）倍。 A．3 B．2 C．2.5 D．1.5 12．已知如图3所示的一个图，若从顶点V1出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（）。 A．V1V2V4V8V5V3V6V7 B．V1V2V4V5V8V3V6V7 C．V1V2V4V8V3V5V6V7 D．V1V3V6V7V2V4V5V8 数据结构试卷（1） 一、选择题(30分) 1．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。 (A) 20 (B) 30 (C) 40 (D) 45 2．执行一趟快速排序能够得到的序列是（）。 (A) [41，12，34，45，27] 55 [72，63] (B) [45，34，12，41] 55 [72，63，27] (C) [63，12，34，45，27] 55 [41，72] (D) [12，27，45，41] 55 [34，63，72] 3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 4．时间复杂度不受数据初始状态影响而恒为O(nlog 2 n)的是（）。 (A) 堆排序(B) 冒泡排序(C) 希尔排序(D) 快速排序 5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。 (A) 空或只有一个结点(B) 高度等于其结点数 (C) 任一结点无左孩子(D) 任一结点无右孩子 6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。 (A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希尔排序 7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。 (A) 3 (B) 4 (C) 5 (D) 6 8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。 (A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og 2 n) 9．二路归并排序的时间复杂度为（）。 (A) O(n) (B) O(n2) (C) O(nlog 2n) (D) O(1og 2 n) 10. 深度为k的完全二叉树中最少有（）个结点。 (A) 2k-1-1 (B) 2k-1(C) 2k-1+1 (D) 2k-1 11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针， 指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 (A) front->next=s；front=s；(B) s->next=rear；rear=s； (C) rear->next=s；rear=s；(D) s->next=front；front=s； 12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。 (A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3) 13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。 (A) 99 (B) 100 (C) 101 (D) 102 14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。 (A) O(n) (B) O(n2) (C) O(nlog 2n) (D) O(1og 2 n) 15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。 (A) 第i行非0元素的个数之和(B) 第i列非0元素的个数之和 (C) 第i行0元素的个数之和(D) 第i列0元素的个数之和 二、判断题(20分) 数据结构试题及答案(十套)数据结构试题及答案(十套) 一、选择题 1. 数据结构是指（）。 A. 存储数据的方式 B. 数据的逻辑结构和物理结构 C. 数据的存储结构和存储方式 D. 数据的逻辑结构、存储结构和存储方式 答案：D 2. 在数据结构中，线性表的存储方式包括（）。 A. 顺序存储和链式存储 B. 数组存储和链表存储 C. 顺序存储、链表存储和索引存储 D. 顺序存储、链表存储和树形存储 答案：A 3. 栈是一种（）的数据结构。 A. 先进先出 B. 先进后出 C. 后进先出 D. 后进后出 答案：C 4. 队列是一种（）的数据结构。 A. 先进先出 B. 先进后出 C. 后进先出 D. 后进后出 答案：A 5. 二叉树中，度为0的节点称为（）。 A. 叶子节点 B. 根节点 C. 中间节点 D. 子节点 答案：A 6. 以下哪个排序算法是稳定的？ A. 快速排序 B. 选择排序 C. 插入排序 D. 希尔排序 答案：C 7. 图中表示顶点之间关系的边的数量称为（）。 A. 顶点度数 B. 边数 C. 路径数 D. 网络 答案：B 8. 哈希表通过（）来实现高效的查找操作。 A. 散列函数 B. 排序算法 C. 遍历操作 D. 顺序存储 答案：A 9. 平衡二叉树是一种具有左右子树高度差不超过（）的二叉树。 A. 0 B. 1 C. 2 D. 3 答案：B 10. 在链表中，删除节点的操作时间复杂度是（）。 A. O(1) B. O(logn) C. O(n) D. O(nlogn) 答案：A 二、填空题 1. 在顺序存储结构中，元素之间的逻辑关系由（）表示。 答案：下标 2. 二叉查找树的中序遍历结果是一个（）序列。 答案：递增 3. 哈希表通过散列函数将关键字映射到（）上。 数据结构试题（A05） 一、选择题（共10小题，每小题1分，共10分） 1.下面程序段的时间复杂度是( ) m=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) m=m+1； A. O(n2) B.O(m+n+1) C.O(m+n) D. O(n) 2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( ) A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在长度为n的顺序表，当在任何位置上删除一个元素的概率相等时，删除一个元素需要移动的元素的平均个数为( ) A.n/2 B.（n-1）/ 2 C.(n+1)/2 D.(n+2)/2 4.一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 6.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为( ) A. r-f B. r-f+1 C. (r-f) mod n+1 D. (r-f+n) mod n 7.以下序列不是堆的是( )。 A.（100，85，98，77，80，60，82，40，20，10，66） B.（100，98，85，82，80，77，66，60，40，20，10） C.（100，85，40，77，80，60，66，98，82，10，20） D.（10，20，40，60，66，77，80，82，85，98，100） 8．在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为( )。 A. 3 B. 4 C. 5 D. 2 9.在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 A.选择排序 B.冒泡排序 C.快速排序 D.插入排序 二、填空题（共20小题，每小题1分，共20分） 1、在单链表中，删除指针P所指结点的后继结点的语句是。 2、线性表的两种存储结构分别是和。 3、己知完全二叉树的第4层有5个结点，则其叶子结点数是。 4、将下三角矩阵A[1….8，1….8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址是。 5、有n个结点的强连通有向图G至少有条弧。 7、在有序表A[1….20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较的元素的下标依次为。 第一章概论 一、选择题 1、研究数据结构就是研究（ D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i O(m+n) 6、算法是（ D ）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（A ）。 i=s=0; while(s 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 全真模拟试题 、单项选择题(在每个小题的 4个备选答案中，选出正确的答案，并将其号码填在题后 的括号内。每小题 2分，共24分) 1•一个具有n 个顶点的无向完全图的边数为( ) ① n(n+1)/2 ② n(n-1)/2 ③ n( n-1) ④ n(n +1) 2•在索引顺序表中查找一个元素，可用的且最快的方法是( ) ① 用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 ② 用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 ③ 用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 ④ 用二分查找法确定元素所在块，再用二分查找法在相应块中查找 3 .若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个 元素，则采用( )存储方式最节省运算时间。 ①单链表 ③带头结点的双循环链表 4•串是( ) 5•堆排序在最坏情况下，其时间复杂性为( ) ① 0(nlog 2n) ② 0(n 2) ③ O(log 2n 2) ④ O(log 2n) 6•快速排序的记录移动次数( )比较次数，其总执行时间为 0(nlog2n)。 ①大于 ②大于等于 ③小于等于 ④小于 7. —棵二叉树有n 个结点，要按某顺序对该二叉树中的结点编号， (号码为1-n ),编 号须具有如下性质：二叉树中任一结点 V ,其编号等于其左子树中结点的最大编号加 1。 而其右子树中结点的最小编号等于 V 的编号加1。试冋应按()遍历顺序编号。 9•对有n 个记录的有序表采用二分查找，其平均查找长度的量级为( ) ① O(log 2n) ② O(nlog 2n) ③O(n) ④ O(n 2) 10 •对有n 个记录的表按记录键值有序的顺序建立二叉树，在这种情况下，其平均查 找长度的量 级为( ) ① O(n) ② O(nlog 2n) ③ O(1) ④(log 2n) 11 .栈操作的原则是( ) ①先进先出②后进先出 ③栈顶插入④栈顶删除 12 .设矩阵A 是一对称矩阵(a ij =a ji ,1<=i,j<=8)，若每个矩阵元素占 3个单元，将其上 三角部分(包括对角线)按行序为主序存放在数组 B 中，B 的首地址为1000,则矩阵元素 a 67的地址为() ① 1031 ② 1093 ③ 1096 ④ 1032 二、判断题(判断下列各题是否正确，正确在括号内打“V” ，错的打“x”。每小题1 分, 共10分) ②双链表 ④容量足够大的顺序表 ①一些符号构成的序列 ③一个以上的字符构成的序列 ②有限个字母构成的序列 ④有限个字符构成的序列 ①前根 ②中根 8.3个结点可构成( ①2 ②3 ③4 ③后根 ④层次 )个不同形态的二叉树。 ④5 数据结构考试试题及答案 数据结构考试试题及答案 数据结构是计算机科学中非常重要的一门课程，它涉及到了计算机程序设计中的数据组织、存储和管理等方面。在学习数据结构的过程中，掌握基本的数据结构类型、操作和算法是非常重要的。为了帮助大家更好地掌握数据结构，下面将提供一些常见的数据结构考试试题及答案。 一、选择题 1. 下面哪个不是线性数据结构？ A. 数组 B. 链表 C. 栈 D. 队列 答案：D. 队列 2. 下面哪个数据结构可以实现先进先出（FIFO）的操作？ A. 栈 B. 队列 C. 链表 D. 树 答案：B. 队列 3. 下面哪个数据结构可以实现后进先出（LIFO）的操作？ A. 栈 B. 队列 C. 链表 D. 树 答案：A. 栈 4. 下面哪个数据结构可以实现快速查找和插入操作？ A. 数组 B. 链表 C. 栈 D. 队列 答案：A. 数组 5. 下面哪个数据结构可以实现快速查找和删除操作？ A. 数组 B. 链表 C. 栈 D. 队列 答案：B. 链表 二、填空题 1. 请写出数组的插入操作的时间复杂度。 答案：O(n) 2. 请写出链表的删除操作的时间复杂度。 答案：O(1) 3. 请写出栈的出栈操作的时间复杂度。 答案：O(1) 4. 请写出队列的入队操作的时间复杂度。 答案：O(1) 5. 请写出二叉搜索树的查找操作的时间复杂度。 答案：O(log n) 三、简答题 1. 什么是数据结构？ 答案：数据结构是计算机存储、组织数据的方式，它定义了数据的逻辑结构和存储结构，以及对数据进行操作的算法。 2. 请解释什么是时间复杂度和空间复杂度。 答案：时间复杂度是衡量算法执行时间的度量，它表示算法执行所需的时间与问题规模之间的关系。空间复杂度是衡量算法所需的存储空间的度量，它表示算法所需的存储空间与问题规模之间的关系。 3. 请解释什么是递归算法，并给出一个例子。 答案：递归算法是一种自己调用自己的算法。一个经典的例子是计算斐波那契数列的第n项。代码如下： ``` int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } 1 下列数据结构中，能用二分法进行查找的是__A____。 A、顺序存储的有序线性表 B、线性链表 C、二叉链表 D、有序线性链表 解析：二分法查找只合用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减罗列(即从小到大，但允许相邻元素值相等)。 2 在软件设计中，不属于过程设计工具的是__D____。 A、PDL(过程设计语言) B、PAD 图 C、N-S 图 D、DFD 图 解析：软件设计工具包括：程序流程图、 N-S、PAD、HIPO，判定表， PDL(伪码)。而 DFD(数据流图)属于结构化分析工具。 3 在 switch(expression)语句中， expression 的数据类型不能是__A____。 A、double B、char C、byte D、short 解析：表达式expression 只能返回这个几种类型的值： int、byte、short 和 char。多分支语句把表达式返回的值挨次与每一个 case 子句中的值相比较，如果遇到匹配的值，则执行该 case 子句后的语句序列。 4 下列叙述中，错误的是__D____。 A、父类不能替代子类 B、子类能够替代父类 C、子类继承父类 D、父类包含子类 5 通过继承实现代码复用： Java 中所有的类都是通过直接或者间接地继承 https://www.doczj.com/doc/3e19205174.html,ng.Object 类得到的。继承而得到的类称为子类，被继承的类称为父类。子类不能继承父类中访问权限为 private 的成员变量和方法，子类可以重写父类的方法，及命名与父类同名的成员变量。 子类通过隐藏父类的成员变量和重写父类的方法，把父类的状态和行为改变为自身的状态和行为。注意：子类中重写的方法和父类中被重写的方法要具有相同的名字，相同的参数表和相同的返回类型，只是函数体不同。 由于子类继承了父类所有的属性(私有的除外)，所以子类对象可以作为父类对象使用。程序中凡是使用父类对象的地方，都可以用子类对象来代替。一个对象可以通过引用子类的实例来调用子类的方法。 java 运行时系统根据调用该方法的实例，来决定调用哪个方法。对子类的一个实例，如果子类重写了父类的方法，则运行时系统调用子类的方法;如果子类继承了父类的方法(未重写)，则运行时系统调用父类的方法。 6 自定义表格类中的 model 部份应实现的接口是___A___。 A、AbstractTableModel B、JTable C、TableModel D、TableModelable 7 下列代码中，将引起编译错误的行是__B____。 1)public class Exercise{ 2) public static void main(String args[]){ 3) float f=0.0; 4) f+=1.0; 5) } 6) } A、第 2 行 B、第 3 行 C、第 4 行 D、第 6 行 解析： float 定义变量赋值时，需要在数值后面加f 以标识它为浮点型，让系统知道该给它精确到多少位。 8 下列关于 Java 多线程并发控制机制的叙述中，错误的是___B___。 A、Java 中对共享数据操作的并发控制是采用加锁技术 B、线程之间的交互，提倡采用 suspend()/resume()方法 数据结构试卷（一） (1) 数据结构试卷（二） (4) 数据结构试卷（三） (6) 数据结构试卷（四） (8) 数据结构试卷（五） (11) 数据结构试卷（六） (14) 数据结构试卷（七） (16) 数据结构试卷（八） (18) 数据结构试卷（九） (20) 数据结构试卷（十） .............................. 23 数据结构试卷（一）参考答案. (26) 数据结构试卷（二）参考答案 (27) 数据结构试卷（三）参考答案 (28) 数据结构试卷（四）参考答案 (30) 数据结构试卷（五）参考答案 (32) 数据结构试卷（六）参考答案 (33) 数据结构试卷（七）参考答案 (36) 数据结构试卷（八）参考答案 (37) 数据结构试卷（九）参考答案 (38) 数据结构试卷（十）参考答案 (39) 这些都挺有用 数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 数据结构试题库及答案 第一章 概论 一、选择题 1、研究数据结构就是研究（ D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i计算机专业基础综合数据结构(排序)模拟试卷2(题后含答案及解析)
数据结构模拟题及答案
数据结构模拟卷(含答案)经典习题
数据结构模拟试题及答案
数据结构模拟题及答案
数据结构练习题(含答案)
数据结构习题答案全真模拟题试题
数据结构模拟试题及答案3
数据结构模拟试题附答案
数据结构试题及答案(十套)
数据结构模拟题及答案
数据结构试题集(包含答案 完整版)
数据结构试题及答案(十套)
《数据结构》全真模拟试题与解答
数据结构考试试题及答案
java数据结构测试题及答案解析
数据结构十套试题及答案
数据结构试题库及答案
相关主题
文本预览