1、各种方法的基本思想：顺序存储：逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。链接存储：通过附加指针域表示数据元素之间的关系。索引存储：除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。散列存储：根据关键字直接计算出该结点的存储地址，通常称为关键字地址转换法。第2章2.1 线性表L=（a1，a2，an），下列说法正确的是： A. 每个元素都有一个直接前驱和一个直接后继。 B. 线性表中至少有一个元素。 C. 表中元素的排列顺序必须是由小到大或由大到小。 D. 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。2.2 下面关于线性表的叙述中，错误的是：
2、A线性表若采用顺序存储，必须占用一片连续的存储单元 B线性表若采用顺序存储，便于进行插入和删除操作 C线性表若采用链接存储，不必占用一片连续的存储单元 D线性表若采用链接存储，便于插入和删除操作2.3 在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数为： A .n-i+1 B .n-i C .i D .i-12.4 删除长度为n的顺序表中的第i（1in）个位置上的元素，元素的移动次数为： A. n-i+1 B. n-i C. i D. i-12.5 已知一个带头结点单链表L，在表头元素前插入新结点 *s的语句为： A. L=s; s-next=L; B. s-next
3、=L-next; L-next=s; C. s=L; D. s- s=L;2.6 已知一个不带头结点单链表的头指针为L，则在表头元素之前插入一个新结点*s的语句为： L=s;2.7 已知单链表上一结点的指针为p，则在该结点之后插入新结点*s的正确操作语句为： A p-next=p- B s- p- C p-next=s- D p-2.8 已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是： A s= p- p=p- free（s）; B p=p- free（p）; C s= p- D p=p- free（p-next）;2.9 设一个链表最常用的操作是在表尾插入结点和在表头删除结点
4、，则选用下列哪种存储结构效率最高？ A. 单链表 B. 双链表 C. 单循环链表 D. 带尾指针的单循环链表2.10 线性表的链接存储结构是一种（ ）存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取2.11 链表不具备的特点是： A. 插入删除不需要移动元素 B. 不必事先估计存储空间 C. 可随机访问任一结点 D. 所需空间与其长度成正比2.1 在单链表L中，指针p所指结点有后继结点的条件是 p-next!=NULL 。2.2 判断带头结点的单链表L为空的条件 L-next=NULL。2.12 顺序表和链表中能实现随机存取的是 顺序表 ，插入、删除操作效率高的是 链
5、表 。2.13 对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为 O（1） ；若已知一个结点的值为x，在其后插入一个新结点的时间复杂度为 O（n） 。2.14 顺序表的存储密度 大 ，链表的存储密度 小 。2.15 比较顺序表和链表这两种线性表不同存储结构的特点。顺序表存储密度大存储空间连续静态分配随机存取插、删效率低链表存储空间可不连续动态分配顺序存取插、删效率高2.16 简述头结点的作用。头结点的作用是使得单链表在表头位置的插、删操作同中间位置的插、删操作完全相同。即使“空表”与“非空表”的操作统一，也使“表头结点”与其他位置结点的操作完全一致，无须特
6、殊处理。2.17 写出单链表存储结构的C语言描述。typedef int DataType; typedef struct Node DataType data; struct Node *next; LinkList;完善程序题：2.18 设计一个算法，其功能为：向一个带头结点的有序单链表（从小到大有序）中插入一个元素x，使插入后链表仍然有序。请将代码补充完整。 typedef int DataType; typedef struct Node DataType data; ; /*定义指向该结构类型的指针变量next*/ Linklist; void insert（Linklist *L,
7、DataType x） Linklist *s,*p=L; while（p-next &next-datadata=x; ; /*将*s结点插入到*p结点的后面*/ struct Node * next; s=（LinkList *）malloc（sizeof（LinkList）; p-2.19 设计一个函数功能为：在带头结点的单链表中删除值最小的元素。 typedef Node /*定义结构体类型*/ DataType data; struct Node * next; void deleteMin（LinkList *L） LinkList *p=L-next,*q; /*首先查找值最小的
8、元素，指针q指向最小元素结点*/ q=p; while（p） if（ p-data data） q=p; ; /* p指针后移一步，比较单链表中的每一个结点*/ if（!q） return; /*不存在最小结点（空表）时，直接退出*/ p=L; /*若存在最小结点，则先找到最小结点的前驱，即*q的前驱*/ while（ ） p=p- ; /*从单链表中删除最小元素结点（指针q所指结点）*/ /* 释放指针q所指结点的空间*/struct=qnext=q- free（q）;算法设计题：2.20 已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数：（
9、1）线性表采用顺序存储；（2）线性表采用单链表存储。（1）线性表采用顺序存储 #define MAX 1024 typedef struct DataType dataMAX; int last; SeqList; int LocateElem （SeqList *L, DataType item） int i,j=0; for（i=0;ilast ;i+） if（ L-datai item ） j+; return j;（2）线性表采用单链表存储 typedef struct Node DataType data; struct Node *next;LinkList;int locateE
10、lem（LinkList *L, DataType item ） LinkList *p=L- int i=0; while （ p ） if（ p-data item） i+; return i ;2.21 试写一算法实现对不带头结点的单链表H进行就地（不额外增加空间）逆置。typedef struct Node LinkList * Reverse（LinkList *L） LinkList *p,*q; if （!L） return;p=H- q=H-next=NULL;while（q）q=q-next= L; L=p; p=q; return L;第3章3.1 设一个栈的输入序列是 1
11、，2，3，4，5，则下列序列中，是栈的合法输出序列的是： A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 2 1 5 D. 3 5 2 4 1 3.2 设有一顺序栈，元素1，2，3，4，5依次进栈，如果出栈顺序是2，4，3，5，1则栈的容量至少是： A .1 B. 2 C. 3 D. 43.3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当入队一个元素，再出队两个元素后，rear和front的值分别为： A. 1和 5 B. 2和4 C. 4和2 D. 5和1 3.4 栈和队列都是操作受限的线性表，栈的运算特点是 LIFO ，队列的运算特
12、点是 FIFO 。3.5 若序列a、b、c、d、e按顺序入栈，假设P表示入栈操作，S表示出栈操作，则操作序列PSPPSPSPSS后得到的输出序列为 acdeb 。3.6 已知一个顺序栈*s，栈顶指针是top，它的容量为MAXSIZE，则判断栈空的条件为 s-top=-1 ，栈满的条件是 s-top=MAXSIZE-1 。3.7 对于队列来说，允许进行删除的一端称为 队头 ，允许进行插入的一端称为 队尾 。3.8 某循环队列的容量MAXSIZE=6，队头指针front=3，队尾指针rear=0，则该队列有_3_个元素。3.9 栈上的基本运算有哪些？栈的基本运算有：（1）初始化栈 initStac
13、k（s）：构造了一个空栈s。（2）判栈空empty（s）：若栈s为空栈，返回值为“真”（1），否则返回值为“假”（0）。（3）入栈push（s，x）：在栈s的顶部插入一个新元素x， x成为新的栈顶元素。（4）出栈pop（s）：删除栈s的栈顶元素。（5）读栈顶元素top（s）：栈顶元素作为结果返回，不改变栈的状态。3.10 循环顺序队列的存储结构图示及C语言描述？C语言描述： 循环顺序队列图示：#define MAXSIZE 1024 typedef int DataType;typedef struct DataType dataMAXSIZE; int rear , front;SeQueu
14、e;SeQueue *sq;3.11 简述栈和队列有哪些联系与区别？栈和队列都是运算运算受限的线性表，逻辑结构相同；都可以顺序存储和链接存储，存储结构也相同；插入和删除运算都限制在线性表的表端完成，且不需要查找运算。二者差别主要体现在运算的限制不同：栈是后进先出（LIFO）的线性表，限制它的插入和删除操作仅在表的一端进行。队列是先进先出（FIFO）的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。3.12 通常称正读和反读都相同的字符序列为“回文”，例如，“abcdeedcba”、 “abcdcba”是回文。若字符序列存储在一个单链表中，编写算法判断此字符序列是否为回文。（提示：将一
15、半字符先依次进栈）#define maxsize 100typedef char datatype1;typedef struct datatype1 datamaxsize; int top; seqstack;typedef int datatype;typedef struct node datatype data; struct node *next; Linklist;Duichen（Linklist *head） int i=1; Linklist *p; seqstack *s; s=initSeqStack（）; p= head-n=0; while（p）n+; p=head-
16、 while（idata）; i+; if （n%2!=0） p=p- while（p&p-data=pop（s） p=p- if （p） return 0 else return 1;第5章5.1 设数据结构D-S可以用二元组表示为D-S=（D，S），rS，其中： D=A，B，C，D， r=，B，D，则数据结构D-S是： A线性结构 B树形结构 C图形结构 D集合5.2 树最适合用来表示： A有序数据元素 B.无序数据元素 C元素之间具有分支层次关系的数据 D.元素之间无联系的数据5.3 有关二叉树下列说法正确的是： A二叉树是度为2的有序树 B二叉树中结点的度可以小于2 C二叉树中至少有一
17、个结点的度为2 D二叉树中任何一个结点的度都为25.4 深度为10的完全二叉树，第3层上的的结点数是： A .15 B .16 C . 4 D .325.5 设一棵树的度为4，其中度为1、2、3、4的结点个数分别为6、3、2、1，则这棵树中叶子结点的个数为： A .8 B. 9 C. 10 D. 115.6 对于二叉树来说，第i 层上最多包含的结点个数为： A2i - 1 B. 2i + 1 C2i D.2i5.7 树的后根遍历序列等同于与该树对应的二叉树的哪种序列？ A. 前序序列 B. 中序序列 C. 后序序列 D. 层序序列5.8 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为
18、M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： AM1 BM1+M2 CM3 DM2+M35.9 二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 11 。5.10 包含n个结点的二叉树，高度最大为 n ，高度最小为。5.11 某完全二叉树共有200个结点，则该二叉树中有 1 个度为1的结点。5.12 一棵高度为10的满二叉树中的结点总数为 210-1 个，其中叶子结点数为 29 。5.13 某完全二叉树结点按层顺序编号（根结点的编号是1），若21号结点有左孩子结点，则它的左孩子结点的编号为_42_。5.14 深度为k的完全二叉树至少有 2k-1 个结
19、点，至多有 2k-1 个结点。5.15 n个结点的线索二叉树上含有 n+1 条线索。5.16 画出包含三个结点的树和二叉树的所有不同形态。5.17 找出满足下面条件的二叉树： （1）前序遍历与中序遍历结果相同：只有右分支的单分支二叉树 （2）前序遍历和后序遍历结果相同：只有一个根结点的二叉树 （3）中序遍历和后序遍历结果相同：只有左分支的单分支二叉树5.18 一棵二叉树的中序、后序遍历序列分别为： G L D H B E I A C J F K和L G H D I E B J K F C A，请回答： （1）画出二叉树逻辑结构的图示。 （2）画出此二叉树的二叉链表存储结构的图示并给出C语言描述
20、。 （3）画出上题中二叉树的中序线索二叉树。 （4）画出中序线索二叉链表存储结构图示并给出C语言描述。（1）二叉树的逻辑结构图示：（2）二叉链表存储结构的图示及C语言描述：typedef char DataType;typedef struct Node DataType data; struct Node *lchild,*rchild;BiTree;（3）中序线索二叉树：（4）中序线索二叉链表的图示及C语言描述： int ltag,rtag;BiThrTree;5.19 设有森林如图5.31所示，请回答： （1）画出与该森林对应的二叉树的逻辑结构图示。 （2）写出该二叉树的前序、中序、后序
21、遍历序列。 （3）画出该二叉树的中序线索二叉链表的图示并给出C语言描述。图5.31 （2）前序遍历序列：ABCDFGEH，中序遍历序列：ADGFCBHE 后序遍历序列：GFDCHEBA（3）中序线索二叉链表的图示及C语言描述：5.20 设有森林 B=（D,S）, D=A,B,C,D,E,F,G,H,I,J, rSA,B,A,DB,EC,FG,HG,II,J 请回答： （1）画出与森林对应的二叉树的逻辑结构图示。 （2）写出此二叉树的前序、中序、后序遍历序列。 （3）画出此二叉树的二叉链表存储结构的图示并给出C语言描述。（1）与森林对应的二叉树的逻辑结构图示： （2）前序遍历序列：ABECFDG
22、HIJ，EBFCDAHJIGEFDCBJIHGA（3）二叉链表存储结构的图示及C语言描述：5.21 请画出5.32中的各二叉树对应的森林。图5.325.22 假设用于通信的电文由字符集a，b，c，d，e，f，g，h中的字母构成，这8个字母在电文中出现的概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，试为这8个字母进行哈夫曼编码。请回答： （1）画出哈夫曼树（按根点权值左小右大的原则）。 （2）写出依此哈夫曼树对各个字母的哈夫曼编码。 （3）求出此哈夫曼树的带权路径长度WPL。（1）哈夫曼树：（2）各字母的哈夫曼编码： a:1010 b:00 c:10000 d:1001 e:11f:10001g:01h:1011（3）哈夫曼树的带权路径长度WPL： =0.074+0.192+0.025+0.064+0.322+0.035+0.212+0.104=2.615.23 设计一个算法，其功能为：利用中序线索求结点的中序后继。 struct Node *lchild, ;BiThrTree * InOr
