当前位置:首页 >> 学科竞赛 >>

数据结构


1. 填写下面表格,对以下几种排序方法进行比较: 排序方法
选择排序

排序种类
直接选择排序 堆排序

平均时间复杂度
O(n2) O(nlog2n) O(n ) O(nlog2n) O(nlog2n) O(n ) O(nlog2n)
2 2

最坏情况
O(n2)

r />2

空间复杂度
O(1) O(1)

是否稳定

插入排序

直接接插入排序 拆半接插入排序 Shell 排序

O(n )

O(1) O(1) O(1)

冒泡排序 快速排序 归并排序 二叉树排序 红黑树 线性排序

(交换排序)

O(n ) O(n2) O(nlog2n)

2

O(1) O(1) O(n)

2-路归并排序

O(nlog2n)

计数排序 桶排序 基数排序

1.

具有 N 个元素的顺序存储的循环队列中,假定 front 和 rear 分别指向队头元素的前一位置和队尾元素 的位置,则判断队空的和队满的条件分别是 和 。求此队列中元素个数的计算公式 为: 。 单链表是 的链式存储结构,链栈和链队分别是 和 的链式存储结构。

2. 3.

线性表的顺序存储中,元素之间的逻辑关系是通过 之间的逻辑关系是通过 决定的。

决定的,在线性表的链接存储中,元素

4.

数据结构即数据的逻辑结构包括 、 、 三种类型,树型结构和图型结 构称为 。 一.选择题 1. 有一个 10 阶对称矩阵,采用压缩存储方式,以行序为主序存储,A[0][0]的地址为 1,则 A[7][4]的 地址为( ) A 13 B. 18 C. 33 D. 40 2. 线性表采用链表存储时其存储地址 。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 3. 下列叙述中错误的是 。 A. 串是一种特殊的线性表,其特殊性体现在数据元素是一个字符 B. 栈和队列是两种特殊的线性表,栈的特点是后进先出,队列的特点是先进先出。 C. 线性表的线性存储结构优于链式存储结构 D. 二维数组是其数据元素为线性表的线性表 4. 一棵二叉树的顺序存储结构如题图 4-1 所示,若中序遍历该二叉树,则遍历次序为 A. DBEGACFH B. ABDEGCFH C. DGEBHFCA D. ABCDEFGH A B C D E F G H
1

.

5. 设一棵二叉树的顺序存储结构如题图 4-2 所示,则该二叉树是
A.完全二叉树 C.深度为 4 的二叉树 1 2 3 B.满二叉树 D.深度为 3 的二叉树 4
题图 4-2

.

5

6

7

6. 设 T 是 Huffman 树,它具有 6 个树叶,且各树叶的权分别为 1,2,3,4,5,6。那么该树的非叶子结 点的权之和为 。 A.51 B.21 C.30 D.49 7.设有一无向图的邻接矩阵如下所示,则该图所有顶点的度之和为 。 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 A.8 B.9 C.10 D.11 11.对线性表进行折半(二分)查找时,要求线性表必须 。 A.以顺序方式存储 B.以顺序方式存储且数据元素有序 C.以链表方式存储 D.以链表方式存储且数据元素有序 12. 顺序查找一个具有 n 个元素的线性表, 其时间复杂度为 , 二分查找一个具有 n 个元素的线性表, 其时间复杂度为 。 2 A.O(n) B.O(log2n) C.O(n ) D.O(nlog2n) 13.从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列中的正确位置上, 此方法称为 ;从未排序序列中挑选元素,并将其放入已排序序列中的一端,此方法称为 ; 依次将每两个相临的有序表合并成一个有序表的排序方法称为 ;当两个元素比较出现反序时就相 互交换位置的排序方法称为 ; A.归并排序 B.选择排序 C.交换排序 D.插入排序 已知一无向图如题图 4-4 所示,请给出该图的 1 1. 每个顶点的度。 2. 邻接矩阵 2 3 4 3. 邻接表 4. 按上述的邻接表写出广度和深度遍历序列。 5 6
题图 4-4 二.假定一个表为 (32, 75, 63, 48, 94, 25, 36, 18, 70) , 散列空间为[0..10], 1. 若采用除留余数法构造表,哈希函数为 H(K)=K MOD 11,用线性探测法解决冲突,试画出哈希表, 并求在等概率情况下的平均查找长度。

