浙江理工大学991数据结构2018年考研真题

2018年全国硕士研究生入学统一考试计算机学科专业基础综合试卷一、单项选择题：140小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

b5E2RGbCAP 1．已知程序如下：ints(int n>{ return (n<=0> ? 0 : s(n-1> +n。

}void main(>{ cout<< s(1>。

}程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main(>->S(1>->S(0> B．S(0>->S(1>->main(>p1EanqFDPwC．main(>->S(0>->S(1> D．S(1>->S(0>->main(>DXDiTa9E3d【参考答案】 D【考查知识点】栈的基本概念和函数调用的原理。

2．先序序列为a,b,c,d的不同二叉树的个数是A．13B．14C．15D．16【参考答案】 C【考查知识点】二叉树的基本概念。

3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和 24，10，7B．24，10，5和24，12，7C．24，10，10和 24，14，11 D．24，10，5和 24，14，6【参考答案】 C【考查知识点】哈夫曼树的原理。

4．现在有一颗无重复关键字的平衡二叉树<AVL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是RTCrpUDGiTA．根节点的度一定为2B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树【参考答案】 B【考查知识点】树的中序遍历和AVL树的基本概念。

5．设有向图G=(V,E>，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是5PCzVD7HxAA．2 B．3 C．4 D．5【参考答案】 D【考查知识点】图的深度优先遍历。

模拟试卷二参考答案一、单选题（每题2分，共20分）1．B 2．B 3．A 4．C 5．D 6．A 7．C 8．C 9．D 10．D二、填空题（每空1分，共26分） 1.集合结构 线性结构 树结构 图结构 2. O(n) 3.O(1) O(1) 4.7 2 25. 94 3 X Y * + 2 Y * 3 / -6. 16 317.孩子（或子）结点 双亲（或父）结点 8. 45 n(n-1)9.（12，36） （17,5,49） （74，82） （63） 10.减少1（或减少） 11. O(log 2n) O(nlog 2n) 12. n/m三、 运算题（每题6分，共24分） 1．线性表为：（90，40，78，50，34，60）2． 当前序序列为ABKCDFGHIJ ，中序序列为KBCDAFHIGJ 时，逐步形成二叉树的过程如下图4所示：图4 3．用克鲁斯卡尔算法得到的最小生成树为：(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 4．见图5。

图5四、 阅读算法（每题7分，共14分） 1． (1) La=(26,34,57,79,100)(2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 2．前序遍历链式存储的二叉树。

五、算法填空（每空2分，共8 分）(low<=high) K==A[mid].key Binsch(A,mid+1,hight,K) return -1六、编写算法（8分）bool Find(LNode* HL, ElemType &item) {LNode* p=HL; while pif (p->data==item){ return true; }else p=p->next; return false; }。

模拟试卷四参考答案一、单选题（每题2分，共20分）1.B2.C3.A4.B5.B6.C7.A8.C9.C 10.B二、填空题（每空1分，共26分）1.联系树（或树结构）2.单（子）表3.O(n) O(1)4.p->next=HS;HS=p HS=HS->next5.先进后出先进先出6.行列7.k-18. 2.6259.邻接矩阵邻接表边集数组10.2 111.O(n) O(nlog2n) O(n)12.哈夫曼树带权路径长度13.稠密稀疏三、运算题（每题6分，共24分）1.(1) 3 X * Y 2 H *- / 1 +（2） 2 X Y 3 + * +2. 先序：a,b,c,d,e,f；中序：c,b,a,e,d,f后序：c,b,e,f,d,a；按层：a,b,d,c,e,f 3.（1）该图的图形如图9示：（2）深度优先遍历序列为：abdce广度优先遍历序列为：abedc4.普里姆：(0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20图9四、阅读算法（每题7分，共14分）1.15 22 8 5 2 102.该函数的功能是：求：akm m nn makm m m nakm m akm m n m n (,)(,),(,(,)),=+=-≠=--≠≠⎧⎨⎪⎩⎪1011001100当时当时当时五、算法填空（共8分，每一空2分）BST->data left right false六、编写算法（8分）递归算法：int halfsearch(SSTable *a, KeyType k,int low,int high){if (low>high)return 0;else{int mid=(low+high)/2if EQ(k,a[mid].key) return mid;else if LT(k,a[mid].key) return halfsearch(a,k,low,mid-1);else return halfsearch(a,k,mid+1,high);}}。

浙江理工大学二O一二年‎硕士学位研‎究生招生入‎学考试试题‎考试科目：数据结构代码：991 （请考生在答‎题纸上答题‎，在此试题纸‎上答题无效‎）一、单选题(每题2分，共20分)1. 不带头结点‎的单链表s‎i mple‎L ist为‎空的判定条‎件是。

A. simpl‎e List‎== nullB. simpl‎e List‎->next == nullC. simpl‎e List‎->next = simpl‎e List‎D. simpl‎e List‎! = null2. 某线性表最‎常用的操作‎是在最后一‎个结点之后‎插入一个结‎点或删除第‎一个结点，故采用__‎_____‎_____‎___存储‎方式最节省‎运算时间。

A. 单链表B. 仅有头结点‎的单循环链‎表C. 双链表D. 仅有尾指针‎的单循环链‎表3. 向一个栈顶‎指针为to‎p的链栈中‎插入一个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;4. 一维数组和‎线性表的区‎别是___‎_____‎_____‎。

A. 前者长度固‎定，后者长度可‎变B. 后者长度固‎定，前者长度可‎变C. 两者长度均‎固定D. 两者长度均‎可变5. 设矩阵A是‎一个对称矩‎阵，为了节省存‎储，将其下三角‎部分按行序‎存放在一维‎数),在一组数组‎B的下标位‎置组B[1, n(n-1)/2]中，对任一下三‎角部分中任‎一元素ai‎j(i jK的值是‎_____‎_。

A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j6.在线索化二‎叉树中，P所指的结‎点没有左子‎树的充要条‎件是___‎_____‎_____‎_____‎_____‎。

浙江理工大学2018年《913设计艺术理论Ⅰ》考研专业课真题试卷参考答案浙江理工大学2018年硕士研究生招生考试初试试题考试科目：设计艺术理论１参考答案一、填空题：1.宋2.通过工具、火和语言的使用以及他的艺术3.道德，价值，审美4.关注生态环境的（答案选自：使设计从关注人与物的关系转向关注人与环境及环境自身的存在，出现了关注生态环境的设计思想和设计潮流）5.密斯·凡·德·罗，西格莱姆大厦6.计成，园冶7.艺术，科技8.直觉设计阶段；经验设计阶段；现代设计阶段9.法国，新艺术运动10.传统艺术，高新技术，传统与现代双轨并行（或：双规并行）11.亨利·德雷夫斯，《人体度量》12.功能性废止，款式性废止，质量性废止13.1853年乘客电梯的发明，1890年钢筋结构的完善14.生活方式，文化，情感二、名词解释：1.①完整的建筑物是视觉艺术的最终目的。

②建筑家、雕塑家、画家都应把目光转向应用艺术。

③艺术家与工艺技术人员没有根本上区别。

④将建筑、雕塑、绘画结合成三位一体。

2.非物质主义设计是以信息社会是一个“提供服务和非物质产品的社会”为前提，以“非物质”这个概念来表述未来设计发展的总趋势：即从物的设计转变为非物质的设计、从产品的设计转变为服务的设计、从占有产品转变为共享服务。

非物质主义不拘泥于特定的技术、材料，而是对人类生活和消费方式进行重新规划，在更高层次上理解产品和服务，突破传统设计的作用领域去研究“人与非物”的关系，力图以更少的资源消耗和物质产出保证生活质量，达到可持续发展的目的。

3.思维是人们头脑对自然界事物的本质属性琢其内在联系的间接的、概括的反映；而设计则是通过改变自然物的性质，形成为人所用的物品。

人借助于思维将自己的本质力量对象化，因此设计与思维在设计的过程中是一个完整的概念，"设计"是前提，限定了的思维的范畴，"思维"是手段，借助于各种表现形式，最终形成设计产品。

浙江省2018年1月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

每小题2分，共38分)1.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( )的二叉树。

A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子2.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是( )A.堆排序B.冒泡排序C.直接选择排序D.快速排序3.下列排序算法中，( )算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

A.堆排序B.冒泡排序C.快速排序D.SHELL排序4.一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( )A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 25.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为( )A. r-fB. r-f+1C. (r-f) mod n+1D. (r-f+n) mod n6.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。

A.单链表B.双链表C.带头结点的双循环链表D.单循环链表7.在有n个结点的二叉链表中，值为非空的链域的个数为( )A. n-1B. 2n-1C. n+1D. 2n+18.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为( )A. 0B. 1C. 2D.不确定9.数组A［５］［６］的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，５］的地址为( )A. 1140B. 1145C. 1120D. 112510.求最短路径的DIJKSTRA算法的时间复杂度为( )A. O(n)B. O(n+e)C. O(n2)D. O(n×e)11.对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，312.快速排序算法在最好情况下的时间复杂度为( )A. O(n)B. O(nlog2n)C. O(n2)D. O(log2n)13.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )A.堆排序B.冒泡排序C.快速排序D.直接插入排序14.二叉树在线索化后，仍不能有效求解的问题是( )A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋D.后序线索二叉树中求后序后继15.DFS算法的时间复杂度为( )A. O(n)B. O(n3)C. O(n2)D. O(n+e)16.队列操作的原则是( )A.先进先出B.后进先出C.只能进行插入D.只能进行删除17.有64个结点的完全二叉树的深度为( )(根的层次为1)。

浙江理工大学数据结构与算法期末样卷(1)模拟试卷二一、单选题（每题2分，共20分）1．在一个具有额外字段结点的单链表中hl中，若要向字段填入一个由指针p指向的结点，则继续执行()a.hl=p;p->next=hl;b.p->next=hl->next;hl->next=p;c.p->next=hl;p=hl;d.p->next=hl;hl=p;2．若顺序存储的循环队列的queuemaxsize=n,则该队列最多可以存储（）个元素a.nb.n-1c.n+1d.不确定3．下列哪一条就是顺序存储方式的优点？（）a.存储密度大b.插入和删除运算方便c.获取符合某种条件的元素方便d.查找运算速度快4．建有一个二维数组a[m][n]，假设a[0][0]放置边线在600(10)，a[3][3]放置边线在678(10)，每个元素占到一个空间，问a[2][3](10)存放在什么边线？(注释(10)则表示用10十进制则表示,m>3)a.658b.648c.633d.6535．下列关于二叉树遍历的叙述中，正确的是()a.若一个树叶就是某二叉树的中序结点的最后一个结点，则它必就是该二叉树的前序结点最后一个结点b.若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点c.若一个结点就是某二叉树的中序结点的最后一个结点，则它必就是该二叉树的前序最后一个结点d.若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6．k层二叉树的结点总数最多为()a.2k-1b.2k+1c.2k-1d.2k-17．对线性表展开二分法搜寻，其前提条件就是()a.线性表以链接方式存储，并且按关键码值排好序b.线性表以顺序方式存储，并且按关键码值的检索频率排好序c.线性表以顺序方式存储，并且按关键码值排好序d.线性表以链接方式存储，并且按关键码值的检索频率排好序8．对n个记录进行堆排序，所需要的辅助存储空间为()a.o（1og2n）b.o（n）c.o（1）d.o（n2）9．对于线性表（7，34，77，25，64，49，20，14）展开杂凑存储时，若采用h（k）=k%7做为杂凑函数，则杂凑地址为0的元素存有（）个，a.1b.2c.3d.410．以下关于数据结构的描述中，恰当的就是()a.数组就是相同类型值的子集b.递归算法的程序结构比迭代算法的程序结构更为精炼c.树是一种线性结构d.用一维数组存储一棵全然二叉树就是有效率的存储方法二、填空题（每空1分，共26分）1．数据的逻辑结构被分成_________、________、__________和___________四种。

2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1．若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：（1）从S1中依次弹出两个操作数a和b；（2）从S2中弹出一个运算符op；（3）执行相应的运算b op a；（4）将运算结果压人S1中。

假定S1中的操作数依次是5, 8, 3, 2（2在栈顶），S2中的运算符依次是*, - , +（+在栈顶）。

调用3次F()后，S1栈顶保存的值是。

A. -15B. 15C. -20D. 202. 现有队列Q与栈S，初始时Q中的元素依次是1, 2, 3, 4, 5, 6（1在队头），S为空。

若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素人栈；③出栈并输出出栈元素，则不能得到的输出序列是。

A. 1, 2, 5, 6, 4, 3B. 2, 3, 4, 5, 6, 1C. 3, 4, 5, 6, 1, 2D. 6, 5, 4, 3, 2, 13. 设有一个12×12的对称矩阵M，将其上三角部分的元素m i, j（1≤i≤j≤12）按行优先存人C 语言的一维数组N中，元素m6, 6在N中的下标是。

A. 50B. 51C. 55D. 664. 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。

若T有k个叶结点，则T的结点总数是。

A. 2k-1B. 2kC. k2D. 2k-15. 已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是。

A. 00, 1011, 01, 1010, 11, 100B. 00, 100, 110, 000, 0010, 01C. 10, 1011, 11, 0011, 00, 010D. 0011, 10, 11, 0010, 01, 0006. 已知二叉排序树如下图所示，元素之间应满足的大小关系是。

数据结构习题集含答案目录目录 (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 ）。

2014年浙江理工大学938数据结构与数据库技术考研真题浙江理工大学2014年硕士学位研究生招生入学考试试题考试科目：数据结构与数据库技术代码：938（请考生在答题纸上答题，在此试题纸上答题无效）第一部分：数据结构（本部分共90分）一、程序设计题（按得分最高的4小题计分，本题得分最多不超过90分）1．已知单链表lnode结构如下，其头结点为head。

试编写程序算法，判断该单链表中元素是否按递增次序排列。

（本题20分）struct lnode{int data;struct lnode*next;}2．已知带头结点head的单循环链表lnode和以链表存储的堆栈snode，其结构分别如下。

试编写程序算法，将单链表中值为奇数的结点进栈到堆栈snode中去。

（本题20分）struct lnode{int data;struct lnode*next; }struct snode{int data;struct snode*next; }3．已知二叉树的根节点为t，其二叉链表结构如下：struct node{char data;struct node*lch,*rch;}这里，data为结点的值域，lch为结点的左孩子，rch为结点的右孩子。

试编写一个非递归函数，按照中序遍历次序，给出最后一个父节点的值（即data域的值）。

（本题25分）4．试编写程序，实现数据的冒泡排序算法，并分析算法的时间复杂度。

（本题25分）5．解答题（本题25分）。

①已知一个散列存储的线性表{18,81,58,34,26,75,67, 49,93}，散列函数为h(k)=k%11，散列地址空间为0~10。

若采用外链地址法处理冲突，试计算在该散列表上进行查找的平均查找长度。

（本小题15分）；②以数据集{4，5，6，7，18，12，10}为结点权值构造哈夫曼树，试计算其带权路径长度WPL值。

（本小题10分）第二部分：数据库技术（本部分共60分）二、解答题（每小题10分，按得分最高的6小题计分，本题得分最多不超过60分）数据库Sales用来存放某企业销售数据，它有4张表，Products表用来存储产品信息，Customers表用来存储客户信息，Orders表用来存储订单信息，OrderItems表用来存储订单明细信息，各表结构如下：(1)．Products表结构：列名类型长度规则中文说明ProductID数值型8主键产品编码ProductName字符型30非空产品名称Category字符型20非空产品类别QuantityPerUnit字符型20非空规格型号UnitPrice数值型8,2成本单价Products表记录举例：ProductID ProductName Category QuantityPerUnit UnitPrice 1Chai Beverages10boxes x20bags18.202Chang Beverages24–12oz bottles19.50 3Aniseed Syrup Condiments12–550ml bottles10.254Chef Anton’s GumboMixCondiments36boxes21.35……………14Tofu Produce40-100g pkgs23.25……………77Escargots de Bourgogne Seafood24pieces13.25(2)．Customers表结构：列名类型长度规则中文说明CustomerID字符型5主键客户编码CustomerName字符型50非空客户名称Address字符型60单位地址City字符型20所在城市Customers表记录举例：CustomerID CustomerName Address City ALFKI Alfreds Futterkiste Obere Str.57BerlinANATR Ana Trujillo Emparedados yheladosAvda.De la Constitución222MéxicoD.F.ANTON Antonio Moreno Taquería Mataderos2312México D.F.AROUT Around the Horn120Hanover Sq.London …………(3)．Orders表结构：列名类型长度规则中文说明OrderID数值型8主键订单编号CustomerID字符型5非空，外键客户编码OrderDate日期型8非空订单日期RequiredDate日期型8要货日期ShippedDate日期型8发货日期Orders表记录举例：OrderID CustomerID OrderDate RequiredDate ShippedDate 10248VINET2009-07-042009-08-012009-08-16 10249TOMSP2009-07-052009-08-162009-08-16 10250HANAR2009-08-082009-09-052009-09-07 10251VINET2009-08-112009-09-152009-09-12……………(4)．OrderItems表结构：列名类型长度规则中文说明OrderID数值型8外键订单编号ProductID数值型8外键产品编码UnitPrice数值型8,2两位小数，单价大于0销售单价Quantity数值型8非空，默认为0销售数量Amount数值型12,2计算列（=unitprice*quantity）销售额OrderItems表记录举例：OrderID ProductID UnitPrice Quantity Amount10248111412.5175.001024842910.493.60102487234 5.6190.401024914189.5171.0010249514240.451698.901025041710.2571.7510250514235.251480.50……………1．使用SQL语句，完成以下各项功能（注：必要时一个小题可以用多条语句去实现）①在客户表Customers中检索哪些客户其名称中包含“ch”或“an”这两个字符串。

模拟试卷一参考答案一、单选题（每题2分，共20分）1.B2.D3.A4.B5.B6.C7.A8.C9.B 10.B二、填空题（每空1分，共26分） 1. 顺序 链表 索引 散列 2. O(n) O(1)3. p->next=HS;HS=p HS=HS->next4. 2i 2i+1 ⎣i/2⎦（或i/2）5. 向上 根6. 2.97. 邻接矩阵 邻接表 边集数组 8. 1 49. O(n) O(nlog 2n) O(n)10. ⎡m/2⎤-1 m-1 ⎡m/2⎤ m三、 运算题（每题6分，共24分） 1. (1) 3 X * Y 2 - / 1 +(2) 2 X Y 3 + * + 2. （1）图3（2）见图3所示：3.(1)不是小根堆。

调整为：{12,65,33,70,24,56,48,92,86,33}(2)是小根堆。

4.普里姆算法从顶点1出发得到最小生成树为：(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20四、阅读算法（每题7分，共14分）1.30 24 16 10 2 102.该函数的功能是：统计出BT所指向的二叉树的结点总数和叶子总数五、算法填空（共8分，每一空2分）newptr==NULL newptr->=data newptr p=p->next六、编写算法（8分）void Delete(List& L, int i){for(int j=i-1;j<L.size-1; j++)L.list[j]=L.list[j+1]; //第i个元素的下标为i-1 L.size--;}。

2018年软件工程913真题
第一部分数据结构
第一小题：1）给出算法稳定性的解释？（2分）
2）对给出的6个方法进行稳定性分类（3分）
第二小题：1）将中序算术表达式改为后序算术表达式需要什么数据结构？（2分）
2）给出算法设计？（3分）
5.算法题3道共20分
第一小题：给出删除顺序表中最小值元素的算法？（6分）
第二小题：给出求二叉树深度的递归算法（3分）和非递归算法（5分）
第三小题：给出快速排序算法？（6分）
第二部分操作系统
4.算法题1道共10分
1）用C语言写出迪杰史特拉给出的哲学家就餐问题的经典解决方法？（10分）
5.论述题3道共30分
第一道题：1）画出UNIX经典的成链空闲块组织体系？（5分）
2）论述空闲块分配和回收的几种算法？（5分）
第二道题：题目给画了一张地址映射表
1）求虚拟地址总空间？（2分）
2）求物理地址总空间？（3分）
3）论述地址转换机制？（3分）
4）如何在虚拟地址空间远远小于物理地址空间的情况下，提高存储器利用率？（2分）
第三道题：描述了一个情景，关于磁盘的，然后问
1）什么是电梯调度？（2分）有什么优点？（2分）
2）计算机性能与电梯调度算法是否有关？（2分）
3）如何解释在实际测试中先来先服务和电梯算法结果一致？（4分）。

一、选择题1. 算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（C），它必须具备（B）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（ B ）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C.5. 下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（ C ）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低4A．(1) B.(1),(2) C.(1),(4) D.(3)【武汉交通科技大学 1996 7．从逻辑上可以把数据结构分为（ C ）两大类。

一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）。