面试中常见的数据结构与算法题

数组（共30题，含答案）

1.矩阵中的行列数可以是不相等的，这样的说法正确吗？

A.正确

B.不正确

2.对矩阵压缩存储是为了

A.方便运算

B.方便存储

C.提高运算速度

D.减少存储空间

3.一维数组与线性表的区别是

A.前者长度固定,后者长度可变

B.后者长度固定,前者长度可变

C.两者长度均固定

D.两者长度均可变

4.在以下的叙述中，正确的是

A.线性表的顺序存储结构优于链表存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

5.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。

A.T

B.F

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

A.对

B.错

7.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？

脚注(10)表示用10进制表示

A.688

B.678

C.692

D.696

8.定义了一维 int 型数组 a[10] 后，下面错误的引用是

A.a[0] = 1;

B.a[0] = 5*2;

C.a[10] = 2;

D.a[1] = a[2] * a[0];

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

A.n-i，n-i+1

B.n-i+1，n-i

C.n-i，n-i

D.n-i+1，n-i+1

10.已知 10*12 的二维数组 A ，以行序为主序进行存储，每个元素占 1 个存储单元，已知 A[1][1] 的存储地址为 420 ，则 A[5][5] 的存储地址为

A.470

B.471

C.472

D.473

11.取线性表的第i个元素的时间同i的大小有关。

A.T

B.F

12.若要定义一个具有 5 元素的整型数组，以下错误的定义语句是

A.int a[5] = {0};

B.int a[] = {0, 0, 0, 0, 0};

C.int a[2+3];

D.int i = 5, a[i];

13.长度为n 的非空顺序表，若在第i个位置插入新的元素X，则i的取值范围是 1≤i≤n+1，需要移动的元素个数为

A.i

B.n-i-1

C.n-i

D.n-i+1

14.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为

A.13

B.33

C.18

D.40

15.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为

A.O(n)

B.O(nlog2n)

C.O(1)

D.O(n2)

16.定义语句"double * array [8]"的含义正确的是

A.array是一个指针，它指向一个数组，数组的元素时是双精度实型

B.array是一个数组，数组的每一个元素是指向双精度实型数据的指针C

C语言中不允许这样的定义语句

D.以上都不对

17.有一个用数组C[1..m]表示的环形队列，m为数组的长度。假设f为队头元素在数组中的位置，r为队尾元素的后一位置（按顺时针方向）。若队列非空，则计算队列中元素个数的公式应为？

A.（m+r-f）mod m

B.r-f

C.(m-r+f) mod m

D.(m-r-f) mod m

E.(r-f) mod m

F.需要判断边界

18.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}

};

A.9

B.2

C.6

D.Overflow

19.线性表是________。

A.一个有限序列，可以为空

B.一个有限序列，不可以为空

C.一个无限序列，可以为空

D.一个无限序列，不可以为空

20.将一个A[1..100,1..100]的三对角矩阵,按行优先存入一维数组B[1..298]中,A中元素A6665 (即该元素下标i=66,j=65),在B数组中的位置K为( )供选择的答案:

A.198

B.195

C.197

21.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n（n+1）/2]中，对上述任一元素aij (1≤i，j≤n，且i≤j)在B中的位置为

A.i（i-1）/2+j

B.j（j-1）/2+i

C.j（j-1）/2+i-1

D.i（i-1）/2+j-1

22.下列给定程序中，函数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]);

}

A.N，< ，k

B.N， >，k

C.M，<，k

D.M，>，k

23.数组 A[0…5 ， 0…6] 的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A[5 ， 5] 的地址为

A.1175

B.1180

C.1205

D.1210

24.下列程序的功能是求两个 2 行 3 列的数组的和，即数组对应位置的元素—相加，请为横线处选择合适的程序

A.void M::

B.friend M

C.M

D.M M::

25.若对n阶对称矩阵A(下标从1,1开始）以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1…(n(n+1))/2]中,则在B中确定aij (i<j)的位置k的关系为

