免费智能真题库 > 历年试卷 > 软件设计师 > 2014年上半年 软件设计师 上午试卷 综合知识
第58题      2014年上半年 软件设计师 上午试卷 综合知识
所属知识点           关键词   二叉树   空指针   链表   数据   顺序存储   一维数组   数组   指针
考点辞典   数组   二叉树   指针   数组      二叉树

 
二叉树如图所示,若进行顺序存储(即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系,例如,对于下标为i的结点,其左孩子的下标为2i、右孩子的下标为2i+1),则该数组的大小至少为(58);若采用三叉链表存储该二叉树(各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针),则该链表的所有结点中空指针的数目为(59)。
 
 
  A.  6
 
  B.  10
 
  C.  12
 
  D.  15
 
 
 

   知识点 更多相关真题:    更多>  
 
  第59题    2009年上半年  
   45%
下面关于二叉排序树的叙述,错误的是(59)。
  第64题    2013年上半年  
   28%
一个高度为h的满二叉树的结点总数为2h-1,从根结点开始,自上而下、同层次结点从左至右,对结点按照顺序依次编号,即根结点编号为1,其左、右孩子结点编号分别为2和3,再下一层从左到..
  第59题    2014年下半年  
   36%
某个二叉查找树(即二叉排序树)中进行查找时,效率最差的情形是该二叉查找树是()。
 

数组
       数组的定义及基本运算
       n维数组是一种"同构"的数据结构,其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张,即线性表中的元素又是一个线性表。
       数组结构的特点是:数据元素数目固定;数据元素具有相同的类型;数据元素的下标关系具有上下界的约束且下标有序。
       对数组进行的基本运算有以下两种。
       (1)给定一组下标,存取相应的数据元素。
       (2)给定一组下标,修改相应的数据元素中某个数据项的值。
       数组的顺序存储
       一旦定义了数组,结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。
       由于计算机的内存结构是一维线性的,因此存储多维数组时必须按照某种方式进行降维处理,即将数组元素排成一个线性序列,这就产生了次序约定问题。对二维数组有两种存储方式:一种是以列为主序的存储方式;另一种是以行为主序的存储方式。
未完......点击标题查看......
二叉树
       二叉树的定义
       二叉树(Binary Tree)是n(n≥0)个节点的有限集合,它或者是空树(n=0),或者是由一个根节点及两棵互不相交的、分别称为左子树和右子树的二叉树所组成。
       二叉树与树的区别如下。
       .二叉树的节点的子树要区分左子树和右子树,即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
       .二叉树的节点的最大度为2,而树中不限制节点的度数。
       二叉树的运算
       二叉树的基本运算是遍历,其他运算可建立在遍历运算的基础上。
       二叉树的性质
       二叉树具有以下性质。
未完......点击标题查看......
指针
指针是C语言中最为重要也是最难的一个关键点,很多数据结构都是基于指针实现的,如链表、链式队列、链栈、二叉树等。
所谓指针,就是一个用来存储地址的变量。这可谓指针的本质,需要牢记。
也许你会很纳闷,指针为什么一定要定义成某类型(int、char)呢?指针不能就是"指针类型"吗?接触过汇编的人就很容易理解为什么。存储单元的单位是字节,就是说一般地址是按字节编址的,对一个地址进行操作(读取或赋值)就要指明是对单字节(不用特别声明)、两字节(WORD PTR),还是双字节(四字节,DWORD PTR)进行操作。同样,指针是存储地址的,即指针就是一个地址,自然也要说明其类型;而且,这个类型还关乎指针自加自减时真正加减的字节数。
顺便说一下,数组名也是指针。数组在申请空间时,数组名存储该存储空间的首地址。注意:数组名存储的是地址,因此也是指针,只是该指针一旦赋值后就不能修改,即所谓常指针。当直接输出数组名时,输出的其实是数组的首地址。这样,当形参声明为指针时,亦可将数组名作为实参进行传递。因此,可以用指针的方式访问数组中的元素,如下例采用指针的方式遍历输出数组。
当指针作为函数参数传递时,需要特别注意C语言中的"值"传递原则。下例中的函数希望为指针p申请空间,但不能达到目的,为什么呢?
归根结底,C函数的形参与实参之间只是"值传递":当形参是普通变量时,传递的是实参的值;当形参是指针时,传递的是指针变量的值,即某变量的地址,这样可以通过指针成功地改变其所指单元的值,但自身的改变不会传回给实参。上例可改为:
未完......点击标题查看......
数组
数组是最常用的数据结构之一,在程序中,数组常用来实现顺序存储的线性表。数组由固定个数的元素组成,全部元素的类型相同,元素依次顺序存储。每个元素对应一个下标,数组元素按数组名和元素的下标引用,引用数组元素的下标个数称为数组的维数。
在C语言中,n个元素的数组中,第一个元素的下标为0,最后一个元素的下标为n-1。
数组可以分为静态数组和动态数组两类。
(1)静态数组是指数组的存储空间分配是在使用之前进行,在程序运行中不能改变,不利于数组的扩展。
(2)动态数组是在程序执行中进行数组存储空间的分配。
动态数组一般采用链式存储结构,而静态数组一般采用顺序存储结构。
数组元素可以是任意类型,当元素本身又是数组时,就构成了多维数组。多维数组是一维数组的推广,最常用的是二维数组。在C语言中,数组元素按行优先顺序存放。
一般用多维数组表示矩阵,矩阵的类型有对称矩阵、三角矩阵(下三角矩阵或上三角矩阵)和对角矩阵。
稀疏矩阵的存储:用顺序存储结构的三元数组对稀疏矩阵进行存储,分别记录行、列和值。
未完......点击标题查看......
1)定义
树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用。
树是由一个或多个节点组成的有限集T,它满足以下两个条件:有一个特定的节点称为根节点;其余的节点分成m个互不相交的有限集T1, T2, …, Tm,其中每个集又都是一棵树,称T1, T2, …, Tm为根节点的子树。
可见树的定义是递归的,即一棵树由子树构成,子树又由更小的子树构成。
2)相关概念
.一个节点的子树数目称为该节点的度。
.树中各节点的度的最大值称为树的度。
.树中节点的最大层次称为树的深度。
若将树中节点的各子树看成是从左到右具有次序的,即不能交换,则称该树为有序树,否则称为无序树。
未完......点击标题查看......
二叉树
1)定义
二叉树是n个节点的有限集合,它或者是空树,或者是由一个根节点及两棵不相交的、分别称为左子树和右子树的树所组成。
2)树和二叉树最主要的区别
二叉树的节点的子树要区分左子树和右子树,即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树;另外,二叉树的节点的最大度为2,而树中不限制节点的度数。
3)二叉树的性质
.在二叉树的第i层至多有2i-1个节点(根节点为1层)。
.深度为k的二叉树至多有2k-1个节点。
.对任何一棵二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1。
.具有n个节点的完全二叉树的深度为[log2n」+1。
未完......点击标题查看......

 题号导航      2014年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况 
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
↓第58题