数据结构((本)期末综合练习(月)

1、数据结构期末综合练习2018年 12月期末练习一一、单项选择题1. 一种逻辑结构在存储时（）。A.只要存储数据元素间的关系B .只能采用一种存储结构C 可采用不同的存储结构D 只要存储数据元素的值2同一种逻辑结构（）。A.只能有唯一的存储结构B.可以有不同的存储结构C 只能表示某一种数据元素之间的关系D 以上三种说法均不正确3 . 对链表 , 以下叙述中正确的是（）。A.不能随机访问任一结点B .结点占用的存储空间是连续的C.插入删除元素的操作一定要要移动结点D .可以通过下标对链表进行直接访问4链表所具备的特点是（）。A.可以随机访问任一结点B .占用连续的存储空间C.插入删除元素的操作不需

2、要移动元素结点D .可以通过下标对链表进行直接访问5线性表在存储后, 如果相关操作是: 要求已知第i 个结点的位置访问该结点的前驱结点，则采用（）存储方式是不可行的。A.单链表 B ,双链表 C ,单循环链表 D .顺序表6数据的物理结构（）。A 与数据的逻辑结构无关B 仅仅包括数据元素的表示C.只包括数据元素间关系的表示 D .包括数据元素的表示和关系的表示7栈和队列的共同特点是（）。A.都是先进后出 B.元素都可以随机进出C.只容许在端点处插入和删除元素D .都是先进先出8线性结构中数据元素的位置之间存在（）的关系。A 一对一B 一对多9元素2， 4， 6， 8 按顺序依次进栈，按该栈的的

3、可能输出序列依次入队列，该队列的可能输出序列是（）（进栈出栈可以交替进行）。A 8， 6，2，4 B 8，4，2，6C 6，2， 4， 8D 8，6，4，210以下表中可以随机访问的是（）。A 单向链表B 双向链表C.单向循环链表D.顺序表11 在一个不带头结点的链队中，假设f 和 r 分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量x 中的运算为（）。A x=rdata ；r=rnext 。B r=r next 。 x=r dataC x=fdata ；f=fnext 。D f=f next 。 x=f data12算法的时间复杂度与（）有关。A.所使用的计算机B .与计

4、算机的操作系统C.与算法本身D .与数据结构13.设有一个20阶的对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B 中（数组下标从1 开始），则数组中第38 号元素对应于矩阵中的元素是（）。A a10,8B a7,6C a9,2D a8,514设有一个长度为n 的顺序表，要删除第i 个元素需移动元素的个数为（）。A n-i+1 B n-i C n-i-1 D i15.在C语言中，分别存储“S"和's',各需要占用（）字节。A 一个和两个B 两个C 一个D 两个和一个16在一个单链表中，p、 q 分别指向表中两个相邻的结点，且q 所指结点是p

5、 所指结点的直接后继，现要删除q 所指结点，可用的语句是（）。A p=q->next B p->next=q C p->next=q next D q->next=NULL17 一棵有n 个结点，采用链式存储的二叉树中，共有（）个指针域被有效使用（即指针域为非空）。A n+1 B n C n-1 D n-218从一个栈顶指针为top 的链栈中删除一个结点时，用变量x 保存被删结点的值，则执行（）。A x=top->data 。top=top->next。Bx=top->data 。Ctop=top->next。 x=top->data。Dt

6、op=top->next。 x=data 。19 在一棵二叉树中，若编号为i 的结点存在双亲结点，则双亲结点的顺序编号为（）。A i/2.0B i/2 向下取整C 2i+1 D i+220在一个链队中，假设f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（）。A r=f->next。 B r=r->next。 C f=f->next 。 D f=r->next 。21设一棵哈夫曼树共有2n+1 个结点，则该树有（）个非叶结点。A n Bn+1C n-1 D2n22. 一个栈的进栈序列是a, b, c, d, e,则栈的不可能输出序列是（）（进栈出栈可以交替

7、进行）。A dceab B edcba C decba D abcde23一棵完全二叉树共有4 层，且第4 层上有 2 个结点，该树共有（）个非叶子结点（ 根为第一层） 。A 5B 4C 3D 924有一个长度为10 的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A 26/10 B 29/10 C 29/9 D 31/1025如图1 所示的一个图，若从顶点a 出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A abedfc B acfebd C aebcdf D aebcfd26 .排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）

8、中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）。A.冒泡 B.直接插入C.折半插入 D.选择排序27 . 一组记录的关键字序列为（56, 30,89 , 66, 48, 50, 94,87,100 ）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A . 30, 50,48 , 56, 66, 89, 94,100,87B , 50, 30,48 , 56, 66, 89, 94,87,100C. 48, 30,50 , 56, 66, 89, 94,87,100D . 50, 30,48 , 66, 56, 89, 94,87,100

9、28 .设有一个10阶的对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组 B中（数组下标从1开始），则矩阵中元素A8,5在一维数组 B中的下标是（ ）。A. 33 B . 32 C. 85 D . 4129 .线性表以（）方式存储，能进行折半查找。A .关键字有序的链接B.顺序C.关键字有序的顺序 D.数组C.多对多D .每一个元素都有一个直接前驱和一个直接后继30 .在一个无向图中，所有顶点的度数之和等于边数的（）倍。A. 3 B . 2.5 C . 1.5 D . 2二、填空题1 .数据的逻辑结构在计算机中的表示称为 结构。2 .栈和队列的操作特点分别是 和 _o3

10、 .求两个n阶矩阵的乘积，算法的基本操作为 ，时间复杂度为 。4 .结构中的数据元素存在多对多的关系称为 结构。5 . 设有一个长度为25的顺序表，第8号元素到第25号元素依次存放的值为 8,9,10,11, 25,某人想要在第 8个元素前插入1个元素7 （也就是插入元素作为新表的第8个元素），他的做法是从第8号元素开始，直到第25号元素依次向后移动 1个位置，然后把7存放在8号位置，其结果是新表中第25号元素的值为 。6 .根据数据元素间关系的不同特性，通常可分为集合、线性、四类基本结构。7 .在双向链表中，要在p所指的结后插入q所指的结点（设q所指的结点已赋值），其中所用的一条语句（p-&

11、gt;next） ->prior=q ;的功能是使 P所指结点的 指向q。8 .要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为 和。9 .设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL,现要删除头结点，并使该单向链表构造成单向循环链表，通过 操彳head=head->next。 。10 .在一个单向链表中 p所指结点之后插入一个s所指向的结点时，应执行 和p->next=s。的操作。11 .从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可

12、执行。（结点的指针域为next,数据域为data）12 .在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、13循环链队列中，设 front和rear分别为队头和队尾指针，（最多元素为 MaxSize,采用少用一 个元素的模式工判断循环链队列为满的条件为 。14 . 一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为15 .对稀疏矩阵进行压缩存储，可采用三元组表，一个 6行7列的稀疏矩阵A相应的三元组表共有8个元素，则矩阵A共有 个零元素。16 .向一个栈顶指针为 h的链栈中插入一个 s所指结点时，可执行 s->next=h。和。17 .一棵有20个

13、结点的4度的树，其中3度结1个，2度结1个，1度结2个，则该树共有 个叶结点。18 .在一个链队中，设 f和r分别为队头和队尾指针，则插入s所指结点的操作为 和r=s。（结点的指针域为next）19 . 一棵有18个结点的二叉树，其 2度结点数的个数为 8,则该树共有 个1度结点20 .设有一棵深度为 4的完全二叉树，第四层上有5个结点，该树共有 个结点。（根所在结点为第1层）21 .如图2所示的二叉树，其先序遍历序列为 。图222 .对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的、 和 三项信息。23 .在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为24

14、 .在对一组记录（55,39,97,22,16,73,65,47,88）进行直接插入排序时，当把第 7个记录65 插入到有序表时，为寻找插入位置需比较 次。三、综合题1. (1)对给定权值3, 1 , 4, 4, 5, 6,构造深度为5的哈夫曼树。(设根为第1层) (2)求树的带权路径长度。(3)链接存储上述哈夫曼树，结点中共有多少个个指针域为空，说明理由.2.(1)以2, 3, 4, 7, 8, 9作为叶结点的权，构造一棵哈夫曼树(要求每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。(2) 一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由？3.

15、(1)如下的一棵树，给出先序遍历序列(2)把1,2,3,4,5,6,7,8,9填人，使它成为一棵二叉排序树提示：设图中的树是二叉排序树，找出中序遍历序列与1, 2,9的对应关系(3)请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。4. 一组记录的关键字序列为( 46, 79, 56, 38, 40, 84)(1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果(给出逐次交 换元素的过程，要求以升序排列)5. )对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。5设查找表为(5,6,7,8,9,10,11,12,13,14)( 1 )画出对上述有

16、序表进行折半查找所对应的判定树(要求以数据元素作为树结点)(2) 给出二叉排序树的定义, 针对上述折半查找所对应的判定树的构造过程,说明判定树是否是二叉排序树(设树中没有相同结点)？(3)为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？6设查找表为(50,60,75,85,96,98,105,110,120,130)1 1) 说出进行折半查找成功查找到元素120 需要进行多少次元素间的比较？(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？3)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)四、程序填空题2 .以下函数为直接选择排序算法，对

