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

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

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

For the following Java or C# code(3 Points),What will my Array3[2][2] returns?

int [][] myArray3 = 
new int[3][]{ 
new int[3]{5,6,2}, 
new int[5]{6,9,7,8,3}, 
new int[2]{3,2}
};  
9
2
6
overflow

将一个集合拆分成两个不相交的子集,两个子集元素之和相等,如{1, 2, 3, 4, 5, 6, 7},拆分成: {2, 5, 7}, {1, 3, 4, 6} 给出一个集合,求所有符合上面要求的拆分,效率最高分越高,函数原型为int cal_num(int n);

#include <iostream>
using namespace std;
#define MAXN 100
  
void dfs(int pi,int curSum,bool res[],int n,int half,int &num,int left[])
{
    for(int i=pi+1;i<=n;i++) { 
        res[i]=true; 
        if(curSum+left[i]=1;i--)
            left[i]=i+left[i+1]; 
    dfs(0,0,res,n,half,cnt,left);
    return cnt;
}
int main()
{
    int n=20;
    int num=cal_num(n);
    printf("num=%d\n",num);
    return 0;
}

在一个长度为n的顺序表中删除第i个元素,要移动_______个元素。如果要在第i个元素前插入一个元素,要后移_________个元素。

n-i,n-i+1
n-i+1,n-i
n-i,n-i
n-i+1,n-i+1

二叉树的前序遍历和中序遍历序列如下:前序遍历:EFHIGJK;中序遍历:HFIEJKG。该二叉树根的右子树的根是()

E
F
G
H

有两个从小到大排好序的数组,长度分别为N和M,将这两个数组合并成一个有序数组的最小比较次数是?

Min(N, M)
M + N -1
N + M
Max(N, M)

现在有 n=2^k(k为正整数)支足球队,编号为0,1,…,n-1,给出二维数组winner[][],winner[i][j]表示当编号为i的队和编号为j的队比赛时,会胜出的队伍的编号,winner[i][j]一定是i,j之中的一个(不存在平局),输入保证winner[i][j]=winner[j][i],现在给出一个单败淘汰赛的签位一位数组order[],order[i]表示第i个签位上的队伍的编号,order保证是0到n-1的一个排列。返回比赛最后的排名顺序,同一轮被淘汰的队伍名次并列,并列的队伍之间的排名顺序任意。要求时间和空间复杂度尽量低。

将结果写到一维数组result[]里面即可。 接口定义:
c:
void calculate_result(int n, int **winner, int *order, int *result);
c++:
void calculate_result(int n, vectorwinner, vectororder, vectorresult);
Java:
void calculate_result(int n, int [][]winner, int []order, int []result);

用一维数组存储二叉树时,总是以前序遍历顺序存储结点()


给定n个数(1,2,……,n),从中选取任意两两不同的k个数请编写程序输出所有的可能的选择,则要求不重不漏。

程序思路:定义一个数组,其下标表示1到n个数,数组元素的值为1表示其下标代数的数被选中,为零则没被选中。

首先初始化,将数组前k个元素置1,表示第一个组合为前k个数。 然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”组合。

同时将其左边的所有“1”全部移到数组的最左端。 当第一个“1”移动到数组的n-k的位置,即k个“1”全部移动到最右端时,就得到了最后一个组合。

2个有序数组,长度为n,查找两个数组整体中值(中值:一组数组中居中的数),复杂度是()?用()方法?

时间复杂度O(logn)

方法如下:

(1)取所有数组的最小值和最大值,求出全体的最大值和最小值min max然后取m=(min+max)/2

(2)用m在所有数组中搜索,找到比m小的数的个数n1,若n1大于M*N/2,则mid=(min+mid)/2,否则mid=(mid+max)/2

(3)重复上述搜索一共循环log(max-min)次

在一个元素个数为N的数组里,找到升序排在N/5位置的元素的最优算法时间复杂度是

O(n)
O(n log n)
O(n (log n)2)
O(n 3/2)

有一个二维数组A[10][5],每个数据元素占1个字节,且A[0][0]的存储地址是1000,则A[i][j]的地址是多少 ?

1000+10i+j
1000+i+j
1000+5i+j
1000+10i+5j

下列哪些不是线性表?

队列

关联数组
链表

请给Array本地对象增加一个原型方法,它用于删除数组条目中重复的条目(可能有多个),返回值是一个包含被删除的重复条目的新数组。

Array.prototype.distinct = function() {
    var ret = [];
    for (var i = 0; i < this.length; i++)
    {
        for (var j = i+1; j < this.length;) {   
            if (this[i] === this[j]) {
                ret.push(this.splice(j, 1)[0]);
            } else {
                j++;
            }
        }
     }
     return ret;
}
//for test
alert(['a','b','c','d','b','a','e'].distinct());

假定一个二维数组的定义语句为“int a[3][4]={{3,4},{2,8,6}};”,则元素a[1][2]的值为

6
4
2
8

有两个N*N的矩阵A和B,想要在PC上按矩阵乘法基本算法编程实现计算A*B。假设N较大,本机内存也很大,可以存下A、B和结果矩阵。那么,为了计算速度,A和B在内存中应该如何存储(按行存指先存储第一行,再第二行,直到最后一行;按列存指先存储第一列,再第二列,直到最后一列)?

A按行存,B按行存。
A按行存,B按列存。
A按列存,B按行存。
A按列存,B按列存。

对线性表进行折半查找时,要求线性表必须()

以顺序方式存储
以顺序方式存储,且数据元素有序
以链接方式存储
以链接方式存储,且数据元素有序

当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度()

必定快
必定不快
在大部分情况下要快
取决于表递增还是递减

下面的说法那个正确

#define NUMA 10000000
#define NUMB 1000
int a[NUMA], b[NUMB];
  
void pa()
{
    int i, j;
    for(i = 0; i < NUMB; ++i)
        for(j = 0; j < NUMA; ++j)
            ++a[j];
}
void pb()
{
    int i, j;
    for(i = 0; i < NUMA; ++i)
        for(j = 0; j < NUMB; ++j)
            ++b[j];
}
pa 和 pb 运行的一样快
pa 比 pb 快
pb 比 pa 快
无法判断

既希望较快的查找又便于线性表动态变化的查找方法是

()


顺序查找
折半查找
分块查找
哈希法查找


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

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

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

客服QQ


QQ:2248886839


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