A.i*(i-1)/2+j

B.j*(j-1)/2+i

C.i*(i+1)/2+j

D.j*(j+1)/2+i

26.优先级队列和有序数组的一个区别是

A.最低优先级别的数据项不能从数组中轻易的提取出来，而在优先级队列中可以。

B.数组必须是有序的，而优先级队列不需要。

C.最高优先级的数据项可以很容易地从优先级队列中提取出来，而有序数组不行。

D.其他三个选项都是。

27.【多选】数组ARR=[1,2,3,4,5],以下返回值为5的是

A.arr.push()

B.arr.pop()

C.arr.shift()

D.arr.unshift()

28.【多选】以下能对一维数组 a 进行正确初始化的语句是

A.int a[10]=(0, 0, 0, 0, 0);

B.int a[10]={ };

C.int a[]={0};

D.int a[10]={10*a};

29.【多选】选项代码中能正确操作数组元素的是

int main(){

int a[N][N]={{0,0},{0,0}};

for(int i=0;i<N;i++){

for(int j=0;j<N;j++){

//访问二维数组a的值

//选项代码

}

}

}

A.*(*(a+i)+j)=1

B.*(a[i]+j)=1

C.**(a+i)[j]=1

D.*((a+i)+j)=1

30.【多选】在一个有8个int数据的数组中，随机给出数组的数据，找出最大和第二大元素一定需要进行几次比较

A.8

B.9

C.10

D.11

数组 - 答案：

1. A

2. D

3. A

4. B

5. B

6. B

7. C

8. C

9. A

10. C

11. B

12. D

13. D

14. B

15. C

16. B

17. A

18. D

19. A

20. B

21. B

22. C

23. A

24. D

25. B

26. A

27. B

28. BC

29. AB

30. B

字符串（共30题，含答案）

1.为查找某一特定单词在文本中出现的位置，可应用的串运算是( D )

A.插入

B.删除

C.串联接

D.子串定位

2.字符串的长度是指：

A.串中不同字符的个数

B.串中不同字母的个数

C.串中所含字符的个数

D.串中不同数字的个数

3.子串“ ABC ”在主串“ AABCABCD ”中的位置为 2 （下标从0开始）。

A.正确

B.错误

4.下面关于串的叙述中，哪一个是不正确的？

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

5.串的长度是指：

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

6.以下数据结构中,哪一个是线性结构？

A.广义表

B.二叉树

C.稀疏矩阵

D.串

7.若有以下程序

main( )

{

char c1,c2;

c1 ='C'+'8'－'3';

c2 ='9'－'0';

printf("%c %d\n",c1,c2);

}

则程序的输出结果是：

A.H'9'

B.H 9

C.F'9'

D.表达式不合法输出无定值

8.设串 s1=’ABCDEFG’ ， s2=’PQRST’ ，函数 con(x,y) 返回 x 和 y 串的连接串， subs(s, i, j) 返回串 s 的从序号 i 开始的 j 个字符组成的子串， len(s) 返回串 s 的长度，则 con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2)) 的结果串是？（本题序号从1开始。）

A.BCDEF

B.BCDEFG

C.BCPQRST

D.BCDEFEF

9.设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为：

A.2n-1

B.n²

C.(n²/2)+(n/2)

D.(n²/2)+(n/2)-1

E.(n²/2)-(n/2)-1

F.其他情况

10.设有两个串S1和S2,求S2在S1中首次出现的位置的运算称作

A.求子串

B.判断是否相等

C.模型匹配

D.连接

11.串中任意个字符组成的子序列称为该串的子串。

A.正确

B.错误

12.判断下列说法是否正确：设有两个串S1和S2,求S2在SI中首次出现位置的运算称为求子串。

A.正确

B.错误

13.由4个“1”和4个“0”组成的8位二进制补码，能表示的最小整数是：

A.-125

B.-32

C.-121

D.-3

