2014福建省数据结构与算法一点通科目一

C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]
39、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。
A) 单链表 B) 仅有头指针的单循环链表
A）必须是连续的 B）连续不连续都可以
C）部分地址必须是连续 D）必须是不连续的
35、n个顶点的图的最小生成树必定（ D ），是不正确的描述。
A）不唯一 B）权的总和唯一
C）不含回路 D）有n条边
C) 广义表 D) 图
22、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。
A）p->next=p->next->next; B） p=p->next;
C）p=p->next->next; D） p->next=p;
C）查找 D）定位
15、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。
A）9 B）11 C）15 D）不能确定
16、以下属于顺序存储结构优点的是（ A ）。
A) 存储密度大 B) 插入运算方便
A） (G) B） (D) C） C D） D
7、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。
A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表
8、串的逻辑结构与（ D ）的逻辑构不相同。 13、n个顶点的图的最小生成树必定（ D ），是不正确的描述。
A）不唯一 B）权的总和唯一
C）不含回路 D）有n条边

精心整理第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5A6{x=x-10;y--;}elsex++;（2）for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;（3）s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;（6）x=n;//n>1y=0;while(x≥(y+1)*(y+1))y++;1。

C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以（6）线性表Ｌ在（）情况下适用于使用链式结构实现。

A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂（7）单链表的存储密度（）。

A．大于1B．等于1 C．小于1D．不能确定（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A．nB．2n-1 C．2nD．n-1（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。

A．n-i B．n-i+1 C．n-i-1D．i(10)线性表L=(a1，a2,……a n)，下列说法正确的是（）。

A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少有一个元素C．表中诸元素的排列必须是由小到大或由大到小D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

1、结构化程序设计的三种基本控制结构是____。

A、顺序、选择和转向B、层次、网状和循环C、模块、选择和循环D、顺序、循环和选择2、网页上有超链接的地方，鼠标的指针会变成____形状。

A、小手B、箭头C、十字D、竖线3、在ASCII码文件中一个英文字母占____字节。

A、2B、8C、1D、164、在Windows中，控制菜单图标位于窗口的____。

A、左上角B、左下角C、右上角D、右下角5、Internet在中国被称为因特网或____。

A、网中网B、国际互联网C、国际联网D、计算机网络系统6、英文缩写URL所表示的中文含义是____。

A、通用串行总线B、文件传输协议C、电子邮件协议D、统一资源定位器7、标准ASCII码是用7位____代码来表示的。

A、八进制代码B、十进制代码C、二进制代码D、十六进制代码8、在对Word文档进行编辑时，如果操作错误，则____。

A、无法纠正B、只能手工修改C、单击’自动更正’D、单击*撒消’9、在网页中，表单的作用主要是____。

A、收集资料B、发布信息C、处理信息D、分析信息10、计算机联网的主要目的是实现____。

A、数据通信B、资源共享C、远程登录D、分布式处理11、要在Word中使用“格式刷”对同一个格式进行多次复制时，应先用鼠标____。

A、左键单击“格式刷”按钮B、右键单击“格式刷”按钮C、左键双击“格式刷”按钮D、右键双击“格式刷”按钮12、在Word的编辑状态，打开了"wi．doe"文档，若要将经过编辑后的文档以"w2.doc"为名存盘，应当执行“文件”菜单中的命令是____。

A、保存B、别存为HTMLC、另存为D、版本13、关于信息处理的论述正确的是____。

A、信息处理包括信息收集、信息加工、信息存储、信息传递等几项内容B、同学们对一段课文总结中心思想这不能算是一个信息加工过程C、信息传递不是信息处理的一项内容D、信息的存储只能使用计算机的磁盘14、收到一封邮件，再把它寄给别人，一般可以用____。

