大工20春9月网考【数据结构】复习资料
- 格式：docx
- 大小：40.18 KB
- 文档页数：7
下载文档原格式
合集下载
大工20春9月网考【数据结构】复习资料
大连理工大学网络教育学院2020年春《数据结构》期末考试复习题☆注意事项：本复习题满分共：200分。
一、单项选择题1、在队列中存取数据的原则是（）。
A．先进先出B．后进先出C．先进后出D．随意进出2、在下列链表中，不能从当前结点出发访问到其余各结点的是（）。
A．单链表B．单循环链表C．双向链表D．双向循环链表3、在一棵二叉树上第5层的结点数最多为（）设树根为第1层。
A．16 B．15 C．8 D．324、一棵有124叶子结点的完全二叉树，最多有（）个结点。
A．247 B．249 C．248 D．1255、具有10个叶子结点的二叉树中有（）个度为2的结点。
A．8 B．9 C．10 D．116、若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（）。
A．gdbehfca B．bdgaechfC．gdbecfha D．gcefhabd7、对线性表进行顺序查找时，要求线性表的存储结构是（）。
A．倒排表B．索引表C．顺序表或链表D．散列表8、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找，则查找元素26的查找长度为（）。
A．2 B．3 C．4 D．59、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）。
A．希尔排序B．起泡排序C．插入排序D．选择排序10、堆的形状是一棵（）。
A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树11、线性表采用顺序存储结构时，其地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以12、在栈中存取数据的原则是（）。
A．先进先出B．后进先出C．后进后出D．随意进出13、插入和删除只能在一端进行的线性表，称为（）。
A．队列B．循环队列C．栈D．数组14、一个基本线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）。
电大《数据结构(本)》复习题及答案
数据结构(本)复习题一、单项选择题(每小题2分，共30分)1．深度为5的完全二叉树共有20个结点，则第5层上有( )个结点(根所在结点为第一层)。
A．3B．8C．5D．62．已知一个图的边数为ii，则该图的所有顶点的度数之和为( )。
A．2mB．mC．2m+1D．m/23．数据结构中，与所使用的计算机无关的是数据的( )结构。
A．物理B．存储C．逻辑与物理D．逻辑4．链表所具备的特点是( )。
A．可以随机访问任一结点B．占用连续的存储空间C．插人删除不需要移动元素结点D．可以通过下标对链表进行直接访问5．线性表只要以( )方式存储就能进行折半查找。
A．链接B．顺序C．关键字有序的顺序D．二又树6．散列查找的原理是( )。
A．在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系B．按待查记录的关键字有序的顺序方式存储C．按关键字值的比较进行查找D．基于二分查找的方法7．对n个元素进行冒泡排序若某趟冒泡中只进行了( )次元素间的交换，则表明序列已经排好序。
A．1B．2C．0D．n-18．排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是( )。
A．直接插入排序B．快速排序C．冒泡排序D．选择排序9．在对一组元素(64,48,106,33,25,82,70,55,93)进行直接插入排序时，当进行到要把第7个元素70插入到已经排好序的子表时，为找到插人位置，需进行( )次元素n的比较(指由小到大排序)。
A．6B．2C．3D．410．采用顺序查找法对长度为n的线性表进行查找(不采用表尾设监视哨的方法)，最坏的情况下要进行( )次元素间的比较。
A．n+2B．nC．n-1D．n/211如图，若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为( )。
A．acebdgfB．abecdgfC．acfedgbD．abecfdg12．元素2,4,6,8按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。
开放大学数据结构2020年考试必备填空题
1、数据结构按结点间的关系，可分为4种逻辑结构：集合、线性结构、树形结构、图状结构。
2、数据结构中的数据元素存在多对多的关系称为图状结构结构。
3、在一个长度为n的顺序存储结构的线性表中，向第i(1≤i≤n+1)个元素之前插入新元素时，需向后移动n-i+1个数据元素。
4、从长度为n的采用顺序存储结构的线性表中删除第i(1≤i≤n+1)个元素，需向前移动n-i个元素。
5、数据的逻辑结构在计算机中的表示称为物理结构或存储结构。
6、除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为线性结构，每个结点可有任意多个前驱和后继结点数的结构为非线性结构。
7、算法的5个重要特性是有穷性、确定性、可形性、有零个或多个输入、有零个或多个输出。
8、数据结构中的数据元素存在一对多的关系称树形结构结构。
9、往栈中插入元素的操作方式是：先移动栈顶指针，后存入元素。
10、数据结构中的数据元素存在一对一的关系称为线性结构结构。
11、要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。
则比较的次数和算法的时间复杂度分别为n-1和O(n)。
12、在一个单链表中p所指结点之后插入一个s所指结点时，应执行__s->next=p->next;__和p->next=s;的操作。
13、设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next= =head，则p所指结点为尾结点。
14、在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。
则可以用操作q->next=p->next; 。
15、设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL,通过操作p->next=head;,就可使该单向链表构造成单向循环链表。
16、每个结点只包含一个指针域的线性表叫单链表。
17、线性表具有顺序存储和链式存储两种存储结构。
北语20春《数据结构》作业4.doc
1.A.AB.BC.CD.D【参考答案】: D2.A.AB.BC.CD.D【参考答案】: A3.不定长文件是指___。
A.文件的长度不固定B.记录的长度不固定C.字段的长度不固定D.关键字项的长度不固定【参考答案】: B4.在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行___操作与链表的长度有关。
A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素【参考答案】: B5.栈的插入和删除操作在___进行。
A.栈顶B.栈底C.任意位置D.指定位置【参考答案】: A6.A.AB.BC.CD.D【参考答案】: D7.顺序查找法适合于存储结构为___的线性表。
A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储【参考答案】: B8.以下____不是队列的基本运算。
A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值【参考答案】: B9.A.AB.BC.CD.D【参考答案】: C10.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有___条有向边。
A.nB.n-1C.mD.m-1【参考答案】: C11.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为___。
A.O（0）B.O（1）C.O（n）D.O（n2）【参考答案】: C12.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为___。
A.O（1）B.O（n）C.O（m）D.O（mn）【参考答案】: C13.A.AB.BC.CD.D【参考答案】: A14.线性表（a1,a2,...,an）以链式方式存储，访问第i位置元素的时间复杂度为___。
A.O（0）B.O（1）C.O（n）D.O（n2）【参考答案】: C15.A.AB.BC.CD.D【参考答案】: B16.A.AB.BC.CD.D【参考答案】: A17.线性表采用链式存储时，结点的存储地址___。
大工19秋《数据结构》期末考试复习题
机密★启用前大连理工大学网络教育学院2019年秋《数据结构》期末考试复习题☆注意事项：本复习题满分共：200分。
一、单项选择题1、在队列中存取数据的原则是（）。
A．先进先出B．后进先出C．先进后出D．随意进出2、在下列链表中，不能从当前结点出发访问到其余各结点的是（）。
A．单链表B．单循环链表C．双向链表D．双向循环链表3、在一棵二叉树上第5层的结点数最多为（）设树根为第1层。
A．16 B．15 C．8 D．324、一棵有124叶子结点的完全二叉树，最多有（）个结点。
A．247 B．249 C．248 D．1255、具有10个叶子结点的二叉树中有（）个度为2的结点。
A．8 B．9 C．10 D．116、若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（）。
A．gdbehfca B．bdgaechfC．gdbecfha D．gcefhabd7、对线性表进行顺序查找时，要求线性表的存储结构是（）。
A．倒排表B．索引表C．顺序表或链表D．散列表8、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找，则查找元素26的查找长度为（）。
A．2 B．3 C．4 D．59、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）。
A．希尔排序B．起泡排序C．插入排序D．选择排序10、堆的形状是一棵（）。
A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树11、线性表采用顺序存储结构时，其地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以12、在栈中存取数据的原则是（）。
A．先进先出B．后进先出C．后进后出D．随意进出13、插入和删除只能在一端进行的线性表，称为（）。
A．队列B．循环队列C．栈D．数组14、一个基本线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）。
电大数据结构(本)期末复习汇报材料
中央电大开放本科计算机科学与技术数据结构（本）期末综合练习一、单项选择题1．数据元素是数据的基本单位，它（ C ）。
A．只能有一个数据项组成 B．至少有二个数据项组成C．可以是一个数据项也可以由若干个数据项组成 D．至少有一个数据项为指针类型2．一种逻辑结构（ A ）存储结构。
A．可以有不同的 B．只能有唯一的C．的数据元素在计算机中的表示称为 D．的数据元素之间的关系称为3．线性表的顺序结构中，（ C ）。
A．逻辑上相邻的元素在物理位置上不一定相邻 B．数据元素是不能随机访问的C．逻辑上相邻的元素在物理位置上也相邻 D．进行数据元素的插入、删除效率较高4．以下说法中不正确的是（ B ）。
A．双向循环链表中每个结点需要包含两个指针域B．已知单向链表中任一结点的指针就能访问到链表中每个结点C．顺序存储的线性链表是可以随机访问的 D．单向循环链表中尾结点的指针域中存放的是头指针5．以下表中可以随机访问的是（ D ）。
A．单向链表 B．双向链表 C．单向循环链表 D．顺序表6．双向循环链表结点的数据类型为：struct node{ int data;struct node *next; /*指向直接后继*/struct node *prior;}；设p指向表中某一结点，要显示p所指结点的直接前驱结点的数据元素，可用操作（ B ）。
A．printf(“%d”,p->next->data); B．printf(“%d”,p->prior->data);C．printf(“%d”,p->prior->next); D．printf(“%d”,p->data);7 .设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（ A ）。
A．(n+1)/2 B．n C．2n D．n-i8．一个栈的进栈序列是efgh，则栈的不可能的出栈序列是（ D ）（进出栈操作可以交替进行）。
大工16春《数据结构》开卷考试复习资料
机密★启用前大连理工大学网络教育学院2016年9月《数据结构》课程期末复习资料☆注意事项：本复习题满分共：400分。
一、单项选择题（本大题共65小题，每小题3分，共195分）1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。
(A).正确性 (B). 可行性 (C). 健壮性 (D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。
for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A).n2 (B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。
（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。
（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k 6．具有60个结点的二叉树，其叶子结点有12个，则度为1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377.下列程序段的时间复杂度为（）。
for(i=0； i<m； i++) for(j=0； j<t； j++) c[i][j]=0；for(i=0；i<m；i++) for(j=0；j<t；j++) for(k=0；k<n；k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]；(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n) 8．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
(A) n-i (B) n+1 -i (C) n-1-i (D) i9．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。
[大连理工大学]20春《数据结构》在线作业1-复习资料答案
科目名称：大工20春《数据结构》在线作业1学校名称：奥鹏-大连理工大学一、单选题 (共 10 道试题,共 50 分)1.以下选项属于非线性结构的是( )。
A.广义表B.队列C.优先队列D.栈提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：A2.在存储数据时,通常不仅需要存储数据元素的值,还要存储( )。
A.数据元素的类型B.数据的基本运算C.数据元素之间的关系D.数据的存取方式提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：C3.以下选项属于逻辑结构的是( )。
A.顺序表B.散列表C.有序表D.单链表提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：C4.一个递归算法必须包括( )。
A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：B5.算法的时间复杂度与( )有关。
A.问题规模B.计算机硬件的运行速度C.源程序的长度D.编译后执行程序的质量提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：A6.静态链表与动态链表相比较,其缺点是( )。
A.插入和删除需移动较多数据B.有可能浪费较多存储空间C.不能随机存取D.以上都不是提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：B7.链式栈和顺序栈相比,有一个比较明显的优点,即( )。
A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：B8.链式栈的栈顶在链表的( )位置。
A.链头B.链尾C.链中D.任意提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：A9.栈和队列具有相同的( )。
A.逻辑结构B.存储结构C.存取点D.运算提示：本题为必答题，请认真阅读题目后再作答--本题参考答案：A10.计算机操作系统为了实现进程管理,采用了多种进程调度策略,先来先服务的策略使用了( )作为算法实现的基础。
大连理工大学22春“计算机科学与技术”《数据结构》期末考试高频考点版(带答案)试卷号：5
大连理工大学22春“计算机科学与技术”《数据结构》期末考试高频考点版（带答案）一.综合考核(共50题)1.一个算法是可行的，即算法中描述的操作都是可以通过已实现的基本运算执行有限次来实现的。
()A.正确B.错误参考答案：A2.串的长度是指()。
A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数参考答案：B3.一个栈的输入序列为123...n，若输出序列的第一个元素是n，输出第i(1=i=n)个元素是()。
A.不确定B.n-i+1C.iD.n-i参考答案：B4.具有10个叶结点的二叉树中有()个度为2的结点。
A.8B.9C.10D.11参考答案：B5.若一棵二叉树的先序遍历序列为efhigjk，中序遍历序列为hfiejkg，则该二叉树根结点的右孩子为()。
A.eB.fC.gD.h参考答案：C6.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是()。
A.空B.完全二叉树C.二叉排序树D.高度等于其结点数参考答案：D7.同一个算法，实现语言级别越高，算法执行的效率越低。
()A.正确B.错误参考答案：A8.一棵线索二叉树中含有的线索数比分支数多()个。
A.2B.1C.0D.不确定参考答案：A9.队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。
()A.正确B.错误参考答案：A10.栈和队列具有相同的()。
A.逻辑结构B.存储结构C.存取点D.运算参考答案：A11.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
()A.正确B.错误参考答案：B12.一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。
()A.正确B.错误参考答案：A13.树的后根遍历序列等同于该树对应的二叉树的()。
A.先序序列B.中序序列C.后序序列D.以上都不对参考答案：B14.从19个记录中查找其中的某个记录，最多进行4次关键字的比较，则采用的查找方法只可能是()。
数据结构考试试题库含答案解析
数据结构习题集含答案目录目录 (1)选择题 (2)第一章绪论. (2)第二章线性表. (4)第三章栈和队列. (6)第四章串. (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图. (11)第八章查找. (13)第九章排序. (14)简答题 (19)第一章绪论. (19)第二章线性表. (24)第三章栈和队列. (26)第四章串. (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图. (36)第八章查找. (38)第九章排序. (39)编程题 (41)第一章绪论. (41)第二章线性表. (41)第三章栈和队列. (52)第四章串. (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图. (52)第八章查找. (52)第九章排序. (57)选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（ A ）A、针对非数值计算的程序设计问题 B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（ D ）A、研究数据对象和数据之间的关系 B 、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（ C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班级的学生成绩表是数据对象，90 分是数据元素C、某班级的学生成绩表是数据对象，90 分是数据项D、某班级的学生成绩表是数据元素，90 分是数据元素4. *数据结构是指（A ）。
A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。
A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6. 算法分析的目的是（ C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7. 算法分析的主要方法（ A ）。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
大连理工大学网络教育学院2020年春《数据结构》期末考试复习题☆注意事项：本复习题满分共：200分。
一、单项选择题1、在队列中存取数据的原则是（）。
A．先进先出B．后进先出C．先进后出D．随意进出2、在下列链表中，不能从当前结点出发访问到其余各结点的是（）。
A．单链表B．单循环链表C．双向链表D．双向循环链表3、在一棵二叉树上第5层的结点数最多为（）设树根为第1层。
A．16 B．15 C．8 D．324、一棵有124叶子结点的完全二叉树，最多有（）个结点。
A．247 B．249 C．248 D．1255、具有10个叶子结点的二叉树中有（）个度为2的结点。
A．8 B．9 C．10 D．116、若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（）。
A．gdbehfca B．bdgaechfC．gdbecfha D．gcefhabd7、对线性表进行顺序查找时，要求线性表的存储结构是（）。
A．倒排表B．索引表C．顺序表或链表D．散列表8、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找，则查找元素26的查找长度为（）。
A．2 B．3 C．4 D．59、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）。
A．希尔排序B．起泡排序C．插入排序D．选择排序10、堆的形状是一棵（）。
A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树11、线性表采用顺序存储结构时，其地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以12、在栈中存取数据的原则是（）。
A．先进先出B．后进先出C．后进后出D．随意进出13、插入和删除只能在一端进行的线性表，称为（）。
A．队列B．循环队列C．栈D．数组14、一个基本线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）。
A．110 B．108 C．100 D．12015、算法分析的目的（）。
A．找出数据结构的合理性B．研究算法中的输入与输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性16、结点前序为xyz的不同二叉树，那么它有（）种不同状态。
A．3 B．4 C．5 D．617、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。
A．98 B．99 C．50 D．4818、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（），设根结点的所在高度为1。
A．2h B．2h-1C．2h+1 D．h+119、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。
A．n B．n+1C．n-1 D．n/220、存储在磁带上的顺序文件的查找只能用（）。
A．顺序查找B．二分查找C．分块查找D．树表查找单选题答案1． A 2． A 3． A 4． C 5． B6． A 7． C 8． C 9． D 10． C11． A 12．B 13．C 14．B 15． C16． C 17．A 18．B 19．C 20． A二、填空题1、一个算法有五个特性：_______、_______、_______、有零个或多个输入、有一个或多个输出。
2、栈S在进行出栈操作时首先要判断_______。
3、在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=_______。
4、设front为队首指针，rear为队尾指针，则循环队列sq是空队列的条件是_______。
5、同一数组中各元素的长度_______。
6、深度为k的二叉树共有2k-1个结点，该二叉树为_______二叉树。
7、若图G中每条边都_______方向，则称G为无向图。
8、二叉树的按层次遍历类似于图的_______遍历。
9、选择排序算法的效率为_______。
10、冒泡排序算法的效率为_______。
答案：1、有穷性、确定性、可行性2、栈空否3、n2+14、sq->rear==sq->front5、相等6、满7、没有8、广度优先9、O(nlogn)10、O(n2)三、判断题1、数组的缺点是插入、删除运算效率低。
（√）2、链表的优点是插入、删除运算效率高。
（√）3、对图进行深度优先遍历时，应借助于一个队列。
（×）4、二叉树的深度优先遍历与先序序列一致。
（√）5、归并排序算法是原地算法。
( ×)6、堆数据结构可以看作是一个非完全二叉树。
( ×)7、对图进行广度优先遍历时，应借助于一个队列。
（√）8、二叉树的深度优先遍历与后序序列一致。
（×）9、对图进行广度优先遍历时，应借助于一个栈。
（×）10、冒泡排序算法是原地算法。
( √)四、简答题1、初始为空的队列中，元素f,e,d,c,b,a依次进队以后，连续进行了三次出队操作，此时的队首元素是什么？队尾元素是什么？队列操作应遵循的原则是什么？答：（1）队首元素是c（2）队尾元素是a（3）队列操作应遵循的原则是先进先出2、当为解决某一问题而选择数据结构时，应从哪些方法考虑？答：通常从两方法考虑；第一是算法所需的存储空间量，第二是算法所需的时间。
对算法所需的时又涉及以下几点：1）程序运行时所需输入的数据总量2）计算机执行每条指令所需的时间3）程序中指令重复执行的次数3、写出用直接插入法排序将数值序列{33,23,8,41,68,64,50}排序过程的每一趟结果。
答：（1）23 33 8 41 68 64 50（2）8 23 33 41 68 64 50（3）8 23 33 41 68 64 50（4）8 23 33 41 68 64 50（5）8 23 33 41 64 68 50（6）8 23 33 41 50 64 684、简述顺序表特点。
答：优点：可随机存取表中任意数据元素，算法简单，空间利用率高；直接可获取线性表的长度。
缺点：1）需要预先确定数据元素的最大个数；2）数据元素的插入、删除相对麻烦，插入和删除时需要移动较多的数据元素。
5、简述逻辑结构和存储结构的关系。
答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。
存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各种数据元素间的逻辑关系。
通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储或链式存储结构表示。
6、简述线性表、栈和队列的异同。
答：线性表、栈和队列中元素这之间的逻辑关系都是线性关系。
栈和队列是操作位置受限的线性表，即对播入和删除操作的位置加以限制，都只能在端点进行。
栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。
队列是只允许在表的一端进行插入，另一端进行删除操作的线性表，因而是先进先出表。
7、堆排序是否是一种稳定的排序方法？为什么？答：堆排序是不种不稳定的排序方法。
因为在堆的调整过程中，关键字进行比较和交换所走的是该节点到叶子节点的一条路径，因此对相同的关键字而言，就可能出现排在后面的关键字补交换到前面来的情况。
8、若频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构，为什么？答：宜采用链式存储结构。
因为采用链式结构存储线性表，在插入和删除操作时只修改相关节点的指针域，不需要移动节点；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。
修改指针域操作比移动元素操作花费的时间少得多。
9、对单链表设置头节点的作用是什么？答：对于带头节点的单链表，在单链表的任何节点之前插入节点或删除节点，所要做的都是修改前一个节点的指针域，因为任何节点都有前驱节点（若单链表没有头节点，则首节点没有前驱节点，在其前插入节点和删除节点时操作复杂些）。
对于带头节点的链表，在表空时也存在一个头节点，因此空表与非空表的处理是一样的。
五、算法题1、简述冒泡排序算法的思想，并通过类Ｃ语言给出代码实现。
算法思想1）不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。
2）检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束。
void BubbleSort(Record Array[], int n) {bool NoSwap;// 是否发生了交换的标志int i, j;for (i = 0; i < n-1; i++) {NoSwap = true;// 标志初始为真for (j = n-1; j > i; j--)if (Array[j] < Array[j-1]) { // 判断是否逆置swap(Array, j, j-1);// 交换逆置对NoSwap = false;// 发生了交换，标志变为假}if (NoSwap) // 没发生交换，则排好序return;}}2、简述直接选择排序算法的思想，并用类Ｃ语言给出算法实现。
算法思想：选出未排序记录中的最小记录，然后直接与未排序序列中第1个记录交换。
void SelectSort(Record Array[], int n) {// 依次选出第i小的记录，即剩余记录中最小的那个for (int i=0; i<n-1; i++) {// 首先假设记录i就是最小的int Smallest = i;// 开始向后扫描所有剩余记录for (int j=i+1;j<n; j++)// 如果发现更小的记录，记录它的位置if (Array[j] < Array[Smallest])Smallest = j;//将第i小的记录放在数组中第i个位置Record temp = Array[Smallest];Array[Smallest]= Array[i];Array[i]= temp;}}3、简述直接插入排序算法的思想，并通过类Ｃ语言给出代码实现。
算法思想:利用有序表的插入操作进行排序void InsertSort (Record Array[], int n) {//Array[]为待排序数组，n为数组长度Record TempRecord;// 临时变量for (int i=1; i<n; i++) {// 依次插入第i个记录TempRecord = Array[i];//从i开始往前寻找记录i的正确位置int j = i-1;//将那些大于等于记录i的记录后移while ((j>=0) && (TempRecord < Array[j])) {Array[j+1] = Array[j];j = j - 1;}//此时j后面就是记录i的正确位置，回填Array[j+1] = TempRecord;}}。