大学数据结构考试题和答案.pdf

《大学数据结构考试题和答案.pdf》由会员分享，可在线阅读，更多相关《大学数据结构考试题和答案.pdf（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 1 章 绪论1、填空题1.常见的数据结构有_线性 _结构，_树形 _结构，_图形 _结构等三种。2.常见的存储结构有_顺序存储 _结构，_链式存储 _结构等两种。3.数据的基本单位是_数据元素 _，它在计算机中是作为一个整体来处理的。4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，_线性结构_和_非线性结构 _。2、应用题1、给出以下算法的时间复杂度.void fun(int n)int i=1,k=100;while(in)k=k+1;i=i+2;时间复杂度为_O（n）_。2、给出以下算法的时间复杂度.void fun2(int n)int i=1,k=100;whil

2、e(inext=p-next_；_p-next=s _；4.在单向链表中，若要删除某个结点p，一般要找到 _p 的前趋 _结点，才能实现该操作。2、选择题1.将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是A。(A)n (B)2n 1(C)2n (D)n-1 2.在单链表中，如果在结点p 之后插入一个新结点s，其操作为 A。（A）s-next=p-next;p-next=s;（B）p-next=s;s-next=p-next;（C）s-next=p;p-next=s-next;（D）p-next=s;s-next=p;3.若长度为n 的线性表采用顺序存储结构，在其第i 个位置删

3、除一个元素的算法的平均时间复杂度为(C)。(1i n)AO(0)BO(1)C.O(n)D O(n2)4.若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素需要移动的元素个数为(B)。(1i n+1)An-i Bn-i+1 C.i Dn-i-1 3、判断题1.线性表中每一个元素都有一个前驱和一个后继。（）4、程序设计题1、单链表的结点结构定义如下：struct LinkNode 文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T

4、5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文

5、档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T

6、5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文

7、档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T

8、5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文

9、档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T

10、5B7Y4A6 ZY8R3B8L7K1 LinkNode*next;int data;请根据述函数的功能写程序。void Insert(LinkNode*h,LinkNode*s)/h指向链表的头结点（即使链表中没有元素，头结点也存在。）/链表中元素已经递增有序/函数功能为将结点s 插入到链表h 中。插入后链表仍然保持递增的顺序LinkNode*p,*q;/q指向 p 的前驱q=h;p=h-next;while(p)if(p-datas-data)/寻找到插入点位置，插入s q-next=s;s-next=p;return;else q=p;(1分)p=p-next;(1分)/当表中没有比s

11、大的结点时，插入到表尾s-next=q-next;(2分)q-next=s;(2分)2、设顺序表L 是一个递增有序表，试写一算法，将x 插入 L 中，并使L 仍是一个有序表。顺序表的结构定义如下：#define ListSize 100 /假定表空间大小为100 struct SqList int elemListSize;/数组 elem 用于存放表中的数据int length;/当前的表长度;/以上为顺序表的结构/函数头定义如下void InsertIncreaseList(SqList&L,int x)int i;if(L.length=ListSize)cout0&L.elem i-1

12、 x;i-)L.elem i=L.elem i-1 ;/比较并移动元素文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y

13、4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:

14、CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y

15、4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:

16、CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y

17、4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:

18、CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1L.elem i =x;/插入 x L.length+;/表长增 1 /3、单链表中结点的结构如下所示：typedef struct node int data;struct node*next;node;请设计满足下述功能的函数。要求：建立带头结点的单链表H，要求函数从屏幕上读入m个整数

19、，每读入一个，便生成相应的结点，并且把它插入到链表H 的尾部。函数形式为void CreateLinkList(node*H)。参考程序：void CreateList(node*H)/H指向头指针int m,temp;coutm;/int i=1;node*tail;H-next=NULL;tail=H;while(i=m)coutplease input your number:temp;node*t=new node;t-data=temp;t-next=tail-next;tail-next=t;tail=t;i+;第 3 章 栈和队列1、填空题1.栈和队列在本质上都是_线性表 _。2

20、.栈的操作特点是_后进先出 _。队列的操作特点是_先进先出 _。2、选择题1.消除递归不一定需要使用栈，此说法_A_。A.正确 B.错误文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8

21、R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3

22、O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8

23、R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3

24、O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8

25、R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3

26、O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K12.对于栈，输入序列为（1，2，3，4），不可能得到的输出序列有_D_。(A)（1，2，3，4）(B)（4，3，2，1）(C)（1，3，4，2）(D)（3，1，2，4）3.用单循环链表表示队列，正确的说法是B。(A)可设一个