14.字符串”qiniu”根据顺序不同有多少种排列组合的方式？

A.96

B.72

C.60

D.24

15.不能所字符串“Good!”存放到数组 s 中的代码是:

A.char s[8] = {'G','o','o','d','!', 'A.char s[8] = {'G','o','o','d','!', '\0'};'};

B.char s[8];strcpy(s, "Good!");
C.char s[8];s = "Good!";

D.char s[8] = "Good!";

16.请问在64位平台机器下sizeof(string_a),sizeof(string_b)大小分别是:

1.char *string_a=(char *)malloc(100*sizeof(char));

2.char string_b[100];

A.8 100

B.100 8

C.100 100

D.8 8

17.哈弗曼编码是一种无损二进制熵编码算法，其加权路径长度最小，字符串“alibaba”的二进制哈弗曼编码有___位（bit）

A.11

B.12

C.13

D.14

18.以下不属于字符串的方法的是？

A.split
B.slice

C.reverse

D.Contact

19.串是一种特殊的线性表，其特殊性体现在：

A.可以顺序存储

B.数组元素是一个字符

C.可以连续存储

D.数据元素可以是多个字符

20.对字符串“mabnmnm”的二进制进行哈夫曼编码有多少位？

A.12

B.13

C.14

D.15

21.设语句定义char a[ 80 ]= " 012389 "; ，则sizeof(a)和strlen(a)的值分别为

A.80和9

B.80和7

C.80和5

D.80和6

22.在给定文件中查找与设定条件相符字符串的命令为？

A.find

B.gzip

C.grep

D.Sort

23.字符串′ababaabab′的nextval为：

A.(0,1,0,1,0,4,1,0,1)

B.(0,1,0,1,0,2,1,0,1)

C.(0,1,0,1,0,0,0,1,1)

D.(0,1,0,1,0,1,0,1,1)

24.下面程序段的输出结果是：

char *p1 = ”123”, *p2 = ”ABC”, str[50] = “xyz”;

strcpy(str + 2, strcat(p1, p2));

printf(“%s\n”, str);

A.xyz123ABC

B.z123ABC

C.xy123ABC

D.出错

25.用 0 - 9 这 10 个数字组成一个首尾相连的字符串，每个数字可以重复出现多次，并且字符串中任意 2 个数字都相邻出现过。此字符串最小长度是：

A.47

B.48

C.49

D.50

26.以下程序段的输出结果是：

char s[]="\1234563456\t";printf("%d\n",strlen(s));

A.12

B.13

C.16

D.以上都不对

27.下面关于字符串的描述正确的是：【多选

A.通过String s1=new String("abc")和String s2="abc"，则s1==s2为true。

B."abc"+"def"则会创建三个字符串对象，第三个是"abcdef"。也就是说，在Java中对字符串的一切操作，都会产生一个新的字符串对象。

C.StringBuffer是线程安全的，它比String快。

D.StringBuilder是线程安全的，它比String快

28.【多选】有如下语句序列：char str[10]；cin>>str；当从键盘输入”I love this game”时，str中的字符串是：

A."I love this game"

B."I love thi"

C."I love"

D."I"

29.【多选】String str = new String(“abc”)，“abc”在内存中是怎么分配的？

A.堆

B.栈

C.字符串常量区

D.寄存器

30.【多选】在下列表述中是错误的

A.含有一个或多个空格字符的串称为空串

B.对n(n>0)个顶点的网,求出权最小的n-1条边便可构成其最小生成树

C.选择排序算法是不稳定的

D.平衡二叉树的左右子树的结点数之差的绝对值不超过1

字符串 - 答案：

1. D

2. C

3. B

4. B

5. B

6. D

7. B

8. D

9. D

10. C

11. B

12. B

13. C

14. C

15. C

16. A

17. C

18. C

19. B

20. B

21. A

22. C

23. A

24. D

25. D

26. A

27. BC

28. AC

30. ABD