满足：
T
(n)
2T
(n
O(1) / 2)
O(n)
n 1 n 1
可得T (n) O(n log n)
第 1 页共 4 页
试卷答案网课刷课代刷完成flyingjgh
2、 初始堆（3 分）
删除最大元素后的堆（3 分）
3、 （ 6 分 ） 反 例 （ 不唯一） ：如下图所示，源点为 V1，Dijkstra 算法结束时， dist[3]=1;dist[2]=2 而实际 dist[3]应该为 0。
(1) 置 M 为空集；（1 分） (2) 找出一条关于 M 的增广路径 P，并用 M⊕P 代替 M；（2 分） (3) 重复步骤(2)直至不存在关于 M 的增广路径，最后得到的匹配就是 G 的一 个最大匹配。（1 分）
7、证明：设 n1 为二叉树 T 中度为 1 的结点数 ∵二叉树中所有结点的度均小于或等于 2
int j=q.front();q.pop();// 删除孤独者 if(--c[f[j]]==0)q.push(f[j]);// 新增孤独者入队 } for(int i=0;i<n;i++) if(c[i]==1){cout<<i<<endl;ans++;}// 输出最大和谐子社团 return ans; }
4、一条边 1 分，全对得 6 分。
5、
（3 分）在等概率情况下，该表成功的平均查找长度如下： （ 1×5＋ 2×1＋ 3×1＋ 4×1＋ 6×1） /9＝ 20/9
6、 最 大 匹 配 的 增 广 路 径 算 法 如 下 ：
第 2 页共 4 页
试卷答案网课刷课代刷完成flyingjgh
设 M 是图 G 的一个匹配，将 M 中每边所关联的顶点称为已匹配顶点，其余 顶点称为未匹配顶点。若 p 是图 G 中一条连通 2 个未匹配顶点的路径，并且在路径 p 上属于 M 的边和不属于 M 的边交替出现，则称 p 为一条关于 M 的增广路径。 （2 分）

数据结构第一章课后习题与答案资料1.什么是数据结构？答：数据结构是指数据对象以及数据对象之间的关系、操作和约束的一种逻辑结构。

它关注如何将数据以及数据之间的关系组织起来，以便更高效地进行操作和使用。

2.数据结构的分类有哪些？答：数据结构可以分为线性数据结构和非线性数据结构。

线性数据结构包括数组、链表、栈和队列；非线性数据结构包括树和图。

3.什么是算法？答：算法是指解决特定问题的一系列步骤和规则。

它可以描述为一个有限的指令集，用于将输入数据转换为输出结果。

4.算法的特征有哪些？答：算法具有以下特征：•输入：算法必须有输入，可以是零个或多个。

•输出：算法必须有输出，可以是零个或多个。

•有穷性：算法必须在有限步骤内结束。

•确定性：算法的每一步骤必须明确且无歧义。

•可行性：算法的每一步骤必须可行，即可以执行。

5.算法的时间复杂度是什么？如何表示时间复杂度？答：算法的时间复杂度是指算法执行所需的时间。

它通常用大O符号表示。

常见的时间复杂度有O(1)、O(n)、O(n^2)等。

6.算法的空间复杂度是什么？如何表示空间复杂度？答：算法的空间复杂度是指算法执行所需的额外空间。

它通常用大O符号表示。

常见的空间复杂度有O(1)、O(n)、O(n^2)等。

7.什么是数据的逻辑结构？答：数据的逻辑结构是指数据对象之间的关系。

常见的逻辑结构有线性结构、树形结构和图形结构。

8.什么是数据的存储结构？答：数据的存储结构是指数据在计算机内存中的表示方式。

常见的存储结构有顺序存储结构和链式存储结构。

9.顺序存储结构和链式存储结构有什么区别？答：顺序存储结构将数据存储在一块连续的内存空间中，可以随机访问元素，但插入和删除操作需要移动大量元素。

链式存储结构将数据存储在不连续的内存空间中，通过指针相连，插入和删除操作只需要修改指针，但访问元素需要遍历链表。

10.数组和链表的区别是什么？答：数组是一种顺序存储结构，元素在内存中连续存储，可以通过下标直接访问元素；链表是一种链式存储结构，元素在内存中不连续存储，通过指针相连。

