文档库 最新最全的文档下载
当前位置:文档库 › 数据结构整理

数据结构整理

数据结构整理
数据结构整理

一、选择题

1、数据结构是一门研究非数值计算程序中计算机的 A 以及它们之间的 B 和运算等的学科。

1 A. 操作对象 B. 计算方法 C. 逻辑存储 D. 数据映像

2 A. 结构 B. 关系 C. 运算 D. 算法

2、线性结构的顺序存储结构是一种 A 的存储结构,线性结构的链式存储结构是一种 B 的存储结构。

1 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取

2 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取

3、下面程序的时间复杂度为 C 。

for(i=0; i

for(j=0; j

A[i][j]=i*j;

A. O(m2)

B. O(n2)

C. O(m×n)

D. O(m+n)

4、下面算法的时间复杂度为O(n) 。

int f(int n)

{

if(n==0||n==1) return 1;

else return n*f(n-1);

}

5、计算机算法是解决问题的有限运算序列,具备输入、输出、 B 五个特性。

A. 可执行性、可移植性和可扩充性

B. 可行性、确定性和有穷性

C. 确定性、有穷性和稳定性 C. 易读性、稳定性和安全性

6、通常所说的时间复杂度是指 C .

A. 语句的频度

B. 算法的时间消耗

C. 渐进时间复杂度

D. 最坏的时间复杂度

7、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新的元素算法的时间复杂度为 C 。

A. O(log2n)

B. O(1)

C. O(n)

D. O(n2)

8、以下关于线性表的说法中,不正确的是 C 。

A. 线性表中的数据元素可以是数字、字符、结构等不同类型

B. 线性表中包含的数据元素个数不是任意的

C. 线性表中的每一个结点都有且只有一个直接前驱和直接后继

D. 存在这样的线性表:表中各结点都没有直接前驱和直接后继

9在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为 B 。

A. O(1)

B. O(n)

C. O(n2)

D. O(log2n)

10、等概率情况下,在有n个结点的顺序表上做插入结点操作,需平均移动的结点数目为 B 。

A. n

B. (n-1)/2

C. n/2

D. (n+1)/2

11、在一个长度为n的顺序存储的线性表中查找值为x的元素时,平均查找长度(及x同元素的平均比较次数,假定查找每个元素的概率都相等)为 C 。

A. n

B. n/2

C. (n+1)/2

D. (n-1)/2

12、在顺序表中,只要知道 A ,就可以求出任一结点的存储地址。

A. 基地址

B. 结点大小

C. 向量大小

D. 基地址和结点大小

13、将两个各有n个元素的有序表归并为一个有序表,其最少的比较次数是

A 。

A. n

B. 2n-1

C. 2n

D. n-1

14、线性表采用链表存储时其存储地址要求 D 。

A. 必须是连续的

B. 部分地址必须是连续的

C. 必须是不连续的

D. 连续的和不连续的都可以

15、下面关于线性表的描述中,错误的是 B 。

A. 线性表采用顺序存储,必须占用一片连续的存储单元

B. 线性表采用顺序存储,便于进行插入和删除操作

C. 线性表采用链式存储,不必占用一片连续的存储单元

D. 线性表采用链式存储,便于插入和删除操作

16、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 B

A. O(1)

B. O(n)

C. O(n2)

D. O(log2n)

17、在一个带头结点的单链表HL中,若要向表头插入一个由指针p指向的结点,则执行的语句是 D 。

A. HL=p; p->next=HL;

B. p->next=HL; HL=p;

C. p->next=HL; p=HL;

D. p->next=HL->next; HL->next=p;

18、在一个单链表HL中,若要删除由指针q所指向结点的后继结点,则执行的语句是

C 。

A. p=q->next; p->next=q->next;

B. p=q->next; q->next=p;

C. p=q->next; q->next=p->next;

D. q->next=q->next->next; q->next=q;

19、在双向链表中,在指针p所指的结点前插入一个指针q所指向的结点,操作是

C 。

A. p->Prior=q; q->Next=p; p->Prior->next=q; q->Prior=q;

B. p->Prior=q; p->Prior->next=q; q->next=p; q->Prior=p->Prior;

C. q->Next=p; q->Prior=p->Prior; p->Prior->Next=q; p->Prior=q;

D. q->Prior=p->Prior; q->Next=q; p->Prior=q; p->Next=q;

二、填空题

1、线性结构中元素的关系是一对一,树形结构中元素的关系是一对多,图形结构中元素的关系是多对多。

2、算法的5个重要特性是可行性、和确定性、有穷性、输入和输出。

3、评价一个算法优劣的两个主要指标是时间复杂性和空间复杂

性。

4、线性表中结点的集合是有限的,结点之间的关系是一对一关系。

5、顺序表中访问任一个结点的时间复杂度为O(1) 。

6、线性表中第一个结点没有直接前驱,称为头结点。

7、在一个长度为n的顺序表中删除第i个元素,要移动n-i 个元素。

8、在一个长度为n的顺序表中,如果要在第i个元素前插入一个元素,要后移n-i+1 个元素,在插入操作中,移动元素的均值为(n+1)/2 。

9、根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成单向链表和双向链表。

10、链式存储的特点是利用指针来表示数据元素之间的逻辑关系。

11、静态链表(线性表的游标实现)是指用数组下标表示单链表的指针。

一、选择题

1、设有编号为1, 2, 3, 4的4辆列车,顺序进入一个栈结构的站台,下列不可能的出栈顺序为 D 。

A. 1234

B. 1243

C. 1324

D. 1423

2、4个元素按A, B, C, D顺序进入S栈,执行两次Pop(S, x)运算后,栈顶元素的值是B 。

A. A

B. B

C. C

D. D

3、从一个栈顶指针为top的链栈中删除一个结点时,用x保存被删除的结点,应执行下列

A 命令。

A. x=top; top=top->next;

B. top=top->next; x=top->data;

C. x=top->data;

D. x=top->data; top=top->next;

4、向顺序栈中输入元素时 A 。

A. 先存入元素,后移动栈顶指针

B. 先移动栈顶指针,后存入元素

C. 谁先谁后无关紧要

D. 同时进行

5、设有一个顺序栈,元素A, B, C, D, E, F依次进栈,如果6个元素出栈的顺序是B, D, C, F, E, A,则栈的容量至少为 A 。

A. 3

B. 4

C. 5 6. 6

6、设已将元素A, B, C依次入栈,元素D正等待进栈。那么下列4个序列中不可能出现的出栈顺序为 A 。

A. CADB

B. CBDA

C. CDBA

D. DCBA

7、栈和队列的相同之处是 C 。

A.元素的进出满足先进后出

B.元素的进出满足后进先出

C.只允许在端点进行插入和删除操作

D.无共同点

8、设栈S 和队列Q 的初始状态为空,元素e1,e2,e3,e4,e5 和e6 依次通过栈,一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S 的容量至少应该是 B 。

A. 6

B. 4

C. 3

D. 2

9、队列通常采用的两种存储结构是( A)。

A. 顺序存储结构和链式存储结构

B.散列方式和索引方式

C. 链表存储结构和线性存储结构

D.线性存储结构和非线性存储结构

10、循环队列SQ队满的条件是 B 。

A. SQ->rear==SQ->front

B. (SQ->rear+1)%MAXLEN==SQ->front

B. SQ->rear==0 D. SQ->front==0

11、若用一个大小为6的数组来实现循环队列,且当前front和rear的值分别为3和0,当从队列中删除一个元素,再加入两个元素后,front和rear的值分别为 B 。

A. 5和1

B. 4和2

C. 2和4

D. 1和5

12、链栈与顺序栈相比,有一个较为明显的优点是 A 。

A. 通常不会出现满栈的情况

B. 通常不会出现栈空的情况

C. 插入操作更加方便

D. 删除操作更加方便

13、设用一个大小为M=60的顺序表A[M]表示一个循环队列,如果当前的尾指针rear=32,头指针front=15,则当前循环队列的元素的个数为 C 。

A. 42

B. 16

C. 17

D. 41

14、串是一种特殊的线性表,其特殊性体现在 B 。

A. 可以顺序存储

B. 数据元素是一个字符

C. 可以链式存储

D. 数据元素可以是多个字符

15、设主串的长度为n,模式串的长度为m,则串匹配的KMP算法的时间复杂度为 C 。

A. O(m)

B. O(n)

C. O(m+n)

D. O(m×n)

16、已知串S=“abab”,其Next数组值为 A 。

A. 0123

B. 0121

C. 0112

D. 0122

17、若字符串“ABCDEFG”采用不带表头的链式存储,每个结点保存一个字符。假设每个字符占用1个字节,每个指针占用两个字节,则该字符串的存储密度为 C 。

A. 20%

B. 40%

C. 50%

D. 33.3%

二、填空题

1、在栈中,可进行插入和删除操作的一端称栈顶。

2、在进栈运算时,应先判别栈是否为满。在出栈运算时应先判别栈是否为空。当栈中元素为n个时,进栈运算时发生上溢,则说明该栈的最大容量为n 。

3、设有一空栈,现有输入序列为1, 2, 3, 4, 5,经过push, push, pop, push, pop, push, push, pop, pop之后,输出序列为2354 。

4、对于循环向量的循环队列,求队列长度的公式为(rear-front+n)%n 。

5、栈的逻辑特点是先进后出。队列的逻辑特点是先进先出。两者的共同特点是只允许在它们的端点出插入和删除数据元素,区别是栈只能在一端,队列可以在两端。

6、链队列LQ为空时,LQ->front->next= rear .

7、在一个链队列中,若队首指针为front,队尾指针为rear,则判断该队列只有一个结点的条件为front+1=rear 。

8、设串S=“Ilikecomputer”,T=“com”,则Length(S)= 13 。Index(S, T)= 6 。

9、在KMP算法中,next[j]只与子串有关,而与主串无关。

10、字符串“ababaab“的Next数组值是0112342 。

一、选择题

1、在按行优先顺序存储的三元组表中,下述陈述错误的是 D 。

A. 同一行的非零元素,是按列号递增次序存储的

B. 同一列的非零元素,是按行号递增次序存储的

C. 三元组表中三元组行号是非递减的

D. 三元组表中三元组列号是非递减的

2、在稀疏矩阵的三元组表示法中,每个三元组表示 D 。

A. 矩阵中非零元素的值

B. 矩阵中数据元素的行号和列号

C. 矩阵中数据元素的行号、列号和值

D. 矩阵中非零数据元素的行号、列号和值

3、对特殊矩阵采用压缩存储的目的主要是为了 D 。

A. 表达变得简单

B. 对矩阵元素的存取变得简单

C. 去掉矩阵中的多余元素

D. 减少不必要的存储空间

4、广义表是线性表的推广,它们之间的区别在于 A 。

A. 能否使用子表

B. 能否使用原子项

C. 表的长度

D. 是否能为空

5、已知广义表(a, b, c, d)的表头是 A ,表尾是 D 。

A. a

B. ()

C. (a, b, c, d)

D. (b, c, d)

6、下面说法不正确的是 A 。

A. 广义表的表头总是一个广义表

B. 广义表的表尾总是一个广义表

C. 广义表难以用顺序存储结构表示

D. 广义表可以是一个多层次的结构

7、若广义表A满足Head(A)=Tail(A),则A为 C 。

A. ( )

B. (())

C. (( ),( ))

D. (( ), ( ), ( ))

8、在一棵树中,如果结点A有3个兄弟,B是A的双亲,则B的度为 D

A. 1

B. 2

C. 3

D. 4

9、深度为h的完全二叉树至少有 D 个结点,至多有 B 个结点

A. 2h

B. 2h-1

C. 2h+1

D. 2h-1

10、具有n个结点的满二叉树有 C 个叶结点。

A. n/2

B. (n-1)/2

C. (n+1)/2

D. n/2+1

11、一棵具有25个叶结点的完全二叉树最多有 C 个结点。

A. 48

B. 49

C. 50

D. 51

12、已知二叉树的先根遍历序列是ABCDEF,中根遍历序列是CBAEDF,则后根遍历序列是 A 。

A. CBEFDA

B. FEDCBA

C. CBEDFA

D. 不定

13、具有10个叶结点的二叉树中有 B 个度为2的结点。

A. 8

B. 9

C. 10

D. 11

14、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足

C 。

A. 所有非叶结点均无左孩子

B. 所有非叶结点均无右孩子

C. 只有一个叶子结点

D. A和B同时成立

二、填空题

1、稀疏矩阵一般压缩存储的方式有三种,分别是三元数组存储、行指针链表和十字链表。

2、二维数组M中每个元素的长度是3字节,行下标i从0~7,列下标j从0~9,从首地址&M[0][0]开始连续存放在存储器中。若按行优先的方式存放,元素M[7][5]的起始地址为

M[0][0]+228 ;若按列优先方式存放,元素M[7][5]的起始地址为M[0][0]+144 。

3、广义表(a, (a, b), d, e, ((i, j), k))的长度是 5 ,深度是 3 。

4、设广义表A((( ), (a, (b), c))),则Cal(Cdr(Cal(Cdr(Cal(A))))= (b)

5、一棵二叉树有67个结点,结点的度是0和2。问这棵二叉树中度为2的结点有33 个。

6、含A, B, C三个结点的不同形态的二叉树有 5 棵。

7、含有4个度为2的结点和5个叶子结点的完全二叉树,有 1 个度为1的结点。

一、选择题

1、在线索二叉树中,t所指结点没有左子树的充要条件是 D 。

A. t->left=NULL

B. t->ltag=TRUE

C. t->ltag=TRUE且t->left=NULL

D. 以上都不对

2、n个结点的线索二叉树上含有的线索数为 C 。

A. 2n

B. n-1

C. n+1

D. n

3、具有n(n>1)个结点的完全二叉树中,结点i(2i>n)的左孩子结点是 D 。

A. 2i

B. 2i+1

C. 2i-1

D. 不存在

4、将一颗有100个结点的完全二叉树从上到下、从左到右一次对结点进行编号,根结点的编号为1,则编号为45的结点的右孩子的编号为 D 。

A. 46

B. 47

C. 90

D. 91

二、填空题

1、具有100个结点的完全二叉树的叶子结点数为50 。

2、在用左右链表示的具有n个结点的二叉树中,共有2n 个指针域,其中n-1 个指针域用于指向其左右孩子,剩下的n+1 个指针域是空的。

3、如果一颗完全二叉树的任意一个非终结结点的元素都不小于其左儿子结点和右儿子结点(如果有的话)的元素,则称此完全二叉树为最大堆。

一、选择题

1、在结点数为n的堆中插入一个结点时,复杂度为 C 。

A. O(n)

B. O(n2)

C. O(log2n)

D. O(log n2)

2、两个二叉树是等价的,则它们满足 D 。

A. 它们都为空

B. 它们的左右子树都具有相同的结构

C. 它们对应的结点包含相同的信息

D. A、B和C

3、包含n个元素的堆的高度为 C 。(符号「a表示取不小a最小整数)

A. n

B. 「log2n

C. 「log2(n+1)

D. n+1

二、填空题

1、堆是一种特殊形式的完全二叉树,对于最大堆而言,其根结点的元素的值应该是所有结点元素中最大的。

2、二叉树的复制是指按照一棵已知的二叉树复制一个副本,使两者等价。复制二叉树最长用的方法是后根遍历递归算法。

3、在定义堆时,通常采用结构体方式定义相应的二叉树,这样可以很容易实现其相关操作。

4、在构建选择树时,根据孩子结点的获胜者确定他们双亲结点所得到的选择树称为胜者树。根据孩子结点的失败者确定他们双亲结点所得到的选择树称为败者树。

5、树的表示方法包括数组表示、邻接表表示和左右链表示。

一、选择题

1、以下说法错误的是 B

A. 存在这样的二叉树,对其采用任何次序的遍历其结点访问序列均相同

B. 二叉树是树的特殊情形

C. 由树转换成二叉树,其根结点的右子树总是空的

D. 在二叉树中只有一棵子树的情形下,也要指出是左子树还是右子树

2、设F是一个森林,B是由F变换得到的二叉树。若F中有n个非终端结点,则B中没有右孩子的结点有 C 个。

A. n-1

B. n

C. n+1

D. n+2

3、将一棵树T转换为二叉树B,则T的后根序列是B的 B 。

A. 先根序列

B. 中根序列

C. 后根序列

D. 层次序列

4、设树T的度为4,其中度为1, 2, 3, 4的结点个数分别为4, 2, 1, 1,则T中的叶结点的个数为 D 。

A. 5

B. 6

C. 7

D. 8

5、设森林F中有三棵树,第一、第二、第三棵树的结点个数分别为M1, M2, M3。与森林F

对应的二叉树根结点的右子树上的结点个数为 D 。

A. M1-1

B. M1+M2

C. M2

D. M2+M3

6、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序,则该二叉树是 C 。

A. 二叉排序树

B. 哈夫曼树

C. 堆

D. 线索二叉树

7、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是 B 。

A. 32

B. 33

C. 34

D. 15

二、填空题

1、表达式(a+b*(c-d))-e/f的波兰式(前缀式)是-+a*b-cd/ef ,逆波兰式(后缀式)是abcd-*+ef/- 。

2、设F是由T1、T2、T3三棵树组成的森林,与F对应的二叉树为B。已知T1, T2, T3的结点数分别为n1, n2和n3,则二叉树B的左子树中有n1-1 个结点,二叉树B的右子树中有n2+n3 个结点。

3、设二叉树的中根序列为ABCDEFG,后根序列为BDCAFGE。则该二叉树的先根序列为EACBDGF 。该二叉树对应的森林中包含 2 棵树。

4、先根次序遍历森林等同于按先根遍历对应的二叉树,后根次序遍历森林等同与按中根遍历对应的二叉树。

5、一棵哈夫曼树有19个结点,则其叶子结点的个数为10 。

6、设有数据WG={7, 19, 2, 6, 32, 3, 21, 10}叶节点权重集合,则所构建哈夫曼树的高是 5 ,带权路径长度WPL为169 。

7、设有一份电文中共使用6个字符a, b, c, d, e, f,其中出现频率依次为2,3,4,7,8,9,则字符c的哈夫曼编码是001 ,电文编码的总长度为80 。

8、在有n个结点的哈夫曼树中,叶子结点总数为(n+1)/2 ,非叶结点的总数为(n-1)/2 。

一、选择题

1、在一个无向图中,所有顶点的度数之和等于所有边数的 C 倍。

A. 1/2

B. 1

C. 2

D. 4

2、在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的 B 倍。

A. 1/2

B. 1

C. 2

D. 4

3、G是一个非连通无向图,共有28条边,则该图至少有 D 个顶点。

A. 6

B. 7

C. 8

D. 9

4、深度优先遍历类似与二叉树的 A

A. 先根遍历

B. 中根遍历

C. 后根遍历

D. 层次遍历

5、广度优先遍历类似与二叉树的 D

A. 先根遍历

B. 中根遍历

C. 后根遍历

D. 层次遍历

6、有n个顶点的无向图的邻接矩阵使用 B 数组存储的。

A. 一维

B. n行n列

C. 任意行n列

D. n行任意列

7、对于一个具有n个顶点和e条边的无向图,采用邻接表表示,则表头数组大小至少为(假设下标为0的数组参与使用) C 。

A. n-1

B. n+1

C. n

D. n+e

二、填空题

1、若无向图G中顶点数为n,则图G至多有n*(n-1)/2 条边;若G为有向图,则图G至多有n*(n-1) 条边。

2、图的存储结构主要有两种,分别是邻接矩阵和邻接表。

3、已知一个图的邻接矩阵表示,计算第j个顶点的入度的方法是将第j列的数相加,计算第j个顶点的出度的方法是将第j行的数相加。

4、图的遍历有深度优先遍历和广度优先遍历等方法。

5、在深度优先搜索和广度优先搜索中,都采用visited[i]= false 的方式设置第i个顶点为new,而采用visited[i]= true 的方式标识第i个结点为old。

6、由于深度优先算法的特点,深度优先往往采用递归的方式实现。

7、由于广度优先算法的特点,在广度优先实现过程中,往往要借助于另一种数据结构

队列实现。

一、选择题

1、下面 B 方法可以判断出一个有向图是否有环(回路)。

A. 深度优先遍历

B. 拓扑排序

C. 求最短路径

D. 求关键路径

2、设网(带权的图)有n个顶点和e条边,则采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为 C 。

A. O(n)

B. O(n+e)

C. O(n2)

D. O(n3)

3、设图有n个顶点和e条边,求解最短路径的Floyd算法的时间复杂度为 D 。

A. O(n)

B. O(n+e)

C. O(n2)

D. O(n3)

4、最小生成树是指 C 。

A. 由连通网所得到的边数最少的生成树。

B. 由连通网所得到的顶点数相对较少的生成树。

C. 连通网树。

D. 连通网的极小连通子图。

5、下面关于工程计划的AOE网的叙述中,不正确的是 B 。

A. 关键活动不按期完成就会影响整个工程的完成时间。

B. 任何一个关键活动提前完成,那么整个工程将会提前完成。

C. 所有关键活动都提前完成,那么整个工程将会提前完成。

D. 某些关键工程若提前完成,那么整个工程将会提前完成。

6、在AOE网中,始点和汇点的个数为 D 。

A. 1个始点,若干个汇点

B. 若干个始点,若干个汇点

C. 若干个始点,1个汇点 C. 1个始点,1个汇点

7、在下图所示的无向图中,从顶点v1开始采用Prim算法生成最小生成树,算法过程中产生的顶点次序为 B 。

A. v1, v3, v4, v2, v5, v6

B. v1, v3, v6, v2, v5, v4

C. v1, v2, v3, v4, v5, v6

D. v1, v3, v6, v4, v2, v5

8、在上图所示的图中,采用Cruskal算法生成最小生成树,过程中产生的边的次序是 C 。

A. (v1, v2), (v2, v3), (v5, v6), (v1, v5)

B. (v1, v3), (v2, v6), (v2, v5), (v1, v4)

C. (v1, v3), (v2, v5), (v3, v6), (v4, v5)

D. (v2, v5), (v1, v3), (v5, v6), (v4, v5)

9、在下图所示的有向网中,从顶点v1到其他顶点的最短路径分别是 C 。

A. 6, 1, 6, 10, 4

B. 5, 1, 6, 7, 4

C. 5, 1, 6, 8, 4

D. 6, 1, 6, 8, 6

10、如下图所示的图中,其中一个拓扑排序的结果是 A 。

A. v1→v2→v3→v6→v4→v5→v7→v8

B. v1→v2→v3→v4→v5→v6→v7→v8

C. v1→v6→v4→v5→v2→v3→v7→v8

D. v1→v6→v2→v3→v7→v8→v4→v5

11、在下图所示的AOE网中,活动a9的最早开始时间为 B 。

A. 13

B. 14

C. 15

D. 16

12、在上图所示的AOE网中,活动a4的最迟开始时间为 D

A. 4

B. 5

C. 6

D. 7

二、填空题

1、一个不存在回路的有向图称为无环路有向图,简称dag(Directed Acyclic Graph)。

2、对于含有n个顶点e条边的连通图,利用Prim算法求其最小生成树的时间复杂度为O(n2) ,利用Kruscal算法求最小生成树的时间复杂度是O(n) 。

3、具有n个顶点的有向图,某顶点到其他各顶点的最短路径的Dijkstra算法的时间复杂度是O(n3) 。

4、顶点表示活动的网简称为AOV ;边表示活动的网简称为AOE 。

5、一个含有n个顶点的无向连通图,其每条边的权重都是a(a>0),则其最小生成树的权重等于(n-1)*a 。

6、动态查找表和静态查找表的重要区别是:前者包含插入和删除运

算,而后者不包含这两种运算。 设有一个稀疏矩阵:

??

?

???

???

?

?????

??

???--00060

002000700005000000000810030000000

040

1、写出三元组顺序表存储表示

A=??

??

??????

???

?

??????????????--635

254714533802161331410776

2、写出十字链表存储的顺序表示

0 1 4

^

^ 1 3 -3

4 5 2

^

^ 4 1 -7

^

^ 3 3 5

^

^

2 0 8

^

^ 1 6 1

^

^ 5 3 6

^

^ M.chead M.rhead

六、画出广义表LS=(( ), (e), (a, (b, c, d)))的头尾链表存储结构(类似于教材P70图2-27.9)。 要求:按照教材中的事例画出相应的图形,不需要编程。 其中第一个节点如下:

三、画出下图所表示的二叉树的中序线索二叉树和先序线索二叉树。

四、已知二叉树的先根序列是AEFBGCDHIKJ ,中根序列是EFAGBCHKIJD ,画出此二叉树,并画出后序线索二叉树。

t

t

t f ^ f e ^ f ^ f a t ^ f b f c

f d ^

三、假设现在有如下的元素:7、16、49、82、5、31、6、2、44。画出将每一个元素插入堆中以后的最大堆。 要求: 利用基本操作Insert 的基本原理,先用第一个元素7构成一个二叉树,然后将第二个元素16插入该二叉树中,再将第三个元素49插入堆中,……,直到最后一个元素插入为止。上述过程要求画图完成。

7

16 16

7

1.

2. 16

7 49

49

7 16

A

R

C

D E

F

G

J

H

K

I 后序线索FEGKJIHDCRA

3 49

7 16 82

49

82 49

7

82

49 16

7

4 82

49 16 7 5

5.

82

49 16

7 5 31

82

49 31 7 5 16

6 82

49 31

7 5 16 6

三、传输一段电文如下:CATEATDA TACAECA TAEAAE 。设计出这段电文中的每个字符的哈夫曼编码,并计算整段电文的编码长度。

四、给定叶子结点的权值集合{15, 3,14, 2, 6, 9, 16, 17},构造相应的哈夫曼树,并计算其带权路径长度。

N(A):9 N(C):3 N(D):1 N(E):4 N(T):4

21

12 9

4

8

1

3

4

4 0 0 0 0 1 1 1 1 A:1 C:001 D:000 E:010 T:011

W=9*1+(3+1+4+4)*3=45

7

2 82

49 31

7 5 16 6

8

2 82

49 31

7 5 16

6

44

2 82

49

31

44 5 16 6

7

六、画出下图所示的森林经转换后所对应的二叉树,并指出在二叉树中某结点为叶子结点时,所对应的森林中结点应满足的条件。

七、已知森林F 的先根序列为:ABCDEFGHIJKL ,后根序列为:CBEFDGAJIKLH ,试画出森林F 。

提示:先画出森林F 所对应的二叉树B ,然后再将B 转换为森林。

A

B F

E

C H G

D

J

I

若一个节点为叶节点,则它必定是森林中树的最右子节点或是单节点树。

16 17

5 2

3

6

82

49

33

20

29 11 9

15

14

W=(2+3)*5+6*4+(9+14+15)*3 +(16+17)*2=229

八、画出表达式(A+B*C/D)*E+F*G 所对应的树结构,并写出该表达式的波兰表示式和逆波

兰表示式。

三、已知一个连通图如下图所示,试给出图的邻接矩阵和邻接表存储示意图,若从顶点v1出发对该图进行遍历,分别给出一个按深度优先遍历和广度优先遍历的顶点序列。

0 1 0 1 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0

v1 v2 v3 v4 v5 v6 v1 v2 v3 v4 v5 v6

A B G

C

D F

E

H

I L

J

K

A B * C / D

F G * + E

+ *

波兰表示法:+*+A*B/CDE*FG 逆波兰式:ABCD/*+E*FG*+

深度优先:v1 v2 v3 v5 v4 v6 广度优先:v1 v2 v4 v6 v3 v5

四、已知一个无向图的顶点集为{a, b, c, d, e},其邻接矩阵如下,画出该无向图,并写出从顶点a 出发按深度优先遍历和按广度优先遍历的结点序列。

HEAD v2 v1 v4 v6 ^ v1 v2 v3 v4 v2 v3 v5 ^ v1 v4 v2 v5 v2 v5 v3 v4 ^

v1

v6

v4 ^

v5 ^ v6 ^

a b

c

d

e

深度优先:a b d c e 广度优先:a b e d c

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件:

(1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 非空线性表的结构特征: (1)且只有一个根结点a1,它无前件; (2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。 线性表的顺序存储结构具有以下两个基本特点: (1)线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为:adr(ai)=adr(a1)+(i-1)k,,adr(a1)为第一个元素的地址,k代表每个元素占的字节数。 顺序表的运算:插入、删除。(详见14--16页) 4 栈和队列 栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。 栈按照“先进后出”(filo)或“后进先出”(lifo)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。 栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。rear指针指向队尾,front指针指向队头。 队列是“先进行出”(fifo)或“后进后出”(lilo)的线性表。 队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。循环队列:s=0表示队列空,s=1且front=rear表示队列满

数据结构整理完整版

第二章线性表 一、顺序表和链表的优缺点 1.顺序表 定义:用一组连续的存储单元(地址连续)依次存放线性表的各个数据元素。即:在顺序表中逻辑结构上相邻的数据元素,其物理位置也是相邻的。 优点 逻辑相邻,物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素(平均约需移动一半结点,当n很大时,算法的效率较低) 预先分配空间需按最大空间分配,利用不充分 表容量难以扩充 2.链式存储结构 定义:由分别表示a1,a2,…,a i-1,a i,…,a n的N 个结点依次相链构成的链表,称为线性表的链式存储表示 优势: (1)能有效利用存储空间; 动态存储分配的结构,不需预先为线性表分配足够大的空间,而是向系统“随用随取”,在删除元素时可同时释放空间。 (2)用“指针”指示数据元素之间的后继关系,便于进行“插入”、“删除”等操作; 插入或删除时只需要修改指针,而不需要元素移动。 劣势: (1)不能随机存取数据元素; (2)丢失了一些顺序表的长处,如线性表的“表长”和数据元素在线性表中的 “位序”,在单链表中都看不见了。如,不便于在表尾插入元素,需遍历整个表才能找到插入的位置。 二、单链表中删除一个节点和插入一个节点的语句操作,p29 1.插入元素操作 算法基本思想:首先找到相应结点,然后修改相应指针。 假定在a,b之间插入结点X,s指向X, p指向a,指针修改语句为: s->next=p->next; p->next =s;

2.删除元素操作 算法基本思想:首先找到第i-1 个结点,然后修改相应指针。 删除b结点,其中,P指向a,指针修改语句为:p->next=p->next->next; 三、单链表的就地逆置习题集2.22 算法的基本思想:以单链表作存储结构进行就地逆置的正确做法应该是:将原链表的头结点和第一个元素结点断开(令其指针域为空),先构成一个新的空表,然后将原链表中各结点,从第一个结点起,依次插入这个新表的头部(即令每个插入的结点成为新的第一个元素结点)。 算法思路:依次取原链表中的每个结点,将其作为第一个结点插入到新链表中去,指针p用来指向当前结点,p为空时结束。 void reverse (Linklist H){ LNode *p; p=H->next; /*p指向第一个数据结点*/ H->next=NULL; /*将原链表置为空表H*/ while (p){ q=p; p=p->next; q->next=H->next; /*将当前结点插到头结点的后面*/ H->next=q; } } 第三章栈和队列 一、栈和队列的特性 1.特点 栈必须按“后进先出”(LIFO)的规则进行操作,仅限在表尾进行插入和删除的操作。 队列(FIFO)必须按“先进先出”的规则进行操作,队尾插入,队头删除。 二、循环队列为空和满的判定方法,p63 队空条件:front == rear; 队满条件:(rear + 1) % maxSize == front

数据结构复习提纲(整理)

复习提纲 第一章数据结构概述 基本概念与术语(P3) 1.数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2.数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2.数据元素是数据的基本单位 3.数据对象相同性质的数据元素的集合 4.数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. (1)数据的逻辑结构指数据元素之间固有的逻辑关系. (2)数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释:数据结构、二元组 2、根据数据元素之间关系的不同,数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型,它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i=0)个具有相同性质的数据元素a1,a2,a3……,an组成的有穷序列 //顺序表结构 #define MAXSIZE 100 typedef int DataType; Typedef struct{ DataType items[MAXSIZE]; Int length; }Sqlist,*LinkList; //初始化链表 void InitList(LinkList *L){ (*L)=(LinkList)malloc(sizeof(LNode)); if(!L){ cout<<”初始化失败!”; return;

数据结构课程设计报告模板

《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月

三级项目报告注意事项 1. 按照项目要求书写项目报告,条理清晰,数据准确; 2. 项目报告严禁抄袭,如发现抄袭的情况,则抄袭者与被抄袭者均 以0分计; 3. 课程结束后报告上交教师,并进行考核与存档。 三级项目报告格式规范 1. 正文:宋体,小四号,首行缩进2字符,1.5倍行距,段前段后 各0行; 2. 图表:居中,图名用五号字,中文用宋体,英文用“Times New Roman”,位于图表下方,须全文统一。

目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一:项目成员 (6) 附录二:相关代码、电路图等 (6)

一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能: 1)利用数据结构的知识独立完成一个应用系统设计 2)程序正常运行,能够实现基本的数据增加、删除、修改、查询等功能3)体现程序实现算法复杂度优化 4)体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能: (结合本系统预期具体实现,描述出对应基本要求(增、删、改、查等)的具体功能) 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 (基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现) 模块一: 主要任务:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二: 主要任务:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n: 主要任务:XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

