数据结构题库之数组(四)

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

[v_act]方便运算
方便存储
提高运算速度
减少存储空间 [/v_act]

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

[v_act]不能是子表
只能是子表
只能是原子
是原子或子表 [/v_act]

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

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

#include 
#include 
#include 
 
#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是否在这个矩阵中。 描述算法并且给出时间复杂度(不考虑载入矩阵的消耗)

[v_act]算法思想: 沿着对角线查找,获得i,使得k位于a[i][i]与a[i+1][i+1]之间。 k只可能存在于a[i][i]对应的右上角矩阵 和a[i+1][i+1]对应的左下角矩阵。 使用递归法继续查找即可。 时间复杂度 O(n)[/v_act][dm href='']

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<

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

[v_act]对
[/v_act]

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

[v_act]
错 [/v_act]

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

[v_act]
错 [/v_act]

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

[v_act]对
[/v_act]

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

[v_act]对
[/v_act]

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

[v_act]对
[/v_act]

下面描述中正确的为:

[v_act]线性表的逻辑顺序与物理顺序总是一致的。
线性表的顺序存储表示优于链式存储表示。
线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
二维数组是其数组元素为线性表的线性表。 [/v_act]

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

[v_act]
错 [/v_act]

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

[v_act]对
[/v_act]

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

[v_act]对
[/v_act]

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

[v_act]对
[/v_act]

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

[v_act]对
[/v_act]

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

[v_act]对
[/v_act]

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

[v_act]Search complexity when both are sorted

Dynamically add/remove

Random access efficiency

Data storage type [/v_act]

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构题库之数组(四)
分享到:
赞(0)

评论抢沙发

评论前必须登录!