2010深圳大学专插本计算机科学与技术专业试题

1、2010年深大计算机组成原理（回忆版）一、填空题（10个空）1 .组成计算机的5个组成基本部件；2 .主储存器的三个主要性能指标；3 .浮点数加减运算的五个步骤；4 .三级存储器结构；5 .DMAE种工作方式；6 .五种数据传送控制方式；小结A:以上从我脑海挖出大概，希望对大家有帮助。还有感觉我写过一个填高速缓冲存储器，哈哈。总体感觉比较简单，我只有一个填空不确定。其实你可以上题目看到出得不会很难，要懂得归纳重点知识（报考时每一科目我都准备一小本来归纳重要知识点和提纲），所以复习全面，我的意思至少看书两三遍，应该没什么问题。二、选择题一共10题，题字数的特点就是很短、不多，不会冗长。最后选择题

2、弄得我头绪很乱，就是有几个选项不确定。大概考了（我写出可能类似题目，以此题目自己扩展）定点小数不定范围；动态存储器器件与静态存储器器件的比较与区别；虚拟存储器概念等等。二、计算题1 .用补码一位乘法Booth算法（其他要掌握加减乘除算法）2 .计算虚拟地址和物理地、页表长度是多少？具体题目见计算机构成与组成（第4版）P260题7.10小结B:可以看出做一做书后练习题，选择做基础的基本的题目，因为课后练习题有写题目有点难。四、名词解释1 .控制存储器2 .水平型微指令3 .微指令、微操作、微程序（印象考了其中一个）小结C:自己要懂得归纳每章主要的知识点，重点词汇。最后两个我是模棱两可的大概的写上

3、去，我的意思尽量凭自己理解答上去，不要空着。最后两题好像不像提纲给例题，还是我记得不太清楚。五.综合题1 .中断请求排队逻辑（考查询法、串行排队链法内容，还要求画图，有2小题）具体参考书上P338339,还有课外书力推计算机组成原理习题与解析（徐爱萍）。嘻嘻，我发现很多题目跟这本书一模一样。2 .中断处理过程（这题太简单，哈哈）总结：本人用了两个星期看计算机组成原理，然后寒假又认真学习几遍。课本和计算机组成原理习题与解析（徐爱萍）相结合学习（还有其他课外书，这些书都是图书馆借来的，但是用的最多也是这本书），学习与复习要点是对照提纲（汗！深大出的提纲让人难以理解，什么是要掌握，什么是了解，都是模

4、棱两可,我想偷懒都不行。）总结本章主要知识点，写在笔记本上。从试题看总体难度不会很深，要牢固知识点。2010年数据结构深大题目（回忆版）题目类型不像以往出10个简答题，当时看到有填空题就傻了眼（最后冷静下来还是可以做的，>.<|）一、填空题.1 .给个程序计算时间复杂度；2 .考队的知识，列出一些条件，写出循环队结束条件。3 .记不清是二叉树或图的遍历算法，例如告诉你元素之间关系，然后写出其中一个（先、中、后）遍历次序。以下题目6个简答题（包括题中小题目），最后一道是写程序（这个忘了，我也没有写，其实我知道我一定不会写，哈）。二、简答题1 .赫夫曼算法（今年考具体看数据结构c语言版

5、严蔚敏P148例6-2）2 .哈希算法与解决冲突（1）开放定址法（2）拉链地址法3 .最小生成树（普里姆prim）4 .最短路径（迪杰斯特拉Dijkstra）5 .希尔排序算法6 .快速排序算法（包括计算平均查找长度）7 .归并排序算法8 .关键路径（搞清楚最早发生时间、最迟发生时间、最早开始时间和最早开始时间）9 .二叉排序树的插入和删除小结：以上排序不分先后，主要要理解算法，推荐网上找清华大学严蔚敏教学视频，还有书上有例题可以理解后试试自己做一下，当然不缺少课外辅导书，推荐数据结构习题与解析李春葆里面有许多例题多做。【转】2008年深大数据结构一共有10道大题。1 .二叉树的中序遍历顺序（

