数据结构往年卷

选择题

1. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

选项：
- A. 8
- B. 63.5
- C. 63
- D. 7
答案： B. 63.5

2. 设有一个二维数组`A[m][n]`，假设`A[0][0]`存放位置在644（10），`A[2][2]`存放位置在676（10），每个元素占一个空间，则`A[3][3]`在（）位置，（10）表明用10进数表示。

选项：
- A. 692（10）
- B. 626（10）
- C. 709（10）
- D. 724（10）
答案： A. 692（10）
解释： 在二维数组中，元素的位置可以通过行和列的索引来计算。已知 $A[0][0] = 644$，每个元素占1个空间。我们可以计算 A[1][0]、A[1][1]、A[1][2]、A[2][0]、A[2][1]、A[2][2]的地址。
- A[2][2]的位置为 676，所以 A[2][2]之后的元素为 A[2][3]，以此类推。可以得出A[3][3] 的位置为：
- $676 + (3 - 2) \times n + (3 - 2) = 676 + n + 1$
- 假设 n=6，这样可以得出A[3][3] 在 692（10）的位置。

3. 一个有序顺序表有255个对象，采用顺序搜索查表，平均搜索长度为（）。

选项：
- A. 128
- B. 127
- C. 126
- D. 255
答案： A. 128
解释： 在顺序搜索中，平均搜索长度是 $(n + 1) / 2$，其中 $n$ 是元素的数量。对于255个对象，平均搜索长度为 $(255 + 1) / 2 = 128$。

4. 含5个结点（元素值均不相同）的二叉树搜索树有（）种。

选项：
- A. 54
- B. 42
- C. 36
- D. 65
答案： B. 42
解释： 对于具有 $n$ 个不同节点的二叉搜索树的构造方式，可以通过卡塔兰数计算。卡塔兰数公式为： $ C_n = $ 对于 $n = 5$： $ C_5 = = = 42 $

5. N个顶点的连通图至少有（）条边。

选项：
- A. N－1
- B. N
- C. N＋1
- D. 0
答案： A. N－1
解释： 对于一个连通图，至少需要 $N - 1$ 条边来保证图的连通性。 $N - 1$ 条边构成一棵生成树，确保所有顶点都是连通的。

6. 对于两个函数，若函数名相同，但只是（）不同则不是重载函数。

选项：
- A. 参数类型
- B. 参数个数
- C. 函数类型
- D. 函数个数
答案： C. 函数类型
解释： 在C++中，函数重载是指允许同一函数名根据不同的参数类型或参数个数来定义多个函数。如果两个函数的名称相同，但函数的返回类型不同，它们并不构成重载，因为返回类型不参与重载判定。

7. 若需利用形参直接访问实参，则应把形参变量表明为（）参数。

选项：
- A. 指针
- B. 引用
- C. 值
- D. 地址
答案： B. 引用
解释： 在C++中，如果希望通过形参直接访问实参并且允许修改实参的值，应该使用引用参数。引用参数是实参的别名，因此可以直接访问和修改实参。

8. 下面程序的时间复杂度为（）。

1
2
3

for(int i=0; i<m;i++)
    for(int j=0; j<n;j++)
        a[i][j]=i*j;

选项：
- A. $O(m^2)$
- B. $O(n^2)$
- C. $O(m*n)$
- D. $O(m+n)$
答案： C. $O(m*n)$
解释： 该程序包含两个嵌套的循环，外层循环的次数是 $m$，内层循环的次数是 $n$。因此，总的时间复杂度是 $O(m \times n)$。

9. 下面算法的时间复杂度为（）。

int f(unsigned int n) {
    if(n==0 || n==1) return 1;
    else return n * f(n-1);
}

选项：
- A. $O(1)$
- B. $O(n)$
- C. $O(n^2)$
- D. $O(n!)$
答案： B. $O(n)$
解释： 这是一个递归函数，计算 $n!$。每次递归调用的深度是 $n$，因此时间复杂度为 $O(n)$。

