数据结构和算法试题。
一、单项选择题（本大题共25小题，每小题2分，共50分）
1.下列四种基本的逻辑结构中，数据元素之间关系属于一对一的是 (b )
a 集合 b 线性结构 c 树形结构 d 图状结构。
2. 数据结构ds(data struct)可以被形式地定义为ds=（d，r），其中d是 b 的有限集合，r是d上的 d 有限集合。
① a．算法 ｂ．数据元素 ｃ．数据操作 ｄ．数据对象。
② a．操作 ｂ．映象 ｃ．存储 ｄ．关系。
3．求单链表中当前结点的后继和前驱的时间复杂度分别是（ b ）
a．o（n）和o（1）b．o（1）和o（1）
c．o（1）和o（n）d．o(n)和o（n）
4．非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（ a ）
a．rear->next= =headb．rear->next->next= =head
c．head->next= =reard．head->next->next= =rear
5．计算机算法指的是解决问题的步骤序列，它必须具备（ b ） 这三个主要特性。
a．可行性、正确性、可读性。
b．可行性、确定性、有穷性。
c．确定性、有穷性、稳定性。
d．易读性、健壮性、安全性。
6．在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的（a ）
a．最小代价生成树b．哈夫曼树。
c．关键路径 d．最短路径。
7.一个栈的输入序列是12345,则栈的不可能的输出序列是( c )
a．54321b．45321
c．43512d．12345
8．下面关于算法说法错误的是（c ）。
a．算法最终必须由计算机程序实现。
b．为解决某问题的算法同为该问题编写的程序含义是相同的。
c．算法的可行性是指指令不能有二义性。
d．以上几个都是错误的。
9．除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ c ）
a．1/2倍b．1倍。
c．2倍 d．3倍。
10．对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（ d ）
a．o（n）b．o(e)
c．o(n+e)d．o(n*n)
11．如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ b ）
a．深度优先搜索算法 b．广度优先搜索算法。
c．求最小生成树的prim算法；d．拓扑排序算法
12．连续存储设计时，存储单元的地址（a ）。
a．一定连续 b．一定不连续 c．不一定连续 d．部分连续，部分不连续。
13．下述哪一条是顺序存储结构的优点？（ a ）
a．存储密度大 b．插入运算方便。
c．删除运算方便 d．可方便地用于各种逻辑结构的存储表示。
14．算法的时间复杂度取决于（ c ）。
a．问题的规模 b．待处理数据的初态c．a和b d．无。
15．栈和队列的共同点是__d__。
a. 都是先进后出 b. 都是先进先出。
c. 只允许在端点处插入和删除元素 d. 都是线性结构。
16．对于图的遍历，通常有两种方法，（ d ）类似于树的层次遍历，（ c ）类似于树的先根遍历。
a．层次遍历 b．邻接遍历。
c．深度优先遍历d．广度优先遍历。
17 已知二叉树结点的前序序列和中序序列分别为： 前序序列： 18 14 7 3 11 22 35 27, 中序序列：
3 7 11 14 18 22 27 35 , 二叉树的后序序列为( d )
a．3 7 11 14 27 35 22 18 b．3 7 11 27 14 35 22 18
c．3 7 11 27 14 22 35 18 d． 3 11 7 14 27 35 22 18
18 由n个结点构成的所有二叉树中路径长度最短的二叉树是(a )
a．最小代价生成树b．哈夫曼树。
c．二叉排序树 d．最小带权树
19 一棵深度为4的二叉树的第3层最多有( b )个结点，整个二叉树最多有( d )个结点。
a．3 b．4
c．16 d．15
20 一棵二叉树，叶子结点的数目是6，其度数为2的结点数为( c )
a．3 b．4
c．5 d．6
21、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为(c )。1≤i≤n+1)
a．o(0) b．o(1) d．o(n2)
22. 数据元素是数据的基本单位，其内 ( c) 数据项。
a 只能包括一个 b 不包含。
c 可以包含多个 d 必须包含多个值的链点。
23．设无向图的顶点个数为n，则该图最多有（ b ）条边。
a．n-1 b．n(n-1)/2 c． n(n+1)/2 d．0
24、对二叉排序树进行( a )遍历，最容易找到该二叉树的根结点排序序列。
a. 前序 b．中序 c．后序 d．按层次
25、算法的时间复杂度取决于 d
a. 问题的规模b .待处理数据的初态
c. 待处理数据的顺序 d. a 和 b
二、填空题（本大题共10小题，每小题1.5分，共15分）
请在每小题的空格中填上正确答案。错填、不填均无分。
1．抽象数据类型通常可分为 __数据元素关系基本操作___组成。
2．队列是按___先进先出___的原则进行的。
3．图的遍历方式有 __深度优先遍历和 __广度优先遍历两种方式。
4．图的存储表示方式有__邻接矩阵邻接表___邻接多重表___和___十字链表___四种。
5．具有n个结点的完全二叉树的深度为___log 2 （n+1）-1___
6．结点数为20的二叉树可能达到的最大高度为 __19___
7．树的遍历方法有 _前序 __和___中序___和___后序 _。
8．插入排序分为 __直接插入___和___希尔___排序。
9．交换排序分为___冒泡排序和 __快速排序排序 。
10。典型的最小生成树的算法是 __克鲁斯卡尔算法和___普利姆算法___算法。
三 ，判断题（共5题，每题1分）
1. 图是线性数据结构。( f )
2． 树的先序遍历是先遍历根，再左孩子 ，再遍历右孩子。（ t ）
3． 归并排序的思想是先分组，然后将其相邻两个有序自序列依次排序为一个有序序列 ( t )
4． 队列是先进后出的数据结构。（ f ）
5. 带有权的图称为网络。（ t ）
四 、简答题（本大题共4小题，每小题5分，共20分）
1. 请简单阐述树的遍历方式都有哪些，写出常用的三种遍历方式 ，并说出他们的思想。
2.请写出栈的抽象数据类型。
3.根据二叉树的定义，具有a、b、c三个结点的二叉树有5种不同的形态，请将它们分别画出。(本小题5分)
4. 请简单阐述冒泡排序的思想。
五编成题（10分）
1. 用栈进行单词逆序，比如有一个字母序列为 abcdefg ，要求使用栈的思想编程并最后输出gfedcba。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...