数据结构本试题集

1、数据结构（本）期末综合练习2017年5月有得看就不难综合练习一、单项选择题指针 p 指向其尾结点 , 要删除1设有头指针为 head 的带有头结点的非空单向循环链表头结点 , 并使其仍为单向循环链表A p =head; B p=NULL; C 2在一个单链表中 p 指向结点 a, q 行（ ）。A p->next=q->next ;C p->next=q;3. 以下说法不正确的是, 则可利用下述语句 p->next =head; D 指向结点a的直接后继结点b,要删除结点head =head->next ;( head=p; p=q->next; p->

2、;next=q;）。b,可执A. 线性表的链式存储结构不必占用连续的存储空间 B 一种逻辑结构只能有唯一的存储结构C. 一种逻辑结构可以有不同的存储结构D.线性表的顺序存储结构必须占用连续的存储空间4在一个单向链表中 , 在 p 所指结点之后插入一个 s 所指的结点时,可执行（）; 和p->next=s;A . p= s; B . p->next=s->next;C. p=s->next;D. s->next=p->next;5. 把数据存储到计算机中,并具体体现 （ ） 称为物理结构 。A. 数据元素间的逻辑关系B. 数据的处理方法C. 数据的性质D .数

3、据的运算6 .设有一个长度为 23的顺序表,要删除第 8个元素需移动元素的个数为（）。A . 16 B . 14 C . 15 D . 137. 链表所具备的特点之一是（）。A .可以随机访问任一结点B .需要占用连续的存储空间C .插入元素的操作不需要移动元素 D .删除元素的操作需要移动元素8. 设一棵有 8 个叶结点的二叉树,度数为 1 的结点有 3 个, 则该树共有（ ）个结点。A. 20B18 C . 17 D . 169. 图状结构中数据元素的位置之间存在（）的关系。A.一对一B.多对多C .一对多D.每一个元素都有一个直接前驱和一个直接后继10. 一棵具有 5层的完全二叉树,最后

4、一层有 4 个结点,则该树总共有（ ）个结点。A . 14 B . 15 C . 19 D . 1811. 元素 15, 9, 11, 13 按顺序依次进栈,则该栈的不可能输出序列是（）进栈出栈可以交替进行）A . 13, 11, 9 , 15B15, 9, 11, 13C . 13, 11 , 15, 9D9, 15 , 13, 1112.设主串为“ FABcCDABcdEFaB”以下模式串能与主串成功匹配的是（A. EFaBcB. ABCdEC. DABCCD .FAbcC13 .设有一个14阶的对称矩阵 A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维

5、数组B中（数组下标从1开始），则矩阵中元素一维数组B中的下标是（A . 9B. 10 C . 11 D . 814 .元素111, 113, 115, 117按顺序依次进栈，则该栈的不可能输出序列是（栈出栈可以交替进行）°A . 117, 115, 113, 111C . 113, 111, 117, 11515 .在一棵二叉树中，若编号为A . 1816 .Aa4,3 在)(进C.17.A18.111 , 113, 115, 117D. 117, 115, 111, 1138的结点存在右孩子，则右孩子的顺序编号为（.16）°B以下说法不正确的是（.栈和队列都是线性结构栈和

6、队列的特点都是先进后出 设一棵哈夫曼树共有 14个非叶结点,.29B.27 C.17.栈的特点是后进先出.队列的特点是先进先出）个结点。.28D则该树总共有（.30 D设有一个15阶的对称矩阵A（第一个元素为ai,i），采用压缩存储的方式，将其下角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素 a4,2在一维数组B中的下标是（A. 9 B .19 .如图1所示的一个图，到的一种顶点序列为（A . abecdf B）°.8 C .,若从顶点 a出发,)°.acfebd C7 D . 10按深度优先搜索法进行遍历，则可能得.aebcfd D . aedbf

7、c图120 如图2所示的一个图，若从顶点 a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）°A . acedbf B. acebfd C.aebcfd D . aedfcba二、填空题1. 队列的特点之一是：元素进、出队的次序是：先进。2. 序列13,11,14,12,17,15,采用冒泡排序算法，经一趟冒泡后，序列的结果是 。3. 结构中，数据元素间存在一对多的关系。4. 对16个元素的序列用冒泡排法进行排序，通常需要进行 趟冒泡。5 .对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是_。6. 对9个元素的一组记录(58, 35, 93,

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

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

10、 ) ,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= " teiji ng" , a2 =" tef " , a3=" teifa ng ", a4=“ tefi "最小的24 .设有串 p仁” ABADF ,P

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

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

