《数据结构》基本习题答案.doc 15页

'《数据结构》基本习题第1章绪论1自测习题二、选择题1．以下数据结构中，属于线性结构的是(B)A）有向图B）串C）线索二叉树D）B树2．下列与数据元素有关的叙述中错误的是(A)A）数据元素是有独立含义的数据最小单位B）数据元素是描述数据的基本单位C）数据元素可以称做结点D）数据元素可以称做记录3．以下术语中与数据的存储结构无关的是(A)A）栈B）散列表C）顺序表D）双链表4．以下数据结构中，属于线性结构的是(B)A）有向图B）串C）线索二叉树D）B树三、填空题1．数据结构包括的三方面内容分别是：数据的逻辑结构、数据的存储结构和数据的运算。2．数据元素是数据的基本单位，在某些情况下也可以称为结点、记录和顶点。-15- 《数据结构》基本习题3．数据逻辑结构的4种基本形态包括集合结构、线性结构、树型结构和图（网）结构。4．一个正确的算法应该具有5个特性：输入、输出、确定性、可行性和有穷性。5．数据的存储结构包括顺序、链式、索引和散列四种。6．一个数据结构在计算机中的映象称为存储结构。7．一个算法的效率主要是指该算法的时间效率和空间效率。8．以下程序段的时间复杂度T（n）=______。sum=0;for(i=0;ilink=p->link->link。2．线性表L=(a1,a2,…an-15- 《数据结构》基本习题)用数组存储。假定删除表中任一元素的概率相同，则删除一个元素平均需要移动的元素个数是(n-1)/2。3．设有结点定义structnode{intdata;structnode*next;};且已建立如图2-2所示的带有头结点的单向链表：…head头^datanext图2-2填空题3附图函数sum的功能是：计算链表中各结点数据域之和，作为函数值返回。请填空。intsum(structnode*head){ints=0;structnode*p;p=head->next;do{s=s+p->data;p=p->next;}while(p!=NULL);-15- 《数据结构》基本习题returns;}第3章栈和队列3自测习题二、选择题1．有6个元素按6、5、4、3、2、1的顺序进栈，进栈过程中可以出栈，则以下可能的出栈序列是（B，D）A）1、4、3、5、2、6B）6、5、4、3、2、1C）3、1、4、2、6、5D）5、6、3、4、2、12．栈和队列都是（C）A）顺序存储的线性结构B）链式存储的线性结构C）限制存取点的线性结构D）限制存取点的非线性结构3．设循环队列的队首指针用front表示，队尾指针用rear表示，则判断队空的条件是（A）A）front==rearB）front+1=rearC）rear+1=frontD）rear==04、设有中缀算术表达式：15–3*（7+2）,其对应的后缀算术表达式为（B）A）153-72+*B）15372+*-C）153*72+D）153-*72+-15- 《数据结构》基本习题三、填空题1．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其操作特点是先进先出。2．设有一个空栈，栈顶指针值为100，现有输入序列为1，2，3，4，5，经过操作序列：Push、Pop、Push、Push、Pop、Push、Push、Pop后，现在已出栈的序列是1、3、5，栈顶指针是102。3．设有后缀算术表达式：2xy+*3y-/，其对应的中缀表达式为2*(x+y)/(3-y)。4．已知一算术表达式的中缀形式为：(a+b)-(b+c)/2，其对应的前缀表达式形式应为-+ab/+bc2。第4章串4.1自测习题一．选择题1．设有一个字符串S=“ABC123XYZ”，问该串的长度为（C）A）9B）10C）11D）122．设有一个字符串S=”windows”，其子串的数目是(29个)A）25个B）26个C）27个D）28个3．串是一种特殊的线性表，其特殊性表现在(D)-15- 《数据结构》基本习题A）串中允许有空串B）串可以顺序存储C）串可以链式存储D）数据元素是一个字符。一．填空题１．已知串S=”abaabccd”，求该串S的子串运算结果，SubStr(“abaabccd”,4,3)=＿abc＿＿，SubStr(“abaabccd”,5,0)=＿∮＿。２．两个串相等的充分必要条件是＿不仅两个串的长度相等，而＿且各个位置上对应的字符也要相等。３．不含任何字符的串称为＿空串＿＿，其长度为0＿。４．只含有空格字符的串称为＿空格＿，其长度为＿串中空格符的个数＿。第5章数组与广义表5自测习题一．选择题１．设有二维数组A[0．．．9,0．．．19]，其每个元素占２个字节，数组按行优先顺序存储，第一个元素的存储地址为100，那么元素A[8,12]的存储地址为(D)A）262B）284C）402D）444２．设有一个10-15- 《数据结构》基本习题阶的对称矩阵Ａ，采用压缩存储方式，以行优先顺序存储，a11为第一个元素，其存储地址为1，且每个元素占1个地址空间，则a75的地址为(A)Ａ）26Ｂ）17Ｃ）33Ｄ）23一．填空题１．设有二维数组A[10][10]，其每个元素占２个字节，数组按列优先顺序存储，第一个元素的存储地址为100，那么元素A[6,6]的存储地址为＿232＿＿＿。(下标从0开始)２．设有广义表A=((x,(a,b)),((x,(a,b)),y))，则广义表A的长度为＿＿2＿＿，深度为＿＿4＿＿。第6章树6自测习题三.选择题1.如果结点A是结点B的双亲，而且结点Ｂ有４个兄弟，则结点A的度是(D)A）2B）3C）4D）52.设有一棵二叉树，其１度结点有m个，２度结点有n个，则该二叉树的结点总数为(D)A）m+nB）2*m+nC）m+2*nD）m+2*n+13.设有一棵二叉树，其先序遍历序列是：ABCDEFG-15- 《数据结构》基本习题，中序遍历序列是：CBDAFEG，则该二叉树的后序遍历序列是(A)A）CDBFGEAB）CDFGBEAC）CDBAFGED）CDBFEGA1.设有13个值，由它们组成一棵哈夫曼树，则该哈夫曼树中结点个数共有(D)。A）13B）12C）26D）252.设电文中出现的字母为A、B、C、D和E，每个字母在电文中出现的次数分别为：6，23，3，5和12，按哈夫曼编码，则字母C的编码应是(C)(D)A）10B）110C）1110D）11113.已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是(G)A）EB）FC）GD）J4.设结点A有左孩子结点B，右孩子结点C，则在先序遍历、中序遍历、后序遍历这三种基本遍历序列中B一定是C的(A)A）前驱B）后继C）相邻结点D）不相邻结点四.填空题1.采用二叉链式存储结构，具有n个结点的二叉树中，一共有2n个指针域，其中n+1个指针域为空。-15- 《数据结构》基本习题1.一棵非空的二叉树，其第i层上最多有＿＿＿＿＿个结点。2.满二叉树是一棵深度为k的且恰好有＿-1＿＿＿＿个结点的二叉树。3.将一棵完全二叉树按层次编号，对任一编号为i的结点有：如该结点有左孩子，则其编号为2i；如该结点有右孩子，则其编号为2i+1。4.设一棵二叉树中只有叶子结点和左、右子树都非空的结点，如果叶子结点的个数是m，则左、右子树都非空的结点个数是＿m-1＿＿＿＿5.设有一棵树（如图6-5所示），请回答下列问题：根结点是＿A＿；叶子结点有＿DHIJFK；Ｅ的双亲是＿B＿；Ｆ的祖先是＿CA＿；Ｇ的孩子是＿K＿；Ｄ的孩子是＿无；Ｅ的子孙有＿＿HIJ＿＿；Ｄ的兄弟是E＿＿；Ｂ的兄弟是＿C＿；结点Ｈ的层数是＿4＿；树的深度是＿4＿；Ｅ为根的子树深度是＿2；这棵树的度是＿3＿。图6-5填空题6的附图-15- 《数据结构》基本习题1.现有一表达式(a+b)*c-d/e，写出该表达式的波兰式＿-*+abc/de＿＿＿，以及逆波兰式＿ab+c*de/-＿＿＿＿＿。第7章图7自测习题二、选择题1．对如图7-4所示的无向图G，若从顶点V1开始，按深度优先搜索法进行遍历，则可能的访问顺序为（A）A）V1V2V4V8V5V6V3V7B）V1V2V3V4V5V6V7V8C）V1V2V3V4V8V5V6V7D）V1V2V4V5V8V3V6V72．对如图7-5所示的无向图G，若从顶点V1开始，按广度优先搜索法进行遍历，则可能的访问顺序为（C）-15- 《数据结构》基本习题A）V1V2V3V4V5V6V7V8B）V1V2V6V3V4V5V7V8C）V1V2V6V3V4V7V8V5D）V1V2V6V3V5V4V7V83．在一个无向图中，所有顶点的度数之和等于所有边数的（B）A）1倍B）2倍C）1/2倍D）不确定三、填空题1．有n个顶点的无向连通图至少有n-1条边，有n个顶点的有向强连通图至少有n条弧。2．在一个有n个顶点的无向图中，要连通所有顶点，至少需要n-1条边。3．用邻接矩阵表示无向图时，若图中有n=500个顶点，m=500条边，则形成的邻接矩阵共有25000个元素，其中1000个非零元素。4．有n个顶点的无向图的邻接矩阵是对称的，因而只需存储(+n)/2条边即可。5．在一个有向图中，所有顶点的度数之和等于图中弧数的2倍。在一个有向图中，所有顶点的出度之和等于图中弧数的1倍。6．对一个有n个顶点和e条边的连通图，其生成树的顶点数和边数分别为n和n-1。7．无向图的邻接矩阵中一行中非零元素的个数表示该行所对应的顶点的度，一列中非零元素的个数表示该列所对应的顶点的度。-15- 《数据结构》基本习题第8章查找三、选择题1．使用折半查找，线性表必须DA）以顺序方式存储B）以链式方式存储，且元素已按值排好序C）以链式方式存储D）以顺序方式存储，且元素已按值排好序2．散列表的地址区间为0~16，散列函数为H1(K)=K%17，采用线性探测法解决冲突，将关键字序列26，25，72，38，8，18，59依次存储到散列表中（1）元素59存放在散列表中的地址为(D)A）8B）9C）10D）11（2）查找元素59，需要比较的次数为(C)A）2B）3C）4D）5四、填空题1．采用折半查找算法在长度为12的有序表中查找一个元素时，查找成功的平均查找长度为_37/12____。2．从有序表（12，18，30，43，56，78，82，95）中，采用折半查找算法依次搜索20、43、56时，查找长度分别为4、1、3。-15- 《数据结构》基本习题第9章排序二、选择题1．下列排序方法中，哪一种是稳定的排序方法：(B)A）选择排序B）归并排序C）快速排序D）希尔排序2．快速排序每次划分的效果好坏和以下何种因素有直接关系：(C)A）关键字的排列情况B）数据元素的个数C）轴的相对大小D）关键字值的最大值3．对以下几个关键字序列进行快速排序，以第一个元素为轴，一次划分效果最好的是：(c)A）1，2，3，4，5B）2，1，3，4，5C）3，1，2，4，5D）5，3，1，2，44．对以下几个关键字序列进行快速排序，以第一个元素为轴，一次划分效果不好的是：(D)A）4，1，2，3，6，5，7B）4，3，1，7，6，5，2C）4，2，1，3，6，7，5D）1，2，3，4，5，6，75．设待排序数据元素序列为[4，1，2，3]，应用一种排序方法进行递增序排序，已知两趟后的结果为[1，2，3，4]，则所选用的排序方法为：(C)A）直接插入B）直接选择-15- 《数据结构》基本习题C）冒泡（从前向后）D）C冒泡（从后向前）6．排序方法中，关键字的比较次数与记录的初始排列无关的是：(C)A）希尔排序B）归并排序(有关)C）直接选择排序D）直接插入排序7．下列字符序列中，不符合堆定义的为：(C)A）ACDGHMPQRXB）ACMDHPXGQRC）ADPRCQXMHGD）ADCMPGHXRQ三、填空题1．排序是指将无序的数据元素序列转变成一个有序序列，把序列中的记录，通过某些方法整理成按关键字递增或递减次序排列的处理过程。2．排序算法分成内部排序算法和外部排序算法。3．排序算法的稳定性是指关键字值相同的记录经过排序后的相对位置是否发生变化，永不发生变化的排序算法，就是稳定的；否则就是不稳定的。4．排序算法的基本操作是关键字的比较和关键字的移动。5．排序算法的时间效率取决于关键字的比较和记录的移动等基本操作的次数。-15-'