10. 设单链表中结点的结构为(data, link)。已知指针q所指结点是指针p所指结点的直接前驱，若在q与p之间插入结点*s，则应执行下列哪一个操作（）。

选项：
- A. s->link=p->link; p->link =s;
- B. q->link=s; s->link =p;
- C. p->link=s->link; s->link =q;
- D. p->link=s; s->link =q;
答案： B. q->link=s; s->link =p;
解释： 在链表中插入结点s到结点q和*p之间时，需要将指针q的link指向结点s，然后将结点s的link指向结点p。这样可以保持链表的结构完整。

11. 设单链表中结点的结构为(data, link)。若想摘除结点*p的直接后继，则应执行下列哪一个操作（）。

选项：
- A. p->link = p->link->link;
- B. p = p->link; p->link = p->link->link;
- C. p->link = p->link;
- D. p = p->link->link;
答案： A. p->link = p->link->link;
解释： 为了删除结点p的直接后继，应该将结点p的link指向它的后继的后继，即 p->link = p->link->link，这样可以从链表中跳过后继结点，实现摘除。

12. 栈的插入和删除操作在（）进行。

选项：
- A. 栈顶
- B. 栈底
- C. 任意位置
- D. 指定位置
答案： A. 栈顶
解释： 栈是一种后进先出（LIFO）的数据结构，插入（push）和删除（pop）操作均在栈顶进行。

13. 若让元素1，2，3依次进栈，则出栈次序不可能出现哪种情况（）。

选项：
- A. 3，2，1
- B. 2，1，3
- C. 3，1，2
- D. 1，3，2
答案： C. 3，1，2：
不可能。如果3出栈后，栈中剩下的顺序是1、2，因此1必须先于2出栈。而这个顺序无法通过任何合法的栈操作实现，因为3弹出后不可能将1留在栈内再弹出2。

14. 广义表A(a)，则表尾为（）。

选项：
- A. a
- B. (())
- C. 空表
- D. （a）
答案： A. a
解释： 广义表的表头通常是第一个元素，而表尾是除去表头后剩下的部分。对于广义表A(a)，表头是a，表尾为空，因此表尾为a。

15. 下列广义表是线性表的有（）。

选项：
- A. E(a,(b,c))
- B. E(a,E)
- C. E(a,b)
- D. E(a,L())
答案： C. E(a,b)
解释： 广义表的线性表特指只有一个层级的表。选项C中的E(a,b)是一个线性表，其包含的元素都是原子（单一元素），而其他选项都包含嵌套结构，不是线性表。

16. 折半搜索与二叉搜索树（即二叉排序树）的时间性能（）。

选项：
- A. 相同
- B. 完全不同
- C. 有时不相同
- D. 不确定
答案： C. 有时不相同
解释： 折半搜索在有序数组中进行，时间复杂度为 $O(\log n)$，而二叉搜索树的性能取决于树的结构。若二叉搜索树为平衡树，性能可与折半搜索相同；若为不平衡树，则可能变为 $O(n)$，因此二者的时间性能有时会不相同。

17. 采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（）。

选项：
- A. $O(n \log_2 n)$
- B. $O(n)$
- C. $O(\log_2 n)$
- D. $O(n)$
答案： C. $O(\log_2 n)$
解释： 折半搜索算法在每一步将搜索范围缩小一半，因此在长度为n的有序表中，平均搜索长度为 $O(\log_2 n)$。

18. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。

选项：
- A. 中序遍历
- B. 前序遍历
- C. 后序遍历
- D. 按层次遍历
答案： B. 前序遍历
解释： 深度优先遍历（DFS）首先访问节点然后再递归访问其子节点，这种访问顺序类似于二叉树的前序遍历。

19. 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做（）排序。

选项：
- A. 插入
- B. 选择
- C. 交换
- D. 外排序
答案： B. 选择
解释： 选择排序是一种简单的排序算法，它通过不断选择最小（或最大）元素并将其放到已排序部分的末尾，从而实现排序。

20. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。