17、a1,a2,an中的记录进行直接选择排序，完成 程序中的空格typedef struct int key 。NODE 。void selsort(NODE a,int n) int i,j,k 。NODE temp。for(i=1 。 i<= _(1) 。 i+)k=i 。for(j=i+1 。 j<= _(2) 。 j+)if(aj.key<ak.key) _(3) 。if(i!=k)temp=ai 。_(4)。(5)。3 .以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,n,完成程序中空格部分。NODE *create(n)

18、NODE *head , *p, *q 。int i。p=(NODE*)malloc(sizeof(NODE)。head= (1)。(2)。p next=NULL 。 /* 建立头结点 */for(i=1 。 i<=n。 i+) p= (3)。p data=i。p next=NULL 。q next= (4)。(5)。return(head)。3 .设有一个头指针为 head的不带头结点单向链表，且p、q是指向链表中结点类型的指 针变量，p指向链表中某结点 a (设链表中没有结点的数据域与结点a的数据域相同)写出相关语句(1).使该单向链表成为单向循环链表(2)删去a结点q=p。x=p-

19、>data。while (q->next!=NULL ) q=q->next。q=p。 p=p->next。 while(p->data!=x) q=p。_(2),4.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中 左、右指针域分别为left和right,数据域data为字符型，BT指向根结点)。void Inorder (struct BTreeNode *BT) if(BT!=NULL)7 / 36图4期末复习一答案一、单项选择题1 . C 2 . B3 . A4 . C5 . A 6 .D7 . C8 . A9 . D10 . D 1

