1~5Aadc bd 6~12abdca cb
第三章作业
Aab
4．如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为___DCBA____________。
5．队列中允许进行删除的一端为____队首______。
6.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为___bceda__。 第五章数组和广义表 单项选择题。
(1)空的广义表是指广义表（ D ）。 A．深度为0 B．尚未赋值
C．不含任何原子元素 D．不含任何元素 (2)广义表中元素分为（ C ）。 A．原子元素 B．表元素
C．原子元素和表元素 D．任意元素 (3)广义表的长度是指（ A ）。
A．广义表中元素的个数 B．广义表中原子元素的个数 C．广义表中表元素的个数 D．广义表中括号嵌套的层数 (4)广义表的深度是指（ D ）。
A．广义表中元素的个数 B．广义表中原子元素的个数 C．广义表中表元素的个数 D．广义表中括号嵌套的层数 (5)在一个长度为n，包含m个原子元素的广义表中，（ B ）。
A．m和n相等 B．m不大于n C．m不小于n D．m与n无关 (6)广义表A=(( )，(a)，(b，(c，d)))的长度为（ B ）。 A．2 B．3 C．4 D．5
(7)广义表A：(( )，(a)，(b，(c，d)))的深度为（ B ）。 A．2 B．3 C．4 D．5
5．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（ C ）
A．116 B．118 C．120 D．122
6.为查找某一特定单词在文本中出现的位置，可应用的串运算是( D ) A.插入 B.删除 C.串联接 D.子串定位
10.假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为__55___。
第六章 树和二叉树（答案）
一．判断题(在你认为正确的题后的括号中打√，否则打X)。
(1)在树型结构中，每一个结点最多只有一个前驱结点，但可以有多个后继结点。 (√ )
(2)在树型结构中，每—个结点不能没有前驱结点。 (X ) (3)在度为k的树中，至少有一个度为k的结点。 (√ ) (4)度为2的树是二叉树。 (X )
(5)在非空完全二叉树中，只有最下面一层的结点为叶结点。 (X ) (6)在完全二叉树中，没有左孩子的结点一定是叶结点。 (√ ) (7)在完全二叉树中，没有右孩子的结点一定是叶结点。 (X )
(8)在结点数目一定的前提下，各种形态的二叉树中，完全二叉树具有最小深度。√ (9)满二叉树中的每个结点的度不是0就是2。 (√ )
(10)在所有深度相同的二叉树中，满二叉树具有最大结点数目。 (√ ) (11)由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。 (√ ) (12)由二叉树的中序序列和后序序列可以唯一地确定一棵二叉树。 (√ ) (13)由二叉树的前序序列和后序序列可以唯一地确定一棵二叉树。 (X ) (14)哈夫曼树中不存在度为1的结点。 (√ ) (15)满二叉树一定是完全二叉树。 (√ )
二、单项选择题。
(1)树型结构最适合用来描述( C )。 A．有序的数据元素 B．无序的数据元素
C．数据元素之间具有层次关系的数据 D．数据元素之间没有关系的数据
(2)按照二叉树的定义，具有3个结点的二叉树有( D )种形态(不考虑数据信息的组合情况)。
A．2 B．3 C．4 D．5
(3)若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数是( B )。 A．9 B．11 C．12 D．不确定
(4)若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为( B )。 A．512 B．1024 C．2048 D．4096
(5)深度为h的满二叉树的第i层有( )个结点。(i≤h) ( B ) A．2i—1 B．2i-1 C．2h—1 D．2h-1 (6)深度为h的满二叉树共有( C )个结点。(i (7)若某完全二叉树的深度为h，则该完全二叉树中至少有( D )个结点。 — A．2h B．2h-1 c．2h+1 D．2h1 三、填空题。 (1)任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的______根______。 (2)树的层次定义为__树中结点的最大层数__________________。 (3)度为k的树中第i层最多有_______ki-1________个结点(i≥1)。 (4)深度为h的k叉树最多有_______kh-1_/k-1____________个结点。 (5)非空二叉树一共有________4_______种基本形态。 (6)非空二叉树中第i层最多有______ 2i-1_________个结点。 (7)深度为h的二叉树最多有____________2h-1___________________个结点。 (8)具有n个结点的完全二叉树的深度h=log2n+1_。 (9)若二叉树有N0个叶结点，n2个度为2的结点，则N0与n2的关系是________n0=n2+1_______。 (10)若具有n个结点的非空二叉树．树有N0个叶结点，则该二叉树有_______n0-1_____个度为2的结点，____n-2n0+1________个度为1的结点。 (11)对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为_______i/2________，左孩子的编号为_______2i________，右孩子的编号为_____2i+1_________。 (12)若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有________2n________个指针域，其中有________n-1________个指针域用于链接孩子结点，_______n+1________个指针域空闲存放着NULL。 (13)已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为__DCBFGEA_________。 (14)已知某完全二叉树采用顺序存储结构，结点的存放次序为A,B，C,D，E，F，G，H，I，J，该完全二叉树的后序序列为_____HDEBFGCA_________。 (15)具有N0个叶结点的哈夫曼树共有_______2N0-1_____个结点。 第七章 图 习 题 一、 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)n个顶点的无向图最多有n(n-1)条边。 (X ) (2)在有向图中，所有顶点的入度之和等于所有顶点的出度之和。 (√ ) (3)在无向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。 (√ ) (4)在有向图中，若顶点i到顶点j有路径，则这两个顶点之间是连通的。 (X ) (5)连通图的最小生成树是唯一的。 (X ) (6)邻接矩阵主要用来表示顶点之间的关系。 (√ ) (7)若表示某图的邻接矩阵不是对称矩阵，则该图一定是有向图。 (√ ) (8)对于同一个有向图，邻接表中的边结点数目与逆邻接表中边结点数目相等。 (√ ) (9)无向图的邻接表中边结点数目一定为偶数。 (√ ) (10)对图进行广度优先搜索的过程中要用到队列。 (√ ) (11)对图进行深度优先搜索的过程中要用到堆栈。 (√ ) (12)最短路径一定是简单路径。 (√ ) (13)求源点到各点的最短路径的迪杰斯特拉算法不适用于存在回路的有向网络。 (X )（12，13可不掌握） 二、单项选择题。 (1)在一个图中，所有顶点的度数之和等于所有边数的( C )倍。 A．1／2 B．1 C．2 D．4 (2)一个具有n个顶点的无向图最多有( A )条边。 A．n(n-1)／2 B．n(n-1) C．n(n+1)/2 D．n(2) (3)一个具有n个顶点的有向图最多有( B )条边。 A．n(n-1)/2 B．n(n-1) C．n(n+1)/2 D．n(2) (4)在一个具有n个顶点的无向图中，要连通全部顶点至少需要(C )条边。 A．n B．n+1 C．n-1 D．2n (5)具有n个顶点的连通图的生成树一定有( C )条边。 A．n B．n+1 C．n-1 D．2n (6)在带权图中，两个顶点之间的路径长度是( D )。 A．路径上的顶点数目 B．路径上的边的数目 C．路径上顶点和边的数目 D．路径上所有边上的权值之和 (7)若具有n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵一定为一个( B )。 A．一般矩阵 B．对称矩阵 C．对角矩阵 D．稀疏矩阵 (8)若图的邻接矩阵中主对角线上的元素均为0，其余元素全为1，则可以断定该图一定 ( C ). A．是无向图 B．是有向图 C．是完全图 D．不是带权图 (9)有向图的邻接表的第i个链表中的边结点数目是第i个顶点的( B )。 A．度数 B．出度 C．人数 D．边数 (10)若某图的邻接表中的边结点数目为奇数，则该图( C )。 A．一定有奇数个顶点 B．一定有偶数个顶点 C．一定是有向图 D。可能是无向图 (11)若某图的邻接表中的边结点数目为偶数，则该图( C)。 A．一定是无向图 B。可能是有向图 C．可能是无向图，也可能是有向图 D．一定有偶数个顶点 (12)若无向图有k条边，则相应的邻接表中就有( C)个边结点。 A．k-1 B．k C．2k D．K2 (13)若有向图有k条边，则相应的邻接表中就有( B )个边结点。 A．k-1 B．k C．2k D．K2 (14)对于一个不带权的无向图的邻接矩阵而言，( C )。 A．矩阵中非零元素的数目等于图中边的数目 B．矩阵中非全零的行的数目等于图中顶点的数目 C．第i行的非零元素的数目与第i列的非零元素的数目相等 D．第i行与第i列的非零元素的总数等于第i个顶点的度数 (15)若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个( B )图。 B． 非连通 B．连通 C．强连通 D．完全 三． 求出下图的最小生成树