(完整版)非常实用的数据结构知识点总结

数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位,可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义: ·逻辑结构:从逻辑结构上描述数据,独立于计算机。·线性结构:一对一关系。 ·线性结构:多对多关系。 ·存储结构:是逻辑结构用计算机语言的实现。·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·索引存储结构:·稠密索引:每个结点都有索引项。 ·稀疏索引:每组结点都有索引项。 ·散列存储结构:如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上,每种逻辑结构都有一个运算集合。 ·常用的有:检索、插入、删除、更新、排序。 数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型:由用户借助于描述机制定义,是导出类型。 抽象数据类型ADT:·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构,设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程,以一个或多个值输入,并以一个或多个值输出。 评价算法的好坏的因素:·算法是正确的; ·执行算法的时间; ·执行算法的存储空间(主要是辅助存储空间); ·算法易于理解、编码、调试。 时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模n的函数。 渐近时间复杂度:是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。 评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O (n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

数据结构复习要点整理版

第一章数据结构概述 基本概念与术语 1.数据:数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2.数据元素:数据元素是数据的基本单位,是数据这个集合中的个体,也称之为元素,结点,顶点记录。 (补充:一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。)3.数据对象:数据对象是具有相同性质的数据元素的集合,是数据的一个子集。(有时候也叫做属性。) 4.数据结构:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构:数据的逻辑结构是指数据元素之间存在的固有逻辑关系,常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关,是独立于计算机的。 依据数据元素之间的关系,可以把数据的逻辑结构分成以下几种: 1.集合:数据中的数据元素之间除了“同属于一个集合“的关系以外,没有其他关系。 2.线性结构:结构中的数据元素之间存在“一对一“的关系。若结构为非空集合,则除了第一个元素之外,和最后一个元素之外,其他每个元素都只有一个直接前驱和一个直接后继。 3.树形结构:结构中的数据元素之间存在“一对多“的关系。若数据为非空集,则除了第一个元素(根)之外,其它每个数据元素都只有一个直接前驱,以及多个或零个直接后继。 4.图状结构:结构中的数据元素存在“多对多”的关系。若结构为非空集,折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构:数据元素及其关系在计算机的表示称为数据的存储结构。 想要计算机处理数据,就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构: 1.顺序存储结构:把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中,借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2.链式存储结构:借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5.时间复杂度分析:1.常量阶:算法的时间复杂度与问题规模n无关系T(n)=O(1) 2.线性阶:算法的时间复杂度与问题规模n成线性关系T(n)=O(n) 3.平方阶和立方阶:一般为循环的嵌套,循环体最后条件为i++ 时间复杂度的大小比较: O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n )

