川大数据结构期终复习
模拟试题（一）
一、单项选择题（每小题2 分，共20分）
（1）以下数据结构中哪一个是线性结构？（）
A）有向图B）队列C）线索二叉树D）B树（2）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（）语句序列。
A）p=q; p->next=q; B）p->next=q; q->next=p;
C）p->next=q->next; p=q; D）q->next=p->next; p->next=q;
（3）（）不是队列的基本运算。
A）在队列第i个元素之后插入一个元素B）从队头删除一个元素
C）判断一个队列是否为空D）读取队头元素的值（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串。
A）14 B）5 C）6 D）8
（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。
A）11 B）35 C）19 D）53 以下6-8题基于下图：
（6）该二叉树结点的前序遍历的序列为（）。
A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D
C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B （7）该二叉树结点的中序遍历的序列为（）。
A）A、B、C、D、E、G、F B）E、A、G、C、F、B、D
C）E、A、C、B、D、G、F D）B、D、C、A、F、G、E （8）该二叉树的按层遍历的序列为（）。
A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F
C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （9）下面关于图的存储的叙述中正确的是（）。
A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
B）用邻接表法存储图，占用的存储空间大小与图中边数和顶点个数都有关
C）用邻接矩阵法存储图，占用的存储空间大小与图中顶点个数和边数都有关
D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
（10）设有关键字序列('q', 'g', 'm', 'z', 'a', 'n', 'p', 'x', 'h')，下面哪一个序列是从上述序列出
发建堆的结果?（ ）
A ）'a', 'g', 'h', 'm', 'n', 'p', 'q', 'x', 'z
B ）'a', 'g', 'm', 'h', 'q', 'n', 'p', 'x', 'z'
C ）'g', 'm', 'q', 'a', 'n', 'p', 'x', 'h', 'z'
D ）'h', 'g', 'm', 'p', 'a', 'n', 'q', 'x', 'z' 二、（每小题4分，共8分）
已知一个6?5稀疏矩阵如下所示，试：
?????????
?
?????
??
???--00
70
00000520000000100000010000 （1）写出它的三元组线性表；
（2）给出三元组线性表的顺序存储表示。 三、（本题8分）
求网的最小生成树有哪些算法？它们的时间复杂度分别下多少，各适用何种情况？ 四、（每小题4分，共8分）
对于如下图所示的有向图采用邻接表存储结构，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：
（1）从顶点v1出发进行深度优先搜索所得到的顶点序列； （2）从顶点v2出发进行广度优先搜索所得到的顶点序列。
五、（本题8分）
已知一个图的顶点集V 和边集E 分别为： V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};
若采用邻接表存储结构，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试给出得到的拓扑排序的序列（入度为零的顶点可采用栈或队列来进行存储）。
六、（本题8分）
对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。 七、（本题8分）
一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容。
先序序列： B F ICEH G 中序序列：D KFIA EJC
后序序列： K FBHJ G A 八、（每小题2分，共8分）
设有序列：w={23,24,27,80,28}，试给出： （1）二叉排序树； （2）哈夫曼树； （3）平衡二叉树；
（4）对于增量d=2按降序执行一遍希尔排序的结果。 九、（本题9分）
有关键字序列{7,23,6,9,17,19,21,22,5}，Hash 函数为H(key)=key % 5，采用链地址法处理冲突，试构造哈希表。
十、（本题15分）
假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。
模拟试题（一）参考答案
一、单项选择题
（1）B （2）D （3）A （4）B （5）B
（6）C （7）A （8）C （9）B （10）B
二、（每小题4分，共8分）
（1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) （2）三元组线性表的顺序存储表示如下所示：
?
?????????
?????????
?--726515254123151556 三、（本题8分）
求网的最小生成树可使用Prim 算法，时间复杂度为O(n 2
)，此算法适用于边较多的稠密图，也可使用Kruskal 算法，时间复杂度为O(eloge)，此算法适用于边较少的稀疏图。
四、（每小题4分，共8分） （1）DFS ：v1 v2 v3 v4 v5
（2）BFS：v2 v3 v4 v5 v1
五、（本题8分）
用栈存储入度为零的顶点得到的拓扑排序为：4 3 6 5 7 2 1
用队列存储入度为零的顶点得到的拓扑排序为：4 3 6 2 5 1 7
六、（本题8分）
所构造的堆如下图所示：
七、（本题8分）
在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。
八、（每小题2分，共8分）
（1）二叉排序树如下图所示：
（2）哈夫曼树如下图所示：
（3）平衡二叉树如下图所示：
（4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23
九、（本题9分）
哈希表如下图所示：
十、（本题15分）
从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第
三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。
具体算法实现如下：
// 文件路径名:exam1\alg.h
template
void DisplayHelp(BinTreeNode
// 操作结果：按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1
{
if(r != NULL)
{ // 空树不显式，只显式非空树
DisplayHelp
cout << endl; // 显示新行
for(int i = 0; i < level - 1; i++)
cout << " "; // 确保在第level列显示结点cout << r->data; // 显示结点
DisplayHelp
}
}
template
void Display(const BinaryTree
// 操作结果：树状形式显示二叉树
{
DisplayHelp
cout << endl; // 换行
}
模拟试题（二）
一、单项选择题（每小题2 分，共20分）
（1）设Huffman树的叶子结点数为m，则结点总数为（）。
A）2m B）2m-1
C）2m+1 D）m+1
（2）若元素a,b,c,d,e,f依次入栈，允许入栈、出栈操作交替进行。但不允许连续三次进行出栈操作，则不可能得到的出栈序列是（）
A）dcebfa B）cbdaef C）dbcaef D）afedcb （3）在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（）
A）41 B）82 C）113 D）122
（4）设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，m>3）（）。
A）658 B）648 C）633 D）653 （5）下列关于二叉树遍历的叙述中，正确的是（）。
A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点
B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点
C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点
D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点
（6）k层二叉树的结点总数最多为（）。
A）2k-1 B）2k+1C）2K-1 D）2k-1（7）对线性表进行二分法查找，其前提条件是（）。
A）线性表以链接方式存储，并且按关键字值排好序
B）线性表以顺序方式存储，并且按关键字值的检索频率排好序
C）线性表以顺序方式存储，并且按关键字值排好序
D）线性表以链接方式存储，并且按关键字值的检索频率排好序（8）对n个记录进行堆排序，所需要的辅助存储空间为（）。
A）O(1og2n) B）O(n)C）O(1) D）O(n2) （9）对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列函数值为为0的元素有（）个。
A）1 B）2 C）3 D）4 （10）下列关于数据结构的叙述中，正确的是（）。
A）数组是不同类型值的集合
B）递归算法的程序结构比迭代算法的程序结构更为精炼
C）树是一种线性结构
D）用一维数组存储一棵完全二叉树是有效的存储方法
二、（本题8分）
有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？
三、（每小题4分，共8分）
已知一个无向图的顶点集为{a, b, c, d, e}，其邻接矩阵如下所示：
???????
?????????1011001101000111001001001 （1）画出该图的图形；
（2）根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
四、（本题8分）
树有哪些遍历方法？它们分别对应于把树转变为二叉树的哪些遍历方法？ 五、（本题8分）
将关键字序列（7、8、11、18、9、14, 30）散列存储到散列列表中，散列表的存储空
间是一个下标从0开始的一个一维数组，散列函数为：H(key)=（key * 3）% m （m 为表长），
处理冲突采用线性探测再散列法，要求装填（载）因子为0.7，请画出所构造的散列表；计算查找成功的平均查找长度。
六、（本题8分）
试列出如下图中全部可能的拓扑排序序列。
七、（本题8分）
请说明对一棵二叉树进行按照先遍左子树，后右子树的方式进行前序、中序和后序遍历，其叶结点的相对次序是否会发生改变？为什么？
八、（本题8分）
设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉排序树。
九、（本题9分）
试画出表达式(a+b/c)*(d-e*f)的二叉树表示，并写出此表达式的波兰式表示，中缀表示及逆波兰式表示。
十、（本题15分）
以二叉链表作存储结构，试编写计算二叉树中叶子结点数目的递归算法。
模拟试题（二）参考答案
一、单项选择题（每小题 2 分，共20分） （1）B （2）D （3）B （4）D
（5）A
（6）A （7）C （8）C （9）D （10）D
二、（本题8分）
按照栈的特点可知以元素C第一个出栈，D第二个出栈的次序有CDEBA 、CDBAE 和CDBEA 3种。
三、（每小题4分，共8分）
【解答】
（1）该图的图形如下图所示：
（2）深度优先遍历序列为：abdce；广度优先遍历序列为：abedc。
四、（本题8分）
树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。
五、（本题8分）
由装载因子0.7，由于有7个数据元素，可得7/m=0.7，从而m=10，所以，构造的散列表为：
下标0 1 2 3 4 5 6 7 8 9
关键字30 7 14 11 8 18 . 9 .
比较次数 1 1 1 1 1 2 1
H（7）=（7*3）% 10=1
H（8）=（8*3）% 10=4
H（11）=（11*3）% 10=3
H（18）=（18*3）% 10=4
H（9）=（9*3）% 10=7
H（14）=（14*3）% 10=2
H（30）=（30*3）% 10=2
（2）查找成功的ASL=(1+1+1+1+1+2+1)/7=8/7
六、（本题8分）
全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364
七、（本题8分）
二叉树任两个中叶结点必在某结点的左/右子树中，三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的。所以在三种遍历序列中叶结点的相对次序是不会发生改变的。
八、（本题8分）
九、（本题9分）
表达式的波兰式表示，中缀表示及逆波兰式表示分别是此表达式的二叉树表示的前序遍历、中序遍历及后序遍历序列。
二叉树表示如下图所示：
波兰式表示：*+a/bc-d*ef
中缀表示：a+b/c*d-e*f
逆波兰式表示：abc/+def*-*
十、（本题15分）
本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。
具体算法实现如下：
// 文件路径名:exam2\alg.h
template
long LeafCountHelp(BinTreeNode
// 操作结果：按树状形式显示二叉树，level为层次数，可设根结点的层次数为1
{
if (r == NULL)
{ // 空二叉树
return 0; // 空树返回0
}
else if (r->leftChild == NULL && r->rightChild == NULL)
{ // 只有一个结点的树
return 1; // 只有一个结点的树返回1
}
else
{ // 其他情况, 叶子结点数为左右子树的叶子结点数之和
return LeafCountHelp(r->leftChild) + LeafCountHelp(r->rightChild);
}
}
template
long LeafCount(const BinaryTree
// 操作结果：计算二叉树中叶子结点数目
{
return LeafCountHelp(bt.GetRoot()); // 调用辅助函数实现计算二叉树中叶子结点数目}
模拟试题（三）
一、单项选择题（每小题2 分，共20分）
（1）对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下第一趟：2，12，16，5，10，88
第二趟：2，12，5，10，16，88
第三趟：2，5，10，12，16，88
则采用的排序方法可能是（）。
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，则下列序列中不可能是栈的输出序列的是（）。
A）2 3 1 B）3 2 1 C）3 1 2 D）1 2 3 （5）每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。
A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序（6）采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A）低于链接法处理冲突B）高于链接法处理冲突
C）与链接法处理冲突相同D）高于二分查找
（7）若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A）值B）函数C）指针D）引用（8）为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。
A）栈B）队列C）树D）图在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A）行号B）列号C）元素值D）非零元素个数（9）快速排序在最坏情况下的时间复杂度为（）。
A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2) （10）从二叉搜索树中查找一个元素时，其时间复杂度大致为（）。
A）O(n) B）O(1) C）O(log2n) D）O(n2)
二、（本题8分）
已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
三、（本题8分）
请画出如下图所示的邻接矩阵和邻接表。
四、（每小题4分，共8分）
设有如下图所示的AOE网（其中vi（i=l，2，…，6）表示事件，有向边上的权值表示活动的天数）。
（1）找出所有的关键路径。
（2）v3事件的最早开始时间是多少。
五、（本题8分）
一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1。但一个恰有一个顶点入度为0、其他顶点入度为1的有向图却不一定是一棵有向树。请举例说明之。
六、（本题8分）
假设把n个元素的序列（a1,a2,…a n）满足条件a k 七、（本题8分） 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种 解决该问题的方法： ①设最短路径初始时仅包含初始顶点，令当前顶点u 为初始顶点； ②选择离u 最近且尚未在最短路径中的一个顶点v ，加入到最短路径中，修改当前顶点u=v ； ③重复步骤②，直到u 是目标顶点时为止。 请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。 八、（本题8分） 已知一组关键字为（19,14,23,1,68,20,84,27,55,11,10,79），哈希函数： H(key)=key MOD 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。 九、（本题9分） 已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。 十、（本题15分） 编写一个算法求二又树的深度。 模拟试题（三）参考答案 一、单项选择题（每小题 2 分，共20分） （1）A （2）A （3）B （4）C （5）B （6）B （7）D （8）B （9）D （10）C 二、（本题8分） 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 三、（本题8分） 邻接矩阵： ??? ? ??? ? ????????01110 10101110111010101110 邻接表如下图所示： 四、（每小题4分，共8分） （1）找出所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。 （2）v3事件的最早开始时间是13。 五、（本题8分） 如下图所示的有向图，只有一个顶点的入度为0外，其他每个顶点的入度都为1，因为非连通，所以此图却不是有向树。 六、（本题8分） 不对，例如序列｛3、3、4、2、l ｝的“逆序元素”个数是2，2和1是“逆序元素”；但是将第二个3和2交换后，成为｛3、2、4、3、l ｝，此时“逆序元素”个数是3，2、3和1是“逆序元素”。然而交换后一定减少的是“逆序对”的个数，例如上例中｛3、3、4、2、l ｝的逆序对的个数是 7，交换第二个 3和2后，｛3、2、4、3、1｝的逆序对的个数是6。 七、（每小题4分，共8分） 该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A 到C 的最短路径为A →B →C ，事实上其最短路径为 A →D →C 。 八、（本题8分） 用链地址法处理冲突的哈希表如下图所示： ASL=121(1*6+2*4+3*1+4*1)=1.75 九、（本题9分） 构造二叉排序树的过程如下图所示。 构造的二叉排序树如下图所示： 十、（本题15分） 若二叉树为空，深度为0；若二叉树不空，则二叉树的深度为左右子树深度的最大值加1。本题最简单算法是递归算法。 具体算法实现如下： // 文件路径名:exam3\alg.h template int DepthHelp(BinTreeNode // 操作结果：求二叉树的深度 { if (r == NULL) { // 空二叉树 return 0; // 空二叉树的深度为0 } else { // 非空二叉树 int lDepth = DepthHelp(r->leftChild); // 左子树的深度 int rDepth = DepthHelp(r->rightChild); // 右子树的深度 return ((lDepth > rDepth) ? lDepth : rDepth) + 1; // 返回左右子树的深度最大值加1 } } template int Depth(BinaryTree // 操作结果：求二叉树的深度 { return DepthHelp(bt.GetRoot()); // 调用辅助函数求二叉树的深度 } 模拟试题（四） 一、单项选择题（每小题2 分，共20分） （1）以下数据结构中哪一个是线性结构？（） A）有向图B）栈C）二叉树D）B树 （2）若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。 A）单链表B）双链表C）带头结点的双循环链表D）单循环链表（3）（）不是队列的基本运算。 A）在队列第i个元素之后插入一个元素B）从队头删除一个元素 C）判断一个队列是否为空D）读取队头元素的值 （4）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串？ A）15 B）14 C）16 D）21 （5）由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。 A）11 B）37 C）19 D）53 以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。 （6）则该二叉树结点的前序遍历的序列为（）。 A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B （7）该二叉树有（）个叶子。 A）3 B）2 C）5 D）4 （8）该二叉树的按层遍历的序列为（）。 A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （9）下面的二叉树中，（）不是完全二叉树。 （10）设有关键字序列('q', 'g', 'm', 'z', 'a')，（）序列是从上述序列出发建的 小根堆的结果。 A）'a', 'g' , 'm', 'q', 'z' B）'a', 'g', 'm', 'z', 'q' C）'g', 'm', 'q', 'a', 'z' D）'g', 'm', 'a', 'q', 'z' 二、（本题8分） 试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求，对长度为n 的查找表来说，三种查找法在查找成功时的查找长度各是多少？ 三、（本题8分） 设有一个输入数据的序列是{46, 25, 78, 62, 12, 80 }，试画出从空树起，逐个输入各个数据而生成的二叉排序树。 四、（本题8分） 给定一个关键字序列｛24，19，32，43，38，6，13，22｝，请写出快速排序第一趟的结果；堆排序时所建的初始堆。 五、（本题8分） 设有带权无向网Net如下图所示。 试给出： （1）Net的邻接矩阵表示； （2）从V1开始的深度优先遍历； （3）从V1开始的广度优先遍历； （4）从V1开始执行的普里姆（Prim）算法过程中所选边的序列。 六、（本题8分） 用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。 七、（本题8分） 已知哈希表地址空间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。 八、（本题8分） 对于如下图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的变化情况。 九、（本题9分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI 十、（本题15分） 试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key 的元素值。 。 模拟试题（四）参考答案 一、单项选择题（每小题 2 分，共20分） （1）B （2）C （3）A （4）B （5）B （6）C （7）A （8）C （9）C （10）B 二、（本题8分） 三种方法对查找的要求分别如下： 顺序查找法：表中元素可以任意存放； 折半查找法：表中元素必须以关键字的大小递增或递减的次序存放： 分块查找法：表中元素每块内的元素可任意存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大于（或小）后一块内任何元素的关键字。 三种方法的平均查找长度分别如下： 顺序查找法：查找成功的平均查找长度为 2 1 +n ； 折半查找法：查找成功的平均查找长度为log 2(n+1)+1； 分块查找法：若用顺序查找确定所在的块，平均查找长度为 1)(21++s s n ；若用折半确定所在块，平均查找长度为2 )1( log 2s s n ++。 三、（本题8分） 如下图所示： 四、（本题8分） 快速排序的第一趟结果为｛22,19,13,6,24,38,43,12｝；堆排序时所建立的初始大顶堆如所图所示： 五、（本题8分） （1）Net 的邻接矩阵表示： ???????????? ??????????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞89767581946531410310 （2）从V 1开始的深度优先遍历：V1 V2 V4 V8 V5 V3 V6 V7 （3）从V 1开始的广度优先遍历：V1 V2 V3 V4 V5 V6 V7 V8 （4）从V 1开始执行的普里姆（Prim ）算法过程中所选边的序列： (V1,V3)，(V3,V6)，(V3,V7)，(V1,V2)，(V2,V5)，(V2,V4)，(V5,V8) 六、（本题8分） 先画出该二叉树的树形结构。对其进行后序遍历得到后序序列为：HIDJKEBLFGCA 。 七、（本题8分） 哈希表及查找各关键字要比较的次数如下图所示： 1(4×1+1×2+1×4+2×5)=2.5 ASL= 8 八、（本题8分） 用Kruskal算法构造最小生成树的过程如下图所示： 九、（本题9分） 先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下图所示。 十、（本题15分） 可按先遍历右子树，遍历根结点，再遍历左子树进行中序遍历，这样可实现由大到小遍历一棵二叉排序树。 具体算法实现如下： // 文件路径名:exam4\alg.h #include "binary_sort_tree.h" // 二叉排序树类 template void InOrderHelp(BinTreeNode // 操作结果: 从大到小输出以r为根的二叉排序树中所有的关键字值小于key的元素值 { if (r != NULL) { // 非空二叉排序树 InOrderHelp(r->rightChild, key); // 遍历右子树 if(r->data < key) cout << r->data << " "; // 输出根结点 else return; InOrderHelp(r->leftChild, key); // 遍历左子树 } } template void InOrder(const BinarySortTree // 操作结果: 从大到小输出二叉排序树中所有的关键字值不小于key的元素值 { InOrderHelp(t.GetRoot(), key); // 调用辅助函数实现从大到小输出二叉排序树中所有的关键字值不小于key的元素值} 模拟试题（五） 一、单项选择题（每小题2 分，共20分） （1）队列的特点是（）。 A）先进后出B）先进先出 C）任意位置进出D）前面都不正确 （2）有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（）遍分配与收集。 A）n B）d C）r D）n - d （3）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（）。 A）都不相同B）完全相同 C）先序和中序相同，而与后序不同D）中序和后序相同，而与先序不同（4）限定在一端加入和删除元素的线性表称为（）。 A）双向链表B）单向链表C）栈D）队列（5）若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。 A）起泡排序B）插入排序C）选择排序D）二路归并排序（6）设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（）。 A）m-n-1 B）n+1 C）m-n+1 D）m-n （7）对于具有n个顶点的强连有向图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 .. ;.. 第一章 概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K ）以及这些数据之间的 一组二元关系（关系集合R ）来表示：(K, R) 结点集K 是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R 是定义在集合K 上的一组关系，其中每个关系r （r ∈R ）都是K ×K 上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char ）、指针类型（pointer ） b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a ．大Ο分析法：上限，表明最坏情况 b ．Ω分析法：下限，表明最好情况 c ．Θ分析法：当上限和下限相同时，表明平均情况 第二章 线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L （设每个元素需占用L 个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e .插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n ）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n ）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head 和tail 指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n ）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n ）】 e.不足：next 仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head 和tail 指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相 比其比例较大时，应该慎重选择 第三章 栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch ： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项> <项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ? <常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp 为中缀表达式，PostfixExp 为后缀表达式 初始化操作数栈OP ，运算符栈OPND ；OPND.push('#'); 读取InfixExp 表达式的一项 操作数：直接输出到PostfixExp 中； 操作符： 当‘（’：入OPND; 当‘）’：OPND 此时若空，则出错；OPND 若非空，栈中元 素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若 为‘（’，弹出即可 当‘四则运算符’：循环（当栈非空且栈顶不是‘（’&& 当前运算符优先级>栈顶运算符优先级），反复弹出栈顶运 算符并输入到PostfixExp 中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP ； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP ； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear ；队满：(rear+1)%n==front 第五章 二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶结点的层数 d.如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树 e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树 f.当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶组成扩充二叉树，扩充二叉树是满二叉树 外部路径长度E ：从扩充的二叉树的根到每个外部结点（新增的空树叶）的路径长度之和 内部路径长度I ：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i 层（根为第0层，i ≥0）最多有2^i 个结点 b. 深度为k 的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1 f. 有n 个结点（n>0）的完全二叉树的高度为?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n 个结点的完全二叉树，结点按层次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点编号是 (i-1)/2 2) 当2i+1 判断： 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因 此属于同一数据对象正确 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中，插入和删除元素时，移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A，B,C,D，可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中，任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下，不能做出出栈操作，否则产生溢出正确 13.在前序遍历二叉树的序列中，任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空： 1.在N个节点的顺序表中删除一个节点平均需要移动（（N-1）/2）个节点，具体的移 动次数取决于（表长N和删除位置） 2.在单链表中除首节点外，任意节点的存储位置都由（直接前驱）节点中的指针指示 3.树中节点的最大层次称为树的（度） 4.由一颗二叉树的前序序列和（中）序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度（最小）的二叉树 6.二插排序树任意节点的关键字值（大于）其左子树中各节点的关键字值（小于）其 右子树中的各节点关键字值 7.二分查找法，表中元素必须按（关键字有序）存放 选择： 1.用单链表方式存储的线性表，储存每个节点需要两个域，一个数据域，另一个是（B 指针域） 2.设A1，A2，A3为三个节点；P，10，,2代表地址，则如下的链表存储结构称为（B 单链表） 3.单链表的存储密度（C 小于1） 4.在线性表中（B 中间元素）只有一个直接前驱和一个直接后续 5.两个指针P和Q，分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是（D P==Q） 6.在栈中存取数据的原则是（B 后进先出） 7.顺序栈判空的条件是（C top==-1） 8.串是一种特殊的线性表，其特殊性体现在（B 数据元素是一个字符） 9.求字符串T和字符串S中首次出现的位置的操作为（C 串的模式匹配） 10.深度为H的二叉树至多有（B 2H-1）个节点 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 一、选择(2’×15=30’) 1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时 间复杂度为( ) A.O(0) B.O(1) C.O(n) D.O(n2) 2.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾 结点，则在进行删除操作时( ) A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都不修改 D.队头、队尾指针都可能要修改 3.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S，若每个元素出栈 后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是( ) A.1 B.2 C.3 D.4 4.对n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( ) A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 5.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是( ) A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEG 6.下列线索二叉树中（用虚线表示线索），符合后序线索二叉树定义的是( D) 7.下面关于二分查找的叙述正确的是( ) A.表必须有序，表可以顺序方式存储，也可以链表方式存储 B.表必须有序，且表中数据必须是整型，实型或字符型 C.表必须有序，而且只能从小到大排列 D.表必须有序，且表只能以顺序方式存储 8.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受 数据初始特性影响的是( ) A.直接插入排序 B.快速排序 C.直接选择排序 D.堆排序 9.下列关于无向连通图特性的叙述中，正确的是( ) I.所有顶点的度之和为偶数 II.边数大于顶点个数减1 1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 安徽大学2014-2015学年第一学期《数据结构》期末考试试卷（A卷） （含参考答案） 一、单项选择题（本大题共15小题，第小题2分，共30分）在每小题列出的四个选项中只有一 个符合题目要求，请将其代码填在题后的括号内。错选或未选均无分。 1. 算法必须具备输入、输出和[ C ] A. 计算方法 B. 排序方法 C．解决问题的有限运算步骤 D. 程序设计方法 2. 有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是[ A ] A.访问第i个节点（1≤i≤n） B.在第i个节点后插入一个新节点（1≤i≤n） C.删除第i个节点（1≤i≤n） D.将n个节点从小到大排序 3．单链表的存储密度[ C] A．大于1 B. 等于1 C．小于1 D. 不能确定 4. 循环队列SQ的存储空间是数组d[m]，队头、队尾指针分别是front和rear，则执行出队后其头指针front值是[ D ] A．front=front+1 B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m 5. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 [ B ] A. O(1) B. O(n) C. O(n2) D. O(nlogn) 6 设二维数组A[0..m-1][0..n-1]按行优先顺序存储，则元素A[i][j]的地址为 [ B ] A．LOC(A[0][0])+(i*m+j) B．LOC(A[0][0])+(i*n+j) C.LOC(A[0][0])+[(i-1)*n+j-1] D. LOC(A[0][0])+[(i-1)*m+j-1] 7．设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是[ B] A．23415 B. 54132 C．23145 D. 15432 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系集， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。√ 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。√ 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。√ 15. 完全二叉树必定是平衡二叉树。√ 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。√ 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。√ 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 (e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中(c)具有先进先出（FIFO）特性，( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 的结果是 ( d ) 。 a: ‘database’ b: ‘data-base’ c: ‘bas’ d: ‘data-basucture’ 2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答：C。 9. 以下序列不是堆（大根或小根）的是 d 。 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.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20} 1.如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) { int low=0; int high=n-1; while (low<=high) { int mid=_______________________________； if (K==A[mid].key) return mid; //查找成功，返回元素的下标 else if (K大学数据结构期末知识点重点总结(考试专用)
数据结构期末考试复习笔记
2017年数据结构期末考试题及答案A
大连理工大学软件学院2014数据结构期末考试)
数据结构 期末考试复习题及答案
数据结构复习资料,java数据结构期末考试
数据结构期末考试试题及答案
安徽大学2014数据结构期末考试试卷(A卷)
数据结构学生期末复习卷习题答案
数据结构期末考试试题含答案
北方工业大学数据结构期末复习题
- 数据结构期末复习题
- (完整word版)数据结构期末复习资料
- 《数据结构》 期末考试复习参考题库2020年
- 数据结构 期末考试复习题及答案
- 电大数据结构(本)期末复习材料-考试
- 数据结构总复习.docx
- 计算机数据结构期末复习题
- 数据结构期末复习题及答案6
- 数据结构期末复习
- (完整word版)数据结构期末复习题
- 数据结构期末考试复习试题(整理完的)
- 数据结构c语言版期末考试复习题库
- 数据结构(C语言版)期末考试复习试题
- 数据结构期末复习提纲
- 数据结构期末考试复习笔记
- 《数据结构》期末复习题
- 数据结构期末考试复习总结
- 数据结构总复习资料(完整版)
- 数据结构复习资料java数据结构期末考试
- 数据结构总复习资料(完整版)