《数据结构》练习一（1-4章）
一、填空
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
1．数据的逻辑结构被分为____________、___________、____________和集合四种。
2．数据的存储结构被分为顺序、___________、____________和散列四种。
3．顺序存储的线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
，设其长度为n，在任何位置上插入或删除操作的时间代价基本上都是等效的。则插入一个元素大约要移动表中的 个元素，删除一个元素时大约要移动表中的 个元素。
4．数组的长度是 ，线性表的长度是 。
5．当向—个顺序表插入一个元素时，从插入位置开始向后的所有元素均需 一个位置，移动过程是从 向 依次移动每一个元素。
6．要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需 一个位置，移动过程是从 向 依次移动每一个元素。
7．在双向链表中，每个结点含有两个指针域，—个指向上 结点，另一个指向 结点。
8．根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为 和 ；
而根据指针的联接方式，链表又可分为 和 。
9．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用 存储结构为宜，相反，当经常进行的是插入和删除操作时，则采用 存储结构为宜。
10．顺序表中逻辑上相邻的元素，物理位置 紧邻，单链表中逻辑上相邻的元素，物理位置
紧邻。
11．线性表、栈和队列都是 结构，可以在线性表的 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 插入元素和在 删除元素。
12．设有一空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，push，push后，输出序列是 。
13．无论对于顺序存储还是链接存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为 。
14．设字符串S1=‘ABCDEF’，S2=‘PQRS’，则运算S=CONCAT(SUB(S1，2，LEN(S2))，SUB(Sl，LEN(S2)，2))后的串值为 。
15．空串是指 ，空格串是指 。
二、单项选择题：（每空2分，共30分）
1．下面程序段的时间复杂度为（ ）。
for(int i=0; i
next=p->next->next； B．p=p->next：
C．p=p->next->next； D．p->next=p：
5．线性表采用链式存储刚，其地址（ ）。
A．必须是连续的 B．一定是不连续的
C．部分地址必须是连续的 D．连续与否均可以是
6．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则须执行（ ）。
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
7．线性表是（ ）。
A．一个有限序列，可以为空 B．一个有限序列，不可以为空
C．一个无限序列，可以为空 D．一个无限序列，不可以为空
8．在一个长度为n的顺序表中向第i个元素(onext=s； B．s->next=hs; hs=s；
C．s->next=hs->next；hs->next=s： D．s->next=hs；hs=hs->next；
14．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作应执行（ ）。
A．front->next=s; front=s B．s->next=rear； rear=s
C．rear->next=s; rear=s D．s->next=front； front=s
15．在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ ）。
A．front=front->next B．rear=rear->next
C．rear=front->next D．front=rear->next
三、简述以下算法的功能（每题5分，共10分）
1．status A(LinkedList L)
{if (L&&L→next){
Q=L; L=L→next; P=L;
while (P→next) P=P→next;
P→next=Q; Q→next=NULL;
}
Return OK;
}
2．status algo2(Stack S, int e)
{
Stack T; int d;
InitStack(T);
while(!StackEmpty(S)){
Pop(S,d);
if(d!=e) Push(T,d);
}
while (!StackEmpty(T)){
Pop(T,d);
Push(S,d);
}
}
四、算法编写（共25分）
1．
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
在无头结点的单链表中删除第i个结点的算法。（7分）
2．设计将单循环链表逆置的算法。（8分）
3．编写一个程序，将两个字符串s1和s2进行比较，若s1>s2则输出一个正数，若s1=s2则输出0，若s1
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
是二叉树采用（ ）存储结构。
A．三叉链表 B．广义表
C．二叉链表 D．顺序
14．设a，b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（ ）。
A．a在b右方 B．a在b左方
C．a是b的祖先 D．a是b的子孙
15．线索二叉树是一种（ ）结构。
A．逻辑 B．逻辑和存储
C．物理 D．线性
三、应用题（每题6分，共24分）
1．二叉树与树之间有何区别？度为2的树与二叉树有何区别？
2．一棵二叉树如图：写出对此树进行先序、中序、后序遍历时得到的结点序列。
3．已知一组元素为（45，25，80，60，18，30，12，40，70），试画出按元素输入排列顺序而生成的一棵二叉排序树。
4．任一棵有n个结点的二叉树，已知它有m个叶子结点。证明：度为2的结点有m-1个，其他结点是度数为1的结点。
四、算法编写（每题8分，共16分）
1．试编写一个判别表达式中开、闭括号是否配对的算法。
2．试写出先序遍历二叉树的递归算法。
《数据结构》练习三（7、9章）
一、填空题（每空2分，共40分）
1．设无向图G的顶点数为n，图G最少有 边；最多有 条边。若G为有向图，有n个顶点，则图G最少有 条边，最多有 条边。
2．假定一个无向图，有n个顶点e条边，则在邻接矩阵表示中，求任一个顶点度数的时间复杂度为 ，用邻接表表示中，访问一个顶点的所有邻接点的时间复杂度为 。
3．对于含有n个顶点e条边的无向连通图，利用普里姆算法生成最小生成树的时间复杂度为 ，利用克鲁斯卡算法生成最小生成树的时间复杂度为 ，在具有n个顶点的图的生成树中，含有 条边。
4．对用邻接矩阵表示的图进行深度优先或广度优先搜索遍历时的时间复杂度为 ，对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为 ，图的深度优先或广度优先搜索遍历的空间复杂度均为 。
5．在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的 ；而对于无向图而言等于该顶点的 。
6．设有向图G有n个顶点e条边，进行拓扑排序时的总的计算时间为 。
7．若无向图G的顶点度数的最小值大于或等于 时，G至少有一条回路。
8．假定查找有序表R[0．．11]中每个元素的概率相等，则进行顺序查找的平均查找长度为 ，进行二分查找时的平均查找长度为 。
二、单项选择题：（每空2分，共32分）
1．已知一个图如下所示，则从顶点a出发按深度优先搜索遍历则可以得到的一种顶点序列为（ ）。
A． a， b， c， c， d， f B． a， c， f， e， b， d
C． a， c， b， c， f， d D． a， e， d， f， c， b
2．在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。
A．1/2 B．2
C．1 D．4
3．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2
C．1 D．4
4．一个具有n个顶点的无向图中，要连通全部顶点至少需要（ ）条边。
A．n B．n+l
C．n/2 D．n-1
5．关键路径是事件结点网络中的（ ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长的回路 D．最短的回路
6．对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（ ）。
A．n B．(n-1)2
C．(n十1)2 D．n2
7．n个顶点的强连通图至少有（ ）条边。
A．n B．n-1
C．n+1 D．n(n-1)
8．采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。
A．中序遍历 B．先序遍历
C．后序遍历 D．按层遍历
9．采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。
A．按层遍历 B．中序遍历
C．后序遍历 D．先序遍历
10．判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。
A．求关键路径的方法 B．求最短路径的Dijkstra方法
C．深度优先遍历算法 D．宽度优先遍历算法
11．采用顺序查找的方法查找长度为n的线性表，则查找每个元素的平均比较次数为（ ）。
A．n B．n/2
C．(n+l)/2 D．(n-1)/2
12．采用二分查找的方法查找长度为n的有序表，查找每个元素时平均比较次数与对应判定树的高度(设高度≥2)相比较是（ ）。
A．小于 B．大于
C．等于 D．大于等于
13．对线性表进行二分查找时，
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
线性表必须（ ）。
A．以顺序存储方式存储 B．以链式存储方式存储
C．以顺序存储方式存储，且数据元素有序 D．以链式存储方式存储，且数据元素有序
14．己知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分查找值为90的元素时，查找成功的比较次数为（ ）。
A．1 B．2
C．3 D．4
15．对于一个线性表，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（ ）。
A．以顺序方式存储 B．以链接方式存储
C．以散列方式存储 D．以上均可
16．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则宜采用的查找方法为 （ ）。
A．分块查找 B．顺序查找
C．折半查找 D．基于属性查找
三、应用题（共28分）
1、如下图所示的带权有向图G，试回答以下问题：（10分）
(1)给出从结点V1出发按深度优先搜索遍历G所得的结点序列，并给出按广度优先搜索遍历G所得的结点序列。
(2)给出G的一个拓扑序列。
(3)给出从结点v1到结点v8的最短路径和关键路径．
2、证明具有n个顶点的无向完全图的边数为n(n-1)/2。（8分）
3、已知一个长度为12的表{Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}
(1)试按表中元素的次序依次插入一棵初始为空的二叉排序树。 (字符之间以字典顺序比较大小)画出对应的二叉排序树，并求出在等概率情况下查找成功的平均查找长度。
(2)若对表中元素先排序构成有序表，试求在等概率情况下对此有序表进行折半查找时查找成功的平均查找长度。（10分）
《数据结构》练习四（10章）
一、填空题（每空1分，共32分）
1．在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次。
2．对n个元素的序列进行冒泡排序，最少的比较次数是 ，此时元素的排列情况 ，在 的情况下比较次数最多，其比较次数为 。
3．在对一组记录(50，40，95，20，15，70，60，45，80)进行直接选择排序时，第4次交换和选择后，未排序记录(即无序表)为 。
4．在对一组记录(50，40，95，20，15，70，60，45，80)进行堆排序时，根据初始记录构成初始堆后，最后4条记录为 。
5．在对一组记录(50，40，95，20，15，70，60，45，80)进行冒泡排序时，第一趟需进行相邻记录的交换的次数为 ，在整个排序过程中共需进行 趟才可完成。
6．在利用快速排序方法对一组记录(50，40，95，20，15，70，60，45，80)进行快速排序后递归调用使用的栈所能达到的最大深度为 ，其需递归调用的次数为 ，其中第二次递归调用是对 一组记录进行快速排序。
7．在归并排序中，若待排序记录的个数为20，则共需要进行 趟归并，在第三趟归并中，是把长度为 的有序表归并为长度为 的有序表。
8．在堆排序和快速排序中，若原始记录接近正序或反序，则选用 ，若原始记录无序，则最好选用 。
9．在直接插入和直接选择排序中，若初始数据基本有序，则选用 ，若初始数据基本反序，则选用 。
10．在堆排序，快速排序和归并排序中，若从节省存储空间考虑，则应首先选取 方法，其次选取 方法，最后选取 方法：若只从扑序结果的稳定性考虑，则应选择 方法；若只从平均情况下排序的速度来考虑，则选择 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 方法。
11．在内部排序中，平均比较次数最少的是 求附加的内存容量最大的是 ，排序时不稳定的有 ， ， ，
等几种方法
二、单项选择题：（每空2分，共40分）
1．从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中
的正确位置上，此方法称为（ ）。
A．归并排序 B．选择排序
C．交换排序 D．插入排序
2．从未排序序列中挑选元素，并将其放入己排序序列的一端，此方法称为（ ）。
A．归并排序 B．选择排序
C．交换排序 D．插入排序
3．依次将每两个相邻的有序表合并成一个有序表的排序方法叫做（ ）。
A．归并排序 B．选择排序
C．交换排序 D．插入排序
4．在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（ ）。
A．Shell排序 B．冒泡排序
C．直接插入排序 D．直接选择排序
5．在直接选择排序中，记录比较次数为（ ）数量级。
A．O(n) B．O(log2n)
C．O(n2) D．O(log2n)
6．一组记录的关键字为(45，80，55，40，42，85)，则利用堆排序的方法建立的初始堆为（ ）。
浙公网安备 33021202002483