13、1)以1 , 2, 3 , 6, 7, 8作为叶结点的权，构造一棵哈夫曼树(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)returnelse if ()low=mid+1;else (5)

14、Jreturn -12. 设线性表以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。完成程序中空格部分。#define NULL 0void mai n() NODE *head ,*p ;p=head; /*p为工作指针*/dopri ntf(“ dn”，);_ Jwhile( (3)_ );3. 以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、 右指针域分别为left和right，数据域data为字符型，BT指向根结点)。void Ino rder (struct BTreeNode *BT)if(BT!=NUL

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

16、1,中查找关键字等于 k的记录，查找成功返回记录的下标,败时返回-1*/ int i=0;while( i< n && ai.key (1)(2) _ _if (3)return i;else return -1;综合练习一答案一、单项选择题I. C 2. A 3. B4 .D 5.A 6 .C7 .C 8. B9. B 10.C 11 .C12 . A 13. A 14. D 15. D 16. C 17 . A 18. B 19 .D 20 . B二、填空题1 .先出2 . 11,13,12,14,15,173. 树型4 . 155 .行下标列下标数组元素6 . 4次

17、7 . 38 .树形9.存储位置10 . 18II. 1012. 2113 . 2014. 1 , 3, 7, 18, 6, 9, 12, 1315 .二叉排序树16 . 1517. 叶18. 中序19.420 . 621.2 , 4, 3, 5, 6, 8, 7, 922 . 323. a224. P1三、综合题(2) 3 資(3) JMm為木w"+2*2+3*4+4*4)AMU3GOCD7493. 18 , 20, 25, 59, 26, 36图7 20 , 18, 26, 36, 59, 644.(1+2*2+3*4+4*3)/10=29/1045.图91 00002 0001

18、3 0016 017 108 11四、程序填空题1. (1) low<=high(2) ( low+high)/2(3) mid;(4) amid.key<k(5) high=mid-1;2.(1) p->data(2) p=p->next(3) p!=NULL3.(1) printf(“ C' ,BT->data)(2) Inorder(BT->left)(3) a b d f e c4(1) Inorder(BT->right)(2) printf( “%c”,BT->data)5.(1) !=k(2) i+;(3) ai.key=

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

20、 head->next; Chead->next=p->next;5链表所具备的特点之一是（A 可以随机访问任一结点D）。 head->next=p; p->next=head;C 插入删除元素的操作不需要移动元素结点6元素 111， 113， 115， 117 栈出栈可以交替进行） 。A 117， 115， 113， 111 117， 115， 111 ， 113按顺序依次进栈，占用连续的存储空间D 可以通过下标对链表进行直接访问则该栈的不可能输出序列是（）线性结构中数据元素的位置之间存在（ 一对一B多对多D以下说法正确的是（栈的特点是先进后出B.栈的特点是先进

21、先出）。 iii ， ii3， ii5 ， ii7 ii3， iii， ii7， ii5)的关系。一对多每一个元素都有一个直接前驱和一个直接后继C 队列的特点是先进后出D. 栈和队列的特点都是先进后出）。9 在一个单向链表中p所指结点之后插入一个s所指的结点时，可执行（A p->next= s; s->next= p->next B p->next=s->next;Cp=s->nextDs->next=p->next; p->next=s;10设有一个20阶的对称矩阵A（第一个元素为ai,i），采用压缩存储的方式，将其下角部分以行序为主序存

22、储到一维数组b中（数组下标从1开始），则矩阵中元素 a®2在一维数组B中的下标是（）。A. 24B. 17 C . 16 D . 2311.元素11, 13, 15, 17按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A .17, 15, 13, 11B.11,13, 15, 17C .17, 15, 11, 13D.13,11, 17, 1512.设一棵有2n+1个结点的二叉树，除叶结点外每个结点度数都为2,则该树共有（）个叶结点。A. nB. n+1 C . n+2 D . n-113 .设有一个20阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方

23、式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素 a5,2在一维数组B中的下标是（）。A . 11B. 1214 .已知如图1所示的一个图，若从顶点 得到的一种顶点序列为（A . abecdf B）。.aecbdf.13 D . 10a出发，按广度优先搜索法进行遍历，则可能aebcfd D . aedfcbC15 .设一棵哈夫曼树共有11个非叶结点，则该树有（）个叶结点。A.22B.10C.11D. 1216 .线性表以（,）方式存储，能进行折半查找。A.关键字有序的顺序B.顺序C.链接D.二叉树17 .一棵具有38个结点的完全二一叉树，取后'层有（）

24、个结点。A.7B.5C.6D.818 .一棵具有38个结点的完全二一叉树，取后'层有（）个结点。A.7B. 5C.6D.819 .已知如图2所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。20 .对一个栈顶指针为top的链栈进行出栈操作，用变量 e保存栈顶元素的值，则执行 ( )°A. e= top->n ext; top->data=e;C. e=top->data; top=top->n ext;B. top=top->n ext; e=top->data;二、填空题1. 字符串 a1= ” BE

25、IJING" , a2 =是_°2. 数组a经初始化 char a=D. top=top->n ext; e=data;BEF , a3=” BEFANG , a4=“ BEI"最小的"English ” ; a7中存放的是 °3 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为 °4 .设有串 p仁” ABADF ,P2= ” ABAFD, P3=” ABADFA P4=' ABAF', 四个串中最大的是5 设有一个长度为 22的顺序表，要删除第 8个元素需移动元素的个数为 °6 .在一棵二叉

26、树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为 °7 .在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为 °&设有一个长度为 20的顺序表，要插入一个元素，并作为第8个元素，需移动元素的个数为°9 .设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有 个结点。10 .结构中的数据元素存在多对多的关系称为 结构。11.在对一组序列(45,29,87,12,6,63,55,37,78)进行直接插入排序时，当把第8个记录37插入到有序表时，为寻找插入位置需比较 次。(由小到大排序)12 .设有一棵深度为 4的完全二叉树，

27、第四层上有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趟冒泡要进行 _次元素间的比较。19. 广义表(a , (a ,b) , d , e ,(

28、(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),元素的下标依次为 1,2,3,11.(1) 画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(

29、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),给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述)。对关键字序列(47,80,57,39,41,85)采用快

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

31、t BTreeNode *BT)if(BT!=NULL)In order(BT->left);(1)；(2);利用上述程序对右图进行中序遍历，结果是(3)2. 设线性表为(6, 10, 16, 4),以下程序用说明结构变量的方法建立单向链表，并输出 链表中各结点中的数据。#defi ne NULL 0void mai n()NODE a,b,c,d,*head,*p;a. data=6;b. data=10;c. data=16;d. data=4; /*d是尾结点 */head= (1);a. n ext=&b;b. n ext=&c;c. n ext=&d;(

32、2): /*以上结束建表过程*/p=head; /*p为工作指针，准备输出链表*/dopri ntf(“ 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=O;for(i=1;(2);i+)if(ai.key>ai+1.key)flag=1;temp=ai;(3)；(4；if(flag= =0)break;程序中flag 的

33、功能是 4.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、 右指针域分别为left和right，数据域data为字符型，BT指向根结点)。void In order (struct BTreeNode *BT)if(BT!=NULL)(1) ;(2) ;In order(BT->right);利用上述程序对右图进行遍历，结果是(3)图5综合练习二答案一、单项选择题I. C 2 . D 3 . A 4 . D 5 . C 6 . C 7 .A 8. A 9 . D 10. BII. C 12 . B 13 . B 14 . B 15. D 16. A 17. A

34、 18. A 19.D 20.C二、填空题1. a22. 字符串的结束符3. 物理结构(存储结构)4. p25. 146 . 2i+17 . 2i8. 139. 2n-110 .图状11. 512 . 1213. n-114. n+115. 1116. 317. 中序18. n-j19. 521. 322.23.20.2 n-1二叉排序树12,14,13,15,16,18244综合题1 .(1)图6(2) 4 次(3) ASL=(1+2*2+3*4+4*4)/11=3402.(1)2973395510181(2) 3,4,6,8,5,73(1) 39 , 41 , 46, 80, 47, 57

35、(2) 41 , 39, 47, 57, 80, 85 abdefcg4.(1)图10（2）2 ： 00004 00015 0018 109 1110 01（3）31,29,37,47,70,85四、程序填空题1.（1）printf（ “ %c” ,BT->data）（ 2） Inorder（BT->right）（3） dbeafc2（1）&a（ 2） d->next=NULL（ 3） p->data（ 4） p=p->next（ 5） p!=NULL3（ 1） j<=n-1（ 2） i<=n-j（3） ai=ai+1（ 4） ai+1=tem

36、p（5）当某趟冒泡中没有出现交换则已排好序，结束循环4（ 1） Inorder（BT->left）（ 2） printf（ “ %c” ,BT->data）（ 3） bedafc综合练习三一、单项选择题1. 数据的存储结构包括数据元素的表示和（ ）。A . 数据处理的方法 B. 数据元素的类型C . 相关算法D.数据元素间的关系的表示, 指针 p 指向其尾结点 和（ ）。2设有头指针为 head 的不带头结点的非空的单向循环链表 删除第一个结点 , 则可利用下述语句 head=head->next;A p =head; B p=NULL; C p->next =head

37、; D head=p;3树状结构中数据元素的位置之间存在（ ）的关系。A 每一个元素都有一个直接前驱和一个直接后继 B 一对一 C 多对多 D 一对多 4. 以下说法正确的是 （ ） 。A. 线性表的链式存储结构必须占用连续的存储空间B. 一种逻辑结构可以有不同的存储结构C 一种逻辑结构只能有唯一的存储结构D 线性表的顺序存储结构不必占用连续的存储空间5设有一个长度为 26的顺序表，要插入一个元素 ,并使它成为新表的第 6个元素 ,需移动元素的个数为（ ）。A 21 B22C20196把数据存储到计算机中，并具体体现 A 数据的处理方法 B C 数据的运算 D.（ ） 称为物理结构。数据的性质

38、 数据元素间的逻辑关系7头指针为 head 的带头结点的单向循环链表， p 所指向尾结点，要使该链表成为不带头结点的单向循环链表可执行 head=head->nex; 和（ ）。A p= head->nextBC head->next=p->nextD8顺序表所具备的特点之一是（）。A 可以随机访问任一结点BC 插入元素的操作不需要移动元素 head->next=p p->next=head;不需要占用连续的存储空间D 删除元素的操作不需要移动元素）（进9 元素 111，113，115，117 按顺序依次进栈，则该栈的不可能输出序列是（栈出栈可以交替进行）A

39、 117，115，113，111B111，113，115， 117C 117，115，111，113D113，111，117， 11510图状结构中数据元素的位置之间存在（）的关系。A 一对一B一对多C 多对多D每一个元素都有一个直接前驱和一个直接后继11以下说法正确的是（）。A 栈的特点是先进先出B 栈的特点是先进后出C 队列的特点是先进后出12元素 20，14，16，18 按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行） 。Ai8，i6，i4，20B20，i4，i6，i8C i8，i6，20，i4Di4，20，i8，i6D. 栈和队列的特点都是后进后出13. 设有一个2

40、0阶的对称矩阵A（第一个元素为ai,i），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组b中（数组下标从1开始），则矩阵元素a6,2在一维数组A . 21B中的下标是（B. 17.2314 .设有一个12阶的对称矩阵a（左上角第一个兀素为a1,1），米用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5,4在一维数组b中的下标是（A . 1415 .设有串大的是（A . p3B. 12p仁” ABADF ,P2=” ）BCABAFD,.13 DP3=” ABADFA ,P4=”.11ABAF ,以下四个串中最16.设有一个长度为o.

41、P222的顺序表,C .要删除第p1D. p48个元素需移动元素的个数为（A . 25 B17.数组a经初始化字符串的结束符、h”A.C.18A.14 C char a=B.D.在一棵二叉树中，若编号为.12 B . 9 C.15“ En glish字符h变量h5的结点存在右孩子，则右孩子的顺序编号为（.11 D . 10D . 23” ;a7中存放的是（19.设主串为“ ABcCDABcdEFaB”以下模式串能与主串成功匹配的是（A. Bcd B. BCd C. ABC D. Abc20 . 一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（A . 14B. 15C. 19 D .

42、 1821 .在一棵二叉树中，若编号为A . 2i+122 .如图1所示，种顶点序列为（A . abcdfge.15i的结点存在左孩子，则左孩子的顺序编号为（B. 2i-1若从顶点a出发，）。B . abcedfg C个结点。23 .如图2所示,若从顶点到的一种顶点序列为（A . abecdf BC . 2i D. 2i+2按图的广度优先搜索法进行遍历，则可能得到的一.acbfedg Da出发，按图的广度优先搜索法进行遍历，则可能得）°.aecbdf C . aebcfd D . aedfcba24. 字符串” abcd321ABCD的子串是（）。A. ” 21ABCB.abcABC

43、DC. abcDD.321a25.线性表以（）方式存储，能进行折半查找。B .顺序 C.关键字有序的顺序D.二叉树A.字符nB.C."n"DA .链接26.数组a经初始化 char a=English ” ;a1字符Ew e“中存放的是（）。27.棵具有38个结点的完全二叉树，最后一层有（）个结点。28 .如图3所示，若从顶点 到的一种顶点序列为（A . abecdf Ba出发，按图的深度优先搜索法进行遍历，则可能得）。.acfebd C . aebcfd D . aedfcb29.卜图的拓扑序列是（) 。A . 5 2 3 4 6BC . 5 6 2 3 4D. 2 3

