2019-2020-1 数据结构期末试卷¶

2018级

科目：数据结构主讲教师：胡卉芪出卷人：胡卉芪

一、选择题（8分）¶

(1)以下说法正确的是（）

A 每个函数至少要有一个参数 B 每个函数都必须返回一个值

C 函数在被调用之前必须先声明 D 函数不能自己调用自己

（2）下列关于对象初始化的叙述中，正确的是（）

A 定义对象的时候不能对对象进行初始化

B 可以为一个对象多次调用构造函数初始化

C 定义对象时将自动调用构造函数进行初始化

D 在一个类中必须显式地定义构造函数实现初始化

（3）对类成员访问权限的控制，是通过设置成员的访问控制属性实现的，下列不是访问控制属性的是( )

A 公有类型 B私有类型 C 保护类型 D友元类型

（4）下列关于基类和派生类关系的叙述中，正确的是（）

A 每个类最多只能有一个直接基类

B 派生类中的成员可以访问基类中的任何成员

C 基类的构造函数必须在派生类的构造函数体中调用

D 派生类除了继承基类的成员，还可以定义新的成员

二、请写出程序运行的结果（6分）¶

#include<iostream> 
using namespace std; 
class base{
public: 
    virtual void print() const { cout<<"base::f()"<<endl; } 
};
class derived: public base { 
public: 
    virtual void print() const { cout<<"derived::f()"<<endl;}
}; 
void print(const base& obj) 
{ 
    obj.print(); 
} 
int main() 
{ 
  base* pb1=new derived(); 
  print(*pb1); 
  base* pb2=new base(*pb1); 
  print(*pb2); 
  base b; 
  print(b);
  delete pb1; 
  delete pb2; 
  return 0; 
}

三、请指出下述C++代码中三处语法或执行时的错误，每个指出的错误简述可能的解决方案, 并填入下述表格的错误1-3中(多写不加分)。（9分）¶

#include <stdio.h>
#include <string.h>
class CBuffer
{
    char * m_pBuffer;
    int m_size;
public:
    CBuffer()
    {
        m_pBuffer = NULL;
    }
    ~CBuffer()
    {
        Free();
    }
    void Allocte(int size){
        m_size = size;
        m_pBuffer = new char[size];
    }
private:
    void Free()
    {
            delete m_pBuffer;
            m_pBuffer = NULL;
    }
public:
    void SaveString(const char* pText) const
    {
        strcpy(m_pBuffer, pText);
        m_size = sizeof(pText);
    }
    char* GetBuffer() const
    {
        return m_pBuffer;
    }
};
int main(int argc, char* argv[])
{
    CBuffer buffer1;
    CBuffer buffer2(buffer1);
    buffer1.SaveString("Microsoft");
    printf (buffer1.GetBuffer());   
    return 0;
}

错误	类型	错误描述	改正方法
错误1
错误2
错误3

四、栈和队列（6分）¶

给出栈采用顺序存储(数组存储),在栈的存储结构中如何判别栈空与栈满？

设top用来存放栈顶元素的下标。 S->top表示栈顶。数组大小为Stack_Size。必要时可以引入栈内元素个数， S->count。

（1）判断栈S空：

（2）判断栈S满：

五、迷宫问题（8分）¶

用下述二维数组matrix[][]描述迷宫，初始时其中-1表示迷宫的墙， 0表示没有墙，可通行。现在起点在src位置，终点在des位置（src位置的值为1， des位置的值为0）。

-1	-1	-1	0
-1	-1	0	0
0	-1	-1	0
0	0	0	0
-1	-1	-1	0 des

现在Pos src为起点, 通过调用DFS(src, 1) 函数，请画出完整执行后的迷宫数组，填写在下面。代码中Pos是一个结构体:

struct Pos {
    int row; //表示数组的行
    int col; //表示数组的列
};
void DFS(Pos cur, int step) {
    //迷宫终点找到
    if (cur.row ==4 && cur.col == 4) {      
return;
    }
    //按照左，上，右，下的顺序探索迷宫
    int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}}; 
    Pos next;
    for (int z = 0; z < 4; z++) {
        next.row = cur.row + dir[z][0];
        next.col = cur.col + dir[z][1];
         if (matrix[cur.row][cur.col] == 0) {
            matrix[next.row][next.col] = step + 1;
            DFS_(next, step + 1);
         }
    }
}

待填写的二维数组：

六、排序，二分查找（7分）。¶

设有一组序列为（13，90，83，50，35，47，18，24，62）

1、给出第四趟的插入排序的结果：

2、排序完成之后，采用二分查找的方法，要求计算出查找关键字62时的比较次数。

