建立一个带头结点的单向链表,并用随机函数为各结点数据域赋值。

单元练习2一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（×）（1）线性表的链式存储结构优于顺序存储。

（×）（2）链表的每个结点都恰好包含一个指针域。

（√）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

（×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。

（×）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

（×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

（√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。

（×）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

二．填空题（1）顺序表中逻辑上相邻的元素在物理位置上必须相连。

（2）线性表中结点的集合是有限的，结点间的关系是一对一关系。

（3）顺序表相对于链表的优点是：节省存储和随机存取。

（4）链表相对于顺序表的优点是：插入、删除方便。

（5）采用顺序存储结构的线性表叫顺序表。

（6）顺序表中访问任意一个结点的时间复杂度均为O(1)。

（7）链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小。

（8）在双链表中要删除已知结点*P，其时间复杂度为O(1)。

（9）在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。

（10）单链表中需知道头指针才能遍历整个链表。

（11）线性表中第一个结点没有直接前趋，称为开始结点。

（12）在一个长度为n的顺序表中删除第i个元素，要移动n-i 个元素。

（13）在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n- i +1 个元素。

c语⾔实现--带头结点单链表操作可能是顺序表研究的细致了⼀点，单链表操作⼀下⼦就实现了。

这⾥先实现带头结点的单链表操作。

⼤概有以下知识点.1;结点：结点就是单链表中研究的数据元素，结点中存储数据的部分称为数据域，存储直接后继地址的部分称为指针域。

2;结点⽰意图：3;头指针：头指针始终指向链表第⼀个元素，当有头结点时头结点就是链表第⼀个元素。

头指针具有标识左右，故头指针命名为链表的名字，这⾥为linklist。

头指针是⼀定存在的。

4;头结点：引⼊头结点的⽬的是，将链表⾸元结点的插⼊和删除操作与其他结点的插⼊和删除操作统⼀起来。

