计算机软件基础试题

1、百度文库软件技术基础试题库课程名称：软件技术基础适用专业：软件技术、计算机应用、网络、信息等计算机相关专业第一章概述第二章数据结构一、单项选择题1 .若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动个数据元素。()A. n-iB. n+iC. n-i-1D. n-i+1答案：A2 .在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行。()A. link(s)-link(p)link(p)-sB. link(q)厂Hnk(s)-pC. link(p)-link(s)ink(s)-pD. link(p)厂Hnk

2、(s)-q/答案：B3 .高度为h(h>0)的二叉树最少有个结点。()/A. h/B. h-1C. h+1答案：A4 .n个顶点的带权无向连通图的最小生成树包含个顶点。（）2+1/答案：B5 .采用拉链法解决冲突的散列表中，查找的平均查找长度（）。A.直接与关键字个数有关'B.直接与装填因子a有关C.直接与表的容量有关D.直接与散列函数有关答案：D6 .树型结构最适合用来描述（）A.有序的数据元素B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据答案：C7 .若二叉树中度为2的结点有15个，度为1的结点有10个个叶结点。（）答案：C8 .若深度为

3、6的完全二叉树的第6层有3个叶结点，则该二叉树一共有个结点。（）答案：C9 .若某完全二叉树的深度为h,则该完全二叉树中至少有个结点。（）+1./答案：C/10 .在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该（）A.只有左子树上的所有结点B.只有左子树上的部分结点C.只有右子树上的所有结点D.只有右子树上的部分结点答案：A11 .下面关于哈夫曼树的说法，不正确的是（）A.对应于一组权值构造出的哈夫曼树一般不是唯一的B.哈夫曼树具有最小带权路径长度C.哈夫曼树中没有度为1的结点D.哈夫曼树中除了度为1的结点外，还有度为2的结点和叶结点答案：D12 .数据结构是一门研究计算机中对象及其关

4、系的学科。（）A.数值运算B.非数值运算C.集合D.非集合答案：B13 .数据结构的定义为（K,R）,其中K是的集合。（）A.算法B.数据元素C.数据操作D.逻辑结构、答案：B14.算法分析的目的是。（）/A.找出数据结构的合理性/B.研究算法中输入和输出的关系/C.分析算法的效率以求改进D.分析算法的易懂性和文档性答案：C15.数据的不可分割的基本单位是。()A.元素B.结点/C.数据类型D.数据项答案：D/16 .是具有相同特性数据元素的集合，是数据的子集。()A.数据符号B.数据对象C.数据D.数据结构'答案：B17 .数据结构是研究数据的及它们之间的相互联系。()A.理想结构、

5、物理结构B.理想结构、逻辑结构C.物理结构、逻辑结构D.抽象结构、逻辑结构答案：C18 .组成数据的基本单位是。()A.数据项B.数据类型C.数据元素D.数据变量答案：C19 .数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为。()A.存储结构/B.逻辑结构/C.顺序存储结构D.链式存储结构/答案：C20.算法指的是。()'/A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列答案：D21.由组成的集合是一个数据对象。()A.不同类型的数据项/B.不同类型的数据元素/C.相同类型的数据项D.相同类型的数据元素答案：D22 .关于顺序存储的叙述中

6、，哪一条是不正确的。()A.存储密度大B.逻辑上相邻的节点物理上不必邻接,C.可以通过计算直接确定第i个节点的位置'D.插入、删除操作不方便答案：B23 .一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是。()答案：B24 .已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da,则第i个结点的地址为。()+(i-1)*m+i*m*m+(i+1)*m答案：A25.链表是一种采用存储结构存储的线性表。()/A.顺序/B.链式/C.星式D.网状答案：B/26.线性表若采用链式存储结构时，要求内存中可用存储单元的地址。()A.必须是连续

