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

尾插法建表是将新结点插入到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。试写出尾插法建表的算法。函数头为:LinkListGreateListR(void)

已知稀疏矩阵采用带行表的三元组表表示,其形式说明如下:

define MaxRow 100 //稀疏矩阵的最大行数

typedef struct

int i,j,v; //行号、列号、元素值

}TriTupleNode;

typedef struct{

TriTupleNode data[MaxSize];

int RowTab[MaxRow+1];//行表

int m,n,t: //矩阵的行数、列数和非零元素个数

}RTriTupleTable;

下列算法f31的功能是:以行优先的顺序输入稀疏矩阵的非零元素(行号、列号、元素值),

建立稀疏矩阵的带行表的三元组表存储结构请在空缺处填合适内容,使其成为一个完

整的算法。(注:矩阵的行、列下标均从1起计)

void f31(RTriTupleTable *R)

{int i,k;

scanf("%d %d %d", & R->m, R->n, &R->t);

R→RowTab[1]=0;

k=1;//k指示当前输人的非零元素的行号

for(i=0:(1)i++)

{scanf("% %d %d", (2) , (3) ,&R->data[i]. v);

while(kdata[i]. i)

{ (4)

R->RowTab[k]=i

}

}

}

(1)

(2)

(3)

(4)

设输入为整数数组a[n],a[n],其中≤a[i

void demo(int a[], int b], int c[], int k)

{

int i,

for(i=0;i

for(j=0:j

for(i=: i

for(j=n-1>=0--)

{

b[c[a[j]]-1]=a[j]:

c[a[j]]—

}

(1)当标号①行的循环执行完后,c[i(0≤i

(2)当标号②行的循环执行完后,c[i(≤i

(3)算法执行后,b数组的内容有何特点?

(4)当k=0(n)时,算法的时间复杂度是多少?

(1)

(2)

(3)

(4)

下列程序段search(a,n,k)是在数组a的前n(n>=1个元素中找出第k(1的值。这里假设数组a中各元素的值都不相同,在空缺处填写相应的语句

#define MAXN 100

int a[MAXN],n, k;

int search(int],int n, int k)

(int low, high,i,j,m,t;

k--,low=0;high=n-11

do {i-low;j-high ;t-aClow],

do{while(i

if(i<) a[i++]=];

while(i=[]) i++:

if(i

}while(i

a[i]-t:

if (1)

if(i

}while( (4) );

return(a[k]);

}

(1)

(2)

(3)

(4)

下面是二分查找算法的非递归实现方法,在空缺处填入合适内容,使其成为一个完整的算法。

int BinSearch(SeqList R, KeyType k, int n)

{int low=, mid, high=n;//初始化上下界

while(low<=high){

mid=(low+high)/2;

if(R[mid]. key==k)

return mid,//查找成功,返回其下标

if(R[mid]. key>k)

(1) ;//修改上界

Else (2) ;//修改下界

}

Return0;//查找失败,返回0值

}

(1)

(2)

画出题图所示二叉树的中序线索链表的存储表示。

已知3阶B树如题图所示。

(1)画出将关键字88插入之后的B树。

(2)画出将关键字47和66依次插入之后的B树。

设散列表长度为11,散列函数h(x)=x%1,给定的关键字序列为:1,12,13,34,38,33,27,22,试画出用拉链法解决冲突时所构造的散列表。

假设二叉树包含的结点为1,3,7,2,12

(1)画出两棵高度最大的二叉树

(2)画出两棵完全二叉树,要求每个双亲结点的值大于其孩子结点的值。

在一般情况下用直接插入排序、直接选择排序和冒泡排序的过程中,所需移动记录次数最少的是( )

a=(x,a,b,c,d),函数 head headtail()的运算结果是( )

G是一个非连通无向图,共有28条边,则该图至少有( )个顶点。

待排序记录的存储方式一般有三种:顺序结构、( )和辅助表形式。

深度为k的二叉树至多有( )个结点(k≥1)

常用的解决冲突的方法有两大类,即开放定址法和( )

按中序遍历二叉排序树所得到的中序序列是一个( )有序序列。

邻接表是图的一种( )存储结构

具有10个顶点的无向图,边的总数最多为( )

在双链表中间插入一个结点,需要修改_( )个指针域。

设数组A[m]为循环队列Q的存储空间, front为队头指针,rear为队尾指针,采用少用一个元素空间的方法来解决队空和队满的判定问题则判定Q为空队列的条件是【】

线索二叉树中的线索是指【】

对下图所示的无向图,从顶点1开始进行深度优先遍历,可以得到的顶点访问序列为【】

一个队列的输入序列是abcd,则队列的输出序列是【】

在头指针为head且表长大于1的单循环链表中,指针p指向表中某个结点,若next-next=head,则【】

下列关键字序列中,构成小根堆的是【】

删除双向链表中间某个结点,需要修改【】个指针域。

已知有向图G=(V,E),其中V={v,v2,a,4,vg,v,v},e={v,>,,,,,G}的拓扑序列是【】

最不适合用作链队的链表是【】

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

s=0;for(i=0;

ifor(j=0;

js=s+a[i][j];

二维数组a的每个元素是由6个字符组成的串,行下标的范围从0到8,列下标的范围从1到10,则存放a至少需要【】个字符。

如果将矩阵Anx的每一列看成一个子表,整个矩阵看成是一个广义表L,即L=((a1a21,,an1),(a1,22,an2),…,(a1na2n,am)),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素,则求得a12的运算是【】

在计算机的存储结构中,逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里,称之为【】

下列排序方法中,最好与最坏时间复杂度不相同的排序方法是【】

用单链表方式存储的线性表,存储每个结点需要两个域,一个是数据域,另一个是【】