20、1 . C9 / 3613. C14. B15. D16. C17. C 18A19. B 20 . C21. A22. A 23 . B24, B25.26. C27. B 28 . A29. C 30 . D二、填空题1. .物理(存储)2. 后进先出、先进先出3. 乘法 O(n3)4. 图状(网状)5. 86. 树形图状7. 直接前驱的左指针8. n-1,O(n)、9. p->next= head。10. s->next=p->next 。11. d=top->data。 top=top->next。12. 左指针右指针13. front= =(rear+1

21、)%MaxSize14. 2i 2i+115. 3416. h=s。17. 1318. r->next=s 。19. 120. 1221, 21534789622. 行下标、列下标、非零元素值23. 主关键字24. 3三、综合应用题1. (1)(2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58(3)共11个结点,22个指针域，除根结点外，每个结点对应一个指针域.，共10个指针域非空，故 有 22-10=12个空指针域，2.图52: 11103: 11114: 1107: 008: 019: 102 2) 2n-1个，因为非叶结点数比叶结点数少一个。3 .(1) A1 A

22、2 A4 A7 A8 A5 A9 A3 A6(2)610 / 3612134.(1)初始序列46,79,56,38,40,8440,79,56,38,40,8440,79,56,38,79,8440,38,56,38,79,8440,38,56,56,79,8440,38,46,56,79,845.(1)图7(2)二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树 非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子 树的所有结点的值都大于(若允许结点有相同的值，则大于等于)它的根结点的值。 左，右子树也是一棵二叉排序树，按定义判定树是二叉排序树。3次

