自考数据结构

### 自考数据结构知识点解析 #### 一、单项选择题解析 **1. 按值可否分解，数据类型通常可分为两类，它们是（C）** - **选项解析**： - A．静态类型和动态类型：这两种类型是根据变量的生命周期来分类的，而非值是否可分解。 - B．原子类型和表类型：表类型是一种容器类型，但这里的分类标准是基于值是否可进一步分解。 - C．原子类型和结构类型：这是正确的分类方式。原子类型是指不可再分的基本数据类型，如整型、字符型等；结构类型则是由多个原子类型组合而成的复合类型，例如数组、记录等。 - D．数组类型和指针类型：虽然这两者都是重要的数据结构，但并不是按照值是否可分解来划分的。 **2. 对于三个函数f(n)=2008n^3+8n^2+96000，g(n)=8n^3+8n+2008和h(n)=8888nlogn+3n^2，下列陈述中不成立的是（C）** - **选项解析**： - A．f(n)是O(g(n))：正确，因为f(n)和g(n)的主导项都是n^3。 - B．g(n)是O(f(n))：正确，理由同上。 - C．h(n)是O(nlogn)：不正确，虽然h(n)的主导项是nlogn，但这并不意味着它就是O(nlogn)级别的所有函数，实际上h(n)的增长速度比一般的nlogn快，因为它还包含了一个3n^2的项。 - D．h(n)是O(n^2)：正确，因为3n^2的增长速度快于nlogn，所以h(n)整体上是O(n^2)级别的。 **3. 指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（A）** - **选项解析**： - A．p->next=r；q->next=r->next；r->next=q；：正确，这组语句首先将p指向r，然后将q指向r原来指向的节点，最后r指向q。 - B．p->next=r；r->next=q；q->next=r->next；：错误，最后一步会使q指向r原来的下一个节点，而不是使r指向q。 - C．r->next=q；q->next=r->next；p->next=r；：错误，最后一步只会改变p指向r，但不会使得r指向q。 - D．r->next=q；p->next=r；q->next=r->next；：错误，最后一行会导致q指向r的下一个节点，而不是完成交换。 **4. 若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（B）** - **解析**：当元素进栈和出栈可以穿插进行时，出栈序列的可能情况取决于栈的使用方式。对于3个元素，可能的出栈序列包括abc、acb、bac、bca、cba、cab，总共6种情况，但题目中给出的是5种，这意味着某些序列是不可能出现的。考虑到栈的先进后出特性，不可能出现的序列是bac，因为b不能在a之前出栈。因此，实际可能的出栈序列个数为5种。 **5. 假设以数组A[n]存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为（D）** - **解析**：在循环队列中，为了区分队空和队满的情况，通常会牺牲一个存储位置。当rear与front相邻时，队列满。具体来说，如果rear+1等于front或者rear与front之间的距离为1，就表示队列满了。选项D正确地表达了这个条件。 **6. 串的操作函数str定义为：int str(char *s){ char *p=s； while(*p != '\0') p++； return p-s； }则str("abcde")的返回值是（C）** - **解析**：此函数计算字符串的长度。通过遍历直到遇到'\0'字符停止，然后返回p与s之间的距离，即字符串的长度。"abcde"的长度为5，故正确答案为C。 **7. 二维数组A[10][6]采用行优先的存储方法，若每个元素占4个存储单元，已知元素A[3][4]的存储地址为1000，则元素A[4][3]的存储地址为（A）** - **解析**：行优先存储下，A[i][j]的地址可以通过公式计算：Address = Base Address + [i * Columns * Element Size + j * Element Size]。已知A[3][4]的地址为1000，每个元素占用4个存储单元，所以Base Address + [3 * 6 * 4 + 4 * 4] = 1000。由此可以计算出Base Address = 1000 - (72 + 16) = 912。那么A[4][3]的地址为：912 + [4 * 6 * 4 + 3 * 4] = 1020，故选A。 **8. 对广义表L=(a，())执行操作tail(L)的结果是（B）** - **解析**：tail操作返回广义表除去第一个元素后的剩余部分。对于L=(a, ())，tail(L)的结果是去掉'a'后的剩余部分，即'()'。 **9. 已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（A）** - **解析**：根据二叉树的中序和后序序列可以唯一确定一颗二叉树。由于中序和后序序列相同，说明该二叉树是一棵完全左偏或右偏的二叉树。这里，根据后序序列可知最后一个元素F是根节点，因此先序序列的顺序是从根节点开始，先遍历右子树，再遍历左子树，得到FEDCBA。 **10. 已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7，3，5，l，2，则与F对应的二叉树的右子树中的结点个数为（D）** - **解析**：将森林转换为二叉树时，每棵树的第一个孩子变为二叉树的左子树，而兄弟节点变为二叉树的右子树。所以右子树的结点数等于森林中除第一棵树之外的所有树的结点数之和，即3+5+1+2=11。 **11. 若非连通无向图G含有21条边，则G的顶点个数至少为（B）** - **解析**：对于一个非连通无向图，至少有一个连通分量，如果要使顶点数最少，则应尽可能让这些连通分量中的一个连通分量具有最多的边。一个连通无向图中，如果有n个顶点，最多有n-1条边（构成一棵树）。为了达到21条边，最少需要一个连通分量构成一棵树加上一个或多个只有一个顶点的连通分量（不贡献边的数量）。因此，至少需要8个顶点才能构成这样的图。 **12. 如图所示的有向图的拓扑序列是（B）** - **解析**：拓扑排序是对有向无环图(DAG)的一种排序方法，它产生的结果是一个线性的排序序列，该序列保证了图中所有的有向边的方向都保持一致。在这个例子中，根据图中边的方向，正确的拓扑序列是c，a，d，b，e。 **13. 对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为（C）** - **解析**：在快速排序中，选择第一个元素6作为基准，比6小的元素移到左边，比6大的元素移到右边。最终序列应该是5、1、4、3、2排在6的左边，8、7排在6的右边。 **14. 分块查找方法将表分为多块，并要求（B）** - **解析**：分块查找方法将表分成多个块，每个块内的元素不必有序，但块与块之间必须有序。 **15. 便于进行布尔查询的文件组织方式是（D）** - **解析**：多关键字文件允许在文件中根据多个字段进行索引，这使得它非常适合进行复杂的布尔查询。 #### 二、填空题解析 **16. 数据的链式存储结构的特点是借助__指针__表示数据元素之间的逻辑关系。** **17. 如果需要对线性表频繁进行___插入__或__删除___操作，则不宜采用顺序存储结构。** **18. 如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是__top2=top1___。** **19. 静态存储分配的顺序串在进行插入、置换和__联接__等操作时可能发生越界。** **20. 广义表L=（a，（b，()））的深度为__2___。** **21. 任意一棵完全二叉树中，度为1的结点数最多为__1___。** **22. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中__边__的数目正相关。**