数据结构课程设计报告模板

课程设计说明书 课程名称:数据结构 专业:班级: 姓名:学号: 指导教师:成绩: 完成日期:年月日

任务书 题目:黑白棋系统 设计内容及要求: 1.课程设计任务内容 通过玩家与电脑双方的交替下棋,在一个8行8列的方格中,进行棋子的相互交替翻转。反复循环下棋,最后让双方的棋子填满整个方格。再根据循环遍历方格程序,判断玩家与电脑双方的棋子数。进行大小判断,最红给出胜负的一方。并根据y/n选项,判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境:vc++6.0 实现目标: (1)熟悉的运用c语言程序编写代码。 (2)能够理清整个程序的运行过程并绘画流程图 (3)了解如何定义局部变量和整体变量; (4)学会上机调试程序,发现问题,并解决 (5)学习使用C++程序来了解游戏原理。 (6)学习用文档书写程序说明

摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋,计算机下棋是人工智能领域中的一个研究热点,多年以来,随着计算机技术和人工智能技术的不断发展,计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的,多的一方为胜,少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时,程序采用削弱对手行动力战术,即尽量减少对手能够落子的位置;在游戏终局时则采用最大贪吃战术,即尽可能多的吃掉对手的棋子;而四角优先战术则是贯穿游戏的始终,棋盘的四角围稳定角,不会被对手吃掉,所以这里是兵家的必争之地,在阻止对手进角的同时,自己却又要努力的进角。 关键词:黑白棋;编程;设计