7、的B.部分地址必须是连续的C. 一定是不连续的D.连续或不连续都可以答案：D27.线性表L在情况下适用于使用链式结构实现。（）A.需经常修改L中的结点值B.需不断对L进行删除插入C.L中含有大量的结点D. L中结点结构复杂答案：B28 .在长度为n的顺序表的第i（1wiwn+价位置上插入一个元素，元素的移动次数为。（）+1答案：A29 .线性表是。（）A. 一个有限系列，可以为空B. 一个有限系列，不能为空C.一个无限系列，可以为空D.一个无限系列，不能为空答案：A30 .是线性表。（）A.（孔子，诸葛亮，曹雪芹）B.A,B,C,DC.10,11,12,13,14D.（1,2,3，）答案：A3

8、1 .一是表示线性数据结构的。（）/A.循环链表/B.邻接多重表/C.孩子链表D.单链表/答案：D32.将线性表的数据元素以结构存放，查找一个数据元素所需时间不依赖于表长。（）A.循环双链表B.哈希(Hash)表C.一维数组D.单链表/答案：C33 .在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行()>link=p;p->link=s;/、>link=p->link;p->link=s;>link=p->link;p=s;>link=s;s->link=p;答案：34 .在循环链表中first为指向链表表头的指针，

9、current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是。()>link=NULL>link=current=current>link=first答案：35 .从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较个结点。()2C.(n-1)/2D.(n+1)/2答案：36 .用链表表示线性表的优点是。()A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同答案：37 .当需要随机查找线性表的元素时，宜采用作存储Z构。()/A.双向链表/B.循环链表/C.顺序表D.单链表

10、9;、/答案：38 .线性表的链接实现有利于运算。()A.插入B.读表元C.查找D.定位/答案：39 .线性表采用链式存储时，其地址。（）A.必须是连续的/B.部分地址是连续的C.一定是不连续的D.连续与否均可以答案：40 .设单链表中指针p指着结点a,若要删除a之后的结点（若存在），则需要修改指针的操作为。（）>next=p->next->next=p->next=p->next->next>next=p答案：A41 .向一个有127个元素顺序表中插入一个新元素并保存原来顺序不变，平均要移动一个元素。（）答案：A42 .向一个有127个元素的顺序表中

11、删除一个元素，平均要移动个元素。（）答案：C43 .又称为FIFO表。（）A.队列/B.散列表/C.栈D.哈希表/答案：44 .设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有。（）45 .链式栈与顺序栈相比，一个比较明显的优点是。()A.插入操作更加方便/B.通常不会出现栈满的情况/C.不会出现栈空的情况/D.删除操作更加方便答案：46 .在一个顺序存储的循环队列中，队头指针指向队头元素的。()A.前一个位置、B.后一个位置C.队头元素位置D.队尾元素的前一位置答案：47 .若一个栈的输入序列是1,2,3n,则输出序列的第一个元素是n,则第i个输出元素是°()+

12、1答案：48 .栈的数组表示中，top为栈顶指针，栈空的条件是。()=0=maxSize=maxSize=-1/答案：49 .在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是。()/=maxSize、/B.(rear+1)%maxSize=front/=maxSize、-/=front/答案：50 .栈和队列的共同特点是。()9百度文库A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除D.没有共同点/答案：51 .若非空队列采用链式存储结构，front和rear分别为队头元素与队列尾元素的指针，删除此时队列的一个元素的操

13、作时依次执行pfront,callRET(P)。()link(rear)link(p)/link(front)link(p)答案：52 .由两个栈共享一个向量空间的好处是。()A.减少存取时间，降低下溢发生的机率B.节省存储空间，降低上溢发生的机率'C.减少存取时间，降低上溢发生的机率D.节省存储空间，降低下溢发生的机率答案：53 .数组datam为循环队列的存储空间，front为队头指针，rare为队尾指针，则执行入队的操作为。()=rare+1二(rare+1)%(m-1)二(rare-1)%m二(rare+1)%m答案：54 .将递归算法转换成对应的非递归算法时，通常需要使用。(

