《数据结构》试题库1
班级 姓名 学号 题号 得分 一 二 三 四 五 总得分 评卷人 审核人 一、填空题[每空1分，共10分]
1、线性表的顺序存储结构中元素的存储位置是“顺序”的，但只要确定了存储线性表的起始
位置，线性表中任一数据元素都可以___________存取；线性表的链式存储结构中元素的存储位置是“随机”的，但线性表中任一数据元素只能___________存取。
2、数据结构讨论的算法中哪一个算法的时间复杂度为O(c)____?哪一个算法的时间复杂度为
O(logn) ____? 哪一个算法的时间复杂度为O(n)____? 哪一个算法的时间复杂度为
2
O(nlogn)____? 哪一个算法的时间复杂度为O(n)____? 哪一个算法的时间复杂度为
n
O(2)____?。
3、在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行
下列语句：
s->next=p；s->prior=________；p->prior=s；________=s； 二、单项选择题[每题2分，共20分]
1、设一个栈的输入序列为A,B,C,D，则借助一个栈所得到的输出序列不可能是_____。
A、A,B,C,D B、D,C,B,A C、A,C,B,D D、D,A,B,C 2、对矩阵压缩存储是为了_____。
A、方便运算 B、节省空间 C、方便存储 D、提高运算速度 3、具有10个叶结点的二叉树中有_____个度为2的结点。
A、8 B、9 C、10 D、ll
4、在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是( )。
A、堆排序 B、希尔排序 C、冒泡排序 D、快速排序 5、判定一个循环队列Q（元素最多为m个）为满的条件是_____。
A、Q.front=Q.rear B、Q.front≠Q.rear
C、Q.front=(Q.rear+1) mod m D、Q.front≠(Q.rear+1) mod m 6、邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的( )。
A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 7、队列操作的原则是_______。
A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除
8、设一棵二叉树，其叶子结点分别带权10，12，4，7，5，18，2则其带权路径长度最小为( )。
第 1 页/共 4 页
A、120 B、130 C、140 D、150 9、下列哪一种图的邻接矩阵是对称矩阵( )。
A、有向图 B、无向图 C、AOV网 D、AOE网 10、带头结点的单链表Head为空的判定条件是( )。
A、Head=NIL B、Head^.Next=NIL C、Head^.Next=Head D、Head=Head 三、应用题[共40分]
1、[10分]给出利用栈和队列判断任意输入但以’@’结束的字符串是否回文的算法思想。 2、[15分]某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是
dgbaechf。画出该二叉树，并将其后序线索化。 3、[15分]设有一有向图G如下图所示：
1 6 2 5 3 4 (1)、画出图G的邻接表存储表示（邻接顶点要请以顶点序号递增序排列，以使答案唯一）。 (2)、写出从顶点1开始按深度优先遍历G得到的顶点序列。 四、算法设计题[每题15分，共30分]
1、设计一个算法，判断无向图G是否连通。若连通则返回1；否则返回0。 2、有一种简单的排序算法，叫做计数排序(count sorting)。这种排序算法对一个待排序的表
(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的计数值为c,那么，这个记录在新的有序表中的合适的存放位置即为c（如c=0，则当前元素存放在新表的0号单元）。编程实现计数排序算法。
第 2 页/共 4 页