数据结构基础知识整理

数据结构基础知识整理 *名词解释1、数据:是信息的载体,能够被计算机识别、存储和加工处理。 *2、数据元素:是数据的基本单位,也称为元素、结点、顶点、记录。一个数据元素可 以由若干个数据项组成,数据项是具有独立含义的最小标识单位。 *3、数据结构:指的是数据及数据之间的相互关系,即数据的组织形式,它包括数据的 逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构:指数据元素之间的逻辑关系,即从逻辑关系上描述数据,它与数 据的存储无关,是独立于计算机的。 *5、数据的存储结构:指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结 构用计算机语言的实现,是依赖于计算机语言的。 *6、线性结构:其逻辑特征为,若结构是非空集,则有且仅有一个开始结点和一个终端 结点,并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构:其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法:是任意一个良定义的计算过程,它以一个或多个值作为输入,并产生一个或 多个值作为输出;即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n):是该算法的时间耗费,它是该算法所求解问题规模n趋向无穷大时,我们把时间复杂度T(n)的数量级(阶)称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度:由于算法中语句的频度不仅与问题规模n有关,还与输入实例等因素有关;这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下,算法的期望运行时间。 *11、数据的运算:指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的,而 实现是要在存储结构上进行。 *12、线性表:由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关 系(一个结点对应一个直接后继,除终端结点外;或一个结点对应一个直接前趋,除开始结点外),这是一种线性结构。 *13、顺序表:顺序存储的线性表,它是一种随机存取结构。通过将相邻结点存放在相邻 物理位置上来反映结点间逻辑关系。 *14、单链表:每个结点有两个域:一个值域data;另一个指针域next,用来指向该结