七、二叉排序树（8分）。¶

已知二叉排序树由八个连续整数1-8组成，先序，后序遍历序列分别为

先序：4,2,1,3,5,8,6,7

后序：1,3,2,7,6,8,5,4

(1)画出二叉排序树的逻辑结构。

（2）画出删除节点4后的二叉排序树的逻辑结构。

八、堆（9分）。¶

现有一个以数组存储的完全二叉树：{15,9,7,8,20,1,5,4}。

（1）画出对应的完全二叉树。

（2）通过堆构建的方法，将该完全二叉树调整成一个小顶堆，画出该小顶堆。

（3）利用小顶堆堆排序的方法对数组进行降序排序，写出第二趟排序后数组的存储序列。（提示，小顶堆每次产生的最小值会放到数组末尾）

15,8,5,9,20,7,4,1 或 5,8,7,9,20,15,4,1

九、图（12分）。¶

给定一个无向带权图的邻接表：

（1）画出该无向带权图。

（2）从指定节点A开始，按照邻接表中的访问顺序，写出广度优先遍历序列。

A,B,C,D,E,F,G;

（3）从指定节点A开始，画出按prim算法求得的最小生成树。

十（7分）¶

已知两个长度为n的数组，分别存放两个升序的序列，现通过对换两个数组中的成员对两个数组进行调整，要求调整后两个序列仍然各自升序，且第一个序列的最后一个元素小于等于第二个序列的第一个元素。例如，

第一个数组为 4, 12, 28

第二个数组为 1, 9 , 29

输出为

第一个数组 1, 4, 9

第二个数组 12,28,29

（1）排除这两个数组本身，设计空间复杂度 O(n)的算法实现上述功能。

(2) 排除这两个数组本身，设计空间复杂度O(1)的算法实现上述功能。

十一（8分）¶

程序设计题1.给定两个单链表，它们相同的节点定义如下：

struct Node
{
Elemtype data;
Node *next;
}；

判断该这两个单链表中是否交汇，交汇的例子如下图所示，即在某个节点两个链表归并为同一个链表。

如果有，找到相交的节点。按照下列给出的接口和输入输出用伪代码实现相应功能。允许增加函数，也允许使用其他的数据结构，但请做详尽解释。

接口： Node* findLoopStart（Node *h1, Node *h2）; 输入：指向链表头节点的指针h1和h2， h1, h2相当于两个链表的第一个节点，并且它们一定都不为空；输出：如果相交，返回相交节点的指针，否则返回NULL。

十二、程序设计题2（12分）¶

给定一棵二叉树BT，树中节点定义如下：

struct BTNode 
{
Elemtype data;
BTNode *lchild;
BTNode *rchild;
}；

假设该二叉树已经构建好，root是指向BT根节点的指针，请按照下列给出的接口和输入输出用伪代码实现相应功能。允许增加函数，也允许使用其他的数据结构，但请做详尽解释。

（1）求BT中节点的最大距离，即BT中相距最远的两个节点之间的距离。接口：

int GetMaxDistance(root); 输入：指向BT根节点的指针root;输出：BT中相距最远的两个节点之间的距离。

int GetMaxDistance(root)
{
     int left_depth,right_depth;
     GetMaxDistance_2(root,left_depth,right_depth);
}

int GetMaxDistance_2(root,left_depth,right_depth)
{
     int ll_depth,lr_depth,rl_depth,rr_depth;
     int left_maxdist,right_maxdist;

     if(root == NULL)
     {  left_depth = 0;
        right_depth = 0;
        return 0;
     }

     left_maxdist = GetMaxDistance_2(root->lchild,ll_depth,lr_depth);
     left_depth = max(ll_depth,lr_depth);

     right_maxdist = GetMaxDistance_2(root->rchild,rl_depth,rr_depth);
     right_depth = max(rl_depth,rr_depth);

     return max(max(left_maxdist,right_maxdist),left_depth+right_depth);
}

（2）假设有一颗空的二叉树BT_copy，根节点指针为root_copy, 请将二叉树BT复制到BT_copy。接口：void CopyBTree(root,root_copy); 输入：指向BT根节点的指针root和指向BT_copy根节点的指针root_copy; 输出：无返回值。

void CopyBTree(root, root_copy)
{
    if(root==NULL)
       return;
    else{
       root_copy=(BTNode)malloc(sizeof(BTNode));
       root_copy->data=root->data;
       CopyBTree(root->lchild,root_copy->lchild);
       CopyBTree(root->rchild,root_copy->rchild);
     }   
}

2019-2020-1 数据结构 期末试卷¶