44、5 6 42 3 6 4 56530.AF图的拓扑序列是.5 2 3 4 6.5 2 3 6 41 .2.填空题结构中的数据元素存在多对多的关系称为 结构。栈的特点之一是：元素进、出栈的次序是：先进。n个元素进行冒泡法排序，第j趟冒泡要进行 _次元素间的比较。对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息3.4. 是 。5 中序遍历树可得到一个有序序列。6 .在对 10 个记录的序列(9 , 35,19, 77 ,2, 10 ,53, 45,27,68) 当把第6个记录10插入到有序表时，(按升序排序)7.序列待排序的序列为834,1,2,5,9,为()。字符串 a

45、1= "beijing " , a2 =为寻找插入位置，元素间需比较进行直接插入排序时,次。采用直接选择排序算法，当进行了两趟选择后，结果"bef" , a3=" beifa ng ", a4=“ befi "最小的8.是。9 .广义表(a ,b) , d , e ,( (i ,j ) ,k )的长度是.10 . 10个元素进行冒泡法排序，其中第5趟冒泡共需要进行11. 广义表的(c , a , (a ,b) , d , e ,( (i ,j ) ,k )12. 遍历一棵二叉排序树可得到一个有序序列。13. 对稀疏矩阵进行压

46、缩存储，可采用三元组表，一个有95个零元素，其相应的三元组表共有 个元素。14. 广义表(c , (a ,b,c) , ( d , e ,f ) , ( (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个叶结点的哈夫曼树,该树中总共有_o次元素间的比较。深度是10行10列的稀疏矩阵A共有的长度是进行直接插入排序时，当把_次。深度是.个结点。18. 序列4,2,5,3 ,8,

47、 6,采用冒泡排序算法(升序),经一趟冒泡后，结果序列是O19.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 个结点。(根所在结点为第1层)。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经

48、过一趟(1,1)归并后的结果序列为 。三、综合题1 有一个长度为11 的有序表(1,2, 11, 15, 24, 28, 30, 56, 69, 70, 80),元素的下标依次为1,2,3,11，按折半查找对该表进行查找。(1)画出对上述查找表进行折半查找所对应的判定树。(2) 说出成功查找到元素56,需要依次经过与哪些元素的比较？(3) 说出不成功查找元素72,需要进行元素比较的次数？2 .设查找表为序号1234567891011序列8162223415969818990121(1) 画出对上述查找表进行折半查找所对应的判定树。(2) 说明成功查找到元素90需要经过多少次比较？(3) 说明不

49、成功查找元素82,依次与哪些元素进行了比较，需要经过多少次比较？3. (1) 一组记录的关键字序列为(57, 90, 67, 50, 51, 56),利用堆排序(堆顶元素是最小元素)的方法建立初始堆(要求以完全二叉树描述)。(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)