数据结构课程设计报告模板

数据结构课程设计报告模板

课程设计说明书 课程名称:数据结构 专业:班级: 姓名:学号: 指导教师:成绩: 完成日期:年月日

任务书 题目:黑白棋系统 设计内容及要求: 1.课程设计任务内容 通过玩家与电脑双方的交替下棋,在一个8行8列的方格中,进行棋子的相互交替翻转。反复循环下棋,最后让双方的棋子填满整个方格。再根据循环遍历方格程序,判断玩家与电脑双方的棋子数。进行大小判断,最红给出胜负的一方。并根据y/n选项,判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境:vc++6.0 实现目标: (1)熟悉的运用c语言程序编写代码。 (2)能够理清整个程序的运行过程并绘画流程图 (3)了解如何定义局部变量和整体变量; (4)学会上机调试程序,发现问题,并解决 (5)学习使用C++程序来了解游戏原理。 (6)学习用文档书写程序说明

目录 1.引言 (1) 2.课题分析 (4) 3.具体设计过程 (5) 3.1设计思路 (5) 3.2程序设计流程图 (5) 3.3.函数实现说明 (10) 4.程序运行结果 (12) 5.软件使用说明 (16) 6.结论 (19) 参考文献 (20) 附录:源代码 (21)

1.引言 数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解的不同而有不同的表述方法: Sartaj Sahni在他的《数据结构、算法与应用》一书中称:“数据结构是数据对象,以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象(data object)定义为“一个数据对象是实例或值的集合”。Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是:“数据结构是ADT(抽象数据类型Abstract Data Type)的物理实现。” Lobert L.Kruse在《数据结构与程序设计》一书中,将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中,抽象层是指抽象数据类型层,它讨论数据的逻辑结构及其运算,数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。数据结构具体指同一类数据元素中,各元素之间的相互关系,包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。 1.1. 重要意义 一般认为,一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构;数据必须在计算机内存储,数据的存储结构是数据结构的实现形式,是其在计算机内的表示;此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中,数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明,系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候,确定了数据结构后,算法就容易得到了。有些时候事情也会反过来,我们根据特定算法来选择数据结构与之适应。不论哪种情况,选择合适的数据结构都是非常重要的。 选择了数据结构,算法也随之确定,是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现,面向对象的程序设计语言就是其中之一。 1.2. 研究内容

