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

下列哪两个数据结构,同时具有较高的查找和删除性能?()

[v_act]有序数组
有序链表
AVL树
Hash表 [/v_act]

以下操作中,数组比链表速度更快的是____

[v_act]原地逆序
头部插入
返回中间节点
返回头部节点
选择随机节点 [/v_act]

坐标轴上从左到右依次的点为a[0]、a[1]、a[2]……a[n-1],设一根木棒的长度为L,求L最多能覆盖坐标轴的几个点?

[v_act]算法思想:开始时我把题目理解错了,以为是求a中最大子序列和使其等于L,实际上是求满足a[j]-a[i] <= L && a[j+1]-a[i] > L这两个条件的j与i中间的所有点个数中的最大值,即j-i+1最大,这样题目就简单多了,方法也很简单:直接从左到右扫描,两个指针i和j,i从位置0开始,j从位置1开始,如果a[j] – a[i] <= L则j++并记录中间经过的点个数,如果a[j] - a[i] > L则j–回退,覆盖点个数-1回到刚好满足条件的时候,将满足条件的最大值与所求最大值比较,然后i++,j++直到求出最大的点个数。

有两点需要注意:

(1)这里可能没有i和j使得a[j] – a[i]刚好等于L的,所以判断条件不能为a[j] – a[i] = L。
(2)可能存在不同的覆盖点但覆盖的长度相同,此时只选第一次覆盖的点。 [/v_act]

// 求最大覆盖点
#include 
int maxCover(int a[], int n, int L) {
    int count = 2, maxCount = 1, start;
    int i = 0, j = 1;
    while (i < n && j < n) {
        while ((j < n) && (a[j] - a[i] <= L)) {
            j++;
            count++;
        }
        // 退回到满足条件的j    
        j--;
        count--;
        if (maxCount < count) {
            start = i;
            maxCount = count;
        }
        i++;
        j++;
    }
    printf("covered point: ");
    for (i = start; i < start + maxCount; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return maxCount;
}
int main() {
    // test   
    int a[] = { 1, 3, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 21 };
    printf("max count: %d\n\n", maxCover(a, 13, 8));
    int b[] = { 1, 2, 3, 4, 5, 100, 1000 };
    printf("max count: %d\n", maxCover(b, 7, 8));
    return 0;
}

【0、2、1、4、3、9、5、8、6、7】是以数组形式存储的最小堆,删除堆顶元素0后的结果是()

[v_act]【2、1、4、3、9、5、8、6、7】
【1、2、5、4、3、9、8、6、7】
【2、3、1、4、7、9、5、8、6】
【1、2、5、4、3、9、7、8、6】 [/v_act]

在一个长为33厘米的光滑凹轨上,在第3厘米、第6厘米、第19厘米、第22 厘米、第26厘米处各有一个钢珠,凹轨很细,不能同时通过两个钢珠,开始时,钢珠运动方向是任意的。两个钢珠相撞后,以相同速度反向运动。假设所有钢珠初 始速度为每秒运动1厘米,那么所有钢珠离开凹轨的最长可能时间是()

[v_act]30
26
38
33 [/v_act]

给定如下代码: int x[4]={0}; int y[4]={1}; 数组x和y的值为()

[v_act]{0,0,0,0},{1,1,1,1}
{0,0,0,0},{1,0,0,0}
{0,不确定},{1,不确定}
与编译器相关 [/v_act]

声明一个指向含有10个元素的数组的指针,其中每个元素是一个函数指针,该函数的返回值是int,参数是int*,正确的是()

[v_act](int *p[10])(int*)
int [10]*p(int *)
int (*(*p)[10])(int *)
int ((int *)[10])*p
以上选项都不正确 [/v_act]

一个栈的输入序列为123、、、、、n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是()

[v_act]不确定
n-i+1
i
n-i [/v_act]

当很频繁地对序列中部进行插入和删除操作时,应该选择使用的容器是()

[v_act]vector
list
deque
stack [/v_act]

给定一个 query 和一个 text,均由小写字母组成。要求在 text 中找出以同样的顺序连 续出现在 query 中的最长连续字母序列的长度。例如, query 为“acbac”,text 为 “acaccbabb”,那么 text 中的“cba”为最长的连续出现在 query 中的字母序列,因此, 返回结果应该为其长度 3。请注意程序效率。

[v_act]最长公共子序列 [/v_act]

[dm href='http://www.cnblogs.com/ErinCodeMM/archive/2012/10/30/2747042.html']参考一[/dm]

[dm href='http://www.cnblogs.com/zhangchaoyang/articles/2012070.html']参考二[/dm]

栈和队的共同点是()

[v_act]都是先进后出
都是后进先出
只允许在端点处插入和删除元素
没有共同点 [/v_act]

设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按二路归并方法对该序列进行一趟扫描后的结果为 1 。
(输出结果请按照以下格式:ABCDEFG,字母之间没有逗号)

[v_act]DQFXAPBNMYCW[/v_act]

A,B两个整数集合,设计一个算法求他们的交集,尽可能的高效。

[v_act]
如果是有序的用二路归并求交集
如果是无序的可以用map或hash[/v_act]

和顺序栈相比,链栈有一个比较明显的优势是()

[v_act]通常不会出现栈满的情况
通常不会出现栈空的情况
插入操作更容易实现
删除操作更容易实现 [/v_act]

有一个二维数组a[1...100 , 1...65]有100行,65列,我们以行序为主序,如果该数组的基地址是10000,且每个元素占2个存储单元,请问a[56 , 22]的存储地址是 1 。注意是下标是从1开始的

[v_act]10000 + ((56 - 1) * 65 -1 + 22) * 2 = 17192 [/v_act]

Asume you have an object to describe customer data:{ ID(5 digit numeric) Family Name(string) Account Balance(currency) } If you have 500,000 Chinese customers records represented by instances of this object type , what set of data structures is best to get fast retrieval of customers (1) get IDs from Name and (2) get Name from ID?

[v_act](1) Tree with Hash(100 bucket) at leaves(2) Tree with linked list at leaves.
(1) Tree with linked list at leaves(2) Array.
(1) Tree with linked list at leaves(2) Hash(10,000 buckets)
(1) Sort linked list(2) Array. [/v_act]

链表和数组的区别。

[v_act]在有序的情况下搜索
插入和删除
随机访问
数据存储类型 [/v_act]

C#程序段的结果: int[][] array = new int[3][]{ new int[3]{5,6,2}, new int[5]{6,9,7,8,3}, new int[2]{3,2} }; array[2][2] 返回()

[v_act]9
6
2
溢出 [/v_act]

线性表L=(a1,a2,a3,……ai,……an),下列说法正确的是?

[v_act]每个元素都有一个直接前件和直接后件
线性表中至少要有一个元素
表中诸元素的排列顺序必须是由小到大或由大到小
除第一个和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件 [/v_act]

下列数据结构具有记忆功能的是?

[v_act]队列
循环队列

顺序表 [/v_act]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构题库之数组(一)

Leave a Reply