27、头指针使入队、出队都方便；(B)可设一个尾指针使入队、出队都方便；(C)必须设头尾指针才能使入队、出队都方便；(D)无论如何,只可能使入队方便。3、判断题1.栈的特点是先进先出。（）2.可以在队列的任意位置插入元素。（）3.递归程序化非递归程序必须用到栈。（）4.如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。（）5.在用顺序表表示的循环队列中，可用标志位来区分队空或队满的条件。（）第 4 章 串1、选择题1.设有两个串p 和 q，求 q 在 p 中首次出现的位置的运算称作（B）A连接 B模式匹配 C求子串 D求串长2、判断题1.空串和空格串是同一个概念，二者没有区别

28、。（）第 5 章 数组和广义表1、填空题1.二维数组在内存中存储可以有两种存储方式，一种是 _行_优先存储，一种是列优先存储。2.设广义表L(（），（），（）)。则 head(L)是（）；tail(L)是(（），（）)；L 的长度是3；L 的深度是 3。3.设广义表L(（a），（b），（c）)则 head(L)是 _（a）_；tail(L)是_(（b），（c）)_ _。2、选择题1.在 C语言中，如果有数组定义 int A89；假定每个整型数据占2 字节，则数文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6

29、 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2

30、H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6

31、 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2

32、H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6

33、 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2

34、H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6

35、 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1组元素 A44的地址是（A）。A.A+80 B.A+76 C.A+82 D.以上都不对2.广义表 A=（a,b,(c,d),(e,(f,g)）,则下面式子的值为(D)；Head(Tail(Head(Tail(Tail(A)A（g）B.(d)C.c D.d 3、判断题1.在 C语言中，多维数组的存储采取的是行优先的方式。（）2.广义表在本质上也是线性表。（）3.可以用三元组存储法来压缩存储稀疏矩阵。（）4.已 知 广 义 表A=(a,b,c),(d,e,f),从A中 取 出 原 子e的 运 算

36、 是head(tail(head(tail(A)。()第 6 章 树和二叉树1、填空题1.一棵 62 个叶结点的完全二叉树,最多有 _62*2=124_个结点。2.若 规 定 仅 有 根 的 二 叉 树 的 高 度 为1，那 么 高 为h 的 完 全 二 叉 树 最 多 有-_2h-1 _个结点，最少有_2(h-1)_个结点。3.设只包含有根结点的二叉树的高度为0，则高度为k 的二叉树的最大结点数为-_2(k+1)-1_，最小结点数为_k+1_。4.设仅包含根结点的二叉树的高度为1，则高度为k 的二叉树的最大结点数为-_2k-1 _，最小结点数为_k_。2、选择题1.具有 N个结点的完全二叉树

37、的深度是_B_。(A)?log2N?(B)?log2N?+1 (C)?log2(N)?(D)?log2N?-12.设二叉树的树根为第一层，则第i 层上至多有 _C _结点。(A)1 (B)2 (C)2i-1 (D)2i-1 3、判断题1.二叉树的左右子树次序是严格的，不能够任意改变。（）文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8

38、L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8

39、 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8

40、L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8

41、 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8

42、L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8

43、 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K12.若 根 为 第 一 层，则 深 度 为k的 满 二 叉 树 的 结

44、点 为2k-1。（）3.二叉树的三叉链表存储结构可以方便的访问到双亲结点。（）4、应用题1.在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题：（1）什么是哈夫曼树？（3 分）（2）根据题目所给频率值，画出相应的哈夫曼树。（11 分）（3）给出各个字符对应的哈夫曼编码。（6 分）（4）该段文字经过哈夫曼编码后，长度是多少。（4分）参考答案如下：（1）答案为：带权路径长度最小的二叉树称为哈夫曼树。（3 分）（2）根据题目所给频率值，画出相应的哈夫曼树。（11 分，每个结点1 分）（3）给出各个字符对应的哈夫曼编码。（6 分）

45、a:1110 b:1111 c:110 d:00 e:01 f:10（4）该段文字经过哈夫曼编码后，长度是多少。（4分）(7+9)*4+12*3+(22+23+27)*2=244 或者 100+45+55+28+16=244 2.设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。（15 分）参考答案如下：(1)画出二叉树（10 分）错一个结点扣2 分。f c 28 7 9 12 22 23 55 16 27 45 100 a b e d 1 0 0 0 0 0 1 1 1 1 文档编码:CT2H4S3O9E8 HW7T5B7Y4A6

46、ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H

47、4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6

48、ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H

49、4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6

50、ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H4S3O9E8 HW7T5B7Y4A6 ZY8R3B8L7K1文档编码:CT2H