《数据结构(C语言版)》复习重点要点

《数据结构(C语言版)》复习重点 重点在二、三、六、七、九、十章,考试内容两大类:概念,算法 第1章、绪论 1. 数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2. 数据元素:是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 3. 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。 其4类基本结构:集合、线性结构、树形结构、图状结构或网状结构 4. 逻辑结构:是数据元素之间的逻辑关系的描述。 5. 物理结构(存储结构):是数据结构在计算机中的表示(又称映像)。 其4种存储结构:顺序存数结构、链式存数结构、索引存数结构、散列存数结构6. 算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。 其5个重要特性:有穷性、确定性、可行性、输入、输出 7. 时间复杂度:算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作,T(n)=O(f(n));他表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称做算法的渐进时间复杂度,简称时间复杂度。例如: (a) {++x;s=0;} (b) for(i=1;i<=n;++i){++x;s += x;} (c) for(j=1;j<=n;++j) for(k=1;k<=n;++k){++x;s += x;} 含基本操作“x增1”的语句的频度分别为1、n和n2,则这3个程序段的时间复杂度分别为O(1)、O(n)和O(n2),分别称为常量阶、线性阶和平方阶。还可呈现对数阶O(log n)、指数阶O(2的n次方)等。 8. 空间复杂度:算法所需存储空间的度量记作,S(n)=O(f(n))。 第2章、线性表 1. 线性表:是最常用最简单的一种数据结构,一个线性表是n个数据元素的有限序列。 2. 线性表的顺序存储结构:是用一组地址连续的存储单元依次存储线性表的数据元素。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻,可以随机存取表中任一元素。 存储位置计算:假设线性表的每个元素需占用L个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置,线性表的第i个数据元素ai的存储位置为LOC(ai)=LOC(a1)+(i-1)*L 式中LOC(a1)是线性表第一个元素a1的存储位置,通常称做线性表的起始位置或基地址。 3. 线性表的链式存储结构:是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