14、)/A.栈、/B.队列/C.链表D.数组/答案：55.高度为h(h>0)的二叉树最少有个结点。1)答案：56.树型结构最适合用来描述。()A.有序的数据元素7B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据答案：57k有n(n>0)个结点的完全二叉树的深度是。()A. log2(n)B. log2(n)+1C. log2(n+1)D. log2(n)+1答案：58.又是一棵满二叉树。()A.二叉排序树B.深度为5有31个结点的二叉树C.有15个结点的完全二叉树D.哈夫曼(Hufman)树答案：59 .深度为k的满二叉树有个分枝结点。()+1+1答

15、案：60 .若已知一棵二叉树先序序列为ABCDEFG,中序序列为CBDAEGF,则其后序序列为。()/答案：A61 .二叉树第i(i>=1)层上至多有结点。()A. 2iB. 2i)1- 1C. 2iD. 2i-1/答案：62.在一棵具有5层的满二叉树中结点总数为。()A. 31B. 32C. 33/D. 16答案：63.一个二叉树按顺序方式存储在一个维数组中，如图01234567891011121314ABCDEFGHIJ则结点E在二叉树的第层。()答案：64r在一棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为。()A. 4B. 5/C. 6/D. 7

16、/答案：65.n个顶点的带权无向连通图的最小生成树包含个顶点。()2/+1答案：12百度文库66 .具有n个顶点的有向完全图有条弧。()*(n-1)*(n+1)/*n/答案：67 .n个顶点的连通图至少有条边。()+1答案：68 .在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。()A. 1/2B. 1C. 2D. 4答案：69.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为。()A. eB. 2eC. n2eD. n22e答案：D70 .折半查找有序表(6,15,30,37,65,68,70,72,89,99)，若查找元素37,需依次与表中元素进行比较。()/,15,3

17、7,30,37,15,30,15,30,37/答案：71 .对有3600个记录的索引顺序表(分块表)进行查找，最理想的块长为。()答案：B72 .折半查找20个记录的有序表，若查找失败，比较关键字的次数。()A.最多为6B.最多为5/C.最多为4/D.最多为3/答案：B73 .中序遍历一棵二叉排序树所得到的结点序列是键值的序列。()A.递增或递减B.递减C.递增D.无序答案：74 .散列表中的冲突是指。()A.两个元素具有相同的序号B.两个元素的键值相同，而其他属性相同C.不同的键值对应相同的存储地址D.数据元素的地址相同答案：75 .用线形探测法查找散列表，可能要探测多个散列地址，这些位置上

18、的键值。()A.一定是同义词B.不一定是同义词C.一定不是同义词D.都相同答案：76 .在初始为空的杂凑表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),杂凑函数为H(k尸iMOD7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为0:6,采用线性再散列法处理冲突。插入后的杂凑表应该如所示。()/A. 0123456THUTUEWEDFRISUNSATMONB. 0123456/TUETHUWEDFRISUNSATMON'/C. 0123456TUETHUWEDFRISATSUNMOND. 0123456TUETHUWEDSUNSATFRI

19、MON答案：77 .设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过，则散列存储空间应能够至少容纳个表项。（设搜索成功的平均搜索长度为Snl=（1+1/（1-a）/2,其中a为装填因子）（）答案：78 .对长度为10的表作选择（简单选择）排序，共需比较一次关键字。（）答案：79 .设有100个数据元素，采用折半搜索时，最大比较次数为（）。A. 6B. 7C. 8D.1080 .对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是。（）A.选择排序B.直接插入

20、排序,/C.快速排序/D.起泡排序/答案：C81 .对5个不同的数据元素进行直接插入排序，最多需要进行次比较。（）A. 8B. 10/C. 15/D. 25答案：82.采用折半查找方法进行查找，数据文件应为,且限于。（）A.有序表顺序存储结构/B.有序表链式存储结构/C.随机表顺序存储结构/D.随机表链式存储结构答案：83.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其存放在已排序序列的合适位置，该排序方法称为排序法。（）A.插入B.选择C.希尔D.二路并归答案：84.就平均查找速度而言，下列几种查找速度从慢至快的关系是。（）A.顺序折半哈西分块B.顺序分块折半哈西C

21、.分块折半哈西顺序D.顺序哈西分块折半答案：B85 .在下列算法中，算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。（）A.堆排序B.冒泡排序C.插入排序D.快速排序/答案：C86 .堆是一个键值序列（Ki,K2,，K）,对I=1,2n/2蹒足。（）< =K2i<=K2i+1/< K2i+1<K2i/< =K2i且Ki<=K2i+1D.Ki<=K2i或Ki<=K2i+1/答案：87.对于关键字序列46,58,15,45,90,18,10,62,其快速排序第一趟的结果是4518151818151018答案：46106245

22、4658454690454662。（）589062905862589020,15,21,25,47,27,68,/15,20,21,25,35,27,47,/15,20,21,25,27,35,47,则所米用的排序方法是一。（）88.用某种排序方法对关键字序列（25,序列的变化情况如下：A.选择排序 B.希尔排序 C.归并排序 D.快速排序 答案：84,21,47,15,27,68,35,20）进行排序时,35,8468,8468,8489 .下列关键字序列中是堆。（）A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94,31,72D.16,2

23、3,53,31,94,72答案:90 .目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是。（）A.插入排序/B.直接选择排序/C.快速排序/D.冒泡排序/答案：B91.对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为。（）A. n+1B. n/C. n-1'/D. n（n-1）/2答案：二、多项选择题1.根据数据元素之间的不同特性，通常具有这几种基本数据结构。（）A.集合/B.线形结构/C.树型结构/D.图型结构/答案：ABCD2.数据元素之间的关系在计算机中有两种不同的表示方法。（）A.顺序存储结构B.二叉树存储结构C.链式存储结构D.网

24、络结构答案：AC3.查找哈希（Hash）表,解决冲突的的方法有。（）A.除留余数法B.线性探测再散列法C.直接地址法D.链地址法答案：BD三、判断题1 .非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（）答案：F2 .数组是一种没有插入与删除操作的线性结构。（）答案：T3 .非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（）答案：F4 .数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（）答案：F5 .线性链表中各个链结点之间的地址不一定要连续。（）答案：T6 .若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。（）答案：F7 .若

25、线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144,则第1个数据元素的存储地址是101。()答案：F/8 .若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。()/答案：F9 .符号link(p)出现在表达式中表示p所指的那个结点的内容。()答案：F10 .要将指针p移到它所指的结点的下一个结点是执行语句plink(p)。()、答案：T11 .在非空线性链表中由p所指的结点后面插入一个由q所指的结点的过程是依次执行语句：link(q)-link(p);link(p)。()答案：T12 .在非空双向循环链表中由q所指的结

26、点后面插入一个由p指的结点的动作依次为：llink(p)-q,rlink(p)-rlink(q),rlink(q)-p,llink(rl(nk(q)-p答案：F13 .若某堆栈的输入序列为1,2,3,4,则4,3,1,2不可能是堆栈的输出序列之一。()答案：T14 .删除非空链式存储结构的堆栈(设栈顶指针为top)的一个元素的过程是依次执行:ptop,toplink(p),callRET(p)。()答案：T15 .若队列采用链式存储结构，队头指针与指针分别为front和rear,向队列中插入一个数据信息为item的新元素的过程是依次执行：callGETNODE(p),data(P广item,r

27、earp,front()答案：F16 .数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。()答案：T17 .非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。()答案：F/18 .在顺序表中取出第i个元素所花费的时间与i成正比。()答案：F19 .完全二叉树就是满二叉树。（）答案：F20 .已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（）答案：T/21 .有向图是一种非线性结构。（）答案：T/22 .带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。（）答案：T23 .对二叉排序树遍历的结果是一个有序序列。（）答案：T24

28、 .折半查找方法适用于按值有序的线性链表的查找。（）答案：F25 .非空二叉排序树的任意一棵子树也是二叉排序树。（）答案：T26 .哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。（）答案：T四、填空题1 .已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC（a1）,那么，LOC（ai尸。答案：LOC（a1）+（n-1）k2 .若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为。答案：43 .设SQ为循环队列，存储在数组dm中，则SQ出队操作对其队头指针front的修改是答案：4 .n（n>0）个结点二叉树对应的森林最多包含

29、棵非空树。5 .深度为n（n>0）的二叉树最多有个结点。6 .n(n>0)个结点、(n-1)条边的连通无向图中，顶点度数最大值为。7 .在一个图中，所有顶点的度数之和等于所有边的数目的倍。答案：8 .图的深度优先搜索方法类似于二叉树的遍历。9 .带权连通图G,其中V=v1,v2,v3,v4,v5,E=(v1,v2)7,<V1,V3)6,(V1,V4)9,(V2,V3)8,(V2,V3)8,(V2,V4)4,(V2,V5)4,(V3,V4)6,(V4,V5)2(注：顶点偶对右下角的数据为边上的权值)，G的最小生成树的权值之和为。答案：10 .将数据元素2,4,6,8,10,12

30、,14,16,18,20依次存放于一个一维数组中，然后采用折半查找方法、查找元素12,被比较过的数组元素的下标依次为。答案：11 .每趟排序从未排序的子序列中依次取出元素与已经排好序的序列中元素进行比较，然后将其放在已经排好序的序列的合适位置。这种排序法称为排序法。答案：12 .从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为排序法。答案：13 .对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序，以序列的第一个元

31、素为基准元素得到的划分结果是1。/答案：14 .一个数据结构在计算机中的表示(映象)称为?。15 .数据结构被形式地定义为(D,R),其中D是的有限集合，R是D上的有限集合。答案：16 .数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关，是独立于计算机的。17 .一个算法具有5个特性:、有零个或多个输入、有一个或多个输出。答案：18 .线性表中称为表的长度。19 .设长度为n的线性表顺序存贮，若在它的第i-1和第i个元素之间插入一个元素，共需移动个元素（1<iwn）答案：20 .在单链表中要在已知结点*p之前插入一新结点，需找到。答案：21 .循环链表的主要优点是。答案：从任何一个结

32、点出发可以遍历所有结点22 .在一个单链表中删除p所指结点的下一个结点时，应执行以下操作：q=p->link;p->link=Deleteq答案：23 .设SQ为循环队列，存储在数组dm中，则SQ出队操作对其队头指针front的修改是O答案：24 .栈中元素的进出原则为。25 .在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个结构，其主要特点是。答案：26 .对于一个以顺序实现的循环队列Q0m-1,队头、队尾指针分别为f、r,其判空的条件是,判满的条件是。答案：r=f、

33、(r+1)%m=f27 .在具有n个单元的循环队列中，队满时共有个元素。28 .深度为n(n>0)的二叉树最多有个结点。29 .n(n>0)个结点、(n-1)条边的连通无向图中，顶点度数最大值为。30 .一棵深度为6的满二叉树有个非终端结点。31 .若一棵二叉树中有8个度为2的结点，则它有个叶子。32 .树中结点A的称为结点A的度。33 .一棵深度为4的二叉树最多有个结点。34 将转化为二叉树时，其根结点的右子树总是空的。答案：35 .哈夫曼树是带权路径长度的树，通常权值较大的结点离根结点。/答案：36 .具有n个叶子的二叉树，每个叶子的权值为wi(1&i等刚带权路径最小的

34、二叉树被称为。/答案：37 .若已知一棵二叉树的先序序列为-+a*b-cd/ef,中序序列为a+b*c-d-e/f,贝U其后序序歹U为。/答案：38 .已知一棵完全二叉树中共有768结点，则该树中共有个叶子结点。答案：39 .已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30,则总结点数为。答案：40 .具有10个顶点的无向图，边的总数最多为。41 .在有n个顶点的有向图中，每个顶点的度最大可达、。答案：42 .有向图g用邻接矩阵a口m,1m来存储，其第i行的所有元素之和等于顶点i的。答案：43 .有n个球队参加的足球联赛按主客场制进行比赛，共需进行场比赛。、答案：44 .带权连通图G=

35、<V,E>,其中V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v4)6,(v1,v4)9,(v2,v3)8,(v2,v4)4,(v2,v5)4,(v3,v4)6,(v4,v5)2,(注:顶点偶对右下角的数据为边上的权值),G的最小生成树的权值之和为。答案：45 .顺序查找n个元素的顺序表，当使用监视哨时，若查找成功，比较关键字的次数至少为一次，最多为一次；若查找失败，比较关键字的次数为一、次。答案：46 .在单链表上难以实现的排序方法有、和。/答案：快速排序、堆排序、希尔排序五、简答题/问答题/综述题1 .什么是顺序表？顺序表的特点是什么？答案：线性表的顺序存储是

36、指在内存中用一块地址连续的存储空间顺序存放线性表的各元素，用这种形式存储的线性表称为顺序表。数据元素在顺序表中物理位置取决于数据元素在线性表中的逻辑位置，可得出顺序表的特点：逻辑位置相邻，其物理位置也相邻。2 .什么样的图是连通图？答案：在无向图G中，如果从一个顶点Vi到另一个顶点vj(ij)有路径，则称顶点vi和顶点Vj是连通的，若图中任意两顶点间都是相通的，则称此图是连通图。3 .二叉树有哪几种基本形态？画图说明之。答案：六、操作题/综合能力题原始序列答案：共需5趟7638651397275049第1趟结果3865137627504997第2趟结果3813652750497697第3趟结果

37、1338275049657697第4趟结果1327384950657697第5趟结果13273849506576972.若对序列(763865,139727,50,49）采用选择排序法（按照值的大小从小到大）原始序列763865139727答案：第1趟结果7638651349275097第2趟结果5038651349277697第3趟结果5038271349657697第4趟结果4938271350657697第5趟结果1338274950657697第6趟结果1327384950657697第7趟结果1327384950657697进行排序，请分别在下表中写出每一趟的结果:3.把 1 、50

38、494依次进栈（栈初始为空），任何时刻（只要栈不空），都可以出（退）栈，试写出所有可能的出栈序列（如 答案：1234 )。1.若对序列（76,38,65,13,97,27,50,49）采用冒泡排序法（按照值的大小从小到大）进行排序，共需几趟排序？请分别在下表中写出每一趟的结果：271度顶4 .若一二叉树有2度结点100个，则其叶结点有多少个？该二叉树可以有多少个点？答案：5 .已知某非空二叉排序树采用顺序存储结构依次将所有结点的数据信息存放于一维数组ABDIC口EF口口C口口晴分别写出该二叉树的前序遍历序列与中序遍历序列。答案:6 .二叉树的顺序存储结构答案7 .给定30个字符组成的电文DDD

39、DDAAABEEAAFCDAACABBCCCBAADD试为字符A、B、C、D、E、F设计哈夫曼（Hufman）编码。转换为T2T3棵二叉树。T4(1)画出相应的哈夫曼树；(2)分别列出A、B、C、D、E、F的哈夫曼码;(3)计算该树的带权路径长度WPL。答案:8 .试将森林 F= T1,T2,T3,T4 ©T1答案:9 .试画出下列二叉树的中序线索二叉树存储结构图。二叉树答案:10 .试用孩子兄弟(左孩子右兄弟)表示法画出下列树的存储结构图。树答案：11 .已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,F,E,G和D,C,A,F,G,EB试画出该二叉树。答案：12 .

40、试用双亲表示法画出下列树T的存储结构图。/X®附T答案：13 .假定后序遍历二叉树的结果是A,C,B(1)试画出所有可得到这一结果的不同形态的二叉树;(2)分别写出这些二叉树的中序遍历序列。14 .有9个带权结点a、b、c、d、e、f、g、h、I,分别带权4,2,7,12,6,10,5,9,3,试以他们为叶子结点构造一棵哈夫曼树(请按照左子树根结点的权小于等于右子树根结点的权的次序构造)。/答案：15 .某二叉树的结点数据采用顺序存储表示如下：0123456V891011121314151617Z19EAFDHCGIB(1)试画出此二叉树的图形表示。(2)写出结点D的双亲结点及左、右

41、子女。/(3)将此二叉树看作森林的二叉树表示，试将它还原为森林。答案：百度文库16 .图的邻接矩阵：及一答案：/17 .有向图的逆邻接表/©a/答案：18 .找出卜面网络的最小生成树。/二（eVM6募/答案：19.找出卜面网络的最小生成树：''JTo（用61-5答案：20 .试回出卜列图的邻接表。®-w图答案：,z21 .对卜面的带权无向图米用prim算法从顶点28/开始构造取小生成树。（与出加入生成树百度文库47顶点集合S和选择边Edge的顺序）Edge:答案:（顶点，顶点，权值）22.对图所示有向图，试用Dijkstra算法求出从源点1到其它各顶点的最短

42、路径，并写出执行算法过程中扩充结点的每次循环状态。23.已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH请写出从顶点中，边的信息存放于邻接矩阵中，邻接矩阵为A出发对该图进行深度有限搜索后得到的顶点序列。01100V答案:10001010010100100101000000110001000010'01V24 .试按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中，使之仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树；(2)若查找元素17,它将依次与二叉排序树中哪些元素比较

43、大小？(3)假设每个元素的查找概率相等，试计算该树的平均查找长度ASL。(4)对该树进行中序遍历，试写出中序遍历序列。答案：25 .已知一关键字序列为(40,11,16,31,23,55,13,45,50),试生成一棵平衡的二叉排序树再从生成的平衡的二叉排序树中删除关键字45。26 设散列表的长度为13,散列函数为H(k)=k%13，给顶的关键码序列为19,14,23,01,68,20,84,27。试画出用线性探查法解决冲突时所构成的散列表。答案：26 .给出一组关键字(19,01,26,92,87,11,43,87,21)进行冒泡排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行

44、的关键字比较次数。答案：27 .设待排序序列为10,18,4,3,6,12,1,9,15,8,请给出用希尔排序每一趟的结果。增量序列取为5,3,2,1。答案：28 .对于给定键值：83,40,63,12,35,90,65,画出堆排序各趟排序的结果。答案：29 .若对序列(49,38,65,97,76,13,27,50)采用选择排序法排序，则各趟结束后序列。答案：第三章操作系统一、单项选择题1 .操作系统的功能是进行处理机管理、()管理、设备管理和文件管理。A.进程B.存储器C.硬件D.软件答案：B2 .在计算机系统中，操作系统是()/A.一般应用软件B.核心系统软件C.用户应用软件D.用户应用

45、软件答案：B3 .如果分时系统的时间片一定，那么（）,则响应时间越长。A.用户数越少B.用户数越多C.内存越少D.内存越多答案：B/4 .操作系统中采用多道程序设计技术提高CPU和外部设备的（）。A.利用率B.可靠性C.稳定性D.兼容性答案：A）5 .已知，作业的周转时间=作业完成时间一作业的到达时间。现有三个同时到达的作业J1,J2和J3,它们的执行时间分别是T1,T2和T3,且T1<T2<T3。系统按单道方式运行且采用短作业优先算法，则平均周转时间是（）+ T2+T3/+（2/3）T2 +（1/3）T3答案：C6.任何两个并发进程之间（A. 一定存在互斥关系C. 一定彼此独立无

46、关 答案：DB.（T1 +T2 + T3）/3D. T1 + （1/2）T2+T3）B. 一定存在同步关系D.可能存在同步或互斥关系7 .进程从运行状态进入就绪状态的原因可能是（）A.被选中占有处理机B.等待某一事件C.等待的事件已发生D.时间片用完答案：D8 .一作业8:00到达系统，估计运行时间为1小时，若10:00开始执行该作业，其响应比是（）8.1 答案：A9 .多道程序设计是指（）A.在实时系统中并发运行多个程序B.在分布系统中同一时刻运行多个程序C.在一台处理机上同一时刻运行多个程序D.在一台处理机上并发运行多个程序答案：D10 .文件系统采用多级目录结构后，对于不同用户的文件，其

47、文件名（）A.应该相同B.应该不同/C.可以相同，也可以不同'D.受系统约束/答案：C11 .在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减、1的情况是（）A.无上邻空闲区，也无下邻空闲区B.有上邻空闲区，但无下邻空闲区C.有下邻空闲区，但无上邻空闲区D.有上邻空闲区，也有下邻空闲区答案：D12、某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是（）。/A.9B.10C.11D.12答案：B13、操作系统的基本职能是（）。A.控制和管理系统内各种资源，有效地组织多道程序的运行B.提供用户界

48、面，方便用户使用C.提供方便的可视化编辑程序/D.提供功能强大的网络管理工具答案：A14、如果进程PA对信-号量S执行P操作，则信-号量S的值应（A.力口1B.减1C.等于0D.小于0答案：B15、通常，用户编写的程序中所使用的地址是（B.物理地址A.逻辑地址C.绝对地址答案：A16、虚拟存储管理策略可以（A .扩大物理内存容量C.扩大逻辑内存容量答案：C）。B.扩大物理外存容量D.扩大逻辑外存容量17、1在以下的文件物理存储组织形式中，（）常用于存放大型的系统文件。A连续文件B.串连文件C.索引文件D.多重索引文件答案：D18、使用户所编制的程序与实际使用的物理设备无关，这是由设备管理的（）

49、功能实现的。A.设备独立性B.设备分配C.缓冲管理D.虚拟设备/答案：A19、引入缓冲技术的主要目的是（）。/A.改善用户编程环境B.提高CPU的处理速度C.提高CPU与设备之间的并行程度/D.降低计算机的硬件成本答案：C20、银行家算法可以实现死锁的（）。A.预防B.避免C.检测D.恢复答案：B二、多项选择题1 .引入多道程序设计的主要目的在于（）A、提高实时响应速度/B、充分利用处理机，减少处理机空闲时间C、有利于代码共享D、充分利用外围设备E、减少存储器碎片答案：BD2 .段式和页式存储管理的地址结构很类似，但是它们之间有实质上的不同，表现为（）A、页式的逻辑地址是连续的，段式的逻辑地址

50、可以不连续B、页式的地址是一维的，段式的地址是二维的C、分页是操作系统进行的，分段是用户确定的D、各页可以分散存放在主存，每段必须占用连续的主存空间E、页式采用静态重定位方式，段式采用动态重定位方式答案：ABCD3 .利用记录的成组与分解操作能（）A、有效地实现信息转储B、提高存储介质的利用率C、减少操作系统的程序量D、增加启动外设的次数E、提高文件的存取速度答案：ABE4 .线程是操作系统的概念，已具有线程管理的操作系统有（）A、WindowsB、OS/2C、WindowsNTD、DOS/E、Mach答案：BCE5 .文件的二级目录结构由（）和（）组成。/A.根目录B.子目录C.主文件目录D.用户文件目录E.当前目录答案：CD6 .作业与进程的主要区别是（）和（）。A.前者是由用户提交，后者是由系统自动生成/B.两者执行不同的程序段C.前者以用户任务为单位，后者是操作系统控制的单位D.前者是批处理的，后者是分时的E.后者可并发执行，前者则不行答案：AC三、判断题1 .批处理系统的主要优点是系统的吞吐量大、资源利用率高、系统的开销较小。（）答案:T/2 .Windows2000操作系统是支持多任务的操作系统。（）答案：T3 .单级目录结构能够解决文件重名问题。（）答案：F4 .在分页存储管理中，页的大小是可以不相等的。（）答案：F5 .原语是一种不可分