数据结构数组与广义表知识点总结

题目部分，(卷面共有95题,608.0分,各大题标有题量和总分)

一、单项选择题(22小题,共44.0分) (2分)[1]

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为 A、 13 B、 33 C、 18 D、 40 (2分)[2]

二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,?,8,列下标j=1,2,?,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

A、 A[8,5] B、 A[3,10] C、 A[5,8] D、 A[0,9] (2分)[3]

已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =

A、（a） B、 A C、 a D、（b） E、 b

第四章 多维数组和广义表

1. 多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。

2. 一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。

同一数组的不同元素通过不同的下标标识。（a1,a2,…,an) 3. 二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。

4. 多维数组: 三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量……

三维数组中的每个元素aijk都属于三个向量。四维数组中的每个元素都属于四个向量……

5. 数组的顺序存储方式: 由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。 （1）行优先顺序：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。 【例】二维数组Amn的按行优先存储的线性序列为： a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2

题目部分，(卷面共有95题,608.0分,各大题标有题量和总分)

一、单项选择题(22小题,共44.0分) (2分)[1]

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为 A、 13 B、 33 C、 18 D、 40 (2分)[2]

二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,?,8,列下标j=1,2,?,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

A、 A[8,5] B、 A[3,10] C、 A[5,8] D、 A[0,9] (2分)[3]

已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =

A、（a） B、 A C、 a D、（b） E、 b

第 5 章 数组和广义表

一、选择题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。【燕山大学 2001 一、2 （2分）】

A. 13 B. 33 C. 18 D. 40

2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：【上海海运学院 1998 二、2 （5分）】

①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 23

第五章数组和广义表：习题

习 题

一、选择题

1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单

元，基地址为10，则LOC(A[5，5])=( )。 A. 808 B. 818 C. 1010 D. 1020 2．同一数组中的元素( )。

A. 长度可以不同 B．不限 C．类型相同 D. 长度不限

3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范

圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。 (1)存放A至少需要( )个字节。

(2)A的第8列和第5行共占( )个字节。

(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址

一致。

供选择的答案：

(1)A. 90 B. 180 C. 240 D. 270 E.540 (2) A. 108 B. 114 C. 54 D. 60 E.150 (3)A.A[8][5]

数据结构学习总结

壹、研究对象及基本概念

首先从数据结构是什么开始，数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。主要研究：1、数据的逻辑结构，即数据关系之间的逻辑关系；2、数据的存储结构（即物理结构），即数据的逻辑结构在计算机中的表示；3、操作算法，即插入、删除、修改、查询、排序等操作。

一、从数据的逻辑结构划分，即数据之间的逻辑关系从线性分析的角度划

分主要有线性结构和非线性结构。线性结构又可细分为线性表、栈、队列、串、数组。非线性结构又可细分为树型结构和图结构。

线性结构: 线性表、栈、队列、串、数组 树结构

逻辑结构 非线性结构 图结构 二、从存储结构划分 物理结构

顺序结构 链式结构 索引结构 散列结构 各自的定义及特点：

1、顺序存储：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来直接体现。

优点：随机存取表中元素。缺点：插入和删除操作需要移动大量结点。

2、链式存储：它不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。

它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存

第5章 数组和广义表

前面几章我们讨论了线性表、栈、队列和串都是线性数据结构，它们的组成元素都是数据元素，元素的值都是不可分解的。而这章将要讨论的数组和广义表是一种复杂的线性结构，它的组成元素是可以分解的。数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 数组的定义与存储

数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。

5.1.1 数组的定义

数组是由n(n>1)个相同类型的数据元素a0，al，…，ai，…，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，它可以是整型、实型等简单数据类型，也可以是数组、结构体、指针等构造类型。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。

1.一维数组

一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。一维数组记为A[n]或A=( a0，al，…ai，…，an-1)。

一维数组中，一旦a0的存储地址、一个数据元素所占存储单元数k确定，则

习题五 数组和广义表

一、单项选择题

1．常对数组进行的两种基本操作是（ ）

A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引

2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.

A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k

B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k

3．稀疏矩阵的压缩存储方法是只存储 ( )

A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175 B. 1180

第4～5章 串和数组

一、填空题

1. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。

2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为 3 。

4. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。

5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。

6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为 (n-m+1)*m 。

7. 假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基

×

地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。 (注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！)

8.设数组a

数据结构与算法

一知识点：

1.复杂度分析

2.线性表

2.1顺序表、链表特点

2.2顺序表的插入，删除；单链表的插入，删除；，查找，合并，单链表的综合运用；

2.3双链表的插入，删除；

3.栈与队列

3.1栈概念、操作；栈的应用

3.2队列概念、操作；队列的应用

3.3递归

4.字符串

4.1 字符串概念

4.2 模式匹配概念、简单模式匹配算法

5. 二叉树

5.1 二叉树概念、性质

5.2 完全二叉树概念、性质

5.3 满二叉树定义、性质

5.4 二叉树的遍历算法实现（递归与非递归）、线索二叉树的操作

5.5二叉搜索树概念及查找、插入、删除算法

5.6 A VL树概念；A VL树平衡化旋转，插入算法，删除算法

5.7 堆；堆的初始化、堆的插入、删除算法

5.8 Huffman树；Huffman编码

6. 树的概念，树的周游，森林的周游；树、森林与二叉树之间的转换

7. 图的性质

7.1图的性质、图的存储、图的遍历（DFS，BFS）

7.2最小生成树概念，Prim算法，Kruscal算法

7.3最短路径算法：Dijkstra 算法，Floyd算法

7.4拓扑排序，关键路径

8. 查找

8.1静态查找【顺序查找、二分法查找、分块查找】

8.2 动态查找技术：B树、B+树概念、性质；B树插入、删除的调整