数据结构与算法期末考试复习试题

《数据结构与算法》一、选择题1. 组成数据的基本单位是( )。

(A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量2. 线性表的链接实现有利于( )运算。

(A) 插入 (B)读表元 (C)查找 (D)定位3. 串的逻辑结构与( )的逻辑结构不同。

(A) 线性表 (B)栈 (C)队列 (D)树4. 二叉树第i（i≥1）层最多有( )个结点。

(A) 2i (B)2i (C) 2i-1 (D) 2i-15. 设单链表中指针p指向结点A，若要删除A后结点（若存在），则需要修改指针的操作为( )(A) p->next = p->next->next (B)p=p->next(C)p=p->next->next (D)p->next=p6、栈和队列的共同特点是( )。

(A)只允许在端点处插入和删除元素 (B)都是先进后出(C)都是先进先出 (D)没有共同点7、二叉树的第k层的结点数最多为( ).(A)2k+1 (B)2K+1 (C)2K-1(D) 2k-18、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA9、设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-110、下面程序的时间复杂为（）for（i=1,s=0; i<=n; i++）{t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(n3)11、设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

(A) n(n-1) (B) n+1 (C) n (D) n(n+1)12、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

【期末复习】数据结构期末综合练习及参考答案四（算法分析题）数据结构（本科）期末综合练习四（算法分析题）1. 指出算法的功能并求出其时间复杂度。

int fun(int n){int i =1,s=1;while(s< bdsfid="67" p=""><>return i;}功能为：时间复杂度为：2. 指出算法的功能并求出其时间复杂度。

void matrimult(int a[M][N], int b[N][L], int c[M][L]){ //M、N、L均为全局整型常量int i, j, k;for ( i = 0; i < M; i++ )for ( j = 0; j < L; j++ )c[i][j] = 0;for( i =0; i <m;i++)< bdsfid="79" p=""></m;i++)<>for(j=0;j<l;j++)< bdsfid="81" p=""></l;j++)<>for(k=0;k<n;k++)< bdsfid="83" p=""></n;k++)<>c[i][j]+=a[i][k]*b[k][j];}功能为：时间复杂性为：3. 针对如下算法，回答问题：若数组A[n] = {12, 24, 0, 38, 0, 0, 0, 0, 29, 0, 45, 0}, n = 12，给出算法执行后数组A[n]的状态。

templatevoid unknown ( T A[ ], int n ) {int free = 0;for ( int i = 0; i < n; i++ )if ( A[i] != 0 ) {if ( i != free ) {A[free] = A[i];A[i] = 0;}free++;}}算法执行的结果4. 设顺序表SeqList具有下列操作：int Length( ) const; //计算表长度并返回，若表为空则返回0T Remove( ); //删除当前表项并返回其值，置下一表项为当前表项T First( ); //取表中第一个表项的值并返回，并置为当前表项T Next( ); //取当前表项后继表项的值并返回，//并把此后继表项置为当前表项若顺序表中存放的数据为{29,38,47,16,95,64,73,83,51,10,0,26}，表的长度为12，参数值s=10, t=30，说明算法执行后顺序表的状态和长度的变化。

数据结构与算法试题库含答案一、单选题（共100题，每题1分，共100分）1.在 Word 2010 中，关于文档自动保存的正确说法是：A、如果不进行特别设置，Word 2010 不会自动保存文档第 32 组B、默认的自动保存时间间隔为 10 分钟C、自动保存时间间隔越短越好D、自动保存时间间隔越长越好正确答案：B2.设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 5。

该树中度为 3 的结点数为A、3B、不可能有这样的树C、2D、1正确答案：C3.下面属于应用软件的是A、人事管理系统B、Oracle 数据库管理系统C、C++编译系统D、ios 操作系统第 24 组正确答案：A4.树的度为 3，且有 9 个度为 3 的结点，5 个度为 1 的结点，但没有度为 2 的结点。

则该树中的叶子结点数为A、19B、32C、33D、18正确答案：A5.下列叙述错误的是：A、Microsoft Windows 7 属于应用软件B、把高级语言源程序转换为机器语言目标程序的过程，称为编译C、计算机内部对数据的传输、存储和处理都使用二进制D、把数据从内存传输到硬盘的操作称为写盘正确答案：A6.在 Word 文档中，学生“张小民”的名字被多次错误地输入为“张晓明”、“张晓敏”、“张晓民”、“张晓名”，纠正该错误的最优操作方法是：A、从前往后逐个查找错误的名字，并更正。

B、利用Word“查找”功能搜索文本“张晓”，并逐一更正。

C、利用Word“查找和替换”功能搜索文本“张晓*”，并将其全部替换为“张小民”。

D、利用Word“查找和替换”功能搜索文本“张晓?”，并将其全部替换为“张小民”。

第 10 组正确答案：D7.对软件系统总体结构图描述正确的是A、深度等于控制的层数B、扇入是一个模块直接调用的其他模块数C、结构图是描述软件系统功能的D、从属模块一定是原子模块正确答案：A8.计算机中组织和存储信息的基本单位是：A、位B、字长C、字节D、编码正确答案：C9.软件按功能可以分为应用软件、系统软件和支撑软件(或工具软件)。

数据结构与算法题库（含参考答案）一、单选题（共100题，每题1分，共100分）1、在一次校园活动中拍摄了很多数码照片，现需将这些照片整理到一个PowerPoint 演示文稿中，快速制作的最优操作方法是：A、创建一个 PowerPoint 相册文件。

B、创建一个 PowerPoint 演示文稿，然后批量插入图片。

C、创建一个 PowerPoint 演示文稿，然后在每页幻灯片中插入图片。

D、在文件夹中选中所有照片，然后单击鼠标右键直接发送到PowerPoint 演示文稿中。

正确答案：A2、下面对“对象”概念描述错误的是A、对象不具有封装性B、对象是属性和方法的封装体C、对象间的通信是靠消息传递D、一个对象是其对应类的实例正确答案：A3、设栈与队列初始状态为空。

首先A,B,C,D,E依次入栈，再F,G,H,I,J 依次入队；然后依次出队至队空，再依次出栈至栈空。

则输出序列为A、F,G,H,I,J,E,D,C,B,AB、E,D,C,B,A,J,I,H,G,FC、F,G,H,I,J,A,B,C,D,E,D、E,D,C,B,A,F,G,H,I,J正确答案：A4、设表的长度为 20。

则在最坏情况下，冒泡排序的比较次数为A、20B、19C、90D、190正确答案：D5、设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。

则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ正确答案：A6、Excel工作表B列保存了11位手机号码信息，为了保护个人隐私，需将手机号码的后 4 位均用“*”表示，以 B2 单元格为例，最优的操作方法是：A、=REPLACE(B2,7,4,"****")B、=REPLACE(B2,8,4,"****")C、=MID(B2,7,4,"****")D、=MID(B2,8,4,"****")第 10 组正确答案：B7、小金从网站上查到了最近一次全国人口普查的数据表格，他准备将这份表格中的数据引用到 Excel 中以便进一步分析，最优的操作方法是：A、通过 Excel 中的“自网站获取外部数据”功能，直接将网页上的表格导入到 Excel 工作表中。

数据结构期末考试试题(含答案)数据结构期末考试试题(含答案)第一题：多项式相加（20分）将两个多项式 P(x) 和 Q(x) 相加，结果存储在另一个多项式 S(x) 中，请写出相应的算法，并给出其时间复杂度分析。

答案：算法如下：1. 初始化一个空多项式 S(x)。

2. 分别取多项式 P(x) 和 Q(x) 的第一项，判断指数的大小关系，并将指数较小的项加入 S(x)。

3. 若指数相同，则将两项系数相加，并将结果加入 S(x)。

4. 重复步骤2和步骤3，直到两个多项式中的所有项都被处理完。

5. 返回结果多项式 S(x)。

时间复杂度分析：- 假设 P(x) 和 Q(x) 的项数分别为 m 和 n。

- 在最坏情况下，需要比较 m+n 次指数大小，并进行 m+n-1 次系数相加。

- 因此，该算法的时间复杂度为 O(m+n)。

第二题：循环队列设计（30分）请设计一个循环队列，实现入队、出队等基本操作，并给出时间复杂度分析。

答案：定义循环队列的结构体如下：```ctypedef struct {int *data; // 存储队列元素的数组int front; // 队首指针，指向队首元素的位置int rear; // 队尾指针，指向队尾的下一个位置int maxSize; // 队列的最大容量} CircularQueue;```基本操作的实现如下：1. 初始化循环队列：```cvoid initQueue(CircularQueue *queue, int maxSize) {queue->data = (int *)malloc(sizeof(int) * maxSize);queue->front = queue->rear = 0;queue->maxSize = maxSize;}```2. 入队操作：```cint enqueue(CircularQueue *queue, int value) {if ((queue->rear + 1) % queue->maxSize == queue->front) { return 0; // 队列已满，插入失败}queue->data[queue->rear] = value;queue->rear = (queue->rear + 1) % queue->maxSize;return 1; // 插入成功}```3. 出队操作：```cint dequeue(CircularQueue *queue, int *value) {if (queue->front == queue->rear) {return 0; // 队列为空，出队失败}*value = queue->data[queue->front];queue->front = (queue->front + 1) % queue->maxSize; return 1; // 出队成功}```时间复杂度分析：- 入队和出队操作的时间复杂度均为 O(1)。

《数据结构与算法》期末练习一选择题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 54 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．0E．n28．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>, <V1,V3>, <V1,V4>, <V2,V5>, <V3,V5>, <V3,V6>, <V4,V6>, <V5,V7>, <V6,V7>},G的拓扑序列是（ A ）。

数据结构与算法考试题+答案一、单选题（共100题，每题1分，共100分）1.Excel工作表D列保存了18位身份证号码信息，为了保护个人隐私，需将身份证信息的第9到12位用“*”表示，以D2单元格为例，最优的操作方法是：A、=MID(D2,1,8)+"****"+MID(D2,13,6)B、=CONCATENATE(MID(D2,1,8),"****",MID(D.13,6))C、=REPLACE(D2,9,4,"****")D、=MID(D2,9,4,"****")正确答案：C2.小李正在Word中编辑一篇包含12个章节的书稿，他希望每一章都能自动从新的一页开始，最优的操作方法是：A、在每一章最后连续按回车键Enter，直到下一页面开始处B、将每一章标题指定为标题样式，并将样式的段落格式修改为“段前分页”C、在每一章最后插入分页符D、将每一章标题的段落格式设为“段前分页”正确答案：B3.在Excel2010中，要在某个单元格区域的所有空单元格中填入相同的内容，最佳的操作方法是：A、逐一选中这些空单元格，并输入相同的内容B、按住Ctrl键，同时选中这些空单元格，然后在活动单元格中输入所需内容，并使用Ctrl+Enter组合键在其他空单元格中填入相同内容C、选中包含空单元格的区域，并定位到空值，然后在活动单元格中输入所需内容，并使用正确答案：C4.建立表示学生选修课程活动的实体联系模型，其中的两个实体分别是A、课程和成绩B、学生和学号C、课程和课程号D、学生和课程正确答案：D5.PowerPoint2010演示文稿的首张幻灯片为标题版式幻灯片，要从第二张幻灯片开始插入编号，并使编号值从1开始，正确的方法是：A、直接插入幻灯片编号，并勾选“标题幻灯片中不显示”复选框B、从第二张幻灯片开始，依次插入文本框，并在其中输入正确的幻灯片编号值C、首先在“页面设置”对话框中，将幻灯片编号的起始值设置为0，然后插入幻灯片编号，并勾选“标题幻灯片中不显示”复选框D、首先在“页面设置”对话框中，将幻灯片正确答案：C6.JAVA属于：A、操作系统B、办公软件C、数据库系统D、计算机语言正确答案：D7.某公司需要在Excel中统计各类商品的全年销量冠军，最优的操作方法是：A、在销量表中直接找到每类商品的销量冠军，并用特殊的颜色标记。