当前位置：文档之家 › 数据结构习题标准答案

数据结构习题标准答案

  • 格式：doc
  • 大小：828.00 KB
  • 文档页数：27

数据结构习题标准答案————————————————————————————————作者：————————————————————————————————日期：计算机科学与工程学院二OO五年三月目录第一章绪论 (5)第二章线性表 (7)第三章栈和队列 (11)第三章串 (12)第五章数组与广义表 (14)第六章树和二叉树 (16)第七章图 (20)第八章查找 (24)第九章内部排序 (26)第一章绪论1.2.3 综合题 14、设n 为正整数。

试确定下列各程序段中前置以记号@的语句的频度：(1)i = 1; k = 0;While(i<=n - 1) {@ k + = 10 * I ;i ++;}答：n-1(2)i = 1; k = 0;do {@ k + = 10 * I ;i ++;} while (I< = n - 1);答：n-1(3)i = 1; k = 0;While (i<=n - 1) {i ++;@ k + = 10 * i ;}答：n-1(4)k = 0;for ( i = 1;i<=n ;i++) {for ( j = i;j<=n ;j++)@ k + +;}答：(n+1)*n/2(5)for( i = 1;i<=n ;i++) {for( j = i;j<=n ;j++) {for( k = 1;k<=j ;k++)@ x + = delta;}答：1/6*n*(n+1)*( n+2)(6)i=1;j=0;While (i+j<= n){@ if (i>j) j++;else i++;}答：n(7)x= n; y= o;while (x>=(y+1) * (y + 1)){@ y ++;}答：⎣√ n ⎦(8)x= 91; y= 100;while (y>0){@ if (x>100){x-=10; y - -; }else x ++ ;}答：11001.2.3 综合题20、void print_descending(int x,int y,int z)//按从大到小顺序输出三个数{scanf("%d,%d,%d",&x,&y,&z);if(x<y) x<->y; //<->为表示交换的双目运算符,以下同if(y<z) y<->z;if(x<y) x<->y; //冒泡排序printf("%d %d %d",x,y,z);}//print_descending1.2.3 综合题22试编写算法，计算i !. 2i的值并存入数组a[0…arrsize - 1] 的第i- 1个分量中（I= 1,2,….,n）。

假设计算机中允许的整数最大值为maxint, 则当n>arrsize 或对某个k(1≤k≤n)使k!. 2k>maxint 时，应按出错处理，注意选择你认为较好的出错处理方法。

解：Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint{last=1;for(i=1;i<=ARRSIZE;i++){a[i-1]=last*2*i;if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;last=a[i-1];return OK;}}//algo119分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.第二章线性表作业：2.2.2综合题3、编写一个函数将一个向量 A（有 n 个元素且任何元素均不为 0）分拆成两个向量，使 A 中大于 0 的元素存放在 B 中，小于 0 的元素存放在 C 中。

解：本题的算法思想是：依次遍历 A 的元素，比较当前的元素值，大于 0 者赋给 B （假设有 p 个元素），小于 0 者赋给 C（假设有 q 个元素）。

实现本题功能的函数如下： void ret(vector A，int n，vector B，int *p，vector C，int *q) { int i；*p=0；*q=0；for (i=0；i<=n-1；i++){ if (A[i]>0){ (*p)++；B[*p]=A[i]；}if (A[i]<0){ (*q)++；C[*q]=A[i]；}}}2.2.2综合题5、编写一个函数从一给定的向量 A 中删除元素值在 x 到 y(x≤y)之间的所有元素，要求以较高的效率来实现。

解：本题的算法思想是：从 0 开始扫描向量 A，以 k 记录下元素值在 x 到 y 之间的元素个数，对于不满足该条件的元素，前移 k 个位置。

最后返回向量的新长度，这种算法比每删除一个元素后立即移动其后元素效率要高一些。

实现本题功能的过程如下： int del(A，n，x，y)vector A；int n;ElemType x,y;{ int i=0，k=0；while (i<n){ if (A[i]>=x && A[i]<=y) k++；else A[i-k] = A[i]; /* 前移 k 个位置 */i++;}return(n-k);}2.2.2综合题8、有两个向量 A（有 m 个元素）和 B（有 n 个元素），其元素均以从小到大的升序排列，编写一个函数将它们合并成一个向量 C，要求 C 的元素也是以从小到大的升序排列。

解：本题的算法思想是：依次扫描通过 A 和 B 的元素，比较当前的元素的值，将较小值的元素赋给 C，如此直到一个向量扫描完毕，然后将未完的一个向量的余下所有元素赋给C 即可。

实现本题功能的函数如下：int link(vector a,int m,vector b,int n,vector c){ int i=0,j=0,l,k=0;while(i<m && j<n) /* 扫描通过 a 和 b，将当前较小者赋给 c */{ if(a[i]<b[j]) c[k++]=a[i++];else if(a[i]>b[j]) c[k++]=b[j++];else{ /* 相等者只保存一个 */c[k++]=b[j++];i++;}}if(i==m) /* b 未完时，当余下的元素赋给 c*/for(l=j;l<n;l++)c[k++]=b[l];if(j==n) /* a 未完时，当余下的元素赋给 c */ for(l=i;i<m;l++)c[k++]=a[l];return k; /* 返回 c 的长度 */}2.2.2综合题9、有一个单链表（不同结点的数据域值可能相同），其头指针为 head，编写一个函数计算数据域为 x 的结点个数。

解：本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加 1，结点个数存储在变量 n 中。

实现本题功能的函数如下：int count(head,x)node *head;ElemType x;{node *p;int n=0;p=head;while (p!=NULL){if (p->data==x) n++;p=p->next;}return(n);}2.2.2综合题11、有一个单链表 L（至少有 1 个结点），其头结点指针为 head，编写一个函数将 L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。

解：本题采用的算法是：从头到尾扫描单链表 L，将第一个结点的 next 域置为 NULL，将第二个结点的 next 域指向第一个结点，将第三个结点的 next 域指向第二个结点，如此等等，直到最后一个结点，便用 head 指向它，这样达到了本题的要求。

实现本题功能的函数如下：void invert(head)node *head;{node *p，*q，*r;p=head;q=p->next;while (q!=NULL) /*当 L 没有后续结点时终止*/{ r=q->next;q->next=p;p=q;q=r;} head->next=NULL;head=p; /*p 指向 L 的最后一个结点，现改为头结点*/ }2.2.2综合题16、有一个有序单链表（从小到大排列），表头指针为 head，编写一个函数向该单链表中插入一个元素为 x 的结点，使插入后该链表仍然有序。

解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。

实现本题功能的函数如下：node *insertorder(head，x)node *head; ElemType x;{node *s，*p，*q;s=(node *)malloc(sizeof(node)); /*建立一个待插入的结点*/s->data=x;s->next=NULL;if (head==NULL || x<head->data) /*若单链表为空或 x 小于第一个结点的date 域*/{s->next=head; /*则把 s 结点插入到表头后面*/head=s;}else{ q=head; /*为 s 结点寻找插入位置，p 指向待比较的结点，q 指向 p 的前驱结点*/p=q->next;while (p!=NULL && x>p->data) /*若 x 小于 p 所指结点的 data 域值*/if (x>p->data) /*则退出 while 循环*/ {q=p;p=p->next;}s->next=p; /*将 s 结点插入到 q 和 p 之间*/q->next=s;}return(head);}2.2.2综合题23、假设在长度大于 1 的循环单链表中，既无头结点也无头指针，p 为指向该链表中某个结点的指针，编写一个函数删除该结点的前驱结点。

解：本题利用循环单链表的特点，通过 p 指针可循环找到其前驱结点 q 及 q 的前驱结点 r，然后将其删除。

实现本题功能的函数如下：node *del(p)node *p;{node *q，*r;q=p; /*查找 p 结点的前驱结点，用 q 指针指向 */while (q->next!=p) q=q->next;r=q; /*查找 q 结点的前驱结点，用 r 指针指向 */while (r->next!=q) r=r->next;r->next=p; /*删除 q 所指的结点 */free(q);return(p);}2.2.2综合题41试写一算法在带头结点的单链表结构上的实现线性表操作LOCATE（L，X）。

合集下载

数据结构习题(含答案)

数据结构习题(含答案)

数据结构习题(含答案)数据结构习题(含答案)1. 题目描述：请实现一个栈，要求支持以下操作：push(x)将元素x 入栈；pop()弹出栈顶元素；top()返回栈顶元素；empty()判断栈是否为空。

解答：我们可以使用数组来实现栈的功能。

首先定义一个数组stack来存储栈中的元素，同时定义一个整型变量top来表示栈顶的索引位置。

初始时，将top设置为-1，表示栈中没有元素。

1.1 push(x)操作：当要将元素x入栈时，我们先将top的值加1，然后将x赋值给stack[top]，即将x放入栈顶位置。

1.2 pop()操作：当调用pop()操作时，我们首先判断栈是否为空，即判断top的值是否为-1。

如果top等于-1，说明栈为空，无法进行pop()操作。

如果不为空，则将top的值减1，同时返回stack[top]，即弹出栈顶元素。

1.3 top()操作：top()操作与pop()操作类似，只需在操作完成后不弹出栈顶元素，而是直接返回stack[top]即可。

1.4 empty()操作：empty()操作用来判断栈是否为空，只需判断top的值是否为-1即可。

如果top等于-1，则返回true，表示栈为空；否则返回false，表示栈不为空。

综上所述，我们可以用数组实现一个栈，满足push、pop、top和empty等操作。

2. 题目描述：请实现一个队列，要求支持以下操作：push(x)将元素x入队；pop()将队首元素出队；peek()返回队首元素；empty()判断队列是否为空。

解答：我们可以使用两个栈来实现一个队列的功能。

首先定义两个栈stack1和stack2，其中stack1用来存储新加入队列的元素，stack2用来存储队列中已经处理过的元素。

定义两个整型变量top1和top2，分别表示stack1和stack2的栈顶索引位置。

初始时，top1和top2均设置为-1，表示两个栈均为空。

2.1 push(x)操作：当要将元素x入队时，我们直接将x加入到stack1中，同时将top1的值加1。

数据结构课后习题答案_(C语言版_严蔚敏)

数据结构课后习题答案_(C语言版_严蔚敏)

3
for(j=i; j<=n; j++) @ k++; } (5) for(i=1; i<=n; i++) { for(j=1; j<=i; j++) { for(k=1; k<=j; k++) @ x += delta; } (6) i=1; j=0; while(i+j<=n) { @ if(i>j) j++; else i++; } (7) x=n; y=0; // n 是不小于 1 的常数 while(x>=(y+1)*(y+1)) { @ y++; } (8) x=91; y=100; while(y>0) { @ if(x>100) { x -= 10; y--; } else x++; } 解：(1) n-1 (2) n-1 (3) n-1 (4) n+(n-1)+(n-2)+...+1=
6
for(i=0;i<k+1;i++){ if(i<k-1) p[i]=0; else p[i]=1; } for(i=k+1;i<n+1;i++){ x=p[0]; for(j=0;j<k;j++) p[j]=p[j+1]; p[k]=2*p[k-1]-x; } return p[k]; } 1.18 假设有 A，B，C，D，E 五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计 算机，并构成一张表，表中每一行的形式为 项目名称 性别 校名 成绩 得分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。 解： typedef enum{A,B,C,D,E} SchoolName; typedef enum{Female,Male} SexType; typedef struct{ char event[3]; //项目 SexType sex; SchoolName school; int score; } Component; typedef struct{ int MaleSum; //男团总分 int FemaleSum; //女团总分 int TotalSum; //团体总分 } Sum; Sum SumScore(SchoolName sn,Component a[],int n) { Sum temp; temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; int i; for(i=0;i<n;i++){ if(a[i].school==sn){ if(a[i].sex==Male) temp.MaleSum+=a[i].score; if(a[i].sex==Female) temp.FemaleSum+=a[i].score; } } temp.TotalSum=temp.MaleSum+temp.FemaleSum; return temp;
数据结构习题及参考答案

数据结构习题及参考答案

数据结构习题及参考答案一、概述在计算机科学领域，数据结构是指组织和存储数据的方式，以便于有效地访问和操作。

它是计算机算法和程序设计的基础。

下面将介绍一些常见的数据结构习题，并提供相应的参考答案，帮助读者更好地理解和掌握数据结构。

二、数组1. 习题：给定一个数组，编写一个函数来计算数组中元素的和。

【参考答案】```pythondef sum_array(arr):sum = 0for num in arr:sum += numreturn sum```三、链表1. 习题：给定一个链表，反转链表，并返回反转后的头节点。

【参考答案】```pythonclass ListNode:def __init__(self, val=0, next=None): self.val = valself.next = nextdef reverse_linked_list(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev```四、栈和队列1. 习题：使用栈实现队列的功能。

【参考答案】```pythonclass MyQueue:def __init__(self):self.stack1 = []self.stack2 = []def push(self, x):self.stack1.append(x)def pop(self):if not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2.pop()def peek(self):if not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2[-1]def empty(self):return len(self.stack1) == 0 and len(self.stack2) == 0 ```五、树1. 习题：给定一个二叉树，判断它是否是高度平衡的。

数据结构课后习题及答案

数据结构课后习题及答案

填空题（10 ＊1’ = 10' ）一、概念题2。

2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。

2。

3。

当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。

2。

6。

带头结点的单链表L中只有一个元素结点的条件是L—〉Next->Next==Null。

3。

6。

循环队列的引入,目的是为了克服假溢出.4。

2。

长度为0的字符串称为空串。

4。

5.组成串的数据元素只能是字符。

4。

8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。

7.2。

为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。

5.7。

广义表的深度是广义表中括号的重数7。

8.有向图G可拓扑排序的判别条件是有无回路。

7.9。

若要求一个稠密图的最小生成树，最好用Prim算法求解。

8。

8.直接定址法法构造的哈希函数肯定不会发生冲突。

9。

2。

排序算法所花费的时间，通常用在数据的比较和交换两大操作。

1。

1。

通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。

1。

2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。

1。

3。

存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。

1。

4。

抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变,都不影响其外部使用。

1。

5.一个算法具有五大特性:有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。

2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句:s—〉prior= p—〉prior; s-〉next= p; p-〉prior- next= s；p-〉prior= s；。

2.9。

在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空,并使得对单链表的操作（如插入和删除)在各种情况下统一。