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

浙江大学远程教育学院

《数据构造与算法》課程离线作业

—————————————————————————————

一、填空題：（【序号，章，节】。。。。。。）

【1，1，2】线性构造中元素之间存在一对一关系，树形构造中元素之间存在

一对多关系，图形构造中元素之间存在多对多关系。

【2，1，2】為了最快地存取数据元素，物理构造宜采用次序存储构造。

【3，1，2】存储构造可根据数据元素在机器中的位置与否一定持续分為次序存储构造_，链式存储构造_。

【4，1，3】度量算法效率可通过時间复杂度_来进行。

【5，1，3】设n為正整数，下面程序段中前置以记号@的語句的频度是n(n+1)/2。

for(i=0;in;i++){

for(j=0;jn;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結点的直接前驱結点的語句序列是___1012811414____。

b.删除結点P的語句序列是____10127314____。

c.删除尾元結点的語句序列是___911314___。

(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】下列程序把十进制数转换為十六进制数，請填写合适的語句成分。

voidconversion10_16()

{InitStack(s);

scanf(“%d”,N);

while(N){

______P