选项：
- A. 中序遍历
- B. 前序遍历
- C. 后序遍历
- D. 按层次遍历
答案： D. 按层次遍历
解释： 广度优先遍历（BFS）是逐层访问图中的节点，访问完一层后再进入下一层，这种访问顺序与二叉树的按层次遍历相似。

判断题

（y） 直接选择排序是一种不稳定的排序方法。
- 解释： 直接选择排序在相同关键字的元素之间可能会改变它们的相对位置，因此是一个不稳定的排序算法。
（n） 折半搜索只适用于有序表，包括有序的顺序表和有序的链表。
- 解释： 折半搜索仅适用于有序的顺序表（数组）而不适用于链表，因为链表的访问时间是线性的，不能高效地直接访问中间元素。
（y） 数据的逻辑结构与数据元素本身的内容和形式无关。
- 解释： 数据的逻辑结构指的是数据元素之间的关系，而与元素的具体内容和形式无关。
（n） 数据结构是指相互之间存在一种或多种关系的数据元素的全体。
- 解释： 数据结构不仅仅是数据元素的集合，更重要的是它们之间的关系和组织方式。
（n） 线性表的逻辑顺序与物理顺序总是一致的。
- 解释： 线性表的逻辑顺序和物理顺序可以不一致。例如，链表的逻辑顺序是线性的，但存储在内存中的物理位置不一定是连续的。
（y） 线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。
- 解释： 链式存储结构（如链表）允许存储单元的地址不连续，因为每个元素通过指针相连。
（y） 二叉树是数的特殊情形。
- 解释： 二叉树是一种特定的树结构，每个节点最多有两个子节点，可以视为一种特殊的树。
（y） 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。
- 解释： 在二叉树中，叶子节点的遍历顺序关系可以确保中序遍历的最后一个叶子节点也是前序遍历的最后一个叶子节点。
（n） 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。
- 解释： 前序遍历的最后一个节点不一定是中序遍历的最后一个节点，因为前序遍历先访问根节点而后访问子树，不能确定其在中序中的相对位置。
（n） 任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。
- 解释： 二叉搜索树的搜索效率依赖于其高度，最坏情况下的搜索时间可能与顺序搜索相当，因此不总是优于顺序搜索。
（n） 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。
- 解释： 不同的输入顺序会导致不同的二叉搜索树结构，因此它们不一定相同。
（y） 最优二叉搜索树的任何子树都是最优二叉搜索树。
- 解释： 最优二叉搜索树的定义是为了优化搜索效率，因此其任何子树也应满足最优性质。
（y） 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。
- 解释： 插入新结点时，只需找到合适的位置并更新指针，不需要移动已有结点。
（y） 有 $n$（$n \geq 1$）个顶点的有向强连通图最少有 $n$ 条边。
- 解释： 有向强连通图要求每一对顶点都有路径相连，至少需要 $n$ 条边以保持这种连通性。
（n） 连通分量是无向图中的极小连通子图。
- 解释： 连通分量是指图中所有的连通子图，而不是“极小”的，因为连通分量可以包含多个顶点。
（n） 二叉树中任何一个结点的度都是2。
- 解释： 二叉树中的每个节点可以有0、1或2个子节点，因此并不是所有节点的度都是2。
（n） 单链表从任何一个结点出发，都能访问到所有结点。
- 解释： 单链表是线性的，如果从某个节点出发但该节点不是链表的头结点，就无法访问到链表的所有节点。

程序阅读填空

1. 在顺序表中第 $ i $ 个位置插入新元素 $ x $

template <class Type> int SeqList<Type>::Insert (Type & x, int i) {
    if (i < 0 || i > last + 1 || last == MaxSize - 1) return 0;  // 插入不成功
    else {
        last++;
        for (int j = last; j > i; j--)
            data[j] = data[j - 1];		
        data[i] = x;
        return 1;  // 插入成功
    }
}

2. 删去链表中除表头结点外的所有其他结点

