王道数据结构课后题

Author： MixZou
发布时间：September 19, 2021
176views
No comments
109 words
Categories：笔记学习

# 数据结构习题

> 未整理，只是记录问题

## 选择填空知识点

### 线性表

- 栈是抽象数据类型，只表示逻辑结构
- 线性表既可以用顺序存储方式实现又可以用链式存储实现
- $O(1)<O(log_2n)<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$
- 线性表（逻辑结构）定义：相同数据类型的有限序列
- 存取方式指读写方式，顺序表支持随机存取
- 顺序表和链表是根据线性表的存储结构来划分概念，而有序表只描述元素之间的逻辑关系
- 执行图的广度优先遍历需要使用队列作为辅助存储空间
- **有序单链表上做顺序查找，查找成功的平均查找长度与在无序顺序表或有序顺序表上做顺序查找的平均查找长度相同，都是$(n+1) / 2$**
- **选择排序算法的比较次数始终为$n(n-1)/2$，与序列状态无关**

### 查找

- 折半查找过程所对应的判定树是一棵平衡二叉树
- 散列表查找中，评判一个散列函数优劣的两个主要条件是：值均匀分布于表空间以减少冲突；函数尽可能简单以方便计算

### 树

- 二叉树转化为森林的方法：从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…直到所有这些根节点与右孩子的连线都删除为止

### 图

- 执行图的广度优先遍历需要使用队列作为辅助存储空间
- **具有n个顶点的无向图至少有$(n-1)(n-2)/2+1$条边才能确保是一个连通图，最少是$n-1$条**

## 代码题

### 线性表

顺序表删除唯一最小值并由最后一个元素补空

```c
bool Del_Min(SqList &L, ElemType &value){
    if(L.length==0)
        return false;
    value = L.data[0];
    int position = 0;
    for(int i=1;i<L.length;i++){
        if(L.data[i]<value){
            value = L.data[i];
            positon = i;
        }
    }
    L.data[postiton] = L.data[L.length-1];
    L.length--;
    return true;
}
```

空间复杂度O(1)，将顺序表元素逆置

``` c
void Reverse(SqList &L){
    ElemType temp;
    for(int i=0; i<L.length/2; i++){
        temp = L.data[i];
        L.data[i] = L.data[L.length-i-1];
        L.data[L.length-i-1] = temp;
    }
}
```

长度为n顺序表L，时间复杂度O(n)、空间复杂度O(1)。删除所有值为x的元素

``` c
void DelX(SqList &L, ElemType x){
    int k = 0;
    for(int i=0; i<L.length; i++){
        if(L.data[i]!=x){
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}
```

有序表删除给定值s与t之间所有元素，要求s<t

```c
bool DelRange(SqList &L, ElemType s ElmeType t){
    int i, j;
    if(L.length==0 || s>=t)
        return false;
    for(i=0; i<L.length && L.data[i]<s; i++);
    if(i>L.length)
        return false;
    for(j=i; j<L.length && L.data[j]>t; j++);
    for(j<L.length; i++; j++)
        L.data[i] = L.data[j];
    L.length = i;
    return true;
}
```

顺序表删除在定值s到t之间的所有值，包含s和t，要求s<t

```c
bool DelRange(SqList &L, ElemType s ElmeType t){
    int i,k=0;
    if(L.length==0 || s>=t)
        return false;
    for(i=0; i<L.length; i++){
        if(L.data[i]>=s && L.data[i]<=t)
            k++;
        else
            L.data[i-k] = L.data[i];
    }
    L.length -= k;
    return true;
}
```

有序表删除所有值重复的元素

```c
bool Delete_Same(SeqList &L){
    if(L.length==0)
        return false;
    int i,j;
    for(i=0, j=1; j<L.length; j++)
        if(L.data[i]!=L.data[j])
            L.data[++i] = L.data[j];
    L.length = i+1;
    return true;
}
//因为有序表相同值的数一定在连续位置上
```

将两个有序表合并成新的有序顺序表

```c
bool Merge(SeqList A, SeqList B, SeqList &C){
    if(A.length+B.length > C.maxSize)
        return false;
    int i=0, j=0, k=0;
    while(i<A.length && j<B.length){
        if(A.data[i]≤B.data[j])
            C.data[k++] = A.data[i++];
        else
            C.data[K++] = B.data[j++];
    }
    while(i<A.length)
        C.data[k++] = A.data[i++];
    while(j<B.length)
        C.data[k++] = B.data[j++];
    C.length=k;
    return true;
}
```

线性表元素递增且有序按顺序存储，寻找数值为x的元素，找到后与后继元素交换位置，若找不到将其插入表中，使表中元素仍递增有序

```c
void SearchExchangeInsert(ElemType A[], ElemType x, ElemType temp){
    int low=0, high=n-1, mid;
    while(low<=high){
        mid = (low+high)/2;
        if(A[mid]==x)
            break;
        else if(A[mid]<x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    if(A[mid]==x && mid!=n-1){
        temp = A[mid];
        A[mid] = A[mid+1];
        A[mid+1] = temp;
    }
    if(low>high){
        for(int i=n-1; i>high; i--)
            A[i+1] = A[i];
        A[i+1] = x;
    }
}
```

