2017《数据结构》期末考试试题及答案.pdf

第 1 页 共 23 页2017数据结构期末考试试题及答案数据结构期末考试试题及答案1.2试题 1 答案.7数据结构期末考试试题及答案2.9试题 2 答案.14 数据结构期末考试试题及答案3.16 试题 3 答案.21 第 2 页 共 23 页数据结构期末考试试题及答案1 一、单选题（每题2 分，共 20 分）1.栈和队列的共同特点是()。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时().A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？()A.队列B.栈C.线性表D.二叉树4.设有一个二维数组Amn，假设A00 存放位置在644(10)，A22 存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用 10 进制表示。A688 B678 C692 D696 5.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第 k 层的结点数最多为().A2k-1 B.2K+1 C.2K-1 D.2k-1 7.若有 18 个元素的有序表存放在一维数组A19 中，第一个元素放 A1 中，现进行二分查找，则查找A3的比较序列的下标依次为()A.1，2，3 B.9，5，2，3 C.9，5，3 D.9，4，2，3 8.对 n 个记录的文件进行快速排序，所需要的辅助存储空间大致为A.O（1）B.O（n）C.O（1og2n）D.O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储第 3 页 共 23 页时，若选用 H（K）=K%9 作为散列函数，则散列地址为1 的元素有（）个，A1 B2 C3 D4 10.设有 6 个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5 B.6 C.7 D.8 二、填空题（每空 1 分，共 26分）1.通常从四个方面评价算法的质量：_ _、_ _、_和_。2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_。3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为_个，树的深度为_，树的度为_。4.后缀算式 9 2 3+-10 2/-的值为 _。中缀算式（3+4X）-2Y/3对应的后缀算式为 _。5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有_个指针域，其中有 _个指针域是存放了地址，有_ 个指针是空指针。6.对于一个具有 n 个顶点和 e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_n_个和_个。7.AOV 网是一种 _ 的图。8.在一个具有n 个顶点的无向完全图中，包含有_条边，在一个具有 n 个顶点的有向完全图中，包含有_条边。9.假定一个线性表为(12,23,74,55,63,40)，若按 Key%4 条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为 _、_、_ 和_。10.向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 _。11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。第 4 页 共 23 页12.在快速排序、堆排序、归并排序中，_排序是稳定的。三、运算题（每题6 分，共 24 分）1.在如下数组 A 中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2.请画出图 10 的邻接矩阵和邻接表。3.已知一个图的顶点集V 和边集 E 分别为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 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;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4.画出向小根堆中加入数据4,2,5,8,3 时，每加入一个数据后堆的变化。四、阅读算法（每题7 分，共 14分）1.LinkList mynote(LinkList L)/L 是不带头结点的单链表的头指针if(L&L-next)q=L；L=Lnext；p=L；S1：while(pnext)p=pnext；S2：pnext=q；qnext=NULL；return L；图 10 第 5 页 共 23 页 请回答下列问题：1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,an,a1）（1）说明语句 S1的功能；（2）说明语句组 S2的功能；（3）设链表表示的线性表为（a1,a2,an）,写出算法执行后的返回值所表示的线性表。2.void ABC(BTNode*BT)if BT ABC(BT-left);ABC(BT-right);coutdatadata)item=BST-data;/查找成功return _;else if(itemdata)return Find(_,item);else return Find(_,item);第 6 页 共 23 页/if 六、编写算法（共 8 分）统计出单链表 HL 中结点的值等于给定值X 的结点数。int CountX(LNode*HL,ElemType x)第 7 页 共 23 页试题 1 答案一、单选题（每题 2 分，共 20 分）1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、填空题（每空 1 分，共 26 分）1.正确性易读性强壮性高效率2.O(n)3.9 3 3 4.-1 3 4 X*+2 Y*3/-5.2n n-1 n+1 6.e 2e 7.有向无回路8.n(n-1)/2 n(n-1)9.（12，40）（）（74）（23,55，63）10.增加 1 11.O(log2n)O(nlog2n)12.归并三、运算题（每题 6 分，共 24 分）1.线性表为：（78，50，40，60，34，90）2.邻接矩阵：0111010101110111010101110邻接表如图 11 所示：图 11 3.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 4.见图 12 第 8 页 共 23 页5.4.画出向小根堆中加入数据4,2,5,8,3 时，每加入一个数据后堆的变化。6.图 12 四、阅读算法（每题 7 分，共 14 分）3.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,an,a1）4.递归地后序遍历链式存储的二叉树。五、算法填空（每空 2 分，共 8 分）true BST-left BST-right 六、编写算法（8 分）int CountX(LNode*HL,ElemType x)int i=0;LNode*p=HL;/i为计数器while(p!=NULL)if(P-data=x)i+;p=p-next;/while,出循环时 i 中的值即为 x 结点个数return i;/CountX 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 第 9 页 共 23 页数据结构期末考试试题及答案2 一、单选题（每小题 2 分，共 8 分）1、在一个长度为 n 的顺序线性表中顺序查找值为x 的元素时，查找成功时的平均查找长度（即x 与元素的平均比较次数，假定查找每个元素的概率都相等）为()。A n B n/2 C(n+1)/2 D(n-1)/2 2、在一个单链表中,若 q 所指结点是 p所指结点的前驱结点,若在 q与 p 之间插入一个 s所指的结点,则执行()。A slink=plink;plink=s;B plink=s;slink=q;C plink=slink;slink=p;D q link=s;slink=p;3、栈的插入和删除操作在（）进行。A 栈顶B 栈底C 任意位置D 指定位置4、由权值分别为 11，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A 24 B 71 C 48 D 53 二、填空题（每空 1 分，共 32 分）1、数据的逻辑结构被分为 _、_、_和_四种。2、一种抽象数据类型包括_ 和_ 两个部分。3、在下面的数组a 中链接存储着一个线性表，表头指针为ao.next，则该线性表为_。a 0 1 2 3 4 5 6 7 8 data next 4、在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中，判 断 链 表 为 空 的 条 件 分 别 为 _和60 56 42 38 74 25 4 3 7 6 2 0 1 第 10 页 共 23 页_。5、用具有 n 个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的_，该循环队列的最大长度为_。6、当 堆 栈 采 用 顺 序 存 储 结 构 时，栈 顶 元 素 的 值 可 用 表示；当堆栈采用链接存储结构时，栈顶元素的值可用 _ 表示。7、一棵高度为5 的二叉树中最少含有 _个结点，最多含有_个结点；一棵高度为 5 的理想平衡树中，最少含有 _个结点，最多含有 _个结点。8、在图的邻接表中，每个结点被称为_，通常它包含三 个 域：一 是 _；二 是 _；三 是_。9、在一个索引文件的索引表中，每个索引项包含对应记录的_和_ 两项数据。10、假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J），则树中所含的结点数为_个，树的深度为_,树的度为 _,结点 H 的双亲结点为 _,孩子结点为 _。11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂 度 为 _,整 个 堆 排 序 过 程 的 时 间 复 杂 度 为_。12、在对 m 阶的 B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于_个，则必须把它分裂为_个结点。三、运算题（每小题 6 分，共 24分）1、已知一组记录的排序码为（46，79，56，38，40，80,95，24），写出对其进行快速排序的每一次划分结果。2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），第 11 页 共 23 页设散列表为 HT0.12，散列函数为 H（key）=key%13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是 EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。4、已知一个图的顶点集V 各边集 G 如下：V=0，1，2，3，4，5，6，7，8，9；E=（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）当它用邻接矩阵表示和邻接表表示时，分别写出从顶点 V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。四、阅读算法，回答问题（每小题8 分，共 16 分）1、假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 1，请写出输出结果。#include#include consst int stackmaxsize=30;typedef int elemtype;struct stack elemtype stack stackmaxsize;int top;图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时第 12 页 共 23 页;#include“stack.h”Void main()stack a;initstack(a);int x;cin x;while(x!=-1)push(a,x);cin x;while(!stackempty(a)cout pop(a)”;cout end1;该算法的输出结果为：_.2、阅读以下二叉树操作算法，指出该算法的功能。Template void BinTree ：unknown(BinTreeNode*t)BinTreeNode*p=t,*temp;if(p!=NULL)temp=pleftchild;pleftchild=prightchild;prightchild=temp;unknown(pleftchild);undnown(prightchild);该算法的功能是：_ 第 13 页 共 23 页五、算法填空，在画有横线的地方填写合适的内容（10 分）对顺序存储的有序表进行二分查找的递归算法。int Binsch(ElemType A,int low,int high,KeyType K)if(low=high)int mid=1 if(K=A mid.key)return mid;else if(K=0；i-)for(j=0；jnext;p-next=Q.front-next;（B）、p=Q.front-next;Q.front-next=p-next;（C）、p=Q.rear-next;p-next=Q.rear-next;（D）、p=Q-next;Q-next=p-next;9 Huffman 树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10线索二叉链表是利用（）域存储后继结点的地址。（A）、lchild （B）、data （C）、rchild （D）、root b c d a front 第 17 页 共 23 页二、填空题1逻 辑 结 构 决 定 了 算 法 的，而 存 储 结 构 决 定 了 算 法的。2栈和队列都是一种的线性表，栈的插入和删除只能在进行。3线性表（a1,a2,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为4已知一双向链表如下(指针域名为next 和 prior)：q p 现 将p所 指 的 结 点 插 入 到x和y结 点 之 间，其 操 作 步 骤为：；5n 个结点无向完全图的的边数为，n个结点的生成树的边数为。6已知一有向无环图如下：任意写出二种拓扑排序序列：、。7已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。三、应用题1设散列函数H(k)=k%13,设关键字系列为22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。(6 分)(1)构造 HASH 表。(2)分别求查找成功和不成功时的平均查找长度。2 给定表（19,14,22,15,20,21,56,10）.（8 分）（1）按元素在表中的次序，建立一棵二叉排序树（2）对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。x ye B ACDFEG第 18 页 共 23 页（3）画出对(2)中的遍历序列进行折半查找过程的判定树。3 已知二个稀疏矩阵A和 B的压缩存储三元组表如下：A B i j V i j V 1 3-5 2 5 2 2 4 6 3 3 7 2 5 2 4 1 3 4 2-1 5 2-9 5 2 9 5 5 8 写出 A-B 压缩存储的三元组表。（5 分）4 已知一维数组中的数据为（18,12,25,53,18）,试写出插入排序（升序）过程。并指出具有n 个元素的插入排序的时间复杂度是多少？(5 分)5 已知一网络的邻接矩阵如下，求从顶点A 开始的最小生成树。(8 分，要有过程)A B C D E F（1）求从顶点A开始的最小生成树。（2）分别画出以A为起点的DFS生成树和BFS生成树。6已知数据六个字母及在通信中出现频率如下表：A B C D E F 0.15 0.15 0.1 0.1 0.2 0.3 把这些字母和频率作为叶子结点及权值，完成如下工作(7 分，要有过程)。（1）画出对应的Huffman 树。（2）计算带权路径长度WPL。（3）求 A、B、C、D、E、F 的 Huffman 编码。7 已知有如下的有向网：64266346751275356156FEDCBA第 19 页 共 23 页求顶点 A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6 分）三、设计题（30 分，每题 10 分,用 C语言写出算法，做在答题纸上）1 已知线性表（a1,a2,an）以顺序存储结构为存储结构，其类型定义如下：#define LIST_INIT_SIZE 100/顺序表初始分配容量typedef struct Elemtype*elem;/顺序存储空间基址int length;/当前长度（存储元素个数）SqList;设计一个算法，删除其元素值为x 的结点（假若x 是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：S tatus ListDelete(Sqlist&L,Elemtype x)2设顺序栈如左图所示。其中结点定义如下：top typedef struct Elemtype*base;/栈底指针Elemtype*top;/栈顶指针Stack;设计算法，将栈顶元素出栈并存入e中base 3设二叉链树的类型定义如下：typedef int Elemtype;typedef struct node Elemtype data;struct node*lchild,*rchild;BinNode,*BinTree;试写出求该二叉树叶子结点数的算法:S tatus CountLeaves(BinTree&root,int&n)2 5 3 6 4 10 6 1 2 A B C D E ana2a1第 20 页 共 23 页/n is the number of leaves