当前位置：首页 » 数据结构习题解析 » 正文

数据结构习题及解析二

2058 人参与 2018年08月19日 20:59 分类 : 数据结构习题解析评论

一、选择题

1、数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是（）
A．数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分
B．数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体
C．数组的读、写运算只能读取或修改一个数据元素的一部分
D．数组的读、写运算只能读取或修改一个数据元素整体

解析：本题考点是数组的数据元素类型的定义。 数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体，当数据元素本身不是原子项时，我们可以修改一个数据元素的一部分。因此，本题参考答案是B。 

2、在以下栈的基本运算中，不是加工型运算的是（）
A．lnitStack(S)
B．Push(S,X)
C．Pop(S)
D．Empty(S)

解析：本题考点是加工型运算的判别。 清空栈不是加工型运算。因此，本题参考答案是D。 

3、以下不稳定的排序方法是（）
A．直接插入排序
B．冒泡排序
C．直接选择排序
D．二路归并排序

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

4、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。
A．n
B．n/2
C．(n+1)/2
D．(n-1)/2

解析：本题考点是平均查找长度的计算方法。 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。按照此方法计算可得，本题参考答案是C。 

5、以下说法错误的是（）
A．数据的物理结构是指数据在计算机内实际的存储形式
B．算法和程序没有区别，所以在数据结构中二者是通用的
C．对链表进行插人和删除操作时，不必移动结点
D．双链表中至多只有一个结点的后继指针为空

解析：本题考点是数据结构中相关基本概念。 算法是解决问题的步骤；程序是算法的代码实现。算法要依靠程序来完成功能；程序需要算法作为灵魂。因此，本题参考答案是B。 

6、顺序队列的出队操作为（）
A．sq.front=(sq.front+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.front+1。因此，本题参考答案是B。 

7、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用 H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。
A．1
B．2
C．3
D．4

解析：本题考点是线性表散列存储的特点。 散列函数即哈希函数，哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为：Addr = H（key）。线性表中的值就是函数中的自变量，代入函数可知，55,64,46和10散列地址都为1。因此，本题参考答案是D。 

8、在以下队列的基本运算中，不是加工型运算的是（）
A．InitQueue(Q)
B．EnQueue(Q,X)
C．OutQueu(Q,X)
D．GetHead(Q,x)

解析：本题考点是队列的基本运算。 获取队头元素不是加工型运算。因此，本题参考答案是D。 

9、设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。
A．abedfc
B．acfebd
C．aebdfc
D．aedfcb

解析：本题考点是图的深度优先遍历。 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。因此，本题参考答案是C。 

10、根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格处理中的五种功能以下解释错误的是（）
A．查找引用型运算，功能是找出满足某种条件的结点在s(线形结构)中的位置
B．读取引用型运算功能是读出s(线形结构)中某指定位置结点的内容
C．插入引用型运算，功能是在s(线形结构)的某指定位置上增加一个新结点
D．删除加工型运算，功能是撤消s(线形结构)某指定位置上的结点

解析：本题考点是加工型运算、引用型运算的功能。 插入是加工型运算。因此，本题参考答案是C。 

二、判断题

1、快速排序是排序算法中平均性能最好的一种排序。( )
A正确
B错误

解析：本题考点是快速排序的性能。 快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是排序算法中平均性能最好的一种排序。因此，本题参考答案是A。 

2、在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。（）
A正确
B错误

解析：本题考点是循环队列的特性。 循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。在一个顺序存储的循环队列中, 队头指针指向队头元素的前一个位置。因此，本题参考答案是B。 

3、散列法存储的基本思想是由关键码的值决定数据的存储地址。( )
A正确
B错误

解析：本题考点是散列法存储的基本思想。 散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储。因此，本题参考答案是A。 

4、在使用后缀表示实现计算器类时用到一个栈的实例, 它的作用是暂存运算器对象。（）
A正确
B错误

解析：本题考点是后缀表示的应用。 栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。在使用后缀表示实现计算器类时用到一个栈的实例, 它的作用是暂存运算器对象。因此，本题参考答案是A。 

5、在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（）
A正确
B错误

解析：本题考点是循环单链表的应用。 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针，由于是循环队列，通过队尾移动指针即可找到队头。因此，本题参考答案是A。 

6、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )
A正确
B错误

解析：本题考点是冒泡排序的特点。 冒泡排序，是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。冒泡排序在初始关键字序列为有序的情况下执行的交换次数最少。冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。因此，本题参考答案是A。 

7、在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front == Q->rear。（）
A正确
B错误

解析：本题考点是单链表表示链式队列的特点。 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front == Q->rear+1。因此，本题参考答案是B。 

8、递归定义的数据结构通常用递归算法来实现对它的操作。（）
A正确
B错误

解析：本题考点是递归定义数据结构的特点。 程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。递归定义的数据结构通常用递归算法来实现对它的操作。因此，本题参考答案是A。 

9、二叉树中有双子女的父结点，在中序遍历中后继一定是其中一个子女结点( )
A正确
B错误

解析：本题考点是二叉树的基本特性。 二叉树是每个节点最多有两个子树的树结构。通常子树被称作"左子树"和"右子树"。二叉树中有双子女的父结点，在中序遍历中后继不一定是其中一个子女结点。因此，本题参考答案是B。 

10、递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。（）
A正确
B错误

解析：本题考点是递归调用算法的缺点。 递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。因此，本题参考答案是A。 

三、分析题

1、给定表（45,36,56,6,64,78,8,96），按数据元素在表中的次序构造一棵二叉排序树。

解析：本题考点是二叉排序树的构造方法。 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； 
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； 
（3）左、右子树也分别为二叉排序树； 
（4）没有键值相等的节点。 
根据二叉排序树的定义即可根据给定表构造出出二叉排序树。 因此，本题答题要点如下： 
二叉排序树为：

2、判断序列（16，19，10，15，4，23，36，20）是否为（小顶）堆？为什么？如果不是，请按照建立堆的思想把它调整为堆，并用图表示建堆的过程。

解析：本题考点是堆的定义和建立方法。 n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)： (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n/2 ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 
因此，本题答题要点如下： 
因为不满足（ai<a2i 和ai<a2i+1）如a1=16,a3=10，所以不是小顶堆。 可以调整为堆：（4，15，10，16，19，23，36，20）

3、简述顺序队列、循环队列的类型定义。

解析：本题考点是顺序队列、循环队列的定义。 顺序队列的类型定义如下：
该类型变量有三个域：data,front,rear。其中data存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，实际取值范围为0~maxsize－1。 循环队列的类型定义如下：

4、给定有序表D={006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908}，用二分查找法在D中查找586，试用图示法表示出查找过程。

解析：本题考点是二分查找算法的定义及过程。 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
因此，本题答题要点如下： 