数据结构第三次作业题及答案.doc

一、单项选择题1.一个栈的入栈序列是a，b，c，d，e，则栈不可能输出的序列是（ C ）。

A．edcba B．decba C．dceab D．abcde2.一个队列的入队序列是1，2，3，4，则队列的输出序列是（ B ）。

A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 3.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为P1，P2，P3…，Pn，若P1=n，则Pi为（ C ）。

A．i B．n-i C．n-i+1 D．不确定4.判定一个栈S（最多元素为m0）为空的条件是（ B ）A．S.top!=0 B．S.top = =0 C．S.top!= m0 -1 D．S.top = = m0 -15.判定一个队列Q（最多元素为m0）为空的条件是（ C ）。

A．Q.rear－Q.front= = m0B．Q.rear－Q.front－1= = m0C．Q.front = =Q.rear D．Q.front=Q.rear+16.判定一个循环队列Q（最多元素为m0）为满的条件是（ C ）。

A．Q.front = =Q.rear B．Q.front !=Q.rearC．Q.front = =(Q.rear+1)% m0D．Q.front ! =(Q.rear+1)% m07.栈和队列的共同点是（ C ）。

A．都是后进先出B．都是先进先出C．只允许在端点处插入和删除元素D．没有共同点二、写出下列程序段的输出结果。

①void main( ) {stack S;char x,y;InitStack(S);x=‟c‟ ; y=‟k‟ ;Push(S,x); Push(S,‟a‟); Push(S,y);Pop(S,x); Push(S,‟t‟); Push(S,x);Pop(S,x); Push(S,‟s‟);while(!StackEmpty(S)) {Pop(S,y); printf(y);}printf(x);}输出结果：stack② void main( ) {Queue Q; InitQueue(Q); char x=…e‟, y=…c‟;EnQueue(Q,‟h‟); EnQueue(Q,‟r‟); EnQueue(Q,y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q,‟a‟); while(!QueueEmpty(S)) {DeQueue(Q, y); printf(y); }printf(x); }输出结果：char栈S栈Sk 出栈，x=‟k ‟栈S栈S栈S栈St 出栈，y=‟t ‟ 输出y 的值t同理，接着a 出栈，y=‟a ‟，输出y 的值a 。

第三次作业第三章栈和队列一、选择题1. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。

A. i-j-1B. i-jC. j-i+1D. 不确定的2. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ AD ）。

A. |top[2]-top[1]|=0B. top[1]+1=top[2]C. top[1]+top[2]=mD.top[1]=top[2]3. 栈在（ D ）中应用。

A. 递归调用B. 子程序调用C. 表达式求值D. A，Ｂ，Ｃ4. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ D ），其中^为乘幂。

