数据结构试题库答案1

数据结构试题及答案

一、单项选择题

(1) 一个算法应该是（ ）。

A) 程序 B) 问题求解步骤的描述

C) 要满足五个基本属性 D) A 和 C

(2) 算法指的是（ ）。

A) 计算机程序 B) 解决问题的计算方法

C) 排序算法 D) 解决问题的有限运算序列。

(3) 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。

　　B）数据的逻辑结构属于线性结构，存储结构属于非线性结构

　　C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

(6) 数据的基本单位是（　　　）

A) 数据项 B) 数据类型 C) 数据元素 D) 数据变量

(7) 下列程序的时间复杂度为（　　　）

i=0；s=0；

while（s<n）

{ i++；s=s+i；}

A) O（

） B) O（

A[i][j] = i*j ;

A）O(m2) B）O(n2) C）O(m*n) D）(m+n) 　

(9) 程序段如下：

sum=0；

) D) O(n

2

) 　

(10) 在下面的程序段中，对 x 的赋值语句的频度为（ ）。

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

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

A) O(2n) B)O(n) C) O(n

) D) O(log

2

n

)

(11) 程序段 for ( i:=n-1; i<=1; i--）

2

int fact(int n)

{ /* 大于等于 0 */

if ( n<=0 ) return 1 ;

else return n*fact (n-1) ;

则计算 fact(n)需要调用该函数的次数为（ ）。

s+=j;

A)

B)

C)

D)

(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= =head B) rear->next->next= =head

C) head->next= =rear D) head->next->next= =rear

(17) 从一个长度为 n 的顺序表中删除第 i 个元素（1≤i≤n）时，需向前移动的元素的个数是

（　　）。

(20) 设有一个 10 阶的对称矩阵 A，采用压缩存储方式以行序为主序存储，a00 为第一个元素，

其存储地址为 0，每个元素占有 1 个存储地址空间，则 a45 的地址为（　　）。

(21) 线性表采用链式存储时，节点的存储的地址（ ）。

C) 必须是连续的 D) 和头节点的存储地址相连续

C) 不必事先估计存储空间 D) 所需空间与线性长度成正比

(24) 在长度为 n 的顺序表中删除第 i 个元素(1≤i≤n)时，元素移动的次数为( )。

A) n-i+1 　　　 B) i　　 C) i+1 　　　　 D) n-i

(25) 采用顺序搜索方法查找长度为 n 的顺序表示，搜索成功的平均搜索长度为（ ）。

A) n　　　 B) n/2　　 C) (n-1)/2 　　　　 D) (n+1)/2

(26) 将长度为 n 的单链表链接在长度为 m 的单链表之后的算法的时间复杂度为（ ）。

A) O(1) B) O(n) C) O(m) D) O(m+n)

(27) 若不带头结点的单链表的头指针为 head，则该链表为空的判定条件是( )。

A) head==NULL 　　 B) head->next==NULL C) head!=NULL　　 D) head->next==head

(28) 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用

（ ）存储方式最节省运算时间。

A) 单链表 B) 仅有头指针的单循环链表

C) 双链表 D) 仅有尾指针的单循环链表

(29) 若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用

的辅助结构是（　　　）。

A) 栈 B) 线性表 C) 队列 D) 二叉排序树

(30) 顺序栈 S 中 top 为栈顶指针，指向栈顶元素所在的位置，elem 为存放栈的数组，则元素 e 进

A) s.elem［top］=e； s.top=s.top+1； B) s.elem［top+1］=e；s.top=s.top+1；

C) s.top=s.top+1； s.elem［top+1］=e； D) s.top=s.top+1；s.elem［top］=e；

(32) 链式栈与顺序栈相比，一个比较明显的优点是（ ）。

A) 插入操作更加方便 B) 通常不会出现栈满的情况

C) 不会出现栈空的情况 D) 删除操作更加方便

常递归过程比非递归过程（ ）。

A) edcba B) decba C) dceab D) abcde

(36) 若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列

是( )。

A) 2，4，3，1，5，6　　 B) 3，2，4，1，6，5

C) 4，3，2，1，5，6 　　 D) 2，3，5，1，6，4

(37) 对于栈操作数据的原则是（ ）。

A) 先进先出 B) 后进先出 C) 后进后出 D) 不分顺序

(38) 栈和队列的共同点是（ ）。

A) 都是先进先出 B) 都是先进后出

C) 只允许在端点处插入和删除元素 D) 没有共同点

(39) 一个队列的入队序列是 1，2，3，4，则队列的输出序列是（ ）。

A) 4,3,2,1 B) 1,2,3,4 C)1,4,3,2 D) 3,2,4,1

(40) 设数组 data[m]作为循环队列 SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行

出对操作后其头指针 front 值为（ ）。

(41) 引起循环队列队头位置发生变化的操作是( )。

A) 429　　　　　 B) 432　　 C) 435 　　　　　 D) 438

(43) 设有一个 10 阶的对称矩阵 A[10][10]，采用压缩方式按行将矩阵中下三角部分的元素存入一

维数组 B[]中，A[0][0]存入 B[0]中，则 A[8][5]在 B[]中（ ）位置。

A) 32 B) 33　　 C) 41 D) 65

(44) 若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次

存放于一维数组 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

(45) 对稀疏矩阵进行压缩存储目的是（ ）。

A) 便于进行矩阵运算 B) 便于输入和输出

C) 节省存储空间 D) 降低运算的时间复杂度

(49) 在一棵具有 n 个结点的二叉链表中，所有结点的空域个数等于（ ）。

A) n B) n-1 C) n+1 D) 2*n

(50) 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。