第5章 数组与广义表
一、选择题
（1）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。
A．808 B．818 C．1010 D．1020
（2）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（ ）。
A．BA+141 B．BA+180 C．BA+222 D．BA+225
（3）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A．13 B．33 C．18 D．40
（4）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i A．i*(i-1)/2+j B．j*(j-1)/2+i C．i*(i+1)/2+j D．j*(j+1)/2+i （5）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。 A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-i)/2+1 D．j(i-1)/2+1 （6）设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ ）。 A．(i-1)*n+j B．(i-1)*n+j-1 C．i*(j-1) D．j*m+i-1 （7）数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。 A．55 B．45 C．36 D．16 （8）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。 A．(g) B．(d) C．c D．d （9）广义表((a,b,c,d))的表头是（ ），表尾是（ ）。 A．a B．( ) C．(a,b,c,d) D．(b,c,d) （10）设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。 A．1和1 B．1和3 C．1和2 D．2和3 二、问答题 （1）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： ① 存放该数组所需多少单元？ ② 存放数组第4列所有元素至少需多少单元？ ③ 数组按行存放时，元素A[7,4]的起始地址是多少？ ④ 数组按列存放时，元素A[4,7]的起始地址是多少？ (2)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear) 第6章 树和二叉树 1．选择题 （1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。 A．唯一的 Ｂ．有多种 C．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子 （2）由3 个结点可以构造出多少种不同的二叉树？（ ） A．2 B．3 C．4 D．5 （3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 A．250 B． 500 C．254 D．501 （4）一个具有1025个结点的二叉树的高h为（ ）。 A．11 B．10 C．11至1025之间 D．10至1024之间 （5）深度为h的满m叉树的第k层有（ ）个结点。(1= A．指向最左孩子 B．指向最右孩子 C．空 D．非空 （7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 （8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 （9）在下列存储形式中，（ ）不是树的存储形式？ A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 （10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。 A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 （11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 （12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。 A．X的双亲 B．X的右子树中最左的结点 C．X的左子树中最右结点 D．X的左子树中最右叶结点 （13）引入二叉线索树的目的是（ ）。 A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 （14）线索二叉树是一种（ ）结构。 A．逻辑 B． 逻辑和存储 C．物理 D．线性 （15）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。 A． n-1 B．n C． n+1 D． n+2 2．应用题 （1）试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同 （2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树（或森林）。 （3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 ① 试为这8个字母设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例，比较两种方案的优缺点。 第7章 图 1．选择题 （1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。 A．1/2 B．1 C．2 D．4 （2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 （3）具有n个顶点的有向图最多有（ ）条边。 A．n B．n(n-1) C．n(n+1) D．n2 （4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。 A．n B．2(n-1) C．n/2 D．n2 （5）G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A．7 B．8 C．9 D．10 （6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。 A．非连通 B．连通 C．强连通 D．有向 （7）下面（ ）算法适合构造一个稠密图G的最小生成树。 A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法 （8）用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 （9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 （10）深度优先遍历类似于二叉树的（ ）。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 （11）广度优先遍历类似于二叉树的（ ）。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 （12）图的BFS生成树的树高比DFS生成树的树高（ ）。 A．小 B．相等 C．小或相等 D．大或相等 （13）已知图的邻接矩阵如图7.1所示，则从顶点0出发按深度优先遍历的结果是（ ）。 ?011?100??100??110?101??000?110?101?1001??0100??0110?1010??1101?0010??1A．0 2 4 3 1 5 6 B．0 1 3 6 5 4 2 C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 2 图7.1 邻接矩阵 （14）已知图的邻接表如图7.2所示，则从顶点0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ）。 A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 图7.2 邻接表 （15）下面（ ）方法可以判断出一个有向图是否有环。 A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 2．应用题 （1）已知如图7.3所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表； ④ 逆邻接表。 （2）已知如图7.4所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 （3）已知图的邻接矩阵如7.5所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。 ???4??3??????????????4?559???35?5???5?55?7654?9?7?3?????63?2????5?2?6?????5??4??????6????? 图7.3 有向图 图7.4 无向网 （4）有向网如图7.6所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表7.1。 终点 i=1 b c d e f g vj S 终点集 i=2 i=3 i=4 i=5 i=6 图7.6 有向网 5 邻接矩阵