数据结构自测题 第10章排序自测卷空题

国开期末考试《数据结构与算法》机考试题及答案(第10套)一、选择题（每题2分，共20分）1. 数据的逻辑结构是指（）。

A. 数据元素之间的逻辑关系B. 数据元素本身的特点C. 数据的存储结构D. 数据的加工处理过程答案：A. 数据元素之间的逻辑关系二、填空题（每题2分，共20分）2. 在栈中，最后进入的数据元素总是首先被（）。

答案：弹出三、判断题（每题2分，共20分）3. 线性表是一种线性结构。

（）答案：正确四、简答题（每题10分，共30分）4. 简述顺序存储结构和链式存储结构的特点。

答案：顺序存储结构：数据元素在物理位置上连续存储，可以通过下标快速访问。

五、编程题（共50分）5. 编写一个函数，实现单链表的排序。

（20分）答案：class ListNode:def __init__(self, value):self.value = valueself.next = Nonedef sort_linked_list(head):if not head or not head.next:return headpivot = head.valueless = less_head = ListNode(None) equal = equal_head = ListNode(None) greater = greater_head = ListNode(None)current = headwhile current:if current.value < pivot:less.next = currentless = less.nextelif current.value == pivot:equal.next = currentequal = equal.nextelse:greater.next = currentgreater = greater.nextcurrent = current.nextless.next = less_head.nextequal.next = equal_head.next greater.next = greater_head.nextreturn merge_sorted_lists(sort_linked_list(less_head.next),sort_linked_list(equal_head.next), sort_linked_list(greater_head.next))def merge_sorted_lists(l1, l2, l3):dummy = ListNode(None)current = dummywhile l1 and l2 and l3:if l1.value < l2.value and l1.value < l3.value:current.next = l1l1 = l1.nextelif l2.value < l1.value and l2.value < l3.value:current.next = l2l2 = l2.nextelse:current.next = l3l3 = l3.nextcurrent = current.nextif l1:current.next = l1 elif l2:current.next = l2 else:current.next = l3 return dummy.next。

数据结构自测题及答案**数据结构自测题及答案**一、选择题（每题2分，共10分）1. 数据结构是一种用于组织和管理数据的方式，它主要关注的是：A. 数据的存储和表示方式B. 数据的输入和输出方式C. 算法和数据的交互方式D. 数据处理的速度和效率2. 在数据结构中，数组是一种：A. 线性结构B. 树形结构C. 图形结构D. 集合结构3. 下列哪种数据结构是先进先出（FIFO）的：A. 栈B. 队列C. 链表D. 哈希表4. 在二叉树中，每个节点最多有几个子节点：A. 0B. 1C. 2D. 35. 下列哪种数据结构适合用于实现图的存储：A. 数组B. 链表C. 堆D. 散列表二、填空题（每题2分，共10分）1. 在栈中，最后一个进入栈的元素最先出栈，这种特点叫做**后进先出**。

2. 哈希表一般是通过**散列函数**将键映射到存储位置上。

3. 图中节点之间的关系可以用**边**来表示。

4. 在二叉搜索树中，左子树的值都小于根节点的值，右子树的值都大于根节点的值，这种特点叫做**二叉搜索树的性质**。

5. 在链表中，每个节点都包含一个指向下一个节点的**指针**。

三、判断题（每题2分，共10分）1. 队列是一种先进先出（FIFO）的数据结构。

（正确）2. 图是一种非线性的数据结构。

（正确）3. 二叉树是一种树形数据结构，每个节点最多有两个子节点。

（正确）4. 栈可以用数组和链表两种方式实现。

（正确）5. 哈希表的插入和查询操作的时间复杂度都为O(1)。

（错误）四、程序设计题（总分20分）请编写一个程序，实现以下功能：1. 定义一个结构体，用于表示学生信息，包含姓名、年龄和成绩三个字段。

2. 动态创建一个长度为5的数组，用于存储学生信息。

3. 通过键盘输入，依次为每个学生的姓名、年龄和成绩赋值，并存储到数组中。

4. 分别计算学生的平均年龄和平均成绩，并输出结果。

