下载文档原格式
数据结构与算法分析考试试题一、选择题（共 20 小题，每小题 3 分，共 60 分）1、在一个具有 n 个元素的顺序表中，查找一个元素的平均时间复杂度为（）A O(n)B O(logn)C O(nlogn)D O(n²)2、以下数据结构中，哪一个不是线性结构（）A 栈B 队列C 二叉树D 线性表3、一个栈的入栈序列是 1，2，3，4，5，则栈的不可能的出栈序列是（）A 5，4，3，2，1B 4，5，3，2，1C 4，3，5，1，2D 1，2，3，4，54、若一棵二叉树的先序遍历序列为 ABCDEFG，中序遍历序列为CBDAEGF，则其后序遍历序列为（）A CDBGFEAB CDBFGEAC CDBAGFED BCDAGFE5、具有 n 个顶点的无向完全图的边数为（）A n(n 1)B n(n 1) ／ 2C n(n ＋ 1) ／ 2D n²6、以下排序算法中，在最坏情况下时间复杂度不是O(n²)的是（）A 冒泡排序B 选择排序C 插入排序D 快速排序7、在一个长度为 n 的顺序表中，删除第 i 个元素（1≤i≤n）时，需要向前移动（）个元素。
A n iB iC n i ＋ 1D n i 18、对于一个具有 n 个顶点和 e 条边的有向图，其邻接表表示中，所有顶点的边表中边的总数为（）A eB 2eC e/2D n(e 1)9、以下关于哈夫曼树的描述，错误的是（）A 哈夫曼树是带权路径长度最短的二叉树B 哈夫曼树中没有度为 1 的节点C 哈夫曼树中两个权值最小的节点一定是兄弟节点D 哈夫曼树中每个节点的权值等于其左右子树权值之和10、用邻接矩阵存储一个具有 n 个顶点的无向图时，矩阵的大小为（）A nB n²C （n 1)²D （n ＋ 1)²11、下列关于堆的描述，正确的是（）A 大根堆中，每个节点的值都大于其左右子节点的值B 小根堆中，每个节点的值都小于其左右子节点的值C 堆一定是完全二叉树D 以上都对12、在一个具有 n 个单元的顺序存储的循环队列中，假定 front 和rear 分别为队头指针和队尾指针，则判断队满的条件是（）A （rear ＋ 1) ％ n ＝＝ frontB （front ＋ 1) ％ n ＝＝ rearC rear ＝＝ frontD rear ＝＝ 013、已知一个图的邻接表如下所示，从顶点 1 出发，按深度优先搜索法进行遍历，则得到的一种可能的顶点序列为（）｜顶点|邻接顶点|｜｜｜｜1|2, 3|｜2|4, 5|｜3|5|｜4|6|｜5|6|｜6| ｜A 1, 2, 4, 6, 5, 3B 1, 2, 5, 3, 4, 6C 1, 2, 3, 5, 4, 6D 1, 3, 2, 4, 5, 614、对线性表进行二分查找时，要求线性表必须（）A 以顺序方式存储，且元素按值有序排列B 以顺序方式存储，且元素按值无序排列C 以链式方式存储，且元素按值有序排列D 以链式方式存储，且元素按值无序排列15、以下算法的时间复杂度为 O(nlogn)的是（）A 顺序查找B 折半查找C 冒泡排序D 归并排序16、若某链表最常用的操作是在最后一个节点之后插入一个节点和删除最后一个节点，则采用（）存储方式最节省时间。
（第9题配图：数组的下标为0,1,2,3）
10.对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )
A.35和41
B.23和39
C.15和44
D.25和51
11.有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找
63，要经过( C )次与63比较。
A.12
B.6
C.4
D.5
12.下述几种排序方法中，稳定的排序算法是( B )
A.直接插入排序
B.快速排序
C.堆排序
D.希尔排序
13.具有n个顶点的无向图至少要有( B )条边才能确保是一个连通图。
A.n(n+1)
B.n-1
C.n+1
D.n(n-1)
14.二叉树是非线性数据结构，所以 ( C )
A.它不能用顺序存储结构存储
B.它不能用链式存储结构存储
C.顺序存储结构和链式存储结构都能存储
D.顺序存储结构和链式存储结构都不能使用
15.有8个结点的无向图最多有( B )条边。
A.14
B.28
C.56
D.112
二、填空题（每小题2分，共30分）
1.下面程序段的时间复杂度为___O(n)_____。
sum=1; for(i=0;sum<n;i++) sum+=1;
2. 设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存
放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，则判定Q队列的队。
一、选择题（10*2%=20%）1．代码段for (j=1; j<=n;j++) 的时间复杂性是B。
for (k=n; k>=1; k/=2)count++;A、O(n2)B、O(nlogn)C、O(logn)D、O(n)2．对某个无向图的邻接矩阵来说，下列叙述正确的是 A 。
A、第i行上的非零元素个数和第i列上的非零元素个数一定相等B、矩阵中的非零元素个数等于图中的边数C、第i行与第i列上的非零元素的总数等于顶点vi的度数D、矩阵中非全零行的行数等于图中的顶点数3．循环双链表中在p所指结点之后插入结点s的操作是D。
A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->nextB、p->next=s; p->next->prior=s; s->prior=p; s->next=p->nextC、s->prior=p; s->next=p->next; p->next=s; p->next->prior=sD、s->prior=p; s->next=p->next; p->next->prior=s; p->next=s4．4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态如图，，不可能的出栈顺序是C。
A、a4，a3，a2，a1B、a3，a2，a4，a1C、a3，a1，a4，a2D、a3，a4，a2，a15．下列四种排序方法中，不稳定的方法是D。
A、插入排序B、冒泡排序C、归并排序D、选择排序6．单个结点二叉树的高度为0，所有含有15个结点的二叉树中，最小高度是D。
A、6B、5C、4D、37．在一个具有n个顶点的无向图中，要连通全部顶点至少需要B条边。
A、nB、n-1C、n/2D、n+18．快速排序法的运行效率取决于D。
师⼤《数据结构与算法》期末练习题答案福建师范⼤学数学与计算机学院计算机科学与技术《数据结构与算法》期末练习⼀选择题1．以下与数据的存储结构⽆关的术语是（ D ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈2. 算法的时间复杂度取决于（ A ）A．问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu3. ⼀个栈的输⼊序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。
A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 24. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，⼜有动态链表的优点。
所以，它存取表中第i个元素的时间与i⽆关。
(2) 静态链表中能容纳的元素个数的最⼤数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插⼊、删除上类似，不需做元素的移动。
以上错误的是（ B ）A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）5．对于有n 个结点的⼆叉树, 其⾼度为（ D ）A．nlog2n B．log2n C．?log2n?|+1 D．不确定6．从下列有关树的叙述中,选出正确的叙述（ C ）A．⼆叉树中每个结点有两个⼦结点,⽽树⽆此限制,因此⼆叉树是树的特殊情况。
B．当K≥1时⾼度为K的⼆叉树⾄多有2k-1个结点。
C．哈夫曼树是带权路径最短的树,路径上权值较⼤的结点离根较近。
D．在⼆叉树中插⼊结点,该⼆叉树便不再是⼆叉树。
7．设⽆向图的顶点个数为n，则该图最多有（ B ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n28．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={, , , , , , , , },G的拓扑序列是（ A ）。
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V79．下列排序算法中，其中（ D ）是稳定的。
2022年福州大学软件工程专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、设16个处理器编号分别为0，1，2，...，15用Cube，互联函数时，第10号处理机与第（）号处理机相联。
A.11B.8C.14D.22、"一次重叠"中消除"指令相关"最好的方法是( )。
A.不准修改指令B.设相关专用通路C.推后分析下条指令D.推后执行下条指令3、Cache存贮器常用的地址映象方式是( )。
A.全相联映象B.页表法映象C.组相联映象D.段页表映象4、下列关于标量流水机的说法不正确的是（）A.可对标量数据进行流水处理B.没有向量数据表示C.不能对向量数据进行运算D.可以对向量、数组进行运算5、（）属于MIMD系统结构。
A.各处理单元同时受同一个控制单元的管理B.各处理单元同时接受同一个控制单元送来的指令C.松耦合多处理机和多计算机D.阵列处理机6、静态流水线是指( )A.只有一种功能的流水线B.功能不能改变的流水线C.同时只能完成一种功能的多功能流水线D.可同时执行多种功能的流水线7、对系统程序员不透明的应当是( )。
A.Cache存贮器XB.系列机各档不同的数据通路宽度C.指令缓冲寄存器D.虚拟存贮器8、在系统结构设计中，提高软件功能实现的比例会( )。
A.提高解题速度B.减少需要的存贮容量C.提高系统的灵活性D.提高系统的性能价格比9、在计算机系统设计中，比较好的方法是( )A.从上向下设计B.从下向上设计C.从两头向中间设计D.从中间开始向上、向下设计10、在计算机系统设计中，比较好的方法是（）。
A.从上向下设计B.从下向上设计C.从两头向中间设计D.从中间开始向上、向下设计二、填空题11、Cache系统的加速比是命中率H和________与________比值的函数12、Cache存贮器是增加辅助________件，使之速度接近于Cache的，容量是存的。
数据结构与算法试题及答案数据结构与算法试题及答案在计算机科学领域，数据结构与算法是非常重要的基础知识。
数据结构是一种组织和存储数据的方式，而算法则是解决问题的方法和步骤。
掌握好数据结构与算法，有助于提高程序的运行效率和解决实际问题。
下面是一些关于数据结构与算法的试题及其答案，希望能够帮助大家更好地理解和应用这方面的知识。
试题一：什么是数据结构？请举例说明。
答案一：数据结构是一种组织和存储数据的方式。
它可以使数据的操作更加高效。
常见的数据结构有数组、链表、栈、队列、树和图等。
举个例子，数组是一种线性数据结构，可以存储一组相同类型的元素。
试题二：什么是算法？请举例说明。
答案二：算法是一种解决问题的方法和步骤。
它是一个精确的描述，用于解决特定问题。
常见的算法有排序算法、查找算法、递归算法等。
例如，冒泡排序算法是一种比较简单的排序算法，通过不断交换相邻元素的位置来达到排序的目的。
试题三：什么是时间复杂度和空间复杂度？答案三：时间复杂度和空间复杂度是衡量算法性能的两个指标。
时间复杂度是指算法执行所需要的时间，通常用大O符号表示。
空间复杂度是指算法执行所需要的额外空间，通常也用大O符号表示。
它们都是描述算法随着输入规模增大而变化的趋势。
试题四：介绍一下常见的数据结构和相应的操作。
答案四：常见的数据结构有数组、链表、栈、队列、树和图等。
- 数组是一种线性数据结构，可以随机访问元素，并且在插入和删除元素时需要移动其他元素。
- 链表是一种动态数据结构，不需要固定的内存空间，但只能通过指针进行元素的访问。
- 栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除元素的操作。
- 队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。
- 树是一种非线性数据结构，由节点和指向子节点的边组成。
常见的树有二叉树、二叉搜索树和AVL树等。
- 图是一种复杂的数据结构，由节点和边组成，可以表示各种关系。
《数据结构与算法》试卷A适用专业： 考试日期： 闭卷 所需时间：120分钟 总分：100分一、 选择题(每题1分, 共20题，总共20分)。
1.算法分析的目的是（ ） A ．辨别数据结构的合理性 B ．评价算法的效率C ．研究算法中输入与输出的关系D ．鉴别算法的可读性2.在一个单链表HL 中，若要在当前由指针p 指向的结点后面插入一个由q 指向的结点，则执行如下( )语句序列。
A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（ ）A. 在队列第i 个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。
A ． 11 B.35 C. 19 D. 535.如下图所示的4棵二叉树中，（ ）不是完全二叉树。
6．下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。
B ．线性表采用顺序存储，便于进行插入和删除操作。
C ．线性表采用链接存储，不必占用一片连续的存储单元。
D ．线性表采用链接存储，便于插入和删除操作。
7．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A ．单链表B ．仅有头指针的单循环链表C ．双链表D ．仅有尾指针的单循环链表8. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
A. O(0)B. O(1)C. O(n)D. O(n 2)9. 若已知一个栈的入栈序列是1,2,3,…,n ，其输出序列为p 1,p 2,p 3，…，p N ,若p N 是n ，则p i 是( )。
