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

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

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

以下数据结构属于非线性数据结构的是

队列
线性表
二叉树

Which of the following statements are true?

We can create a binary tree from given inorder and preorder traversal sequences.
We can create a binary tree from given preorder and postorder traversal sequences.
For an almost sorted array, insertion sort can be more effective than Quicksort.
Suppose T(n) is the runtime of resolving a problem with n elements, T(n) = Θ(1) if n = 1; T(n) = 2T(n/2) + Θ(n) if > 1; so T(n) is Θ(n log n).
None of the above.

说出ArrayList,Vector, LinkedList的存储性能和特性?

ArrayList 采用的是数组形式来保存对象的,这种方式将对象放在连续的位置中,所以最大的缺点就是插入删除时非常麻烦 LinkedList 采用的将对象存放在独立的空间中,而且在每个空间中还保存下一个链接的索引 但是缺点就是查找非常麻烦 要丛第一个索引开始

ArrayList和Vector都是用数组方式存储数据,此数组元素数要大于实际的存储空间以便进行元素增加和插入操作,他们都允许直接用序号索引元素,但是插入数据元素涉及到元素移动等内存操作,所以索引数据快而插入数据慢.

Vector使用了sychronized方法(线程安全),所以在性能上比ArrayList要差些.
LinkedList使用双向链表方式存储数据,按序号索引数据需要前向或后向遍历数据,所以索引数据慢,是插入数据时只需要记录前后项即可,所以插入的速度快。

下面哪项不是链表优于数组的特点?

方便删除
方便插入
长度可变
存储空间小

在以下哪个操作中, 数组比链表更快?

原地逆序
头部插入
返回头节点
返回随机节点

假设要存储一个数据集,数据维持有序,对其的操作只有插入、删除和顺序遍历,综合存储效率和运行速度,下列哪种数据结构是最适合的是?

数组
链表
哈希表
队列

若用数组S[0. .n-1]做为两个栈S1和S2的共同存储结构,对任何一个栈,只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是( )。

S1的栈底位置为0,S2的栈底位置为n-1
S1的栈底位置为0,S2的栈底位置为n/2
S1的栈底位置为1,S2的栈底位置为n/2

int (*p)[3] p的含义是什么?

一个指向int元素大小为3的指针数组
一个指向元素个数为3的int数组的指针
不合法
以上说法都不正确

下列数组定义及赋值,错误的是

int intArray[ ];
int intArray=new int[3]; intArray[1]=1; intArray[2]=2;
int a[ ]={1, 2, 3, 4, 5};
int a[ ] [ ]=new int[2] [ ]; a[0]=new int[3]; a[1]=new int[3];

最坏情况下,合并两个大小为n的已排序数组所需要的比较次数_____。

2n
2n-1
2n+1
2n-2

一个5*4的矩阵,有多少个长方形?(正方形也算是长方形)

120
150
100
80

short a[100],sizeof(a) 返回什么?

2
4
100
200
400

下列关于数组与指针的区别描述正确的是?

数组要么在静态存储区被创建(如全局数组),要么在栈上被创建。
用运算符sizeof 可以计算出数组的容量(字节数)
指针可以随时指向任意类型的内存块。
用运算符sizeof 可以计算出指针所指向内容的容量(字节数)

数组指针和指针数组有什么区别 ?

数组指针只是一个指针变量,它占有内存中一个指针的存储空间
指针数组只是一个指针变量,它占有内存中一个指针的存储空间
指针数组是多个指针变量,以数组形式存在内存当中,占有多个指针的存储空间
数组指针是多个指针变量,以数组形式存在内存当中,占有多个指针的存储空间

下列给定程序中,函数fun的功能是:把形参a所指数组中的奇数按原顺序依次存放到a[0]、a[1]、a[2]…中,把偶数从数组中删除,奇数个数通过函数值返回。 例如,若a所指数组中的数据最初排列为:9,1,4,2,3,6,5,8,7,删除偶数后,a所指数组中的数据为:9,1,3,5,7,返回值为5。
请在程序的下画线处填入正确的内容并将下画线删除,使程序得出正确的结果。

试题程序:

#include<stdio.h>
#define N9
int fun (int a[], int n)
{ 
    int i, j;
    j=0;
    for (i=0; i<n; i++)
    /**********found**********/
    if (a[i]%2== _________ )
    {
        /**********found**********/
        a[j]=a[i];   
        _________;
    }
    /**********found**********/
    return _________;
}
main( )
{ 
    int b[N]={9,1,4,2,3,6,5,8,7}, i, n;
    printf("\nThe original data:\n");
    for(i=0; i<N; i++)
        printf("% 4d", b[i]);
    printf("\n");
    n=fun(b, N);
    printf("\nThe number of odd:% d\n", n);
    printf("\nThe odd number: \n");
    for(i=0; i<n; i++)
        printf("%4d",b[i]);
    printf("\n");
}
0 j++ j
1 j++ j+1
0 j++ j+1
1 j++ j
int fun (int a[], int n)
{
    int i, j;
    j=0;
    for (i=0; i<n; i++)
    /**********found**********/
    if (a[i]%2== 1 ) // 这里是要判断为奇数时,将其值存储到新的位置
    {
        /**********found**********/
        a[j]=a[i];
        j++; // j为新索引,每次赋值后需要加1
    }
    /**********found**********/
    return j; // 因为在上一步中已经加过1了,所以这里直接返回j即可
}
结果如下:

The original data:
   9   1   4   2   3   6   5   8   7

The number of odd: 5

The odd number:
   9   1   3   5   7

下列给定程序中,函数fun的功能是:把形参a所指数组中的最小值放在元素a[0]中,接着把a所指数组中的最大值放在a[1]元素中;再把a所指数组元素中的次小值放在a[2]中,把a索取数组元素中的次大值放在a[3],以此类推。
例如:若a所指数组中的数据最初排列为:9,1,4,2,3,6,5,8,7;按规则移动后,数据排列为:1,9,2,8,3,7,4,6,5。形参n中存放a所指数组中数据的个数。
规定fun函数中的max存放的当前所找的最大值,px存放当前所找最大值得下标。 请在程序的下画线处填入正确的内容并将下画线删除,使程序得出正确的结果。
试题程序。

#include<stdio.h>
#define N 9
void fun(int a[ ], int n)
{
    int i, j, max, min, px, pn, t;
    for (i = 0; i < n - 1; i += 2)
    {
 
        max = min = __;
        px = pn = i;
        for (j = i + 1; j < n; j++)
        {
 
            if (max <  __)
            {
                max = a[j];
                px = j;
            }
 
            if (min > __ )
            {
                min = a[j];
                pn = j;
            }
        }
        if (pn != i)
        {
            t = a[i];
            a[i] = min;
            a[pn] = t;
            if (px == i)
                px = pn;
        }
        if (px != i + 1)
        {
            t = a[i + 1];
            a[i + 1] = max;
            a[px] = t;
        }
    }
}
int main( )
{
    int b[N] = {9, 1, 4, 2, 3, 6, 5, 8, 7};
    printf("\nThe original data:\n");
    for (int i = 0; i < N; i++)
        printf("% 4d", b[i]);
    printf("\n");
    fun(b, N);
    printf("\nThe data after mocinng \n");
    for (int i = 0; i < N; i++)
        printf("% 4d", b[i]);
    printf("\n");
}
0 a[i] a[i]
a[i] a[j] a[j]
0 a[j] a[j]
a[i] a[i] a[i]

下列给定程序中,函数fun的功能是:进行数字字符转换。若形参ch中是数字字符’0’~’9′,则将’0’转换成’9′,’1’转换成’8′, ‘2’转换成’7′,…, ‘9’转换成’0′;如果是其他字符则保持不变,并将转换后的结果作为函数值返回。
请在程序的下画线处填入正确的内容并将下画线删除,使程序得出正确的结果。

试题程序。

#include<stdio.h>
_____ fun(char ch)
{
    if(ch>='0'&& _______)
        return'9'-(ch- ______);
    return ch;
}
main( )
{ 
    char c1,c2;
    printf("\nThe result:\n");
    c1='2';
    c2=fun(c1);
    printf("c1=%c c2=%c\n",c1,c2);
    c1='8';
    c2=fun(c1);
    printf("c1=%c c2=%c\n",c1,c2);
    c1='a';
    c2=fun(c1);
    printf("c1=%c c2=%c\n",c1,c2);
}

int ch<='9' '0'
char ch<='9' '0'
char ch<='9' 0 int ch<='9' 0 [/v_act]
int fun(char ch)
{
    if(ch>='0'&& ch<='9')
        return'9'-(ch-'0');
    return ch;
}

一个有序数列,序列中的每一个值都能够被2或者3或者5所整除,这个序列的初始值从1开始,但是1并不在这个数列中。求第1500个值是多少?

[v_act]2040
2042
2045
2050

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

下列给定程序中,函数fun的功能是:求ss所指字符串数组中长度最短的字符串所在的行下标,作为函数值返回,并把其串长放在形参n所指的变量中。ss所指字符串数数组中共有M个字符串,且串长小于N。
请在程序的下画线处填入正确的内容并将下画线删除,使程序得出正确的结果。

试题程序。

#define M 5
 #define N 20
 int fun(char(* ss)[N], int *n)
 {
     int i, k = 0, len = N;
     for (i = 0; i < ______; i++)
     {
         len = strlen(ss[i]);
         if (i == 0)
             *n = len;
         if (len ____ * n)
         {
             *n = len;
             k = i;
         }
     }
     return ( _____ );
 }
 main( )
 {
     char ss[M][N] = {"shanghai", "guangzhou", "beijing", "tianjing", "chongqing"};
     int n, k, i;
     printf("\nThe originalb stringsare:\n");
     for (i = 0; i < M; i++)
         puts(ss[i]);
     k = fun(ss, &n);
     printf("\nThe length of shortest string is: % d\n", n);
     printf("\nThe shortest string is: % s\n", ss[k]);
 }
N,< ,k N, >,k
M,<,k
M,>,k
int fun(char(* ss)[N], int *n)
 {
     int i, k = 0, len = N;
     for (i = 0; i < ___M___; i++) // 这里是要遍历数组,数组的长度为M,
     {
         len = strlen(ss[i]);
         if (i == 0)
             *n = len;
         if (len _<___ * n); // 这里是取最小的长度,
         {
             *n = len;
             k = i;
         }
     }
     return ( _____ ); // 函数返回最小长度字符串的下标,这里为k
 }

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

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

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

客服QQ


QQ:2248886839


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