[精]软件技术基础试题库

[精]软件技术基础试题库内容摘要：

二叉树对应的森林最多包含 _______________ 棵非空树。 答案： 5． 深度为 n(n0) 的二叉树最多有 _______________ 个结点。 答案： 6． n(n0) 个结点、 (n1) 条边的连通无向图中，顶点度数最大值为 _______________。 答案： 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 的最小生成树的权值之和为 ____________。 答案： 2,4,6,8,10,12,14,16,18,20 依次存放于一个一维 数组中，然后采用折半查找方法查找元素 12，被比较过的数组元素的下标依次为 _________。 答案： ，然后将其放在已经排好序的序列的合适位置。 这种排序法称为 _________排序法。 答案： ，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。 这种排序法称为 _________排序法。 答 案： (49,38,65,97,76,27,13,50)采用快速排序法进行排序，以序列的第一个元素为基准元《软件技术基础》试题库 素得到的划分结果是 __________________。 答案： 14． 一个数据结构在计算机中的表示 (映象 )称为 ________________。 答案： 15． 数据结构被形式地定义为（ D, R ），其中 D 是 的有限集合， R 是 D 上 的 有限集合。 答案： 16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的 _____无关，是独立 于计算机的。 答案： 17．一个算法具有 5 个特性 :__________、 __________、 ___________、有零个或多个输入、有一个或多个输出。 答案： 18．线性表中 ____________________________ 称为表的长度。 答案： 19．设长度为 n 的线性表顺序存贮 ,若在它的第 i1 和第 i 个元素之间插入一个元素 , 共需移动 _________ 个元素 (1i≤n)。 答案： 20．在单链表中要在已知结点 *p 之前插入一新结点，需找到。 答案： 21．循环链表的主要优点是。 答案： 从任何一个结点出发可以遍历所有结点 22．在一个单链表中删除 p 所指结点的下一个结点时，应执行以下操作： q=plink。 plink=____ __ Delete q 答案： 23．设 SQ 为循环队列，存储在数组 d[m] 中，则 SQ 出队操作对其队头指针 front 的修改是 _______________。 答案： 《软件技术基础》试题库 24．栈中元素的进出原则为 _____________________。 答案： 25．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。 该缓冲区应该是一个 结构，其主要特点是。 答案： 26．对于一个以顺序实现的循环队列 Q[0…m 1]，队头、队尾指针分别为 f、 r，其判空的条件是 ，判满的条件是。 答案： r=f、 (r+1)%m=f 27．在具有 n 个单元的循环队列中，队满时共有 _______个元素。 答案： 28．深度为 n(n0) 的二叉树最多有 _______________ 个结点。 答案： 29． n(n0) 个结点、 (n1) 条边的连通无向图中，顶点度数最大值为 _______________。 答案： 30．一棵深度为 6 的满二叉树有 ______个非终端结点。 答案： 31．若一棵二叉树中有 8 个度为 2 的结点 ,则它有 _____个叶子。 答案： 32．树中结点 A 的 ____________________ 称为 结点 A 的度。 答案： 33．一棵深度为 4 的二叉树最多有 _______ 个结点。 答案： 34．将 转化为二叉树时，其根结点的右子树总是空的。 答案： 35．哈夫曼树是带权路径长度 的树，通常权值较大的结点离根结点。 答案： 《软件技术基础》试题库 36．具有 n 个叶子的二叉树，每个叶子的权值为 wi(1≤i≤n)其中带权路径最小的二叉树被称为。 答案： 37．若已知一棵二叉树的先序序列为 – + a * b – c d / e f，中序序列为 a + b * c – d – e / f，则其后序序列为 ___________。 答案： 38．已知一棵完全二叉树中共有 768 结点，则该树中共有 _____个叶子结点。 答案： 39．已知二叉树有 50 个叶子结点，且仅有一个孩子的结点数为 30，则总结点数为。 答案： 40．具有 10 个顶点的无向图 ,边的总数最多为 _____________。 答案： 41．在有 n 个顶点的有向图中，每个顶点的度最大可达。 答案： 42．有向图 g 用 邻接矩阵 a［１ …m,1…m ］来存储，其第 i 行的所有元素之和等于顶点 i的。 答案： 43． 有 n 个球队参加的足球联赛按主客场制进行比赛，共需进行 场比赛。 答案： 44． 带权连通图 G=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．什么是 顺序表。 顺序表的 特点 是什么。 答案： 线性表的顺序存储是指在内存中用一块地址连续的存储空间顺序存放线性表的各元素，用这种形式存储的线性表称为顺序 表。 数据元素在顺序表中物理位置取决于数据元素在线性表中的逻辑位置，可得出顺序表的特点：逻辑位置相邻，其物理位置也相邻。 2．什么样的图是连通图。 答案： 在无向图 G 中，如果从一个顶点 vi 到另一个顶点 vj(i≠j)有路径，则称顶点 vi 和顶点vj 是连通的，若图中任意两顶点间都是相通的，则称此图是 连通图。 3． 二叉树有哪几种基本形态 ? 画图说明之。 答案： 六、操作题 /综合能力题 1．若对序列 (76， 38， 65， 13， 97， 27， 50， 49)采用 冒泡 排序法 (按照值的大小从小到大 )进行排序， 共需几趟排序。 请分别 在下表中写出每一趟的结果： 原始序列 76 38 65 13 97 27 50 49 答案： 共需 5 趟 第 1 趟结果 38 65 13 76 27 50 49 97 第 2 趟结果 38 13 65 27 50 49 76 97 第 3 趟结果 13 38 27 50 49 65 76 97 第 4 趟结果 13 27 38 49 50 65 76 97 第 5 趟结果 13 27 38 49 50 65 76 97 2． 若对序列 (76， 38， 65， 13， 97， 27， 50， 49)采用 选择 排 序法 (按照值的大小从小到大 )进行排序，请分别在下表中写出每一趟的结果： 原始序列 76 38 65 13 97 27 50 49 答案： 第 1 趟结果 76 38 65 13 49 27 50 97 第 2 趟结果 50 38 65 13 49 27 76 97 第 3 趟结果 50 38 27 13 49 65 76 97 第 4 趟结果 49 38 27 13 50 65 76 97 第 5 趟结果 13 38 27 49 50 65 76 97 第 6 趟结果 13 27 38 49 50 65 76 97 第 7 趟结果 13 27 38 49 50 65 76 97 3． 把 1 、 2 、 3 、 4 依次进栈（栈初始为空），任何时刻（只要栈不空），都可以出（退）《软件技术基础》试题库 栈，试写出所有可能的出栈序列（如 1234 ）。 答案： 4． 若一二叉树有 2 度结点 100 个，则其叶结点有多少个。 该二叉树可以有多少个 1 度顶点。 答案： 5． 已知某非空二叉排序树采用顺序存储结构依次将所有结点的数据信息存放于一维数组 ABDIC□EF□□C□□□H， 请分别写出该二叉树的前序遍历序列与中序遍历序列。 答案 ： 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． 试画出下列图的邻接表。 《软件技术基础》试题库 图 答案：。