6、只要写出顺序就行，不用写算法，但算法也是要理解了才写得出来）2 .构造huffman树（画出一棵树就行了，这题是不应该扣分的）3 .二叉排序数的遍历与结点删除（写出遍历的顺序和删除后的二叉排序数）4 .哈稀表，解决冲突的算法；（这题我没做，有12分，可惜了！，有好几种解决冲突的算法，建议都要掌握，必考啊！）5 .排序（归并排序，堆排序），每趟的排序结果；（只要写出每趟的排序结果，重要啊，算法一定要理解才行，虽然这里不用写具体算法。）6 .邻接表的拓扑排序结果；（写出拓扑排序的结果，拓扑排序的算法P181）7 .最短路径问题（这题具体怎样就不记得了，自己看看书吧！离散数学那本书也有得说。）以下是

7、算法设计题：8 .将一数值插入到数组中9 .字符用模式匹配算法（课本P79,这个无论如何都要记下来，不只一年出了这道题）10 .求邻接表入度的算法小结：感谢2008年师兄提高数据结构回忆版，其实对于数据结构试题深大并没有给出，其实很郁闷，郁闷的是怎样去考试，因为不知道他要怎样考，如何掌握考试的“度”？所以我在百度苦苦地寻找。这些对我的备考很大帮助。这是学校内师兄给的，但是不知道哪年的题目，大概是06、07年的题目吧。数据结构：十几道题，全是解答题，没考填空跟选择，跟研究生题型差不多难度也差不多（网上有得下），当然难度难的比它低，考试范围也没那么广，跟师兄说的去年所考题型不同，跟广大的也不同。内

8、容考了二叉排序树建树，二插归并排序，堆排序过程，最短路径拓扑排序，哈希排序（除余数法，冲突线性探测再散列跟拉链法两种）还有几题忘了，最后两道是要写出代码的，一道是模式匹配算法index,一道是输出图的入度。总体而言难度不是很大，如果方向正确跟复习到位，可以拿高分，可惜我复习方向不正确。这个深大专业网页（类似精品课程）上找，这资料【赞】一、写函数voidDelData(inta,intN),删除有序表a中多余的相同元素。其中N为元素个数2007-09-18。intaN;voidDelData(inta,intN)inti,j;for(i=0,j=0;j<N;i+,j+)if(i<j)

9、ai=aj;while(ai=aj+1)j+;ai=aj;二、现有模式串ababaabbab,求其next值。请写出每个next值的求取过程2007-09-27解：求nextj值的算法、j的初值为1,next1=0,i=0、While(j<模式串长度) .若i=0或者Ti=Tj,则i+,j+,nextj=i .否则，i=nexti设ababaabbab的次序为：12345678910则next(1)=0;next(2)=1;next(3)=1;因为P2=b!=Pnext(2)=P1=anext(4)=2;因为P3=a=Pnext(3)=P1=anext(5)=3;因为P4=b=Pnext

10、(4)=P2=bnext(6)=4;因为P5=a=Pnext(5)=P3=anext(7)=2;因为P6=a!=Pnext(6)=P4=b且!=Pnext(4)=P2=b且!=Pnext(2)=P1=anext(8)=3;因为P7=b=Pnext(7)=P2=bnext(9)=1;因为P8=b!=Pnext(8)=P3=a且!=Pnext(3)=P1=anext(10)=2;因为P9=b=Pnext(9)=P1=a、假设字符a,b,c,d,e的频度分别为34%,14%,25%,12%,15%,计算Huffman编码（要求Huffman树的右子树小于左子树）.2007-10-16解：a: 00b

11、: 010c: 10d: 011e: 11四、请采用普里姆（Prim）算法（从顶点1开始）和克鲁斯卡尔（Kruskal）算法分别生成下图的最小生成树（请画出每一步的过程）。2007-10-25解：1、普里姆（Prim）算法是从指定点开始，连通分量不断增长的过程其中：（4,5）和（4,6）两条边权值相等，因此哪个先做都可以。2、克鲁斯卡尔（Kruskal）算法是从最小的边开始，不断将两个连通分量变成一个连通分量的过程其中：（4,5）,（4,6）,（1,3）三条边权值都为1,因此哪个先做都可以；然后，再做（2,4）,（1,4）两条边，当然这两条边权值也相等，因此，哪个先做都可以。五.有向网N=V,