代码示例（C语言）：```c#include<stdio.h>#include<stdlib.h>struct Student {char name[20];int age;float score;};int main() {struct Student* students = (struct Student*)malloc(5 * sizeof(struct Student));for (int i = 0; i < 5; i++) {printf("请输入第 %d 个学生的姓名：", i + 1);scanf("%s", students[i].name);printf("请输入第 %d 个学生的年龄：", i + 1);scanf("%d", &students[i].age);printf("请输入第 %d 个学生的成绩：", i + 1);scanf("%f", &students[i].score);printf("\n");}int totalAge = 0;float totalScore = 0.0;for (int i = 0; i < 5; i++) {totalAge += students[i].age;totalScore += students[i].score;}float avgAge = totalAge / 5.0;float avgScore = totalScore / 5.0;printf("平均年龄： %.2f\n", avgAge);printf("平均成绩： %.2f\n", avgScore);free(students);return 0;}```以上就是自测题及答案的全部内容。

一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行(A )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（D）。

A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D）参数。

A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A）。

A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（D）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

第十章内部排序10.23void Insert_Sortl(SqList &L)〃监视哨设在高下标端的插入排序算法{k=L」ength;for(i=k-l;i;-i)//从后向前逐个插入排序if(L.r[i].key>L.r[i+1] .key){L.r[k+l].key=L.r[i].key;// 监视哨for(j=i+l;L.rfj].key>L.r[i].key；4-+j)L.r [j-1 ] .key=L.r[j] .key; 〃前移L.r [j-1 ] .key=L.r[k+1 ] .key; 〃插入}}//Insert_Sortl10.24void BiInsert_Sort(SqList &L)〃二路插入排序的算法{int dlMAXSIZE];//辅助存储x=L.r .key;d =x;first= 1 ;final= 1;for(i=2;i<=L.length;i++){if(L.r[i].key>=x) //插入前部{for(j=final;d[j]>L.r[i].key;j—)dU+l]=dU];d[j+l]=L.r[i].key;final++;}else//插入后部{for(j=first;d[j]d[j-l]=d[j];dl(j-2)%MAXSIZE+ l]=L.r[iJ.key;first=(first-2)%MAXSIZE+1; //&种形式的表达式是为了兼顾first=l的情况}}//forfor(i=first j= 1 ;dLiJ ；i=i%MAXS!ZE+1 ,j++)//^l 各序列复制回去L.r[j].key=d[i];}//BiInsert_Sort10.25void SLInsert_Sort(SLList &L)〃静态链农的插入排序算法L.r[0].key=0;L.r[0].next=l;L.r[l].ncxt=O; 〃建初始循环链表for(i=2;i<=L.length;i++) // 逐个插入{p=O;x=L.r[i].key;while(L.rLL.r[p].next].keyp=L.r[p].next;q=L.r[p].next;L.r[p].ncxt=i;L.r[i].next=q;}//forp=L.r[OJ.next;for(i=l;i{whilc(pq=L.r[p].ncxt;if(p!二i){L.r[pJ<->L.r[iJ;L.r[i].next=p;}p=q；}//for}//SLInsert_Sort10.26void Bubble_Sortl(int a[ ],int n)〃对包含n个元素的数组a进彳亍改进的冒泡排序{change=n-l; //change指示上一趟冒泡中最后发生交换的元素while(change){for(c=0,i=0;iif(a[i]>a[i+1]){a[i]<->a[i+l];c=i+l;//c指示这一趟冒泡屮发生交换的元素}changc=c;}//while}//Bubble_Sortl10.27void Bubblc_Sort2(int a[ ],int n)〃相邻两趟是反方向起泡的冒泡排序算法{low=0;high=n-1; 〃冒泡的上F界change=l;while(low{change=():for(i=low;iif(a[i]>a[i+1])chanse=l:}high-;//修改上界for(i=high;i>low;i-) //从F 向上起泡a[i]<->a[i-l];changc=l;}low++;〃修改卜-界}//while}//Bubble_Sort210.28void Bubble_Sort3(int a[ ],int n)〃对上一题的算法进行化简，循环体中只包含一次冒泡{int b[ 3 ]; //b[0]为冒泡的下界,b[ 2 ]为上界,b[l]无用d=l;b[0]=0;b[2]=n-l;//d为冒泡方向的标识,1为向上,・1为向下changc=l;while(b[0]{change=0;for(i=b[l -dl ;i!=bfl +d] ;i+=d) // 统一的冒泡算法if((a[i]・a[i+d])*d>0)//注意这个交换条件{a[i]<->a[i+d];change=l;}b[l+d]-=d; //修改边界d*=-l；〃换个方向}//while}//Bubble_Sort310.29void OE_Sort(int a[ ],int n)〃奇偶交换排序的算法{change=l;while(cha nge){change=():for(i= 1 ;iif(a[i]>a[i+1]){a[i]<->a[i+l];change=l;}for(i=0;iif(a[i]>a[i+1])}}//while}//OE_Sort分析:木算法的结束条件是连续两趟比较无交换发生10.30typcdcf struct {int low;int high;} boundary; //了序列的上下界类型void QSort_NotRecurve(int SQList &L)〃快速排序的非递归算法{low= 1 ;high=L.length;InitStack(S); //S 的元素为boundary 类型while(low{if(high-Iow>2) //如果当前了序列氏度大于3 尚未排好序{pivot=Partition(L,low,high); 〃进行一趟划分if(high-pivot>pivot-low){Push(S,{pivot+1 ,high}); //把长的了序列边界入栈high=pivot-l; 〃短的子序列留待下次排序}else{Push(S,{ low,pivot-1});low=pivot+l;}}〃讦else if(low{Easy_Sort(L,low,high); //直接进行比较排序low=high; 〃当前子序列标,忐为已排好序}else//如果当前子序列己排好序但栈屮还有未排序的子序列{Pop(S,a); 〃从栈中取出一个了序列low=a.low;high=a.high;}}//while}//QSort_NotRecurveint Partition(SQList &L,int low,int high)//-•趟划分的算法，与书上相同L.r[0]=L.r[low];pivotkey=L.r[low] .key;while(low=pivotkey)high-;L.r[low]=L.r[high];while(lowlow++;L.r[high]=L.r[low];}//whileL.r[lowJ=L.r[OJ;return low;{//Partitionvoid Easy_Sort(SQList &L,int low,int high)//对长度小于3的子序列进行比较排序{if(high-low==l)//子序列只含两个元索if(L.r[low] .key>L.r[high] .key) L.r[low]<->L.r[high];C1SC//T序列含冇三个元素{if(L.r[low].key>L.r[low+ l].key) L.r[low]<->L.r[low+1 ];if(L.r[low+1 J.key>L.r[high].key) L.r[low+1 J<->L.r[high];if(L.r[low].key>L.r[low+ l].key) L.r[low]<->L.r[low+ 1J;}}//Easy_Sort10.31void Divide(int a[ l,int n)〃把数组a中所有值为负的记录调到非负的记录ZMj{low=();high=n-l;whilc(low{while(low=0) high-; 〃以0作为虚拟的枢轴记录a[lowJ<->aLhighJ;while(lowallow]<->a[high];}[//Divide10.32typedef enum {RED,WHITE,BLUE} color; //三种颜色void Flag_Arrange(color a[ ],int n)〃把由三种颜色组成的序列重排为按照红，白，蓝的顺序排列{i=0;j=0;k=n-1;while(j<=k)switch(a[jj){case RED:i++；j++；break;case WHITE:j++；break;case BLUE:a[j]<->a[k];k-; 〃这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况}}//Flag_Arrange分析:这个算法屮设立了三个指针.其屮,j表示当前元素;i以前的元素全部为红色;k以示的元索全部为蓝色.这样，就可以根据j的颜色，把其交换到序列的前部或者后部.10.33void LinkedList_Select_Sort(LinkedList &L)〃单链表上的简单选择排序算法{for(p=L;p->next->next;p=p->next){q=p->ncxt;x=q->data;for(r=q,s=q;r->next;r=r->next)//?l： q后面寻找元素值最小的结点if(「>n ext->data{x=r- >n ext->data;s=r;}if(s!=q) //找至【J了值比q->data更小的最小结点s->next{p->next=s->next;s->next=q;(二q・> next;q・>next二pp->ncxt->ncxt=t;} 〃交换q和s->next两个结点}//for}//LinkedList_Select_Sort10.34void Build_Heap(Heap &H,int n)〃从低下标到高下标逐个插入建堆的算法{for(i=2;i{ 〃此时从H.r[l]到H.r[i・l]己经是大顶堆• •J=l;while(j!=l)//把H.r[i]插入{k=j/2;if(H.r|j] .key>H.r[kJ .key)H.r[j]<->H.r[k];j=k;}}//for}//Build_Heap10.35void TriHeap_Sort(Heap &H)〃利用三叉树形式的堆进行排序的算法{for(i=H.length/3;i>0;i—)Heap_Adjust(H,i,H.length);for(i=H」ength;i>l;i—){H.r[l]<->H.r[i];Heap_Adjust(H, 1 ,i-l);}}//TriHeap_Sortvoid Heap_Adjust(Heap &H,int s,int m)//顺序表H 中,H.r[s+1]到H.r[m]已经是堆，把H.r[s]插入并调整成堆{rc=H.r[s];for(j=3 *s-1 ;j<=m;j=3 *j-1){s=j；}H.rfs]=rc;}//Heap_ Adjust分析:本算法与课本上的堆排序算法相比，只有两处改动:1.建初始堆时,i的上限从H.length/3 开始(为什么?)2.调整堆的时候，要从结点的三个孩子结点中选择最大的那一个，最左边的孩子的序号的计算公式为j=3*s・l(为什么?)10.36void Merge_Sort(int a[ ],int n)〃归并排序的非递归算法{for(l= 1 ;lfor(i=0;(2*i-l)*l{start 1 =2*1 *i; //求出待归并的两段的上下界end l=start 1+1-1;start2=cnd 1+1;end2=(start2+l-1 )>(n-1 )?(n-1 )start2+l-1);//注意end2 可能超出边界Merge(a,start 1 ,end 1 ,start2,end2); 〃归)[■}}//Merge_Sortvoid Merge(int a[ ],int sl,int el,int s2,int e2)〃将有序子序列a[sl]到a[el]和a[s2]到a[e2]归并为有序序列a[sl]到a[e2]{int bfMAXSIZE]; 〃设立辅助存储数组bfor(i=s 1 ,j=s2,k=s 1 ;i<=e 1 &&jv二e2;k++) if(a[i]else b[k]=a[j++]; while(i<=el) b[k++]=a[i++];while(j<=e2) b[k++]=a[j++]；〃归并到b 屮for(i=s 1 ;i<=e2;i++) // 复制回去a[iJ=bLiJ；}//Merge10.37void LinkedList_Merge_Sort 1 (LinkedList &L)〃链农结构上的归并排序非递归算法{for(l= 1 ;lfor(p=L->next,e2=p;p->next;p=e2){for(i= 1 ,q=p;i<=l&&q->next;i++,q=q->next);cl=q；for(i= l;i<=l&&q->next;i++,q=q->next);e2=q; 〃求出两个待归并子序列的尾指针if (el !=e2) LinkedList_Merge(L,p,el,e2); // 归并}}//LinkcdList_Mcrgc_Sort 1void LinkedList_Merge(LinkedList &L,LNode *p,LNode *el,LNode *e2)〃対链表上的子序列进行归并，第一个子序列是从p->next到el,第二个是从e 1 ->next到e2{q=p->ncxt;r=c 1 ->ncxt; //q和r为两个了序列的起始位置while(q!=el->next&&r!=e2->next){if(q->datadata) //^择关键字较小的那个结点接在p的后而{p->next=q;p=q;q=q->ncxt;}else{p->next=r;p=r;r=r->ncxt;}}//whilewhile(q!=el->next) //接上剩余部分{p->ncxt=q;p=q;q=q->next;}while(r!=e2->next){p->next=r;p=r;r=r->next;}//LinkedList_Merge10.38void LinkedList_Merge_Sort2(LinkedList &L)〃初始归并段为最大有序子序列的归并排序，采用链表存储结构{LNodc *cnd[MAXSIZE]; 〃设立一个数组来存储各冇序了序列的尾指针for(p=L->next->nextj=0;p;p=p->next) // 求各有序子序列的尾指针if(!p->nextllp->data>p->next->data) end[i++]=p;while(end[O]->next) //当不止一个子序列时进行两两归并{j=O；k=O；//j：当前子序列尾指针存储位B!；k：归并后的子序列尾指针存储位置for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列{el二end[j];e2=end[j+l]; //确定两个子序列if(e 1 ->next) LinkedList_Merge(L,p,e 1 ,e2); 〃归并cnd[k++]=c2; //用新序列的尾指针取代原来的尾指针j+=2;〃转到后面两个子序列}}//while}//LinkedList_Merge_Sort2void LinkcdList_Mcrgc(LinkcdList &L,LNodc *p,LNodc *cl,LNodc *c2)〃对链表上的了序列进行归并，第一个了序列是从p->next到el,第二个是从el->next到e2{q=p->next;r=e 1 ->next;while(q!=e 1 ->next&&r!=e2->next){if(q->datadata){p->next=q;p=q;q=q->next;}else{p->next=r;p=r;r=r->next;}}//whilewhile(q!=e 1 ->next){p->next=q;p=q;q=q->next;}while(r!=e2->next)p->next=r;p=r;}//LinkedList_Merge,与上一题完全相同10.39void SL_Mcrgc(int a[ ],int ll,int 12)//把长度分别为11,12且11A2<(11+12)的两个有序子序列归并为有序序列{startl=0;start2=ll;//分别表示序列1和序列2的剩余未归并部分的起始位直for(i=0;i{for(j=start2;jk=j-start2; //k为要向右循环移动的位数RSh(a,start 1 j-1 ,k);//W a[startl]到a[j・l]之间的子序列循环右移k位start l+=k+l;start2=j; 〃修改两序列尚未归并部分的起始位置}}//SL_Mergevoid RSh(int a[ ] jnt start,int end,int k)〃将a[start]到a[end]之间的子序列循环右移k 位,算法原理参见5.18{len=end-start+l;for(i=l;i<=k;i++)if(len%i==0&&k%i==0) p=i; 〃求len 和k 的最大公约数pfor(i=0;i{j=start+i;l=start+(i+k)%len;temp=a|jj;while(l!=start+i){a[j]=tcmp;temp=a[l];all]=a|j]；j=l；l=start+(j-start4-k)%len; // 依次|H J右移}a[start+i]=temp;}//for}//RSh10.40E后给出的解题思路在表述上存在问题，无法理解•比如说,“把第一个序列划分为两个子序列, 使其中的第一个子序列含有si个记录,0<=s 110.41void Hash_Sort(int a[ J)//X'j 1000个关键字为四位整数的记录进行排序{int b[ 10000];for(i=0;ivl000;i卄)〃直接按关键字散列{for(j=a[i] ;b[j] ;j=(j+1)% 10000);fo「(i=0,j=0;ivl000;j++)〃将散列收回a 中if(b[j]){for(x=b[j],k=j ;b[kj ;k=(k+1)%10000)if(b[k>=x){a[i++]=x;b[k]=0;}}//if}//Hash_Sort10.42typedef stmct {int gt; //大于该记录的个数int It; 〃小于该记录的个数} place; 〃整个序列中比某个关键字大或小的记录个数int Get_Mid(int a[ J,int n)〃求一个序列的中值记录的位置{place b[MAXSIZEJ;for(i=();ifor(j=0;j{if(a[j]>a[i])b[i].gt++;else if(a[j]}mid=0;min_dif=abs(b[0].gt-b[0].lt);for(i=0;iif(abs(b[i].gt-b[i].lt)return mid;}//Gct_Mid10.43void Count_Sort(int a[ ],int n)〃计数排序算法{int cfMAXSIZE];for(i=0;i{for(j=0,count=0;jif(a[j]c[i]=count;}for(i=0;i{min=();for(j=0;jif(c[j]a[i]<->a[min]; 〃与第i 个记录交换c[minJ=INFINITY; //修改该记录的c值为无穷大以便下一次选収}}//Count_Sort10.44void Enum_Sort(int a[ ],int n)〃对关键字只能取v到w Z间任意整数的序列进行排序int number[w+1 J,pos[w+1J; for(i=0;ifor(pos[0]=0,i=l；ipos[i]=pos[i-l]+num[i]; //pos 数组可以把关键字的值映射为元素在排好的序列中的位置for(i=0;ic[pos[a[i]]++]=a[i];for(i=0;ia[i]=c[i];}//Enum_Sort分析:木算法参考了第五章三元组稀疏矩阵转置的算法思想，其中的pos数组和那里的cpot数组起的是相类似的作用.10.45typedef enum {0,1,2,3,4,5,6,7,8,9} digit; //个位数类型typedef digit[3] num; //3位自然数类型，假设低位存储在低下标，高位存储在高卜•标void Enuni_Radix_Sort(num a[ ],int n)〃利用计数实现基数排序,其屮关键字为3位白然数，共有n个自然数{int number ,pos ;num c[MAXSIZEJ;for(j=0;j<3;j++) //依次对个位，十位和百位排序{for(i=0;ifor(pos[0]=0,i=l;ipos[iJ=pos[i-l]+numLi]; //把关键字的值映射为元素在排好的序列中的位置for(i=0;ic[pos[a[ij[j]]++]=a[i];for(i=0;ia[i]=c[i];}//for}//Enum_Radix_Sort分析:计数排序是一种稳定的排序方法.」E因为如此，它才能够被用来实现基数排序.10.46typedef struct {int key;int pos;} Shadow;//影子序列的记录类型void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)〃对元素很人的记录序列b进行排序,结果放入a中，不移动元素{Shadow d[MAXSIZE];for(i=0;i{d[i].key=b[i].key;dfi].pos=i;}for(i=n-l ,change= 1 ;i> 1 &&change;i・・)//对影子序列执行冒泡排序{change=0;for(j=O;jif(d[j].key>d[j+l].key){dU]<->dU+U；change=l;}//forfor(i=0;ia[i]=b[d[i].pos]; }//Shadow_Sort。

自测题（6-10章）一、填空题1、二叉树第i(i>=1)层上至多有______个结点，深度为k(k>=1)的二叉树至多有______个结点。

2、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

3、满二叉树上各层的节点数已达到了二叉树可以容纳的______，满二叉树也是______二叉树，但反之不然。

4、具有n个结点的完全二叉树的深度为______。

5、具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。

6、二叉树有不同的链式存储结构，其中最常用的是________与________。

7、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。

8、由________转换成二叉树时，其根结点的右子树总是空的。

9、哈夫曼树是带权路径长度________的树，通常权值较大的结点离根________。

10、有m个叶子结点的哈夫曼树，其结点总数为________。

11、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有________个叶子结点。

12、具有10个顶点的无向图，边的总数最多为________。

13、N个顶点的连通图的生成树含有________条边。

14、无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。

15、一个具有n个顶点的完全无向图的边数为________，一个具有n个顶点的完全有向图的弧数为________。

16、遍历图的基本方法有________优先搜索和________优先搜索两种。

17、在有向图的邻接矩阵上，由第i行可得到第________个结点的________，而由第j列可得到第________个结点的________。

18、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素________比较大小。

1．下列排序算法中，其中（ D ）是稳定的。

A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。

A．下面的B，C，D都不对。

B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，203.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。

A. 直接插入排序B. 快速排序C. 直接选择排序D. 堆排序4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。

A. 插入B. 选择C. 希尔D. 二路归并6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。

A. 选择B. 冒泡C. 插入D. 堆7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。

A. 3B. 10C. 15D. 258. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B )A. lB. 4C. 3D. 29. 堆排序是（ E ）类排序A. 插入B. 交换C. 归并D. 基数E. 选择10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。

9.1选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。

A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序方法是（）Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（）排序是不稳定排序法。

A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（）情况下最不利于发挥其长处。

Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

第10章排序一、选择题1．某内排序方法的稳定性是指( )。

【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( )排序法是不稳定性排序法。

【北京航空航天大学 1999 一、10 （2分）】A. 插入B. 冒泡C. 二路归并D. 堆积3．下列排序算法中，其中（）是稳定的。

【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。

【北京邮电大学 2001 一、5（2分）】7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

（）就是不稳定的排序方法。

【清华大学 1998 一、3 (2分）】A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。

A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。