班级学号姓名得分。
题目部分，(卷面共有45题，100分，各大题标有题量和总分)
一、判断正误(11小题，共11分)
1．即使对不含相同元素的同意输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序也一定相同。（
2．栈和队列都是限制存取点的线性结构。(
3．任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。(
4．己知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。(
5．有n个数存放在伊维数组h[1…n]中，在进行顺序查找时．这n个数的排列有序或无序其平均查找长度小同。(
6．二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。
7．用希尔(shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（
8．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。 （
9．完全二叉树就是满二叉树。（
10．在散列法中，一个可用散列函数必须保证绝对不产生冲突。（
11．快速排序是对起泡排序的一种改进。(
二、单项选择题(20小题，共42分)
1．在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，其修改指针的操作是___
a、 b、 c、 d、
2．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）链中结点数大于2，p不是第一个结点）
a、p^.llink^.rlink:
=p^.llink; p^.llink^.
rlink:=p^.rlink; dispose(p); b、dispose(p); p^.
llink^.rlink:=p^.
llink; p^.llink^,rlink:=p^.
rlink; c、p^.llink^.rlink:
=p^.llink; dispose(p); p^.llink^.
rlink:=p^.rlink; d、以上a，b，c都不对。
3．某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是。
a、 a，c，b，d b、 b, c，d，a c、 c, d，b, a d、 d, c，a，b
4．栈和队都是。
a、顺序存储的线性结构 b、 链式存储的非线性结构 c、 限制存取点的线性结构 d、 限制存取点的非线性结构。
5．数组的基本操作主要包括 。
a、 建立与删除 b、 索引与修改 c、 访问与修改 d、 访问与索引
6．下面说法不正确的是。
a、 广义表的表头总是一个广义表 b、 广义表的表尾总是一个广义表 c、 广义表难以用顺序存储结构 d、 广义表可以是一个多层次的结构。
7．设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是。
a、 a*b+c/(d*e)+(f-g) b、 (a*b+c)/(d*e)+(f-g) c、 (a*b+c)/(d*e+（f-g）) d、 a*b+c/d*e+f-g
8．深度为６（根据的层次为１）的二叉树至多有( )个结点。
a、 64 b、 63 c、 31 d、 32
9．下面不正确的说法是。
(1) 在aoe网中．减小任一关键活动上的权值后，整个工期也就相应减小。
(2)aoe一网工程工期为关键活动上的权之和；
3)在关键活路径上的活动都是关键活动，而关键活动也必在关键路径上，a、(1) b、(2) c、(3) d、(1)、(2)
10．下列说法中不正确的是。
a、无向图中的极大连通子图称为连通分量。
b、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。
c、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点。
d、有向图的遍历不可采用广度优先搜索方法。
11．设有一个按各元素的值排好序的线性表且长度大于2，对给定的值k，分别用顺序查找法和二分法查找一个与k相等的元素，比较次数分别s 和b；在查找不成功的情况下，正确的s 和b的数量关系是___
a、 总有s=b b、总有s>b c、总有s12．设散列表的长m=14，散列函数为h(k)=k％11，表中已有4个记录(如图所示)，如果采用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是
a、 8 b、 3 c、 5 d、 9
13．归并排序中，归并的趟数是。
a、o（n） b、o(logn) c、o(nlogn) d、o(n*n)
14．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。
a、 冒泡 b、 希尔 c、 快速 d、 堆
15．快速排序在最坏情况下时间复杂度是，比（ ）的性能差。
a、堆排序 b、起泡排序 c、选择排序。
16．若对一个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂性为。
a、o(l) b、 c、 d、
17．数据表示是指数据。
a、 书写在纸上。
b、 从机外转为机内。
c、 磁盘中的数据。
d、 光盘中的数据
18．以下数据结构中，哪一个是线性结构？
a、广义表 b、 二叉树 c、稀疏矩阵 d、 串。
19．某二叉树的前序和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
a、空或只有一个结点 b、高度等于其结点数 c、任一结点无左孩子 d、任一结点无右孩子。
20．在10阶b-树中根结点所包含的关键码个数最多为（ ）最少为。
a、1 b、2 c、9 d、10
三、填空题(14小题，共47分)
1．在一个不带头结点单链表中，在表头插入或删除与在其他位置插入或删除其操作过程。
2．根据需要，用适当的语句填入下面算法的___中：
问题：设有n件物品，重量分别为w1,w2,w3,…,wn和一个能装载总重量为t的背包。能否从n件物品中选择若干件恰好使它们的重量之和等于t。
若能，则背包问题有解，否则无解。解此问题的算法如下：
function kanp_stack(var stack,w:array[1..n] of real; var top:
integer; t:real):boolean;
begin
top:=0; i:=1;
while (1)__and(2)__do
[if (3)__or (4)__and (i 济南大学2012 2013学年第一学期课程考试试卷 a卷 课程数据结构授课教师。考试时间 201 年月日考试班级。学号姓名。一 选择题 每小题2分，共40分 1 对顺序存储的线性表，设长度为n，在任何位置上插入或删除操作都是等概率的，删除一个元素时平均要移动表中的 个元素。a b cd n 2设一条... 专业年级学号。姓名成绩。一 选择题 本题共25分 1.1分 简单队列对数据处理的方式是。a.先来先服务 b.后来先服务。c.先来后服务 d.以上均不对。2.2分 下面哪些问题的求解应用了栈。a 函数调用时保存函数的参数 局部变量等。b 检查括号匹配。c 图的宽度优先搜索。d 基于深度优先搜索的图的拓... 试卷编号拟题教研室 或教师 签名乐晓波教研室主任签名。长沙理工大学考试试卷 a卷 课程名称 含档次 数据结构a 课程代号 0812002615 课程编号 002131 专业计算机相关专业层次 本 专 本科考试方式 开 闭卷 闭卷 一 应用题 2小题，共8分 设有一个栈，元素进栈的次序为 a，b，c，...2019试卷数据结构A卷
数据结构2024年A卷
数据结构A期末试卷 A卷