数据结构习题及解析一

一、选择题

1. 1、顺序表是线性表的（     ） 
   A．链式存储结构 
   B．顺序存储结构 
   C．索引存储结构 
   D．散列存储结构

2. 
   

解析：本题考点是顺序表的基本特点。 
顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
因此，本题参考答案是B。 


3. 2、以下说法错误的是（     ）
   A．求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 
   B．顺序存储的线性表可以随机存取 
   C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

   D．线性表的链式存储结构优于顺序存储结构

解析：本题考点是线性表相关基本概念。 
"线性表的链式存储结构优于顺序存储结构"这种说法是不准确的，可能在某种情况下是对的。比如在随机查找时，顺序表比较有优势。因此，本题参考答案是D。 


4. 3、某二叉树的前序和后序序列正好相同，则该二叉树一定是（     ）的二叉树。 
   A．空或只有一个结点 
   B．高度等于其结点数 
   C．任一结点无左孩子 
   D．任一结点无右孩子

解析：本题考点是二叉树的基本特点。 
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。某二叉树的前序和后序序列正好相同，则该二叉树一定是空或只有一个结点的二叉树。
因此，本题参考答案是A。 


5. 4、以下说法错误的是（    ）
   A．每个存储结点只能存放一个数据元素 
   B．数据元素之间的关联方式可由存储结点之间的关联方式直接表达 
   C．一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级

   D．语言级描述可经编译自动转换成机器级，因此也可以看成是一种机内表示

解析：本题考点是数据结构相关基本概念。 
数据元素之间的关联方式不可以由存储结点之间的关联方式直接表达。
因此，本题参考答案是B。 


6. 5、用链接方式存储的队列，在进行插入运算时（     ）。 
   A．仅修改头指针 
   B．头、尾指针都要修改 
   C．仅修改尾指针 
   D．头、尾指针可能都要修改

解析：本题考点是队列的操作。 
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。用链接方式存储的队列，在进行插入运算时头、尾指针可能都要修改。
因此，本题参考答案是D。 


7. 6、循环队列的出队操作为（     ）
   A．sq.front=(sq.ftont+1)% maxsize
   B．sq.front=sq.front+1
   C．sq.rear=(sq.rear+1)% maxsize
   D．sq.rear=sq.rear+1

解析：本题考点是循环队列的基本操作。 
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。循环队列的出队操作为sq.front=(sq.ftont+1)% maxsize。
因此，本题参考答案是A。 


8. 7、下列排序算法中，其中（     ）是稳定的。
   A．堆排序，冒泡排序 
   B．快速排序，堆排序 
   C．直接选择排序，希尔排序

   D．归并排序，冒泡排序

解析：本题考点是算法稳定性的度量。 
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。归并排序，冒泡排序是稳定的。
因此，本题参考答案是D。 


9. 8、最小堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足（     ）
   A．ki≤k2i≤k2i+1
   B．ki<k2i+1<k2i
   C．ki≤k2i且ki≤k2i+1(2i+1≤n)
   D．ki≤k2i 或ki≤k2i+1(2i+1≤n)

解析：本题考点是最小堆的基本概念。 
堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。最大堆和最小堆是二叉堆的两种形式。 最大堆：根结点的键值是所有堆结点键值中最大者。 最小堆：根结点的键值是所有堆结点键值中最小者。
因此，本题参考答案是C。 


10. 9、设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（      ）
    A．front=front+1
    B．front=(front+1)% m
    C．rear=(rear+1)%m

    D．front=(front+1)%(m+1)

解析：本题考点是队列的出队操作。 
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。出队操作的语句为front=(front+1)%(m+1)。
因此，本题参考答案是D。 


11. 10、以下说法错误的是（      ）
    A．树形结构的特点是一个结点可以有多个直接前趋 
    B．线性结构中的一个结点至多只有一个直接后继 
    C．树形结构可以表达(组织)更复杂的数据 
    D．树(及一切树形结构)是一种"分支层次"结构

解析：本题考点是树形结构的特点。 
树形结构的特点是一个结点最多有一个直接前趋。
因此，本题参考答案是A。 

二、判断题

1. 1、中序遍历二叉排序树可以得到一个有序的序列（     ） 
   A正确

   B错误

解析：本题考点是二叉排序树的遍历。 
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； 
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； 
（3）左、右子树也分别为二叉排序树； 
（4）没有键值相等的节点。 中序遍历二叉排序树可以得到一个有序的序列。
因此，本题参考答案是A。 


