搜索
1数据结构作业（一）班级姓名学号一、填空题1.数据结构按逻辑结构可分为两大类，他们分别是和，其中___________分为____________、___________和___________三种。2.数据的存储结构被分为___________、____________、___________和___________四种。常用的两种存储方法为和。3.数据结构研究内容包括数据的、数据的和数据的这三方面的内容。4.数据元素是数据的_____________单位。是数据不可分割的最小单位。5.一个算法的效率可分为效率和效率。6.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为。7.按顺序存储方式存储的线性表称为，按链式存储方法存储的线性表称为；若经常要对线性表进行插入和删除运算，则最好采用存储结构，若经常要对线性表进行查找运算，则最好采用存储结构。8.在长度为n的顺序存储的线性表中，删除第i（1=i=n）个元素时，需向前移动个元素；在表的第i（1=i=n+1）号位置上插入新结点，需向后移动________个元素。9.头指针为H的带头结点的单链表和循环单链表，则空表的判定条件分别是________和；头指针为H的不带头结点的单链表和循环单链表，则空表的判定条件分别是________和；在头指针为L的循环链表中，结点的指针为P，P所指的结点为尾结点的条件是。10.链表适合存取，而顺序表更适合存取。二、选择题1．已知n为问题规模，则下面程序段的时间复杂度为。for(i=0;i=n-1;i++)for(j=i+1;j=n-1;j++)s++;A.O(1)B.O(n)C.O(n2)D.O(log2n)2．下列时间复杂度最好的是；最差的是。A.O(2n)B.O(log2n)C.O(n)D.O(n2)3．一个存储结点存放一个。A.数据项B.数据元素C.数据结构D.数据类型4．线性表若采用顺序存储结构时，要求内存中可用存储单元的地址；若采用链式存储结构时，要求内存中可用存储单元的地址。A.必须连续B.部分地址必须连续C.一定是不连续的D.连续或不连续都可以5．线性表的长度是。A.顺序存储方式下数组占用的存储空间的大小B.表中的数据元素的个数C.链式存储方式下所有结点占用的存储空间的大小D.所能存储的最大结点的个数26．链表中设头结点的目的是为了。A.标识单链表B.方便运算的实现C.使链表中至少有一个结点D.标识起始结点的位置7．设H是带表头结点循环单向链表的表头指针。当这种链表成为空链表时，。A.表头结点指针域的值为空B.H的值为空C.表头结点指针域的值与H的值相等D.表头结点指针域的值与H的地址相等8．在程序中，为了设置一个空的顺序表，必须。A.给各数组元素赋空值B.给各顺序表元素赋空值C.给表示顺序表长度的变量赋零值D.给数组变量名赋初始值9．若某线性表最常用的操作是取第i个元素和查找第i个元素的直接前躯，则采用存储方式最节省时间。A.单链表B.双链表C.循环单链表D.顺序表10．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表11．在一个表头指针为L的单链表中，若要在指针q所指结点个后面插入一个由指针p所指向的结点，则执行操作。A.q-next=p-next;p=q;B.q-next=p-next;p-next=q;C.p-next=q-next;q=p;D.p-next=q-next;q-next=p;12．在一个表头指针为L的单链表中，若要删除由指针q所指向结点的后继结点（若存在的话），则至少执行操作。A.p=q-next;p-next=q-next;B.p=q-next;q-next=p-next;C.p=q-next;q-next=p;D.q-next=q-next-next;q-next=q;13．在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q指针所指向的结点，则需要对p-prior-next赋值为。A.qB.pC.p-nextD.p-prior14．在一个带头结点的循环双向链表中，若要删除指针p所指向的结点，则执行操作。A.p-prior-next=p-next;p-next-prior=p-prior;B.p-next-prior=p;p-next=p-next-next;C.p-prior-next=p;p-next=p-next-prior;D.p=p-next;p-prior-next=p-prior;15．已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为Da1,则第i个结点的地址为。A.Da1+（i-1）*mB.Da1+i*mC.Da1-i*mD.Da1+（i+1）*m三、阅读程序1、已知head为不带表头结点的单链表的头指针，链表结构如图所示：typedefstructnode{intn;headstructnode*next;1645^}Lnode,*LinkList;3算法一：LinkListex1(LinkListhead){LinkListu,v,r;if(!head)returnhead;u=NULL;v=head;r=v-next;while(v){v-next=u;u=v;v=r;if(r!=NULL)r=r-next;}returnu;}问，如执行head=ex1(head);之后，画出head所示的链表结构示意图。算法二：LinkListex2(LinkListhead){LinkListp,q,r;q=(LinkList)malloc(sizeof(Lnode));q-next=head;head=q;p=head-next;while(p){if(p-n%3==1){q-next=p-next;r=p;p=p-next;free(r);continue;}q=p;p=p-next;}r=head;head=head-next;free(r);returnhead;}问，如执行head=ex2(head);之后，画出head所示的链表结构示意图。2、设整数3、2、-5、7、-9、4依次存储在循环单链表L中，如图所示：试对L执行下面算法，画出执行算法后L的结构示意图。L32-57-94typedefstructnode{intdata;structnode*next;结构示意图：}LNode,*LinkList;voidex3(LinkListL){LinkListp=L;while(p-next!=L){q=p-next;if(p-dataq-data){t=p-data;p-data=q-data;q-data=t;}p=q;}}4四、算法设计题1、已知一个顺序表L，设计一个将表中元素进行倒置的算法函数voidreverse(SeqList*L)，即把原表{a1,a2,...,an}倒置后变成{an,an-1,...,a1}。直接在原表上倒置。顺序表数据类型定义为：typedefstruct{datatypedata[MAX];intlast;/*顺序表长度*/}Seqlist;2、已知一个带头结点的单链表头指针为head，数据域的值为整数，数据类型定义如下：typedefstructnode{intdata;structnode*next;}Lnode,*LinkList;设计一个函数voiddelete(LinkListhead)，将表中所有奇数值的结点删除。