• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

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

极客题库 Geekerstar 11个月前 (06-12) 712次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

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

方便运算
方便存储
提高运算速度
减少存储空间

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

不能是子表
只能是子表
只能是原子
是原子或子表

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

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

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

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?

Search complexity when both are sorted

Dynamically add/remove

Random access efficiency

Data storage type


丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构题库之数组(四)
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00