template <class Type> void List<Type>::MakeEmpty() {
    ListNode<Type>* q;
    while (first->link != NULL) {
        q = first->link;  // 将表头结点后第一个结点从链中摘下
        first->link = q->link;
        delete q;  // 释放它 
    }
    last = first;  // 修改表尾指针
}

3. **删去链式队头结点（队头指针为 `QueueNode<Type>* front`），并返回队头元素的值**

template <class Type> Type Queue<Type>::DeQueue() {
    assert(!IsEmpty());  // 判队空的断言

    QueueNode<Type>* p = front;  // 填空部分
    Type retvalue = p->data;  // 保存队头的值

    front = front->link;  // 新队头
    delete p;
    return retvalue;
}

4. 最小堆的向下调整算法

template <class Type> void MinHeap<Type>::FilterDown(int start, int EndOfHeap) {
    int i = start, j = 2 * i + 1;  // j 是 i 的左子女
    Type temp = heap[i];
    while (j <= EndOfHeap) {
        if (j < EndOfHeap && heap[j].key > heap[j + 1].key) j++;  // 两子女中选小者
        if (temp.key <= heap[j].key) break;

        else {
            heap[i] = heap[j]; 
            i = j; 
            j = 2 * j + 1;  // 填空部分
        }
    }
    heap[i] = temp;  // 填空部分
}

5. 基于有序顺序表的折半搜索递归算法

template <class Type> int orderedList<Type>::BinarySearch(const Type & x, const int low, const int high) const {
    int mid = -1;
    if (low <= high) {
        mid = (low + high) / 2;  // 填空部分
        if (Element[mid].getKey() < x)
            mid = BinarySearch(x, mid + 1, high);  // 填空部分
        else if (Element[mid].getKey() > x)
            mid = BinarySearch(x, low, mid - 1);
    }
    return mid;
}

6. 直接插入排序的算法

template <class Type> void InsertionSort(datalist<Type> & list) {
    for (int i = 1; i < list.CurrentSize; i++)
        Insert(list, i);  // 填空部分
}

template <class Type> void Insert(datalist<Type> & list, int i) {
    Element<Type> temp = list.Vector[i];
    int j = i;  // 从后向前顺序比较    
    while (j > 0 && temp.getKey() < list.Vector[j - 1].getKey()) {
        list.Vector[j] = list.Vector[j - 1];  // 填空部分
        j--;
    }
    list.Vector[j] = temp;
}

7. 直接选择排序的算法

template <class Type> void SelectSort(datalist<Type> & list) {
    for (int i = 0; i < list.CurrentSize - 1; i++)
        SelectExchange(list, i);  // 填空部分
}

template <class Type> void SelectExchange(datalist<Type> & list, const int i) {
    int k = i;    
    for (int j = i + 1; j < list.CurrentSize; j++)
        if (list.Vector[j].getKey() < list.Vector[k].getKey())
            k = j;  // 当前具有最小关键码的对象  
    if (k != i) Swap(list.Vector[i], list.Vector[k]);  // 交换
}

8. 判断一个带表头结点的双向循环链表 L 是否对称相等的算法

int symmetry(DblList DL) {
    int sym = 1;
    DblNode *p = DL->rLink, *q = DL->lLink;
    while (p != q && p->rLink != q && sym == 1)  // 注意：此处 while 的首字母应为小写
        if (p->data == q->data) {
            p = p->rLink;  // 填空部分
            q = q->lLink;  // 填空部分
        }
        else
            sym = 0;
    return sym;
}

解答题

1. 线性表的顺序表与链表的优缺点

顺序表的优缺点

优点：
- 存取速度快：顺序存储结构下，元素在内存中是连续存放的，支持 O(1) 的随机访问。
- 占用内存小：结构简单，内存管理相对容易。
缺点：
- 插入和删除操作不灵活：需要移动大量元素，时间复杂度为 O(n)。
- 预先需要分配固定大小的内存，可能导致内存浪费或溢出。

链表的优缺点

