复习题1

一、选择题

1-1 下列关于数据和逻辑结构的叙述中，哪一个是不正确的（ ）。 A ) 数据的逻辑结构是数据间关系的描述

B) 数据的逻辑结构抽象反映数据元素间的逻辑关系

C) 数据的逻辑结构具体反映数据在计算机中的存储方式 D) 数据的逻辑结构分为线性结构和非线性结构 C

1-2 以下关于数据的存储结构的叙述中哪一条是正确的（ ）。 A) 数据的存储结构是数据间关系的抽象描述

B) 数据的存储结构是逻辑结构在计算机存储器中的实现 C) 数据的存储结构分为线性结构和非线性结构

D) 数据的存储结构对数据运算的具体实现没有影响 B

二、简答题

1-1 数据结构的存储方式有哪几种？

1-2 算法的时间复杂度仅与问题的规模相关吗 ? 1-1 数据结构的存储方式有哪几种？ 【解析】

常用的存储表示方法有四种 :

1 、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。

2 、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构 , 通常借助于程序语言的指针类型描述。

3 、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（ Dense Index ）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。

4 、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 1-2 算法的时间复杂度仅与问题的规模相关吗 ? 【解析】

算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。 三、应用题: 分析以下程序段的时间复杂度。 int i ， j ， k ；

for （ i=0 ； i 〈 n ； i++ 〉 // ① for （ j=0 ； j 〈 n ； j++ 〉 // ② { c[i][j]=0 ； // ③

for （ k=0 ； k 〈 n ； k++ 〉 // ④ c[i][j]=c[i][j]+a[i][k]+b[k][j] ； // ⑤ }

【解析】

语句①的循环控制变量 i 要增加到 n ，测试到 i=n 成立才会终止，故它的频度为 n+1 ； 语句②作为语句①循环体内的语句应该执行 n 次，但语句②本身要执行 n+1 次，故语句②的频度是 n （ n+1 ）；

同理可得语句③、④和⑤的频度分别是 n 2 ， n 2 （ n+1 ）和 n 3 。该程序段所有语句的频度之和为：

T （ n ） =2n3 +3n 2 +2n+1 其复杂度为 O （ n ）。

一、简答

1 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

2 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?

3 为什么在单循环链表中设置尾指针比设置头指针更好?

4 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 5 下述算法的功能是什么? LinkList Demo(LinkList L){

// L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){

Q=L;L=L->next;P=L;

while (P->next) P=P->next; P->next=Q; Q->next=NULL; } return L; } // Demo

6、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。

二、下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。

void union (LinkList La, LinkList Lb){

/*本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中*/ LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb);

while (pa && pb){ if (pa -> data data) { pre = pa; pa = pa -> next;} else if (pa -> data > pb ->data) {

(1) ; 3

pre = pb; pb = pb -> next; (2) ; }

else {

q = pb; pb = pb -> next; free (q); } }

if (pb) (3) ; }

（1）pre->next=pb; （2）pre->next=pa; （3）pre->next=pb;

三、已知一个线性表有n（n≤30）个元素，其中每个元素的数据占8个字节。假设一个指针的大小为4个字节。如果采用有30个元素的数组存储，那么当数组中有效元素个数n满足什么条件时，数组的存储效率比不带头结点的单链表更高。

数组总的空间240个字节，数组的效率为8n/240；链表的总空间为12n，效率为8n/12n。故可得：n〉20

四、画出执行下列各语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(Lnode)); P=L;

for(i=1;i<=4;i++){ p->next=(LinkList) malloc(sizeof(Lnode)); p=p->next; P->data=i*2-1;} P->next=NULL; for(i=4;i>=1;i--) InsertList (L,i+1,i*2); for(i=1;i<=3;i++) DeleteList (L,i);

2、顺序队列一般应该组织成为循环队列的形式，而且一般队列头或为队列尾其中之一虚指一位，满队列时实际上数组中还有一个空闲位置。请分析这样设置的理由。

有利于判断队列是空还是满。因为队列有n+2种状态：空，1个元素， 2个元素，…, n个元素，满。但实际上rear只有n种可能的取值，故必须寻求其他途径解决队空和队满。当然也有其他方法。

3、队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请分析对于循环单链表实现的队列，用那种方案更合适。

设置尾指针。因为是循环单链表，设置尾指针，可以在O(1)的时间内找到头；如果只设置头指针，要在O(n)时间内找到尾。设置尾指针，入队和出队的时间复杂度均为O(1)，设置头指针，出队O(1)，入队O(n)。

一、单项选择题

1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 （A）正确 （B）错误

2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 (A)空或只有一个结点 (B) 完全二叉树 (C)二叉排序树 (D) 高度等于其节点数 3、深度为5的二叉树至多有 多少个结点 (A)16 (B)32 (C)31 (D)10

4、根据使用频率为5个字符设计的哈夫曼编码不可能是 （A）111，110，10，01，00 （B）000，001，010，011，1 （C）100，11，10，1，0 （D）001，000，01，11，10 二、填空题

1、树和二叉树的主要差别是 ， 。

2、深度为k的完全二叉树至少有 个结点，至多有 个结点。 3、一棵二叉树的第i(i?1)层最多有 个结点；一棵有n（n>0）个结点的满二叉树共有 个叶子结点和 个非叶子结点。

1、 （1）每个结点最多有两棵子树； （2）子树有左右之分 2、2k-1,2k-1,

3、2i-1, 2 ? log2n ?， n- 2 ? log2n ?

1、一棵度为2的树与一棵二叉树有何区别？

2、具有三个结点的树和具有三个结点的二叉树它们的所有不同形态有哪些？

3、请说明一棵二叉树进行先序、中序和后序遍历，其叶结点的次序是否会发生变化？为什么？

1、解答：度为2的树结点有两个分支，没有左右之分；一棵二叉树的结点也可有两个分支，但有左右之分，且左右不能交换。

3.解答：二叉树中叶结点必在某结点的左或右子树中，三种遍历方法对左右子树的遍历都是按先左后右的原则进行。所以在三种遍历序列中叶结点的相对次序是不会发生变化的。

4、假设一棵二叉树的结点数为33个，则它的最小高度为（ ），最大高度为（ ）。 5、一个高度为h的满m叉树，第k层最多有（ ）个结点，整棵树最多有（ ）个结点。

4、最小高度为：6，最大高度为：33

5、第k层最多有 mk-1,整棵树最多有(mk-1)/(m- 1)

6、一个二叉树的对称序列和后序序列分别是DCBAEFG和DCBGFEA，请给出该二叉树的前序序列。 6、ABCDEFG