2.

若采用除留余数法构造表,哈希函数为 H(K)=K MOD 11,用链地址法解决冲突,试画出哈希表,并 求在等概率情况下的平均查找长度。

三.有 8 个带权结点,权值为(3,7,8,2,6,10,14,9) ,试以它们为叶子结点构造一棵哈夫曼树(要 求每个结点左子树的权值小于等于右子树的权值) ,并计算出带权路径长度。 四.一对称阵 An*n,若只存储此对称阵的上半三角元,写出以行为主序存储和以列为主序存储时计算每一 元素 Aij 存储地址的公式。
2

1:求下图的最小生成树

实际背景: 要在 n 个居民点之间架设煤气管道,很显然最多可架设 n(n-1)/2 条管道,然而要连通 n 个居民点架设 n-1 条管道(无环出现)就可以了,为了使造价最小,选择哪 n-1 条边?这就是最小生成树问题。 算法 1(prim 算法):书本 P104 页 (1)图采用邻接矩阵存储。 (2)找到目前情况下能连上的权值最小的边的另一端点,加入之,直到所有的顶点加入完毕。 算法 2(kruskal 算法):书本 P107 页 (1)图采用边目录方式存储。 (2)选目前情况下能连上的权值最小的边,若与以生成的树不够成环,加入之,直到 n-1 条边加入完毕。 单对顶点间的最短路径: 例 1: 输入起点, 终点, 求其最短路径? 1.Dijkstra 算法:书本 P91 页 基本思想是:设置一个顶点的集合 s, 并不断地扩充这个集合,一个顶点属于 集合 s 当且仅当从源点到该点的路径已 求出。开始时 s 中仅有源点,并且调整 非 s 中点的最短路径长度,找当前最短 路径点,将其加入到集合 s,直到终点 在 s 中。 2.迭代算法(ford 算法) :书本 P97 页 Dijkstra 算法只能适合权为正值的情况,但当权为负值时,是 Dijkstra 算法爱莫能助,这时只要图中不 存在负权回路可用迭代算法。 迭代算法的思想:不停地调整图中的顶点值(源点到该点的最短路径值),直到没有点的值调整了为止。

2. 2 一点到其它所有点的最短路径 例 2:如下图:求起点到所有点的最短路径?

3

1.Dijkstra 算法: 基本思想是:设置一个顶点的集合 s,并不断地扩充这个集合,一个顶点属于集合 s 当且仅当从源点到该 点的路径已求出。开始时 s 中仅有源点,并且调整非 s 中点的最短路径长度,找当前最短路径点,将其加 入到集合 s 中,直到所有的点都在 s 中。 2.ford 算法 3.所有点间的最短路径 弗洛耶德算法(Floyed 算法): 基本思想:求解所有点间的路径需要进行 n 次试探。对于顶点 i 到顶点 j 的路径长度,首先考虑让路径经 过顶点 1,比较路径(i,j)和(i,1,j)的长度取其短者为当前求得的最短路径长度。对每一对顶点的 路径都做这样的试探,则可求得一个矩阵设为 A(1),求 n 次即得每对顶点间的最短路径 A(n)。A(0)=A: 邻接矩阵。如下图: 注意:弗洛耶德算法(Floyed 算法)思想可用 与判断有向图中任意两点是否连通?算法如下: for k:=1 to n do for i:=1 to n do for j:=1 to n do if (a[i,k]=1)and (a[k,j]=1) then a[i,j]=1 (a[i,j]=1 表示 i 可达 j,a[i,j]=0 表示 i 不可达 j)。 AOV 网 在现代化管理中,人们常用有向图来描述和分析一项工程的计划和实施过程,一个工程常被分为多个小的 子工程,这些子工程被称为活动(Activity),在有向图中若以顶点表示活动,有向边表示活动之间的先 后关系,这样的图简称为 AOV 网。如下图是计算机专业课程之间的先后关系: 基础知识课程应先于其它所有课程, pascal 语言课程应先 于数据结构。