A. 3,2,4,1,1；(*^(+*-B. 3,2,8；(*^-C. 3,2,4,2,2；(*^(-D. 3,2,8；(*^(-5. 用链接方式存储的队列，在进行删除运算时（ D ）。

A. 仅修改头指针B. 仅修改尾指针C. 头、尾指针都要修改D. 头、尾指针可能都要修改6. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m7. 栈和队列的共同点是（ C ）。

A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点8. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。

A． 6 B. 4 C. 3 D. 2二、判断题1.消除递归不一定需要使用栈，此说法（√）2. 栈是实现过程和函数等子程序所必需的结构。

国家开放大学电大《数据结构》网络课形考任务3作业及答案档任务3一、单项选择题（每小题2分，共38分）题目1 假定一棵二叉树中，双分支结点数为15,单分支结点数为30,则叶子结点数为（）。

选择一项： A、47 B、16 C、17 D、15 题目2 二叉树第k层上最多有（）个结点。

选择一项： A、2k-l B、2k-l C、2k-l D、2k 题目3 将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1,则编号为69的结点的双亲结点的编号为（）。

选择一项： A、36 B、35 C、34 D、33 题目4 如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。

选择一项： A、二叉树 B、哈夫曼树 C、完全二叉树 D、平衡二叉树在一棵度具有5层的满二又树中结点总数为（ )o 选择一项: A、16 B、3231 D、33 题目6 一棵完全二叉树共有6层，且第6层上有6个结点，该树共有（）个结点。

选择一项: A、31 B、37 C、38 D、72 题目7 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（在一棵树中，（）没有前驱结点。

)、选择一项: A、18 B、16 C、30 D、12 题目8 选择一项: A、树根结点 B、叶结点 C、空结点 D、分支结点题目9 设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2,该树结点中共有20个指针域为空，则该树有（）个叶结点。

选择一项: B、10 C、21 D、22 题目10 在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。

选择一项： A、2 B、1 C、4 D、1/2 题目11 邻接表是图的一种（）＜、选择一项： A、链式存储结构 B、顺序存储结构C、散列存储结构 D、索引存储结构题目12 图的深度优先遍历算法类似于二叉树的（）遍历。

一、单选题：C D B A A A C B C C二、填空题：n n/2 7 n2+2n3+…..+(m-1)n m+1 只有根节点的二叉树逆序1000000 2000 最大24三、应用题1、参考答案A B C D E F G H10 001 11 0001 0110 0111 010 00002、0 1 2 3 4 5 6 7 8 9 1012 100 25 16 17 18 8 40 7(1) (2) (1) (1) (1) (1) (1) （3）(4)搜索成功的平均搜索长度为ASL succ = 19(1 + 2+ 1 + 1 + 1 + 1 +1+ 3+ 4) = 533、4、最小生成树或最小生成树不唯一，有两棵，如上所示。

5、四、算法设计题1、void Bucketsort ( ElementType A[ ], int N )12 45635 6 11 1618 1 24563{int Counter[ 3 ];int i, j, k;for ( i = 0; i < 3; i++ )Counter[ i ] = 0;for ( i = 0, i < N; i++ ) {if ( A[ i ] == false )Counter[ 0 ] ++;elseif ( A[ i ] == maybe )Counter[ 1 ] ++;elseCounter[ 2 ] ++;}k = 0;for ( i = 0; i < Counter[ 0 ]; i++ )A[ i ] = false;k += Counter[ 0 ];for ( i = 0; i < Counter[ 1 ]; i++ )A[ k+i ] = maybe;k += Counter[ 1 ];for ( i = 0; i < Counter[ 2 ]; i++ )A[ k+i ] = true;}2、int BinaryTree<Type> :: leaf ( BinTreeNode<Type> * ptr ) {if ( ptr == NULL ) return 0;else if ( ptr->leftChild == NULL && ptr->rightChild == NULL ) return 1;else return leaf ( ptr->leftChild ) + leaf ( ptr->rightChild );}3、int max=0;int Find_All_Path(Graph *G,int S,int T, int K)/{G->setMark(S,VIEITED);if(S==T) //找到了一条简单路径{ if (max<K) max=K; return(max); }elsefor(int p=G->first(S);p<G->n();p=G->next(S,p){if(G->getMark(p)==UNVISITED) Find_All_Path(G,p,T,k+1); //继续寻找}G->setMark(S,UNVIEITED); }。

2015秋西南大学《数据结构》第三次作业及答案一、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。

试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度算法如下:LinkList Link( LinkList L1 , LinkList L2 ) {//将两个单链表连接在一起 ListNode *p , *q p=L1; q=L2;while ( p->next ) p=p->next; //查找终端结点p->next = q->next //将L2的开始结点链接在L1之后 return L1 } 本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为： m+1=O(m)二、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。

已知s为指向链表中某个结点指针，试编写算法在链表中删除指针s所指结点的前驱结点。

void Delprior ( Link s){ p = q = s;while (p->next!=s){ q = p;p = p->next; }q->next = s; delete ( p); }三、指出以下算法中的错误和低效之处，并把它改写为一个既正确又高效的算法。

Status DeleteK( SqList &a,int I, int k){ //本过程从顺序存储结构的线性表a中删除第I个元素起的k个元素。

if (I<1|| k<0|| I+k > a.length) return ERROR; else {for (count=1;count<k;count++){ //删除一个元素for (j=a.Length; j >=I+1;j--) a.elem[j-1] = a.elem[j]; a.length--; } rreturn OK; }//DeleteK更正：for (j = I+k; j <=a.Length; j++) a.elem[j-k] =a.elem[j]; a.Length = a.Length – k;四、假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也用三元组表示。

数据结构第三次单元测验答案一、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/22.适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。

A．35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlogn）D. O（logn）6.对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为（）A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，37.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。

A.2B. 3C. 4D.128.用n个键值构造一棵二叉排序树，最低高度为（）A.n/2B.、nC.lognD.logn+19．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130）B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D.(100，80， 60， 90， 120，130，110)10.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key% 13,散列地址为1的链中有（）个记录。

第3次作业一、填空题（本大题共30分，共 10 小题，每小题 3 分）1.栈是一种特殊的线性表，允许插入和删除运算的一端称为 ______ 。

不允许插入和删除运算的一端称为 ______ 。

2.二叉树由，，三个基本单元组成。

3.构造连通网最小生成树的两个典型算法是______。

4.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________、________和________三项。

5.直接插入排序用监视哨的作用是_______。

6.AOV网中,结点表示______,边表示______。

AOE网中,结点表示______,边表示______。

7.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是________。

8.一棵深度为6的满二叉树有______个分支结点和______个叶子。

9.已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是。

10.在哈希文件中，处理冲突的方法通常有______、______ 、______和______四种。

二、算法设计题（本大题共20分，共 2 小题，每小题 10 分）1.编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。

2.设稀疏矩阵Mmxn中有t个非零元素，用三元组顺序表的方式存储。

请设计一个算法，计算矩阵M的转置矩阵N，要求转置算法的时间复杂度为O(n+t)。

三、简答题（本大题共20分，共 4 小题，每小题 5 分）1.假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.(1)为这8个字母设计哈夫曼编码。

(2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?2.若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。

数据结构第三次作业补充题环形链表队列的插入和删除函数void en_queue(ptail, x)NODE **ptail;int x;{NODE *p;p=(NODE *)malloc(sizeof(NODE)); p->data=x;if(*ptail==NULL)p->link=p;else{p->link=(*ptail)->link;(*ptail)->link=p;}*ptail=p;}int delete(ptail, px)NODE **ptail;int *px;{NODE *p;if(*ptail==NULL) return(1);p=(*ptail)->link;*px=p->data;if(p==(*ptail))*ptail=NULL;else(*ptail)->link=p->link;free(p);return(0);}1.19void rebuild(phead)NODE **phead;{NODE *p, *q;int s;p=*phead;if(p==NULL)s=0;elses=1;while(p->link!=NULL){p=p->link;s++;}q=(NODE *)malloc(sizeof(NODE));q->data=s;q->link=*phead;p->link=q;*phead=q;}1.20 (1)#define M 1000int t[m];void makenull(t)int t[];{int i;for(i=0;i<M;i++)t[i]=-1;}void storage(t)int t[];{int x,y,i,j,k,m;m=power(2,31);y=568731;for(i=1;i<=800;i++){y=(15625*y+22221)%m;x=1000*y/m;for(j=0;t[(x+j)%M]!=x&&t[{x+j}%M]>=0;j++);k=(x+j)%M;if(t[k]<0)t[k]=x;}}1.21int depth(p)NODE *p;{int dep, max;if(p==NULL)return 0;max=0;while(p!=NULL){if(p->tag){dep=depth(p->dd.dlink);if(dep>max)max=dep;}p=p->link;}return max+1;}2.1#define MAXL 100#include “stdio.h”char s[MAXL], t[MAXL];void costring(s,t,n,m) char s[], t[];int n, m;{int i,j,k,length1;int index, length;index=0;length=0;i=0;while(i<n){j=0;while(j<m){if(s[i]==t[j]){length1=1;for(k=1;s[i+k]==t[j+k];k++)length1++;if(length1>length){index=i;length=length1;}}j++;}i++;}printf(“longest substring is:”); for(i=0;i<length;i++)printf(“%c”,s[index+i]);}2．2#define M 100typedef struct node{char c[4];struct node *link;} NODE;NODE *s1;char s2[M];NODE *search(s, i, pj)NODE *s;int i, *pj;{int k, l;NODE *p;k=0;p=s;while(k<i){if(p==NULL) return (NULL);for(l=0; l<4&&k<i; l++)if(p->c[l]!=’#’)k++;if(k<i)p=p->link;}*pj=l;return p;}int strins(s1, i , s2)NODE *s1;char s2[];int i;{NODE *p, *q, *r, 8h;int j, k;j=0;if(s2[j]==’\0’) return (0);r=NULL;while(s2[j]!=’\0’){q=(NODE *)malloc(sizeof(NODE));for(k=0;k<4&&s2[j]!=’\0’;k++)q->c[k]=s2[j++];while(k<4)q->c[k++]=’#’;if(r==NULL)r=p=q;else{p->link=q;p=q;}}q->link=NULL;//if(!(p=search(s1, i, &j))) return(1);//if(j!=0){h=(NODE *)malloc(sizeof(NODE));for(k=0; k<j; k++)h->c[k]=’#’;for(k=j; k<4; k++){h->c[k]=p->c[k];p->c[k]=’#’;}h->link=p->link;}q->link=h;p->link=r;return(0);}2. 3int strdel(s, i, j)NODE *s;int i, j;{NODE *p, *q;int k, l;if(!(p=search(s, i, &k))) return(1);if(k!=0){for(l=k; l<4&&j>0; l++)if(p->c[l]!=’\0’&&p->c[l]!=’#’){p->c[l]=’#’;j--;}else if(p->c[k]==’\0’)return (1);}//if(!(q=search(p->link, j, &k))) return(1);//p->link=q;if(k!=0)for(l=0; l<k; l++)q->c[l]=’#’;return (0);}2.42.5一开始，两个语句，O（1）；while外循环，执行n次，O（n）；while内循环，取决于j。

2021数据结构作业3 树与二叉树参考答案2021数据结构作业3-树与二叉树-参考答案作业3.树非编程作业：1．请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

参考答案：具备3个结点的树：具有3个结点的二叉树：2．未知二叉树的先序结点序列就是eabdcfhgikj，中序结点序列就是abcdefghijk，请构造二叉树，并写出其层次遍历序列和后序遍历序列。

参考答案：eaf层次：eafbhdgickjbh后序---cdbagjkihfedcgikj3．将下图所示的森林转换成一棵二叉树。

agkbcdhijlef参考答案：转换成的二叉树为：abcdghikljef4．将下图所示的二叉树还原成树或森林。

abcdlfeghmknji参考答案：切换为森林：aegbcdfhijlmnk5．假设用于通信的电文由7个字母组成{a,b,c,d,e,f,g}，字母在电文中出现的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。

精义这7个字母设计哈夫曼编码，并排序其有向路径长度wpl。

参考答案：哈夫曼树为：0.1810.39g0.610.210.290.32e0.17a0.090.09b0.12wpl=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56a:101b:001c:100d:0001e: 11f:0000g:01编程作业：二叉树采用二叉链表存储，试设计算法实现：1．createbt(bitree&t)：从键盘输入二叉树的先序结点序列字符串（以”#”代表空结点），创建其二叉链表；如输入：ab#d##ce#f###则建立如下图所示二叉树的二叉链表2．exchangebt(bitreet):设计递归算法实现二叉树中所有结点的左右孩子交换；3．countleaf(bitreet,telemtypex,int&count):统计数据以值x的结点为根的子树中叶子结点的数目；4．dispbitree(bitreet,intlevel):按树状打印二叉树。

第3章作业参考答案1.1,4,3,5,2)能,1011100100：(1,4,2,3,5)不能，因为4先于3和2出栈，4出栈时，2和3都在栈中，且2压在3之下，故只能3 先出栈才能2出栈。

*若借助栈由输入序列1,2，…，n得到输出序列为P1/p2，…,p n,则在输出序列中不可能出现这样的情形：存在着ivjvk使PjVpkVpi。

2.借助栈T,删除栈S中元素值为k的元素。

4.〃定义双向栈类template <class ElemType>〃声明一个类模板class DSqStack{public: 〃双向栈类的各成员函数DSqStack(int m = 100);~DSqStack();bool Empty(int i) const;ElemType & Top(int i) const;void Push(const ElemType &e」nt i);void Pop(int i);private: 〃双向栈类的数据成员ElemType *base; 〃基地址指针int top[2]; 〃栈顶指针int size; 〃向量空间大小}；〃构造函数，分配m个结点的顺序空间，构造一个空的双向栈。

template <class ElemType>DSqStack <ElemType>::DSqStack(int m){top[0] =-l;top[l] = m;base = new ElemType[m];size = m;}//DSqStack〃析构函数，将栈结构销毀。

template <class ElemType>DSqStack <ElemType>::~DSqStack()讦(base != NULL) deleted base;}//~SqStack〃判栈是否为空,若为空，则返回true,否则返回false。

template <class ElemType> bool DSqStack <ElemType>::Empty(int i) const{//i的取值为0或1if (i==0)return top[0] == -1;elsereturn top[l] == size;}//Empty〃取栈顶元素的值。

head 11级计本、信本第3章 栈和队列 自测卷答案一、填空题（每空1分，共15分）1.向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。

不允许插入和删除运算的一端称为 栈底 。

3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。

5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。

6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。

7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。

8.带表头结点的空循环双向链表的长度等于 0 。

解：二、判断正误（判断下列概念的正确性，并作出简要的说明。

）（每小题1分，共10分）（ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU 中也用队列。

（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ × ）5. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

（ × ）6. 栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

第十章内部排序一、基本知识题答案1. 排序：将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。

内部排序：数据存储在内存中，并在内存中加以处理的排序方法叫内部排序。

堆：堆是一个完全二叉树，它的每个结点对应于原始数据的一个元素，且规定如果一个结点有儿子结点，此结点数据必须大于或等于其儿子结点数据。

稳定排序：一种排序方法，若排序后具有相同关键字的记录仍维持原来的相对次序，则称之为稳定的，否则称为不稳定的。

2. 回答下面问题(1) 5000个无序的数据，希望用最快速度挑选出其中前10个最大的元素，在快速排序、堆排序、归并排序和基数排序中采用哪种方法最好？为什么？(2) 大多数排序算法都有哪两个基本操作？答：(1)采用堆排序最好。

因为以上几种算法中，快速排序、归并排序和基数排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。

堆排序则每次输出一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。

根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。

(2)两个基本操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身。

3. 3. 已知序列{17，25，55，43，3，32，78，67，91}，请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。

答：采用冒泡排序法排序时的各趟结果如下：初始：17，25，55，43，3，32，78，67，91第1趟：17，25，43，3，32，55，67，78，91第2趟：17，25，3，32，43，55，67，78，91第3趟：17，3，25，32，43，55，67，78，91第4趟：3，17，25，32，43，55，67，78，91第5趟：3，17，25，32，43，55，67，78，91第5趟无元素交换，排序结束。

4. 已知序列{491，77，572，16，996，101，863，258，689，325}，请分别给出采用快速排序、堆排序和基数排序法对该序列作递增排序时每一趟的结果。

难度系数及复杂系数说明：难度系数从易到难分别为：N1、N2、N3、N4、N5复杂系数从简到繁分别为：F1、F2、F3、F4、F5数据结构第三阶段作业第6章树和二叉树6.1 单项选择题1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B___。

（N2F1）A. 正确B. 错误2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 B 个。

（N2F1）A．15 B．16 C．17 D．473. 按照二叉树的定义，具有3个结点的不同形状的二叉树有__C__种。

（N2F1）A. 3B. 4C. 5D. 64. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有__C__种。

（N3F1）A. 5B. 6C. 30D. 325. 深度为5的二叉树至多有__C__个结点。

（N2F1）A. 16B. 32C. 31D. 106. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ _A__。

（N3F1）A. 2hB. 2h-1C. 2h+1D. h+17. 对一个满二叉树，m个树叶，n个结点，深度为h，则_D___ 。

（N3F1）A. n=h+mB. h+m=2nC. m=h-1D. n=2 h-18. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__A__。

（N3F1）A.不发生改变B.发生改变C.不能确定D.以上都不对9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_C___。

（N3F1）A. uwvtsB. vwutsC. wuvtsD. wutsv6.2 简答题1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。

（N2F3）2. 假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。

（N3F2）请画出该树。

第三阶段离线作业第七章 图7.1 已知图7.1所示的有向图，请给出该图的⑴ 每个顶点的入/出度；⑵ 邻接矩阵； ⑶ 邻接表；⑷ 逆邻接表；图7.1 （1）（2）A= 0 1 0 0 0 10 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0（3）→ →→ → → → → → → → （4）→ → → → →→ → → →7.2 用深度优先搜索和广度优先搜索对图7.2进行遍历（从顶点1出发），给出遍历序列。

图7.2深度优先1→2→4→8→5→3→6→7广度优先1→2→3→4→5→6→7→8第九章查找9.1 画出长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

等概率时查找成功的平均查找长度：ASL succ=(1*1+2*2+3*4+4*3)/10=2.99.2 假设按下述递归方法进行顺序表的查找：若表长≤10，则进行顺序查找，否则进行折半查找。

试画出对表长n=50的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。

ASL succ=(1*1+2*2+3*4+(4+5+6+7+8)*8+9*3)/50=5.689.3 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key%13构造哈希表。

⑴采用开放地址法的线性探测再散列方法解决冲突。

⑵采用开放地址法的二次探测再散列方法解决冲突。

⑶采用开放地址法的随机探测再散列方法解决冲突。

⑷采用链地址法解决冲突。

哈希列表012345678910111213关键字011455276819208423111077(2)哈希列表0123456789101112关键字270114556884192010231177(3)哈希列表0123456789101112关键字840155142768192010231177(4)哈希列表0123456789101112指针015519202311771468841027第十章内部排序10.1 已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采用快速排序法对该序列作升序排序时的每一趟结果。

第三次作业一、选择题1、在按行优先顺序存储的三元组表中，下述陈述错误的是 D 。

A. 同一行的非零元素，是按列号递增次序存储的B. 同一列的非零元素，是按行号递增次序存储的C. 三元组表中三元组行号是非递减的D. 三元组表中三元组列号是非递减的2、在稀疏矩阵的三元组表示法中，每个三元组表示 D 。

A. 矩阵中非零元素的值B. 矩阵中数据元素的行号和列号C. 矩阵中数据元素的行号、列号和值D. 矩阵中非零数据元素的行号、列号和值3、对特殊矩阵采用压缩存储的目的主要是为了 D 。

A. 表达变得简单B. 对矩阵元素的存取变得简单C. 去掉矩阵中的多余元素D. 减少不必要的存储空间4、广义表是线性表的推广，它们之间的区别在于 A 。

A. 能否使用子表B. 能否使用原子项C. 表的长度D. 是否能为空5、已知广义表(a, b, c, d)的表头是 A，则表尾是 D ；A. aB. ()C. (a, b, c, d)D. (b, c, d)//第一个元素为表头，其余元素组成的表为表尾6、下面说法不正确的是 A 。

A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构表示D. 广义表可以是一个多层次的结构7、若广义表A满足Head(A)=Tail(A)，则A为 B 。

A. ( )B. (())C. (( ),( ))D. (( ), ( ), ( ))8、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为 DA. 1B. 2C. 3D. 4//双亲即父节点9、深度为h的完全二叉树至少有 D 个结点，至多有 B 个结点A. 2hB. 2h-1C. 2h+1D. 2h-1//满二叉树是完全二叉树结点最多的情况10、具有n个结点的满二叉树有个叶结点。

A. n/2B. (n-1)/2C. (n+1)/2D. n/2+1//n个结点的满二叉树深度：（2^h）-1=n, 叶结点的个数：x=2^(h-1)=(2^h)/2//所以，x=(n+1)/211、一棵具有25个叶结点的完全二叉树最多有个结点。