序存取以及随机存取。但元素的插入和删除需要涉及大量元素的移动；而线性表的链式存储方便于元素的插入与删除，但是不能实现随机存取，只能进行顺序存取。 6. 【答案】D
【解析】顺序表要求存储空间是连续，所以，只要知道基地址，知道每个元素所占的字节数，就可以求每个元素的存储起始地址。 7. 【答案】D
【解析】在中序线索二叉树中，若某结点有右子树，则在访问完该结点后要访问右子树中最左边的结点，所以答案选D。 8. 【答案】C
【解析】栈的基本性质是后进先出，在入栈序列为abcde，出栈的第一个元素为d时，则 已经入栈，所以，此时“abc”三个元素的出栈序列中，一定是cba的顺序，而不能出现cab的顺序，所以选项C是错误的。 9. 【答案】A
【解析】构成广义表的数据元素可以单个元素，也可以是由若干个元素所组成的子表。广义表属于特殊的线性表，特殊的地方在于广义表的元素中能否使用子表。 10. 【答案】B
【解析】根据二叉树的基本性质3，对于任意一棵二叉树，满足度为0的结点为度为2的结点数加1。所以，答案选B
二、填空题（本大题共10小题，每小题1分，共10分） 1. 【答案】一定相邻
【解析】顺序表采用连续存储空间作为元素的存储结构，所以，逻辑上相邻的数据元的物理存储空间也一定相邻。 2．【答案】块
【解析】在索引顺序表中，将所有的关键字进行分块，块与块之间关键字大小有序，在每个块内部元素排列无序，可以把每个组中最大元素值作为该组的索引加入到索引表中排列，所以，索引表中元素排列是有序的，因此，在查找元素时，先查找索引表，获得查找元素所在组后，再使用顺序查找去查找相应的块。 3. 【答案】分配和收集
【解析】分配法排序属于一种典型的多关键字排序，分配排序的基本思想是排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。 4. 【答案】入度
【解析】拓扑排序每次都选择没有前驱的结点进行输出，其中结点没有前驱，即入度为0。 5．【答案】n+1
【解析】二叉链表中，每个结点有2个指针域，具有n个结点的二叉链表一共有2n个指针域，其中，除根结点外，每个结点需要一个指针来指向，所以空的指针域的个数为n+1。 6.【答案】出度
【解析】有向图的邻接表是指:所有顶点建立顶点结点，以每个顶点为弧尾的所有弧对应的另外一个顶点序号构成表结点链接形成的单链表。所以，通过计数每个单链表中表结点的
11
个数，可以计算每个顶点的出度。 7．【答案】列
【解析】有向图的邻接矩阵的特点是，通过求解每一行上1的个数，可以求解每个顶点的出度；通过求解每一列上1的个数，可以求解每个顶点的出度。无向图的邻接矩阵属于对称矩阵，每个顶点的度即为行或列上1的个个数。 8.【答案】双亲
【解析】树的表示方法一共有三种，双亲表示法、孩子表示法以及孩子兄弟表示法。其中双亲表示法为每个树中元素建立一个结点，包括存储数据元素本身，以及该结点的双亲结点的存储下标，所以，该存储方法可以很容易的求解结点的双亲以及祖先，但是求解结点的孩子及后代需要遍历整个数组。 9．【答案】67。
3319141095235【解析】。图为五个权值形成的哈夫曼树，树的带权路径长度为：
(2+3)*4+5*3+9*2+14*1=67 10. 【答案】n(n-1)
【解析】在有n个顶点的有向完全图中，从每个顶点出去的弧有n-1条，所以总弧数为n(n-1)。
四、综合题（30分，每题5分） 1．答：viod creat(Linklist &L) { L=(Linklist)malloc(sizeof(Lnode)); L->next=NULL; for(i=n;i>0;i++)
{ p=(Linklist)malloc(sizeof(Lnode)); scanf(&p->data); p->next=L->next; L->next=p; }
} 注意：除了使用头插法，还有尾插法，可以查阅资料写出算法。 2．答：
12
1 求顶点0其余各顶点的最短路径 10 (0,1) / / / 2 ∞ 60 (0,1,2) 50 (0,3,2) / / 3 30 (0,3) 30 (0,3) 100 (0,4) 3 / 4 100 (0,4) 90 60 (0,3,4) (0,3,2,4) 2 添加 顶点 1
3．答：根据（1）中序遍历的特点：左子树、根、右子树的遍历顺序；（2）后序遍历的特点：左子树、右子树、根；（3）二叉树的每棵子树也符合该特性。所以，该二叉树的构造过程为:
aabdfbechiddfehifheiabcc
由此可得到二叉树的前序遍历顺序为：abdfceih 4．答：根据二叉排序树的定义，创建过程如下图：
1515443043041130411515154115154112230441111224130
5. 答：
该邻接表的结构描述如下： #define VERTEX_MAX 100 typedef struct node {int adjvex; struct node *next;
}Edgenode; //表结点的类型定义
13
typedef struct vnode {vextype vertex; Edgenode *firstedge;
}VertexNode; //顶点结点的类型定义 Typedef struct
{ VertexNode adjlist[VERTEX_MAX]; int n,e; //顶点数和边数 }ALGraph; //邻接表的类型定义
void BFS(ALGraph *G) {
for(v=0;v
Printf(“%c”,G->adjlist[v].vertex); EnQueue(Q,v)
while(!QueueEmpty(Q)) { DeQueue(Q，u)；
for(p=G->adjlist[u].firstedge;p;p=p->next) if(!visited[p->adjvex]) { visited[p->adjvex]=TRUE;
Printf(“%c”,G->adjlist[p->adjvex].vertex); EnQueue(Q,p->adjvex);
} } } }
6．答：根据哈希函数以及拉链法解决冲突，构造如下哈希表：
14
01234567891011122311192014012779∧ 6855∧ 84∧ 10∧ ∧
山东省2006年普通高等教育专升本统一考试 数据结构（50分）
一、单选题（每小题1分，共10分，） 1. 【答案】D
【解析】所有能输入到计算机中的符号的总称为数据，数据元素是构成数据的基本单位，数据元素可以由若干条记录组成，每条记录又可由若干数据项组成。相同性质的数据元素的集合构成数据对象。数据元素的类型称为数据类型。 2. 【答案】B
【解析】采用顺序存储结构的线性表在进程插入和删除元素时需要涉及大量元素的移动问题。而链式存储结构可以很容易的实现插入和删除操作，因此选B。 3. 【答案】D
【解析】如果9作为第一个出栈元素，前提是3，5，7已经依次入栈了，所以，此时输出顺序只能为9，7，5，3。选项D是错误的。 4. 【答案】D
【解析】字符串的长度应该是串中所有包含的字符的个数，所以选项A只提到了字母，选项B提到了不同字符的个数，均是错误的，每个字符串都属于自己的子串，因此选项C错误。 5. 【答案】D
【解析】广义表的表头是广义表中的头元素，广义表的表尾是指除去表头元素，其余元素所组成的广义表，因此，答案选D而不是C，更不是A和B。 6. 【答案】A
【解析】图的生成树是指包含图中所有的n个顶点，但仅包含连通这个n个顶点的n-1条边。 7. 【答案】C
【解析】根据二叉树的基本性质3：对于任意一棵二叉树满足n0=n2+1，所以，当度为2的结点数为8时，叶子结点个数为9。 8. 【答案】A
15
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库06-09数据结构真题及答案(3)在线全文阅读。
相关推荐：