A ．大于 1
B．等于 1
C． 小于 1 D．不能确定
（ 8）将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（
）。
A．n
B ．2n-1
C． 2n
D ．n-1
（ 9）在一个长度为 n 的顺序表中，在第 i 个元素（ 1≤ i≤ n+1 ）之前插入一个新元素时
须向后移动（ ）个元素。
(15) 在双向循环链表中，在 p 指针所指的结点后插入 q 所指向的新结点，其修改指针 的操作是（ ）。
A ． p->next=q; q->prior=p; p->next->prior=q; q->next=q; B． p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C． q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D． q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
第 1 章 绪论
习题
1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储 结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？
5．选择题
（ 1）在数据结构中，从逻辑上可以把数据结构分成（
（ 5）以下与数据的存储结构无关的术语是（

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（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．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

合肥学院20 13 至20 14 学年第 2 学期数据结构与算法设计 课程考试（ A ）卷答案一、选择题：（2分×15=30分）1．A 2．D 3．B 4．B 5. C 6．D 7. A 8． B 9. D 10. B 11. D 12. D 13. A 14. A 15. A二、填空题：（2分×10=20分）1． n+1-i 2． s->next=p->next; p->next=s3. 12，24，35，27，18，26 4． A[i][j]=1 5. h6. ki<=k2i && ki<=k2i+17. mid=(low+high)/2; r[mid].key>k 8． 中序。

三、应用题：（5分×5=25分）1．树的链式存储结构（3分） 二叉树（2分）2．邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡011110101110111010101110（3分）邻接表：（2分）3．（3分）（2分）4．（4分）E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} （1分） 5、（5分）四、算法阅读题：（7分+5分=12分） 1、（1）查询链表的尾结点 （3分） （2）将第一个结点链接到链表的尾部，作为新的尾结点 （3分） （3）返回的线性表为（a2,a3,…,an,a1）。

（1） 2．递归地后序遍历链式存储的二叉树 （5分） 五、算法设计题：（7分+6分=13分） 1．void mergelklist(lklist *ha,lklist *hb,lklist *&hc)AB GC EH JF D Ilklist *s=hc=0; （2分）while(ha!=0 && hb!=0)if(ha->data<hb->data){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} （3分）if(ha==0) s->next=hb; else s->next=ha; （2分）}2.typedef struct node {int data; struct node *lchild,*rchild;} bitree; （2分）void swapbitree(bitree *bt){bitree *p;if(bt==0) return;swapbitree(bt->lchild); swapbitree(bt->rchild); （2分）p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; （2分）}。

3.简答题
（ 1） 常见的逻辑结构有哪几种， 各自的特点是什么？常用的存储结构有哪几种， 各自的特点是什么？ 【解答】常见的四种逻辑结构有： ① 集合结构：数据元素间的关系是“属于同一个集合” 。 ② 线性结构：数据元素之间存在着一对一的关系。 ③ 树型结构：数据元素之间存在着一对多的关系。 ④ 图型结构：数据元素之间存在着多对多的关系。 常见的四种存储结构有： ① 顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本 的存储表示方法，通常借助于程序设计语言中的数组来实现。 ② 链接存储：对逻辑上相邻的元素不要求不要求物理位置相邻的存储单元，元素间的逻辑关系通过 附设的指针域来表示。 ③ 索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信 息，可通过该地址找到结点其它信息。 ④ 散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。 （2）简述算法和程序的区别。 【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相似，但又有区 别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没 有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是 机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定 的实现。 （3）试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算这三方面的内容。 【解答】略。 （4）运算是数据结构的一个重要方面。试举例说明两个数据结构的逻辑结构和存储方式完全相同， 只是对于运算的定义不同，使得两个结构具有显著不同的特性。 【解答】比如顺序栈和循环队列，二者的逻辑结构都是线性结构，都采用顺序存储方式存储，但它们运算 不同，栈限定元素的插入和删除在栈顶进行，队列限定元素在队尾插入、在队首删除，从而它们是截然不 同的数据结构。 （5）分析下列程序段中带标号“#”语句的执行频度（n 为正整数） 。 1）j=1; k=0; while(j<=n-1)

