发布时间 : 星期四 文章数据结构习题更新完毕开始阅读144210a7195f312b3169a5d5
18．设广义表L=((),()), 则head(L)是 ；tail(L)是 ；L的长度是 ；深度是 。
19. 已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来 。 20. 广义表的深度是_______。
21. 广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: 。 22.广义表(a,(a,b),d,e,((i,j),k))的长度是 ，表头是 ，表尾是 。 23.广义表A（（a，b，c），（d，e，f））的表尾为 。
三、判断题
2.二维数组是数组元素为一维数组的线性表，因此它是线性结构。 3．广义表的表尾可以是原子也可以是列表。
4.一个广义表的表尾总是一个广义表。 5．二维数组是其数组元素为线性表的线性表。
6．每种数据结构都应具备三种基本运算：插入、删除和搜索。
7.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。 8.数组元素之间的关系，既不是线性的，也不是树形的。
1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
四、应用题
1. 二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是多少。
2.画出广义表A=(()，(e),(a,(b,c,d)))的链式存储结构的示意图。
3．画出下列广义表的共享结构图形表示P=（（（z）,(x,y)）,((x,y),x),(z)）。
4. 若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么，A中任一个下三角元素aij(i≥j),在数组B中的下标位置k是什么？ 5. 求下列广义表的运算结果。 （1）CAR(CDR(((a,b),(c,d),(e,f)))) （2）CDR(CAR(((a,b),(c,d),(e,f)))) （3）CAR(CDR(CAR(((a,b),(e,f))))) （4）CDR(CAR(CDR(((a,b),(e,f))))) （5）CDR(CDR(CAR(((a,b),(e,f)))))
25
注：CAR运算相当于有些教材中的Head运算，CDR运算相当于Tail运算。
6. 利用广义表的Head和Ｔail运算，把原子d分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e））。
五、算法设计题
1.对于二维整数数组B[m][n]，对下列三种情况，分别编写相应的函数。
（1）求数组所有边缘的和。 int suml (int B[M][N] , int m , int n) //M和N分别大于等于m和n （2）求从B[0][0]开始的互不相邻的所有元素的和。（注：一个元素的八个方向上的第一个元素均为相邻元素。）int sum2 (int B[M][N] , int m , int n)
（3）假定m=n，请分别计算正、反两条对角线上的元素的和。int sum3(int B [M][N] , int n)
2.一个一维整数数组B[m]中有n (n≤m)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，针对下列三种情况，分别编写相应的函数。
①在数组B[ ]中插入一个新的整数S ，并使得插入后仍保持非递减有序。要求S 插在值相等的整数后面。void InsertSort (int B[ ], int m , int & n , int S)
②将数组中所有整数原地逆置，即利用原数组空间将数组中全部元素反转。void reverse (int B [ ], int n ) ③删除数组中多余的值相等的整数（只保留第一次出现的那个整数）。void delDuplicate (int B [ ] , int & n) 3．阅读下列函数arrange()
int arrange(int a[N],int l,int h,int x) {//1和h分别为数据区的下界和上界 int i,j,t； i=l；j=h；
while(i while(i { t=a[j]；a[j]=a[i]；a[i]=t；} } if(a[i] （1）写出该函数的功能； 26 （2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。 （1）该函数的功能是：调整整数数组a[N];中的元素并返回分界值i，使所有 p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； return q－p； return p－q； } } 六、简答题 1. 利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。 2. 对一个有t个非零元素的Amn 矩阵, 用B[0..t][1..3]的数组来表示，其中第0行的三个元素分别为m,n,t, 从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作确定任意一个元素A[i][j]在B中的位置并修改其值，应如何设计算法可以使时间得到改善？ 3. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？ 4. 试叙述一维数组与有序表的异同。 5. 用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。 6. 数组，广义表与线性表之间有什么样的关系？ 7. 什么是广义表？请简述广义表和线性表的主要区别。 27 第六章 树 一、单项选择题 1.下列存储形式中，( )不是树的存储形式 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 2. 一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( )。 A.1 B.2 C.3 D.4 3.在一棵具有5层的满二叉树中结点数为( ) A.31 B.32 C.33 D.16 4.深度为5的二叉树至多有（ ）个结点。 A. 16 B .32 C. 31 D.10 5.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是( ) A.9 B．11 C．12 D．不确定 6．已知完全二叉树有30个结点，则整个二叉树有（ ）个叶子结点。 A.0 B.15 C.2 D.不确定 7．在有n个结点的二叉链表中的空链域有（ ）个。 A.n B.n+1 C.n-1 D.n+2 8. 在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( )。 A. 2 B. 2 C. 2-1 D. 2 9.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A. 2 B. 1 C. 0 D. –1 h-1 h+1 h h 10.在一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 11.一个二叉树按顺序方式存储在一个维数组中，如图 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点E在二叉树的第（ ）层。 A.1 B.2 C.3 D.4 12.对于下面的二叉树，按后序遍历所得的结点序列为（ ）。 28