（即头指针地址不在发⽣变化）5;单链表结点结构体表⽰：1struct LNode2 {3int data; //姑且认为其数据为整型4struct LNode * next;5 };67 typedef struct LNode * linklist6;单链表的操作集合，头⽂件 defs.h1 #ifndef _DEFS_H_2#define _DEFS_H_34 #include<stdio.h>5 #include<stdlib.h>6 #include<malloc.h>78struct LNode //单链表结点的定义9 {10int data;11struct LNode * next;12 }13 typedef struct LNode * linklist1415//操作集合16void InitList(linklist *L); //申请头结点，头指针地址改变17void DestroyList(linklist *L); //须释放头结点，头指针地址改变18void ClearList(linklist L); //保留头结点，头指针地址不变19void ListEmpty(linklist L);20int ListLength(linklist L);21int GetElem(linklist L, int i, int *e);22int LocateElem(linklist L, int e);23int PriorElem(linklist L, int cur_e, int *pri_e);24int NextElem(linklist L, int cur_e, int *nex_e);25int ListInsert(linklist L, int i, int e); //插⼊不改变头指针的值26int ListDelete(linklist L, int i, int *e); //删除操作也不改变头指针的值27void TravelList(linklist L);28#endif7;InitList操作实现1 #include"defs.h"23void InitList(linklist *L) //接受头指针的地址值4 {5 *L = (linklist)malloc(sizeof(struct LNode)); //*L表⽰头指针67if (*L == NULL)8 {9 printf("分配结点失败。

选择题：1．若有如下结构体定义：struct example{int x;int y;}v1;则（）是正确的引用或定义。

A．example.x=10 B．example v2;v2.x=10;C．struct v2;v2.x=10; D．struct example v2={10};2.下述程序的执行结果是（）。

#include <stdio.h>union un{int i;char c[2];}main(){union un x;x.c[0]=10;x.c[1]=1;printf(“\n%d”,x.i);}A.266B.11C.265D.1383.根据以下定义能输出字母M的语句是（）。

struct person{char name[9];int age;};struct person class[10]={“Jphn”,17,”Paul”,19,”Mary”,18,”Adam‟,16}; A.printf(“%c\n”,class[3].name); B.printf(“%c\n”,class[3].name[1]);C.print(“%c\n”,class[2].name[1])D.print(“%c\n”,class[2].name[0]);4.以下程序的输出是（）。

#include <stdio.h>main(){struct cmplx{int x;int y;}cnum[2]={1,3,2,7};printf(“%d\n”,cnum[0].y/cnum[0].x*cnum[1].x);}A.0B.1C.3D. 65.已知字符0的ASCII代码值的十进制数是48，以下程序：#include <stdio.h>main(){union {int i[2];long k;char c[4];}r,*s=&r;s->i[0]=0x39;s->i[1]=0x38;printf(“%x\n”,s->c[0]);}其输出结果是（）。

数据结构习题习题一一、选择题1、算法分析的两个主要方面是：（）A．正确性和简明性B．时间复杂度和空间复杂度C．数据复杂性和程序复杂性D．可读性和文档性2、在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．逻辑结构和存储结构3、计算机算法具备输入、输出和（）等5个特性：A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性4、算法分析的目的是（）。

A．找出算法的合理性 B．研究算法的输人与输出关系C．分析算法的有效性以求改进 D．分析算法的易懂性二、填空题1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系，图形结构中元素之间存在的关系。

3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。

例如构成一个数据元素的字段、域、属性等都可称之为________。

4、数据的________指数据元素及其关系在计算机存储器内的表示。

_________是逻辑结构在计算机里的实现，也称之为映像。

5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。

三、问答题1、用大O形式写出下面算法的时间复杂度：i＝0；s=0；while(s＜n）｛ i++;s+=i; ｝2、写出以下算法的时间复杂度：for（i＝0; i＜m; i＋＋）for（j＝0 ; j＜t; j＋＋）c[i][j]=0；for（i=0；i＜m；i＋＋）for（j=o; j<t; j++）for（k=0；k＜n；k＋＋）c［i］［j］＋＝a［i］［k］*b[k][j];习题二一、选择题1．在一个长度为n的顺序表中删除第i个元素（0＜i<n）时，需要向前移动( )个元素。

下列给定程序中函数fun()的功能是计算1/n!的值。

例如：给n输入5，则输出0.008333。

请改正程序中的错误，使它能得到正确结果。

（1）错误：int fun(int n)正确：double fun(int n)（2）错误：result *=n++ ;正确：result *=n-- ; 2. 改错题下列给定程序中函数fun()的功能是计算正整数num的各位上的数字之平方和。

（1）错误：long k=1;正确：long k=0;（2）错误：while(num)正确：while(num);下列给定程序中，函数fun()的功能是将字符串s中位于偶数位置的字符或ASCII码为奇数的字符放入字符串t中(规定第一个字符放在第0位中)。

（1）错误： void fun(char s, char t[ ])正确：void fun(char *s, char t[ ])（2）错误： if(i%2=0||s[i]%2!=0)正确：if(i%2==0||s[i]%2!=0)下列给定程序中，函数fun()的功能是找出100～n(不大于1000)之间百位数字加十位数字等于个位数字的所有整数，把这些整数放在s所指的数组中，个数作为函数值返回。

（1）错误：k=n; 正确：k=i;（2）错误：s[j]=i;正确：s[j++]=i;下列给定程序中，函数fun()的功能是求出数组中最小数和次最小数，并把最小数和a[0]中的数对调，次最小数和a[1]中的数对调.1）错误： for(i=0; i<n; i++)正确：for(i=0; i<2; i++)（2）错误：k=m;正确：m=k;下列给定程序中，函数fun()的功能是计算并输出high以内的素数之和。

high由主函数传给fun()函数。

若high的值为100，则函数的值为1060。

（1）错误：ifhigh%j==0正确：if（high%j==0）（2）错误：if(yes==0)正确：if(yes)下列给定程序中，函数fun()的功能是：读入一个字符串(长度<20)，将该字符串中的所有字符按ASCII码降序排序后输出。

数据结构（本）期末综合练习国家开放大学2020年7月《1252本科数据结构（本）》期末考试复习题及答案一、单项选择题1．数据的物理结构（ D）。

A．与数据的逻辑结构无关 B．仅仅包括数据元素的表示C．只包括数据元素间关系的表示 D．包括数据元素的表示和关系的表示2．数据元素是数据的基本单位，它（C ）。

A．只能有一个数据项组成B．至少有二个数据项组成C．可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型3．从n个数中选取最大元素，（ C ）。

A．基本操作是数据元素间的交换B．算法的时间复杂度是O(n2)C．算法的时间复杂度是O(n) D．需要进行(n+1)次数据元素间的比较4．线性表的顺序结构中，（ C ）。

A．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的C．逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高5．以下表中可以随机访问的是（ D ）。

A．单向链表 B．双向链表C．单向循环链表D．顺序表6．带头结点的单向链表为空的判断条件是（ B ）（设头指针为head）。

A．head = =NULL B．head->next= =NULLC．head->next= =head D．head!=NULL7 .设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（ A ）。

A．(n+1)/2 B．n C．2n D．n-i8．线性结构中数据元素的位置之间存在（A ）的关系。

A．一对一B．一对多C．多对多D．每一个元素都有一个直接前驱和一个直接后继9．设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收栈顶元素，则出栈操作为（A ）。

A．x=top->data;top=top->next; B．top=top->next;x=top->data;C．x=top-> next;top=top-> data; D．top->next =top; x=top->data;10．设顺序存储的线性表长度为n，要删除第i个元素，按课本的算法，当i=（ C ）时，移动元素的次数为3 A．3 B．n/2 C．n-3 D．411．以下说法正确的是（ C ）。

全国计算机等级考试C 语言――改错题1．给定程序中fun 函数的功能是：根据整型形参m 的值，计算如下公式的值：m*m 1......3*312*211t ----= 例如，若m 中的值为5，则应输出0.536389。

double fun(int m){ double y=1.0；int i ；/**************found**************/for(i=2；i<m ；i++) 改为：for(i=2；i<=m ；i++)/**************found**************/y-=1/(i*i)； 改为：y-=1.0/(i*i)；return(y)；}main( ){ int n=5；printf("\nThe result is %lf\n"，fun(n))；}2．程序中fun 函数功能是：将s 字符串的正序和反序进行连接，形成一个新字符串放在t 数组中。

例如，当 s 所指字符串为“ABCD”时，则t 所指字符串的内容应为“ABCDDCBA”。

/************found************/void fun (char s ，char t) 改为：void fun (char *s ，char *t){ int i ，d ；d=strlen(s)；for (i=0；i<d ；i++) t[i]=s[i]；for (i=0；i<d ；i++) t[d+i]=s[d-1-i]；/************found************/t[2*d-1]='\0'； } 改为：t[2*d]='\0'；main( ){ char s[100]，t[100]；printf("\nPlease enter string S:")；scanf("%s"，s)；fun(s ，t)；printf("\nThe result is: %s\n"，t)； }3．给定程序中fun 函数的功能是：将s 所指字符串中位于奇数位置的字符或ASCII 码为偶数的字符放入t 所指数组中(规定第一个字符放在第0位中)。

第二章习题参考答案一、判断题1．线性表的逻辑顺序与存储顺序总是一致的。

(ERROR)2．顺序存储的线性表可以按序号随机存取。

(OK)3．顺序表的插入和删除一个数据元素，因为每次操作平均只有近一半的元素需要移动。

（OK）4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

（OK）5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

（ERROR）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

（OK）7．线性表的链式存储结构优于顺序存储结构。

（ERROR）8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

（OK）9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

（OK）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

（ERROR）二、单选题、 (请从下列A，B，C，D选项中选择一项)11．线性表是( A ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（A）个元素。

(A) n/2 (B) (n+1)/2 (C) (n –1)/2 (D) n13．线性表采用链式存储时，其地址( D ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

14．用链表表示线性表的优点是（C ）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同15.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。

第一套、1程序填空给定程序中，函数fun的功能是：有N*N矩阵，将矩阵的外围元素顺时针旋转。

操作顺序是：首先将第一行元素的值存入临时数组r ,然后使第一列成为第一行，最后一行成为第一列，最后一列成为第一行，临时数组中和元素成为最后一列。

第1处t[0][N-j-1]=t[j][0];第2处for(j=N-1;j>=0;j--)第3处t[j][N-1]=r[j];2程序修改给定程序MODI1.C中函数fun的功能是：计算s=f(-n)+f(-n+1)+……+f(0)+f(1)+f(2)+……+f(n)的值。

例如，当n为5时，函数值应为：10.407143。

/*******found******/double f(double x){if(x==0.0||x==2.0)return 0.0;else if(x<0.0)return (x-1)/(x-2);elsereturn (x+1)/(x+2);}double fun(int n){ int i;double s=0.0,y;for(i=-n;i<=n;i++){ y=f(1.0*i);s+=y;}/*******found******/return s;}3程序设计编写函数fun，它的功能是计算：s=根号下(ln(1)+ln(2)+ln(3)+……ln(m))S作为函数返回，在C语言中可调用log(n)函数求ln(n)。

log函数的引用说明是：Double log(double x)例如，若m 的值为：20，fun函数值为：6.506583。

double fun(int m){double s=0.0;int i;for(i=0;i<=m;i++)s+=log(1.0*i);s=sqrt(s);return s;}第二套程序通过定义学生结构体变量，存储了学生学号，姓名和3门课的成绩。

所有学生数据均以二进制方式输出到文件中。

二、程序修改题1.给定程序MODI1.C中函数fun的功能是：计算n!。

2.给定程序MODI1.C中函数fun的功能是：依次取出字符串中所有数字字符，形成新的字符串，并取代原字符串。

3.给定程序MODI1.C中的函数Creatlink的功能是创建带头结点的单向链表，并为各结点数据域赋0到m-1的值。

4.给定程序MODI1.C中函数fun的功能是：在字符串的最前端加入n个*号，形成新串，并且覆盖原串。

5.给定程序MODI1.C中函数fun的功能是：对N名学生的学习成绩，按从高到低的顺序找出前m（m<=10）名学生来，并将这些学生数据放在一个动态分配的连续存储区中，此存储区的首地址作为函数值返回。

6.给定程序MODI1.C中函数fun的功能是：比较两个字符串，将长的那个字符串的首地址作为函数值返回。

#include <stdio.h>7.给定程序MODI1.C中函数fun的功能是：求出数组中最大数和次最大数，并把最大数和a[0]中的数对调，次最大数和a[1]中的数对调。

8.给定程序MODI1.C中函数fun的功能是：求k!（k<13），所求阶乘的值作为函数值返回。

例如：若k=10，则应输出：3628800。

9.给定程序MODI1.C中函数fun的功能是：将s所指字符串中的字母转换为按字母序列的后续字母（但Z转换为A，z转换为a），其它字符不变。

10.给定程序MODI1.C中函数fun的功能是：根据整型形参m，计算如下公式的值：11.给定程序MODI1.C中函数fun的功能是：计算s所指字符串中含有t所指字符串的数目，并作为函数值返回。

12.给定程序MODI1.C中函数fun的功能是：将s所指字符串中位于奇数位置的字符或ASCII 码为偶数的字符放入t所指数组中（规定第一个字符放在第0位中）。

13.给定程序MODI1.C是建立一个带头结点的单向链表，并用随机函数为各结点数据域赋值。