2. 2、用非递归方法实现递归算法时一定要使用递归工作栈。（      ） 
   A正确

   B错误

解析：本题考点是递归算法的非递实现。 
用非递归方法实现递归算法时不一定要使用递归工作栈，使用普通数组模拟栈即可。
因此，本题参考答案是B。 


3. 3、将f = 1 + 1/2 + 1/3+ … + 1/n转化为递归函数时，递归部分为f (n) = f (n-1) + 1/n，递归结束条件为f (1) = 1。（      ） 
   A正确

   B错误

解析：本题考点是递归函数的转化。 
程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。根据题意，递归结束条件为f (1) = 1。
因此，本题参考答案是A。 


4. 4、一个广义表的表头总是一个广义表。（      ） 
   A正确

   B错误

解析：本题考点是广义表的特点。 
广义表的表头是指表的第一个元素，表尾是指除表头外的其余元素构成的表，所以表尾是广义表，而表头不一定是。
因此，本题参考答案是B。 


5. 5、层次遍历初始堆可以得到一个有序的序列。（     ） 
   A正确

   B错误

解析：本题考点是初始堆的层次遍历。 
根据堆的定义，层次遍历初始堆不一定得到一个有序的序列。
因此，本题参考答案是B。 


6. 6、线性表的顺序存储表示优于链式存储表示。（     ） 
   A正确

   B错误

解析：本题考点是线性表的存储表示。 
线性表的顺序存储表示优于链式存储表示，这种说法是不准确的，比如对线性表进行插入和删除时，链式存储有优势。
因此，本题参考答案是B。 


7. 7、一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是 ( (b), c), ( ( (d) ) )。（      ） 
   A正确

   B错误

解析：本题考点是广义表相关基本概念。 
一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是( ( (b), c), ( ( (d) ) ))。
因此，本题参考答案是B。 


8. 8、当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。（      ） 
   A正确

   B错误

解析：本题考点是堆的调整过程。 
堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。最大堆和最小堆是二叉堆的两种形式。 最大堆：根结点的键值是所有堆结点键值中最大者。 最小堆：根结点的键值是所有堆结点键值中最小者。 当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。
因此，本题参考答案是A。 


9. 9、线性表的插入和删除总是伴随着大量数据的移动（     ） 
   A正确

   B错误

解析：本题考点是线性表的基本操作。 
线性表的插入和删除并不总是伴随着大量数据的移动，例如线性表是链式存储时移动代价较小。
因此，本题参考答案是B。 


10. 10、二叉树是一棵无序树。（      ）
    A正确

    B错误

解析：本题考点是二叉树的定义和特点。 
二叉树是每个结点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。
因此，本题参考答案是B。 


• 三、分析题
  

1. 1、设将整数a、b、c、d依次进栈，而只要栈非空，就可以将出栈操作夹入其中。请问能否得到出栈序列adbc和dcba？为什么？

解析：本题考点是进栈和出栈的特点。 
栈是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈是一种后进先出的数据结构。 因此，本题答题要点如下：
能得到dcba：push, push, push,push,pop, pop, pop,pop 
但不能得到adbc: 因为d出来的时候 b,c还在栈内，次序必然b在下c在上，因此紧跟d下一个出栈的必然是c而不是b。 


2. 2、写出下列二叉树的前序序列、中序序列和后序序列。
   
   

解析：本题考点是二叉树的前序、中序和后序遍历算法的基本思想。 
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。 
先序遍历是首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树。 
中序遍历是首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树。 
后序遍历是首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根。 
因此，本题答题要点如下： 
前序序列：_CABEFDHG_； 
中序序列：_ABFECHDG_； 
后序序列：_BFEAHGDC_； 


3. 3、简述链队的类型定义。

解析：本题考点是队列的链式存储结构的表示。 
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。在队列的形成过程中，可以利用线性链表的原理，来生成一个队列。基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。因此，本题答题要点如下： 
typedef struct linked_queue 
{ 
    DataType data; 
    struct linked_queue *next; 
}LqueueTp; 
typedef struct queueptr 
{ 
    LqueueTp *front, *rear; 
}QueptrTp; 
QueptrTp lq; 


4. 4、把下图中的二叉树转化为森林。
    
   

解析：本题考点是二叉树转化为森林的基本方法。 

比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。因此，本题答题要点如下： 
二叉树转化成的森林为：

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=41