数据结构试题库1

《数据结构》试题库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 页

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4