数据结构与算法离线作业.doc

文档介绍：浙江大学远程教育学院
《数据结构与算法》课程离线作业
姓名:
学号:
年级:
学习中心:
—————————————————————————————
一、填空题:(【序号,章,节】)
【1,1,2】线性结构中元素之间存在一对一关系,树形结构中元素之间存在
一对多关系,图形结构中元素之间存在多对多关系。
【2,1,2】为了最快地存取数据元素,物理结构宜采用顺序存储结构。
【3,1,2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构__, 链式存储结构___。
【4,1,3】度量算法效率可通过时间复杂度__来进行。
【5,1,3】设n 为正整数,下面程序段中前置以记号@的语句的频度是 n(n+1)/2 。
for (i=0; i<n; i++){
for (j=0; j<n; j++)
if (i+j==n-1)
@ a[i][j]=0;
}
【6,1,3】设n 为正整数,试确定下列各程序段中前置以记号@的语句的频度:
(1) i=1; k=0;
while (i<=n-1){
i++;
@ k+=10 * i; // 语句的频度是___n-1____。
}
(2) k=0;
for (i=1; i<=n; i++){
for (j=i; j<=n; j++)
@ k++; // 语句的频度是 n(n+1)/2 。
}
【7,3,2】线性表(a1,a2,…,an)有两种存储结构: 顺序存储结构和链式存储结构,请就这两种存储结构完成下列填充: _顺序__ 存储密度较大;_顺序___存储利用率较高;_顺序___可以随机存取;__链式____不可以随机存取;__链式___插入和删除操作比较方便。
【8,3,2】从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动 n-i 个元素。
【9,3,2】带头结点的单链表Head为空的条件是 Head->next=NULL __ 。
【10,3,2】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点,应执行s->next=__ p->next ___;和p->next=___ s_____的操作。
【11,3,2】在一个单链表中删除p所指结点时,应执行以下操作:
q= p->next;
p->data= p->next->data;
p->next= p->next->next __ ;
free(q);
【12,3,2】带头结点的单循环链表Head的判空条件是_ Head->next == Head;___; 不带头结点的单循环链表的判空条件是__ Head == NULL; ___。
【13,3,2】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a. 删除P结点的直接前驱结点的语句序列是________10 12 8 11 4 14 ______。
b. 删除结点P的语句序列是_____________10 12 7 3 14_____________。
c. 删除尾元结点的语句序列是_____________9 11 3 14______。
(1) P = P->next;
(2) P->next = P;
(3) P->next = P->next ->next;
(4) P = P->next ->next;
(5) while (P != NULL) P = P->next;
(6) while (Q->next != NULL){P = Q; Q = Q->next};
(7) while (P->next != Q) P = P->next;
(8) while (P->next->next != Q) P = P->next;
(9) while (P->next->next != NULL) P = P->next;
(10) Q = P;
(11) Q = P->next;
(12) P = L;
(13) L = L->next;
(14) free (Q);
【14,3,3】对一个栈,给定输入的顺序是A、B、C,则全部不可能的输出序列有不可能得到的输出序列有CAB 。
【15,3,3】.在栈顶指针为HS的链栈中,判定栈空的条件是 head->next==NULL 。
【16,3,3】下列程序把十进制数转换为十六进制数,请填写合适的语句成分。
void conversion10_16()
{ InitStack(&s);
scanf(“%d”,&N);
while(N){
___