当前位置：首页 > news >正文

【数据结构与算法】试卷 4（含答案）

news 来源：原创 2024/11/16 18:06:48

一、选择题

1. 研究数据结构就是研究数据的（）

A. 逻辑结构

B. 存储结构

C. 逻辑结构和存储结构

D. 逻辑结构、存储结构及其基本操作

2. 算法分析的两个主要方面是（）

A. 空间复杂度和时间复杂度

B. 正确性和简单性

C. 可读性和文档性

D. 数据复杂性和程序复杂性

3. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为（）

A. O(logn)

B. O(1)

C. O(n)

D. O(n*n)

4. 若一个线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用（）存储方式最节省时间

A. 顺序表

B. 单链表

C. 双链表

D. 单循环链表

5. 一个栈的输入序列为a,b,c,d,e，则栈的不可能输出序列是（）

A. a,b,c,d,e

B. d,e,c,b,a

C. d,c,e,a,b

D. e,d,c,b,a

6. 判断一个循环队列Q（最多n个元素）为满的条件是（）

A. Q->rear==Q->front

B. Q->rear==Q->front+1

C. Q->front==(Q->rear+1)%n

D. Q->front==(Q=>rear-1)%n

7. 设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳

A. 顺序表

B. 链表

C. 队列

D. 栈

8. 设有两个串S1和S2，求串S2在S1中首次出现的位置的运算叫做（）

A. 连接

B. 求子串

C. 模式匹配

D. 判断子串

9. 设广义表L=(a,b,c)，则L的长度和深度分别是（）

A. 1和1

B. 1和3

C. 1和2

D. 2和3

10. 二叉树的深度为k，则二叉树最多有（）个结点

A. 2k

B. 2^(k-1)

C. 2^k-1

D. 2k-1

11. 用顺序存储方式将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（）

A. R[2i-1]

B. R[2i+1]

C. R[2i]

D. R[2/i]

12.对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）

A. n

B. n*n

C. n-1

D. (n-1)(n-1)

13. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）

A. 完全图

B. 连通图

C. 有回路

D. 一棵树

14. 关键路径是事件结点网路中（）

A. 从源点到汇点的最长路径

B. 从源点到汇点的最短路径

C. 最长的回路

D. 最短的回路

15. 已知一个有序表（11,22,33,44,55,66,77,88,99），则折半查找55需要比较（）次

A. 1

B. 2

C. 3

D. 4

16. 若需要在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

17. 下列排序方法中（）方法是不稳定的

A. 冒泡排序

B. 选择排序

C. 堆排序

D. 直接插入排序

18. 带头结点的单链表head为空的判定条件是（）

A. head==NULL

B. head->next==NULL

C. head->next !=NULL

D. head !=NULL

19. 下面（）可以判断出一个有向图中是否有环

A. 广度优先遍历

B. 拓扑排序

C. 求最短路径

D. 求关键路径

20. 带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）

A. 第i行非无穷的元素之和

B. 第i列非无穷的元素之和

C. 第i行非无穷且非0元素个数

D. 第i行和第i列非无穷且非0元素之和

答案：1~5：D A C A C 6~10：C D C C C 11~15：B B B A A 16~20：C C B B B

二、填空题

1. 程序段"i=1;while(i<=n) i=i*2;"时间复杂度为 O(logn) 。

2. 设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，要将q插入到p结点之后，则需要执行的语句是 q->next=p->next;p->next=q; 。

3. 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是 e2,e4,e3,e6,e5,e1，则栈的容量至少应该是 3 。

4. 具有相同函数值的关键字对哈希函数来说称为同义词。