23、6.(1)3 次(2)4 次图8四、程序填空题(1) n-1(2) n(3) k=j(4) ai=ak(5) a止temp11 / 36216 / 36head）。现要删除（进栈出栈可该栈的可1) p2) q=p3) (NODE*)malloc(sizeof(NODE)4) p5) q=p3(1) q->next=head 。(2) p=p->next 。(3) q->next=p->next 。41) Inorder(BT->left)2) printf( “ %c” ,BT->data)3) Inorder(BT->right)期末练习二一、单项选

24、择题1 . 结构中的元素之间存在一对多的关系是（）。A.集合B.线性结构C 树形结构D 图状结构2 .在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。A 4 B 3 C 6 D 123 . 对不带头结点的单向链表, 判断是否为空的条件是（）（设头指针为A head=NULL B head->next= =NULLC head->next= =head D head =NULL4串函数StrCat （ a,b ）的功能是进行串（）。A比较B .复制 C .赋值D .连接5. 在一个不带头结点的单循环链表中，p、 q 分别指向表中第一个结点和尾结点，现要删除第一个结点，可用的

25、语句是（）。A p=q->next 。 p=p->next 。B p->next=q。 p=p->next。C p->next=q->next 。 q=p。D p=p->next。 q->next=p 。6一棵有n 个结点采用链式存储的二叉树中，共有（）个指针域为空。A n+1 B n C n-1 D n-27一个栈的进栈序列是1 ， 2， 3， 4， 5，则栈的不可能输出序列是（）（进栈出栈可以交替进行）。A 12345 B 43512 C 45321 D 543218设一棵哈夫曼树共有n 个非叶结点，则该树有（）个叶结点。A n B n+1

26、C n-1 D 2n9一个队列的入队序列是2， 4， 6， 8，按该队列的输出序列使各元素依次入栈，该栈的可能输出序列是（）。A. 8, 6, 4, 2 B . 6, 2, 4, 8C. 8, 4, 2, 6D. 8, 2, 4, 610.从一个栈顶指针为top的链栈中删除一个结点时，用变量 x保存被删结点的值，则执行 （ ）。A. x=top->data 。 top=top next。 B . x=top->data 。C. top=top->next 。 x=top->data 。 D . top=top->next 。 x=data 。11.在一个链队中，假

27、设f和r分别为队头和队尾指针，已生成一个结点p,要为结点p赋值x,并入队的运算为（）。A . p->data=x 。 p->next=NULL 。 f->next=p 。 f=p 。B. p->data=x 。 p->next=NULL 。 r->next=p 。 r=p。C . p->data=x 。 p->next=r 。 r=s。D. p->data=x 。 p->next=f 。 f=s 。12. 一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（）个结点。A. 30 B . 20 C. 21 D . 2337,6在一维

28、数组.27）倍。B中的下标是13 .设有一个25阶的对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主序存 储到一维数组 B中（数组下标从 1开始），则矩阵中元素.（ ）。A. 34 B . 14 C . 26 D14 .在一个无向图中，所有顶点的度数之和等于边数的（A . 3 B . 2.5 C . 1.5 D . 215 .以下程序段的结果是c的值为()。char a5=" 1236789"，int *p=a, int c=0。while(*p+)c+ 。A . 8,B , 7 C . 10 D . 1216 .已知如图1所示的一个图，若从顶点 V1出发，按深度

29、优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A MV2V4V8V5V3V6WBC. V1V2V4V8V3V5V6V7,MV2 V4V5V8V3 V6”D . V1V3V6V7V2V4V5V8图117 . 一棵有23个结点，采用链式存储的二叉树中，共有（）个指针域为空。A . 24B. 25C. 23D. 4518 .已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A.abcedf B. abcefd C. aebcfd D. acfdeb图219 .在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则双亲结点的顺序编号为（）。A .

30、 i/2B . 2i-1 C . 2i+1 D . i/2-120 .对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列。.按层次B .后序 C .中序D .前序21 .设一棵哈夫曼树共有2n+1个叶结点，则该树有（）个叶结点。A . n-1 B . n C , n+1 D . 2n22 .在有序表2, 4, 7, 14, 34, 43, 47, 64, 75, 80, 90, 97, 120中，用折半查找法 查找值80时，经（）次比较后查找成功。A 4 B . 2C. 3 D. 523 .已知如图3所示的一个图，若从顶点 a出发，按深度优先搜索法进行遍历，则可能得到 的一种顶点序列为

