2013年4月考试数据结构第三次作业

一、单项选择题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. 栈是实现过程和函数等子程序所必需的结构。

附录习题及实验参考答案习题1参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). C. (9). B. (10.)A.1.2.填空题(1). 数据关系(2). 逻辑结构物理结构(3). 线性数据结构树型结构图结构(4). 顺序存储链式存储索引存储散列表（Hash）存储(5). 变量的取值范围操作的类别(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7). 关系网状结构树结构(8). 空间复杂度和时间复杂度(9). 空间时间(10). Ο(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。

数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。

数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。

数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。

数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。

数据类型：是指变量的取值范围和所能够进行的操作的总和。

算法：是对特定问题求解步骤的一种描述，是指令的有限序列。

1.4 语句的时间复杂度为：(1) Ο(n2)(2) Ο(n2)(3) Ο(n2)(4) Ο(n-1)(5) Ο(n3)1.5 参考程序：main(){int X,Y,Z；scanf(“%d, %d, %d”,&X,&Y,Z)；if (X>=Y)if(X>=Z)if (Y>=Z){ printf(“%d, %d, %d”,X,Y,Z);}else{ printf(“%d, %d, %d”,X,Z,Y);}else{ printf(“%d, %d, %d”,Z,X,Y);}elseif(Z>=X)if (Y>=Z){ printf(“%d, %d, %d”,Y,Z,X);}else{ printf(“%d, %d, %d”,Z,Y,X);}else{ printf(“%d, %d, %d”,Y,X,Z);}}1.6 参考程序：main(){int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<=n;i++)scanf(“%f ”,&a[i]);p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x;x=x*x;}printf(“%f”,p)’}习题2参考答案2.1选择题(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.2.2.填空题(1). 有限序列(2). 顺序存储和链式存储(3). Ｏ(n) O(n)(4). n-i+1 n-i(5). 链式(6). 数据指针(7). 前驱后继(8). Ο(1) Ο(n)(9). s->next=p->next; p->next=s ;(10). s->next2.3. 解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…, （n-1）/2的元素交换，输出数组a的元素。

第六章详细设计习题一、名词解释详细设计：确定每个模块的具体执行过程，也称过程设计。

详细设计的结果基本决定了最终的程序代码的质量。

结构化程序设计：是按照一组能提高程序的可读性和易维护性的规则而进行的程序设计方法，目的是为了使程序具有一种合理的结构，以使程序易理解和维护，便于保证和验证程序的正确性。

PDA：问题分析图，是一种算法描述工具。

它是一种从左向右展开的二维树形结构，其控制流程为自上而下，从左到右地执行。

二、填空1、详细设计阶段的主要任务是确定每个模块的具体执行过程。

2、软件的详细设计可以用图形、表格、过程设计语言三种形式的描述工具表示模块的处理过程。

3、处理过程设计中最典型的方法是结构化程序设计方法，其基本要点是自顶向下、逐步求精。

4、任何程序都可由顺序、选择和循环3种基本控制结构构造，这3中基本结构的基本点是单入口、单出口。

5、PAD图是一种从左到右展开的二维树形结构，PAD图的控制流程是自上而下、从左到右地执行。

6、详细设计是软件设计的第二个阶段，主要确定每个模块的具体执行过程，故也成为过程设计。

7、详细设计的目标不仅是逻辑上正确地实现每个模块的功能，还应使设计出的处理过程清晰易懂。

结构化程序设计是实现该目标的关键技术之一，它指导人们用良好的思想方法开发易于阅读、易于理解的程序。

三、单项选择1、在详细设计阶段，经常采用的工具包括（ C ）A.SAB.SDC.PADD.DFD2、详细设计阶段的任务是（ A ）。

A.算法设计B.功能设计C.调用达观系设计D.输入/输出设计3、结构化程序设计的一种基本方法是（ D ）。

A.筛选法B.递归法C.迭代法D.逐步求精法4、下面说法不正确的是（ C ）。

A.流程图不易表示数据结构B.流程图容易造成非结构化的程序结构C.流程图支持逐步求精D.流程图描述的是程序的逻辑结构5、下面说法不正确的是（ B ）。

A. PAD图支持逐步求精B.PAD图容易造成非结构化的程序结构C. PAD图描述的是算法D.PAD图容易表达程序的层次结构四、简答题1、什么是详细设计，？该阶段的基本任务是什么？详细设计是软件设计的第二个阶段，确定每个模块的具体执行过程，也称过程设计。

数据结构第三次作业补充题环形链表队列的插入和删除函数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。

《数据结构》模拟试题10一、单项选择题（每题 3 分，共30分）1．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。

(A) 2n (B) n (C) n/2 (D) n(n-1)2．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。

(A) n (B) n-1 (C) 2n (D) 2n-13．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（）。

(A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80(C) 42，40，55，60，80，85 (D) 42，40，60，85，55，804．（）二叉排序树可以得到一个从小到大的有序序列。

(A) 先序遍历(B) 中序遍历 (C) 后序遍历 (D) 层次遍历5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。

(A) 2i+1 (B) 2i (C) i/2 (D) 2i-16．程序段s=i=0；do {i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（）。

(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。

(A) head==0 (B) head->next==0(C) head->next==head (D) head!=08．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。

(A) 20 (B) 256 (C) 512 (D) 10249．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。

(A) 1 (B) 2 (C) 3 (D) 410.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。

第3次作业一、填空题（本大题共30分，共10小题，每小题3分）1.具有8个顶点的无向图，边的总数最多为_______ o2.树在计算机内的表示方式有______ , ______ , _____ o3.设有一个n阶的下三角矩阵A,如果按照行的顺序将下三角矩阵中的元素（包描对角线上元素）存放在n（n+l）个连续的存储单元中，则A[i][j]与A[0][0] Z间有 _______ 个数据元素。

4.队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是______ O5.在广义表的存储结构中，单元索结点与表元索结点有一个域对应不同，各自分别为______ 域和_______ 域。

6.构造连通网最小生成树的两个典型算法是______ O7.在一个稀疏矩阵中，每个非零元索所对应的三元组包括该元索的_________ 、和三项。

8.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有__________ 个叶子结点。

9.非空的单循环链表head的尾结点（由p指针所指）满足条件10.在哈希文件屮，处理冲突的方法通常有______ 、______ 、______ 和______ 四种。

二、算法设计题（本大题共20分，共2小题，每小题10分）1.回文是指止读反读均相同的字符序列，如〃abba〃和〃abdba"均是回文，但"good" 不是回文。

试写一个算法判定给定的字符向量是否为回文。

2.编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B,其头结点指针分别为g和pb,使得A链表小含有原链表AM序号为奇数的元索，而链表B屮含有原链表A屮序号为偶数的元索，且保持原来的相对顺序。

三、简答题（本大题共20分，共4小题，每小题5分）1.何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2.一棵度为2的树与一棵二义树有何区别？3.指出下述程序段的功能是什么？void Demol( SeqStack *S, int m){ // 设DataType 为int 型SeqStack T; inti;InitStack (&T);while (! StackEmpty( S))if (( i二Pop(S)) !=m) Push( &T, i);while (! StackEmpty( &T)){i二Pop(&T); Push(S, i);4.给定集合{15, 3, 14, 2, 6, 9, 16, 17}(1)(3分)用□表示外部结点，用O表示内部结点，构造相应的huffman 树：(2)(2分)计算它的带权路径长度：(3)(2分)写出它的huffman编码：(4)(3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。

全国2014年4月高等教育自学考试数据结构试题课程代码：02331本试卷满分100分，考试时间150分钟.考生答题注意事项：1.本卷所有试题必须在答题卡上作答。

答在试卷上无效。

试卷空白处和背面均可作草稿纸。

2.第一部分为选择题。

必须对应试卷上的题号使用28铅笔将“答题卡”的相应代码涂黑。

3.第二部分为非选择题。

必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。

4.合理安排答题空间。

超出答题区域无效。

第一部分选择题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

错涂、多涂或未涂均无分。

1.与数据存储结构无关．．的概念是A.栈B.链表C.顺序表D.二叉链表2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是A．1010 B.1016C.1018D.10193.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是A.2B.3C.4D..64.下列关于队列的叙述中,错误．．的是A.队列是一种先进先出的线性表B.队列是一种后进后出的线性表C.循环队列中进行出队操作时要判断队列是否为空D.在链队列中进行入队操作时要判断队列是否为满5.对稀疏矩阵进行压缩存储的目的是A.便于运算B.节省存储空间C.便于输入输出D.降低时间复杂度6.一棵二叉树的第7层上最多含有的结点数为A.14B.64C.127D.1287.下列选项为完全二叉树的是8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是A. n×eB. eC. 2eD. n+e9.无向图中所有顶点的度数之和与所有边数之比是A.1/2B.1C.2D.410.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为A. O（n）B. O（n+e）C. O（n2）D. O（n3）11.对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是A.归并排序B.快速排序C.直接选择排序D.冒泡排序12.比较次数与待排序列初始状态无关的排序方法是A.快速排序B.冒泡排序C.直接插入排序D.直接选择排序13.查找较快,且插入和删除操作也比较方便的查找方法是A.分块查找B.二分查找C.顺序查找D.折半查找14.下列关于m阶B树的叙述中,错误．．的是A.根结点至多有m棵子树B.所有叶子都在同一层次上C.每个非根内部结点至少有棵子树D.结点内部的关键字可以是无序的15.在散列查找中处理冲突时,可以采用开放定址法。

1第一章绪论1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

● 数据：指能够被计算机识别、存储和加工处理的信息载体。

● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。

数据元素有时可以由若干数据项组成。

● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

通常数据类型可以看作是程序设计语言中已实现的数据结构。

● 数据结构：指的是数据之间的相互关系，即数据的组织形式。

一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

● 逻辑结构：指数据元素之间的逻辑关系。

● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.● 线性结构：数据逻辑结构中的一类。

它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

栈、队列、串等都是线性结构。

● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

数组、广义表、树和图等数据结构都是非线性结构。

1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。

这张登记表中，每个学生的各项体检信息排在一行上。

这个表就是一个数据结构。

每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一就确定了这个表的逻辑结构是线性结构。

这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。

在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。