考研数据结构大题整合-创新互联

考研数据结构大题整合

创新互联建站于2013年开始,是专业互联网技术服务公司,拥有项目成都网站建设、成都网站制作网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元高县做网站,已为上家服务,为高县各地企业和个人服务,联系电话:18980820575目录
  • 考研数据结构大题整合
    • 二、TJP组
      • TJP组一
      • TJP组二
      • TJP组三

二、TJP组 TJP组一

四、画图/计算/证明/算法分析(30分)
(1)证明题(8分)
如果一棵树有n1个度为1的结点,n2个度为2的结点,…… ,nm个度为m的结点,证明叶结点的个数n0 = 1+ {提示:模仿二叉树性质证明}。


(2)画图及计算题(8分)
某工程的AOE网如右图所示,弧上的权值为活动a1~a10的期限(即完成活动所需的天数)。

求:
①该工程各事件的最早发生时间Ve和允许的最晚发生时间Vl及各活动的最早开始时间e和允许的最晚开始时间l (请列表Ve,Vl,e,l的各时间),
②完成此项工程至少需要多少时间,及哪些活动是关键活动?

在这里插入图片描述


(3)已知某段电文中仅可能出现C, A, T, F, I五个字符,它们出现的频度分别为35, 15, 25, 7, 18。请图示一棵哈夫曼树并给出各字符的哈夫曼编码。(7分)


(4)给出的一组记录的关键字{78,12,45,98,23,109,85,68,89,256,34},①写出对这组记录进行一趟快速排序的结果,并说明这趟排序中关键字比较的次数为多少;②将这组记录关键字建成一个大根堆(堆顶元素值大)。(7分)


五、程序填空(每格2分,共20分)
1.有序线性表类(带表头的单链表结构)的定义如下:

tmd 气死了

2.快速排序:对a[low]…a[high]的元素按关键字降序排序

void QuickSort(Datatype a[], int low, int high)
{
    int i = low, j = high;
    Datatype temp = a[low];
    while (i< j)
    {
        while (i< j && ___________)
            j--;
        if (i< j)
            a[i++] = a[j];
        while (i< j && a[i].key >= temp.key)
            ______________;
        if (i< j)
            a[j--] = a[i];
    }
    a[i] = temp;
    if (low< i)
        QuickSort(a, low, i - 1);
    if (i< high)
        ____________________;
}
void QuickSort(Datatype a[], int n)
{
    QuickSort(a, 0, n - 1);
}

TJP组二

四、画图/计算/证明/算法分析(30分)
(1)已知一组记录的关键字为{18,2,10,6,78,56,45,50,110,8}, 按输入顺序画出此组记录的平衡二叉树,并求在等概率情况下查找成功的平均查找长度。(8分)


(2)设装填因子为0.77, 散列函数H(Key) = Key MOD 11, 并反复用H(Key) +1解决冲突,试对(1)的记录关键字构造散列表,请图示该表。(7分)


(3)已知有向图的邻接矩阵为:

V0  V1   V2  V3   V4   V5
V0  0   ∞   ∞   ∞    ∞   ∞
V1  30   0   ∞   40    ∞   ∞
V2  ∞  20    0   ∞    ∞   10
V3  ∞  ∞   20    0    50   40
V4  10  ∞   ∞   ∞     0   ∞
V5  20  10   ∞   ∞    20    0

试给出:①原图,②邻接表,③逆邻接表,④强连通分量。(8分)


(4)已知关键字序列{38,12,21,77,65,7,38,53},图示采用快速排序方法(按关键字递增)对其进行第一趟排序时的过程(7分)


五、程序填空(每格2分,共20分)
1.有序线性表类的定义如下:

typedef char Datatype; // 或typedef int Datatype;
const int MaxListSize = 100;
class OrderSeqList
{
private:
    Datatype data[MaxListSize];
    int size; // 实际元素个数,即有效数据是data[0]..data[size-1]
public:
    OrderSeqList(void);
    ~OrderSeqList(void);
    int ListSize(void) const;        // 返回线性表实际大小,即返回size
    int ListEmpty(void) const;       // 判断线性表是否为空
    int Find(Datatype &item) const;  // 返回item在线性表中的位置
    Datatype GetData(int pos) const; // 取出线性表pos位置上的元素
    void Insert(Datatype item);      // 在有序线性表中插入新元素item
    Delete(Datatype item);           // 在有序线性表中删除元素item
    void ClearList(void);            // 清空线性表
};

下面是部分成员函数的实现:(这里的元素位置是指在data中的下标)

int OrderSeqList::Find(Datatype &item) const
{
    if (size == 0)
        return -1;
    int i = 0;
    while (________________________)
        i++;
    if (item == data[i])
        return i;
    else
        return -1;
}
void OrderSeqList::Insert(Datatype item)
{
    int i;
    if (___________________________)
    {
        cerr<< "顺序表已满,无法插入!"<< endl;
        exit(1);
    }
    for (i = size; (data[i - 1] >item) && (i >0); i--)
        data[i] = ___________;
    data[i] = __________________;
    size++;
}
OrderSeqList::Delete(Datatype item)
{
    if (size == 0)
    {
        cerr<< "顺序表已空,无元素可删!"<< endl;
        exit(1);
    }
    int loc = Find(item);
    if (loc != -1)
    {
        for (int j = loc; j< size - 1; j++)
            data[j] = _______________;
        _______________;
    }
}

2.编写一个删除子串的函数:

void deletestr(char *str, int start, int span)
{
    int i;
    int len = strlen(str);
    if ((start< 0) || (start >len - 1))
        return;
    if ((start + span< -1) || (start + span >len))
        return;
    if (span >0)
        for (i = start; i<= _______________; i++)
            str[i] = ________________;
    else
        for (i = __________________; i<= len + span + 1; i++)
            _______________;
}

TJP组三

四、画图/计算/证明/算法分析(30分)
(1)证明题(8分)
试证明二叉树的性质:若完全二叉树的深度为K,则对于具有n个结点的完全二叉树,其K是不大于long2n的最小正数。


(2)画图及计算题(8分)
某工程的AOE网如右图所示,弧上的权值为活动a1~a10的期限(即完成活动所需的天数)。
求:
①该工程各事件的最早发生时间Ve和允许的最晚发生时间Vl及各活动的最早开始时间e和允许的最晚开始时间l (请列表Ve,Vl,e,l的各时间),
②完成此项工程至少需要多少时间,及哪些活动是关键活动?

在这里插入图片描述


(3)已知某段电文中仅可能出现a, b, c, d, e五个字符,它们出现的频度分别为32, 15, 24, 8, 19。要求:①图示一棵哈夫曼树;②再图示一棵对应于该哈夫曼树的后根次序遍历线索二叉树。(7分)


(4)给出的一组记录的关键字{25,18,46,2,53,39,32,4,74,67,60,11},①图示一棵处于平衡状态的二叉排序树(二叉查找树);②列出在等概率情况下各关键字在查找成功时的平均查找次数。(7分)


// ToDo
## 三、LZH组
### LZH 组一
### LZH 组二
### LZH 组三
### LZH 组四
### LZH 组五
### LZH 组六
### LZH 组七
## 四、LB组
### LB组一
### LB组二
### LB组三
### LB组四
### LB组五
### LB组六
### LB组七
### LB组八

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文题目:考研数据结构大题整合-创新互联
地址分享:http://scyanting.com/article/hcspd.html