31、（）。A . abecdf B . acfebd C . aebcfd D . aedbfc24 .有一个长度为 9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A. 25/10 B . 25/9 C . 20/9 D .17/925.已知如图4所示的一个图，若从顶点 种顶点序列为（）。A.BADEHCFGB.ADEHCGFC.BADECHFGB出发，按广度优先法进行遍历，则可能得到的一D.BADEHCFG图426 .排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进 行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是

32、（）。A冒泡 B .直接插入C .折半插入 D .选择排序27 , 一组记录的关键字序列为（46, 38, 56, 40, 79, 84）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A . 40, 38, 46, 79, 56, 84 B , 40, 38, 46, 56, 79, 84C. 40, 38, 46, 84, 56, 79 D , 38, 40, 46, 56, 79, 8428 , 一组记录的关键字序列为（46, 79, 56, 38, 40, 84）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A . 40, 38,46,79,5

33、6,84B , 40, 38, 46, 56, 79, 84C. 40, 38,46,84,56,79D , 38, 40, 46, 56, 79, 8429 .在有序表21 ,23,28,33,43,45, 46, 73, 77, 78, 89, 99,106中，用折半查找值43时，经（）次比较后查找成功。A. 6 B.3 C.8 D . 430.排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的 一端的方法，称为（）排序。A .归并B .插入C .快速D .选择二、填空题1 .本书中介绍的树形结构和 属非线性结构。2 .在二叉树的链式存储结构中，通常每个结点中设置

34、三个域，它们是 、 右指针。3 .设有一个长度为 18的顺序表，要在第 4个元素之前插入 2个元素（也就是插入元素作 为新表的第5个和第4个元素），则最少要移动元素的个数为（）。4 . 一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为5 .在双向链表中，要删除 p所指的结点，可以先用语句（p->prior） ->next=p->next ;然 再用语句。6 .串的两种最基本的存储方式是 和。7 .在一个单向链表中 p所指结点之后插入一个s所指向的结点时，应执行 s->next=p->next。和 的操作.8 . 一棵有2n-1个结点的二叉

35、树，其每一个非叶结点的度数都为2,则该树共有 个叶结点。9 . 一个栈和一个队列的输入序列都为abcdefg ,它们可能有相同的输出序列吗？（若没有则回答没有，若有则写出序列，进栈出栈可以交替进行）。10 .对于一棵具有 n个结点的二叉树，其相应的链式存储结构中共有 个指针域为 空。11 .从一个栈顶指针为top的链栈中取栈顶元素，用d保存栈顶元素的值，可执行。（结点的数据域为 data）12 . 遍历二叉排序树可得到一个有序序列。13 .循环链队列中，设front和rear分别为队头和队尾指针，（最多元素为 MaxSize,）,判断循环 链队列为空的条件是 为真。14 .如图5所示的二叉树，

36、其后序遍历序列为。15 .对稀疏矩阵进彳T压缩存储，可采用三元组表，设a是稀疏矩阵A相应的三元组表类型（结构体类型）变量，a中的一个成员项是三元组类型的结构体数组data,按书中定义，若a.data0.i=2。a.data0.j=3。a.data0.v=16。它提供的 A 数组的相关信息有 16 .如图6所示的二叉树，其先序遍历序列为 。图617 .设有一棵深度为 5的完全二叉树，该树共有 20个结点，第五层上有个叶结点。（根所在结点为第1层）18 .图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是的。（回答正确或不正确）19 .中序遍历 树可得到一个有序序列。20 .二叉树为二叉排

37、序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是 的。（回答正确或不正确）21 .如图7所示的二叉树，其后序遍历序列为 。22 .对记录序列排序是指按记录的某个关键字排序，记录序列按 排序结果是唯一 的。23 .给定一组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的， 这种说法是 的。（回答正确或不正确）24 .按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法 是稳定的，否则是不稳定的。三、综合题1. （1）说明什么是顶点活动网（AOV网）和拓扑序列（2）设有向图G如下，写出3种拓扑序列，（3）在图G中增加一条边，使图 G仅有一条拓

