《2022年数据结构试题文件 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构试题文件 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、山 东 农 业 大 学 课 程 考 试 专 用注：考试期间试卷不允许拆开。第 1 页 共 7 页200 x-200 x学年第 x 学期数据结构试题（x卷）课程代码考试方式闭卷考试时长 100 分钟姓名学号教学班号专业级班题 号一二三四五六七八合计满 分20103040得 分阅卷人一、选择题（201 分）1.算法的计算量的大小称为计算的（）。A效率B.复杂性C.现实性D.难度答案：_B_2.以下数据结构中，（）是非线性数据结构A树B字符串C队D栈答案：_A_3.链表不具有的特点是（）A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比答案：_B_4.对于
2、顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。AO(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)答案：_C_5.在单链表指针为p 的结点之后插入指针为s 的结点，正确的操作是：（）。Ap-next=s;s-next=p-next;B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next;D p-next=s-next;p-next=s;答案：_B_6.对于队列操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序答案：_A_7.若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第
3、j 个输出元素是（）。A.i-j-1B.i-jC.j-i+1D.不确定的得分名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -山 东 农 业 大 学 课 程 考 试 专 用注：考试期间试卷不允许拆开。第 2 页 共 7 页答案：_D_8.若用一个大小为6 的数组来实现循环队列，且当前rear和 front的值分别为0和 3，当从队列中删除一个元素，再加入两个元素后，rear和 front的值分别为多少？()A.1 和 5B.2 和 4C.4 和 2D.5 和 1答案：_B_9.串ababaaababaa 的 next 数组为（）。【中山大学1999 一、7】A012345
4、678999B012121111212C011234223456D0123012322345答案：_C_10.在下述结论中，正确的是（）只有一个结点的二叉树的度为0;二叉树的度为2；二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。ABCD答案：_C_11.有 n 个叶子的哈夫曼树的结点总数为（）。A不确定B2nC2n+1D2n-1答案：_D_12.深度为 h 的满 m叉树的第 k 层有（）个结点。(1=k=h).Amk-1Bmk-1Cmh-1Dmh-1答案：_D_13.树的后根遍历序列等同于该树对应的二叉树的().【A.先序序列B.中序序列C.后序序列答
5、案：_B_14.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是：A、EB、FC、GD、H答案：_C_15.若 X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x 的前驱为()A.X 的双亲B.X 的右子树中最左的结点C.X 的左子树中最右结点D.X 的左子树中最右叶结点答案：_C_16.n 个结点的线索二叉树上含有的线索数为（）.A2nBnlCnlDn答案：_C_17.在有向图G的拓扑序列中，若顶点Vi 在顶点 Vj 之前，则下列情形不可能出现的是（）。AG 中有弧 BG 中有一条从Vi 到 Vj 的路径CG 中没有弧 DG
6、中有一条从Vj 到 Vi 的路径答案：_D_18.下列排序方法中，哪一个是稳定的排序方法？（）。A直接选择排序B折半插入排序C希尔排序D快速排序答案：_B_名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -山 东 农 业 大 学 课 程 考 试 专 用注：考试期间试卷不允许拆开。第 3 页 共 7 页19.对序列 15，9，7，8，20，-1，4，用希尔排序方法排序，经一趟后序列变为15，-l，4，8，20，9，7则该次采用的增量是()A.lB.4C.3D.2答案：_B_20.适用于折半查找的表的存储方式及元素排列要求为()A链接方式存储，元素无序B链接方式存储，元素有序
7、C顺序方式存储，元素无序D顺序方式存储，元素有序答案：_D_二、判断题(在括号内填入或者，101 分)1.排序算法中的比较次数与初始元素序列的排列无关。（）2.在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。()3.顺序查找法适用于存储结构为顺序或链接存储的线性表。()4.哈希表的结点中只包含数据元素自身的信息，不包含任何指针。()5.算法可以用不同的语言描述，如果用C 语言或 PASCAL 语言等高级语言来描述，则算法实际上就是程序了。()6.线性表的特点是每个元素都有一个前驱和一个后继。()7.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。()8.完
8、全二叉树一定存在度为1 的结点。()9.一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。()10.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。()三、三、应用题（共30分）1.设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：A B D F C E G H中序遍历序列：B F D A G E H C（1）画出这棵二叉树。（4 分）（2）将这棵二叉树转换成对应的树（或森林）。（3 分）得分得分名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -山 东 农 业 大 学 课 程 考 试 专 用注：考试期间试卷不允许拆开。第 4 页 共 7 页2.已
9、知一图如下图所示：（1）写出该图的邻接矩阵；（2分）（2）写出以v1 为起点的广度优先遍历序列及生成树（3分）；（3）以 v1 为源点,以 v8 为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；（5 分）（4）求 V1结点到各点的最短距离。（5 分）（3）关键路径有3 条，长 17。（各事件允许发生的最早时间和最晚时间略）V1-V2-V4-V6-V8，V1-V3-V5-V7-V8，V1-V2-V4-V6-V5-V7-V8（4）V1 结点到其它各结点的最短距离为：2，3，6，12，10，15，16。V1V2V4V6V8V7V5V331032546123名师资料总结-精品资料欢迎
10、下载-名师精心整理-第 4 页，共 7 页 -山 东 农 业 大 学 课 程 考 试 专 用注：考试期间试卷不允许拆开。第 5 页 共 7 页3.输入关键字序列10，18，3，8，12，2，7，3 建立一棵二叉排序树（8 分）名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -山 东 农 业 大 学 课 程 考 试 专 用注：考试期间试卷不允许拆开。第 6 页 共 7 页四、算法设计题（根据要求，用c语言写出能够执行的算法，410分）1.删除单链表中第i 个结点#includetypedefstructnode datatypedata;structnode*link;JD
11、;Voiddel_link(intI,JD*head)JD*p,*q;Intj=1;P=q=head;While(p!=NULL&jlink;j+;if(p)q-link=p-link;free(p);elseprintf(Couldnotdeletei);Voidmain()inti;JD*head;Scanf(“%d”,&i);Del_link(I,head);2.设计图的深度优先遍历算法typedefstructnodeintadjvex;structnode*next;JD;typedefstructtnodeintvexdata;/存放顶点信息structnode*firstarc;
12、/指示第一个邻接点TD;voidtraver(TDg,intn)inti;staticintvisitedM;for(i=1;i=n;i+)visitedi=0;for(i=1;iadjvex;if(visitedi=0)dfs(g,i,visited);w=w-next;得分名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -山 东 农 业 大 学 课 程 考 试 专 用注：考试期间试卷不允许拆开。第 7 页 共 7 页3.设计希尔排序算法voidshellsort(intr,intn,intdT)inti,j,k;intx;k=0;while(kT)for(i=dk+1
13、;i0)&(xrj)rj+dk=rj;j=j-dk;rj+dk=x;k+;4.统计二叉树中只有一个孩子的结点的个数#include#includetypedefstructnodechar data;structnode*lchild,*rchild;JD;voidcount(JD*bt,int*count)if(bt!=NULL)if(bt-lchild=NULL)&(bt-rchild!=NULL)|(bt-lchild!=NULL)&(bt-rchild=NULL)(*count)+;return;count(bt-lchild,count);count(bt-rchild,count);名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -