数据结构与操作系统Z试卷
《数据结构》部分（90分）
一、简答题（20分，每题5分）
1、请给出四种数据结构基本类型。
答：根据数据元素之间关系的不同特征，通常有下列4类的基本结构：（1）集合。。。
（2）线性结构。。。
（3）树形结构。。。
（4）图状结构或网状结构。。。
2、简述栈和队列的区别。（P44;P58）
区别和联系：
从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。
栈只允许在表的一端进行插入或删除操作，
队列只允许在表的一端进行插入操作、而在另一端进行删除操作。
因而，栈和队列也可以被称作为操作受限的线性表。
3、什么是关键路径？(P183)
在AOE网中，有些活动可以并行地运行，最短完成时间应是从源点到汇点的最长路径长度（指路径上所有权值之和），称这样的路径为关键路径。
4、插入类排序有哪几种？其中，哪些是不稳定的排序算法？(P265)
二、应用题（40分）
1、如果进栈的序列是12345，请给出所有3、4先出栈的序列（3在4之前出栈）。（5分）(P)
【解答】34215，34251，34521
(可以参考下面这个题：
【￥】铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺
序为：1，2，3，4，5，6，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。
【解答】输入序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。
得到325641的过程如下：123顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。
得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。)
2、给出先缀表达式“- + a * b – c d / e f”对应的后缀式，画出其相应的二叉树，并画出该二叉树的中序线索树。（10分）（P129）
3、某带权有向图及它的邻接表如下图所示，试写出它的广度优先搜索序列，并根据克鲁斯卡尔算法，求它的最小生成树。（10分）
广度优先搜索序列:(P167)
A-->B-->C-->D-->E-->F-->G-->H 克鲁斯卡尔算法，求最小生成树:(P173)
4、请写出应填入下列叙述中（ ）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序、冒泡排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。（15分）(必须对算法的具体步骤有详细的了解，认真看看书吧P263) （①）排序的结果为：12，13，15，18，20，60 （②）排序的结果为：13，15，18，12，20，60 （③）排序的结果为：13，15，20，18，12，60
【参考答案】①快速排序 ②冒泡排序 ③直接插入排序 三、算法设计题（30分）
答题要求：
①用自然语言说明所采用算法的思想；
②给出每个算法所需的数据结构定义，并做必要说明；
③用C语言写出对应的算法程序，并做必要的注释。
1、已知有一个单向循环链表，其每个结点中含三个域：prior, data 和next，其中data为数据域，next为指向后继结点的指针域，prior也为指针域，但它的值为空（NULL），试编写算法将此单向循环链表改为双向循环链表，即使prior成为指向前驱结点的指针域。（15分）
2、编写算法，在二叉树中求位于中序序列中第k个位置的结点的值。（15分）(P129)
分析：实际上是在考察中序遍历，然后在中序遍历中加上一个count变量，用来计数以确定是第几个位置。（一下代码参见P131）
TElemType InOrderTraverse(Bitree T, Status( * visit)(TElemType e)){ InitStack(S);
p=T;
Count=0;
While(p|| !StackEmpty(S)){
If(p){
Push(S,p);
p=p->lchild;
}
Else{
Pop(S,p);
If(!visit(p->data))
Return error;
//出栈一个数，统计count加1；
Count++;
If(Count>=k){//当统计个数到了k个时，返回所对应的数。
Return p->data;
}
p=p->rchild;
}
}
}
《操作系统》部分（60分）
四、简答题（每小题6分，共30分）
1、什么是操作系统？操作系统的主要功能有哪些？
操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。
主要功能:
处理机的管理、存储器的管理、设备的管理、文件的管理、接口的管理（参考题目：
什么是操作系统？它有什么基本特征？
答：操作系统是为了达到方便用户和提高资源利用率的目的而设计的，控制和管理计算机硬件和软件资源，合理的组织计算机工作流程的程序的集合，它具有并发、共享、虚拟、异步性四个基本特征。）
2、何谓进程？进程控制块的作用和包含的信息是什么？（P41）
进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位；
进程控制块的作用：使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。
包含的信息：
进程标识符，处理机状态，进程调度信息，进程控制信息
3、产生死锁的必要条件是什么？处理死锁的基本方法有哪些？
必要条件：
(1）互斥条件（2）请求和保持条件
（3）不剥夺条件（4）环路等待条件
基本方法:
（1）预防死锁（2）避免死锁（3）检测死锁（4）解除死锁
4、何谓虚拟存储器？它有哪些特征？（P143）
虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体的说，是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
虚拟存储器的基本特征是：(P144)
多次性，对换性，虚拟性。
（补充：①离散分配，即不必占用连续的内存空间；②部分装入，即每个作业不是全部一次性地装入内存，而是只装入一部分；③多次对换，即所需的全部程序和数据要分成多次调入内存④虚拟扩充，即不是物理上而是逻辑上扩充了内存容量；
另外：虚拟存储器的容量主要受到指令中表示地址的字长和外存的容量的限制。）
5、Spooling系统由几部分组成？它有哪些特征？（P190）
答：Spooling系统由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程共3部分组成。
Spooling系统的特点有：(P191)
（1）提高了I/O速度。I/O操作时针对输入井和输出井，避免了操作低速I/O设备的速度不匹配。
（2）将独占设备改造为共享设备。Spooling系统没有为任何进程实际分配设备，只是在输入井或输出井中为进程分配一个存储区和建立一张I/O请求表。
（3）实现了虚拟设备功能。宏观上有多个进程在同时使用一台独占设备，但对于每一个进程而言，他们认为自己独占了一个设备。
五、算法和计算题（每小题10分，共30分）
1. 使用P、V操作描述读者-写者问题。要求允许几个阅读者可以同时读该数据集，而一个写着不能与其他进程（不管是写者还是读者）同时访问该数据集。（P63）
答：【分析】读者-写者问题是经常出现的一种同步问题。计算机系统中的数据（文件、记录）常被多个进程共享，但其中某些进程可能只
要求读数据（称为Reader），另一些进程则要求修改数据（称为Writer）。就共享数据而言，Reader 和Writer是两种不同类型的进程。一般地，两个或两个以上的Reader 进程同时访问共享数据时不会产生副作用，但若某个Writer和其他进程（Reader或Writer）同时访问共享数据时，则可能产生错误。为了避免错误，同时尽可能地让读者进程和写者进程并发运行，只要保证任何一个写者进程能与其他进程互斥访问共享数据即可。这个问题称为读者-写者问题。
【解答】P 、V 操作是定义在信号量s 上的两条原语，它是解决进程同步与互斥的有效手段。定义下列信号量：互斥信号量rmutex ，初值为1 ，用于使读者互斥地访问读者计数器，共享变量rcount ；互斥信号量wmutex，初值为1 ，用于实现写者之间以及写者与读者之间互斥地访问共享数据集。用信号量和P 、V 操作描述读者-写者问题如下：Begin
rmutex wmutex:semaphore;
rcount:Integer;
rmutex=wmutex=1;
rcount=0;
Cobegin
Process procedure Reader
begin
P(rmutex); // 保护rcount
rcount:=rcount+1
if rcount=l then P(wmutex); // 保证没有writer 在写
V(rmutex);
Perform read operations;
P(rmutex);
rcount:=rcount-1;
if rcount=O then V(wmutex); //没有reader 时，允许writer 写操作
V(rmutex);
end
Process procedure Writer
begin
P(wmutex);
perform write operations;
V(wmutex);
end
Coend
End
2. 假定在某移动臂磁盘上，刚刚访问了75号柱面的请求，目前正在80号柱面读信息，并且有下述请求序列等待访问磁盘：
试用：（1）电梯调度算法；（2）最短寻找时间优先算法，分别列出实际处理上述请求的次序。
（1）3 6 4 1 2 5 8 7
(2) 1 2 5 8 7 3 6 4
(参考题目及解析：
假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请求，目前正在80号柱面上读信息，并有下列请求序列等待访问磁盘：
请求序列： l 2 3 4 5 6 7 8
欲访问的柱面号：160 40 190 188 90 58 32 102
试用(1)电梯调度算法；(2)最短查找时间优先算法，分别排出实际处理上述请求的次序。
答：(1)电梯调度算法是从移动臂当前位置开始，沿臂的移动方向取选择离当前移动
臂最近的柱面访问，如果该方向上没有访问请求，则改变臂的方向再选择。从题中可以看出，先访问的是75柱面，正在访问80柱面。显然移动臂当前的移动方向是从小柱面号到大柱面号。所以采用电梯调度算法，先依次访问的应该是90、102、160、188、190号柱面，之后掉转方向去依次访问58、40、32号柱面。
(2)最短查找时间优先算法每次总是让查找时间最短的请求先执行，不管它是不是先访问的，也不管它在什么方向上。所谓查找时间最短的是指移动臂从当前位置移动要访问的若干个位置中移动距离最短的位置上所花的时间。针对本题，依次先处理的是90、102号柱面后，磁头当前离58号柱面有44个柱面的距离，而离160号柱面有58个柱面的距离，显然要先访问58号柱面，依次下去访问的应该是40、32、160、188、190号柱面。
(1)用电梯调度算法处理次序是5、8、1、4、3、6、2、7。
(2)用最短查找时间优先算法处理的次序5、8、6、2、7、l、4、3。)
3. 在一个单道批处理系统中，一组作业的提交时刻和运行时间如下表所示：
试计算一下三种作业调度算法的平均周转时间T和平均带权周转时间W：（1）先来先服务；（2）短作业优先；（3）响应比高者优先；
解：作业I 的周转时间Ti ＝作业I 的提交时间－作业I 的完成时间
＝作业I 的运行时间＋作业I 的等待时间
作业I 的带权周转时间Wi＝Ti / 作业I 的运行时间
作业I 的平均周转时间T ＝ 1 / n * ∑Ti ，
作业I 的平均带权周转时间W ＝1 / n * ∑Wi
（1）采用先来先服务（FCFS）调度算法的运行情况如下表所示：
先来先服务算法下的作业运行情况表
山东大学数据库实验答案2—8 CREATE TABLE test2_01 AS SELECT SID, NAME FROM pub.STUDENT WHERE sid NOT IN ( SELECT sid FROM pub.STUDENT_COURSE ) CREATE TABLE test2_02 AS SELECT SID, NAME FROM PUB.STUDENT WHERE SID IN ( SELECT DISTINCT SID FROM PUB.STUDENT_COURSE WHERE CID IN ( SELECT CID FROM PUB.STUDENT_COURSE WHERE SID='200900130417' ) ) CREATE TABLE test2_03 AS
select SID,NAME from PUB.STUDENT where SID in ( select distinct SID from PUB.STUDENT_COURSE where CID in (select CID from PUB.COURSE where FCID='300002') ) CREATE TABLE test2_04 AS select SID,NAME from PUB.STUDENT where SID in ( select distinct SID from PUB.STUDENT_COURSE where CID in (select CID from PUB.COURSE where NAME='操作系统') intersect select distinct SID from PUB.STUDENT_COURSE where CID in (select CID from PUB.COURSE where NAME='数据结构') ) create table test2_05 as with valid_stu(sid,name) as ( select SID,NAME from PUB.STUDENT where AGE=20 and SID in (select SID from PUB.STUDENT_COURSE) ) select sid,name as name,ROUND(avg(score)) as avg_score,sum(score) as sum_score from PUB.STUDENT_COURSE natural join valid_stu where SID in (select SID from valid_stu) group by SID,NAME create table test2_06 as
1.二分搜索一个14个数的数组，查找A[4]所经过的元素有____. 2.一个序列先入栈，再出栈，出栈元素加入队列，生成一个新的顺序（已给出），则栈结构最少需要能保存几个元素_______. 3.一个5000个元素的数据需要排序，在堆排序，基数排序，快速排序里，要求速度最快，选哪一个______. 4.n个结点的m序B树，有____个外部节点。一个5序B树有53个结点，该B树至少有___ 层。 5.已给出一个K=11的散列表已有三个元素，再插入两个元素，则这两个元素的位置是________. 6.已给出一个无序数组，选第一个元素作为基点，快排一趟之后的顺序为____________________. 7.一个图已给3条边，再添加一条边，使其有唯一的拓扑序列，添加的边是_______,拓扑序列为____________. 8已给出一个序列，初始化为最小堆____________________。 1.跳表和散列，分别搜索最小元素写出思想和时间复杂度。 2.已给出一个序列，写出建立A VL树的过程，及删除某一个元素后的结果。 3.已给出一个有向图，写出对应的邻接表，根据Dijkstra算法写出某个顶点到其余各顶点的最短路径。 4.已给出一颗公式化描述的二叉树，画出二叉树并写出前中后序列及转化成森林。 5.无向图用公式化描述，为简化，用数组M表示上三角矩阵。写出A[i,j]到M的映射关系，说明如何求任意顶点i的度。 6.6个有序的序列，20 30 40 60 70 100 通过5次两两合并，生成一个有序的序列，求最少次数的合并过程。 1.删除链表形式的二叉搜索树的最大元素，写出思想，算法实现，时间复杂度。 2.邻接链表表示的图写出算法判断是否存在V->U的路径，以及思想。
1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2)
数据库实验（一） 熟悉环境、建立/删除表、插入数据 Drop table 表名 update dbtest set test=1 select * from dbscore 1．教师信息(教师编号、姓名、性别、年龄、院系名称) test1_teacher：tid char 6 not null、name varchar 10 not null、sex char 2、age int、dname varchar 10。 根据教师名称建立一个索引。 1、create table test1_teacher( tid char(6) primary key, name varchar(10) not null, sex char(2), age int, dname varchar(10) ) 2．学生信息（学生编号、姓名、性别、年龄、出生日期、院系名称、班级）test1_student：sid char 12 not null、name varchar 10 not null、sex char 2、age int、birthday date（oracle的date类型是包含时间信息的，时间信息全部为零）、dname varchar 10、class varchar(10)。 根据姓名建立一个索引。 2、create table test1_student(
sid char(12) primary key, name varchar(10) not null, sex char(2), age int, birthday date, dname varchar(10), class varchar(10) ) 3．课程信息（课程编号、课程名称、先行课编号、学分） test1_course：cid char 6 not null、name varchar 10 not null、fcid char 6、credit numeric 2，1（其中2代表总长度，1代表小数点后面长度）。 根据课程名建立一个索引。 3、create table test1_course( cid char(6) primary key, name varchar(10) not null, fcid char(6), credit numeric(2,1) ) 4．学生选课信息（学号、课程号、成绩、教师编号） test1_student_course：sid char 12 not null、cid char 6 not null、 score numeric 5，1（其中5代表总长度，1代表小数点后面长度）、tid char 6。 4、 create table test1_student_course( sid char(12) , cid char(6) , score numeric(5,1), tid char(6), primary key(sid,cid),
《数据结构》模拟卷 一、选择题 1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（A ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 2.带头结点的单链表first为空的判定条件是：（B ）。 A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 3. 从逻辑上可以把数据结构分为（C ）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为 对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ D ），在被调用程序中可直接操纵实际参数。 A. 空间 B. 副本 C. 返回地址 D. 地址 5. 以下数据结构中，哪一个是线性结构（D ）。 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 6. 以下属于逻辑结构的是（C ）。 A．顺序表 B. 哈希表 C.有序表 D. 单链表 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长 度为（ C ）的值除以9。 A. 20 B. 18 C. 25 D. 22 8.在有向图中每个顶点的度等于该顶点的（ C ）。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差 9.在基于排序码比较的排序算法中，（ C ）算法的最坏情况下的时间复杂度不高于
O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 10.当α的值较小时，散列存储通常比其他存储方式具有（ B ）的查找速度。 A. 较慢 B. 较快 C. 相同 D.不同 二、填空题 1.二维数组是一种非线性结构，其中的每一个数组元素最多有___2___个直接前驱（或直 接后继）。 2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中， A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_「(K+1)／3」_行的元素。 3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_指针__域的值。 4.在一个链式栈中，若栈顶指针等于NULL则为__空栈__。 5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用， 它们都需要利用栈保存调用后的__返回___地址。 6.在一棵树中，_叶子_结点没有后继结点。 7.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为__3__。假定 根结点的层数为0。 8.在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差 的绝对值不超过__1____。 9.n (n﹥0) 个顶点的无向图最多有_n（n-1）/2__条边，最少有___0___条边。 10.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_ 稠密_索引，若对应数据对象表中的若干个表项，则称此索引为__稀疏__索引。 三、判断题 1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的(对) 2.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间 的逻辑顺序(错) 3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针(对)
山东大学操作系统实验报告4进程同步实验
计算机科学与技术学院实验报告 实验题目：实验四、进程同步实验学号： 日期：20120409 班级：计基地12 姓名： 实验目的： 加深对并发协作进程同步与互斥概念的理解，观察和体验并发进程同步与互斥 操作的效果，分析与研究经典进程同步与互斥问题的实际解决方案。了解 Linux 系统中 IPC 进程同步工具的用法，练习并发协作进程的同步与互斥操作的编程与调试技术。 实验内容： 抽烟者问题。假设一个系统中有三个抽烟者进程，每个抽烟者不断地卷烟并抽烟。抽烟者卷起并抽掉一颗烟需要有三种材料：烟草、纸和胶水。一个抽烟者有烟草，一个有纸，另一个有胶水。系统中还有两个供应者进程，它们无限地供应所有三种材料，但每次仅轮流提供三种材料中的两种。得到缺失的两种材料的抽烟者在卷起并抽掉一颗烟后会发信号通知供应者，让它继续提供另外的两种材料。这一过程重复进行。请用以上介绍的 IPC 同步机制编程，实现该问题要求的功能。 硬件环境： 处理器：Intel? Core?i3-2350M CPU @ 2.30GHz ×4 图形：Intel? Sandybridge Mobile x86/MMX/SSE2 内存：4G 操作系统：32位 磁盘：20.1 GB 软件环境： ubuntu13.04 实验步骤： （1）新建定义了producer和consumer共用的IPC函数原型和变量的ipc.h文件。
（2）新建ipc.c文件，编写producer和consumer 共用的IPC的具体相应函数。 （3）新建Producer文件，首先定义producer 的一些行为，利用系统调用，建立共享内存区域，设定其长度并获取共享内存的首地址。然后设定生产者互斥与同步的信号灯，并为他们设置相应的初值。当有生产者进程在运行而其他生产者请求时，相应的信号灯就会阻止他，当共享内存区域已满时，信号等也会提示生产者不能再往共享内存中放入内容。 （4）新建Consumer文件，定义consumer的一些行为，利用系统调用来创建共享内存区域，并设定他的长度并获取共享内存的首地址。然后设定消费者互斥与同步的信号灯，并为他们设置相应的初值。当有消费进程在运行而其他消费者请求时，相应的信号灯就会阻止它，当共享内存区域已空时，信号等也会提示生产者不能再从共享内存中取出相应的内容。 运行的消费者应该与相应的生产者对应起来，只有这样运行结果才会正确。
数据结构考试复习题集团档案编码：[YTTR-YTPT28-YTNTL98-UYTYNN08]
复习题集 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机内部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据]（×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的内存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表]
山大网络教育《数据结构》(-C-卷)
《数据结构》模拟卷 一、单项选择题 1．数据结构是（）。 A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．算法分析的目的是（ B ）。 A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 3．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（ D ）。 A．插入B．删除 C．排序D．定位 4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ B ）。 A．3，2，6，1，4，5 B．3，4，2，1，6，5
C．1，2，5，3，4，6 D．5，6，4，2，3，1 5．设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ D ）。 A．15 B．16 C．17 D．18 6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ A ）。 A．1207 B．1209 C．1211 D．1213 7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ A ）。 A．队列B．栈 C．线性表D．有序表 8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ B ）。A．不一定相同B．都相同 C．都不相同D．互为逆序 9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ C ）。
1.以下与数据的存储结构无关的术语是（c ） C、哈希表 2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B ） B、108 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（C） C、head–>next= =head 4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ D ） D、2，3，5，1，6，4 5.下列关键字序列中，构成小根堆的是（ A ） A、{12，21，49，33，81，56，69，41} 6.下列数据结构中，不属于二叉树的是（ A ） A、B树 7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（ C ）。 C、A[2i+1] 8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ D ） D、 8 9.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下 面哪个序列输入（ B ） B、37，24，12，30，53，45，96 10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） C、5，1，6，3，4，2 11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B ) B、[m/2]-1 12.散列文件也称为( C ) B 、索引文件 13.数据结构是（D ） D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（C ） C、线性结构和树型结构 15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示
软件学院操作系统实验报告 实验题目： 实验二、线程和进程/线程管道通信实验 学号：201100300124 日期：2013年04月19日 班级：5班姓名：韩俊晓 Email：hanjunxiao188@https://www.doczj.com/doc/d917986968.html, 实验目的： 通过Linux 系统中线程和管道通信机制的实验,加深对于线程控制和管道通信概念的理解,观察和体验并发进/线程间的通信和协作的效果,练习利用无名管道进行进/线程间通信的编程和调试技术。 实验要求： 设有二元函数f(x,y) = f(x) + f(y) 其中：f(x) = f(x-1) * x(x >1) f(x)=1(x=1) f(y) = f(y-1) + f(y-2)(y> 2) f(y)=1(y=1,2) 请编程建立3个并发协作进程（或线程），它们分别完成f(x,y)、f(x)、f(y) 其中由父进程（或主线程）完成：f(x,y) = f(x) + f(y) 由子进程1（或线程1）完成：f(x) = f(x-1) * x(x >1) f(x)=1(x=1)
由子进程2（或线程2）完成：f(y) = f(y-1) + f(y-2)(y> 2) f(y)=1(y=1,2) 硬件环境： 实验室计算机 软件环境： Ubuntu08.4－Linux操作系统 BASH_VERSION='3.2.33(1)-release gcc version 4.1.2 gedit 2.18.2 OpenOffice 2.3 实验步骤： 1.实验说明： 1）与线程创建、执行有关的系统调用说明 线程是在共享内存中并发执行的多道执行路径,它们共享一个进程的资源,如进程程序段、文件描述符和信号等,但有各自的执行路径和堆栈。线程的创建无需像进程那样重新申请系统资源,线程在上下文切换时也无需像进程那样更换内存映像。多线程的并发执行即避免了多进程并发的上下文切换的开销又可以提高并发处理的效率。 Linux 利用了特有的内核函数__clone 实现了一个叫phread 的线程库,__clone是fork 函数的替代函数,通过更多的控制父子进程共享哪些资源而实现了线程。Pthread 是一个标准化模型,用它可把一个程序分成一组能够并发执行的多个任务。phread 线程库是POSIX 线程标
2012年贵州大学数据结构复习题及答案 1、下面程序的时间复杂度为___C_ 。 for(i=0;i< m;i++) for(j=0;j< n;j++) A[i][j]=i*j; (A). O(m2) (B). O(n2) (C). O(m*n) (D). O(m+n) 2、在数据结构中，从逻辑上可以把数据结构分成__C__ 。 (A). 动态存储结构和静态存储结构 (B). 紧凑结构和非紧凑结 (C). 线形结构和非线性结构 (D). 内部结构和外部结构 3、下面程序的时间复杂度为__A__ 。 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) 4、下面程序的时间复杂度为__D__ 。 i=1；while(i<=n) i=i*5; (A). O(1) (B). O(n) (C). O(5*n) (D). O(log5n) 5、算法指的是_D__ 。 (A). 计算机程序 (B). 解决问题的步骤 (C). 排序算法 (D). 解决问题的有限运算序列 6、某程序的时间复杂度为（3n+nlog2n+n2+8），其数量级表示为 C (A). O(n) (B). O(nlog2n) (C). O(n2)
(D). O(log2n) 7、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的__B____和运算的科学。 (A). 结构 (B). 关系 (C). 运算 (D). 算法 8、算法分析的目的是__C____。 (A). 找出算法的合理性 (B). 研究算法的输入/输出关系 (C). 分析算法的有效性以求改进 (D). 分析算法的易懂性 9、数据的基本单位是____B____。 (A). 数据 (B). 数据元素 (C). 数据项 (D). 结构体 10、与数据元素本身的形式、内存、相对位置、个数无关的是数据的____B_。 (A). 存储结构 (B). 逻辑结构 (C). 算法 (D). 操作 11、数据逻辑结构在计算机里的实现是___________A_______. (A). 存储结构 (B). 逻辑结构 (C). 算法 (D). 操作 1、在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需要向前移动__A____个元素。 (A). n-i (B). n-i+1 (C). n-i-1 (D). i+1 2、线性表采用链式存储时，其地址___D_____。 (A). 必须是连续的 (B). 一定是不连续的
青岛大学2005年硕士研究生入学考试试题 学科代码：407 科目名称：数据结构（共4页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效 一．单项选择题（本大题共10道小道小题，每小题3分，共30分） 1. 算法的时间复杂度取决于【】 A. 问题的规模 B. 待处理数据的初始状态 C. 软件和硬件的组合 D. 操作系统 2. 向一个栈顶指针为top的链栈中插入一个s结点，则执行【】 A. top->next=s; B. s->next=top->next; top->next=s; C. s->next=top; top=s; D. s->next=top; top=top->next; 3. 广义表（（a））的表头是【】 A. a B. (a) C. () D. ((a)) 4. 由带权为8、2、5、7的叶子结点构造一棵哈夫曼树，该树的带权路径长度为【】 A. 37 B. 32 C. 46 D. 43 5. 采用邻接表存储的图，其BFS算法类似于二叉树的【】 A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层遍历 6. 在非空m阶B_树上，除根结点之外的所有其他非终端结点【】 A. 至少有??2/m棵子树 B.至多有??2/m棵子树 C. 至少有??2/m棵子树 D. 至多有??2/m棵子树 7. 对线性表进行顺序查找时，要求线性表的存储结构为【】 A. 散列存储 B. 顺序存储或者链式存储 C. 压缩存储 D. 索引存储 8. 在关键字“基本有序”的情况下，最佳排序算法为【】 A. 快速排序 B. 冒泡排序 C. 直接插入排序 D. 基数排序 9. 折半查找法和二叉排序树的时间性能【】 A. 与处理数据量有关 B. 相同 C. 不相同 D. 不确定 10. 串是一种特殊的线性表，其特殊性体现在【】 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 二、填空题（本大题共10小题，每小题2分，共20分） 1. 在具有n个单元的循环队列中，队满时共有____________个元素。 2. 单链表中设置头结点的目的是____________。 3. 消除递归_____________需要使用栈。 4. 在具有n(n≥1)个结点的k叉树中，有_____________个空指针。 5. 深度为5的二叉树至多有_________个结点。 6. 一个连通图的__________是一个极小连通子图。 7. 对稀疏图进行DFS遍历时，应该采用___________作为其存储结构。 8. 在哈希表中，装填因子α越大，则_______________________。
第一章作业 第章作 试编个递归数来输个素的 5. 试编写一个递归函数，用来输出n 个元素的 所有子集。例如，三个元素{a, b, c} 的所有子集是：{ }（空集），{a}, {b}, {c}, {a, b}, {a, c}, {,}{,,} b, c} 和a, b, c。
基本思想： 用一个一维数组x[1:n]表示大小为n的数组的一个子集。 如果第j个元素包含在子集中，那么x[j]=1 ，否则x[j]=0； x[j]0 例如原数组为{a,b},那么他的子集为{0，0}，{0，1}，{1，0}，{1，1}。分别对应子集{?}，{}{}{} {b},{a},{a,b}．
函数实现： #include 一、选择题。(每小题2分，共40分) (1) 计算机识别.存储和加工处理的对象被统称为____A____。 A.数据 B.数据元素 C.数据结构 D.数据类型 (2) 数据结构通常是研究数据的____ A _____及它们之间的联系。 A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 (3) 不是数据的逻辑结构是____ A ______。 A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为 山东大学操作系统实验 六 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 软件学院操作系统实验报告 实验题目： 实验六、死锁问题实验 学号：0124 日期：2013年05月23日 班级：5班姓名：韩俊晓 Email： 实验目的： 通过本实验观察死锁产生的现象，考虑解决死锁问题的方法。从而进一步加深对于死锁问题的理解。掌握解决死锁问题的几种算法的编程和调试技术。练习怎样构造管程和条件变量，利用管程机制来避免死锁和饥俄问题的发生。 实验要求： 在两个城市南北方向之间存在一条铁路，多列火车可以分别从两个城市的车站排队等待进入车道向对方城市行驶，该铁路在同一时间，只能允许在同一方向上行车，如果同时有相向的火车行驶将会撞车。请模拟实现两个方向行车，而不会出现撞车或长时间等待的情况。您能构造一个管程来解决这个问题吗？ 硬件环境： 实验室计算机 软件环境： －Linux操作系统 gcc version 实验步骤： 1.实验说明： 管程-Monitor 管程是一种高级抽象数据类型，它支持在它的函数中隐含互斥操作。结合条件变量和其他一些低级通信原语，管程可以解决许多仅用低级原语不能解决的同步问题。利用管程可以提供一个不会发生死锁或饥饿现象的对象;哲学家就餐问题和Java语言中的synchronized对象都是很好的管程的例子. 管程封装了并发进程或线程要互斥执行的函数。为了让这些并发进程或线程在管程内互斥的执行，进入管程的进/线程必须获取到管程锁或二值信号量 条件变量Condition Variables 条件变量提供了一种对管程内并发协作进程的同步机制。如果没有条件变量，管程就不会有很有用。多数同步问题要求在管程中说明条件变量。条件变量代表了管程中一些并发进程或线程可能要等待的条件。一个条件变量管理着管程内的一个等待队列。如果管程内某个进程或线程发现其执行条件为假，则该进程或线程就会被条件变量挂入管程内等待该条件的队列。如果管程内另外的进程或线程满足了这个条件，则它会通过条件变量再次唤醒等待该条件的进程或线程，从而避免了死锁的产生。所以，一个条件变量C应具有两种操作()和()。 当管程内同时出现唤醒者和被唤醒者时，由于要求管程内的进程或线程必须互斥执行，因此就出现了两种样式的条件变量： 青岛大学2017年硕士研究生入学考试试题 科目代码：910 科目名称：数据结构（共5 页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效 一、单项选择题（本大题共10 道小题，每小题 2 分，共20 分） 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．以上都不对 7．由带权为{8，2，5，7}的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。 A．23 B．37 C．46 D 43 8．若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。 A．非连通B．连通C．强连通D．有向 9．适用于折半查找的表的存储方式及元素排列要求为（）。 A．链接方式存储，元素无序B．链接方式存储，元素有序 C．顺序方式存储，元素无序D．顺序方式存储，元素有序 10．对n 个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。A．O(n) B．O(n2) C．O(nlog2n) D．O(n3) 二、简答题（本大题共 6 道小题，每题5 分，共30 分） 1．如果有n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？ 2．有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D 最先出栈（即 C 第一个且 D 第二个出栈）的次序有哪几个？3．简述树与二叉树的转化方法。试举一个例子说明。 4．简要说明图的各种遍历方法。 5．简述顺序查找和折半查找的优缺点。 6．简要说明归并排序的基本思想。 三、综合应用题（本大题共 4 道小题，每题12 分，共48 分） 1．已知一棵二叉树的中序遍历序列为BCAFEC，后序遍历序列为CBECFA，试画出该二叉树，并给出该二叉树的先序序列。 2．对于下图所示的有向图，试给出： (1)邻接表； (2)从顶点v1 出发的深度优先遍历序列； (3)从顶点v3 出发的广度优先遍历序到。 3．设将关键字集合Keys=｛2, 6, 7, 5, 4, 3, 1｝中的元素依次插入到一个空的平衡二叉排序树中，画出所得的平衡二叉排序树。假设查找每一个元素的概率相同，查找此平衡二叉树排序中任一结点的平均查找长度为多少？ 4．某设待排序的关键字集合为{12，2，16，30，28，10，16*，20，6，18}，试分别回答下面的问题。 ①给出希尔排序（增量选取5，3，1）的结果； 、选择题。 (每小题 2 分，共 40分) (1) 计算机识别 . 存储和加工处理的对象被统称为 _______ A A. 数据 B. 数据元素 C. 数据结构 D. 数据类型 ⑷ 数据结构被形式地定义为 ＜D,R ＞,其中D 是 ____ B _____ 的有限集，R 是 _____ C _____ 的有限集。 A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 (5) 组成数据的基本单位是 ______ A _____ 。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 ⑹ 设数据结构 A=(D ，R)，其中 D={1，2，3，4}，R={r}，r={＜1，2＞，＜2，3＞，＜3，4＞，＜4，1＞}，则数据结构 A 是 _____ A ____ 。 A. 线性结构 B. 树型结构 C. 图型结构 D. 集合 (7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为 ___ C A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构 (8) 在数据结构的讨论中把数据结构从逻辑上分为 ___ A A. 内部结构与外部结构 C.线性结构与非线性结构 (9) 对一个算法的评价，不包括如下 A. 健壮性和可读性 B. C. 正确性 D. (10) 算法分析的两个方面是 __ A A. 空间复杂性和时间复杂性 C. 可读性和文档性 D. (11) 线性表是具有 n 个___ C ___ A. 表元素 C. 数据元素 (12) 线性表的存储结构是一种 _____ B __ 的存储结构。 A. 随机存取 B. 顺序存取 (2) 数据结构通常是研究数据的 及它们之间的联系。 A. 存储和逻辑结构 B. 存储和抽象 C.理想和抽象 D. 理想与逻辑 (3) 不是数据的逻辑结构是 A. 散列结构 B. 线性结构 C. 树结构 D. 图结构 B. 静态结构与动态结构 D. 紧凑结构与非紧凑结构 ___ B _____ 方面的内容。 并行性 时空复杂度 __。 B. 正确性和简明性 数据复杂性和程序复杂性 的有限序列(n z 0) B.字符 D. 数据项 硕士入学考试大纲 考试科目代码及名称：910数据结构 一、考试要求 1、掌握数据结构的基本概念、基本原理和基本方法。 2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。 二、考试内容 一、线性表 (一) 线性表的定义和基本操作 (二) 线性表的实现 1、顺序存储 2、链式存储 3、线性表的应用 二、栈、队列和数组 (一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 特殊矩阵的压缩存储 三、树与二叉树 (一) 树的基本概念 (二) 二叉树 1、二叉树的定义及其主要特征 2、二叉树的顺序存储结构和链式存储结构 3、二叉树的遍历 4、线索二叉树的基本概念和构造 (三) 树、森林 1、树的存储结构 2、森林与二叉树的转换 3、树和森林的遍历 (四) 树与二叉树的应用 1、二叉排序树 2、平衡二叉树 3、哈夫曼(Huffman) 树和哈夫曼编码 四、图 (一) 图的基本概念 (二) 图的存储及基本操作 1、邻接矩阵法 2、邻接表法 3、邻接多重表、十字链表 (三) 图的遍历 1、深度优先搜索 2、广度优先搜索 (四) 图的基本应用 1、最小(代价) 生成树 2、最短路径 3、拓扑排序 4、关键路径 五、查找 (一) 查找的基本概念 (二) 顺序查找法 (三) 分块查找法 (四) 折半查找法 (五) B-树及其基本操作、B+树的基本概念 (六) 散列(Hash) 表 (七) 字符串模式匹配 (八) 查找算法的分析及应用 六、排序 (一) 排序的基本概念 (二) 插入排序 1、直接插入排序 2、折半插入排序 (三) 冒泡排序(Bubble Sort)数据结构复习题及答案(12级).
山东大学操作系统实验六完整版
青岛大学910数据结构
数据结构复习题及答案(12级)
青岛大学2020年910数据结构考试大纲
相关主题
文本预览