38、扑序列a图82.设查找表为(16,15,20,53,64,7),(1)用冒泡法对该表进行排序(要求升序排列)，写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第 j趟要进行多少次元素间的比较？(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为吉点)3.如下是一棵二叉排序树，A1,A2,A9代表1, 2, 3,9中各个不同数字，(1)给出对该树中序遍历的结果(2) A3,A5,A7的值各为多少？(3)请在该树中再插入一个结点9 .5作为叶结点，并使它仍然是一棵二叉排序树4(1)设有查找表5,14,2,6,18,7,4,16,3,依次取表中数

39、据，构造一棵二叉排序树。(2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中 序遍历的结果。5(1) 设有查找表17， 26， 14， 16， 15， 30， 18， 19， 28，依次取表中数据构造一棵二叉排序树 .(2) 对上述二叉树给出后序遍历的结果(3) . 对上述二叉树给出中后序遍历的结果(4)在上述二叉树中查找元素15共要进行多少次元素的比较?6(1 )对给定权值2， 1 ， 3， 3， 4， 5，构造哈夫曼树。( 2)同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。四、程序填空题1以下函数是二叉排序树的查找算法，

40、若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针 p (查找成功p指向查到的树结点，不成功 p指向为 NULL完成程序中的空格typedef struct Bnode int key 。struct Bnode *left 。struct Bnode *right 。 Bnode。Bnode *BSearch(Bnode *bt, int k)/* bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/ Bnode *p 。if(bt=_(1)return (bt)。p=bt 。while(p->key!=_(2) if(k<p->key)_(

41、3)。else_(4)。if(p=NULL) break。return( _(5) 。3 . 设有一个头指针为head 的不带头结点单向链表，p、 q 是指向链表中结点类型的指针变量， p 指向链表中结点a, (设链表中没有结点的数据域与结点a 的数据域相同),写出相关语句(1) .使该单向链表成为单向循环链表(2)插入结点s,使它成为a结点的直接前驱q=p。 x=p->data。while ( _(1)_ ) q=q->next。q->next=head。q=p。 p=p->next。 while(p->data!=x) q=p 。_(2)_s->next

42、=p 。 _(3)_答案一、单项选择题1 C2A 3A 4D5D 6A 7B8B9A 10 A11B12 C13D14D 15 B16 A 17 A 18 B 19A 20C 21 C22A23D24B 25C 26C27 B 28B 29 B30 D二、填空题1 图状结构2值域左指针3 154 2i 和 2i+15(p->next) ->prior=p->prior ；6顺序存储链式存储7 p->next=s。8 n9 abcdefg10 n+111 d=top->data。12中序13 front= =rear14 gdbeihfca15 A 的第一个非零元素

43、的下标为2， 3 ，元素为1616 abdefcg17 518正确19二叉排序20不正确21 51987643222 .主关键字23 .不正确24 .关键字相等的记录三、综合应用题1 .(1)原序列 16 15 20 53 64 715 16 20 53 7 64n-1 趟15 16 20 7 53 64n-j 次15 16 7 20 53 6415 7 16 20 53 647 15 16 20 53 6423 / 36(2)图102.原序列16 15 20 53 64 715 16 20 53 7 64 n-1 趟15 16 20 7 53 64 n-j 次15 16 7 20 53 64

44、15 7 16 20 53 647 15 16 20 53 64(2)图11(3)平均查找长度 =(1*1+2*2+3*3 ) /6=14/63.图12(2)中序遍历中序2, 3, 4,5, 6, 7, 14, 16, 184.图13(2)中序遍历中序2, 3, 4,5, 6, 7, 14, 16,185.(122 / 3621wpl1=4530 / 36(2)图15wpl2=456.(1)答wpl1=45四、程序填空题(1) . (1) NULL(2) k(3) p=p->left(4) p=p->right(5) p(1) &a(2) d ne

45、xt=NULL(3) p->data(4) p=p->next(5) p!=NULL3.q->next!=NULL(2) p=p->next 。(3)q->next=s。4.(1) Postorder(BT->left)(2) Postorder(BT->right)(3) printf( " d ,BT->data)期末练习三一、单项选择题1 .数据结构在计算机内存中的表示是指（）。A.数据元素之间的关系B .数据的存储结构C .数据元素的类型D .数据的逻辑结构2 .在数据结构和算法中，与所使用的计算机有关的是（）。A .数据元数间

46、的抽象关系B .数据的存储结构C .算法的时间复杂度 D.数据的逻辑结构3 .结构中的元素之间存在多对多的关系是（）。A.集合B.线性结构C .树形结构 D .图状结构4 .对顺序表，以下叙述中正确的是 （）。A.用一组地址连续的存储单元依次存放线性表的数据元素B.各个数据元素的首地址是连续的C .数据元素不能随机访问D.插入操作不需要移动元素5 .设有一个长度为 20的顺序表，要在第 5个元素之前插入1个元素（也就是插入元素作为 新表的第5个元素），则移动元素个数为（）。A . 15 B .16C.5 D . 46 .设有一个长度为 25的顺序表，要删除第 10个元素（下标从1开始），需移动

47、元素的个数为 （ ）。A . 9 B . 10 C . 15 D . 167 .在一个尾指针为rear的不带头结点的单循环链表中，插入一个s所指的结点，并作为第一）。个结点，可执行（A rear next= s 。 s next=rear next B rear next=s next 。C rear=s next D s next=rear next 。 rear next=s 。8 .设单向链表中，指针p指向结点 A,若要删除 A的直接后继，则所需修改指针的操作为（）。A.p->next=p->next->next 。B.p=p->next 。C.p=p->n

48、ext->next 。 D.p->next=p 。9元素a， b， c,d 按顺序依次进栈，则该栈的可能输出序列是（）（进栈出栈可以交替进行）。A c,a,b ， dB d， b， c,aCa,c ，b，dDd，c，a,b10元素 1，3，5，7 按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（）。（进栈出栈可以交替进行）。A 7，5，3， 1B 7， 3，1,5C 7，5，1，3D 5,1， 3， 711从一个栈顶指针为top 的链栈中取栈顶元素，用变量x 保存该元素的值，则执行（）。A x=top->data 。 top=top next 。 B

49、x=top->data 。C top=top->next 。 x=top->data 。 D top=top->next 。 x=data 。12 对一个栈顶指针为top 的链栈进行进栈操作，设P 为待进栈的结点，则执行（）。A p=top->next 。 top=top next 。 B p->next=top 。C p->next=top 。 top=p 。 D top=p 。13 .设有一个对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组 B 中（数组下标从1 开始），B 数组共有55 个元素 , 则该矩阵是（）阶的对称矩

50、阵。A 5 B 20 C 10 D 1514 .设有一个18阶的对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B 中（数组下标从1 开始），则数组中第33 号元素对应于矩阵中的元素是（）。B a7,6A a10,8 C a9,2 D a8,515 .设有一个18阶的对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B 中（数组下标从1 开始），则数组中第53 号元素对应于矩阵中的元素是（）。A a8,5 ,B a10,8C a8,1,D a7,616 .设有一个17阶的对称矩阵 A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组

51、 b中（数组下标从1开始），则矩阵中元素&6在一维数组b中的下标是（）。A 45,B 18 C 51 D 5317 . 以下程序段的结果是c 的值为（）。char * a5=“ 12378” ,“ 1237” ,“ 1236789” ,“ 1237” , “ 123708” 。int i,c=0。for（i=0 。 i<5:i+）if（StrCmp（ai,“1237”）=0）c+ 。A. 2,B .5 C .0 D . 123718 .串函数 StrCmp （ " ABCd' , " ABCD ）的值为（）。A . 0 B . -1 C .1 D .

52、319 . 一棵采用链式存储的二叉树中，共有 n个指针域被有效使用（即指针域为非空）。该二 叉树有（）个结点。A. n+1 B . n C . n-1 D . n-220 . 一棵采用链式存储的二叉树中有n个指针域为空，该二叉树共有（）个结点。A . n+1 B . n C . n-1 D . n-221 .在一棵二叉树中，若编号为 i的结点是其双亲结点的右孩子，则双亲结点的顺序编号为 （）。A. i/2.0B . i/2+1C , 2i+1 D . i/2 向下取整22 .设一棵哈夫曼树共有n个非叶结点，则该树有（）个结点。A. 2nB. 2n+2 C . 2n-1 D . 2n+123 .设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2,该树结点中共有 2n个指针域为空。则该树有（）个叶结点。A. 2nB. 2n+1 C . 2n+2 D . n24 . 一棵结点数31<n<40的完全二叉树，最后一层有