已知一维数组[m+n]中依次存放两个线性表，将数组中两个线性表位置互换

``` c++
typedef int DataType;

void Reverse(DataType A[], int left, int right, int arraySize){
    //逆置
    if(left>=right || right>=arraySize)
        return;
    int mid = (left+right)/2;
    for(int i=0; i<=mid-left; i++){
        DataType temp = A[left+i];
        A[left+i] = A[right-i];
        A[right-i] = temp;
    }
}

void Exchange(DataType A[], int m, int n, int arraySize){
    /*
    数组A[m+n]中，从0到m-1存放顺序表a1，a2.。。am，从m到m+n+-1存放顺序表b1.。。bn，将这两个表的位置互换
    */
    Reverse(A, 0, m+n-1, arraySize);
    Reverse(A, 0, n-1, arraySize);
    Reverse(A, n, m+n-1, arraySize);
}
```

将n(n>1)个整数存放到一维数组R中，设计一个在空间时间尽可能高效的算法，将R中保存的序列循环左移p个位置0<p<n

```c++
/*
基本思路：将一个数组按p分成a、b两个数组；a是前p个元素，b是余下n-p个，先后将a、b逆置，再将整个数组逆置
*/
void Reverse(int R[], int from, int to){
    int i, temp;
    for(i=0; i<(to-from+1)/2; i++){		//在一半的时候就可以对应逆置
        temp = R[from+i];
        R[from+i] = R[to-i];
        R[to-i] = temp;
    }
}

void Converse(int R[], int n, int p){
    Reverse(R, 0, p-1);					//O(p/2)
    Reverse(R, p, n-1);					//O((n-p)/2)
    Reverse(R, 0, n-1);					//O(n-1)
}

/*
另解：借助辅助数组思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回R中的后续单元。时间复杂度O(n),空间复杂度O(p)
*/
```

一个长度为L(L≥1)的升序序列S，S1和S2的中位数是11，现在两个等长升序序列A和B，找出它们的中位数

```c++
/*
思路；设A、B中位数分别为a、b；若a=b，即为所求中位数；a<b，舍弃A中较小的一半，B中较大的一半，要求舍弃长度相等；a>b，舍弃A中较大的一半，B中较小的一半，要求舍弃长度相等；在保留的两个升序序列中，重复以上三个步骤，直到两个序列中均只剩下一个元素为止，较小的为中位数；O(log_2 n)，空间复杂度O(1)
*/

int M_Search(int A[], int B[], int n){
    int s1=0, d1=n-1, m1, s2=0, d2=n-1, m2;		//首位数、末位数、中位数
    while(s1!=d1 || s2!=d2){
        m1 = (s1+d1)/2;
        m2 = (s2+d1)/2;
        if(A[m1] == B[m2])
            return A[m1];
        if(A[m1]<B[m2]){
            if((s1+d1)%2==0){
                s1 = m1;
                d2 = m2;
            }
            else{
                s1 = m1 + 1;
                d2 = m2;
            }
        }
        else{
            if((s1+d1)%2==0){
                d1 = m1;
                s2 = m2;
            }
            else{
                d1 = m1 + 1;
                s2 = m2;
            }
        }
    }
    return A[s1]<B[s2]?A[S1]:B[s2];
}
```

已知整数序列$A=(a_0,a_1,...,a_{n-1})，其中0≤a_i<n(0≤i<n)。若存在a_{p1}=a_{p2}=...a_{pm}=x，且m>n/2(0≤p_k<n,1≤k≤m),则称x为A的主元素。$假设A中的n个元素保存在一维数组中，找出A的主元素并输出

```c++
int Majority(int A[], int n){
    int i, c, count=1;
    c = A[0];				//c保存候选主元素
    for(i=0; i<n; i++){
        if(A[i] == c)
            count++;
        else{
            if(count>0)
                count--;
            else{			//更换候选主元素，重新技术
                c = A[i];
                count = 1;
            }
        }      
    }
    if(count>0){			//统计候选元素实际出现次数
        for(i=count=0; i<n; i++){
            if(A[i]==c)
                count++;
        }
    }
    if(count>n/2)
        return c;
    else
        return -1;
}

/*
思路：选取候选的主元素；依次扫描所给数组每一个整数，将第一个遇到的整数保存到c中，记录次数1；若遇到下一个整数仍为它则计数加1，否则减1；当计数等于0时，将遇到的下一个整数保存到c中，重新计数为1；重复，直到扫描完整个数组元素。
判断c中元素是否为真正的主元素，再次扫描整个数组，统计c出现次数，若大于n/2，则为主元素。
*/
```

给定n(n>1)个整数的数组，找出数组中未出现的最小正整数，例如数组{-5,3,2,3}中未出现的最小正整数是1

