文档介绍：该【数据结构（本）期末综合练习题 】是由【1781111****】上传分享，文档一共【30】页，该文档可以免费在线阅读，需要了解更多关于【数据结构（本）期末综合练习题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..综合练****一一、,指针p指向其尾结点,要删除头结点,并使其仍为单向循环链表,则可利用下述语句head=head->next;()。=head;=NULL;->next=head;=p;,q指向结点a的直接后继结点b,要删除结点b,可执行()。->next=q->next;=q->next;->next=q;->next=q;,在p所指结点之后插入一个s所指的结点时,可执行();和p->next=s;=s;->next=s->next;=s->next;->next=p->next;,并具体体现()称为物理结构。,要删除第8个元素需移动元素的个数为()。()。,度数为1的结点有3个,则该树共有()个结点。()的关系。,最后一层有4个结点,则该树总共有()个结点。,9,11,13按顺序依次进栈,则该栈的不可能输出序列是()(进栈出栈可以交替进行)。,11,9,,9,11,,11,15,,15,13,“DABcdEFaBc”,以下模式串能与主串成功匹配的是()。:..14阶的对称矩阵A(第一个元素为a),采用压缩存储的方式,将其下三角部分以行序为主序存1,1储到一维数组B中(数组下标从1开始),则矩阵中元素a在一维数组B中的下标是()。4,,113,115,117按顺序依次进栈,则该栈的不可能输出序列是()(进栈出栈可以交替进行)。,115,113,,113,115,,111,117,,115,111,,若编号为8的结点存在右孩子,则右孩子的顺序编号为()。()。,则该树总共有()个结点。(第一个元素为a),采用压缩存储的方式,将其下三1,1角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵中元素a4,2在一维数组B中的下标是()。,若从顶点a出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为()。,若从顶点a出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为()。:..:元素进、出队的次序是:先进_______。,11,14,12,17,15,采用冒泡排序算法,经一趟冒泡后,序列的结果是________。,数据元素间存在一对多的关系。,通常需要进行________趟冒泡。,矩阵中每个非零元素对应的三元组包括该元素的三项信息是_______。(58,35,93,20,12,78,56,41,79)进行直接插入排序(由小到大排序),当把第7个记录56插入有序表,为寻找插入位置需比较________次。(12,35,9,7,2,11,56,95,37,58,60)进行直接插入排序时,当把第6个记录11插入到有序表时,为寻找插入位置,元素间需比较_________次。(由小到大排列)。。,第5层上有3个结点,该树共有_______个结点。(根所在结点为第1层),通常需要进行19趟冒泡,其中第10趟冒泡共需要进行________次元素间的比较。,共有10个非叶结点,则该树共有_______个结点。,采用链式结构存储,该树结构中有_____个指针域为空。,1,7,18,6,9,13,12经一趟归并排序的结果为______。。,则该树共有_______个非叶结点。,。(a,(d,a,b),h,(e,((i,j),k)))深度是________。(f,h,(a,b,d,c),d,e,((i,j),k))的长度是________。,2,5,3,8,6,7,9,采用归并排序算法(升序),经一趟归并后,序列的结果________。(h,c,g,a,(a,b),d,e,((i,j),k))深度是_______。=〝teijing〞,a2=〝tef〞,a3=〝teifang〞,a4=“tefi〞最小的是________。=”ABADF”,P2=”ABAFD”,P3=”ABADFA”P4=”ABAF”,四个串中最小的是________。三、:..1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)(2)说明成功查找到元素86需要经过多少次比较?(3)求在等概率条件下,成功查找的平均比较次数?2.(1)设有数据集合{50,39,17,83,111,14,65,13,91,102,49},依次取集合中各数据构造一棵二叉排序树。一组记录的关键字序列为(6,9,7,4,5,8),利用堆排序(堆顶元素是最小元素)的方法建立初始堆。(要求用完全二叉树表示)3.(1)一组记录的关键字序列为(26,59,36,18,20,25),给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述)。(2)对关键字序列(26,59,36,18,20,64)采用快速排序,给出以第一个关键字为分割元素,经过一次划分后的结果。4.(1)如下表为一个长度为10的有序表,给出按折半查找对该表进行查找的判定树(2)按折半查找对该表进行查找,求在等概率情况下查找成功的平均比较次数。为了成功查找72,给出元素的比较次数。序号**********序列234939182560728455595.(1)以1,2,3,6,7,8作为叶结点的权,构造一棵哈夫曼树(2)给出具有相应权重值的叶结点的哈夫曼编码。4:..[0]到a[n-1]中,用折半查找算法查找关键字等于k的记录,查找成功返回该记录的下标,失败时返回-1,完成程序中的空格struct{intkey;??}NODE;intBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0;high=n-1;while(__(1)______){mid=(__(2)______)if(a[mid].key==k)return__(3)______;elseif(__(4)______)low=mid+1;else__(5)______;}return-1}5:..(3)mid;(4)a[mid].key<k(5)high=mid-1;,以下程序的功能是输出链表中各结点中的数据域data。完成程序中空格部分。#defineNULL0voidmain(){NODE*head,*p;p=head;/*p为工作指针*/don”,___(1)_____);___(2)_____;}while(___(3)_____);}2(1)p->data(2)p=p->next(3)p!=,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。voidInorder(structBTreeNode*BT){if(BT!=NULL){__(1)________(2)______;Inorder(BT-->right);}}利用上述程序对右图进行前序遍历,结果是__(3)______;abcde6f图3:..)printf(“%c”,BT->data)(2)Inorder(BT->left)(3),完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。完成程序中空格部分。voidInorder(structBTreeNode*BT){if(BT!=NULL){Inorder(BT->left);___(1)________(2)_____}4.(1)Inorder(BT->right)(2)printf(“%c”,BT->data),完成程序中空格部分。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;}(1)!=k(2)i++;(3)a[i].key==k一、:..,13,12,14,15,,3,7,18,6,9,12,,4,3,5,6,8,7,:..1.(1)5561885934196586101712377711725811图4(2)3次(3)平均查找长度=(1+2*2+3*4+4*4)/11=32.(1)5039831749651**********图5(2)4,5,7,9,6,89:..495759658图61820,25,59,26,36182025592636图7(2)20,18,26,36,59,644.(1)5281369471072图8(2)(1+2*2+3*4+4*3)/10=29/104次5.(1)10:..2712**********(2)1000020001300160171081111:..一、,指针p指向尾结点,则满足表达式()为真。->next====->next====()。()。,p指向尾结点,要使该链表成为单向循环链表可执行()。=head->next;->next=p;->next=p->next;->next=head;()。,113,115,117按顺序依次进栈,则该栈的不可能输出序列是()(进栈出栈可以交替进行)。,115,113,,113,115,,115,111,,111,117,()的关系。()。,可执行()。->next=s;s->next=p->->next=s->next;=s->->next=p->next;p->next=s;(第一个元素为a),采用压缩存储的方式,将其下三1,1角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵中元素a6,2在一维数组B中的下标是()。,13,15,17按顺序依次进栈,则该栈的不可能输出序列是()(进栈出栈可以交替进行)。,15,13,,13,15,,15,11,,11,17,+1个结点的二叉树,除叶结点外每个结点度数都为2,则该树共有()个叶结点。++-1:..20阶的对称矩阵A(第一个元素为a),采用压缩存储的方式,将其下三角部分以行序为主序存1,1储到一维数组B中(数组下标从1开始),则矩阵中元素a在一维数组B中的下标是()。5,,若从顶点a出发,按广度优先搜索法进行遍历,则可能得到的一种顶点序列为()。,则该树有()个叶结点。()方式存储,能进行折半查找。,最后一层有()个结点。,最后一层有()个结点。,若从顶点a出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为()。,用变量13e保存栈顶元素的值,则执行:..。=top->next;top->data=e;=top->next;e=top->data;=top->data;top=top->next;=top->next;e=data;二、填空题字符串a1=〝BEIJING〞,a2=〝BEF〞,a3=〝BEFANG〞,a4=“BEI〞最小的是______。[]=“English”;a[7]中存放的是_字符串的结束符。,并具体体现数据元素间的逻辑结构称为__物理结构(存储结构)。=”ABADF”,P2=”ABAFD”,P3=”ABADFA”P4=”ABAF”,四个串中最大的是________。,要删除第8个元素需移动元素的个数为______。,若编号为i的结点存在右孩子,则右孩子的顺序编号为________。,若编号为i的结点存在左孩子,则左孩子的顺序编号为______。,要插入一个元素,并作为第8个元素,需移动元素的个数为________。,除叶结点外每个结点度数都为2,则该树共有______个结点。。(45,29,87,12,6,63,55,37,78)进行直接插入排序时,当把第8个记录37插入到有序表时,为寻找插入位置需比较_________次。(由小到大排序),第四层上有5个结点,该树共有_______个结点。(根所在结点为第1层),通常需要进行________趟冒泡。,每一个非叶结点的度数都为2,则该树共有_______个叶结点。,该树中有_____个叶结点。(55,39,97,22,16,73,65,47,88)进行直接插入排序时,当把第7个记录65插入到有序表时,为寻找插入位置需比较_________次。(。,第j趟冒泡要进行______次元素间的比较。(a,(a,b),d,e,((i,j),k))的长度是________。,则该树共有_______个结点。(a,(a,b),d,e,((i,j),k))深度是________。。,12,15,13,18,16,采用冒泡排序算法(升序),经一趟冒泡后,序列的结果是________。((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)求在等概率条件下,成功查找的平均比较次数?14:..)设有数据集合{40,29,7,73,101,4,55,2,81,92,39},依次取集合中各数据构造一棵二叉排序树。一组记录的关键字序列为(5,8,6,3,4,7),利用堆排序(堆顶元素是最小元素)的方法建立初始堆。(要求用完全二叉树表示)3.(1)一组记录的关键字序列为(47,80,57,39,41,46),给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述)。(2)对关键字序列(47,80,57,39,41,85)采用快速排序,给出以第一个关键字为分割元素,经过一次划分后的结果。(3)如图3所示的二叉树,给出其前序遍历序列。abcdgef图34.(1)以2,3,4,7,8,9作为叶结点的权,构造一棵哈夫曼树(2)给出上述哈夫曼树叶结点的哈夫曼编码。(3)一组记录的关键字序列为(37,70,47,29,31,85),利用快速排序,以第一个关键字为分割元素,给出经过一次划分后结果。(由小到大排序)15:..,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。voidInorder(structBTreeNode*BT)a{if(BT!=NULL){bcInorder(BT->left);}(1);(2);def}利用上述程序对右图进行中序遍历,结果是(3);图41.(1)printf(“%c”,BT->data)(2)Inorder(BT->right)(3)(6,10,16,4),以下程序用说明结构变量的方法建立单向链表,并输出链表中各结点中的数据。#defineNULL0voidmain(){NODEa,b,c,d,*head,*p;=6;=10;=16;=4;/*d是尾结点*/head=(1);=&b;=&c;=&d;(2);/*以上结束建表过程*/p=head;/*p为工作指针,准备输出链表*/don”,(3));(4);}while((5));}2.(1)&a(2)d->next=NULL(3)p->data(4)p=p->next(5)p!=[1],a[2],??,a[n]中的序列进行排序,完成程序中16:..是元素个数,要求按升序排列。voidbsort(NODEa[],intn){NODEtemp;inti,j,flag;for(j=1;(1);j++);{flag=0;for(i=1;(2);i++)if(a[i].key>a[i+1].key){flag=1;temp=a[i];(3);(4);}if(flag==0)break;}}程序中flag的功能是(5)(1)j<=n-1(2)i<=n-j(3)a[i]=a[i+1](4)a[i+1]=temp(5)当某趟冒泡中没有出现交换则已排好序,,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。voidInorder(structBTreeNode*BT)a{if(BT!=NULL){bc(1);(2);Inorder(BT->right);}ef}利用上述程序对右图进行遍历,结果是(3);d4.(1)Inorder(BT->left)图5(2)printf(“%c”,BT->data)(3)bedafc综合练****二答案一、单项选择题17:..、(存储结构)+--+--,14,13,15,16,:..(1)39171025811图6(2)4次(3)ASL=(1+2*2+3*4+4*4)/11=(1)73955101481292(2)3,4,6,8,5,7图7346857图83(1)39,41,46,80,47,57394**********图9:..4139,47,57,80,85(3)abdefcg.(1)33181599785423图10(2)2:000040001500**********(3)31,29,37,47,70,8520:..一、()。,指针p指向其尾结点,要删除第一个结点,则可利用下述语句head=head->next;和()。=head;=NULL;->next=head;=p;()的关系。()。,要插入一个元素,并使它成为新表的第6个元素,需移动元素的个数为()。,并具体体现()称为物理结构。,p所指向尾结点,要使该链表成为不带头结点的单向循环链表,可执行head=head->nex;和()。=head->->next=->next=p->->next=head;()。,113,115,117按顺序依次进栈,则该栈的不可能输出序列是()(进栈出栈可以交替进行)。,115,113,,113,115,,115,111,,111,117,()的关系。()。,14,16,18按顺序依次进栈,则该栈的不可能输出序列是()(进栈出栈可以交替进行)。,16,14,,14,16,1821:..18,16,20,,20,18,(第一个元素为a),采用压缩存储的方式,将其下三1,1角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵元素a6,2在一维数组B中的下标是()。(左上角第一个元素为a),采用压缩存储的方式,将其下三角部分以行序为1,1主序存储到一维数组B中(数组下标从1开始),则矩阵中元素a在一维数组B中的下标是()。5,=”