数据结构题库之数组（四）

对矩阵压缩存储是为了()

一个非空广义表的表尾()

编写一个方法，去掉一个数组的重复元素。

链接：https://www.nowcoder.com/questionTerminal/21d25135db744ee0868d7bfc23fb2f05
来源：牛客网

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N 255
 
static int tmp[N];
 
void delete_duplication(char *src)
{
     
    int i, j;
    int index;
    int length = strlen(src);
 
    for (i = 0; i < length; ++i)
    {
        /* code */
        index = (int)(*(src + i));
        tmp[index] += 1;   
 
        if (tmp[index] == 1)
        {
            /* code */
            printf("%c", index);
        }
    }
     
}
 
 
int main(void)
{
    /* code */
    //char str[] = "asadasddasfadsgdfggdfgsdf";
    char str[] = "qwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnm";
 
    delete_duplication(str);
 
    return 0;
}

给定如下的 n*n 的数字矩阵，每行从左到右是严格递增， 每列的数据也是严格递增

1 2 3

3 5 6

4 8 9

现在要求设计一个算法， 给定一个数 k 判断出 k 是否在这个矩阵中。 描述算法并且给出时间复杂度（不考虑载入矩阵的消耗）

int searchK(int int_arr[][],int n,int startlow,int startclm,int k)
{
        int lefttemp=0;
        int downtemp=0;
        int i=0;
        while(int_arr[startlow+i][startclm+i]
                i++;
        if (i==n)
                return 0;
        else if(arr[i][i]==k)
                reuturn 1;
        else
        return searchK(int_arr,n,startlow,startclm+i,k)+searchK(int_arr,n,startlow+i,startclm,k);
}

在一个长度为 n 的整形数组 a 里，除了三个数字只出现一次外，其他的数字都出现了 2 次。请写程序输出任意一个只出现一次的数字，程序时间和空间复杂度越小越好。

例如：a = {1,3,7,9,5,9,4,3,6,1,7}，输出 4 或 5 或 6
C/C++：
void find(int* a , int n);

Java:
void find(int[] a);

int lowbit(int x) 
{ 
    return x&~(x-1); 
} 
   
void find(int* a , int n) 
{ 
    int i , xors; 
    xors = 0; 
    for(i = 0 ; i < n ; ++i)
        xors ^= a[i];
        // 三个数两两的异或后 lowbit 有两个相同，一个不同，可以分为两组
    int fips = 0;
    for(i = 0 ; i < n ; ++i)
        fips ^= lowbit(xors ^ a[i]); // 表示的是：
    flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)
    int b; // 假设三个只出现一次的其中一个数为 b
    b = 0;
    for(i = 0 ; i < n ; ++i) {
        if(lowbit(xors ^ a[i]) == fips)
           b ^= a[i];
     } // 成功找到三个数中一个数
     cout<<b<<endl; 
 
}

数组不适合作为任何二叉树的存储结构()

从逻辑结构上看,n 维数组的每个元素均属于 1 个 n 维向量()

稀疏矩阵压缩存储后,必会失去随机存取功能()

数组必须是同类型值的集合()

数组可看成线性结构的一种推广,因此与线性表一样,可以对它进行插入,删除等操作()

一个稀疏矩阵 Am*n 采用三元组形式表示,若把三元组中有关行下标与列下标的值互换,并把 m 和 n 的值互换,则就完成了 Am*n 的转置运算()

下面描述中正确的为：

二维以上的数组其实是一种特殊的广义表()

广义表的取表尾运算,其结果通常是个表,但有时也可是个单元素值()

若一个广义表的表头为空表,则此广义表亦为空表()

广义表中的元素或者是一个不可分割的原子,或者是一个非空的广义表()

数组是一种线性结构,因此只能用来存储线性表()

广义表(((a,b,c),d,e,f))的长度是 4()

What is the difference between a linked list and an array?

喜欢 (0)赏

[247507792@qq.com]

分享 (0)