选择题----------第1题在多媒体课件中，学生可以按照自己的意愿来选择学习内容，这主要体现的多媒体技术特征是A 数字性B 交互性C 集成性D 传播性答案：B第2题下列不属于图像文件的是A 实验.bmpB 实验.psdC 实验.wavD 实验.jpg答案：C第3题下列适合于制作多媒体作品的软件是A PowerPointB ExcelC AccessD Wave Edit答案：A第4题如图所示的搜索引擎类型属于A 全文搜索引擎B 目录搜索引擎C 元搜索引擎D 垂直搜索引擎答案：B第5题下列书写正确的电子邮箱地址是A @163B 192.168.243.5C fjjcjy@D 答案：C第6题在网址""中，""称为A 主页名B 主机名C E_mail地址D 域名答案：D第7题下列属于数据库管理系统的是A AccessB OfficeC WindowsD Linux答案：A第8题下列属于数据库系统阶段特点的是A 数据结构化B 数据冗余度大C 数据与程序联系紧密D 数据独立性差答案：A第9题下列属于Access数据库文件的是A 图书.exeB 图书.rarC 图书.psdD 图书.mdb答案：D第10题下列用计算机编程解决问题的基本步骤，正确的顺序是①编写程序②设计算法③分析问题④调试程序A ①②③④B ③④①②C ②③①④D ③②①④答案：D第11题下列不属于程序基本结构的是A 树形结构B 顺序结构C 选择结构D 循环结构答案：A第12题在VB语言中，下列正确的变量定义语句是A Dim As String xuehaoB Dim xuehao As StringC Dim String As xuehaoD Const xuehao As String答案：B第13题下列关于VB控件的叙述，正确的是A 控件被添加到窗体后，不能改变其位置和大小B 单击工具箱中的控件图标后，该控件被添加到窗体中央C 选定控件后，可按Delete键删除控件D 不能对控件进行复制和粘贴答案：C第14题在VB语言中，Label1的默认触发事件是A Label1_Load()B Label1_Click()C Label1_Change()D Label1_DblClick() 答案： B 第15题 下列属于VB 工程文件的是 A Form1.frm B 工程1.vbp C Date.txt D Ert.pdf 答案： B 第16题 下列不属于高级程序设计语言的是 A Visual Basic B Pascal C Dim D C++ 答案： C 第17题 在VB 中，下列合法的变量名是 A date B V+B C 2aB D WWW 答案： D 第18题 在VB 中，表达式 6 * 8 \ 9的值为 A 5 B 4 C 0 D 9 答案： A 第19题 若a=9、b=7，则语句 Print "a-b=";a-b 的运行结果为 A 9-7=2 B a-b= 2 C "a-b="2 D 9-7=a-b 答案： B第20题 将代数式b a a 32转换为VB 表达式，正确的是 A 2a^3/a-b B 2a*3/a-b C 2*a^3/(a-b) D 2*a*3/a-b 答案： C 第21题 下列可用于表示"8≤a ≤20"的VB 表达式是 A a>=8 and a<=20 B a ≥8 and a ≤20 C 8<=a<=20 D 8≤a ≤20 答案： A 第22题 函数Int (-6.8 + 5)的返回值是A -3B 1C -4D -2答案：D第23题下列不正确的赋值语句是A Text1.text=XB x=x+1C x+1=xD X=Text1.text答案：C第24题若x、y均为整型变量，执行下列程序段后，x、y的值分别为x = 8y = 6x = x Mod yy = y/xA 3，2B 2，3C 3，1D 1，3答案：B第25题如图所示的算法用于求正方体的体积。