3. 2 拓扑排序 在 AOV 网中为了更好地完成工程,必须满足活动之间先后 关系,需要将各活动排一个先后次序即为拓扑排序。如上 图的拓扑排序 基础知识;Pascal;数据结构;离散数学。或 基础知识;离散数学 Pascal;数据结构。 拓扑排序的方法和步骤: (1)在图中选一个没有前趋的顶点并输出之 (2)删除该顶点及由它发出的各边,直到图中不存在没有前趋的顶点为止。 若图中存在回路,拓扑排序无法进行。 以下是将一 AOV 网进行拓扑排序的算法: 网采用邻接矩阵 A 表示,若 a[i,j]=1,表示活动 i 先于 j,a[i,j]=0,表示活动 i 与 j 不存在先后关系。 (1)计算各顶点的入度 (2)找入度为零的点输出之,删除该点,且与该点关联各点的入度减 1 (3)若所有顶点都输出完毕。

4

AOE 网 在现代化管理中,人们常用有向图来描述和分析一项工程的计划和实施过程,一个工程常被分为多个小的 子工程,这些子工程被称为活动(Activity),在带权有向图中若以顶点表示事件,有向边表示活动,边 上的权值表示该活动持续的时间,这样的图简称为 AOE 网,如下图。 AOE 网具有以下性质: (1)只有在某顶点所代表的事件发生后, 从该顶点出发的各有向边所代表的活动才 能开始。 (2)只有在进入某点的各有向边所代表的 活动都已结束,该顶点所代表的时事件才能 发生。 可以将上图假想一个工程有 6 项活动,网中 5 个顶点,分别表示 5 个事件,边上的权值分别表示各项活动 所需要的时间,事件 v1 表示工程开始,事件 v3 表示活动 3 和 4 完成后,活动 5 可以开始,事件 v4 表示 活动 2 完成活动 4 和活动 6 开始,v5 表示活动 1 完成活动 3 开始,事件 v2 表示工程结束。 4. 2 关键路径及其算法 1.关键路径: 在 AOE 网中所关心的问题是完成整个工程至少需要多少时间和哪些活动是影响整个工程进度的关键。 由于 AOE 网中的某些活动能够平行地进行,故完成整个工程所需的时间是从开始顶点到结束顶点的最长路 径长度(路径上的权值和)最长路径叫关键路径。如上述工程的关键路径是 1->4->3->2,关键路径长度为 2+7+6=15,关键活动是 a2,a4,a5。 2.关键路径算法 1: 1)将网拓扑排序 2)以拓扑序列划分阶段 3)用动态规划求解关键路径 3.关键路径算法 2: 若结点的排列已经过拓扑排序,即序号前面的结点会影响序号后面结点的活动,如下图。 可使用如下算法: (1)求活动最早可以开始的时间 eet[1]:=0;eet[k]:=max(eet[j]+r[j,k] ) (2)求活动最迟应该开始的时间 et[n]:=eet[n];et[k]:=min(et[j]-r[k,j]); (3)关键路径通过点 J,具有如下的性质:eet[j]=et[j]

5

5.1 鸽巢原理 1.简单形式 如果 n+1 个物体被放进 n 个盒子,那么至少有一个盒子包含两个或更多的物体。 例 1:在 13 个人中存在两个人,他们的生日在同一月份里。 例 2:设有 n 对已婚夫妇。为保证有一对夫妇被选出,至少要从这 2n 个人中选出多少人?(n+1) 2.加强形式 令 q1,q2,...qn 为正整数。如果将 q1+q2+...+qn-n+1 个物体放入 n 个盒子内,那么或者第一个盒子至少含有 q1 个物体,或者第二个盒子至少含有 q2 个物体,...,或者第 n 个盒子含有 qn 个物体. 例 3:一篮子水果装有苹果、香蕉、和橘子。为了保证篮子内或者至少 8 个苹果或者至少 6 个香蕉或者至少 9 个橘子,则放入篮子中的水果的最小件数是多少?(21 件) 5. 2 容斥原理及应用 原理:集 S 的不具有性质 P1,P2,...,Pm 的物体的个数由下式给出: |A1∩A2∩...∩Am|=|S|-∑|Ai|+∑|Ai∩Aj|-∑|Ai∩Aj∩

