软件技术基础试题库.doc

软件技术基础试题库课程名称：软件技术基础 适用专业：软件技术、计算机应用、网络、信息等计算机相关专业第一章 概述第二章 数据结构一、单项选择题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)s，link(s)pC. link(p)link(s)，link(s)pD. link(p)s，link(s)q答案：B3高度为h(h0) 的二叉树最少有_个结点。（ ）A. hB. h-1 C. h+1D. 2h答案：A4n个顶点的带权无向连通图的最小生成树包含 _ 个顶点。（）A.n-1 B.n C.n/2 D.n+1答案：B5采用拉链法解决冲突的散列表中，查找的平均查找长度( )。A. 直接与关键字个数有关 B. 直接与装填因子 a 有关 C. 直接与表的容量有关 D. 直接与散列函数有关答案：D6树型结构最适合用来描述( )A.有序的数据元素 B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据答案：C7若二叉树中度为2的结点有15个，度为1的结点有10个_个叶结点。( )A.25 B.10C.16 D.41答案：C 度0的结点比度2的结点多18若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有_个结点。( )A.32 B.33C.34 D.25答案：C9若某完全二叉树的深度为h，则该完全二叉树中至少有_个结点。( )A.2h B.2h-1C.2h-2D.2h-1+1答案：C10在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该( )A.只有左子树上的所有结点B.只有左子树上的部分结点C.只有右子树上的所有结点 D.只有右子树上的部分结点答案：A11下面关于哈夫曼树的说法，不正确的是( )A.对应于一组权值构造出的哈夫曼树一般不是唯一的B.哈夫曼树具有最小带权路径长度C.哈夫曼树中没有度为1的结点D.哈夫曼树中除了度为1的结点外，还有度为2的结点和叶结点答案：D12数据结构是一门研究计算机中 对象及其关系的学科。( )A. 数值运算B.非数值运算C.集合D.非集合答案：B13数据结构的定义为(K，R)，其中K是 的集合。( )A.算法B.数据元素C.数据操作D.逻辑结构答案：B14算法分析的目的是_。( )A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答案：C15数据的不可分割的基本单位是 。( )A.元素B.结点C.数据类型D.数据项答案：D16 是具有相同特性数据元素的集合，是数据的子集。( )A.数据符号B.数据对象C.数据D.数据结构答案：B17数据结构是研究数据的 及它们之间的相互联系。（ ）A.理想结构、物理结构B.理想结构、逻辑结构C.物理结构、逻辑结构D.抽象结构、逻辑结构答案：C18组成数据的基本单位是 。（ ）A.数据项B.数据类型C.数据元素D.数据变量答案：C19数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为 。（ ）A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构答案：C20算法指的是 。（ ）A计算机程序B解决问题的计算方法C排序算法D解决问题的有限运算序列答案：D21. 由_组成的集合是一个数据对象。( )A.不同类型的数据项B.不同类型的数据元素C.相同类型的数据项D.相同类型的数据元素答案：D22关于顺序存储的叙述中,哪一条是不正确的。( )A.存储密度大B.逻辑上相邻的节点物理上不必邻接C.可以通过计算直接确定第i个节点的位置D.插入、删除操作不方便答案：B23一个向量第一个元素的存储地址是 100 ，每个元素的长度为 2 ，则第 5 个元素的地址是 。（ ）A.110B.108C.100D.120 答案：B24已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为 。（ ）A.da+(i-1)*mB.da+i*mC.da-i*mD.da+(i+1)*m答案：A25链表是一种采用 存储结构存储的线性表。（ ） A.顺序B.链式C.星式D.网状答案：B26线性表若采用链式存储结构时，要求内存中可用存储单元的地址 。（ ）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以答案：D27线性表在 情况下适用于使用链式结构实现。 ( )A.需经常修改中的结点值B.需不断对进行删除插入C.中含有大量的结点D.中结点结构复杂答案：B28在长度为 n 的顺序表的第 i (1in+1) 个位置上插入一个元素，元素的移动次数为 。（ ）A.n-i+1B.n-iC.iD.i-1答案：A29线性表是 。（ ）A.一个有限系列，可以为空B.一个有限系列，不能为空C.一个无限系列，可以为空D.一个无限系列，不能为空答案：A30. _是线性表。( )A.(孔子,诸葛亮,曹雪芹)B.A,B,C,DC.10,11,12,13,14D.(1,2,3,.)答案：A31. _ 是表示线性数据结构的。( )A.循环链表B.邻接多重表C.孩子链表D.单链表答案：D32. 将线性表的数据元素以_结构存放, 查找一个数据元素所需时间不依赖于表长。( )A.循环双链表B.哈希(Hash)表C.一维数组D.单链表答案：C33. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。( )A.s-link=p;p-link=s;B.s-link=p-link;p-link=s;C.s-link=p-link;p=s;D.p-link=s;s-link=p;答案：34. 在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是_。( )A.current-link=NULLB.first-link=currentC.first=currentD.current-link=first答案：35. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。( )A.NB.n/2C.(n-1)/2D.(n+1)/2答案：36. 用链表表示线性表的优点是_。 ( ) A. 便于随机存取B. 花费的存储空间比顺序表少C. 便于插入与删除D. 数据元素的物理顺序与逻辑顺序相同答案：37. 当需要随机查找线性表的元素时,宜采用_作存储结构。( )A.双向链表B.循环链表C.顺序表D.单链表答案：38. 线性表的链接实现有利于 运算。( )A.插入B.读表元C.查找D.定位答案：39. 线性表采用链式存储时，其地址_。 ( ) A.必须是连续的B.部分地址是连续的C.一定是不连续的D.连续与否均可以答案：40. 设单链表中指针p指着结点a，若要删除a之后的结点（若存在），则需要修改指针的操作为_。 ( ) A.p-next=p-next-nextB.p=p-nextC.p= p-next-nextD.p-next=p答案：A41. 向一个有127个元素顺序表中插入一个新元素并保存原来顺序不变，平均要移动 个元素。( )A.64B.63.5C.63D.64.5答案：A42. 向一个有 127 个元素的顺序表中删除一个元素，平均要移动 个元素。( )A.8B.63.5C.63D.7答案：C43_又称为FIFO表。( )A.队列B.散列表C.栈D.哈希表答案：A44设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有_。( )A.a.b,c,dB.a,d,c,bC.b,a,d,cD.c,d,a,b答案：D45. 链式栈与顺序栈相比，一个比较明显的优点是_。( )A. 插入操作更加方便B. 通常不会出现栈满的情况C. 不会出现栈空的情况D. 删除操作更加方便答案：46. 在一个顺序存储的循环队列中，队头指针指向队头元素的_。( )A. 前一个位置B. 后一个位置C. 队头元素位置D. 队尾元素的前一位置答案：47. 若一个栈的输入序列是1，2，3n，则输出序列的第一个元素是n，则第i个输出元素是_。( )A.n-iB.iC.n-i+1D.n-i-1答案：C48. 栈的数组表示中，top为栈顶指针，栈空的条件是_。( )A.top=0B.top=maxSizeC.top=maxSizeD.top=-1答案：D49. 在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是_。( )A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeD.rear=front答案：B50. 栈和队列的共同特点是_。( )A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除D.没有共同点答案：C51若非空队列采用链式存储结构，front和rear分别为队头元素与队列尾元素的指针，删除此时队列的一个元素的操作时依次执行pfront，_ ，call RET(P)。( )A.frontlink(rear)B.rearlink(p)C.rearlink(front)D.frontlink(p)答案：52由两个栈共享一个向量空间的好处是_。( )A减少存取时间，降低下溢发生的机率B节省存储空间，降低上溢发生的机率C减少存取时间，降低上溢发生的机率D节省存储空间，降低下溢发生的机率答案：53数组datam为循环队列的存储空间, front为队头指针, rare为队尾指针,则执行入队的操作为_。( )A.rare=rare+1B.rare=(rare+1)%(m-1)C.rare=(rare-1)%mD.rare=(rare+1)%m答案：D54. 将递归算法转换成对应的非递归算法时，通常需要使用_。( )A.栈B.队列C.链表D.数组答案：55高度为 h(h0) 的二叉树最少有 _ 个结点。( )A.hB.h-1C.h+1D.2h答案：A56树型结构最适合用来描述_。( )A.有序的数据元素B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据答案：C57有n(n0)个结点的完全二叉树的深度是_。( )A.log2(n)B.log2(n)+1C.log2(n+1)D.log2(n)+1答案：BD58. _ 又是一棵满二叉树。( )A.二叉排序树B.深度为5有31个结点的二叉树C.有15个结点的完全二叉树D.哈夫曼(Huffman)树(没有度为1的结点)答案：C59. 深度为k的满二叉树有_个分枝结点。( )A.2k-1B.2k-1-1C.2k+1D.2k-1+1答案：60. 若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为_。( )A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE答案：A61. 二叉树第i(i=1)层上至多有 结点。( )A.iB.iC.iD.i答案：C62. 在一棵具有5层的满二叉树中结点总数为_。( )A. 31B. 32C. 33D. 16答案：A63. 一个二叉树按顺序方式存储在一个维数组中，如图0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ则结点E在二叉树的第 层。( )A.1B.2C.3D.4答案：C64在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为_。( )A4B5C6D7答案：C65n 个顶点的带权无向连通图的最小生成树包含 _ 个顶点。( )A.n-1B.nC.n/2D.n+1答案：B66具有 n 个顶点的有向完全图有 条弧。( )A.nB.n*(n-1)C.n*(n+1)D.n*n答案：B67. n 个顶点的连通图至少有 条边。( )A.n-1 B.n C.n+1 D.0答案：68在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 倍。( )A1/2B1C2D4答案：69在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为_。( )AeB2eCn2eDn22e答案：D70折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素_进行比较。( )A.65,15,37B.68,30,37C.65,15,30D.65,15,30,37答案：D71对有3600个记录的索引顺序表(分块表)进行查找,最理想的块长为_。( )A.1800B.60C.1200D.log2 3600答案：B72. 折半查找20个记录的有序表,若查找失败,比较关键字的次数_。( )A.最多为6B.最多为5C.最多为4D.最多为3答案：B73. 中序遍历一棵二叉排序树所得到的结点序列是键值的 序列。( )A.递增或递减B.递减C.递增D.无序答案：C74散列表中的冲突是指_。( )A.两个元素具有相同的序号B.两个元素的键值相同，而其他属性相同C.不同的键值对应相同的存储地址D.数据元素的地址相同答案：75用线形探测法查找散列表，可能要探测多个散列地址，这些位置上的键值_。( )A.一定是同义词B.不一定是同义词C.一定不是同义词D.都相同答案：76在初始为空的杂凑表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT，SUN), 杂凑函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为0:6，采用线性再散列法处理冲突。插入后的杂凑表应该如_所示。( )A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MONB. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MONC. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MOND. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON答案：77设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳 个表项。（设搜索成功的平均搜索长度为Snl=(1+1/(1-a)/2,其中a 为装填因子）( )A.400B.526C.624D.676答案：78对长度为10的表作选择(简单选择)排序,共需比较_次关键字。( )A.45B.90C.55D.110答案：79. 设有100个数据元素，采用折半搜索时，最大比较次数为 ( )。A. 6B. 7C. 8D. 10答案：A80. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是_。( )A. 选择排序B. 直接插入排序C. 快速排序D. 起泡排序答案：C81. 对5个不同的数据元素进行直接插入排序，最多需要进行 次比较。( )A. 8B. 10C. 15D. 25答案：82. 采用折半查找方法进行查找，数据文件应为 ，且限于 。( )A.有序表 顺序存储结构B.有序表 链式存储结构C.随机表 顺序存储结构D.随机表 链式存储结构答案：A83. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其存放在已排序序列的合适位置，该排序方法称为 排序法。( )A.插入B.选择C.希尔D.二路并归答案：A84. 就平均查找速度而言，下列几种查找速度从慢至快的关系是 。( )A.顺序 折半 哈西 分块B.顺序 分块 折半 哈西C.分块 折半 哈西 顺序D.顺序 哈西 分块 折半答案：B85. 在下列算法中， 算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。( )A.堆排序B.冒泡排序C.插入排序D.快速排序答案：C86堆是一个键值序列( K1, K2, , Kn )，对 I = 1,2n/2, 满足 。( )A.Ki = K2i = K2i+1B.Ki K2i+1 K2i C.Ki = K2i 且 Ki =K2i+1D. Ki = K2i 或 Ki 0) 个结点二叉树对应的森林最多包含_ 棵非空树。答案：5深度为 n(n0) 的二叉树最多有 _ 个结点。 答案：2的n次方-16n(n0) 个结点、 (n-1) 条边的连通无向图中，顶点度数最大值为 _ 。 答案：2（n-1）7在一个图中，所有顶点的度数之和等于所有边的数目的_2_倍。答案：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,14,16,18,20依次存放于一个一维数组中，然后采用折半查找方法查找元素12，被比较过的数组元素的下标依次为_。答案：11.每趟排序从未排序的子序列中依次取出元素与已经排好序的序列中元素进行比较，然后将其放在已经排好序的序列的合适位置。这种排序法称为_简单选择_排序法。答案：12.从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为_快速_排序法。答案：13.对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序，以序列的第一个元素为基准元素得到的划分结果是_。答案：38 27 13 49 65 97 76 50 14一个数据结构在计算机中的表示(映象)称为 _。答案：15数据结构被形式地定义为（ D, R ），其中 D 是 数据元素 的有限集合， R 是 D 上的 有限集合。 答案：16数据的逻辑结构是从逻辑关系上描述数据，它与数据的_无关，是独立于计算机的。答案：17一个算法具有5个特性:_、_、_、有零个或多个输入、有一个或多个输出。答案：18线性表中 _ 称为表的长度。答案：19设长度为n的线性表顺序存贮,若在它的第i-1和第i个元素之间插入一个元素, 共需移动 _ 个元素(1link;p-link=_ _Delete q答案：23设 SQ 为循环队列，存储在数组 dm 中，则 SQ 出队操作对其队头指针 front 的修改是 _ 。答案：24栈中元素的进出原则为 _先进后出_ 。答案：25在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个 结构，其主要特点是 。答案：26对于一个以顺序实现的循环队列Q0m-1，队头、队尾指针分别为f、r，其判空的条件是f=r ，判满的条件是 (r+1)%m=f 。答案：r=f、(r+1)%m=f27在具有n个单元的循环队列中，队满时共有_个元素。答案：28深度为 n(n0) 的二叉树最多有 _ 个结点。答案：2的n次方-129n(n0) 个结点、 (n-1) 条边的连通无向图中，顶点度数最大值为 _2（n-1）_ 。答案：30一棵深度为6的满二叉树有_31_个非终端结点。答案：31若一棵二叉树中有8个度为2的结点,则它有_9_个叶子。答案：32树中结点A的 _拥有的后件个数_ 称为结点A的度。答案：33一棵深度为4的二叉树最多有 _15_ 个结点。答案：34将 树转化为二叉树时，其根结点的右子树总是空的。答案：35哈夫曼树是带权路径长度 最小 的树，通常权值较大的结点离根结点 近 。答案：36具有n个叶子的二叉树，每个叶子的权值为wi(1in)其中带权路径最小的二叉树被称为 哈夫曼树（最优二叉树） 。答案：37若已知一棵二叉树的先序序列为 + a * b c d / e f，中序序列为a + b * c d e / f，则其后序序列为_。答案：38已知一棵完全二叉树中共有768结点，则该树中共有_个叶子结点。答案：39已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为 129 。答案：50+30+49=12940具有10个顶点的无向图,边的总数最多为 _ 。答案：41在有n个顶点的有向图中，每个顶点的度最大可达 n-1 。答案：42有向图g用邻接矩阵am,1m来存储，其第i行的所有元素之和等于顶点i的。答案：43有n个球队参加的足球联赛按主客场制进行比赛，共需进行 场比赛。答案：44带权连通图G=，其中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什么是顺序表？顺序表的特点是什么？答案：线性表的顺序存储是指在内存中用一块地址连续的存储空间顺序存放线性表的各元素，用这种形式存储的线性表称为顺序表。数据元素在顺序表中物理位置取决于数据元素在线性表中的逻辑位置，可得出顺序表的特点：逻辑位置相邻，其物理位置也相邻。2什么样的图是连通图？答案：在无向图G中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和顶点vj是连通的，若图中任意两顶点间都是相通的，则称此图是连通图。3二叉树有哪几种基本形态? 画图说明之。答案：二叉树，满二叉树，完全二叉树六、操作题/综合能力题1若对序列(76，38，65，13，97，27，50，49)采用冒泡排序法(按照值的大小从小到大)进行排序，共需几趟排序？请分别在下表中写出每一趟的结果：5分所以应该写5趟原始序列 76 38 65 13 97 27 50 49答案：共需5趟第1趟结果3865137627504997第2趟结果3813652750497697第3趟结果1338275049657697第4趟结果1327384950657697第5趟结果13273849506576972若对序列(76，38，65，13，97，27，50，49)采用选择排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟的结果：原始序列 76 38 65 13 97 27 50 49答案：第1趟结果7638651349275097第2趟结果5038651349277697第3趟结果5038271349657697第4趟结果4938271350657697第5趟结果1338274950657697第6趟结果1327384950657697第7趟结果13273849506576973把 1 、 2 、 3 、 4依次进栈（栈初始为空），任何时刻（只要栈不空），都可以出（退）栈，试写出所有可能的出栈序列（如 1234 ）。 答案：4若一二叉树有 2 度结点 100个，则其叶结点有多少个？该二叉树可以有多少个 1 度顶点？答案：叶结点101个 1度结点可以有 101个5已知某非空二叉排序树采用顺序存储结构依次将所有结点的数据信息存放于一维数组ABDICEFCH，请分别写出该二叉树的前序遍历序列与中序遍历序列。答案：6二叉树的顺序存储结构:答案：7给定30个字符组成的电文:D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D试为字符 A、B、C、D、E、F 设计哈夫曼(Huffman)编码。 (1)画出相应的哈夫曼树； (2)分别列出 A、B、C、D、E、F 的哈夫曼码；(3)计算该树的带权路径长度WPL。答案：8试将森林 F= T1,T2,T3,T4 转换为一棵二叉树。 T1 T2 T3 T4答案：9试画出下列二叉树的中序线索二叉树存储结构图。 二叉树答案：10试用孩子兄弟(左孩子右兄弟)表示法画出下列树的存储结构图。 树答案：11已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,F,E,G和D,C,A,F,G,E,B, 试画出该二叉树。答案：12试用双亲表示法画出下列树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某二叉树的结点数据采用顺序存储表示如下：(1) 试画出此二叉树的图形表示。(2) 写出结点D的双亲结点及左、右子女。(3) 将此二叉树看作森林的二叉树表示，试将它还原为森林。答案：16图的邻接矩阵:答案：17有向图的逆邻接表: 答案：18找出下面网络的最小生成树。 答案：19找出下面网络的最小生成树:答案：20试画出下列图的邻接表。 图答案：21对下面的带权无向图采用prim算法从顶点 开始构造最小生成树。（写出加入生成树顶点集合S和选择边Edge的顺序）S:顶点号Edge:(顶点，顶点，权值)( ， ， )( ， ， ) ( ， ， )( ， ， )( ， ， ) 答案：5462311015410304101522022对图所示有向图，试用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行算法过程中扩充结点的每次循环状态。答案：23已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH中，边的信息存放于邻接矩阵中，邻接矩阵为0 1 1 0 0 0 0 01 0 0 0 1 0 1 11 0 0 1 0 1 0 00 0 1 0 0 1 0 00 1 0 0 0 0 0 10 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 请写出从顶点A出发对该图进行深度有限搜索后得到的顶点序列。答案：24试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。 (1)试画出插入完成之后的二叉排序树； (2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小? (3)假设每个元素的查找概率相等,试计算该树的平均查找长度ASL。 (4)对该树进行中序遍历,试写出中序遍历序列。答案：25已知一关键字序列为（40，11，16，31，23，55，13，45，50），试生成一棵平衡的二叉排序树,再从生成的平衡的二叉排序树中删除关键字45。3设散列表的长度为13，散列函数为H(k) = k % 13，给顶的关键码序列为19, 14, 23, 01, 68, 20, 84, 27。试画出用线性探查法解决冲突时所构成的散列表。答案：26给出一组关键字（19，01，26，92，87，11，43，87，21）进行冒泡排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。答案：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.用户应用软件答案：B3. 如果分时系统的时间片一定，那么（ ），则响应时间越长。A.用户数越少 B.用户数越多C.内存越少 D.内存越多答案：B4. 操作系统中采用多道程序设计技术提高CPU和外部设备的（ ）。A.利用率 B.可靠性 C.稳定性 D.兼容性答案：A5.已知，作业的周转时间=作业完成时间作业的到达时间。现有三个同时到达的作业J1，J2和J3，它们的执行时间分别是T1，T2和T3，且T1T2T3。系统按单道方式运行且采用短作业优先算法，则平均周转时间是()A.T1T2T3 B.(T1T2T3)/3C.T1(2/3)T2(1/3)T3D.T1(1/2)T2T3答案：C6.任何两个并发进程之间()A.一定存在互斥关系B.一定存在同步关系C.一定彼此独立无关D.可能存在同步或互斥关系答案：D7.进程从运行状态进入就绪状态的原因可能是()A.被选中占有处理机 B.等待某一事件C.等待的事件已发生 D.时间片用完答案：D8.一作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业，其响应比是()A.2 B.1 C.3 D.0.5答案：A9.多道程序设计是指()A.在实时系统中并发运行多个程序B.在分布系统中同一时刻运行多个程序C.在一台处理机上同一时刻运行多个程序D.在一台处理机上并发运行多个程序答案：D10.文件系统采用多级目录结构后，对于不同用户的文件，其文件名()A.应该相同 B.应该不同C.可以相同，也可以不同 D.受系统约束答案：C11.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减1的情况是()A. 无上邻空闲区，也无下邻空闲区B. 有上邻空闲区，但无下邻空闲区C. 有下邻空闲区，但无上邻空闲区D.有上邻空闲区， 也有下邻空闲区答案：D12、某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是（ ）。A9 B10 C11 D12答案：B13、操作系统的基本职能是（ ）。A控制和管理系统内各种资源，有效地组织多道程序的运行 B提供用户界面，方便用户使用 C提供方便的可视化编辑程序D提供功能强大的网络管理工具答案：A14、如果进程PA对信号量S执行P操作，则信号量S的值应（ ）。A加1 B减1 C等于0 D小于0答案：B15、通常，用户编写的程序中所使用的地址是（ ）。A逻辑地址 B物理地址 C绝对地址 D内存地址答案：A16、虚拟存储管理策略可以（ ）。A扩大物理内存容量 B扩大物理外存容量 C扩大逻辑内存容量