A．O（1） B．O（n） C．O（n2） D．O（nlog2n）
5、在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行 B 操作与链表的长度有关。
A．删除单链表中的第一个元素
B．删除单链表中的最后一个元素
C．在单链表第一个元素前插入一个新元素
D．在单链表最后一个元素后插入一个新元素
A．p->prior = s；s->next = p；p->prior->next = s；s->prior = p->prior
B．p->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior
C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s
C）DEBFGCA D）GFCEBDA
30、下列选项中，符合堆定义的是
A．{102，24，55，60，89，93}
B．{24，89，55，60，93，102}
C．{102，93，55，60，89，24}
D．{102，60。89，93，55，24}
31、若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是
D．依附于对应顶点v的边数
13、衡量查找算法效率的主要标准是（ C ）。
A）元素个数 B）所需的存储量
C）平均查找长度 D）算法难易程度
14、6个顶点的强连通图中，含有的边数至少是
A．4 B．5 C．6 D．7
A．p->next == NULL B．p == NULL

《数据结构》-1一、判断题 (每小题1分，共10分)1、线性表的逻辑顺序与物理顺序总是一致的。

( )2、线性表只能采用顺序存储结构或者链式存储结构。

( )3、线性表的顺序存储表示优于链式存储表示。

( )4、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。

( )5、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

( )6、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。

( )7、一般树和二叉树的结点数目都可以为0。

( )8、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。

( )9、每种数据结构都应具备三种基本运算：插入、删除和搜索。

( )10、若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。

( )二、单项选择题 (每小题2分，共20分)1、算法分析的目的是( )A.研究算法的输入与输出之间的关系B.找出数据结构的合理性C.分析算法的效率以求改进算法D.分析算法的可读性与可移植性2、已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作( )A. s->link = p； p->link = s；B. s->link = p->link； p->link = s；C. s->link = p->link； p = s；D. p->link = s； s->link = p；3、图的深度优先搜索类似于树的（）次序遍历。

A.先根B.中根C.后根D.层次4、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列（）A. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，15、若深度为5的完全二叉树的第5层有3个叶结点，则该二叉树一共有( )个结点。

A.15B.16C.17D.186、下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关（）A. 直接插入排序B. 起泡排序C. 快速排序D. 直接选择排序7、对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，38 ,50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是( )A.插入排序法B.选择排序法C.冒泡排序法D.堆积排序法8、对于循环队列，存储空间大小为n，头指针为F，尾指针为R。

1、删除刚刚建立的My Picture文件夹，删除的方法不正确的____A、选中My Picture，按DeleteB、选中My Picture，按右键弹出菜单中的删除C、选中My Picture，双击鼠标左键D、选中MyPicture，按工具栏上的删除按钮2、电子邮件服务的功能不包括____。

A、发邮件B、收邮件C、制作动画D、删除邮箱中的邮件3、在计算机网络中，为了使计算机或终端之间能够正确传送信息，必须按照____来相互通信。

A、信息交换方式B、网卡C、传输装置D、网络协议4、系统软件的核心是____。

A、操作系统B、诊断程序C、软件工具D、语言处理程序5、D、*6、按拓扑类型对计算机网络分类，下列哪项是错的____。

A、环型网B、总线网C、星型网D、广播网7、在Word中，如果对当前编辑的文本进行了修改，没有存盘就选择了关闭命令，则____。

A、Word会显示出错信息，并拒绝执行命令，回到编辑状态。

B、Word会弹出对话框，提醒用户保存对文件所做的修改，然后关闭文本。

C、Word会自动为用户将当前编辑的文件存盘。

D、Word会执行命令关闭编辑的文本，而对当前编辑的文本的最新改动将会丢失。

8、所谓媒体是指____。

A、表示和传播信息的载体B、各种信息的编码C、计算机的输入和输出信息D、计算机屏幕显示的信息9、在PowerPoint2000中，若为幻灯片中的对象设置"飞入"，应选择对话框____。

A、自定义动画B、幻灯片版式C、自定义放映D、幻灯处放映10、用以太网形式构成的局域网，其拓扑结构为____。

A、环型B、总线型C、星型D、网状型11、要在Web浏览器中查看某一公司的主页，必须知道____。

