吉大18秋学期《数据结构》在线作业一满分答案

------------------------------------------------------------------------------------------------------------------------------(单选题) 1: 有如下程序：long fib（int n）{ if（n>2）return（fib（n-1）+fib（n-2））; else return（2）; } main（）{ printf（"%d＼n",fib（3））;} 该程序的输出结果是A: 2B: 4C: 6D: 8正确答案:(单选题) 2: 以下程序有语法错误，有关错误原因的正确说法是main（）{ int G=5,k; void prt_char（）; ... k=prt_char（G）; ... }A: 语句 void prt_char（）;有错，它是函数调用语句，不能用void说明B: 变量名不能使用大写字母C: 函数说明和函数调用语句之间有矛盾D: 函数名不能使用下划线正确答案:(单选题) 3: 下面程序的运行结果是#include main（）{ int y=10; do{y--;}while（--y）; printf（"%d＼n",y--）; }A: 1B: 1C: 8D: 0正确答案:(单选题) 4: 下列程序的输出结果是int b=2; int func（int *a）{ b += *a; return（b）;} main（）{ int a=2, res=2; res += func（&a）; printf（"%d＼n",res）; }A: 4B: 6C: 8D: 10正确答案:(单选题) 5: 执行以下程序后，a,b的值分别为main（）{ int a,b,k=4,m=6,*p1=&k,*p2=&m; a=p1==&m; b=（*p1）/（*p2）+7; printf （"a=%d＼n",a）; printf（"b=%d＼n",b）; }A: -1,5B: 1,6C: 0,7D: 4,10正确答案:(单选题) 6: 请选出以下语句的输出结果printf（"%d＼n",strlen（"＼t＼"＼065＼xff＼n"））;A: 5B: 14C: 8------------------------------------------------------------------------------------------------------------------------------D: 输出项不合法，无正常输出正确答案:(单选题) 7: 函数 rewind 的作用是A: 使文件位置指针重新返回文件的开始位置B: 将文件位置指针指向文件中所要求的特定位置C: 使文件位置指针指向文件的末尾D: 使文件位置指针自动移至下一个字符位置正确答案:(单选题) 8: 以下程序的输出结果是#include "stdio.h"void reverse(int a[],int n){int i,t;for(i=0;i<n/2;i++){t=a[i];a[i]=a[n-1-i];a[n-1-i]=t;}}main(){int b[10]={1,2,3,4,5,6,7,8,9,10};int i,s=0;reverse(b,8);for(i=6;i<10;i++) s+=b[i];printf("%d\n",s);}A: 22B: 10C: 34D: 30正确答案:(单选题) 9: 若已定义: int a［］={0,1,2,3,4,5,6,7,8,9}, *p=a,i; 其中0≤i≤9, 则对a数组元素不正确的引用是A: a［p-a］B: *（&a［i］）C: p［i］D: a［10］正确答案:(单选题) 10: 若有以下程序#include int a［］={2,4,6,8}; main（）{ int i; int *p=a; for（i=0;i<4;i++）a［i］=*p; printf（"%d＼n",a ［2］）; } 上面程序输出结果是A: 6B: 8------------------------------------------------------------------------------------------------------------------------------C: 4D: 2正确答案:(多选题) 1: 内存中供用户使用的存储空间可分为：______。

吉大18春学期《数据结构》在线作业一-0004
通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）A:数据元素具有同一特点
B:不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C:每个数据元素都一样
D:数据元素所包含的数据项的个数要相等
答案：B
链栈与顺序栈相比，有一个比较明显得优点是( )
A:通常不会出现栈满的情况
B:通常不会出现栈空的情况
C:插入操作更加方便
D:删除操作更加方便
答案：A
深度为6的二叉树最多有( )个结点。

A:64
B:63
C:32
D:31
答案：B
设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。

A:k+1
B:2k
C:2k-1
D:2k+1
答案：C
在具有n个单元的循环队列中，队满共有_______个元素。

A:n
B:n-1
C:n+1
D:n+2
答案：B
含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。

A:1
B:n/2
C:n-1
D:n
答案：C
PUSH和POP命令常用于（）操作
A:队列
B:数组
C:栈
D:记录
答案：C
非空的循环单链表head的尾结点(由指针p所指)满足( )。

A:p-&gt;next=NULL
B:p=NULL。

大工17秋《数据结构》在线作业1-0004
试卷总分:100得分:100
一、单选题(共10道试题,共50分)
1.下面关于串的概念的叙述中错误的是()。

（5分）
A.串是字符的有限序列
B.串既可以采用顺序存储，也可以采用链式存储
C.空串是由空格构成的串
D.模式匹配是串的一种重要运算
正确答案:C
2.一个有n个结点的有序单链表中,删除一个结点并仍然使链表有序的时间复杂度是()。

（5分）
A.O(1)
B.O(n)
C.O(n^2)
D.O(nlog2n)
正确答案:B
3.序列{a,b,c,d}顺序进栈,其出栈的顺序不可能为()。

（5分）
A.dcba
B.cdab
C.adcb
D.abcd
正确答案:B
4.以下四种数据结构中()不是线性结构。

（5分）
A.队列
B.线性表
C.栈
D.二叉树
正确答案:D
5.最适合用做链式队列的链表是()。

（5分）
A.带队首指针和队尾指针的循环单链表
B.带队首指针和队尾指针的非循环单链表
C.只带队首指针的非循环单链表
D.只带队首指针的循环单链表
正确答案:B。

大工19秋《数据结构》在线作业1试卷总分:100 得分:100一、单选题(共10 道试题,共50 分)1.线性表采用顺序存储结构时,其地址( )。

A.部分地址必须是连续的B.连续与否均可以C.必须是连续的D.一定是不连续的答案:C2.队列操作的原则是( )。

A.后进先出B.只能插入C.只能删除D.先进先出答案:D3.下述哪一条是顺序存储结构的优点( )。

A.插入运算方便B.存储密度大C.可方便地用于各种逻辑结构的存储表示D.删除运算方便答案:B4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。

A.顺序表B.带头结点的双循环链表C.双链表D.单循环链表答案:A5.链表不具有的特点是( )。

A.插入、删除不需要移动元素B.所需空间与线性长度成正比C.可随机访问任一元素D.不必事先估计存储空间答案:C6.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是( )。

A.不确定B.n-i+1C.n-iD.i答案:B7.设有三个元素X,Y,Z顺序进栈(进的过程中允许出栈),下列得不到的出栈排列是( )。

A.ZYXB.ZXYC.YZXD.XYZ答案:B8.一个递归算法必须包括( )。

A.递归部分B.迭代部分C.终止条件和递归部分D.终止条件和迭代部分答案:C9.设计一个判别表达式中左右括号是否配对出现的算法,采用( )数据结构最佳。

A.队列B.线性表的顺序存储结构C.线性表的链式存储结构D.栈答案:D10.对稀疏矩阵进行压缩存储目的是( )。

A.降低运算的时间复杂度B.节省存储空间C.便于进行矩阵运算D.便于输入和输出答案:B二、判断题(共10 道试题,共50 分)11.数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

答案:正确12.算法的有穷性是指一个算法必须总是(对任何合法的输入)在执行有穷步之后结束,且每一步都可在有穷时间内完成。

数据结构（本）形考作业指导作业1参考答案一、单项选择题1．C 2．D 3．B 4．C 5．D 6．C 7．B 8．C 9．A 10．B11．C 12．D 13．C 14．A 15．B 16．C 17．C 18．B 19．B 20．D二、填空题1．n-i+1 2．n-i3．集合线性结构树形结构图状结构4．物理结构存储结构5．线性结构非线性结构6．有穷性确定性可形性有零个或多个输入有一个或多个输出7．图状结构8．树形结构9．线性结构10．n-1 O(n) 11．s->next=p->next; 12．head13．q->next=p->next; 14．p->next=head; 15．单链表16．顺序存储链式存储17．存储结构18．两个直接后继直接前驱尾结点头结点19．头结点的指针指向第一个结点的指针20．链式链表三、问答题1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。

数据在计算机中的存储表示称为数据的存储结构。

可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。

尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。

采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。

2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。

答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。

优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。

吉大 19年11月《数据结构》作业考核试题总分：100 分一、单选题共 10 题，40 分 1 4 分带头结点的单链表 head 为空的判断条件是()。

Ahead=NULL Bhead->next=NULL Chead->next=head Dhead!=NULL 学生答案：B 2 4 分在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p,q 之间插入s 结点，这执行（）操作。

As->next=p->next;p->next=s Bq->next=s;s->next=p Cp->next=s->next;s->next=p; Dp->next=s;s->next=q; 学生答案：B 3 4 分线性表是具有 n 个（）的有限序列 A 表元素 B 字符 C 数据元素 D 数据项学生答案：C 4 4 分在单链表中，删除p 所指结点的直接后继的操作是( ) Ap->next=p->next->next; Bp=p->next;p->next=p->next->next; Cp->next=p->next; Dp=p->next->next;学生答案：A 5 4 分任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( )。

A 肯定发生变化 B 有时发生变化 C 肯定不发生变化 D 无法确定学生答案：C 64 分在无向图中，所有顶点的度数之和是所有边数的( )倍。

A0.5 B1 C2 D4 学生答案：C 7 4 分单链表中，增加头结点的目的是为了( )。

A 方便运算的实现 B 用于标识单链表 C 使单链表中至少有一个结点D 用于标识起始结点的位置学生答案：A 8 4 分链栈与顺序栈相比，有一个比较明显得优点是( ) A 通常不会出现栈满的情况 B 通常不会出现栈空的情况 C 插入操作更加方便 D 删除操作更加方便学生答案：A 94 分深度为 6 的二叉树最多有( )个结点。

(单选题) 1: 排序趟数与序列的原始状态有关的排序方法是 () 排序法。

A: 直接插入B: 直接选择C: 冒泡D: 归并正确答案:(单选题) 2: 递归过程的实现需用到 ( )。

A: 线性表B: 链表C: 栈D: 队列正确答案:(单选题) 3: 折半查找要求结点 ()。

A: 无序、顺序存储B: 无序、链接存储C: 有序、顺序存储D: 有序、链接存储正确答案:(单选题) 4: 一个有向无环图的拓扑排序序列 () 是唯一的。

A: 一定B: 不一定C: 可能D: 三者均不对正确答案:(单选题) 5: 设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。

A: 求子串B: 求串长C: 联接D: 模式匹配正确答案:(单选题) 6: 下面关于串的叙述中，哪一个是不正确的? ( )A: 串是字符的有限序列B: 空串是由空格构成的串C: 模式匹配是串的一种重要运算D: 串既可以采用顺序存储，也可以采用链式存储正确答案:(单选题) 7: 设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。

A: Ο( 1 )B: Ο(log2n)C: Ο(n)D: Ο(nlog2n)正确答案:(单选题) 8: 在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。

A: 希尔排序B: 插入排序C: 归并排序D: 选择排序正确答案:(单选题) 9: 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是 ( )。

A: UB: VC: XD: Y正确答案:(单选题) 10: 一个有n个结点的图，连通分量的个数最多为 ()。

A: 0B: 1C: n-1D: n正确答案:(单选题) 11: 设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为 ( )。

A: h+1B: 2h-1C: 2hD: 2h+1正确答案:(单选题) 12: 在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。

数据结构作业及答案汇总数据结构是计算机科学中的一个重要概念，它涉及到组织和管理数据的方式和方法。

在学习数据结构的过程中，作业和答案总结是帮助我们巩固知识和理解的重要步骤。

本文将对数据结构作业及答案进行汇总，以便帮助读者更好地学习和掌握数据结构知识。

作业一：栈和队列1. 描述栈和队列的基本特点，并给出它们的应用场景。

栈是一种容器，它具有后进先出（LIFO）的特点。

常见的应用场景有程序调用栈、浏览器的前进后退功能等。

队列是一种容器，它具有先进先出（FIFO）的特点。

常见的应用场景有任务调度、消息队列等。

2. 设计一个栈，使其具有查找最小元素的功能。

给出实现代码和分析时间复杂度。

3. 设计一个队列，使其具有查找最大元素的功能。

给出实现代码和分析时间复杂度。

作业二：链表1. 描述链表的基本特点，并给出它的应用场景。

链表是一种数据结构，它由一系列节点组成。

每个节点包含数据和指向下一节点的指针。

常见的应用场景有实现链表、存储大量数据等。

2. 设计一个单向链表，使其具有反转链表的功能。

给出实现代码和分析时间复杂度。

3. 设计一个双向链表，使其具有插入和删除节点的功能。

给出实现代码和分析时间复杂度。

作业三：树1. 描述树的基本特点，并给出它的应用场景。

树是一种非线性数据结构，它由节点和边组成。

常见的应用场景有文件系统、数据库索引等。

2. 设计一个二叉树，实现遍历功能（前序、中序、后序）。

给出实现代码和分析时间复杂度。

3. 设计一个平衡二叉树，使其具有快速查找节点的功能。

给出实现代码和分析时间复杂度。

作业四：图1. 描述图的基本特点，并给出它的应用场景。

图是一种由顶点和边组成的数据结构，边表示顶点之间的关系。

常见的应用场景有社交网络、地图导航等。

2. 设计一个有向图，实现深度优先搜索（DFS）算法。

给出实现代码和分析时间复杂度。

3. 设计一个无向图，实现广度优先搜索（BFS）算法。

给出实现代码和分析时间复杂度。

答案汇总：在本文中，我们对栈、队列、链表、树和图这几个常见的数据结构进行了作业设计和答案汇总。

吉大15春学期《数据结构与算法》在线
作业一
本文档旨在介绍吉大15春学期《数据结构与算法》课程的在线作业一。

以下是作业的要求和相关内容：
作业要求
- 在线作业一的截止日期是XX月XX日。

- 作业需要在提交截止日期之前完成并提交到指定的平台。

- 作业的评分标准将根据作业的完整性、正确性和代码质量等方面进行评估。

作业内容
在线作业一涵盖以下主题：
1. 数据结构概述
2. 算法分析
3. 线性表
4. 栈和队列
5. 串
学生需要完成以下任务：
1. 阅读教材相关章节，掌握数据结构和算法的基本概念。

2. 完成赋予的编程任务，编写相应的代码实现。

3. 运行和测试编写的代码，确保代码的正确性和稳定性。

4. 将代码提交到指定的平台上，按要求完成作业的提交。

请各位同学按照要求完成作业，并在截止日期前将作业提交。

如有任何疑问，请及时与授课教师联系。

祝各位同学完成作业顺利！
*[简介：本文档介绍了吉大15春学期《数据结构与算法》课程的在线作业一的要求和内容。

作业要求学生在规定时间内完成并提交作业，并按照学校要求进行评估。

学生需要通过阅读教材、编写代码和运行测试来完成作业。

]*。

(单选题) 1: 数据结构是一门研究非数值计算的程序设计问题中,数据元素的（）、数据信息在计算机中的存储结构以及一组相关的运算等的课程。

A: 操作对象B: 计算方法C: 逻辑结构D: 数据映象正确答案:(单选题) 2: 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

A: O(n)B: O(nlog2n)C: O(1)D: O(n2 )正确答案:(单选题) 3: 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。

A: 3B: 4C: 5D: 8正确答案:(单选题) 4: 如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。

A: 起泡排序B: 快速排序C: 简单选择排序D: 堆排序正确答案:(单选题) 5: 下面程序的时间复杂为（） 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(n3)D: O(n4 )正确答案:(单选题) 6: 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。

A: s->next=p;p->next=s;B: s->next=p->next;p->next=s;C: s->next=p->next;p=s;D: p->next=s;s->next=p;正确答案:(单选题) 7: 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。

A: acbedB: decabC: deabcD: cedba正确答案:(单选题) 8: 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。

------------------------------------------------------------------------------------------------------------------------------(单选题) 1:设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A: A，B，C，DB: D，C，B，AC: A，C，D，BD: D，A，B，C正确答案：(单选题) 2:算法的时间复杂度主要取决于A: 问题的规模B: 待处理数据的初态C: 难度D: A和B正确答案：(单选题) 3:文件中，主关键字能唯一标识A: 一个记录B: 一组记录C: 一个类型D: 一个文件正确答案：(单选题) 4:下列程序段 for(i=1;i<=n;i++) A[i,j]=0; 的时间复杂度是A: O(1)B: O(0)C: O(1+n)D: O(n)正确答案：(单选题) 5:二叉树中第5层上的结点个数最多为A: 8B: 15C: 16D: 32正确答案：(单选题) 6:有关二叉树下列说法正确的是A: 二叉树的度为2B: 一棵二叉树的度可以小于2 C: 二叉树中至少有一个结点的度为2D: 二叉树中任何一个结点的度都为2正确答案：(单选题) 7:------------------------------------------------------------------------------------------------------------------------------ 抽象数据类型的三个组成部分分别为A: 数据对象、数据关系和基本操作B: 数据元素、逻辑结构和存储结构C: 数据项、数据元素和数据类型D: 数据元素、数据结构和数据类型正确答案：(单选题) 8:对n个关键字的序列进行快速排序，平均情况下的空间复杂度为A: O(1)B: O(logn)C: O(n)D: O(n logn)正确答案：(单选题) 9:用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为A: 5B: 6C: 8D: 9正确答案：(单选题) 10:十字链表的三元组表是稀疏矩阵的一种A: 顺序存储结构B: 链式存储结构C: 索引存储结构D: 散列存储结构正确答案：(单选题) 11:在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是A: G中有弧<Vi，Vj>B: G中有一条从Vi到Vj的路径C: G中没有弧<Vi,Vj>D: G中有一条从Vj到Vi的路径正确答案：(单选题) 12:如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为A: 插入排序B: 归并排序C: 冒泡排序D: 堆排序正确答案：(单选题) 13:------------------------------------------------------------------------------------------------------------------------------ 在待排关键字序列基本有序的前提下，效率最高的排序方法是A: 直接插入排序B: 快速排序C: 直接选择排序D: 归并排序正确答案：(单选题) 14:下面关于线性表的叙述中，错误的是A: 线性表采用顺序存储，必须占用一片连续的存储单元。

15秋学期《数据结构Ⅰ》在线作业1
试卷总分：100 测试时间：-- 试卷得分：100
一、单选题（共20道试题，共100分。

）
1.
上溢现象通常出现在
A.
顺序栈的入栈操作过程中
B. 顺序栈的出栈操作过程中
C.
链栈的入栈操作过程中
D. 链栈的出栈操作过程中
正确答案：A满分：5分得分：5
2.
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A. 不一定相同
B. 都相同
C. 都不相同
D. 互为逆序
正确答案：B满分：5分得分：5
3.
带行表的三元组表是稀疏矩阵的一种
A. 顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 散列存储结构
正确答案：A满分：5分得分：5
4.
在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A. LL型
B. LR型
C. RL型
D. RR型
正确答案：B满分：5分得分：5
5.
抽象数据类型的三个组成部分分别为
A. 数据对象、数据关系和基本操作。

吉林省专升本考试数据结构分章习题及参考答案———选择题（第一章）1、计算机算法必须具备（）这三个特性。

A、可执行性、可移植性、可扩充性B、可执行性、确定性、有穷性C、确定性、有穷性、稳定性D、易读性、稳定性、安全性2、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A、结构B、关系C、运算D、算法3、具有线性结构的数据结构是（）。

A、图B、树C、广义表D、栈4、设数据结构A=(D, R)，其中D={1, 2, 3, 4}，R={r}, r={<I, 2>, <2, 3>,<3,4>, <4,1>}，则数据结构A是( )。

A、线性结构B、树结构C、图D、集合5、数据结构是指()。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义6、给定有n个元素的向量，建立一个有序单链表的时间复杂度是( )。

A、O(1)）B、O(n)C、O(n2)D、O(n*log2n)7、下列程序段的时间复杂度为（）。

x=n;y=0;while(x>=(y+1)*(y+1))y=y+1;A、O(n)B、O(根号n)C、O(1)D、O(n2)8、计算机算法指的是（）.A、计算方法B、排序方法C、解决问题的步骤序列D、调度方法9、（）是具有相同特性数据元素的集合，是数据的子集。

A、数据符号B、数据对象C、数据D、数据结构10、数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为( )。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构11、算法分析的两个主要方面是：A、空间复杂性和时间复杂性B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性12、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构13、数据结构是一门研究非数值计算的程序设计问题中,数据元素的逻辑结构，数据信息在计算机中的()以及一组相关的运算等的课程。

------------------------------------------------------------------------------------------------------------------------------ (单选题) 1: 主要由于（）原因，使UNIX易于移植。

A: UNIX是由机器指令书写的B: UNIX大部分由汇编少部分用C语言编写C: UNIX是用汇编语言编写的D: UNIX小部分由汇编大部分用C语言编写正确答案:(单选题) 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: 解决不同用户间的文件命名冲突正确答案:(单选题) 7: （）是计算机和用户的交互接口软件。

A: 主存B: 辅存C: 输入输出设备D: CPU正确答案:------------------------------------------------------------------------------------------------------------------------------ (单选题) 8: 如果分时操作系统的时间片一定，那么（），则响应时间越长。

1：38.邻接表的存储结构下图的深度优先遍历类似于二叉树（树）的( )。

1.先序遍历
2.中序遍历
3.后序遍历
4.按层遍历
2：44 下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是( )。

1.归并排序
2.直接插入排序
3.快速排序
4.冒泡排序
3：5.线性表的长度是指（）
1.顺序存储方式下数组所占的空间大小
2.链式存储方式下所有结点占用的空间大小
3.表中的元素个数
4.所能存储的最大的结点个数
4：45．若表r在排序前已按元素键值递增顺序排列，采用( )方法比较次数较少。

1.直接插入排序
2.快速排序
3.归并排序
4.选择排序
5：18.设输入序列为的A,B,C,D,借助一个栈不可以得到的输出序列是( )。

1.A,B,C,D
2.A,C,D,B
3. D,C,B,A
4.D,A,B,C
6：11 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省空间。

1.单链表
2.双链表
3.带头结点的双循环链表
4.单循环链表
7：46 下列四个关键字序列中,( )不是堆。

1. {05,23,16,68,94,72,71,73}
2.{05,16,23,68,94,72,71,73}
3. {05,23,16,73,94,72,71,68}
4.{05,23,16,68,73,71,72,94}。

东北农业大学网络教育学院数据结构作业题（一）一、选择题（每题2分，共20分）1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。

A、O(n)B、O (n/2)C、O (1)D、O (n2)2．带头结点的单链表first为空的判定条件是（）。

A、first == NULL;B、first->link == NULL;C、first->link == first;D、first != NULL;3．在一棵树中，（）没有前驱结点。

A、分支结点B、叶结点C、树根结点D、空结点4．在有向图中每个顶点的度等于该顶点的（）。

A、入度B、出度C、入度与出度之和D、入度与出度之差5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。

A、20B、18C、25D、226．下列程序段的时间复杂度为（）。

s=0；for(i=1；i<n；i++)for(j=1；j<n；j++)s+=i*j；A、O (1)B、O (n)C、O (2n)D、O (n2)7．栈是一种操作受限的线性结构，其操作的主要特征是（）。

A、先进先出B、后进先出C、进优于出D、出优于进8．假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）。

A、(rear-front-1)％nB、(rear-front)％nC、(front-rear+1)％nD、(rear-front+n)％n9．高度为5的完全二叉树中含有的结点数至少为（）。

A、16B、17C、31D、3210．如图所示有向图的一个拓扑序列是( )A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空题（每空1分，共20分）1．n (n﹥0) 个顶点的无向图最多有条边，最少有条边。