数据结构实验报告模板

数据结构实验报告 顺序表实验 1.实验目标 a.熟练掌握线性表的顺序存储结构。 b.熟练掌握顺序表的有关算法设计。 c.根据具体问题的需要,设计出合理的表示数据的顺序结构,并设计相关算法。 2.实验内容和要求 a.顺序表结构和运算定义,算法的实现以库文件方式实现,不得在测试主程序中直接实现; b.实验程序有较好可读性,各运算和变量的命名直观易懂,符合软件工程要求; c.程序有适当的注释。 3.数据结构设计 顺序表 4.算法设计 1.i表示要在顺序表中查找的位置,x表示查找到后返回的值。 int search(seqlist A,int i,elementType &x) { if(i<1||i>A.Len)//查找的范围不在顺序表中 return 0; else { x=A.data[i-1];//复制要查找的值 return 1; } } 2.i表示要在顺序表中插入的位置,x表示要插入的元素。 void insert(seqlist &A,int i,elementType x) { if(i<1||i>A.Len)//超出顺序表范围 cout<<"error"<=i;j--)//找到第i-1个结点擦,并后移元素 A.data[j]=A.data[j-1]; A.data[i-1]=x;//插入元素数据 A.Len++;//改变顺序表长度 }

} 3.先利用循环找到顺序表中第i个结点,然后进行删除操作。 void del(seqlist *L,int i) { int j; if(i<1||i>L->Len+1)//超顺序表范围 cout<<"超出表范围"<Len;j++) L->data[j]=L->data[j+1];//删除第i个结点 L->Len--; cout<<"删除元素后的表为:"; for(int k=0;kLen;k++)//输出顺序表 cout<data[k]<<" "; cout<Len==MAXLEN) return 0; else { int i=L->Len-1; L->Len++; while(x<=L->data[i]) { L->data[i+1]=L->data[i];//查找待插入的位置 i--; } L->data[i+1]=x;//插入元素 return 1; } } 5.申请两个新的顺序表,然后对原表进行遍历,由 A.data[i]%2进行及奇偶的分离,并分别存入顺序表B,C中。 void separatelist(seqlist A,seqlist *B,seqlist *C) { int b(0),c(0); for(int i=0;i

数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)

数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。 2、数据的物理结构亦称存储结构,是数据的逻辑结构在计算机存储器内的表示(或映像)。它依赖于计算机。存储结构可分为4大类:顺序、链式、索引、散列 3、抽象数据类型:由用户定义,用以表示应用问题的数据模型。它由基本的数据类型构成,并包括一组相关的服务(或称操作)。它与数据类型实质上是一个概念,但其特征是使用与实现分离,实行封装和信息隐蔽(独立于计算机)。 4、算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,是一系列输入转换为输出的计算步骤。 5、在数据结构中,从逻辑上可以把数据结构分成( C ) A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于( A ) A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均次数为( E ),删除一个元素需要移动的元素的个数为( A )。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是( B ) A、正确的 B、错误的 C、不一定,与具体的结构有关 4、线性表采用链式存储结构时,要求内存中可用存储单元的地址( D ) A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是( B ) A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是( A ) A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足( C ) A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( B ) A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中,若删除p所指结点的后继结点,则执行( A )

数据结构实验报告模板

2009级数据结构实验报告 实验名称:约瑟夫问题 学生姓名:李凯 班级:21班 班内序号:06 学号:09210609 日期:2010年11月5日 1.实验要求 1)功能描述:有n个人围城一个圆圈,给任意一个正整数m,从第一个人开始依次报数,数到m时则第m个人出列,重复进行,直到所有人均出列为止。请输出n个人的出列顺序。 2)输入描述:从源文件中读取。 输出描述:依次从显示屏上输出出列顺序。 2. 程序分析 1)存储结构的选择 单循环链表 2)链表的ADT定义 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系:R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作: ListInit(&L);//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表,若是,则返回1,否则返回0. ListLength(L); //求单链表L的长度 GetElem(L,i);//返回链表L中第i个数据元素的值; ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除,使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数: 主函数; 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template class CirList;//声明单链表类 template class ListNode{//结点类定义; friend class CirList;//声明链表类LinkList为友元类; Type data;//结点的数据域; ListNode*next;//结点的指针域; public: ListNode():next(NULL){}//默认构造函数; ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值; ListNode*GetNodePtr(){return next;}//返回结点的指针域的值; void SetNodeData(Type&e){data=e;}//设置结点的数据值; void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值; }; 单循环链表类: templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数,建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数,删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继,若不输入参数,则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继,且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构图习题

