第一篇：数据结构试卷及参考答案_10
数据结构试卷
（十）一、选择题(24分)1．下列程序段的时间复杂度为（）。
i=0，s=0； while(s (A)单向链表 (B)单向循环链表(C)双向链表 (D)双向循环链表 3．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。(A)s->next=p->next；p->next=-s；(B)q->next=s； s->next=p；(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q； 4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。(A)5，3，4，6，1，2(B)3，2，5，6，4，1(C)3，1，2，5，4，6(D)1，5，4，6，2，3 5．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。 (A)10(B)19(C)28(D)55 6．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（）个叶子结点。 (A)(i1)Ni1mi(B) Ni1mi(C) Ni2mi(D)1(i1)Ni2mi 7.二叉排序树中左子树上所有结点的值均（）根结点的值。 (A)<(B)>(C)=(D)!= 8.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。 (A)129(B)219(C)189(D)229 9.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。 (A)n2(B)n(n+1)(C)n(n+1)/2(D)n(n-1)/2 10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。 (A)2n(B)n+l(C)2n-1(D)2n+l 11.设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。 (A)6(B)7(C)8(D)9 12.设一组初始记录关键字序列为(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 二、填空题(48分，其中最后两小题各6分)1.设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需要比较_____________次。 2.快速排序算法的平均时间复杂度为____________，直接插入排序算法的平均时间复杂度为___________。 3.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。4.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。 5.设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有_________个空指针域。 6.设指针变量p指向单链表中结点A，则删除结点A的语句序列为： q=p->next；p->data=q->data；p->next=___________；feee(q)； 7.数据结构从逻辑上划分为三种基本类型：___________、__________和___________。8.设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。 9.设散列表的长度为8，散列函数H(k)=k %7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是________。10.设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_____________________。 11.设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为______________________。 12.设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，则该图的一个拓扑序列为_________________________。 13.下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。 typedefstruct node{int data;struct node*lchild;________________;}bitree;void createbitree(bitree *&bt){ scanf(“%c”,&ch);if(ch=='#')___________;else { bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;________;createbitree(bt->rchild);} } 14.下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。 typedef struct node {int data;struct node *next;} lklist;void lklistcreate(_____________ *&head){ for(i=1;i<=n;i++){ p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;if(i==1)head=q=p;else {q->next=p;____________;} } } 三、算法设计题(22分)1． 设计在链式存储结构上合并排序的算法。2． 设计在二叉排序树上查找结点X的算法。 3． 设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。 数据结构试卷 （十）参考答案 一、选择题 1．A 2．D 7．A 8．D 3．B 9．D 4．B 10．C 5．B 11．B 6．D 12．D 二、填空题 1.4，10 2.O(nlog2n)，O(n2)3.n 4.1，2 5.6.7.8.n(m-1)+1 q->next 线性结构，树型结构，图型结构 O(n2)，O(n+e)9.8/3 10.(38，13，27，10，65，76，97)11.(10，13，27，76，65，97，38)12.124653 13.struct node *rchild，bt=0，createbitree(bt->lchild)14.lklist，q=p 三、算法设计题 1.设计在链式存储结构上合并排序的算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc){ lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data else {if(s==0)hc=s=hb;else {s->next=hb;s=hb;};hb=hb->next;} if(ha==0)s->next=hb;else s->next=ha;} 2.设计在二叉排序树上查找结点X的算法。 bitree *bstsearch1(bitree *t, int key){ bitree *p=t; while(p!=0)if(p->key==key)return(p);else if(p->key>key)p=p->lchild;else p=p->rchild; return(0);} 3.设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。 void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j-1]; while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;} r[j-1]=temp;} 一、选择题（每小题2分，共30分）1.数据结构是（D）。 A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．以下与数据的存储结构无关的术语是（D）。 A．链队列 B.链表 C.顺序表 D.栈 3．以下数据结构中，（A）是非线性数据结构 A．树 B．字符串 C．队 D．栈 4．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。 A．98 B．100 C．102 D．106 5．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。A．插入 B．删除 C．排序 D．查找 6．线性表采用链式存储时，其地址(D)。 A．必须是连续的 B．一定是不连续的 C．部分地址必须连续 D．连续与否均可以 7．线性表是(A)。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 8．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）。 A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1 9.若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C）。 A．k B．n-k-1 C．n-k+1 D．不确定 10.对于队列操作数据的原则是（A）。 A.先进先出 B.后进先出 C.先进后出 D.不分顺序 11.栈和队列的共同点是（C）。 A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点 12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（A）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13.空串与空格串（B）。 A．相同 B．不相同 C．可能相同 D．无法确定 14.串与普通的线性表相比较，它的特殊性体现在（C）。A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意 15.串的长度是指（B）。 A.串中所含不同字母的个数 B.串中所含字符的个数 C.串中所含不同字符的个数 D.串中所含非空格字符的个数 二、填空题（每空2分，共20分） 1． 线性表、栈和队列，串都是__线性_____结构。2． 数据的基本单位是__数据元素_______________。 3． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序______存储结构。4． 已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为Loc(a1)，那么，第i个元素的存储地址Loc(ai)= Loc(a1)+(i-1)*k。5． 栈（stack）是限定在表尾进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__栈顶________，而另一端称为_栈底________。6． 一个循环队列Q中，头指针和尾指针分别为Q.front和Q.rear，且最大队列长度为MaxQSize，则判断队空的条件为 Q.rear==Q.front,判断队满的条件为(Q.rear+1)%MaxQSize==Q.front。队列的长度为(.rear-Q.front+MaxQSize)%MaxQSize 7． 两个串相等的充分必要条件是 两个串的长度相等，且各个对应位置的字符都相等。 三、程序填空题（每空3分，共30分） 1.在带头结点的单链表L中第i个数据元素之前插入数据元素e的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 typedef struct node {int data； struct node *next； }linknode,*link； int ListInsert_L(link &L, int i, int e){ Linknode *p；int j； p = L； j = 0； while(p && j < i-1){ p=p->next ； ++j； } // 寻找第i-1个结点 if(!p || j > i-1)return 0； s=(link)malloc(sizeof(linknode))；// 生成新结点s s->data = e； s->next=p->next ； p->next = s； // 插入L中 return 1； } 2.对顺序栈的C语言描述算法如下，其中top为栈顶指针，请填充算法中标出的空白处，插入元素e为新的栈顶元素。 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *base;char *top;int stacksize;}SqStack; int Push(SqStack &S, char e){ // if((s.top-s.base)>=s.stacksize)//栈满，追加存储空间 { S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType))； if(!S.base)return 0； S.top = s.base+s.stacksize ； //修改栈顶指针 S.stacksize += STACKINCREMENT； } *s.top++=e ；//插入元素 return 1； } 3.对链队列的C语言描述算法如下，请填充算法中标出的空白处，删除队列Q 的队头元素并用e返回其值。typedef struct QNode{ QElemType data； struct QNode *next； }QNode, *QueuePtr； typedef struct { QueuePtr front； QueuePtr rear； }LinkQueue； int DeQueue(LinkQueue &Q, QElemType &e){ Linknode *p； if(Q.front==Q.rear)retrun 0；//队列空，返回 p = Q.front-> next； e = p->data； Q.front-> next=p->next；//修改指针 if(Q.rear==p)Q.rear= Q.front ； //队列只有一个元素的情况 free(p)；//释放结点空间 return 1； } 三、算法设计与分析题（每题10分，共20分） 1、简述下列算法实现的功能：（每题5分，共10分）（1）typedef struct LNode{ Char data; struct LNode *next;}LNode,*LinkList;LinkList Demo(LinkList &L){ // L 是无头结点单链表 LNode *Q,*P;if(L&&L->next){ Q=L;L=L->next;P=L;while(P->next)P=P->next; P->next=Q;Q->next=NULL; } return L;}// Demo 答：将单链表的第一个结点删除，放到链尾。 ——————————————————————————————————————————————————— （2）#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;int *top;int stacksize; } Stack;void Demo1(Stack &S, int m){ Stack T;int i; InitStack(T);//初始化栈 while(!StackEmpty(S))//判断栈是否为空 if((i=Pop(S))!=m)Push(T,i);//入栈操作 while(!StackEmpty(T)) { i=Pop(T);//出栈操作 Push(S,i); } } 答：删除栈S中所有值为m的数据元素 2.有一个带头结点的单链表，头指针为head，编写一个算法计算所有数据域为X的结点的个数（不包括头结点）。typedef struct node {int data;struct node *next;}linknode,*link;int sample(link head, int X){ int count=0;link p=head->next;while(p){if(p->data==X)count++;p=p->next;} return count;} 2014－2015学第一学期《数据结构》 期中考试试卷 一、选择题（每题2分，共20分） 1.计算机内部数据处理的基本单位是（B）。 A.数据 B.数据元素 C.数据项 D.数据库 2.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。 for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O(n)C.O(n) D.O(n) 33.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（A）个元素。 A．n-i B．n-i+l C．n-i-1 D．i 4.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（B）。 A．s->next=p->next;p->next=s B．q->next=s;s->next=p C．p->next=s->next;s->next=p D．p->next=s;s->next=q 5.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。C A．top不变 B．top=0 C．top--D．top++ 6.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。D A．rear％n= = front B．（front+l）％n= = rear C．rear％n-1= = front D．(rear+l)％n= = front 7.两个字符串相等的条件是（D）。 A.两串的长度相等 B.两串的长度相等，并且两串包含的字符相同 C.两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 8.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（C）。A.SA+141 B.SA+144 C.SA+222 D.SA+225 9.设有广义表D=(a,b,D)，其长度为（B），深度为（A）。A.无穷大 B.3 C.2 D.5 10.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（B）个。 A.15 B.16 C.17 D.47 二、填空题（每空1分，共20分） 1.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。2.集合，线性，树，图 2.一个算法的效率可分为__________________效率和__________________效率。4.时间，空间 3.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。7．顺 （第1页，共3页） 序，链接 4.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。12．O(1)，O(n)5.可以在线性表的______位置插入和删除元素；对于栈只能在_______位置删除元素；对于队列只能在_______位置插入元素。9任何，栈顶，队尾 6.设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。3.“BCDEDE” 7.一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。1.线性结构，顺序结构，以行为主序，以列为主序 8.三维数组R[c1„d1,c2„d2,c3„d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1） 9.数组A[1„10，-2„6，2„8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。10.913 三、简答题（每题6分，共18分）1.已知L是无表头结点的单链表，且P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1)在P结点后插入S结点。(2)在表首插入S结点。(3)在表尾插入S结点。2已知L是带表头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1)删除P结点的直接后继结点。(2)删除P结点。（3）删除尾元结点。3． LinkList mynote(LinkList L){//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next)p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2, „,an）,写出算法执行后的返回值所表示的线性表。 该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 四、算法设计题（每题14分，共42分）1.假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知p为指向链表中某结点的指针，设计在链表中删除p所指结点的前趋结点的算法。 解：可引入一个指针q，当q->next=p时，说明此时q所指的结点为p所指结点的前趋结点，从而可得算法如下： void delete(LinkList *p){ //在链表中删除p所指结点的前趋结点 LinkList *q,*t; q=p; while(q->next->next!=p)//q->next不是p的前趋结点 （第2页，共3页） q=q->next; t=q->next;//t指向要删除结点 q->next=p;//删除t结点 free(t);｝ 2.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。 2．算法描述如下： delete(LinkList *head, int max, int min){ LinkList *p,*q; q=head; p=head->next; while(p!=NULL) if((p->data<=min)||(p->data>=max)) { q=p; p=p->next; } else { q->next=p->next;free(p);p=q->next;} } 3.假设表达式有单字母变量和双目四则运算符构成。试写一个算法，对一个通常书写形式且书写正确的表达式求值。 （第3页，共3页） 数据结构试卷 （一）一、选择题（20分） 1．组成数据的基本单位是（）。 (A)数据项(B)数据类型(C)数据元素(D)数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。 (A)线性结构(B)树型结构(C)图型结构(D)集合 3．数组的逻辑结构不同于下列（）的逻辑结构。 (A)线性表(B)栈(C)队列(D)树 4．二叉树中第i(i≥1)层上的结点数最多有（）个。 ii-1(A)2i(B)2(C)2(D)2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。 (A)p->next=p->next->next(B)p=p->next (C)p=p->next->next(D)p->next=p 6．设栈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 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。 (A)100(B)40(C)55(D)80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。 (A)3(B)4(C)5(D)1 9．根据二叉树的定义可知二叉树共有（）种不同的形态。 (A)4(B)5(C)6(D)7 10.设有以下四种排序方法，则（）的空间复杂度最大。 (A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序 二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]){ i=j=0;while(i 三、应用题（30分） 1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。 2．设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 3．设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。 4．设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。5．设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树。 四、算法设计题(20分)1.设计判断单链表中结点是否关于中心对称算法。2.设计在链式存储结构上建立一棵二叉树的算法。3.设计判断一棵二叉树是否是二叉排序树的算法。 数据结构试卷 （一）参考答案 一、选择题 1.C 2.C 3.D 4.C 5.A 6.C 7.C 8.B 9.B 10.B 二、填空题 1.(F+1)% m 2.O(n)，O(n)3.2n，n+1 4.s->next=p->next;s->next=s 5.n, 2e 6.m=2e 7.CBA 8.4，16 9.i-j+1，0 10.n-1 三、应用题 1.链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。2.哈夫曼树略，WPL=78 3.(18,5,16,19,21,23)，(5，16，21，19，18，23) h0h18h2012345674.线性探测： 链地址法：h310 81025322768h42532h568h6275.深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)} 四、算法设计题 1.设计判断单链表中结点是否关于中心对称算法。 typedef struct {int s[100];int top;} sqstack;int lklistsymmetry(lklist *head){ sqstack stack;stack.top=-1;lklist *p; for(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;} for(p=head;p!=0;p=p->next)if(p->data==stack.s[stack.top])stack.top=stack.top-1;else return(0); return(1);} 2.设计在链式存储结构上建立一棵二叉树的算法。 typedef char datatype;typedef struct node {datatype data;struct node *lchild,*rchild;} bitree;void createbitree(bitree *&bt){ char ch;scanf(“%c”,&ch); if(ch=='#'){bt=0;return;} bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchild);createbitree(bt->rchild);} 3.设计判断一棵二叉树是否是二叉排序树的算法。 int minnum=-32768,flag=1;typedef struct node{int key;struct node *lchild,*rchild;}bitree;void inorder(bitree *bt){ if(bt!=0) {inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);} } 《数据结构》自考复习思考试题 一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上（） A.操作的有限集合B.映象的有限集合 C.类型的有限集合D.关系的有限集合 2.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为（）A.n-i+1 B.i C.i+1 D.n-i 3.若不带头结点的单链表的头指针为head，则该链表为空的判定条件是（）A.head==NULL B.head->next==NULL C.head!=NULL D.head->next==head 4.引起循环队列队头位置发生变化的操作是（）A.出队 B.入队 C.取队头元素 D.取队尾元素 5.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（）A.2，4，3，1，5，6 B.3，2，4，1，6，5 C.4，3，2，1，5，6 D.2，3，5，1，6，4 6.字符串通常采用的两种存储方式是（）A.散列存储和索引存储 B.索引存储和链式存储 C.顺序存储和链式存储 D.散列存储和顺序存储 7.设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为（）A.m B.n-m C.n-m+1 D.n 8.二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为（）A.429 B.432 C.435 D.438 9.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是（）A.(e,f) B.((e,f))C.(f) D.()10.下列图示的顺序存储结构表示的二叉树是（）11.n个顶点的强连通图中至少含有（）A.n-1条有向边 B.n条有向边 C.n(n-1)/2条有向边 D.n(n-1)条有向边 12.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为（）A.(19，23，56，34，78，67，88，92) B.(23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92) D.(19，23，67，56，34，78，92，88)13.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（） A.4 B.5 C.8 D.9 14.由同一关键字集合构造的各棵二叉排序树（）A.其形态不一定相同，但平均查找长度相同 B.其形态不一定相同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同 D.其形态均相同，平均查找长度也都相同 15.ISAM文件和VSAM文件的区别之一是（）A.前者是索引顺序文件，后者是索引非顺序文件 B.前者只能进行顺序存取，后者只能进行随机存取 C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘 二、填空题(本大题共10小题，每空2分，共20分)16.数据的逻辑结构在计算机存储器内的表示，称为数据的____________。17.删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。18.栈下溢是指在____________时进行出栈操作。 19.已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为____________。 20.去除广义表LS=(a1,a2,a3,„„，an)中第1个元素，由其余元素构成的广义表称为LS的____________。 21.已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。22.在有向图中，以顶点v为终点的边的数目称为v的____________。 23.当关键字的取值范围是实数集合时，无法进行箱排序和____________排序。24.产生冲突现象的两个关键字称为该散列函数的____________。 25.假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中____________。 三、解答题(本大题共4小题，每小题5分，共20分)26.假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。(1)写出队满的条件表达式；(2)写出队空的条件表达式； (3)设m=40,rear=13,quelen=19,求队头元素的位置；(4)写出一般情况下队头元素位置的表达式。 27.已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。28.画出下图所示有向图的所有强连通分量。 29.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；(2)对所举序列进行快速排序，写出排序过程。 四、算法阅读题(本大题共4小题，每小题5分，共20分)30.阅读下列算法，并回答问题：(1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L；(2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L；(3)简述算法的功能。 void f30(SeqList*L, DataType x){ int i =0, j; while(i if(i for(j=i+1;j L->data［j-1］=L->data［j］; L->length--; } else { for(j=L->length;j>i;j--) L->data［j］=L->data［j-1］; L->data［i］=x; L->length++; } } 31.已知图的邻接表表示的形式说明如下： #define MaxNum //图的最大顶点数 typedef struct node { int adjvex; //邻接点域 struct node *next; //链指针域 } EdgeNode; //边表结点结构描述 typedef struct { char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 } VertexNode; //顶点表结点结构描述 typedef struct { VertexNode adjlist［MaxNum］; //邻接表 int n, e; //图中当前的顶点数和边数 } ALGraph; //邻接表结构描述 下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。 typedef enum {FALSE, TRUE} Boolean;Boolean visited［MaxNum］;void DFSForest(ALGraph *G){ int i; for(i=0;i (1) ; for(i=0;i EdgeNode *p; visited［i］=TRUE; p=G->adjlist［i］.firstedge; while(p!=NULL){ if(!visited［p->adjvex］){ printf(″<%c,%c>″,G->adjlist［i］.vertex，G->adjlist［p->adjvex］.vertex); (2) ; } (3) ; } } 32.阅读下列算法，并回答问题： (1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L；(2)写出上述函数调用过程中进行元素交换操作的总次数。void f32(int R［］,int n){ int i,t; for(i=0;i while(R［i］!=i){ t=R［R［i］］; R［R［i］］=R［i］; R［i］=t; } } 33.已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为：。请在空缺处填入适当内容，使其成为一个完整算法。void f33(LinkList L, LinkList H［］, int m){//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在 int i,j; LinkList p,q; for(i=0;i H［i］= (1) ; p=L->next; while(p) { q=p->next; j=p->key%m; (2) ; H［j］=p; (3) ; } free(L); } 五、算法设计题(本大题10分)34.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType;typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指针 struct node *parent; //指向双亲的指针 } BinTNode;typedef BinTNode *BinTree;若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。 (1)就后继的不同情况，简要叙述实现求后继操作的方法； (2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。数据结构标准答案 一、单项选择题 1.(B)2.(D)3.(A)4.(A)5.(D)6.(C)7.(C)8.(A)9.(B)10.(A)11.(B)12.(D)13.(C)14.(B)15.(C) 二、填空题(本大题共10小题，每空2分，共20分)16.存储结构 17.q = p->pre;q->pre->next = p;p->pre = q->pre;free(q);18.栈空 19.“DEFG” //注意双引号不能少 20.表尾 21.２^(I-2)+M/2 叶子结点． 22.入度 23.基数 24.同义词 25.已有m个同义词记录 三、解答题(本大题共4小题，每小题5分，共20分)26.(1)quelen == m(2)quelen == 0(3)(13quelen + m)% m 27.B / A F / E G / C D 28.3个: a、bce、dfg 29.我们知道，对n个关键自序列进行一趟快速排序，要进行n-1次比较，也就是基准和其他n-1个关键字比较。 这里要求10次，而71)= 10，这就要求2趟快速排序后，算法结束。所以，列举出来的序列，要求在做partition的时候，正好将序列平分(1)4 1 3 2 6 5 7 或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7.......(2)自己列吧 :) 四、算法阅读题(本大题共4小题，每小题5分，共20分)30.(1)L=(3,7,11,14,15,20,51)(2)L=(4,7,14,20,51)(3)在顺序表L中查找数x, 找到，则删除x，没找到，则在适当的位置插入x，插入后，L依然有序.31.(1)FALSE //初始化为未访问 (2)DSFTree(G, p->adjvex);//从相邻结点往下继续深度搜索(3)p = p->next;//下一个未访问的相邻结点 32.(1)L = { 0, 1, 2, 3, 4, 5, 6, 7 };(2)5次 33.(1)NULL //初始化 (2)p->next = H[ j ] //和下面一句完成头插法(3)p = q; //继续遍历L 五、算法设计题(本大题10分)34.1) a)*px 有右孩子，则其右孩子为其中序序列中的后继 b)*px 无右孩子，从*px开始回溯其祖先结点，找到第1个身份为左孩子的结点，找到，则该结点的父结点为*px的中序序列中的后继。找不到，则无后继。2)BinTNode * fintNext(BinTNode * px){ if(px-> rchild)return px->rchild;//*px 有右孩子 BinTNode *q, *qp; q = px;while(qp = q->parent){ //未回溯到根结点 if(qp->lchild == q)return qp;//找到1)b)所述结点 q = qp;//往上回溯 } return NULL;//未找到 }第二篇：数据结构期中试卷及答案
第三篇：数据结构期中考试试卷答案
第四篇：数据结构试卷(一)及答案
第五篇：数据结构试题及答案10
点击咨询 