数据结构试题库答案讲解.pdf

数据结构试题及答案
一、单项选择题
(1)一个算法应该是（）。
A)程序B)问题求解步骤的描述
C)要满足五个基本属性D)A和C
(2)算法指的是（）。
A)计算机程序B)解决问题的计算方法
C)排序算法D)解决问题的有限运算序列。
(3)与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A)存储结构B)逻辑结构C)算法D)操作
(4)从逻辑上可以把数据结构分为（）两大类。
A)动态结构、静态结构B)顺序结构、链式结构
C)线性结构、非线性结构D)初等结构、构造型结构
(5)下列叙述中正确的是()。
A）一个逻辑数据结构只能有一种存储结构
B）数据的逻辑结构属于线性结构，存储结构属于非线性结构
C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率
D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
(6)数据的基本单位是（）
A)数据项B)数据类型C)数据元素D)数据变量
(7)下列程序的时间复杂度为（）
i=0；s=0；
while（s<n）
{i++；s=s+i；}

A)O（n）B)O（2n）C)O（n）D)O（n2）

(8)下列程序段的渐进时间复杂度为（）。
for(inti=1;i<=n;i++)
for(intj=1;j<=m;j++)
A[i][j]=i*j;
A）O(m2)B）O(n2)C）O(m*n)D）(m+n)
(9)程序段如下：
sum=0；
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sum++；
其中n为正整数，则最后一行的语句频度在最坏情况下是（）。

A）O(n）B)O(nlogn)C)O(n3)D)O(n2)
(10)在下面的程序段中，对x的赋值语句的频度为（）。
for(i=1;i>=n;i++)

for(j=1;j>=n;j++)

x:=x+1;

A)O(2n)B)O(n)C)O(n2)D)O(logn)
2
(11)程序段for(i:=n-1;i<=1;i--）
for(j:=1;j>=i;j++)
if(a[j]>a[j+1])
{t=a[j];a[j]=a[j+1];a[j+1]=t;}
其中n为正整数，则最后一行的语句频度在最坏情况下是（）。

A)O(n）B)O(nlogn)C)O(n3)D)O(n2)
(12)设有一个递归算法如下：
intfact(intn)
{/*大于等于0*/
if(n<=0)return1;
elsereturnn*fact(n-1);
}
则计算fact(n)需要调用该函数的次数为（）。
A)nB)n+1C)n+2D)n-1
(13)下述程序段中语句①的频度是（）。

s=0;
for(i=1;i<m;i++)
for(j=0;j<=i;j++)
s+=j;
(m1)(m1)m(m1)(m2)(m1)m(m1)
A)B)C)D)
2222
(14)若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节
省运算时间的存储方式是（）。
A)单链表B)仅有头指针的单循环链表
C)双链表D)仅有尾指针的单循环链表
(1)求循环链表中当前结点的后继和前驱的时间复杂度分别是（）。
A)O(n)和O(1)B)O(1)和O(1)C)O(1)和O(n)D)O(n)和O(n)
(15)求单链表中当前结点的后继和前驱的时间复杂度分别是（）。
A)O（n）和O（1）B)O（1）和O（1）
C)O（1）和O（n）D)O(n)和O（n）
(16)非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（）。
A)rear->next==headB)rear->next->next==head
C)head->next==rearD)head->next->next==rear
(17)从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是
（）。

A)n-iB)n-i+1C)n-i-1D)i
(18)已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为
90的元素时，检索成功需比较的次数是（）。

A)1B)2C)3D)4
(19)假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元
素占4个存储单元，则存储地址为2836的元素是（）。
A)R[3][3][3]B)R[3][3][4]C)R[4][3][5]D)R[4][3][4]
(20)设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，
其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（）。

A)1