第七章图:习题 习题 一、选择题 1.设完全无向图的顶点个数为n,则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2.在一个无向图中,所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3.有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4.在无向图G (V,E)中,如果图中任意两个顶点vi、vj (vi、vj∈V,vi≠vj)都的,则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5.若采用邻接矩阵存储具有n个顶点的一个无向图,则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6.若采用邻接矩阵存储具有n个顶点的一个有向图,顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7.对于具有e条边的无向图,它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8.对于含有n个顶点和e条边的无向连通图,利用普里姆Prim算法产生最小生成时间复杂性为( ),利用克鲁斯卡尔Kruskal算法产生最小生成树(假设边已经按权的次序排序),其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9.对于一个具有n个顶点和e条边的有向图,拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10.在一个带权连通图G中,权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1.在一个具有n个顶点的无向完全图中,包含有____条边;在一个具有n个有向完全图中,包含有____条边。 2.对于无向图,顶点vi的度等于其邻接矩阵____ 的元素之和。 3.对于一个具有n个顶点和e条边的无向图,在其邻接表中,含有____个边对于一个具有n个顶点和e条边的有向图,在其邻接表中,含有_______个弧结点。 4.十字链表是有向图的另一种链式存储结构,实际上是将_______和_______结合起来的一种链表。 5.在构造最小生成树时,克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法;普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6.对用邻接表表示的图进行深度优先遍历时,其时间复杂度为一;对用邻接表表示的图进行广度优先遍历时,其时间复杂度为_______。 7.对于一个具有n个顶点和e条边的连通图,其生成树中的顶点数为_______ ,边数为_______。 8.在执行拓扑排序的过程中,当某个顶点的入度为零时,就将此顶点输出,同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零,需要设立一个____来存放入度为零的顶点。

西安交通大学大数据结构复习资料

第一章绪论 1、数据结构的主要研究内容 ①数据的逻辑结构--数据关系之间的逻辑关系 ②数据的存储结构--数据的逻辑结构在计算机中的表示 2、数据逻辑结构的种类:集合、线性表、树和图的性质和特点。 ?集合结构中的元素是各自独立的,元素之间没有联系 ?线性结构中的元素是一个接一个串联起来的,它有一个头元素和一个尾元素,其余为中间元素;每个中间元素既有前驱元素,又有后继元素 ?在树结构中,树根结点只有后继结点,而没有前驱结点;除树根结点外,每个结点都有唯一一个前驱结点,又称为是父结点或双亲结点 ?在图结构中,每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结点。 ?树结构是图结构的特例,线性结构是树结构的特例。为了区别于线性结构,时常把树结构和图结构称为非线性结构。 3、数据结构的二元组定义,能根据给出的二元组来判断数据的逻辑结构类型。 ?集合结构中的元素集合K和二元关系R分别为: K={A,B,C,D,E,F,G} R={ } ?线性结构中的元素集合K和二元关系R分别为: K={A,B,C,D,E,F,G} R={} ?树结构中的元素集合K和二元关系R分别为: K={A,B,C,D,E,F,G} R={} ?图结构中的元素集合K和二元关系R分别为: K={A,B,C,D,E,F,G} R={} 4、了解数据的几种存储结构(物理结构)及它们各自的性质和特点。 (1)顺序的方法: 将逻辑上相邻的元素存储到物理上相邻的存储位置. 常用于线性的数据结构. (2)链式结构:给结点附加一个指针字段, 指出其后继节点的位置, 即存放结点的存储单元分为两部分: (3)散列(hashing) 结构:散列的方法是用结点的关键字值直接计算出结点的存储地址。这个取值函数也称为散列函数。 5、数据的逻辑结构、存储结构和总的数据结构之间的关系 ?逻辑结构相同,但存储结构不同,则认为是不同的数据结构。如顺序表和链表具有相同的逻辑结构,但存储结构分别为顺序结构和链表结构 6、算法的设计要求有那些,会结合实际的语言设计来说明这些要求 1)正确性:对于合法的输入产生符合要求的输出;

数据结构名词解释整理

Data Structure 2015 hash table散列表:存放记录的数组 topological sort拓扑排序:将一个DAG中所有顶点在不违反前置依赖条件规定的基础上排成线性序列的过程称为拓扑排序(44) worst case 最差情况:从一个n元一维数组中找出一个给定的K,如果数组的最后一个元素是K,运行时间会相当长,因为要检查所有n 个元素,这是算法的最差情况(15) FIFO先进先出:队列元素只能从队尾插入,从队首删除(20)(P82)2014 growth rate增长率:算法的增长率是指当输入的值增长时,算法代价的增长速率(14) priority queue 优先队列:一些按照重要性或优先级来组织的对象成为优先队列(26) external sorting外排序:考虑到有一组记录因数量太大而无法存放到主存中的问题,由于记录必须驻留在外存中,因此这些排序方法称为外排序(32) connected component连通分量:无向图的最大连通子图称为连通分量(40) 2013 stack栈:是限定仅在一端进行插入或删除操作的线性表(19)

priority queue 优先队列:一些按照重要性或优先级来组织的对象成为优先队列(26) BFS广度优先搜索:在进一步深入访问其他顶点之前,检查起点的所有相邻顶点(42) collision (in hashing)冲突:对于一个散列函数h和两个关键码值k1和k2,如果h(k1) =β= h(k2) ,其中β是表中的一个槽,那么就说k1和k2对于β在散列函数h下有冲(35) Chapter 1 Data Structures and Algorithms type类型:是指一组值的集合 data type数据类型:一个类型和定义在这个类型上的一组操作abstract data type (ADT) 抽象数据类型:指数据结构作为一个软件构件的实现 data structure数据结构:是ADT的实现 problem问题:一个需要完成的任务,即对应一组输入,就有一组相应的输出 function函数:是输入和输出之间的一种映射关系 algorithm算法:是指解决问题的一种方法或者一个过程algorithm算法是解决问题的步骤,它必须把每一次输入转化为正确的输出;一个算法应该由一系列具体步骤组成,下一步应执行的步骤必须明确;一个算法必须由有限步组成;算法必须可以终止。computer program计算机程序:被认为是使用某种程序设计语言对一个算法的具体实现

相关文档
相关文档 最新文档