A、该公司的电子邮件地址B、该公司所在的省市C、该公司的邮政编码D、该公司的WWW地址12、ISP指的是____。

A、因特网的专线接入方式B、因特网服务提供商C、拨号上网方式D、因特网内容供应商13、PC机中最重要的核心部件是____。

数据结构与算法习题册（课后部分参考答案）《数据结构与算法》课程组目录目录课后习题部分第一章绪论 (1)第二章线性表 (3)第三章栈和队列 (5)第四章串 (8)第五章数组和广义表 (10)第六章树和二叉树 (13)第七章图 (16)第九章查找 (20)第十章排序 (23)第一章绪论一. 填空题1. 从逻辑关系上讲，数据结构的类型主要分为集合、线性结构、树结构和图结构。

2. 数据的存储结构主要有顺序存储和链式存储两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素和数据元素之间的关系。

3. 算法具有五个特性，分别是有穷性、确定性、可行性、输入、输出。

4. 算法设计要求中的健壮性指的是算法在发生非法操作时可以作出处理的特性。

二. 选择题1. 顺序存储结构中数据元素之间的逻辑关系是由 C 表示的，链接存储结构中的数据元素之间的逻辑关系是由 D 表示的。

A 线性结构B 非线性结构C 存储位置D 指针2. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是B 。

A 树B 图C 线性表D 集合3. 算法指的是 A 。

A 对特定问题求解步骤的一种描述，是指令的有限序列。

B 计算机程序C 解决问题的计算方法D 数据处理三. 简答题1. 分析以下各程序段，并用大O记号表示其执行时间。

(1) (2)i=1;k=0; i=1;k=0;While(i<n-1) do{ {k=k+10*i; k=k+10*i;i++; i++;} }while(i<=n)⑴基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。

⑵基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。

2. 设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（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．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

2013—2014学年第一学期闽江学院考试试卷《数据结构与算法》A 卷参考答案及评分标准一、选择题答案（每题2分） 30%二、填空题（每空 2分） 20% 1、p->nexts 2、53、1+n2+2n3+…+(k-1)nk4、n-1 n+15、CDBGFEA6、2n-17、A[7]、A[3]、A[5]、A[4] 8、2e三、判断题（每题1分） 10%四、应用题（5小题） 32 %1、（6分）画哈夫曼树（每个叶子结点位置正确得0.5分，总5分） 计算WPL 正确得1分WPL=(2+4)*5+(5+7+8)*4+(9+10+15+18)*3+22*2=30+80+156+44=3102、（8分）(1)二叉排序树 (每个结点在正确的位置正确得0.5分，总6分)(2)查找成功时的平均查找长度： （总2分） ASL=(1*1+2*2+4*3+5*4)/12 =37/12= 3.083、（5分）（每行正确得0.5分，总5分） 原始数据：（27），10，21，37，9，55，16，61，103，2 第一趟后:（10，27），21，37，9，55，16，61，103，2 第二趟后:（10，21，27），37，9，55，16，61，103，2 第三趟后:（10，21，27，37），9，55，16，61，103，2 第四趟后:（9，10，21，27，37），55，16，61，103，2第五趟后:（9，10，21，27，37，55），16，61，103，2 第六趟后:（9，10，16，21，27，37，55），61，103，2 第七趟后:（9，10，16，21，27，37，55，61），103，2 第八趟后:（9，10，16，21，27，37，55，61，103），2 第九趟后:（2，9，10，16，21，27，37，55，61，103） 4、（5分）哈希表，每个表结点在正确的位置得0.5分，计4分；查找成功时的平均查找长ASL 成功=（1*6+2*1+3*1）/8=11/8=1.3625 (1分) 5、（8分）得分标准：每个结点的邻接点均正确得0.5分（即每行0.5分）克鲁斯卡尔算法画出最小生成树的过程（4分）：（1） （2）（3）（4）（5）（6）（7）（8）得分标准：依次得出上面八张图，每张0.5分，计4分，其中第（4）、（5）张，第（6）、（7）张两权值相同的边顺序可调换。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（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．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。