12、E,V=0,1,2,3,4,E=<0,1,1>,<0,3,3>,<0,4,10>,<1,2,5>,<2,4,1>,<3,2,2>,<3,4,6>,E中每个元组的第三个元素表示权。、画出该网。、用Dijkstra算法求最短路径，写出顶点0到其它各顶点的最短路径长度、路径及产生过程。、求关键路径，写出计算过程。2007-11-01解：、有向网N如右图所示Di10,1OO60,1,250,3,230,330,3100,4100,1090,3,460,3,2,40,10,1,30,1,3,20,1,3,2,4、用Dij

13、kstra算法求最短路径过程如下1234S、关键路径求解过程如下先求出拓扑排序为：0,1,3,2,400011426933441010VEiVLi最短路径<0,1><0,3><0,4><1,2><2,4><3,2><3,4>03010014693734EiLi由上表可以看出，只有弧<0,4>（即活动）的关键路径E和L相等（皆为0）,因此,弧<0,4>是六.画出在初始为空的AVL树中依次插入2,1,3,5,8,4,7,6并在有“旋转”时说出“旋转”的类型。2007-11-13时该树的生长全

14、过程,解:、七、假设关键字输入顺序为5,55,67,21,44,12,3,53,23,已知散列函数为：H（Key）=Key%11、用拉链法解决冲突，画出插入所有关键字后的链表结构（假设链表头插入）。、计算该表查找成功的平均查找长度（ASD。2007-11-22012345678910、ASL=(1/9)X(1X6+2X2+3X1)=13/9八、分别用直接插入排序、起泡排序、快速排序、堆排序、归并排序、链式基数排序算法对整数序列43,17,12,8,70,89,75,65,77,9进行升序排序，、写出直接插入排序、起泡排序、归并排序每一趟的排序结果；、写出快速排序第一趟的排序结果；、写出堆排序建

15、初始堆和输出最大两个关键字记录的排序过程；、写出链式基数排序的每一趟分配和收集的结果。2007-12-11解：1、直接插入排序43,17,12,8,70,89,75,65,77,943,17,12,8,70,89,75,65,77,917,43,12,8,70,89,75,65,77,912,17,43,8,70,89,75,65,77,98,12,17,43,70,89,75,65,77,98,12,17,43,70,89,75,65,77,98,12,17,43,70,89,75,65,77,98,12,17,43,70,75,89,65,77,98,12,17,43,65,70,75,8

16、9,77,98,12,17,43,65,70,75,77,89,98,9,12,17,43,65,70,75,77,892、起泡排序43,17,12,8,70,89,75,65,77,917,12,8,43,70,75,65,77,9,8912,8,17,43,70,65,75,9,77,898,12,17,43,65,70,9,75,77,898,12,17,43,65,9,70,75,77,898,12,17,43,9,65,70,75,77,898,12,17,9,43,65,70,75,77,898,12,9,17,43,65,70,75,77,898,9,12,17,43,65,70

17、,75,77,898,9,12,17,43,65,70,75,77,898,9,12,17,43,65,70,75,77,89归并排序43,17,12,8,70,89,75,65,77,917,43,8,12,70,89,65,75,9,778,12,17,43,65,70,75,89,9,778,12,17,43,65,70,75,89,9,778,9,12,17,43,65,70,75,77,894、快速排序第一趟的排序结果4317127089756577取pivotkey=4317127089756577highlow9与pivotkey（43）交换之后，low+,且向右比较1712毕l

18、ow89756577high70与pivotkey（43）交换之后,high-,且向左比较171289756577highlowpivotkey(43)放到low,high指向的位置17128975657770lowhigh43快速排序第一趟结束。5、堆排序建初始堆先将序列43,17,12,8,70,从70开始做筛选，由于70>9,因此，完全二叉树没有变化。从8开始做筛选，由于77>65>8,因此，77代替8,得：17122010年5月9日母亲节快乐（77）70897565从12开始做筛选,由于89>75>12,从17开始做筛选，由于77>70>70,因此，77代替17,由于65>17>8,因此，65代替17,得：从43开始做筛选，由于89>77>43,因此，89代替43,由于75>43>12,因此，75代替43,得：输出最大值89,将9放到根上，由于77>7