Ak|+...+(-1) |A1∩A2∩...∩Am|
如:m=3,时上式为: |A1∩A2∩A3|=|S|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)

m

-|A1∩A2∩A3|
推论:至少具有性质 P1,P2,...Pm 之一的集合 S 的物体的个数有: | A1∪A2∪....∪Am|=|S|—|A1∩A2∩...∩Am|= ∑|Ai|-∑|Ai∩Aj|+∑|Ai∩Aj∩Ak|+...+(-1)
m+1

|A1∩A2∩...∩Am|

例 4:求从 1 到 1000 不能被 5,6,和 8 整除的整数的个数? (1000-(200+166+125)+(33+25+41)-8=600) 5.3 常见递推关系及应用 1.算术序列 每一项比前一项大一个常数 d; 若初始项为 h0:则递推关系为 hn=hn-1+d=h0+nd; 对应的各项为:h0,h0+d,h0+2d,....,h0+nd; 前 n 项的和为(n+1)h0+dn(n+1)/2 例 5: 1,2,3,... 例 6: 1,3,5,7...等都是算术序列。 2.几何序列 每一项是前面一项的常数 q 倍 若初始项为 h0:则递推关系为 hn=h0q q=h0q ; 对应的各项为: h0,h0q ,h0q ,....,h0q 例 7: 1,2,4,8,16,... 例 8: 5,15,45,135,...等都是几何序列; 前 n 项和为((q -1)/(q-1) )h0 3.Fibonacci 序列 除第一、第二项外每一项是它前两项的和; 若首项为 f0 为 0,则序列为 0,1,1,2,3,5,8...递推关系为(n>=2)fn=fn-1+fn-2 前 n 项的和 Sn=f0+f1+f2+...+fn=fn+2-1 例 9:以下是 Fibonacci 的示例: 1.楼梯有 n 阶台阶,上楼可以一步上 1 阶,也可以一步上 2 阶,编一程序计算共有多少种不同的走法? 2.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问 n 个月后共有多少对兔子? 3.有 n*2 的一个长方形方格,用一个 1*2 的骨牌铺满方格。求铺法总数?
n+1 n-1 n 1 2 n

6

4.错位排列 首先看例题: 例 10:在书架上放有编号为 1,2,....n 的 n 本书。现将 n 本书全部取下然后再放回去,当放回去时要求每本书 都不能放在原来的位置上。 例如:n=3 时: 原来位置为:123 放回去时只能为:312 或 231 这两种 问题:求当 n=5 时满足以上条件的放法共有多少种?(不用列出每种放法) (44) {1,2,3,....,n}错位排列是{1,2,3,..,n}的一个排列 i1i2...in,使得 i1<>1,i2<>2,i3<>3,...in<>n 错位排列数列为 0,1,2,9,44,265,.... 错位排列的递推公式是:dn=(n-1)(dn-2+dn-1)(n>=3) =ndn-1+(-1) 5.分平面的最大区域数 1.直线分平面的最大区域数的序列为: 递推公式是: fn=fn-1+n=n(n+1)/2+1 2.折线分平面的最大区域数的序列为: 递推公式是:fn=(n-1)(2n-1)+2n; 3.封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为: 递推公式是:fn=fn-1+2(n-1)=n -n+2 6.Catalan 数列 先看下面两个例题: 例 11:将一个凸多边形区域分成三角形区域的方法数? 令 hn 表示具有 n+1 条边的凸多边形区域分成三角形的方法数。同时令 h1=1,则 hn 满足递推关系 hn=h1hn-1+h2hn-2+...+hn-1h1(n>=2)(想一想,为什么?) 该递推关系的解为 hn=c(2n-2,n-1)/n (n=1,2,3,...) 其对应的序列为 1,1,2,5,14,42,132,....从第二项开始分别是三边形,四边形,...的分法数 即 k 边形分成三角形的方法数为 hk=c(2k-4,k-2)/(k-1)(k>=3) 例 12:n 个+1 和 n 个-1 构成 2n 项 a1,a2,...,a2n 其部分和满足 a1+a2+...+ak>=0(k=1,2,3,..,2n) 对与 n 该数列为 Cn=c(2k,k)/(k+1) (k>=0) 对应的序列为 1,1,2,5,14,42,132,... 序列 1,1,2,5,14,42,132,....叫 Catalan 数列。 例 13:下列问题都是 Catalan 数列。 1.有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票,另外 n 人只有 10 元钞票, 剧院无其它钞票,问有多少中方法使得只要有 10 元的人买票,售票处就有 5 元的钞票找零? 2.一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。如果他 从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路? 3.在圆上选择 2n 个点,将这些点成对连接起来使得所得到的 n 条线段不相交的方法数? 4.n 个结点可够造多少个不同的二叉树?
2 n-2

