数据结构基础题复习
数据结构基础题
1、数据结构概念相关
（1）（ B数据对象 ）是性质相同的数据元素的集合，是数据的子集。
A、数据元素 B．数据对象 C．数据结构 D．数据项
分析：看下图，表中每一行(相当于结点中每一个结点)就是一个数据元素；数据元素中的每一项，比如张三的数学分析是90分就是一个数据项；整个表格是一个数据对象，它代表的都是学生的信息(具有相同性质的数据元素的集合)。
2、数据的存储结构与逻辑结构
知识点介绍：
（1）把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ A 物理结构 ）。
A．物理结构 B．逻辑结构 C．算法的具体实现 D．给相关变量分配存储单元
（2）数据结构中，与所使用的计算机无关的是数据的（ D 逻辑 ）结构。
A．物理 B．存储 C．逻辑与物理 D．逻辑
（3）根据数据元素间关系的不同特性，通常可分为集合、 线性 、 树形 、 图状 四类基本结构。
（4）数据结构中的数据元素存在“一对多”的关系称为 树形 结构。
（5）同一种逻辑结构可以用不同的存储结构实现。（ T ）
例如：线性表可以用顺序表实现，也可以用链表实现。
3、算法概念
知识点：算法是对特定问题求解步骤的一种描述。
（1）算法的5个特征包括： 有穷性 、 确定性 、有效性、输入和输出。
分析：算法的5个特性，详见书P13
（2）从n个数中选取最大元素（ C ）。
A．基本操作是数据元素间的交换 B．算法的时间复杂度是 O(n2)
C．算法的时间复杂度是 O(n) D．需要进行(n+1)次数据元素间的比较
分析：下面是求最大值的流程图，从中可以看到循环的次数是n次，所以它的时间复杂度为O(n)，其实只要是n的数量级的，时间复杂度都为O(n)。
（3）算法的时间复杂度与（ C．算法本身 ）有关。
A．所使用的计算机 B．计算机的操作系统 C．算法本身 D．数据结构
分析：由上图可知，算法的时间复杂度只和算法本身有关。
（4）以下算法的时间复杂度为( A )。
public int fun(int n){
int j=0;
for (int i=1;i<=n;i++)
j=j+i;
return j;
}
A. O(n) B. O(n2) C.O(nlog2n) D.O(log2n)
分析：算法时间复杂度，取决于关键步骤的执行次数，由这个算法分析，关键是循环体内部内容。循环执行的次数，由循环控制条件控制。该控制条件的执行次数为n，所以时间复杂度为O（n）
（5）所谓最坏的时间复杂度是指在最坏的情况下估算算法在执行时间上的一个上界。（ T ） 分析：比如顺序表的插入中，最坏时间复杂度是插入位置在第1个位置的情况。
（6）一个算法可以无限制的执行下去。（ F ） 分析：算法的5个特性之一是有穷性。
4、顺序表相关内容
A、顺序表的插入操作
知识点介绍：
（1）设顺序存储的线性长度为 n，要在第 i（0<=i<=n-1）个元素之前插入一个新元素，当 i= （ D ）时，移动元素次数为 2。
A．n/2 B．n C．1 D．n-2
分析：按照上图介绍，把第n-1个元素移动到n，把第n-2个元素移动到n-1，就完成了两次移动。
（2）设顺序存储的线性表长度为 n，对于插入操作，设插入位置是等概率的，则插入一个元素平均移动元素的次数为（ A ）。
A．n/2 B．n C．n-1 D．n-i+1
0 8
1 7
2 6
3 5
4 4
5 3
6 2
7 1
8 0
36/9 = 4
分析：如插入位置在第n，则移动0个元素；如插入位置在第n-1，则移动1个元素；如插入位置在第n-2，则移动2个元素；……；如插入位置在第0，则移动n个元素。
总的移动次数为0+1+2+3+…+n=n(n+1)/2，一共n+1种情况，所以平均移动次数是n/2。
（3）对于顺序表，在编号为i处插入一个新元素的时间复杂度为（ A ）。
A. O(n) B. O(1) C.O(nlog2n) D.O(log2n)
分析：从上题可以看到移动次数分别是0、1、2、…、n，是n的数量级，所以时间复杂度是O(n)。
B、顺序表的删除操作
知识点介绍：
（1）设有一个长度为n的顺序表，要删除第i(0<=i<=n-1)个元素，需移动元素的个数为 __ n-i-1 。
N=8，删除第i=7个元素，移动n-i-1 = 0
N=8, 删除第i=6个元素，移动n-i-1 = 1
分析：如上图所示，删除第i个元素，需要移动的元素从第i+1到第n-1，一共是(n-1)-(i+1)+1=n-i-1个元素。
（2）一个长度为n的顺序表从0开始编号，为了删除位序号为4的元素，从前到后依次移动了15个元素。则原顺序表的长度为 20 。
分析：移动元素的编号从5到n-1， 则移动元素个数为(n-1)-5+1=n-5＝15，所以n为20（或直接套用公式：n-4-1=15, 则n=20 ）
（3）设顺序存储的线性表从0开始编号，长度为n，要删除第i（0<=i<=n-1）个元素，当i= n-4 时，移动元素的次数为3。
分析：移动元素的编号从i到n-1， 则移动元素个数为(n-1)-i+1=n-i-1＝3，所以i=n-4
（4）设顺序存储的线性表长度为 n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（ A ）。
A．(n-1)/2 B．n C．2n D．n-i
分析：删除第n-1个位置的元素需要移动0个元素；删除第n-2个位置的元素需要移动1个元素；…；删除第1个位置的元素需要移动n-2个元素；删除第0个位置的元素需要移动n-1个元素。共移动元素个数为0+1+2+…+(n-2)+(n-1)=(n-1)n/2，一共有n个移动位置，所以平均移动次数是(n-1)/2。
（5）在包含n个元素的顺序表中删除一个元素，需要平均移动 (n-1)/2 个元素，其中具体移动的元素个数与 被删除元素的位置 有关。
5、链表相关内容
（1）在一个单链表中，在p 所指结点之后插入一个 s 所指的结点时，可执行（ D ）。
A．p.setNext(s); s.setNext(p.getNext()); B．p.setNext(s.getNext());
C．p=s.getNext(); D．s.setNext(p.getNext()); p.setNext(s);
分析：单链表的插入如下图
6、顺序表和链表的比较
知识点介绍：
1、顺序表的查找比较方便，直接给出下标i就可找到；但链表的查找必须要从头开始逐个比对。
2、顺序表的插入要把第i到第n-1个结点移动到后一个，空出位置后插入，顺序表的删除要把第i+1个到第n个移动到前一个位置；而链表的插入和删除不需要移动结点的数据，修改指针就可以了。
（1）顺序表的最大优点是( A )。
A.存储密度大 B.插入运算方便
C.删除运算方便 D.可以方便地用于各种逻辑的存储表示
存储密度： 存储元素需要的空间/元素实际占用的空间
顺序表的存储密度是1
链表的存储密度小于1
（2）线性表采用链式存储时，其地址（ C ）。
A．一定是不连续的 B．必须是连续的
C．可以连续也可以不连续 D．部分地址必须是连续的
（3）下述各线性结构中可以随机访问的是（ D ）。
A. 单向链表 B. 双向链表 C.单向循环链表 D. 顺序表
（4）线性表的顺序结构中，进行数据元素的插入、删除效率较高。（ F ）
（5）线性表采用链式存储便于插入和删除操作的实现。（ T ）
（6）线性表的链式结构中，数据元素是不能随机访问的。（ T ）
（7）线性表采用链式存储可以不必占用一片连续的存储空间。（ T ）
（8）线性表的顺序结构中，逻辑上相邻的元素在物理位置上也相邻。（ T ）
7、栈相关的知识
A、栈的插入和删除
（1）栈的插入操作在（ A ）进行。
A．栈顶 B．栈底 C．栈顶或栈底 D．在任意指定位置
分析：栈的插入和删除操作都在栈顶，特点是先进后出或后进先出。
B、进栈和出栈的顺序
\1. 一个栈的进栈序列是1，2，3，4，则不可能的出栈序列是（ B ）（进出栈操作可以交替进行）。 2314 1234 1324
A．3，2，4，1 B．1，4，2，3 C．4，3，2，1 D．3，2，1，4
分析：按选择项B的进栈和出栈过程，如下图，不可能做到2比3先出栈。
C、链式栈的出栈和入栈
- 设 top 是一个链栈的栈顶指针，栈中每个结点由一个数据域 data 和指针域 next 组成，设用 x 接收栈顶元素，则出栈操作为（ A ）。
A．x=top.getData(); top=top.getNext(); B．top=top.getNext();x=top.getData();
C．x=top.getNext(); top=top.getData(); D．top.setNext(top); x=top.getData();
分析：栈的删除和插入都在栈顶进行，整个过程如下图。
D、其它
（1）栈的两种最基本的存储方式分别是 顺序存储 和 链式存储 。
（2）栈可以用顺序结构实现，也可以使用链表结构实现。（ T ）
（3）浏览器记录用户的访问地址以实现“回撤”操作，可以通过“队列”结构来实现。（F ）
分析：这个操作应该是栈的结构来实现的，比如回撤了两次，肯定是先回撤到后访问的地址，是后进先出。
（4）“递归”的过程可以使用“队列”实现。（ F ）
分析：这也是用栈来实现的。
8、队列相关的知识
A、队列的插入和删除
（1）队列的插入操作在（ B．队尾 ）进行。
A．队头 B．队尾 C．队头或队尾 D．在任意指定位置
分析：队列的插入在队尾，队列的删除操作在队头，特点是先进先出或后进后出。
B、队列的入队和出队
（1）一个队列的入队序列是2，4，6，8，则队列的输出序列是（ B ）。
A．8，6，4，2 B．2，4，6，8 C．4，2，8，6 D．6，4，2，8
分析：队列和栈是有区别的，队列是先进先出，所以不可能有多种可能。
C、链式队列的出队和入队
（1）设有一个带头结点的链队列，队列中每个结点由一个数据域 data 和指针域 next 组成，
front 和 rear 分别为链队列的头指针和尾指针。设 p 指向要入队的新结点(该结点已被
赋值)，则入队操作为（ A ）。
A．rear.setNext§; rear=p; B．rear.setNext§; p = rear;
C．p = rear.getNext(); rear=p; D．rear=p; rear.setNext§;
分析：
（2）在一个链队列中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的操作为（ B ）。
A．f.setNext(s); f=s; B．r.setNext(s); r=s;
C．s.setNext®; r=s; D．s.setNext(f); f=s;
分析：如上题，只不过把rear换成r，p换成s
D、其它
（1）以下说法正确的是（ C ）。
A．栈的特点是先进先出，队列的特点是先进后出
B．栈和队列的特点都是先进后出
C．栈的特点是先进后出，队列的特点是先进先出
D．栈和队列的特点都是先进先出
分析：栈是先进后出，队列是先进先出
（2）栈和队列的相同点是（ D ）。
A．都是后进先出 B．都是后进后出 C．逻辑结构与线性表不同
D．逻辑结构与线性表相同，都是操作规则受到限制的线性表
分析：栈是先进后出，队列是先进先出
（3）以下说法不正确的是（ C ）。
A．栈的特点是后进先出
B．队列的特点是先进先出
C．栈的删除操作在栈底进行，插入操作在栈顶进行
D．队列的插入操作在队尾进行，删除操作在队头进行
分析：栈的插入和删除操作都在栈顶进行。
9、字符串相关的知识
（1）设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）。
A．求子串 B．串的联接 C．串的模式匹配 D．求串长
分析：
（2）下面关于串的叙述中，不正确的是：（ B ）。
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
分析：空串是长度为0的串，而空格串中空格也是字符，两者是不同的。
（3）串的长度是指（ B ）。
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
（4）若两个串有相同的字符集，则说明两个串相等。（ F ）
分析：
（5）串中任意多个连续的字符组成的子序列称为该串的子串。（ T ）
（6） 空 串是任意串的子串，任意串是其自身的子串。
ABC=A，B,C,AB,BC,ABC,空串
10、矩阵压缩
（1）设一个20阶的对称矩阵A(其首元素为A[0][0])，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从0开始），则矩阵中元素A[8][1]在一维数组B中的下标是 。
分析：由下图可知，从第1行算起，一共有元素1+2+3+4+5+6+7+8+2=38，下标从0算起，所以A[8][1]按一维数组来排是37。
（2）若按照压缩存储的思想将n!（n阶、n*n）的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B中，那么，A中任一个下三角元素aij(i≥j≥0)在数组B中的下标位置k(k≥0)为（ B ）。
A. i(i-1)/2+j-1 B. i(i+1)/2+j C. (i-1)(i-2)/2+j D. j(i-1)/2+i 分析：按上图分析，把A[8][1]换成A[i][j]，所以元素个数为1+2+…+i+(j+1)=
，然后再考虑到第1个元素编号为0，所以最后答案为
（3）特殊矩阵压缩是为了去掉矩阵中多余元素。（ F ）
（4）特殊矩阵压缩是减少不必要的存储空间。（ T ）
分析：因为在特殊矩阵中有很多零项或是重复项，为了节省空间，对它们进行压缩。
（5）采用十字链表表示一个稀疏矩阵，每一个非零元素一般用一个含有 5 个域的结点表示。
分析：对于一些零元素较多的矩阵，可以用如右图的十字链表表示，参考书P142页
11、二叉树的遍历
（1）一颗二叉树的中序序列为 ABDCEFG，后序序列为 BDCAFGE, 则其左子树中的结点个数为（ C ）。
A．3 B．2 C. 4 D.5
**分析：由后序遍历BDCAFGE中可知E为根结点；由前序遍历ABDCEFG可知ABDC在E的左面，FG在E的右面。所以左子树有4个结点。
（2）对二叉树的结点从0开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ C ）遍历实现。A．前序 B．中序 C．后序 D．层次
分析：在每个左中右结点中，要求左<右<中，那么顺序就是左右中，是后序。
（3）若二叉树的中序遍历结果是 abcdef，且 c 为根结点，则（ A ）。
A．结点c 有两颗子树 B．二叉树有两个度为 0 的结点
C．二叉树的高为 5 D．以上都不对
分析：c 为根结点，中序是abcdef，所以ab为左子树的两个结点，def为右子树的结点。
12、完全二叉树
**完全二叉树中满足以下条件：
**1**、前**n-1**层都是满的；
**2**、最后一层不能只有右孩子却没有左孩子，但可以只有左孩子却没有右孩子
（1）一棵完全二叉树共有30个结点，则该树的**高度是 5 。
Log2[n+1] 向上取整=log2[31] 求树的深度
分析：因为完全二叉树的前n-1层都是满的，所以30个结点的完全二叉树应该是如下图，所是高度为5。
（2）设只有1个结点的二叉树的深度为1，则深度为k的完全二叉树至少有 2k-1 个结点，至多有 2k-1 个结点。
分析：由上图可知，深度为k的完全二叉树中前k-1层是满的，所以有1+2+4+8+…+2k-2=2k-1-1，最后一层上至少有一个结点，所以总的为2k-1。
最多的情况下是k层也是满的，总结点数为1+2+4+8+…+2k-1=2k-1
（3）将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按**从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为( D )。
A.42 B. 40 C. 21 D. 20
( 4 )将含有62个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为26的结点的双亲结点编号为( A )。
A.13 B. 12 C. 21 D. 20
分析：在完全二叉树中，若编号从1开始，则编号为i的结点，如果有左儿子，则编号为2i，如果有右儿子，则编号为2i+1。
（5）一颗完全二叉树的结点个数为 100，从0开始自上而下、自左至右的顺序对结点进行连续编号，则第 60 个结点的度为（ A ）。
A．0 B．1 C．2 D．不确定
分析：在完全二叉树中，若编号从0开始编号i的结点，如果有左儿子，则编号为2i+1，如果有右儿子，则编号为2i+2。
第60个结点的编号为59，如果有左儿子，则编号为59*2+1=119，右儿子如果有的话，编号为120。而结点数一共是100个，所以第60个结点肯定没有儿子，是叶子结点，度为0。
（6）假设只有1个结点的二叉树的深度为1，具有256个结点的完全二叉树的**深度为 9 。
log2(256+1) 向上取整=9
2^8 = 256
分析：按照上面的定义，一个深度为k的完全二叉树，前k-1层是满二叉树，总结点数为2k-1-1，所以这里k取9， 29-1-1=255，最后第k层只有一个结点。
（7）若对含 n 个结点的完全二叉树从上到下且从左至右进行 0至 n-1 的编号，则对完全二叉树中任意一个编号为 i 的结点，以下正确的是（ C ）。
A. 编号为(i-1)/2的结点为其双亲结点。
B. 编号为 2i+1 的结点为其左孩子结点。
C. 该结点是层次遍历时访问的第i+1个结点（规定根结点为第一个访问到的结点）。
D. 以上都不正确。
分析: A答案没有说明向下取整就正确，所以不正确; B答案 若2i+1>n，则该结点没有左孩子，所以不正确; C答案依据题设是正确的; D答案是干扰选项
（8）从0开始，自顶向下、自左向右对一棵二叉树进行顺序编号，则编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为_ 2i+1_、__**2i+2\ ______。
（9）完全二叉树一定存在度为1的结点。 ( F )
分析：度为1就是一个结点只有一个儿子（如下图左），完全二叉树中可能没有度为1的结点（如下图右）。
13、满二叉树
（1）一棵满二叉树的结点个数为n，高度为h，则n= 2h-1 。
分析：前面完全二叉树中已经介绍过，一棵满二叉树的结点个数n=2h-1。
（2）高度为h的二叉树最大结点个数为：（ C ） 。
A．2h B．2h-1 C．2h-1 D．2h-1-1
（3）对于一个具有n个结点的二叉树，当它为一棵 **满\ 二叉树时具有最小高度。
14、哈夫曼树
（1）一棵哈夫曼树共有 n 个非叶结点，则该树一共有（ B ）个结点。
A. 2n-1 B. 2n +1 C. 2n D. 2(n-1)
分析：按照书P154的性质3，二叉树中的叶结点数正好是双分支的结点数＋1，而哈夫曼树中只有叶结点和双分支结点。所以叶结点有n+1个，总的结点数为2n+1。
（2）设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有 2n0-1 个结点。
\3. 对5个字符进行哈夫曼编码，不可能的编码结果是：（ C ）。
A．111，110，10，01，00 B．000，001， 010，011，1
C．100，11，10，1，0 D．001，000，01，11，10
分析：哈夫曼编码中不允许存在前缀码，也就是一个编码是另一个编码的前面一部分，比如C选择项中1是100、11、10的前缀码，10是100的前缀码。
15、树的其它内容
（1）树形结构最适合用来表示（ C ）。
A．有序数据元素 B. 无序数据元素
C．数据元素之间存在层次关系的数据 D. 元素之间无联系
（2）对于一颗有 n 个结点、度为 4 的树来说，（ A ） 。
A．树的高度最多为 n-3 B．树的高度最多为 n-4
C．第 i 层上最多有 4(i-1)个结点 D．至少在某一层上正好有 4 个结点
分析：极端情况是每一层上都只有一个分支，但度为4要求树至少有一个结点有4个分支，这个结点的3个分结点是没有儿子的。这种情况下高度为n-3。如下图所示。
（3）对于一棵高度为h、度为4的树来说，（ A ） 。
A．至少有h+3个结点 B．至多有4h-1个结点
C．至多有4h个结点 D．至少有h+4个结点
分析：如上图所示，极端情况是除了一个结点的分支有4个以外，其他结点都只有一个分支，总的结点是（h-1）+4=h+3。
（4）对于一颗有50个结点的，度为3的树来说，其最小高度为（ C ） 。
A．3 B．4 C．5 D．6
分析：极端情况是第1层1个结点，第2层3个结点，第3层9个结点，第4层27个结点，一共是40个结点，再加上第5层有10个结点，共50个结点。
（5）一棵有20结点的二叉树，其2度结点数的个数为8，则该树共有 3 个1度结点。
分析：按照书P154的性质3，二叉树中的叶结点数正好是双分支的结点数＋1，2度结点是8个，那么0度结点是9个，总共有20个结点，所以1度结点是3个结点。
（6）数组不适合作为任何二叉树的存储结构。（ **F\ ）
16、生成树和最小生成树
知识点介绍：
\1. 生成树是把图中的所有顶点连通，不形成回路，而且边是原图中的一部分。
\2. 生成树的项点和原图中的顶点是相同的，边是原图的一部分，而且如有n个顶点，则生成树的边数为n-1。
\3. 具有最小权的生成树称为图的最小生成树，同一个图的最小生成树不唯一。
（1）任何一个连通无向图，其最小生成树（ A ）。
A. 有一棵或多棵 B. 一定有多棵 C. 可能不存在 D. 一定只有一棵 分析：同一个图的最小生成树不唯一
（2）连通图G的生成树一定是连通而不包含回路的。（ T ）
（3）一个无向连通图的生成树是含有该连通图的全部顶点的（ A ）。
A. 极小连通子图 B.极小连通图 C. 极大连通子图 D. 极大子图
分析：生成树中只要少一条边，该图就不连通了，所以是极小连通子图。
( 4 ) 已知一个网的形式如下：
l 请利用克鲁斯卡尔算法构造该网的最小生成树，绘制每一步构造过程情况。
l 请利用普里姆(Prim)算法从a点出发构造该网的最小生成树，绘制每一步构造过程情况。
克鲁斯卡尔算法，生成图的最小生成树，步骤：
普里姆(Prim)算法从a点出发构造该网的最小生成树，步骤：
17、图的遍历
（1）如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ C ）。
A．abedfc B．acfebd C．aebcdf D．aebcfd
图1
分析：详见综合题复习中的讲评。从a出发的广度优先搜索中紧接着的三个结点肯定是ebc（这3个的顺序可以不一样），而A、B不满足上述条件；D中既然第二层次是e在前面，那么第三层次的访问中应该是e的邻接结点d在前面，所以不正确。
（2）采用邻接表存储的**图的宽度优先搜索算法类似于二叉树的\（ D ）。
A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 层次序遍历
分析：见下图，相当于层次遍历。
（3）采用邻接表存储的**图的深度优先搜索算法类似于二叉树的\（ A ）。
A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 层次序遍历
分析：下图左面是深度优先搜索的访问顺序，右面是模拟的二叉树，该二叉树的前序遍历与深度优先遍历相同。
（4）如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有的顶点。则该图一定是一个（ B ）。
A. 完全图 B.连通图 C. 有回路 D. 一棵树
18、图的其它知识
（1）具有6个顶点的无向图至少应有( A )条边才能确保是一个连通图。
A. 5 B. 6 C. 7 D. 8
分析：6个顶点至少要6－1＝5条边才可以把它连通，而且它是一棵树。
（2）有n个顶点的无向完全图具有 **n(n-1)/2\ 条边。
分析：**下图是一个有4个结点的完全无向图，每一个结点和其余的结点都有一条边。一共有n(n-1)/2=4(4-1)/2=6条边。\
（3）若用n表示图中顶点数，则有 **n(n-1)/2\ 条边的无向图称为完全图。
（4）具有20个顶点的无向图，边的总数最多为 190 条。
分析：如果是无向图，每个顶点度的最大值是该顶点与其余的n-1个顶点都相连，度为n-1；这里是有向图，所以与每个顶点相连的有两条边，最后的度为2(n-1)
下面的6－9是关于邻接矩阵的，邻接矩阵中如下：
² 无向图的邻接矩阵是对称的。
² 顶点vi的度是第i行或第i列中“1”的元素个数。
（6）将一个具有n个顶点e条边的无向图存储在邻接矩阵中，则非零元素的个数是 2e 。
分析：e条边无向图的邻接矩阵中应该有2e个非零元素。
（7）对于一个具有n个顶点e条边的有向图存储在邻接矩阵中，则非零元素的个数是 _e 。分析：因为是有向图，所以每条边对应一个非零元素。
（8）有10个顶点的连通图用邻接矩阵表示时，该矩阵至少有 10 个非零元素。
分析：10个顶点的无向连通图，至少需要9条边，矩阵中有 18 非零元素
10个顶点的有向连通图，至少需要10条边，矩阵中有 10 非零元素
19、查找
（1）对线性表进行二分查找时，要求线性表必须( B )。
A.以顺序方式存储 B.以顺序方式存储，且结点按关键字值有序排列
C.以链接方式存储 D.以链接方式存储，且结点按关键字值有序排列
分析：有序表才能用二分法来进行查找。
（2）设有200个元素组成的线性表，用二分法检索，最大的比较次数是 ( A ) 。
A. 8 B. 9 C. 100 D. 50
分析：200个元素的二叉搜索树，如果有k+1层，前k层是满二叉树，总的结点数为2k-1<200，求出k=7，多余的元素在第8层上。这样查找一个元素最多比较8次。
书上 P278公式,也可以直接计算: k=log2(n+1), 计算结果上取整
（3）对二叉排序树进行（ C ）遍历，遍历所得到的序列是有序序列。
A．按层次 B．前序 C．中序 D．后序
分析：二叉排序树的介绍详见6月3日的“综合题复习”，对二叉排序树进行中序输出正好是有序序列。
（4）若数据结构中，结点的存储地址与结点的关键字之间存在某种映射关系，则称这种存储结构为（ C ）。
A. 顺序存储结构 B. 链式存储结构 C. 散列存储结构 D. 索引存储结构
分析：散列存储结构中，关键字为自变量，经过一个函数的计算，得到一个地址进行存放。
（5）哈希法存储的基本思想是根据 关键字 来决定存储地址。
20、排序
（1）排序方法中，从尚未排序序列中挑选元素，并将其**依次\放入已排序序列（初始为空）的一端的方法，称为（ D ）排序。
A．归并 B．插入 C．快速 D．选择
分析：
插入排序是每次把无序序列中的一个记录根据其关键字大小插入到有序序列的相应位置。
选择排序是每次从无序序列中选择一个最大或最小的记录放到有序序列中。
（2）对整数序列 5， 3， 6， 2， 8， 4作从小到大排序，经排序算法一次处理后，该序列变成4， 3， 2， 5， 8， 6。 则在以下四种供选择的排序方法中，能实现这个结果的最可能的排序方法是（ B ）。
A. 插入排序 B. 快速排序 C. 选择排序 D. 冒泡排序
分析：一次快速排序是以某一个记录为参考（此处是5），把5小的交换到左面，把5大的交换到右面。
（3）通常对n个元素进行冒泡排序要进行 n-1 趟排序；第i趟冒泡排序要进行_____ n-i-1 次元素间的比较。
分析：第0趟冒泡排序需要进行n-1次元素间的比较，第1趟冒泡排序需要进行n-2次元素间的比较，…，第i次冒泡排序需要进行n-i-1次元素间的比较
（4）稳定的排序算法指（ A ）。
A．经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变
B．经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变
C．排序算法的性能与被排序元素的个数关系不大
D．排序算法的性能与被排序元素的个数关系密切
（5）在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ A ）。
A. 直接插入排序 B．直接选择排序 C．快速排序 D．归并排序
附录
数据结构公式：