```c++
int findMissMin(int A[], int n){
    int i, *B;
    B = (int *)malloc(sizeof(int)*n);	//B为标记数组
    memset(B, 0, sizeof(int)*n);		//初始化赋值为0
    for(i=0; i<n; i++){
        if(A[i]>0 && A[i]<=n)			//小于等于n的数出现，标记在B中
            B[A[i]-1] = 1;
    }
    for(i=0; i<n; i++)					//寻找第一个未被标记的
        if(B[i]==0)
            break;
    return i+1;
}

/*
要求时间高效则采用空间换时间的办法。数组B记录A中是否出现了1～n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B数组元素全部为0.由于A中含有n个整数，因此可能返回的值在1～n+1，当A中n个数恰好为1～n时，返回n+1；
当A中出现小于0或大于n的数时，导致1～n中出现空位，返回的结果必然在1～n，所以，当A中出现前面所述的值时，不采取任何操作；
空间复杂度n，时间复杂度n
*/
```

定义三元组abc，均为正数。它们的距离D=｜a-b｜+｜b-c｜+｜c-a｜。给定3个非空整数集合，安升序分别存在3个数组中，计算并输出所有可能的三元组中的最小距离

```c++
#define INT_MAX 0x7fffffff
/*
F的二进制码为 1111
7的二进制码为 0111
这样一来，整个整数 0x7FFFFFFF 的二进制表示就是除了首位是 0，其余都是1
就是说，这是最大的整型数 int（因为第一位是符号位，0 表示他是正数）
*/

//获取绝对值
int abs_(int){
    if(a<0)
        return -a;
    else
        return a;
}

//判断是否三者最小
bool xls_min(int a, int b, int c){
    if(a<=b && a<=c)
        return true;
    return false;
}

int findMinofTrip(int A[], int n, int B[], int m, int C[], int p){
    //D_min用于记录三元组的最小距离，初值赋为INT_MAX
    int i=0, j=0, k=0, D_min=INT_MAX, D;
    while(i<n && j<m && k<p && D_min>0){
        D = abs_(A[i]-B[j])+abs_(B[j]-C[k])+abs_(C[k]-A[i]);
        if(D<D_min)
            D_min = D;
        if(xls_min(A[i],B[j],C[k]))
            i++;
        else if(xls_min(B[j],C[k]),A[i])
            j++;
        else
            k++;
    }
    return D_min;
}
```

Last modification：October 10th, 2021 at 05:21 pm

如果觉得我的文章对你有用，请随意赞赏

END

本文作者： MixZou
文章标题：王道数据结构课后题
本文地址：http://feiqiuz.com/index.php/archives/14/
版权说明：若无注明，本文皆MixZou的小窝原创，转载请保留文章出处。

王道数据结构课后题

MixZou • 2021 年 09 月 19 日

# 数据结构习题

> 未整理，只是记录问题

## 选择填空知识点

### 线性表

### 查找

### 树

### 图

- 执行图的广度优先遍历需要使用队列作为辅助存储空间
- **具有n个顶点的无向图至少有$(n-1)(n-2)/2+1$条边才能确保是一个连通图，最少是$n-1$条**

## 代码题

### 线性表

顺序表删除唯一最小值并由最后一个元素补空

空间复杂度O(1)，将顺序表元素逆置

长度为n顺序表L，时间复杂度O(n)、空间复杂度O(1)。删除所有值为x的元素

有序表删除给定值s与t之间所有元素，要求s<t

顺序表删除在定值s到t之间的所有值，包含s和t，要求s<t

有序表删除所有值重复的元素

将两个有序表合并成新的有序顺序表

线性表元素递增且有序按顺序存储，寻找数值为x的元素，找到后与后继元素交换位置，若找不到将其插入表中，使表中元素仍递增有序

已知一维数组[m+n]中依次存放两个线性表，将数组中两个线性表位置互换

``` c++
typedef int DataType;

将n(n>1)个整数存放到一维数组R中，设计一个在空间时间尽可能高效的算法，将R中保存的序列循环左移p个位置0<p<n

void Converse(int R[], int n, int p){
    Reverse(R, 0, p-1);					//O(p/2)
    Reverse(R, p, n-1);					//O((n-p)/2)
    Reverse(R, 0, n-1);					//O(n-1)
}

一个长度为L(L≥1)的升序序列S，S1和S2的中位数是11，现在两个等长升序序列A和B，找出它们的中位数

给定n(n>1)个整数的数组，找出数组中未出现的最小正整数，例如数组{-5,3,2,3}中未出现的最小正整数是1

//获取绝对值
int abs_(int){
    if(a<0)
        return -a;
    else
        return a;
}

//判断是否三者最小
bool xls_min(int a, int b, int c){
    if(a<=b && a<=c)
        return true;
    return false;
}

王道数据结构课后题

Leave a Comment Cancel reply

C语言数据结构

王道数据结构课后题

你好，九月，我不好

心肌衰弱预测

About Me

About Me

AE Network

心肌衰弱预测

相册

C语言数据结构

王道数据结构课后题