数据结构习题

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=x)j--； 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