数据结构期末试卷.docx

一、单项选择题（40分）.【单项选择题】（2分）树的路径长度是从树根到每个结点的路径长度的（）。A.平均值O B.总和C.最大值D.最小值.【单项选择题】（2分）某二叉树的先序序列和后续序列正好相反，那么该二叉树一定是（）。A.任一结点无右孩子O B.空或只有一个结点C.高度等于其结点数D.任一结点无左孩子1 .【单项选择题】（2分）假设一棵完全二叉树的先序遍历序列为ABDHGECF,那么以下说法错误的选项是（）。A.结点C的深度为3B.结点C是叶结点C.结点C的高度为1O D.结点c是A的右孩子结点.【单项选择题】（2分）关于图的存储结构，（）是错误的。A.假设一个有向图的邻接矩阵的对角线以下的元素为0,那么该图的拓扑序列必定存在；O B.邻接表只用于有向图的存储，邻接矩阵适用于有向图和无向图；C.使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点数 有关，与边教无关；D.存储无向图的邻接矩阵是对称的，故只需存储令B接矩阵的下三角局部.【单项选择题】（2分）假设利用一个数组s口顺序存储一个栈，用top作为栈顶指针，top=-1表示栈空，当栈未满时，元素x进栈的 操作是（）。A. s+top=x;B. stop=x;C. s-top=x;0 D. stop+=x;4 .【单项选择题】（2分）以下排序方法中，哪一个是稳定的排序方法？（）O A.二分法插入排序B.直接选择排序C.希尔排序D.快速排序5 .【单项选择题】（2分）设散列表长m = 14,散列函数为h（key）=key mod 11,表中仅有4个结点h（15）=4, h（38）=5,h（61）=6, h（84）=7,假设采用线性探测法处理冲突，那么关键字49的结点地址为（）。O A. 8O B. 9C. 3O D. 5.【单项选择题】（2分）栈和队列具有相同的（）。A.运算O B.存储结构C.抽象数据类型D.逻辑结构6 .【单项选择题】（2分）带头结点的双向循环链表L为空的判断条件是（）。A. L-prior= = NULL&L-next= = LL-prior= = L&L-next= = NULLB. L-prior=NULL&L-next= = NULLO D. L-prior= = L8i&L-next= = L7 .【单项选择题】（2分）线性表的顺序存储结构是一种（）。O A.顺序存取的存储结构B.随机存取的存储结构C.索引存取的存储结构D.散列存取的存储结构8 .【单项选择题】（2分）折半查找与二叉排序树的时间性能（）。A.相同B.数量级都是O（n）O C.有时不同D.完全不同12 .【单项选择题】（2分）用直接插入排序方法对下面四个序列进行排序（从小到大），元素比拟次数最少的是（）。A. 90,75,80,55,20,35/00,40O B. 20,35,55,40,75, 80,90,100C. 35,40,20,55,70,100,90,80D. 100,35,40,90,80,55,20,7513 .【单项选择题】（2分）在有n个叶结点的哈夫曼树中，非叶结点的总数是（）。O A. 2nO B. 2n-1OC. n-1O D. n14 .【单项选择题】（2分）以下说法正确的选项是（）A. f图的邻接矩阵表示不唯一，邻接表表示不唯一T图的邻接矩阵表示唯一，令隈表表示唯一OC.一个图的邻接矩阵表示唯一，邻接表表示不唯一D.一个图的邻接矩阵表示不唯一，邻接表表示唯一15 .【单项选择题】（2分）在一棵二叉排序树上，查找关键字为35的结点，依次比拟的关键字可能有（）。A. 46,28,18,36,35O B. 46,36,18,28,35C. 18,36,28,46,35D. 28,36,18,46,3516 .【单项选择题】（2分）分别用以下序列构造二叉排序树，与用其他3个序列所构造的结果不同的是（）。A. 100/20/10,130,80,60,90 100,80,60,90/20/30/10 B. 100,80,90,60/ 20/10,130）O D. 100,60,80,90,120,110J 30 17 .【单项选择题】（2分）对序列15, 9, 7, 8, 20, -1, 4进行排序，进行一趟后数据的排列变为4, 9, -1, 8, 20, 7, 15）;那么 采用的是（）排序。OA.希尔B.快速C.冒泡D.选择18 .【单项选择题】（2分）设一组初始记录关键词为55, 63, 50, 38, 75, 80, 30, 60）,利用筛选法建立的初始小根堆为A. 30,A. 30,38,50, 55, 60, 63, 75, 80B. 30, 55, 63,50, 38, 75, 80, 60C.30, 38,55, 63, 75, 80, 50, 60D. 30, 38, 50, 60, 75, 80, 55, 6319 .【单项选择题】(2分)卜面的程序段中，对x的赋值语句的频度为()。for (k=1;k = n;k+) for(j = 1;j1;当 n = 1 时，T(n) = 123 .【简强】(5分)将关键字9, 10, 14, 30, 11, 12, 7散列存储到散列表中，算列表的存储空间是一个下标从0开始的一 维数组，散列函数为H (Key) = (key*3) mod 7,处理冲突的法规范为线性再散列发，要求装填因子为0.7。(1)请画出所构造的散列表。(2)分别计算出等概率情况下，查找成功和查找不成功的平均查找长度。24 .【简答题】(6分)有一个带头结点的单链表L,设计一个函数使其元素递减有序。其中单链表结构定义如下：struct Lnodeint data;struct Lnode *next;)；25 【简答题】(5分)将(for, case, while, class, protected, virtual, public, private, do, template, const Jf, int)中的关键字依 次插入初态为空的二叉排序树中，请画出所得到的树T,然后画出删去fo之后的二叉排序树设顶点表示村庄，有向边代表交通路线。假设要建立一家医院，试问建立在那个村庄能使得各村庄总体上的交编写函数判断以邻接矩阵存储的有向图是否存在一条从VI到Vj的路径。设计一种数据结构。假设一个族谱里储存着每个人的姓名，生日，死亡日期，孩子名字，孩 子个数，孩子个数最多不超过两个。要求用数据结构来存储族谱，使得将任何一个人的名字 输进去都能输出他的所有子孙后代的所有信息。【例3.3】假设以I和O分别表示进栈和出栈操作.栈的初态和终态均为空，进栈和出 栈的操作序列可表示为仅由I和O组成的序列.F面所示的序列中哪些是合法的?