北航《算法与数据结构》复习题二。
一、单选题（本大题共20小题，每小题1.5分，共30分）
1、向堆中插入一个元素的时间复杂度为（ a ）。
a．o(log2n)
b．o(n)
c．o(1)
d．o(nlog2n)
2、设无向图的顶点个数为n，则该图最多有（ b ）条边。
a．n-1b．n(n-1)/2
c．n(n+1)/2
d．03、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ b ）。
a．23b．51
c．53d．74
4、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ d ）存储方式最节省时间。
a．单链表。
b．双链表。
c．单向循环。
d．顺序表。
5、如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ d ）方法最快。
a．起泡排序。
b．快速排序。
c．简单选择排序。
d．堆排序。
6、在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（ b ）
a．real和rear->next->next
b．rear->next 和rear
c．rear->next->next和rear
d．rear和rear->next
7、当利用大小为n的一维数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（ b ）语句修改top指针。
a．top++
b．top--
c．top=0
d．top8、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（ b ）个元素。
a．n-ib．n-i+1
c．n-i-1
d．i9、指针的全部作用就是（ c ）
a．指向某常量。
b．指向某变量。
c．指向某结点。
d．存储某数据。
10、设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主的存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（ c ）。
a．13b．18
c．33d．40
11、堆排序在最坏情况下，其时间复杂性为（ a ）
a．o(nlog2n)
b．o(n2)
c．o(log2n2)
d．o(log2n)
12、设有广义表d(a,b,d),其深度为（ a ）。
a．∞b．3
c．2d．5
13、设矩阵a（aij ，l≤i,j≤ 10）的元素满足：
aij≠0(i≥j, l≤i, j≤ 10)
aij=0 (i现将a的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素a[9][5]的首址为（ d ）
a．2340
b．2336
c．2164
d．2160
14、下列选项中，（ c ）需要的附加存储开销最大。
a．快速排序。
b．堆排序。
c．归并排序。
d．插入排序。
15、设某数列各元素的顺序依次为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ b ）。
a．3，2，5，6，4，1
b．1，5，4，6，2，3
c．2，4，3，5，1，6
d．4，5，3，6，2，1
16、在索引顺序表中查找一个元素，可用的且最快的方法是（ c ）
a．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找。
b．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找。
c．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找。
d．用二分查找法确定元素所在块，再用二分查找法在相应块中查找。
17、基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（ b ）唯一确定。
a．非零元素。
b．三元组(i,j,aij)
c．aijd．i,j
18、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ d ）。
a．必需是联系的。
b．部分地址必须是连续的。
c．一定是不连续的。
d．连续不连续都可以。
19、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以什么为标准操作（ b ）
a．条件判断。
b．结点移动。
c．算术表达式。
d．赋值语句。
20、以下说法正确的是（ c ）
a．在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素。
b．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
c．顺序存储结构属于静态结构，链式结构属于动态结构。
d．顺序存储方式只能用于存储线性结构。
二、分析题（本大题共4小题每小题15分每小题20分，共70分）
21、已知一棵二叉树的中序遍历结果为dbheaficg，前序遍历结果为abdehcfig，请画出该二叉树。
22、试利用dijkstra算法求下图在从顶点a到其它顶点的最短距离，写出计算过程中各步状态。
23、编写一算法，求出一棵二叉树中所有结点数和叶子结点数。
假定分别用变参c1和c2统计所有结点数和叶子结点数，初值均为0。
24、已知序列，请给出采用快速排序法对该序列作升序排列时每一趟的结果。
去掉652 和462
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...