数据结构本试题集

1、-. z.数据构造本期末综合练习2017年5月有得看就不难综合练习一一、单项选择题1设有头指针为head的带有头结点的非空单向循环链表, 指针p指向其尾结点, 要删除头结点,并使其仍为单向循环链表,则可利用下述语句head =head-ne*t ;。 Ap =head; Bp=NULL; Cp-ne*t =head; Dhead=p; 2在一个单链表中p指向结点a, q指向结点a的直接后继结点b，要删除结点b，可执行。Ap-ne*t=q-ne*t ; Bp=q-ne*t; Cp-ne*t=q; Dp-ne*t=q; 3. 以下说法不正确的选项是 A. 线性表的链式存储构造不必占用连续的存储空间

2、 B一种逻辑构造只能有唯一的存储构造 C. 一种逻辑构造可以有不同的存储构造D线性表的顺序存储构造必须占用连续的存储空间4在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行;和p-ne*t=s; Ap= s; B p-ne*t=s-ne*t; Cp=s-ne*t; D s-ne*t=p-ne*t; 5把数据存储到计算机中，并具体表达( )称为物理构造。 A. 数据元素间的逻辑关系B数据的处理方法C数据的性质 D数据的运算6设有一个长度为23的顺序表，要删除第8个元素需移动元素的个数为。 A16 B14 C15 D13 7链表所具备的特点之一是。 A可以随机访问任一结点 B需要占用

3、连续的存储空间 C插入元素的操作不需要移动元素 D删除元素的操作需要移动元素8设一棵有8个叶结点的二叉树，度数为1的结点有3个,则该树共有个结点。A20 B18 C17 D16 9图状构造中数据元素的位置之间存在的关系。 A一对一 B多对多 C一对多 D每一个元素都有一个直接前驱和一个直接后继10一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有个结点。 A14 B15 C19 D18 11元素15，9，11，13按顺序依次进栈，则该栈的不可能输出序列是进栈出栈可以交替进展。 A13，11，9，15 B15，9，11，13 C13，11，15，9 D9， 15，13，11 12.设主串

4、为FABcCDABcdEFaBc，以下模式串能与主串成功匹配的是。 A. EFaBc B. ABCdE C. DABCC D .FAbcC 13设有一个14阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角局部以行序为主序存储到一维数组B中数组下标从1开场，则矩阵中元素a4,3在一维数组B中的下标是。 A9 B10 C11 D8 14元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是进栈出栈可以交替进展。 A117，115，113，111 B111，113，115，117 C113，111，117，115 D117，115，111，113 15在一棵

5、二叉树中，假设编号为8的结点存在右孩子，则右孩子的顺序编号为。 A18 B16 C15 D17 16以下说法不正确的选项是。 A栈和队列都是线性构造 B栈的特点是后进先出 C. 栈和队列的特点都是先进后出 D队列的特点是先进先出17设一棵哈夫曼树共有14个非叶结点，则该树总共有个结点。 A29 B.27 C30 D28 18设有一个15阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角局部以行序为主序存储到一维数组B中数组下标从1开场，则矩阵中元素a4,2在一维数组B中的下标是。A9 B8 C7 D10 19如图1所示的一个图，假设从顶点a出发，按深度优先搜索法进展遍历，则

6、可能得到的一种顶点序列为。 Aabecdf Bacfebd Caebcfd Daedbfc bbdfeca图120如图2所示的一个图，假设从顶点a出发，按深度优先搜索法进展遍历，则可能得到的一种顶点序列为。 Aacedbf Bacebfd Caebcfd Daedfcb bbdfcea图2二、填空题 1. 队列的特点之一是：元素进、出队的次序是:先进_。2. 序列13,11,14,12,17,15,采用冒泡排序算法,经一趟冒泡后,序列的结果是_。3 _构造中，数据元素间存在一对多的关系。4. 对16个元素的序列用冒泡排法进展排序，通常需要进展_趟冒泡。5对稀疏矩阵进展压缩存储，矩阵中每个非零元

