数据结构期末试卷.docx

一、单项选择题（40分）.【单项选择题】（2分）
树的路径长度是从树根到每个结点的路径长度的（）。
A.平均值
O B.总和
C.最大值
D.最小值.【单项选择题】（2分）
某二叉树的先序序列和后续序列正好相反，那么该二叉树一定是（）。
A.任一结点无右孩子
O B.空或只有一个结点C.高度等于其结点数
D.任一结点无左孩子
1 .【单项选择题】（2分）
假设一棵完全二叉树的先序遍历序列为ABDHGECF,那么以下说法错误的选项是（）。
A.结点C的深度为3B.结点C是叶结点
C.结点C的高度为1
O D.结点c是A的右孩子结点.【单项选择题】（2分）
关于图的存储结构，（）是错误的。
A.假设一个有向图的邻接矩阵的对角线以下的元素为0,那么该图的拓扑序列必定存在；
O B.邻接表只用于有向图的存储，邻接矩阵适用于有向图和无向图；C.使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点数 有关，与边教无关；
D.存储无向图的邻接矩阵是对称的，故只需存储令B接矩阵的下三角局部.【单项选择题】（2分）
假设利用一个数组s口顺序存储一个栈，用top作为栈顶指针，top=-1表示栈空，当栈未满时，元素x进栈的 操作是（）。
A. s[++top]=x;
B. s[top—]=x;
C. s[-top]=x;
0 D. s[top++]=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. 8
O B. 9
C. 3
O D. 5.【单项选择题】（2分）
栈和队列具有相同的（）。
A.运算
O B.存储结构C.抽象数据类型
D.逻辑结构
6 .【单项选择题】（2分）
带头结点的双向循环链表L为空的判断条件是（）。
A. L->prior= = NULL&&L-next= = LL->prior= = L&&L->next= = NULL
B. L->prior=NULL&&L-next= = NULL
O D. L->prior= = L8i&L->next= = L
7 .【单项选择题】（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,40
O B. 20,35,55,40,75, 80,90,100C. 35,40,20,55,70,100,90,80
D. 100,35,40,90,80,55,20,75
13 .【单项选择题】（2分）在有n个叶结点的哈夫曼树中，非叶结点的总数是（）。
O A. 2nO B. 2n-1
OC. n-1O D. n
14 .【单项选择题】（2分）以下说法正确的选项是（）
A. f图的邻接矩阵表示不唯一，邻接表表示不唯一T图的邻接矩阵表示唯一，令隈表表示唯一
OC.一个图的邻接矩阵表示唯一，邻接表表示不唯一D.一个图的邻接矩阵表示不唯一，邻接表表示唯一
15 .【单项选择题】（2分）
在一棵二叉排序树上，查找关键字为35的结点，依次比拟的关键字可能有（）。
A. 46,28,18,36,35
O B. 46,36,18,28,35C. 18,36,28,46,35
D. 28,36,18,46,35
16 .【单项选择题】（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, 80
B. 30, 55, 63,
50, 38, 75, 80, 60
C.30, 38,
55, 63, 75, 80, 50, 60

D. 30, 38, 50, 60, 75, 80, 55, 63
19 .【单项选择题】(2分)卜面的程序段中，对x的赋值语句的频度为()。
for (k=1;k< = n;k++) for(j = 1;j< = n;j + +) x=x+1;A. O(n)
O B. 0(nA2)O C. O(2n)
1 D. O(log n)
20 .【单项选择题】(2分)
在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()。
A. 0(1)
0 B. 0(n)0(n2)
C. O(nlogn)
21 .【简答题】(6分)以关键字序列(230, 309, 675. 141, 927. 779, 594, 090, 338, 822)为例,分别写出执行以下排序 算法的各趟排序结束时，关键字序列的状态。
(1)归并排序：(2)基数排序有以下运行时间函数，分别写出相应的大。表示的运行时间。
(1) T(n)=2 人 6;
(2) T(n)=10n2+2n + 50;
(3) T(n) = n3+50n2+1;
(4) T(n)= 2T (n/2)+n/n>1;当 n = 1 时，T(n) = 1
23 .【简强】(5分)
将关键字｛9, 10, 14, 30, 11, 12, 7｝散列存储到散列表中，算列表的存储空间是一个下标从0开始的一 维数组，散列函数为H (Key) = (key*3) mod 7,处理冲突的法规范为线性再散列发，要求装填因子为0.7。
(1)请画出所构造的散列表。
(2)分别计算出等概率情况下，查找成功和查找不成功的平均查找长度。
24 .【简答题】(6分)
有一个带头结点的单链表L,设计一个函数使其元素递减有序。其中单链表结构定义如下：
struct Lnode｛int 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面所示的序列中哪些是合法的?