济南铁道职业技术学院 专升本辅导教材 数据结构
测试一下自己的水平
一、判断题 (每小题1分，共15分)
1.非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( ) 2.数组是一种没有插入与删除操作的线性结构。( )
3.稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。( ) 4.空串与由空格组成的串没有区别。( )
5.将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。( ) 6.深度为h的非空二叉树的第i层最多有2h-1 个结点。( ) 7.完全二叉树就是满二叉树。( )
8.已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。( ) 9.非空二叉排序树的任意一棵子树也是二叉排序树。( ) 10.有向图是一种非线性结构。( )
11.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( ) 12.AOE 网是一种带权的无环连通图。( )
13.折半查找方法适用于按值有序的线性链表的查找。( )
14.哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。( ) 15.选择排序过程中元素之间的比较次数与原始序列的状态无关。( ) 二、单项选择题 (每小题2分，共20分)
1.若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动_______个数据元素。( )
A.n-i B.n+i C.n-i-1 D.n-i+1
2.在单链表中，已知q指的结点是q指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行________。( ) A.link(s)←link(p)，link(p)←s B.link(q)←s，link(s)←p
C.link(p)←link(s)，link(s)←p D.link(p)←s，link(s)←q
3.在非空双向循环链表中由q所指的那个链结点前面插入一个由p指的链结点的动作对应的语句依次为:rlink(p)←q , llink(p)←llink(q) , llink←p, _________。（空白处为一条赋值语句） A.rlink(q)←p
B.rlink(llink(q)←p C.rlink(llink(p))←p D.rlink(rlink(p)←p
4.为了节省存储空间，将n阶对称矩阵A中包括主对角线元素在内的下三角部分的所有元素按 照行序为主序方式存放在一维数组B[1:n(n-1)/2]中，对任意下三角部分的元素aij(i≥j)在B 的下标k是 ( ) A.i(i-1)/2+j B.(i(i-1))/2+j C.i(i+1)/2+j B.(i(i+1))/2+j
5.某堆栈的输入序列为a,b,c,d,下面的四个序列中，__________不可能是它的输出序列。( )
第 1 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
A.a,c,b,d B.b,c,d,a C.d,c,a,b D.c,d,b,a
6.若非空队列采用链式存储结构，front和rear分别为队头元素与队列尾元素的指针，删除此时队列的一个元素的操作时依次执行p←front，_________________ ，call RET(P)。( )
A.front←link(rear) B.rear←link(p) C.rear←link(front) D.front←link(p)
7.中缀表达式A-(B+C)*D/E的后缀形式是_________________。( ) A.ABC+-D*E/ B.ABC+D*-E/ C.ABC+D-*E/ D.ABC+D*E/-
8.广大义表A=((),(a),(b,(c,d)))的长度为 ( ) A.2 B.3 C.4 D.5
9.在初始为空的杂凑表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT，SUN), 杂凑函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为[0:6]，采用线性再散列法处理冲突。插入后的杂凑表应该如________________所示。( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON
10.从未排序序列中选择一个元素，该元素将未排序序列分成前后两个部分，前一部分中所有元素都小于等于所选元素。后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。这种排序方法称为_____________排序法。( ) A.插入 B.谢尔 C.快速 D.堆积
三、填空题 (每小题2分，共20分)
1.已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)=___________________。
2.若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为______________。 3.具有n个结点的非空二叉排序树的最小深度为_______________。
第 2 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
4.深度为h且有_______________个结点的二叉树称为满二叉树。(设根结点处在第1层)。
5.二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G，D，H，其后序遍历序列为__________________。
6.已知序列(34，76，45，18，26，54，92，65，)，按照逐点插入法建立一棵二叉排序列树，该树的深度是__________________。
7.一个不带有权的有向图采用邻接矩阵存储方法，其邻接矩阵是一个__________________。
8.带权连通图G=
(v2,v3)8，(v2,v4)4，(v2,v5)4，(v3,v4)6，(v4,v5)2，(注：顶点偶对右边的数据为边上的权值)，G的最小生成树的权值之和为__________________ 。
9.在线性表中采用折半查找法（二分查找法）查找一个数据元素，线性表中元素应该按值有序，并且采用______________存储方法。
10.若对序列(49，38，65，97，76，13，27，50)采用选择排序法排序，则第三趟结束后序列的状态是___________________。
四、问题求解题 (每小题10分，共20分) 1.已知AOE网为G=(V,E)，其中, V ={v1,v2,v3,v4,v5,v6,v7},
E = {a1,a2,a3,a4,a5,a6,a7,a8,a9,a10},
a1:(v1,v2)3,a2:(v1,v3)2,a3:(v2,v4)1,a4:(v2,v5)8,a5:(v3,v4)3, a6:(v3,v6)7,a7:(v4,v5)4,a8:(v4,v6)2,a9:(v5,v7)9,a10:(v6,v7)6；
(注：顶点偶对的右括号下方的数据表示该边上的权值)。e[i]与l[i]分别表示活动a1的最早开始时间与最晚开始时间，请分别求出e[i]与l[i](1≤i≤10),填入下面的方格中。 e[1:10] l[1:10]
2.若对序列(76，38，65，13，97，27，50，49)采用堆积排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟的结果：
原始序列 76 38 65 13 97 27 50 49 第1趟结果 第2趟结果 第3趟结果 第4趟结果 第5趟结果 第6趟结果 第7趟结果 第8趟结果
五、算法题 (共25分)
1.已知长度为n的线性表A采用顺序存储结构，并且元素按值大小非递减排列，下面的算法删除线性表中多余的值相同的元素。请在算法的空白处填入适当内容，使之能够正常工作。(10分) procedure DEL (A,n) i←1
while ____________ do if (A[i]≠A[i+1] then i←i+1
第 3 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
else // 查找满足条件的元素 // [ for _________ do A[j-1]←A[j]
end // 删除第i+1个元素 (满足条件的元素) //
______________ ] // 修改线性表的长度 // end end
2.已知非空线性链表的链结点的构造为| date | link |，第一个链结点的指针为list，下面的算法删除链表的第i个结点（设i>0）。请在算法的空白处填入适当内容，使之能够正常工作。 (15分)
procedure DEL (list,i,item)
_____________ // 给变量q赋初值 // if (i=1) then
list←link(q) // 删除第一个链结点 // else
[ for j←1 to ______________ do r←q
q←link (q)
if _________ then
[ call ERROR (i 超过链表的长度！’) return ]
end if // r与q分别指向第i-1个与第i个链结点 // _____________ ] // 删除第i个链结点 // call RET(q) // 删除被删除链结点的空间 end
第一章 课堂练习
1．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)程序与算法没有区别。 ( )
(2)程序设计框图就是一种图形化的算法。 ( )
第 4 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
(3)采用程序设计语言编写的程序也是算法。 ( ) (4)一个算法可以没有输入，但不能没有输出。 ( )
(5)顺序存储结构通过数据元素的地址直接反映数据元素间的逻辑关系。 ( ) (6)链式存储结构通过指针间接地反映数据元素之间的逻辑关系。 ( ) (7)数据的存储结构通常只有顺序存储结构与链式存储结构两种。 ( ) (8)具有相同逻辑结构的数据可以采用不同的存储结构。 ( ) (9)逻辑结构不相同的数据应该采用不同的存储结构。 ( ) (10)算法分析的前提是算法的时空效率高， ( ) 1．2 填空题。
(1)“数据结构”课程研究的主要内容包括——、——和——三个方面。 (2)一般情况下，算法独立于具体的——，与具体的程序设计语言——。 (3)一个完整的算法应该具有——、——、——、——和——五个特性。 (4)数据的逻辑结构可以分为——和——两大类。
(5)除了顺序存储结构与链式存储结构之外，数据的存储结构通常还有——和散列结构。 (6)数据的逻辑结构是指——，而存储结构是指——。
(7)逻辑上相邻的数据元素在物理位置上也相邻是——存储结构的特点之一。 (8)为了实现随机访问，线性结构应该采用——存储结构。 (9)链式存储结构的主要优点是——。
(10)算法分析主要从——和——这两个方面对算法进行分析。
1．3 通常说数据结构是一个二元组(D，R)，其中D，R分别代表什么? 1．4 何谓数据的逻辑结构?何谓数据的存储结构?两者有何联系?
历年试题 一
1．在数据结构中，数据的逻辑结构可以分成（ ）
A．内部结构和外部结构 B．线性结构和非线性结构 C．紧凑结构和非紧揍结构 D．动态结构和静态结构 2．下列说法正确的是（ ）
A．数据是数据元素的基本单位
B．数据元素是数据项中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成 3．数据结构的基本任务是（ ）
A．逻辑结构和存储结构的设计 B．数据结构的运算实现 C．数据结构的评价与选择 D．数据结构的设计与实现
4．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）
2
A．O（1） B．O（n） C．O（nlog2n） D．O(n)
5.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 6、选出正确的表述
(1)顺序存储方式只能用于存储线性结构。
第 5 页 共 63 页