自考计算机网络数据结构模拟试卷二

假设以带头结点的单链表表示有序表,单链表的类型定义如下:

typedef struct node{

DataType data;

struct node next

)LinkNode, LinkList;

编写算法,从有序表A中删除所有和有序表B中元素相同的结点。

下面的算法是用冒泡排序法完成对文件中各个记录按关键字递增次序排序,请仔细阅读程序并把未完成的部分填上。

void bubblesort (SeqList R)

{

int i,;

Boolean exchange;

for (i-1:i

{

exchange-false;

for (j=n-1;j (1)

if(R[+1]. key

{

R[o]=R[j+1];

R[j+1]= (2) ;

(3) =R[0];

exchange=true;

}

if(!exchange)

(4)

}

}

(1)

(2)

(3)

(4)

阅读下列函数F并回答问题

(1)已知如题图所示的二叉树以二叉链表作存储结构rt为指向根结点的指针写出执行函数调用F(rt)的输出结果。

(2)说明函数F的功能题图

void(BinTreeT)

StackS;

if(T)

{

InitStack(&.S);

Push(&S,NULL);

while(T)

{

printf("%c",T->data);

if(T->rchild)Push(&.S,T->rchild);

f(T->Ichild)T=T->lchild;

elseT=Pop(&.S);

}

}

(1)

(2)

算法 MergeList的功能是归并两个有序链表La和b为有序链表Lc。请在空缺处填入合适的内容,使其成为一个完整的算法。

LinkList MergeList(LinkList La, LinkList Lb)

{ }//归并两个有序链表La和Lb为有序链表Lc

ListNode *pa, pb,; LinkList Lc;

pa=la->next;pb=lb->next;//pa和pb分别指向两个链表的开始结点

Le==La;//用La的头结点作为Lc的头结点

while(pa! =NULL&.&.pb! =NULL)

pe->next=pa; pe-pa;pa=pa->next;

}

else{

pe->next-pb: (1) spb=pb->next;

}

}

p->next-pa!-null?(2):pb;//插入链表剩余部分

(3) ;//释放Lb的头结点

return Lc;//返回合并后的表

}

(1)

(2)

(3)

已知用有序链表存储整数集合的元素。阅读算法f30,并回答下列问题:

(1)写出执行f30(a,b)的返回值,其中a和b分别为指向存储集合{2,4,5,7,9,12}和{2,4,5,7,9}的链表的头指针。

(2)简述算法f30的功能。

(3)写出算法f30的时间复杂度。

int f30(LinkList ha, LinkList hb)

{

//LinkList//是带有头结点的单链表

//ha和hb分别为指向存储两个有序整数集合的链表的头指针

LinkList pa,pb;

pa=ha->next;

pb=hb->next;

while(pa & pb & pa->data==pb->data)

pa-pa->next;

pb=pb→next;

}

if(==NULL &.& pb= =NULL) return 1;

else return 0;

}

(1)

(2)

(3)

画出下列广义表的图形表示:

(1)A=(a,(b,c))

(2)B=(a,d)=((a,(b,c)),d)

画出下面两个广义表的图形表示:

(1)A=()

(2)B=(a,(b,c))

分别写出删除单向循环链表和双向循环链表中指针p所指的结点的直接后继结点(非尾结点)的对应语句。

画出题图所示的树对应的二叉树。

顺序表中逻辑上相邻的元素在物理存储位置上相邻,链表结构中逻辑上相邻的

散列存储中使用的函数H(key)称为( ),它实现关键字到存储地址的映射。

广义表((a))的表头是_( )表尾是( )

在线性表上进行查找的方法有顺序查找、( )和分块查找。

数据的链式存储结构的特点是借助( )表示数据元素之间的逻辑关系。

栈是限定在表的一端进行插入和删除运算的线性表,通常将这一端称为( )

( )是一个值的集合以及在这些值上定义的一组操作的总称

对顺序表执行插入操作,其插算法的平均时间复杂度为( )

( )是连通图的包含图中所有顶点的一个极小连通子图。

有一个有序表{1,3,9,12,32,41,45,62,75,7782,95,100},当用二分查找法查找值为82的结点时,经【】次比较后查找成功

下列四个说法中正确的是【】

有一个100×90的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是( )

在下列排序方法中,记录关键字比较的次数与记录的初始排列次序无关的方法是【】

进序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为【】

下列程序的时间复杂度为【】

i=0;

s=0;

while(s{i++;s=s+i;}

下述编码中不是前缀码的是【】

对n个关键字进行快速排序,最大的递归深度是【】

单链表不具有的特点是【】                            

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用哪种存储方式最节省时间【】

【】不是栈的基本运算。

线性表采用链表作为存储结构时,通常会另外附加一个头结点,这样做的好处是【】

有六个元素按6,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列【】

数据结构研究的是数据的【】及它们之间的相互关系。

下列排序算法中,某一趟结束后未必能选出一个元素放其最终位置上的是【】

若图G为n个顶点的有向图,则图G中最多有多少条边【】