2,4,7,11,...., 2, 7, 16,29, ..., 2, 4, 8, 14,...,

5.一个栈(无穷大)的进栈序列为 1,2,3,..n,有多少个不同的出栈序列?
7


相关文章:
《数据结构(c语言版)》知识点概括
数据结构(c语言版)》知识点概括_理学_高等教育_教育专区。觉得好,就下载吧数据结构知识点概括 第一章 概论 数据就是指能够被计算机识别、存储和加工处理的信息...
数据结构各种程序全集
数据结构各种程序全集_工学_高等教育_教育专区。数据结构各种程序全集 //功能:顺序表实现线性表的基本功能 #include <iostream.h> #include <windows.h> #include...
数据结构课后习题详解(超完整,超经典)
数据结构课后习题详解(超完整,超经典)_工学_高等教育_教育专区。第1章 绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据...
数据结构 名词解释
数据结构 名词解释_理学_高等教育_教育专区。沈阳理工大学1. 数据 数据是描述客观事物的符号,是能够被计算机输入、识别、处理的各种符号,是计算机化 的信息。 2. ...
数据结构的小论文
数据结构的小论文作者 学号 一. 名称解释 (1)数据是信息的载体,是对客观事物的符号表示。 通俗的说, 凡是能被计算机识别、 存取和加工处理的符号、 字符、 图形...
数据结构历年试题及答案
一、单项选择题(本大题共 15 小题,每小题 2 分,共 30 分) 1.在数据结构中,数据的逻辑结构可以分成( B ) B.线性结构和非线性结构 2.在以单链表为存储...
数据结构知识点总结(详细无题目)
数据结构知识点总结(详细无题目)_计算机软件及应用_IT/计算机_专业资料。数据结构知识点总结内容概要: 基本概念——线性表——栈与队列——树与二叉树——图——...
数据结构知识点整理(清华大学出版社)
数据结构:主要研究非数值计算问题中计算机的操作对象有哪些结构(逻辑结构)、这些结构在计算机中的表示及 其操作的定义和实现问题。 2. 逻辑结构:不考虑实现,仅看...
数据结构简答题打印版
数据结构简答题打印版_计算机软件及应用_IT/计算机_专业资料。数据结构简答题 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽 象数...
什么是数据结构
a) 集合 b) 线性结构 c) 树形结构 d) 图状结构 (网状结构) 3) 数据结构的形式定义: (D,S): 其中 D 为数据元素有限集 S 为 D 上关系的有限集。 ...
更多相关标签:
数据结构与算法 | 数据结构c语言版 | 数据结构 严蔚敏 | 大数据平台架构 | 大数据系统架构 | 数据结构培训 | 数据结构与算法分析 | java数据结构 |