优点：
- 插入和删除操作灵活：只需改变节点指针，时间复杂度为 O(1)。
- 不需要预先分配固定大小的内存，支持动态扩展。
缺点：
- 存取速度慢：需要逐个访问节点，随机访问时间复杂度为 O(n)。
- 额外的内存开销：每个节点除了存储数据外，还需要存储指针。

2. 生成的二叉搜索树

给定输入数据序列 {46, 25, 78, 62, 12, 37, 70, 29}，逐个插入形成二叉搜索树。

最终二叉搜索树结构如下：

数据结构往年卷

选择题

1. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。

2. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，则A[3][3]在（ ）位置，（10）表明用10进数表示。

3. 一个有序顺序表有255个对象，采用顺序搜索查表，平均搜索长度为（ ）。

4. 含5个结点（元素值均不相同）的二叉树搜索树有（ ）种。

5. N个顶点的连通图至少有（ ）条边。

6. 对于两个函数，若函数名相同，但只是（ ）不同则不是重载函数。

7. 若需利用形参直接访问实参，则应把形参变量表明为（ ）参数。

8. 下面程序的时间复杂度为（ ）。

9. 下面算法的时间复杂度为（ ）。

10. 设单链表中结点的结构为(data, link)。已知指针q所指结点是指针p所指结点的直接前驱，若在q与p之间插入结点*s，则应执行下列哪一个操作（ ）。

11. 设单链表中结点的结构为(data, link)。若想摘除结点*p的直接后继，则应执行下列哪一个操作（ ）。

12. 栈的插入和删除操作在（ ）进行。

13. 若让元素1，2，3依次进栈，则出栈次序不可能出现哪种情况（ ）。

14. 广义表A(a)，则表尾为（ ）。

15. 下列广义表是线性表的有（ ）。

16. 折半搜索与二叉搜索树（即二叉排序树）的时间性能（ ）。

17. 采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ ）。

18. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。

19. 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做（ ）排序。

20. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。

判断题

程序阅读填空

1. 在顺序表中第 $ i $ 个位置插入新元素 $ x $

2. 删去链表中除表头结点外的所有其他结点

3. 删去链式队头结点（队头指针为 QueueNode<Type>* front），并返回队头元素的值

4. 最小堆的向下调整算法

5. 基于有序顺序表的折半搜索递归算法

6. 直接插入排序的算法

7. 直接选择排序的算法

8. 判断一个带表头结点的双向循环链表 L 是否对称相等的算法

解答题

1. 线性表的顺序表与链表的优缺点

顺序表的优缺点

链表的优缺点

2. 生成的二叉搜索树

1. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

2. 设有一个二维数组`A[m][n]`，假设`A[0][0]`存放位置在644（10），`A[2][2]`存放位置在676（10），每个元素占一个空间，则`A[3][3]`在（）位置，（10）表明用10进数表示。

3. 一个有序顺序表有255个对象，采用顺序搜索查表，平均搜索长度为（）。

4. 含5个结点（元素值均不相同）的二叉树搜索树有（）种。

5. N个顶点的连通图至少有（）条边。

6. 对于两个函数，若函数名相同，但只是（）不同则不是重载函数。

7. 若需利用形参直接访问实参，则应把形参变量表明为（）参数。

8. 下面程序的时间复杂度为（）。

9. 下面算法的时间复杂度为（）。

10. 设单链表中结点的结构为(data, link)。已知指针q所指结点是指针p所指结点的直接前驱，若在q与p之间插入结点*s，则应执行下列哪一个操作（）。

11. 设单链表中结点的结构为(data, link)。若想摘除结点*p的直接后继，则应执行下列哪一个操作（）。

12. 栈的插入和删除操作在（）进行。

13. 若让元素1，2，3依次进栈，则出栈次序不可能出现哪种情况（）。

14. 广义表A(a)，则表尾为（）。

15. 下列广义表是线性表的有（）。

16. 折半搜索与二叉搜索树（即二叉排序树）的时间性能（）。

17. 采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（）。

18. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。

19. 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做（）排序。

20. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。

3. **删去链式队头结点（队头指针为 `QueueNode<Type>* front`），并返回队头元素的值**