2014-2015学年一学期数据结构期末考试试卷(A卷)
班级:___________学号:___________姓名:___________得分:___________
题目部分，(卷面共有32题,100分,各大题标有题量和总分)一、应用题(2小题,共16分) 1．一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。
2．分析下面各程序段的时间复杂度 （1） s1(int n) { int p=1,s=0; for (i=1;i<=n;i++) { p*=i;s+=p; } return(s); }
（2） s2(int n) x=0;
y=0; For (k=1;k<=n;k++)
x++; For (i=1;i<=n;i++) For (j=1;j<=n;j++) y++;
二、判断正误(7小题,共14分)
1．线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）
2．顺序队和循环队关于队满和队空的判断条件是一样的。（） 3．在线索二叉树中，任一结点均有指向其前趋和后继的线索。（）
4．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（） 5．散列技术的查找效率主要取决于散列函数和处理冲突的方法。（） 6．数据的逻辑结构和数据的存储结构是相同的。（） 7．逻辑结构与数据元素本身的内容和形式无关。（） 三、单项选择题(10小题,共20分) 1．单链表的存储密度（）。
A．大于1 B．等于1 C．小于1 D．不能确定
2．两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（）。
A．P->next==Q->next B．P->next== Q C．Q->next== P D．P== Q 3．字符串的长度是指（）。
A 串中不同字符的个数 B 串中不同字母的个数 C 串中所含字符的个数 D 串中不同数字的个数
4．线索二叉树中某结点R没有左孩子的充要条件是（）。
A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL
5．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A 20 B 256 C 512 D 1024
6．下面关于工程计划的AOE网的叙述中，不正确的是（） A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完
7．设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。
A 1，2，3，4 B 2，3，4，1 C 1，4，2，3 D 1，2，4，3 8．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生
成的二叉排序树的深度为（）。 A 4 B 5 C 6 D 7
9．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。 A 堆排序 B 冒泡排序 C 快速排序 D 希尔排序 10．算法分析的两个主要方面是（）。
A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 四、算法设计题(3小题,共24分)
1．设计判断单链表中元素是否是递增的算法。 2．设计两个有序单链表的合并排序算法。
3．设计一个求结点x在二叉树中的双亲结点算法。 五、填空题(8小题,共16分)
1．可由一个尾指针唯一确定的链表有（）、（）。
2．栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为（）表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为（）表。
3．在串 S=\"structure\" 中，以 t 为首字符的子串有（）个。
4．二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是____________。
5．一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。
6．对n个元素进行冒泡排序，在（）情况下比较次数最多，其比较次数为（）。 7．图形结构的元素之间存在（）的关系。
8．算法分析的目的是（） 六、简答题(2小题,共10分)
1．设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列，能否得到输出顺序为154623的序列。
2．下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。int index(char s[ ], char t[ ])
{ i=j=0;
while(i 长沙理工大学计算机与通信工程学院 2014-2015学年一学期数据结构期末考试试卷(A卷) 答案部分，(卷面共有32题,100.0分,各大题标有题量和总分) 一、应用题(2小题,共10分) 1． 0 1 2 3 4 5 6 7 8 9 10 11 12 查找成功的平均查找长度： SUCC2．O(n) O(n2) 二、判断正误(7小题,共14分) 1．错 2．错 3．错 4．对 5．错 6．错 7．对。因此逻辑结构是数据组织的主要方面。 三、单项选择题(10小题,共20分) 1．C 2．B 3．C 4．C 5．C 6．B 7．A 8．A 9．D 10．A 四、算法设计题(3小题,共24分) 1．int isriselk(lklist *head) { if(head==0||head->next==0) return(1);else q=p,p=p->next)if(q->data>p->data) return(0); return(1); } 2．void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) For(q=head,p=head->next; p!=0; if(ha->data } 3．typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; Bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) { if (bt!=0 && flag==0) if (bt->data==x) { flag=1; return;} Else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } } void parent(bitree *bt,char x) { int i; preorder(bt,x); for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf(\"not found x\\n\"); else if (i<=r) printf(\"%c\} 五、填空题(8小题,共16分) 1．循环链表，双链表 2．后进先出先进先出 3．12 4． 326 5．2i-1，(n+1)/2，(n-1)/2 6．反序，n(n-1)/2 7．多对多 8．分析算法的效率以求改进 六、简答题(2小题,共10分) 1．不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到部分 输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。 2．i-j+1，0 预览：长沙理工大学计算机与通信工程学院 2013-2014学年二学期数据结构期末考试试卷(A卷) 班级:___________学号:___________姓名:___________得分:___________ 题目部分，(卷面共有32题,100分,各大题标有题量和总分)一、应用题(2小题,共16分) 1．已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)=，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 2．分析下面各程序段的时间复杂度 （1） for (i=0;i 1．在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 2．线性表中的所有元素都有一个前驱元素和后继元素。（） 3．线性表的顺序存储结构比链式存储结构更好。（） 4．线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 5．在循环队列中无溢出现象。 6．一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。 7．串的堆分配存储是一种动态存储结构。 8．稀疏矩阵压缩存储后，必会失去随机存取功能。 9．一个有向图的邻接表和逆邻接表中的结点个数一定相等。 10．调用一次深度优先遍历可以访问到图中的所有顶点。（） 三、单项选择题(10小题,共20分) 1．在下列链表中不能从当前结点出发访问到其余各结点的是（）。 A．双向链表 B．单循环链表 C．单链表 D．双向循环链表 2．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。 A．5和1 B．4和2 C．2和4 D．1和5 3．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。 A 6 B 4 C 3 D 2 4．数组的逻辑结构不同于下列（）的逻辑结构。 A 线性表 B 栈 C 队列 D 树 5．线索二叉树中某结点R没有左孩子的充要条件是（）。 A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL 6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子 。孙的最大层次为（） A h B h+1 C h或h+1 D 任意 7．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。 A abedfc B acfebd C aebdfc D aedfcb 8．已知数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（）。 A 4 B 5 C 6 D 7 9．堆的形状是一棵（）。 A二叉排序树 B满二叉树 C完全二叉树 D 判定树 10．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。 A 堆排序 B 冒泡排序 C 快速排序 D 希尔排序 四、算法设计题(4小题,共32分) 1．设计两个有序单链表的合并排序算法。 2．已知一个单链表，编写一个函数从单链表中删除自第i个结点起的k个结点。 3．已知一个有向图的邻接表，编写算法建立其逆邻接表。 4．设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 五、填空题(6小题,共12分) 1．对一个需要经常进行插入和删除操作的线性表，采用（）存储结构为宜。 2．设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=（）和head=（）（设结点中的两个指针域分别为llink和rlink）。 3．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是（）。 4．若G为有向图，则至少有（）条边，至多有（）条边 5．对n个元素进行起泡排序，在（）情况下比较的次数最少，其比较次数为（）。 6．评价基于比较的排序算法的时间性能，主要标准是（）和（）。 长沙理工大学计算机与通信工程学院 2013-2014学年二学期数据结构期末考试试卷(A卷) 答案部分，(卷面共有32题,100.0分,各大题标有题量和总分) 一、应用题(2小题,共12分) 1．【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用线性探测法处理冲突，得到的散列表如下： 平均查找长度=(1+1+1+1+2+4+5+2+3+5+6+1)/12=32/12 2．O(n*m) O(n2) O(1) 二、判断正误(10小题,共20分) 1．（√） 2．（×） 3．（×） 4．（√） 5．（×） 6．（×） 7．（√） 8．（√） 9．（√） 10．（×） 三、单项选择题(10小题,共20分) 1．C 2．B 3．C 4．D 5．C 6．C 7．B 8．B 9．C 10．D 四、算法设计题(4小题,共32分) 1．void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data if(ha==0) s->next=hb; else s->next=ha; } 2．解： void Del(ListNode *head,int i,int k) { node *p,*q; int j; if (i==1) For (j=1;j<=k;j++) // 删除前k个元素 { p=head; // p指向要删除的结点 head=head->next; Free(p); } Else { p=head; for (j=1;j<=i-2;j++) p=p->next; // p指向要删除的结点的前一个结点 for (j=1;j<=k;j++) { q=p->next; // q 指向要删除的结点 p->next=q->next; free(q); } } } 3．【解答】在有向图中，若邻接表中顶点vi有邻接点vj，在逆邻接表中vj一定有邻接点vi，由此得到本题算法思路：首先将逆邻接表的表头结点firstedge域置空，然后逐行将表头结点的邻接点进行转化。 4．typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix; typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) { int i,j; glinklistnode *p; For(i=0;i<=n-1;i++) g2[i].firstarc=0; For(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) if (g1.edge[i][j]==1) { p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } } 五、填空题(6小题,共12分) 1．链式 2．head->rlink，p->llink 3．p->lchild==0&&p->rchild==0 4．0，n(n-1) 5．正序，n-1 6．关键码的比较次数，记录的移动次数 长沙理工大学计算机与通信工程学院 2013-2014学年二学期数据结构期末考试试卷(B卷) 班级:___________学号:___________姓名:___________得分:___________ 题目部分，(卷面共有31题,100分,各大题标有题量和总分)一、应用题(1小题,共8分) 1．已知无向图G的邻接表如图所示，分别写出从顶点1出发的深度遍历和广度遍历序列。 二、判断正误(7小题,共14分) 1．串中任意个字符组成的子序列称为该串的子串。 2．带权无向图的最小生成树是唯一的。（） 3．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（） 4．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的。（） 5．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（） 6．堆是完全二叉树，完全二叉树不一定是堆。（） 7．数据的逻辑结构和数据的存储结构是相同的。（） 三、单项选择题(10小题,共20分) 1．在顺序表中，只要知道（），就可以求出任一结点的存储地址。 A．基地址 B．结点大小 C．向量大小 D．基地址和结点大小 2．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。 A q=p->next；p->data=q->data；p->next=q->next；free(q)； B q=p->next；q->data=p->data；p->next=q->next；free(q)； C q=p->next；p->next=q->next；free(q)； D q=p->next；p->data=q->data；free(q)； 3．循环队列占用的空间( )。 A．必须连续 B．不必连续 C．不能连续 D．可以不连续 4．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。 A．5和1 B．4和2 C．2和4 D．1和5 5．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A 20 B 256 C 512 D 1024 6．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（）。 A 4 B 5 C 6 D 7 7．若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择（）排序，如果从节省存储空间的角度来考虑则最好选择（）排序。 9．设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（）。 A 40，42，45，55，80，83 B 42，40，45，80，85，88 C 42，40，45，55，80，85 D 42，40，45，85，55，80 10．下列叙述正确的是（） A．算法的执行效率与数据的存储结构无关 B．算法的空间复杂度是指算法程序中指令（或语句）的条数 C．算法的有穷性是指算法必须能在执行有限个步骤之后终止 D．算法的时间复杂度是指执行算法程序所需要的时间 四、算法设计题(4小题,共32分) 1．设计判断单链表中元素是否是递增的算法。 2．一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的记数器cont，试写出相应的入队算法和出队算法。 3．设计一个在链式存储结构上统计二叉树中结点个数的算法。 4．设计算法，计算图中出度为零的顶点个数。 五、填空题(6小题,共12分) 1．当循环队列为空时，不能进行出队运算，这种情况称为（）。 2．已知顺序栈S，在对S进行进栈操作之前首先要判断（），在对S进行出栈操作之前首先要判断（）。 3．设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为( )。 4．完全二叉树中第5层上最少有（）个结点，最多有（）个结点。 5．表示一个有100个顶点，1000条边的有向图的邻接矩阵有（）个非零矩阵元素。 6．若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为（）六、简答题(2小题,共10分) 1．设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列，能否得到输出顺序为154623的序列。 2． 设有无向图G（如下图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。 七、名词解释(1小题,共4分) 1．什么是AOE网? 长沙理工大学计算机与通信工程学院 2013-2014学年二学期数据结构期末考试试卷(B卷) 答案部分，(卷面共有31题,100.0分,各大题标有题量和总分) 一、应用题(1小题,共8分) 1．【解答】深度优先遍历序列为：1，2，3，4，5，6 广度优先遍历序列为：1，2，4，3，5，6 二、判断正误(7小题,共14分) 1．错 2．错 3．对 4．错 5．错 6．对 7．错 三、单项选择题(10小题,共20分) 1．D 2．A 3．A 4．B 5．C 6．A 7．D 8．快速堆 9．C 10．C 四、算法设计题(4小题,共32分) 1．int isriselk(lklist *head) { if(head==0||head->next==0) return(1);else For(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1); } 2．解：用一个循环数组Queue[0，n-1]表示该循环队列，头指针为front，计数器count用来记录队列中结点的个数。 （1）入队算法： void inqueqe(int x) { int temp; if (count==n) printf(\" 队列上溢出\\n\"); Else { count++ temp=(front+count)%n; Queue[temp]=x } } （2）出队算法： int outqueue() { int temp; if (count==0) printf(\" 队列下溢出\\n\"); Else { temp=Queue[front]; front=(front+1)%n; count--; return temp; } } 3．void countnode(bitree *bt,int &count) { if(bt!=0) {count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} } 4．在有向图的邻接矩阵中，一行对应一个顶点，每行的非零元素的个数等于对应顶点的出度。因此，当某行非零元素的个数为零时，则对应顶点的出度为零。据此，从第一行开始，查找每行的非零元素个数是否为零，若是则计数器加1。具体算法如下： 五、填空题(6小题,共12分) 1．下溢 2．栈是否满栈是否空 3．0（1） 4．1，16 5．1000 6． O（n） 六、简答题(2小题,共8分) 2 1．不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到部分 输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。 2．E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 七、名词解释(1小题,共4分) 1．若在带权有向图G中以项点表示事件，以有向边表示活动，边上的权值表示该活动持续 的时间，则此带权有向图称为用边表示活动的网(Activity On Edge network)，简称AOE网。 预览：长沙理工大学计算机与通信工程学院 2013-2014学年二学期数据结构期末考试试卷(C卷) 班级:___________学号:___________姓名:___________得分:___________ 题目部分，(卷面共有32题,100分,各大题标有题量和总分)一、应用题(2小题,共16分) 1．分析下列程序段的时间复杂度： （1）for (i=1; i<=n; i=2*i) ++x; （2）for (i=1; i<=n; ++i) for (j=1; j<=i-1; ++j) ++x; 2．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。 二、判断正误(5小题,共10分) 1．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（） 2．非空的双向循环链表中任何结点的前驱指针均不为空。（） 3．在循环队列中无溢出现象。（） 4．稀疏矩阵压缩存储后，必会失去随机存取功能。（） 5．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（） 三、单项选择题(10小题,共20分) 1．递归算法一般需要利用（）实现。 2．已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（）。 A． B+(i-1)*m B．B+i*m C． B-i*m D． B+(i+1)*m 3．在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（）。 A．已固定 B．不固定 C．可以改变 D．动态变化 4．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A top=top+1; B top=top-1; C top->next=top; D top=top->next; 5．若串S=\"SOFTWARE\"，其子串的数目最多是：（）。 A．35 B．36 C．37 D．38 6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（）。 A h B h+1 C h或h+1 D 任意 7．下列命题正确的是（）。 A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一 8．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。 A 99 B 97 C 91 D 93 9．堆的形状是一棵（）。 A二叉排序树 B满二叉树 C完全二叉树 D 判定树 10．设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。 A F，H，C，D，P，A，M，Q，R，S，Y，X B P，A，C，S，Q，D，F，X，R，H，M，Y C A，D，C，R，F，Q，M，S，Y，P，H，X D H，C，Q，P，A，M，S，R，D，F，X，Y 四、算法设计题(4小题,共32分) 1．设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 2．设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。 3．对给定的带头结点的单链表L，编写一个删除L中值为X的结点的直接前趋结点的算法。4．设计一个在链式存储结构上统计二叉树中结点个数的算法。 五、填空题(11小题,共22分) 1．已知顺序栈S，在对S进行进栈操作之前首先要判断（），在对S进行出栈操作之前首先要判断（）。 2．设循环队列存放在向量sq.data[0:M]中，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。 3．广义表((a), (((b),c)),(d))的表头是（），表尾是（）。 4．在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。 5．一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。 6．希尔排序法属于（） 7．对n个待排序记录序列进行快速排序，所需要的最好时间复杂度是（），最坏时间复杂度是（）。 8．假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（） 9．对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。 10．图形结构的元素之间存在（）的关系。 11．数据的存储结构是指（） 长沙理工大学计算机与通信工程学院 2013-2014学年二学期数据结构期末考试试卷(C卷) 答案部分，(卷面共有32题,100.0分,各大题标有题量和总分) 一、应用题(2小题,共22分) 1．O(log2n) （2）O(n2) 2．【解答】构造的哈夫曼树如图所示。 树的带权路径长度为： WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 =120 二、判断正误(5小题,共22分) 1．错 2．对 3．错 4．对 5．对 三、单项选择题(10小题,共22分) 1．栈 2．A 3．A 4．D 5．C 6．C 7． B 8．B 9．C 10．D 四、算法设计题(4小题,共22分) 1．typedef char datatype; typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) { lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) { head=p->next; p->next=0; if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;} else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } } 2．typedef struct node { int data; struct node *next; }lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; For(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data; t->next=hc; hc=t;} } } 3．解： void delete(ListNode *L) { ListNode *p=L,*q; if (L->next->data==X) { printf (“值为x的结点是第一个结点，没有直接前趋结点可以删除”); return; } for (;p->next->data!=X; q=p; p=p->next); // 删除指针p所指向的结点 q->next=p->next; delete p; } 4．void countnode(bitree *bt,int &count) { if(bt!=0) {count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} } 五、填空题(11小题,共22分) 1．栈是否满栈是否空 2．(sq.rear+1)%(M+1)==sq.front； 3．(a)，((((b),c)),(d)) 4．n，n-1 5．2i-1，(n+1)/2，(n-1)/2 6．插入类排序 【解答】O(nlog2n)，O(n2) 7． 8．n(n-1)/2 9．60 10．多对多 11．数据的逻辑结构在计算机中的表示 因篇幅问题不能全部显示，请点此查看更多更全内容