7、素对应的三元组包括该元素的三项信息是_ _。6. 对9个元素的一组记录58，35，93，20，12，78，56，41，79进展直接插入排序(由小到大排序) ，当把第7个记录56插入有序表，为寻找插入位置需比拟 _次。7在对11个记录的序列(12，35, 9, 7 ,2, 11 ,56 , 95 ,37,58 ,60)进展直接插入排序时，当把第6个记录11 插入到有序表时，为寻找插入位置，元素间需比拟_次。由小到大排列8构造中的数据元素存在一对多的关系称为_构造。9哈希函数是记录关键字的值与该记录_ _之间所构造的对应关系。10设有一棵深度为5的完全二叉树，第5层上有3个结点，该树共有_个结点。

8、根所在结点为第1层 1120个元素进展冒泡法排序，通常需要进展19趟冒泡 ,其中第10趟冒泡共需要进展 _ _次元素间的比拟。12一棵二叉树中每一个非叶结点的度数都为2，共有10个非叶结点，则该树共有 _ 个结点。13一棵有19个结点的二叉树,采用链式构造存储,该树构造中有_ 个指针域为空。14. 序列3,1,7,18,6,9,13,12经一趟归并排序的结果为_ _ _。15中序遍历一棵 _树可得到一个有序序列。16一棵有16个叶结点的哈夫曼树，则该树共有_个非叶结点。17二叉排序树插入操作中,新插入的结点总是以树的_ 结点被插入的18_遍历二叉排序树可得到一个有序序列。19. 广义表的( a

9、 , (d,a ,b) , h , (e ,( (i ,j ) ,k ) )深度是_ 。 20. 广义表( f , h , (a ,b, d, c) , d , e ,( (i ,j ) ,k ) )的长度是_ _。21. 序列4 , 2 , 5 , 3 , 8 , 6 , 7, 9,采用归并排序算法(升序),经一趟归并后,序列的结果 _ _。22. 广义表的( h ,c，g, a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ _。23. 字符串a1=teijing, a2 =tef , a3= teifang, a4=tefi最小的是 _。 24设有串p1=A

10、BADF,P2=ABAFD，P3=ABADFAP4=ABAF, 四个串中最小的是 _ 。三、综合题 1设查找表为序号1234567891011序列41218193755657785861171画出对上述查找表进展折半查找所对应的判定树树中结点用下标表示2说明成功查找到元素86需要经过多少次比拟？3求在等概率条件下，成功查找的平均比拟次数？2.1设有数据集合50，39，17，83，111，14，65，13，91，102，49，依次取集合中各数据构造一棵二叉排序树。 (2) 一组记录的关键字序列为6，9，7，4，5，8，利用堆排序堆顶元素是最小元素的方法建立初始堆。(要求用完全二叉树表示)3.(1

11、) 一组记录的关键字序列为26，59，36，18，20，25，给出利用堆排序堆顶元素是最小元素的方法建立的初始堆要求以完全二叉树描述。 (2) 对关键字序列(26,59,36,18,20,64)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。4. (1) 如下表为一个长度为10的有序表，给出按折半查找对该表进展查找的判定树 (2) 按折半查找对该表进展查找，求在等概率情况下查找成功的平均比拟次数。为了成功查找72 ,给出元素的比拟次数。序号12345678910序列234939182560728455595(1) 以1，2，3 ，6，7，8作为叶结点的权，构造一棵哈夫曼树 (

12、2) 给出具有相应权重值的叶结点的哈夫曼编码。四、程序填空题1以下函数在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE a , int n, int k) int low, mid, high; low=0; high=n-1; while(_(1)_) mid=(_(2)_) if(amid.key=k) return _(3)_; else if (_(4)_) low=mid+1; else _(5)_; return -

13、1 2.设线性表以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。完成程序中空格局部。#define NULL 0void main( ) NODE *head ,*p ;p=head; /*p为工作指针*/ do printf(%dn, _(1)_);_(2)_; while(_(3)_); 3.以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格局部树构造中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点。 void Inorder (struct BTreeNode *BT) if(BT!=NULL)

14、_(1)_; _(2)_; Inorder(BT- right); 利用上述程序对右图进展前序遍历，结果是_(3)_;eeabcdf图34.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格局部树构造中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点。完成程序中空格局部。 void Inorder (struct BTreeNode *BT) if( BT!=NULL) Inorder(BT-left); _(1)_ _(2)_ 5. 顺序查找算法如下, 完成程序中空格局部。 int search (NODE a ,int n , int k ) /* 在a

15、0,a1an-1,中查找关键字等于k的记录，查找成功返回记录的下标，失败时返回 -1*/ int i=0; while( i n & ai.key _(1)_) _(2)_ if (_(3)_) return i; else return -1; 综合练习一答案一、单项选择题1 C 2 A 3 B4D 5A 6C 7 C 8B 9 B 10C11 C 12 A 13 A 14D 15D 16C 17 A 18B 19D 20B二、填空题1先出211,13,12,14,15,17 3树型415 5行下标列下标数组元素64次73 8树形9存储位置1018111012. 2113 20 14. 1，

16、3，7，18，6，9，12，1315二叉排序树161517. 叶18. 中序19.4206 21.2，4，3，5，6，8，7，9223 23.a224. P1 三、综合题1747411852101396图4 18 85 4 19 65 86 12 37 77 117(2) 3次(3) 平均查找长度 =(1+2*2+3*4+4*4)/11=34965102496510291141111713508339图5(1)(2) 4 , 5 , 7 , 9 , 6 , 84949575965568图63. (1) 18，20，25，59，26，36 181820255936图7(2) 20，18，26，3

17、6，59，647257252813647910图8(1+2*2+3*4+4*3)/10=29/10 4次5 (1)667386132271512图9 (2)1 0000 2 00010016 0110 8 11四、程序填空题1.(1) low=high (2)( low+high)/2 (3) mid; (4) amid.keydata2p=p-ne*t3p!=NULL3.1 printf(%c,BT-data)2Inorder(BT-left)3a b d f e c41 Inorder(BT-right)2 printf(%c,BT-data)5. (1) !=k (2) i+; (3)

18、ai.key= =k综合练习二一、单项选择题1设头指针为head的非空的单向循环链表, 指针p指向尾结点,则满足表达式为真。 Ap-ne*t = =NULL Bp= =NULL Cp-ne*t= =head Dp= =head 2.数据的存储构造包括数据元素的表示和。 A . 数据处理的方法 C . 相关算法 D. 数据元素的类型 D. 数据元素间的关系的表示3一种逻辑构造。 A可以有不同的存储构造 B只能有唯一的存储构造C是指*一种数据元素之间的存储关系 D是指*一种数据元素的性质4在一个头指针为head的单向链表中，p指向尾结点，要使该链表成为单向循环链表可执行。 Ap= head-ne*

19、t; B head-ne*t=p; Chead-ne*t=p-ne*t; D p-ne*t=head;5链表所具备的特点之一是。 A可以随机访问任一结点 B占用连续的存储空间 C插入删除元素的操作不需要移动元素结点 D可以通过下标对链表进展直接访问6元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是进栈出栈可以交替进展。 A117，115，113，111 B111，113，115，117 C117，115，111，113 D113，111，117，115 7线性构造中数据元素的位置之间存在的关系。 A一对一 B一对多 C多对多 D每一个元素都有一个直接前驱和一个直接后继

20、8以下说法正确的选项是。 A栈的特点是先进后出B栈的特点是先进先出 C队列的特点是先进后出 D. 栈和队列的特点都是先进后出9在一个单向链表中p所指结点之后插入一个s所指的结点时，可执行。 Ap-ne*t= s; s-ne*t= p-ne*t Bp-ne*t=s-ne*t; Cp=s-ne*t Ds-ne*t=p-ne*t; p-ne*t=s; 10设有一个20阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角局部以行序为主序存储到一维数组B中数组下标从1开场，则矩阵中元素a6,2在一维数组B中的下标是。A24 B17 C16 D23 11元素11，13，15，17按顺序依

21、次进栈，则该栈的不可能输出序列是进栈出栈可以交替进展。 A17，15，13，11 B11，13，15，17 C17，15，11，13 D13，11，17，15 12设一棵有2n+1个结点的二叉树，除叶结点外每个结点度数都为2，则该树共有个叶结点。An Bn+1 Cn+2 Dn-1 13设有一个20阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角局部以行序为主序存储到一维数组B中数组下标从1开场，则矩阵中元素a5,2在一维数组B中的下标是。 A11 B12 C13 D10 14如图1所示的一个图，假设从顶点a出发，按广度优先搜索法进展遍历，则可能得到的一种顶点序列为。 Aa

22、becdf Baecbdf Caebcfd Daedfcb bdbdfeca图115设一棵哈夫曼树共有11个非叶结点，则该树有个叶结点。 A22 B10 C11 D12 16线性表以方式存储，能进展折半查找。 A关键字有序的顺序 B顺序CD二叉树17一棵具有38个结点的完全二叉树，最后一层有个结点。 A7 B5 C6 D8 18一棵具有38个结点的完全二叉树，最后一层有个结点。 A7 B5 C6 D8 19如图2所示的一个图，假设从顶点a出发，按深度优先搜索法进展遍历，则可能得到的一种顶点序列为。 Aabecdf Bacfebd Caebcfd Daedfcb bbdfeca图220 .对一个

23、栈顶指针为top的链栈进展出栈操作，用变量e保存栈顶元素的值，则执行。 A. e= top-ne*t; top-data=e; B. top=top-ne*t; e=top-data;C. e=top-data; top=top-ne*t; D. top=top-ne*t; e=data; 二、填空题1. 字符串a1=BEIJING, a2 =BEF , a3= BEFANG, a4=BEI最小的是_ _。2. 数组a经初始化 char a =English; a7中存放的是_。3把数据存储到计算机中，并具体表达数据元素间的逻辑构造称为_ _。4设有串p1=ABADF,P2=ABAFD，P3=

24、ABADFAP4=ABAF, 四个串中最大的是_。5设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为_ _。6在一棵二叉树中，假设编号为i的结点存在右孩子，则右孩子的顺序编号为_。7在一棵二叉树中，假设编号为i的结点存在左孩子，则左孩子的顺序编号为_ _。8设有一个长度为20的顺序表，要插入一个元素，并作为第8个元素，需移动元素的个数为_。9设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有_ _ 个结点。10构造中的数据元素存在多对多的关系称为_构造。11在对一组序列 (45,29,87,12,6,63,55,37,78)进展直接插入排序时，当把第8个记录37

25、 插入到有序表时，为寻找插入位置需比拟_次。由小到大排序12设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_个结点。根所在结点为第1层13 n个元素进展冒泡法排序，通常需要进展_ _趟冒泡。14一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2，则该树共有_个叶结点。15一棵有21个结点的哈夫曼树,该树中有_ 个叶结点。16在对一组记录(55,39,97,22,16,73,65,47,88)进展直接插入排序时，当把第7个记录65 插入到有序表时，为寻找插入位置需比拟_次。(由小到大排序17_遍历二叉排序树可得到一个有序序列。18. n个元素进展冒泡法排序，第j趟冒泡要进展_ _

26、次元素间的比拟。19. 广义表( a , (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_。20一棵有n个叶结点的哈夫曼树，则该树共有_个结点。21. 广义表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 。22中序遍历_可得到一个有序序列。 23. 序列14,12,15,13,18,16,采用冒泡排序算法(升序),经一趟冒泡后,序列的结果是 _ _。24广义表( (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_ 。三、综合题1设查找表为(7,15,21,22,40,58,68,80,88,89,120

27、) ,元素的下标依次为1,2,3,，11.1画出对上述查找表进展折半查找所对应的判定树树中结点用下标表示2说明成功查找到元素40需要经过多少次比拟？3求在等概率条件下，成功查找的平均比拟次数？2. 1设有数据集合40，29，7，73，101，4，55，2，81，92，39，依次取集合中各数据构造一棵二叉排序树。 (2)一组记录的关键字序列为5，8，6，3，4，7，利用堆排序堆顶元素是最小元素的方法建立初始堆。(要求用完全二叉树表示)3. (1) 一组记录的关键字序列为47，80，57，39，41，46，给出利用堆排序堆顶元素是最小元素的方法建立的初始堆要求以完全二叉树描述。 (2) 对关键字序

28、列( 47,80,57,39,41,85)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。 (3) 如图3所示的二叉树，给出其前序遍历序列。ggfabdec图34 (1) 以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树 (2) 给出上述哈夫曼树叶结点的哈夫曼编码。 (3)一组记录的关键字序列为37，70，47，29，31，85，利用快速排序，以第一个关键字为分割元素，给出经过一次划分后结果。由小到大排序四、程序填空题1以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格局部树构造中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点。e

29、fefabcd图4if(BT!=NULL) Inorder(BT-left);1;2;利用上述程序对右图进展中序遍历，结果是3;2.设线性表为6，10，16，4，以下程序用说明构造变量的方法建立单向链表，并输出链表中各结点中的数据。#define NULL 0 void main( ) NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d是尾结点*/head=1;a.ne*t=&b;b.ne*t=&c;c.ne*t=&d;2; /*以上完毕建表过程*/p=head; /*p为工作指针，准备输出链表*/ do print

30、f(%dn,3);4; while(5);3以下冒泡法程序对存放在a1，a2，an中的序列进展排序，完成程序中的空格局部，其中n是元素个数，要求按升序排列。void bsort (NODE a , int n) NODE temp; int i,j,flag; for(j=1;1;j+); flag=0; for(i=1;2;i+) if(ai.keyai+1.key)flag=1; temp=ai;3;4;if(flag= =0)break;程序中flag的功能是54.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格局部树构造中左、右指针域分别为left和right，数据域data为

31、字符型，BT指向根结点。efefabcd图5 if(BT!=NULL)1;2; Inorder(BT-right); 利用上述程序对右图进展遍历，结果是3;综合练习二答案一、单项选择题1C 2 D 3A 4D 5 C 6C 7 A 8A 9 D 10B 11C 12B 13B 14B 15. D 16A 17. A 18A 19.D 20.C二、填空题1. a22. 字符串的完毕符3. 物理构造(存储构造)4. p2 5. 1462i+1 7 2i 8. 139. 2n-1 10图状11. 5 1212 13 n-114n+1 15 11 16317中序18. n-j19. 520.2n-12

32、1. 322二叉排序树23. 12,14,13,15,16,18244 三、综合题1747411852101396图6(2)4次395539559281410172407329图72(1) (2) 3,4,6,8,5,7 39394658567图83(1) 39，41，46，80，47，57 39394146478057图9(2) 41，39，47，57，80，85(3)abdefcg97597589243331518图10 (1)(2 2：00000001001101101(3) 31,29,37,47,70,85 四、程序填空题1.1 printf(%c,BT-data) 2 Inorde

33、r(BT-right)3dbeafc 21&a2d-ne*t=NULL3p-data4p=p-ne*t5p!=NULL31j=n-12ileft)2 printf(%c,BT-data)3bedafc综合练习三一、单项选择题 1.数据的存储构造包括数据元素的表示和。 A . 数据处理的方法 B. 数据元素的类型 C . 相关算法 D. 数据元素间的关系的表示2设有头指针为head的不带头结点的非空的单向循环链表, 指针p指向其尾结点, 要删除第一个结点,则可利用下述语句 head=head-ne*t;和。 Ap =head; Bp=NULL; Cp-ne*t =head; Dhead=p;3树

34、状构造中数据元素的位置之间存在的关系。 A每一个元素都有一个直接前驱和一个直接后继 B一对一 C多对多 D一对多4. 以下说法正确的选项是( )。 A. 线性表的链式存储构造必须占用连续的存储空间 B. 一种逻辑构造可以有不同的存储构造 C一种逻辑构造只能有唯一的存储构造 D线性表的顺序存储构造不必占用连续的存储空间5设有一个长度为26的顺序表，要插入一个元素,并使它成为新表的第6个元素,需移动元素的个数为。 A21 B22 C20 D196把数据存储到计算机中，并具体表达( )称为物理构造。 A数据的处理方法 B数据的性质 C数据的运算 D. 数据元素间的逻辑关系7头指针为head的带头结点

35、的单向循环链表，p所指向尾结点，要使该链表成为不带头结点的单向循环链表, 可执行head=head-ne*;和。 Ap= head-ne*t B head-ne*t=p Chead-ne*t=p-ne*t D p-ne*t=head;8顺序表所具备的特点之一是。 A可以随机访问任一结点 B不需要占用连续的存储空间 C插入元素的操作不需要移动元素 D删除元素的操作不需要移动元素 9元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是进栈出栈可以交替进展。 A117，115，113，111 B111，113，115，117 C117，115，111，113 D113，111，

36、117，115 10图状构造中数据元素的位置之间存在的关系。 A一对一 B一对多 C多对多 D每一个元素都有一个直接前驱和一个直接后继11以下说法正确的选项是。 A栈的特点是先进先出 B栈的特点是先进后出 C队列的特点是先进后出12元素20，14，16，18按顺序依次进栈，则该栈的不可能输出序列是进栈出栈可以交替进展。 A18，16，14，20 B20，14，16，18 C18，16，20，14 D14，20，18，16 D. 栈和队列的特点都是后进后出 13. 设有一个20阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角局部以行序为主序存储到一维数组B中数组下标从1开场

37、，则矩阵元素a6,2 在一维数组B中的下标是。 A21 B17 C28 D23 14设有一个12阶的对称矩阵A(左上角第一个元素为a1,1)，采用压缩存储的方式，将其下三角局部以行序为主序存储到一维数组B中数组下标从1开场，则矩阵中元素a5,4在一维数组B中的下标是。 A14 B12 C13 D11 15设有串p1=ABADF,P2=ABAFD，P3=ABADFA,P4=ABAF,以下四个串中最大的是( )。 A p3 B p2 C p1 D p416设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为。 A25 B14 C15 D23 17.数组a经初始化 char a =Engl

38、ish; a7中存放的是。 A. 字符串的完毕符 B. 字符h C. h D. 变量h 18在一棵二叉树中，假设编号为5的结点存在右孩子，则右孩子的顺序编号为。 A12 B9 C11 D10 19.设主串为ABcCDABcdEFaBc，以下模式串能与主串成功匹配的是。 A. Bcd B. BCd C. ABC D. Abc20一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有个结点。 A14 B15 C19 D18 21在一棵二叉树中，假设编号为i的结点存在左孩子，则左孩子的顺序编号为。 A2i+1 B2i-1 C2i D2i+2 22 .如图1所示，假设从顶点a出发，按图的广度优先搜

39、索法进展遍历，则可能得到的一种顶点序列为。 Aabcdfge Babcedfg Cacbfedg Dabcfgde ggfabdec图123如图2所示，假设从顶点a出发，按图的广度优先搜索法进展遍历，则可能得到的一种顶点序列为。 Aabecdf Baecbdf Caebcfd Daedfcb bdbdfeca图224.字符串abcd321ABCD的子串是。 A. 21ABC B.abcABCDC. abcD D. 321a25线性表以方式存储，能进展折半查找。 A B顺序C关键字有序的顺序D二叉树26.数组a经初始化char a =English; a1中存放的是。 A. 字符n B. 字符E

40、 C. n D. E27一棵具有38个结点的完全二叉树，最后一层有个结点。 A7 B5 C6 D8 28如图3所示，假设从顶点a出发，按图的深度优先搜索法进展遍历，则可能得到的一种顶点序列为。 Aabecdf Bacfebd Caebcfd Daedfcb bbdfeca图329.下列图的拓扑序列是( )。 A5 2 3 4 6 B2 3 6 4 5 C5 6 2 3 4 D. 2 3 5 6 4223454346530.下列图的拓扑序列是( )。 A5 2 3 4 6 B5 2 3 6 4 C5 6 4 2 3 D. 2 3 4 5 62234543465图3二、填空题1构造中的数据元素存在

41、多对多的关系称为_构造。2. 栈的特点之一是：元素进、出栈的次序是:先进_。3. n个元素进展冒泡法排序，第j趟冒泡要进展_ _次元素间的比拟。4对稀疏矩阵进展压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是_ _。5中序遍历_树可得到一个有序序列。6在对10个记录的序列(9，35,19, 77 ,2, 10 ,53, 45,27,68)进展直接插入排序时，当把第 6个记录10 插入到有序表时，为寻找插入位置，元素间需比拟_次。按升序排序7. 待排序的序列为8,3,4,1,2,5,9, 采用直接选择排序算法,当进展了两趟选择后,结果序列为( )。 8. 字符串a1=beijing

42、, a2 =bef , a3= beifang, a4=befi最小的是 _。9广义表( (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是_ 。 1010个元素进展冒泡法排序，,其中第5趟冒泡共需要进展_ _次元素间的比拟。 11. 广义表的( c， a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_。12_遍历一棵二叉排序树可得到一个有序序列。13. 对稀疏矩阵进展压缩存储,可采用三元组表，一个有10 行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有个元素。14. 广义表( c , (a ,b,c) , ( d , e ,f )

43、 , ( (i ,j ) ,k ) )的长度是_ . 15在对一组记录(50, 49, 97, 22, 16, 73, 65, 47, 88)进展直接插入排序时，当把第7个记录65 插入到有序表时，为寻找插入位置需比拟_次。 16. 广义表的( c , (b,a ,b) , f , e ,( (i ,j ) ,k ) )深度是_ . 17. 一棵有5个叶结点的哈夫曼树,该树中总共有_ 个结点。18. 序列4 , 2 , 5 , 3 ,8, 6,采用冒泡排序算法(升序),经一趟冒泡后, 结果序列是 _。19. 设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_个结点。根所在结点为第1层

44、。 20. 待排序的序列为8,3,4,1,2,5,9, 采用直接选择排序算法,当进展了两趟选择后,结果序列为_.。21设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为_。22. 线性表用_方式存储可以随机访问。23. 有以下程序段 char a =English; char *p=a; int n=0; while( *p!=0) n+; p+; 结果中，n的值是_。 24. 顺序表,6，5，1, 2, 4, 3, 8，7经过一趟(1,1)归并后的结果序列为_。三、综合题 1有一个长度为11的有序表(1, 2, 11, 15, 24, 28, 30, 56, 69, 70, 80

45、) , 元素的下标依次为 1,2,3,11，按折半查找对该表进展查找。 (1画出对上述查找表进展折半查找所对应的判定树。2说出成功查找到元素56,需要依次经过与哪些元素的比拟？3说出不成功查找元素72,需要进展元素比拟的次数？2设查找表为序号1234567891011序列81622234159698189901211画出对上述查找表进展折半查找所对应的判定树。2说明成功查找到元素90需要经过多少次比拟？3说明不成功查找元素82，依次与哪些元素进展了比拟，需要经过多少次比拟？3. (1)一组记录的关键字序列为57，90，67，50，51，56，利用堆排序堆顶元素是最小元素的方法建立初始堆要求以完

46、全二叉树描述。 (2)对关键字序列(56,51,71,54,46,106)利用快速排序，以第一个关键字为分割元素，给出经过一次划分后结果。 (3) 一组记录的关键字序列为 60,47，80，57，39，41，46,30，利用归并排序的方法,分别给出(1,1) 归并、(2,2) 归并、(4,4) 归并的结果序列。4.(1) 一组记录的关键字序列为36，69，46，28，30，35，给出利用堆排序堆顶元素是最小元素的方法建立的初始堆要求以完全二叉树描述。 (2) 对关键字序列(36,69,46,28,30,74)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。(3) 设有数据集合30,73,101,4,8,9,2,81，依次取集合中各数据构造一棵二叉排序树。四、程序填空题1.设线性表为16，20，26，24，以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数