数据结构本试题集

数据结构（本）期末综合练习2017年5月有得看就不难综合练习一一、单项选择题1．设有头指针为head的带有头结点的非空单向循环链表 ,指针p指向其尾结点,要删除头结点,并使其仍为单向循环链表 ,则可利用下述语句head=head->next;（）。A．p=head;B．p=NULL;C．p->next=head;D．head=p;2.在一个单链表中p指向结点a,q指向结点a的直接后继结点b,要删除结点b,可执行（）。A．p->next=q->next;B．p=q->next;C．p->next=q;D．p->next=q;3.以下说法不正确的是线性表的链式存储结构不必占用连续的存储空间一种逻辑结构只能有唯一的存储结构一种逻辑结构可以有不同的存储结构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.数据的运算6．设有一个长度为 23的顺序表，要删除第8个元素需移动元素的个数为（）。A．16B．14C．15D．137．链表所具备的特点之一是（） 。A.可以随机访问任一结点B.需要占用连续的存储空间C.插入元素的操作不需要移动元素 D.删除元素的操作需要移动元素8．设一棵有 8个叶结点的二叉树，度数为1的结点有3个,则该树共有（）个结点。A．20B．18C．17D．169．图状结构中数据元素的位置之间存在（）的关系。A.一又t一B.多对多C.一又t多D.每一个元素都有一个直接前驱和一个直接后继10．一棵具有 5层的完全二叉树，最后一层有 4个结点，则该树总共有（）个结点。A．14B．15C．19D．1811．元素15，9，11，13按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A．13，11，9，15B．15，9，11，13C．13，11，15，9D．9，15，13，1112.设主用为“FABcCDABcdEFaBc以下模式用能与主用成功匹配的是（）。设有一个14阶的对称矩阵A（第一个元素为ai,i）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a4,3在一维数组B中的下标是（）。A.9B.10C.11D.814.元素111,113,115,117按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A.117,115,113,111B,111,113,115,117C.113,111,117,115D,117,115,111,113.在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为（）。A.18B.16C.15D.17.以下说法不正确的是（）。A.栈和队列都是线性结构B.栈的特点是后进先出C.栈和队列的特点都是先进后出D.队列的特点是先进先出.设一棵哈夫曼树共有14个非叶结点，则该树总共有（）个结点。A..30D.28.设有一个15阶的对称矩阵A（第一个元素为an）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a4,2在一维数组B中的下标是（）。A.9B.8C.7D.10.如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）0A.abecdfB.acfebdC.aebcfdD.aedbfc.如图2所示的一个图，若从顶,《70〉发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为幺/八1AxA.acedbfB.acebfdC^aebCfdD.aedfcb一三兽.队列的特点之一是:万碎是：先进 。.序列13,11,14，也次采用论图向守法，受7冒泡后，序列的结果是 o. 结构中，数据元素疝"海）亚6差言.对16个元素的序列用冒泡脚1侪制《，M需演进行 趟冒泡。.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是一.对9个元素的一组［录卫58『35f93,60）,”,78,56,41,79）进行直接插入排序（由小到大排序），当把炉7叁记录56Jf14X为寻找插入位置需比较 次。 图2.在对11个记录的序列（12,35,9,7,2,11,56,95,37,58,60进行直接插入排序时,当把第6个记录11插入到有序表时，为寻找插入位置，元素间需比较 次。（由小到大排列）.结构中的数据元素存在一对多的关系称为 结构。.哈希函数是记录关键字的值与该记录 ―之间所构造的对应关系。

