计算机软件基础试题

1、文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持软件技术基础试题库课程名称：软件技术基础适用专业：软件技术、计算机应用、网络、信息等计算机相关专业第一章概述第二章数据结构一、单项选择题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(

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

3、数据D.数据元素之间没有关系的数据答案： C7若二叉树中度为2 的结点有15 个，度为1 的结点有10 个 个叶结点。()A.25B.10C.16D.41答案： C8 若深度为6 的完全二叉树的第6 层有 3 个叶结点，则该二叉树一共有个结点。 ()A.32B.33C.34D.25答案： C9若某完全二叉树的深度为h，则该完全二叉树中至少有个结点。()A.2hB.2h-1C.2h-2D.2h-1+1答案： C10在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该( )A. 只有左子树上的所有结点B.只有左子树上的部分结点C.只有右子树上的所有结点D.只有右子树上的部分结点答案： A11 下

4、面关于哈夫曼树的说法，不正确的是( )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.分析算法的易懂性和文档性答案

5、： C15数据的不可分割的基本单位是。 ( )A. 元素B.结点C.数据类型D.数据项答案： D16 是具有相同特性数据元素的集合，是数据的子集。( )A. 数据符号B.数据对象C.数据D.数据结构答案： B17数据结构是研究数据的及它们之间的相互联系。()A. 理想结构、物理结构B.理想结构、逻辑结构C.物理结构、逻辑结构D.抽象结构、逻辑结构答案： C3文档收集于互联网，如有不妥请联系删除文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持18组成数据的基本单位是。 （）A. 数据项B.数据类型C.数据元素D.数据变量答案： C19 数据在计算机存储器内表示时，物理地址与逻辑地址

6、相同并且是连续的，称为。 （）A. 存储结构B.逻辑结构C.顺序存储结构D.链式存储结构答案： C20算法指的是。 （）A计算机程序B 解决问题的计算方法C排序算法D 解决问题的有限运算序列答案： D21. 由 组成的集合是一个数据对象。（ ）A. 不同类型的数据项B.不同类型的数据元素C.相同类型的数据项D.相同类型的数据元素答案： D22关于顺序存储的叙述中,哪一条是不正确的。（）A. 存储密度大B.逻辑上相邻的节点物理上不必邻接C.可以通过计算直接确定第i 个节点的位置D.插入、删除操作不方便答案： B23一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第 5 个元素的地

7、址是。 （）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.需

8、不断对进行删除插入C.中含有大量的结点D.中结点结构复杂答案： B28在长度为n 的顺序表的第i （1 i n+个位置上插入一个元素，元素的移动次数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. 将线性表的数据元素

9、以结构存放, 查找一个数据元素所需时间不依赖于表长。( )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 是否达到链表表

10、尾的语句是。 ( )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.循环

11、链表C.顺序表D.单链表答案：38. 线性表的链接实现有利于运算。 ()A. 插入7文档收集于互联网，如有不妥请联系删除.文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持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->n

12、ext=p答案： A41. 向一个有127 个元素顺序表中插入一个新元素并保存原来顺序不变，平均要移动个元素。 ( )A.64B.63.5C.63D.64.5答案： A42. 向一个有127 个元素的顺序表中删除一个元素，平均要移动个元素。( )A.8B.63.5C.63D.7答案： C43. 又称为 FIFO 表。 ( )A. 队列B.散列表C.栈D.哈希表答案：44. 设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有。 ( )A.a.b,c,dB.a,d,c,bC.b,a,d,cD.c,d,a,b答案：45. 链式栈与顺序栈相比，一个比较明显的优点是。 ( )A. 插入

13、操作更加方便B. 通常不会出现栈满的情况C. 不会出现栈空的情况D. 删除操作更加方便答案：46. 在一个顺序存储的循环队列中，队头指针指向队头元素的。 ( )A. 前一个位置B. 后一个位置C. 队头元素位置D. 队尾元素的前一位置答案：47. 若一个栈的输入序列是1 ， 2， 3n，则输出序列的第一个元素是n，则第i 个输出元素是 。 ( )A.n-iB.iC.n-i+1D.n-i-1答案：48. 栈的数组表示中，top 为栈顶指针，栈空的条件是。 ( )A.top=0B.top=maxSizeC.top=maxSizeD.top=-1答案：49. 在数组表示的循环队列中，front、 r

14、ear 分别为队列的头、尾指针，maxSize 为数组的最大长度，队满的条件是。 ( )A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeD.rear=front答案：50. 栈和队列的共同特点是。 ( )A. 都是先进后出B.都是先进先出C.只允许在端点处插入和删除9文档收集于互联网，如有不妥请联系删除.文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持D.没有共同点答案：51若非空队列采用链式存储结构，front 和 rear 分别为队头元素与队列尾元素的指针，删除此时队列的一个元素的操作时依次执行pfront， ， ca

15、ll RET(P) 。 ( )A.front link(rear)B.rear link(p)C.rear link(front)D.front link(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=(ra

16、re+1)%m答案：54. 将递归算法转换成对应的非递归算法时，通常需要使用。 ( )A. 栈B.队列C.链表D.数组答案：55高度为h(h>0) 的二叉树最少有 个结点。( )A.hB.h-1C.h+1D.2h答案：56树型结构最适合用来描述。 ( )A. 有序的数据元素B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据答案：57. 有 n(n>0)个结点的完全二叉树的深度是。 ( )A. log2(n)B. log2(n)+1C. log2(n+1)D. log2(n)+1答案：58. _ 又是一棵满二叉树。( )A. 二叉排序树B.深度为5有

17、 31个结点的二叉树C.有 15 个结点的完全二叉树D.哈夫曼(Huffman) 树答案：59. 深度为k的满二叉树有个分枝结点。( )A.2 k-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答案：62. 在一棵具有5 层的满二叉树中结点总数为。 ( )A. 31B. 32C. 33D. 16答案：63. 一个

18、二叉树按顺序方式存储在一个维数组中，如图01234567891011 1213 14A B C DE FGHI J则结点 E 在二叉树的第层。 ( )A.1B.2C.3D.4 答案：64在一棵度为3 的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为 。 ( )A 4B 5C 6D 7 答案：65 n 个顶点的带权无向连通图的最小生成树包含 个顶点。()A.n-1B.nC.n/2D.n+1 答案：66 具有 n 个顶点的有向完全图有条弧。 ( )A.nB.n*(n-1)C.n*(n+1)D.n*n 答案：67 n 个顶点的连通图至少有条边。 ( )A.n-1B.nC.n

19、+1D.0 答案：68在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。 ( )A 1/2B 1C 2D 4答案：69在含n 个顶点和e 条边的无向图的邻接矩阵中,零元素的个数为。 ( )A eB 2eC n2 eD n2 2e答案： 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答案：71 对有 3600 个记录的索引顺序表(分块表)进行查找,最理想的块长为_。 ( )A.1800B.60C.1200D. lo

20、g2 3600答案： B72. 折半查找20个记录的有序表,若查找失败,比较关键字的次数。 ( )A. 最多为6B.最多为5C.最多为4D.最多为3答案： B73. 中序遍历一棵二叉排序树所得到的结点序列是键值的序列。 ( )A. 递增或递减B.递减C.递增D.无序答案：74散列表中的冲突是指。 ( )A. 两个元素具有相同的序号B.两个元素的键值相同，而其他属性相同C.不同的键值对应相同的存储地址D.数据元素的地址相同答案：75 用线形探测法查找散列表，可能要探测多个散列地址，这些位置上的键值。 ( )A. 一定是同义词B.不一定是同义词C.一定不是同义词13文档收集于互联网，如有不妥请联系

21、删除文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持D.都相同答案：76在初始为空的杂凑表中依次插入关键字序列(MON ， TUE ， WED ， THU ， FRI ， SAT，SUN), 杂凑函数为H(k)=i MOD 7 ， 其中， i 为关键字k 的第一个字母在英文字母表中的序号，地址值域为0:6 ，采用线性再散列法处理冲突。插入后的杂凑表应该如所示。 ( )A. 0123456THU TUE WED FRI SUN SAT MONB. 0123456TUE THU WED FRI SUN SAT MONC. 0123456TUE THU WED FRI SAT SUN

22、MOND. 0123456TUE 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答

23、案：80. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是。 ( )A. 选择排序B. 直接插入排序C. 快速排序D. 起泡排序答案： C81. 对 5 个不同的数据元素进行直接插入排序，最多需要进行次比较。( )A. 8B. 10C. 15D. 25答案：82. 采用折半查找方法进行查找，数据文件应为，且限于。 ( )A. 有序表顺序存储结构B.有序表链式存储结构C.随机表顺序存储结构D.随机表链式存储结构答案：83. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其存放在已排

24、序序列的合适位置，该排序方法称为排序法。()A. 插入B.选择C.希尔D.二路并归答案：84. 就平均查找速度而言，下列几种查找速度从慢至快的关系是。 ( )A. 顺序折半哈西分块B.顺序分块折半哈西C.分块折半哈西顺序D.顺序哈西分块折半答案：B85. 在下列算法中，算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。()A. 堆排序B.冒泡排序C.插入排序D.快速排序答案： C86堆是一个键值序列( K1, K2, , Kn )，对I = 1,2 n/2满足,。 ( )A.K i <= K 2i <= K 2i+1B.Ki < K 2i+1 <

25、 K2iC.Ki <= K 2i 且 Ki <=K 2i+1D. K i <= K2i 或Ki <= K 2i+1答案：87对于关键字序列46 ，58 ，15 ，45 ，90 ，18 ，10 ，6215文档收集于互联网，如有不妥请联系删除.文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持。( )A.1545184610625890B.1015184546586290C.1018154546905862D.1510184546625890答案：88用某种排序方法对关键字序列(25， 84， 21， 47， 15， 27， 68， 35， 20)进行排序时，序

26、列的变化情况如下：20， 15， 21， 25， 47， 27，68， 35， 8415， 20， 21， 25， 35， 27，47， 68， 8415， 20， 21， 25， 27， 35，47， 68， 84则所采用的排序方法是。 ( )A. 选择排序B.希尔排序C.归并排序D.快速排序答案：89下列关键字序列中是堆。 ( )A16，72，31，23，94，53B94，23，31，72，16，53C16，53，23，94，31 ，72D16，23，53，31，94，72答案：90目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是。 ( )A插入排序B 直接

27、选择排序C快速排序D冒泡排序答案：B91对n 个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为。 ( )A n+1B nC n-1D n(n-1)/2答案：二、多项选择题1 根据数据元素之间的不同特性，通常具有这几种基本数据结构。( )A. 集合B. 线形结构C. 树型结构D. 图型结构答案： ABCD2数据元素之间的关系在计算机中有两种不同的表示方法。( )A. 顺序存储结构B. 二叉树存储结构C. 链式存储结构D. 网络结构答案： AC3查找哈希(Hash)表 ,解决冲突的的方法有_。 ( )A. 除留余数法B.线性探测再散列法C.直接地址法D.链地址法答案： BD三、判断题1

28、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( )答案：F2数组是一种没有插入与删除操作的线性结构。( )答案：T3非空线性表中任意一个数据元素都有且仅有一个直接后继元素。()答案：F4数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。(答案：F5线性链表中各个链结点之间的地址不一定要连续。()答案：T6若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。()答案：F7 .若线性表采用顺序存储结构，每个数据元素占用4 个存储单元，第12 个数据元素的存储地址为 144，则第 1 个数据元素的存储地址是101。 ()答案：F8 .若长度为n 的线

29、性表采用顺序存储结构，删除表的第i 个元素之前需要移动表中n-i+1 个元素。()答案：F9 .符号link(p) 出现在表达式中表示p所指的那个结点的内容。()答案：F10 .要将指针p移到它所指的结点的下一个结点是执行语句plink(p)。 ()答案：T11 .在非空线性链表中由p 所指的结点后面插入一个由q 所指的结点的过程是依次执行语句：link(q) link(p);link(p) 。 ( q )答案： T12 . 在非空双向循环链表中由q 所指的结点后面插入一个由p 指的结点的动作依次为：llink(p) q,rlink(p) rlink(q),rlink(q) p,llink。

30、(rl(i nk(q) )p答案：F13 .若某堆栈的输入序列为1,2,3,4，则4,3,1,2 不可能是堆栈的输出序列之一。()答案：T14 . 删 除 非 空 链 式 存 储 结 构 的 堆 栈 ( 设 栈 顶 指 针 为 top) 的 一 个 元 素 的 过 程 是 依 次 执行 :p top,top link(p),call RET(p)。 ()答案： T15 .若队列采用链式存储结构，队头指针与指针分别为front 和rear，向队列中插入一个数据信息为 item 的新元素的过程是依次执行:call GETNODE(p),d ata(P) item,rear p,front 。p()

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

32、。( )答案：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) 个结点二叉树对应的森林最多包含 棵非空树。答案：5深度为n

33、(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,

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

35、素为基准元素得到的划分结果是。答案：14一个数据结构在计算机中的表示(映象 )称为 ?。答案：15数据结构被形式地定义为(D, R ) ，其中 D 是的有限集合，R 是 D 上的有限集合。答案：16 数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关， 是独立于计算机的。答案：17一个算法具有5 个特性 :、 、 、有零个或多个输入、21文档收集于互联网，如有不妥请联系删除文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持有一个或多个输出。答案：18线性表中 称为表的长度。答案：19设长度为n 的线性表顺序存贮,若在它的第i-1 和第 i 个元素之间插入一个元素, 共需移动 个元

36、素 (1<i n。 )答案：20在单链表中要在已知结点*p 之前插入一新结点，需找到。答案：21循环链表的主要优点是。答案：从任何一个结点出发可以遍历所有结点22在一个单链表中删除p 所指结点的下一个结点时，应执行以下操作：q=p->link;p->link=_Delete q答案：23设SQ 为循环队列，存储在数组dm 中，则 SQ 出队操作对其队头指针front 的修改是 。答案：24栈中元素的进出原则为 。答案：25 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应

37、该是一个结构，其主要特点是。答案：26对于一个以顺序实现的循环队列Q0 m -1，队头、队尾指针分别为f、 r，其判空的条件是，判满的条件是。答案： r=f、 (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

38、将转化为二叉树时，其根结点的右子树总是空的。答案：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 个顶点的有向图中，每

39、个顶点的度最大可达。答案：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 个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至

40、少为_次 , 最多为 次；若查找失败,比较关键字的次数为次。答案：46 在单链表上难以实现的排序方法有、和。答案：快速排序、堆排序、希尔排序五、简答题/问答题/综述题1 什么是顺序表？顺序表的特点是什么？答案：线性表的顺序存储是指在内存中用一块地址连续的存储空间顺序存放线性表的各元素， 用这种形式存储的线性表称为顺序表。数据元素在顺序表中物理位置取决于数据元素在线性表中的逻辑位置，可得出顺序表的特点：逻辑位置相邻，其物理位置也相邻。2什么样的图是连通图？答案：在无向图G 中，如果从一个顶点vi 到另一个顶点vj（i 有路径，则称顶点 j）vi和顶点vj 是连通的，若图中任意两顶点间都是相通的，

41、则称此图是连通图 。3二叉树有哪几种基本形态? 画图说明之。答案：六、操作题/综合能力题1 若对序列（76，38，65，13，97，27，50，49）采用冒泡排序法（按照值的大小从小到大）原始序列763865139727答案：共需5 趟第 1 趟结果386513 76275049第 2 趟结果381365 27504976第 3 趟结果133827 50496576第 4 趟结果132738 49506576第 5 趟结果132738 495065762若对序列(76，38，65， 13，97，27，50，进行排序，请分别在下表中写出每一趟的结果：原始序列763865139727答案：第 1

42、趟结果763865 13492750第 2 趟结果503865 13492776第 3 趟结果503827 13496576第 4 趟结果493827 13506576第 5 趟结果133827 49506576第 6 趟结果132738 49506576第 7 趟结果132738 495065763 把 1 、2 、3 、4 依次进栈（栈初始为空）进行排序，共需几趟排序？请分别在下表中写出每一趟的结果：栈，试写出所有可能的出栈序列（如1234 ） 。5049979797979749）采用选择排序法（按照值的大小从小到大）504997979797979797， 任何时刻（只要栈不空）， 都可以

43、出（退）答案：4若一二叉树有2 度结点 100 个，则其叶结点有多少个？该二叉树可以有多少个1 度顶点？答案：5已知某非空二叉排序树采用顺序存储结构依次将所有结点的数据信息存放于一维数组ABDIC EFCH，请分别写出该二叉树的前序遍历序列与中序遍历序列。答案：6二叉树的顺序存储结构 答案：25文档收集于互联网，如有不妥请联系删除文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持.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 设计哈夫曼(H

44、uffman) 编码。(1) 画出相应的哈夫曼树；(2)分别列出A、 B、 C、 D、 E、 F 的哈夫曼码；(3)计算该树的带权路径长度WPL。答案：8试将森林F= T1,T2,T3,T4 转换为一棵二叉树。T1 T2 T3T4答案：9试画出下列二叉树的中序线索二叉树存储结构图。二叉树答案：10试用孩子兄弟(左孩子右兄弟)表示法画出下列树的存储结构图。树答案：11 已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,F,E,G 和 D,C,A,F,G ,E,B,试画出该二叉树。答案：12试用双亲表示法画出下列树T 的存储结构图。答案：13假定后序遍历二叉树的结果是A,C,B(1)试

45、画出所有可得到这一结果的不同形态的二叉树；(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找出下面网络的最小生成树答

46、案：20试画出下列图的邻接表。图答案：21 对下面的带权无向图采用prim 算法从顶点 开始构造最小生成树。(写出加入生成树顶点集合S 和选择边Edge 的顺序)S:顶点号Edge:(顶点，顶点，权值)（，）（，）（，）（，）（，）答案：22对图所示有向图，试用Dijkstra 算法求出从源点1 到其它各顶点的最短路径，并写出执行算法过程中扩充结点的每次循环状态。23已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH 请写出从顶点A 出发对该图进行深度有限搜索后得到的顶点序列。011000001000101110010100001001000100000

47、100110000答案：24试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。(1) 试画出插入完成之后的二叉排序树；29文档收集于互联网，如有不妥请联系删除文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持（2） 若查找元素17,它将依次与二叉排序树中哪些元素比较大小?（3） 假设每个元素的查找概率相等,试计算该树的平均查找长度ASL 。（4） 对该树进行中序遍历,试写出中序遍历序列。答案：25已知一关键字序列为（40， 11， 16， 31 ， 23， 55， 13， 45，

48、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. 如果分时系统的时间片一定，