.设有一棵深度为5的完全二叉树，第5层上有3个结点，该树共有个结点(根所在结点为第1层).20个元素进行冒泡法排序，通常需要进行19趟冒泡,其中第10趟冒泡共需要进行 次元素间的比较。.一棵二叉树中每一个非叶结点的度数都为 2,共有10个非叶结点，则该树共有 个结点。.一棵有19个结点的二叉树，采用链式结构存储，该树结构中有个指针域为空。.序列3,1,7,18,6,9,13,12经一趟归并排序的结果为。.中序遍历一棵 树可得到一个有序序列。.一棵有16个叶结点的哈夫曼树，则该树共有个非叶结点。.二叉排序树插入操作中，新插入的结点总是以树的结点被插入的. 遍历二叉排序树可得到一个有序序列。.广义表的(a,(d,a,b),h,(e,((i,j),k))豚度是。.广义表(f,h,(a,b,d,c),d,e,((i,j),k))l勺长度是。.序列4,2,5,3,8,6,7,9采用归并排序算法(升序),经一趟归并后，序列的结果.广义表的(h,c,g,a,(a,b),d,e,((i,j),k)豚度是。.字符用a1="teijing",a2="tef〃，a3="teifang",a4="tefi"最小的24.设有用p1="ABADF,P2="ABAFD,P3=ABADFAP4=ABAF，四个用中最小的是。三、综合题1.设查找表为序号1234567891011序列4121819375565778586117(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(2)说明成功查找到元素86需要经过多少次比较？(3)求在等概率条件下，成功查找的平均比较次数？(1)设有数据集合{50,39,17,83,111,14,65,13,91,102,49},依次取集合中各数据构造一棵二叉排序树。一组记录的关键字序列为(6,9,7,4,5,8),利用堆排序(堆顶元素是最小元素)的方法建立初始堆。(要求用完全二叉树表示)(1)一组记录的关键字序列为(26,59,36,18,20,25),给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述) 。(2)对关键字序列(26,59,36,18,20,64)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。.(1)如下表为一个长度为10的有序表，给出按折半查找对该表进行查找的判定树(2)按折半查找对该表进行查找，求在等概率情况下查找成功的平均比较次数。为了成功查找72,给出元素的比较次数。序号12345678910序列234939182560728455593,6,7,8作为叶结夫曼树应权重值的叶结点.(1)3,6,7,8作为叶结夫曼树应权重值的叶结点(2)给出具有相的哈夫曼编码。四、程序填空题.以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1,完成程序中的空格typedefstruct{intkey;……}NODE;intBinary_Search(NODEa口,intn,intk){intlow,mid,high;low=0;high=n-1;TOC\o"1-5"\h\zwhile((1) ){mid=((2) )if(a[mid].key==k)return(3);elseif(_(4)_ )low=mid+1;else(5) ;}return-1}head,以下程序的功能是.设线性表以不带头结点的单向链表存储，链表头指针为输出链表中各结点中的数据域data。完成程序中空格部分。head,以下程序的功能是#defineNULL0voidmain()

{NODE*head,*p;p=head;/*p为工作指针*/doTOC\o"1-5"\h\z{printf( 1%d(1) );⑵ ；}while( (3) )；}.以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型，BT指向根结点)。voidInorder(structBTreeNode*BT){if(BT!=NULL){__W;⑵ ；Inorder(BT-->right);}}利用上述程序对右图进行前序遍历,结果是⑶、 ；4.以下程序是后序遍历二叉树的递归算法的程序,中空格部分(树结构中左、右指针域分别为left和right,数据域data4.以下程序是后序遍历二叉树的递归算法的程序,中空格部分(树结构中左、右指针域分别为left和right,数据域data为空格部分。voidInorder(structBTreeNode*BT){中型，BT指向赧结点)。完成程序中if(BT!=NULL){Inorder(BT->left);__(1 dbc―⑵ 图3}5.顺序查找算法如下，完成程序中空格部分intsearch(NODEa口,intn,intk)/*在a[0],a[1]・・a[n-1],中查找关键字等于k的记录，查找成功返回记录的下标，失败时返回-1*/{inti=0;while(i<n&&a[i].key(1) )_=(2)_ if(_=(3)___)returni;elsereturn-1;}综合练习一答案、单项选择题.C2.A3.B4.D5.A6.C7.C8.B9.B10.C11.C12.A13.A14.D15.D16.C17.A18.B19.D20.B二、填空题先出

11,13,12,14,15,17树型15行下标列下标数组元素4次3树形存储位置181013.，3,207,18,6,9,12,13.二叉排序树.15.叶.中序20.，4,22.63,5,6,8,7,31.(1)55188541965867(2)3次(3)平均查找长度=1(1+2.(1)(2)4,5,7,9,6,83.(1)18,20,(2535*2+33105013.，3,207,18,6,9,12,13.二叉排序树.15.叶.中序20.，4,22.63,5,6,8,7,31.(1)55188541965867(2)3次(3)平均查找长度=1(1+2.(1)(2)4,5,7,9,6,83.(1)18,20,(2535*2+3310505811398349451749111981491图626,36102756565125(2)20,18,26,36,59,644.(1)(2) (1+2*2+3*4+4*3)/10=29/10(1)⑵10000200013001601710811四、程序填空题.(1)low<=hig(2)(low+high)/23(3)mid;(4)a[mid227121510(2)20,18,26,36,59,644.(1)(2) (1+2*2+3*4+4*3)/10=29/10(1)⑵10000200013001601710811四、程序填空题.(1)low<=hig(2)(low+high)/23(3)mid;(4)a[mid22712151072图8<k图9(5)high匚mid-1;(1)!=k⑵i++；p->datap=p->nextp!=NULLprintf( "％3,BT->data)Inorder(BT->left)abdfecInorder(BT->right)printf( "％3,BT->data)(3)a[i].key==k综合练习二一、单项选择题.设头指针为head的非空的单向循环链表，指针p指向尾结点，则满足表达式（）为真。A.p->next==NULLB.p==NULLCp->next==headD.p==head.数据的存储结构包括数据元素的表示和（）。A.数据处理的方法C.相关算法D.数据元素的类型D.数据元素间的关系的表示.一种逻辑结构（）。A,可以有不同的存储结构B.只能有唯一的存储结构C.是指某一种数据元素之间的存储关系D.是指某一种数据元素的性质4.在一个头指针为head的单向链表中，p指向尾结点，要使该链表成为单向循环链表可执行（）。A．p=head->next;B．head->next=p;C．head->next=p->next;D．p->next=head;5．链表所具备的特点之一是（） 。A.可以随机访问任一结点B.占用连续的存储空间C.插入删除元素的操作不需要移动元素结点 D.可以通过下标对链表进行直接访问6．元素 111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A．117，115，113，111B．111，113，115，117C．117，115，111，113D．113，111，117，1157．线性结构中数据元素的位置之间存在（）的关系。A.一■又B—'B.一■对多C.多又t多D.每一个元素都有一个直接前驱和一个直接后继8．以下说法正确的是（）。A.栈的特点是先进后出B.栈的特点是先进先出C.队列的特点是先进后出D.栈和队列的特点都是先进后出9．在一个单向链表中p所指结点之后插入一个 s所指的结点时，可执行（）。A．p->next=s;s->next=p->nextB．p->next=s->next;C．p=s->nextD．s->next=p->next;p->next=s;.设有一个20阶的对称矩阵A（第一个元素为ai,i）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从 1开始），则矩阵中元素 a6,2在一维数组B中的下标是（）。A．24B．i7C．i6D．23．元素ii，i3，i5，i7按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A． i7，i5， i3，iiB． ii， i3， i5， i7C． i7，i5， ii，i3D． i3， ii， i7， i5.设一棵有2n+1个结点的二叉树，除叶结点外每个结点度数都为 2,则该树共有（）个叶结点。A．nB．n+1C．n+2D．n-1.设有一个20阶的对称矩阵A（第一个元素为ai,i）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从 1开始），则矩阵中元素 a5,2在一维数组B中的下标是（）。A．11B．12C．13D．10．已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abecdfB．aecbdfC．aebcfdD．aedfcba图1.设一棵哈夫曼树共有11个非叶结点，则该树有（）个叶结点。A.22B.10C.11D.12.线性表以（）方式存储，能进行折半查找。A.关键字有序的顺序B.顺序C链接D.二叉树.一棵具有38个结点的完全二叉树，最后一层有（）个结点。A.7B.5C.6D.8.一棵具有38个结点的完全二叉树，最后一层有（）个结点。A.7B.5C.6D.8.已知如图2所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）0A.abecdfB.acfebdC.aebcfdD.aedfcb.对一个栈顶指针为top的链栈进行出幽11晨小变量e保存栈顶元素的值，则执行（）。!\=top->next;top->data=e;=top->next;e=top->data;=top->data;top=top->next;=top->next;e=datar；.c二、填空题 ...字符用a1='BEIJING',a2="BEF，^^''BEFANG,a4="BEI〃最小的是—_、 « —Gj.数组a经初始化chara□=“English”'a[7]中小妍5是 。.把数据存储到计算机中，并具体体现数据元圉阍的逻辑结构称为 .设有用p1="ABADF,P2="ABAFD,P3="ABADFAP4=abaF,四个用中最大的是.设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为。.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为<.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为。.设有一个长度为20的顺序表，要插入一个元素，并作为第8个元素，需移动元素的个数为C.设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为 2,则该树共有一个结点。.结构中的数据元素存在多对多的关系称为 结构。.在对一组序列（45,29,87,12,6,63,55,37,78进行直接插入排序时，当把第8个记录37插入到有序表时，为寻找插入位置需比较 次。（由小到大排序）.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 个结点。（根所在结点为第1层）.n个元素进行冒泡法排序，通常需要进行 一趟冒泡。

.一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为 2,则该树共有个叶结点。.一棵有21个结点的哈夫曼树，该树中有 个叶结点。.在对一组记录(55,39,97,22,16,73,65,47,88进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较 次。(由小到大排序. 遍历二叉排序树可得到一个有序序列。个元素进行冒泡法排序，第j趟冒泡要进行 次元素间的比较。.广义表(a,(a,b),d,e,((i,j),k)用长度是。.一棵有n个叶结点的哈夫曼树，则该树共有 个结点。.广义表的(a,(a,b),d,e,((i,j),k)深度是。.中序遍历叫得到一个有序序列。.序列14,12,15,13,18,16采用冒泡排序算法(升序),经一趟冒泡后，序列的结果是0.广义表((a,b),d,e,((i,j),k))的长度是。三、综合题.设查找表为(7,15,21,22,40,58,68,80,88,89,120)元素的下标依次为1,2,3,……，11.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(2)说明成功查找到元素40需要经过多少次比较？(3)求在等概率条件下，成功查找的平均比较次数？.(1)设有数据集合{40,29,7,73,101,4,55,2,81,92,39},依次取集合中各数据构造一棵二叉排序树。(2)一组记录的关键字序列为(5,8,6,3,4,7),利用堆排序(堆顶元素是最小元素)的方法建立初始堆。(要求用完全二叉树表示).(1)一组记录的关键字序列为(47,80,57,39,41,46),给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述) 。(2)对关键字序列(47,80,57,39,41,85)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。(3)如图3所示的二叉树，给出其前序遍历序列。棵哈夫曼树.(1)以2,3,4,7,8,9作为叶结点的慎^邓棵哈夫曼树(2)给出上述哈夫曼树叶结点的哈夫曼编码。 ・⑶一组记录的关键字序列为(47,29,个关键字为分割元素，给出经过一施U分后结果。四、程序填空题1.以下程序是中序遍历二叉心派»3算法的程序jg5),利用快速排序，以第(ft小到大排序)(树结构中左、右指针域分别为left⑶一组记录的关键字序列为(47,29,个关键字为分割元素，给出经过一施U分后结果。四、程序填空题1.以下程序是中序遍历二叉心派»3算法的程序jg5),利用快速排序，以第(ft小到大排序)(树结构中左、右指针域分别为left和right,数我voidInorder(structBTreeNode*BT)if(BT!=NULL){ [Inorder(BT->left);}；X2K;}利用上述程序对右图进行中序遍历,abcfde成程序中空格部分指向根结点)图4结果是(3);2.设线性表为(6,10,16,4),以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。8292图8292图7#de巾neNULLOvoidmain(){NODEa,b,c,d,*head,*p;二6;=10;=16;=4;/*d是尾结点*/head=(1);二&b;二&c;=&d;(2);/*以上结束建表过程*/p=head;/*p为工作指针，准备输出链表*/do{printf( "r%d3));(4);}while((5));}.以下冒泡法程序对存放在a[1],a[2],……，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。voidbsort(NODEa口,intn){NODEtemp;(1);j++);(1);j++);⑵;i++)for(j=1;{flag=0;for(i=1;if(a[i].key>a[i+1].key){flag=1;temp=a[i];13r;14K;}if(flag==0)break;}}程序中flag的功能是(5).以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型，voidInorder(structBTreeNode*BT){if(BT!=NULL){-UK;_L2L;Inorder(BT->right);}}利用上述程序对右图进行遍历，结果是(3);

综合练习二答案一、单项选择题C2.D3.A4.D5.C6.C7.A8.A9.D10.BC12.B13.B14...二、填空题.字符串的结束符.物理结构（存储结构）2i+12i10.图状12n-1n+1113中序22.二叉排序树,14,13,15,16,1824.4三、综合题1.⑴(2)4次)/11=32.⑴(2)3,4,6,40729107383910181)/11=32.⑴(2)3,4,6,407291073839101813(1)39,41,46,80,47,57(2)41,39,4757,84.⑴⑵2:00003345857,84.⑴⑵2:00003345890001001101118151.(D(2)prin[1.(D(2)prin[f(Inorde%d>data)(BT->1001(3)31,29,37,47,70,8四、程序填《题图图10dbeafc&ad->next=NULLp->datap=p->nextp!=NULLj<=n-1i<=n-ja[i]=a[i+1]a[i+1]=temp(5)当某趟冒泡中没有出现交换则已排好序，结束循环Inorder(BT->left)printf("%c,BT->data)bedafc综合练习三一、单项选择题1.数据的存储结构包括数据元素的表示和()0A.数据处理的方法B.数据元素的类型C.相关算法D.数据元素间的关系的表示.设有头指针为head的不带头结点的非空的单向循环链表，指针p指向其尾结点，要删除第一个结点，则可利用下述语句head=head->next;和()。A.p=head;B.p=NULL;Cp->next=head;D.head=p;.树状结构中数据元素的位置之间存在()的关系。A.每一个元素都有一个直接前驱和一个直接后继 B.一对一C.多Xt多D.一对多.以下说法正确的是 （）。线性表的链式存储结构必须占用连续的存储空间一种逻辑结构可以有不同的存储结构一种逻辑结构只能有唯一的存储结构D.线性表的顺序存储结构不必占用连续的存储空间5．设有一个长度为 26的顺序表，要插入一个元素,并使它成为新表的第6个元素,需移动元素的个数为（）。A．21B．22C．20D．196．把数据存储到计算机中，并具体体现 （）称为物理结构。A.数据的处理方法B.数据的性质C.数据白^运算D.数据元素间的逻辑关系7．头指针为 head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头结点的单向循环链表 ,可执行head=head->nex;和（）。A．p=head->nextB．head->next=pC．head->next=p->nextD．p->next=head;8．顺序表所具备的特点之一是（） 。A.可以随机访问任一结点B,不需要占用连续的存储空间C.插入元素的操作不需要移动元素 D.删除元素的操作不需要移动元素9．元素 111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A．117，115，113，111B．111，113，115，117C．117，115，111，113D．113，111，117，11510．图状结构中数据元素的位置之间存在（）的关系。A.一■又B—'B.一■对多C.多又t多D.每一个元素都有一个直接前驱和一个直接后继11．以下说法正确的是（）。A.栈的特点是先进先出B.栈的特点是先进后出C.队列的特点是先进后出12．元素 20，14，16，18按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A．18，16，14，20B．20，14，16，18C．18，16，20，14D．14，20，18，16D.栈和队列的特点都是后进后出13.设有一个20阶的对称矩阵A（第一个元素为ai,i）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组 B中（数组下标从 1开始），则矩阵元素 a6,2在一维数组B中的下标是（）。A．2iB．i7C．28D．23.设有一个12阶的对称矩阵A（左上角第一个元素为ai,i）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从 i开始），则矩阵中元素a5,4在一维数组 B中的下标是（） 。A.14B.12C.13D.11.设有用p1="ABADF,P2="ABAFD,P3=ABADFA,P4="ABAF,以下四个用中最大白^是（）。A.p3B.p2C.p1D.p4.设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（）。A.25B.14C.15D.23.数组a经初始化chara[]="English”同7]中存放的是（）。A.字符串的结束符B.字符hC.、'h〃D.变量h.在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（）。A.12B,9C.11D.10.设主用为“ABcCDABcdEFaBc以下模式用能与主用成功匹配的是（）。一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。A.14B.15C.19D.18.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）,A.2i+1B.2i-1C.2iD.2i+2.如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A.abcdfgeB.abcedfgC.acbfedgD.abcfgde24.字符用'、abcd321ABCD的子用是（）。A.'21ABCB."abcABCD图2.、'321a〃.线性表以（）方式存储，能进行折半查找。A.链接B.顺序C.关键字有序的顺序D.二叉树.数组a经初始化chara[]="English"；a[1]中存放的是（）。A.字符nB.字符EC.、'n〃D.、'E〃.一棵具有38个结点的完全二叉树，最后一层有（）个结点。A.7B.5C.6D.828.如图3所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）A.abecdfB.acfebdC.aebcfdD.aedfcb29.下图的拓扑序列是()。A.52346B.23645C.30.下图的拓扑序列是()A.52346B.52364C.、填空题.结构中的数据元素存在多对多的关系称为.栈的特点之一是：兀系个元素进行冒泡法排a29.下图的拓扑序列是()。A.52346B.23645C.30.下图的拓扑序列是()A.52346B.52364C.、填空题.结构中的数据元素存在多对多的关系称为.栈的特点之一是：兀系个元素进行冒泡法排aedb*3进、出栈的次序是：先进j趟冒泡要进行__•达元蔡间的比较。.对稀疏矩阵进行压缩存储，矩阵中幅幅上零元素对应的三元组包括该元素的三项信息.中序遍历 树可得到一个有序序列。.在对10个记录的序列(9,35,19,77,2,10,53,45,27,68进行直接插入排序时，当把第6个记录10插入到有序表时，为寻找插入位置，元素间需比较 次。(按升序排序).待排序的序列为8,3,4,1,2,5,9采用直接选才¥排序算法，当进行了两趟选择后，结果序列为()。.字符用a1="beijing",a2="bef〃,a3="beifang”,a4="befi”最/4的.广义表((a,b),d,e,((i,j),k))的长度是。10.10个元素进行冒泡法排序，，其中第5趟冒泡共需要进行 次元素间白比较。11.广义表的(c,a,(a,b),d,e,((i,j),k)豚度是。. 遍历一棵二叉排序树可得到一个有序序列。.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有个元素。.广义表(c,(a,b,c),(d,e,f),((i,j),k)用长度是..在对一组记录(50,49,97,22,16,73,65,47,88进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较 次。.广义表的(c,(b,a,b),f,e,((i,j),k)深度是..一棵有5个叶结点的哈夫曼树，该树中总共有_____个结点。.序列4,2,5,3,8,6采用冒泡排序算法(升序),经一趟冒泡后，结果序列是。.设有一棵深度为4的完全二叉树，第四层上有 5个结点，该树共有 个结点。(根所在结点为第1层)。.待排序的序列为8,3,4,1,2,5,9采用直接选才¥排序算法，当进行了两趟选择后，结果序列为.设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为<.线性表用 方式存储可以随机访问。.有以下程序段chara[]="English”;char*p=a;intn=0;while(*p!='\0'){n++;p++;}结果中，n的值是。.顺序表,,6,5,1,2,4,3,8,7经过一趟(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)说明不成功查找元素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),给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述) 。⑵对关键字序列(36,69,46,28,30,74)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。(3)设有数据集合{30,73,101,4,8,9,2,81},依次取集合中各数据构造一棵二叉排序树。四、程序填空题.设线性表为(16,20,26,24),以不带头结点的单向链表存储，链表头指针为 head,以下程序的功能是输出链表中各结点中的数据域 data。Structnode{intdata;structnode*next;};typedefstructnodeNODE;#defineNULL0voidmain(){NODE*head,*p;p=head;/