《数据结构》试卷四含答案

《数据结构》试卷四

一、选择题（本题共20分，每小题1分）

1.在数据结构中，从逻辑上可以把数据结构分成（）。

A.动态结构和静态结构B.紧凑结构和非紧凑结构

C.线性结构和非线性结构D.内部结构和外部结构

2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

A.必须是连续的B.部分地址必须是连续的

C.一定是不连续的D.连续不连续都可以

3.不带头结点的单链表head为空的判定条件是（）。

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

4.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间

插入S结点，则执行（）。

A.s-next=p-next;p-next=s;B.p->next=s->next;s-next=p;

C.q->next=s;s->next=p;D.p-next=s;s->next=q;

5.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需

平均比较（）个结点。

A.nB.n/2

C.(n-l)/2D.(n+l)/2

6.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（)o

A.edcbaB.decbaC.dceabD.abcde

7.判定一个循环队列QU（最多元素为m0)为满队列的条件是（

A.QU->front==QU->rearB.QU->front!=QU->rear

C.QU->front==(QU->rear+l)%mOD.QU->front!=(QU->rear+l)%mO

8.栈和队列的共同点是（)

A.都是先进后出B.都是先进先出

C.只允许在端点处插入和删除元素D.没有共同点

9.数组A中，每个元素A的长度为3个字节，行下标i从1到8,列下标j从1至也0,

从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为

()o

A.SA+141B.SA+144

C.SA+222D.SA+225

10.广义表((a,b),c,d)的表尾是()o

A.aB.b

C.(a,b)D.(c,d)

11.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序

存放在一维数组B[l,n（n-l）/2]中,对下三角部分中任一元素ai,j（i»j）,在一维数

组B的下标位置k的值是（

A.i(i-l)/2+j-lB.i(i-l)/2+j

C.i(i+l)/2+j-lD.i(i+l)/2+j

au

aa

A2l22

13.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历

序列是（）。

A.acbedB.decabC.deabcD.cedba

14.按照二叉树的定义，具有3个结点的二叉树有（）种。

A.3B.4

C.5D.6

15.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含

的结点数至少为（）。

A.2hB.2h-l

C.2h+lD.h+1

16.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A.1/2B.1C.2D.4

17.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。

A.nB.n+1

C.n-lD.n/2

18.已知一有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算法，从

顶点vl出发，所得到的顶点序列是（)o

►24

।「I+「口

A.vl,v2,v3,v5,v4B.vl,v2,v3,v4,v5

C.vl,v3,v4,v5,v2D.vl,v4,v3,v5,v2

19.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为

()o

A.nB.n/2

C.(n+1)/2D.(n-l)/2

20.快速排序方法在（）情况下最不利于发挥其长处。

A.要排序的数据量太大B.要排序的数据中含有多个相同值

C.要排序的数据已基本有序D.要排序的数据个数为奇数

二、填空题（本题共20分，每空1分）

1.根据数据元素之间的不同特征，通常有四类基本结构:一和

2.下面程序段的时间复杂度是:

for(i=0；i<n；i++)

for(j=0；j<m；j++)

A[i][j]=0；

3.向一个长度为n的线性表中的第i个元素(iWiWn)之前插入一个元素时，需向

后移动个元素。

4.在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：

(1)s->next=;

(2)p-next=s;

(3)t=p->data;

(4)p->data=;

(5)s->data=;

5.深度为k的完全二叉树至少有一个结点，至多有一个结点，若按自上而下，从

左到右次序给结点编号(从1开始)，则编号最小的叶子结点的编号是—o

6.一个广义表为(a,(a,b),d,e,((i,j),k)),则该广义表的深度为。

7.有一棵树如下图所示，回答下面的问题：结点k3的度是—；这棵树的度为—；

这棵树的深度是—o

8.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时，当把第

七个记录60插入到有序表时，为寻找插入位置需比较次。

9.队列的插入操作在_____进行，删除操作在_______进行。

10.判定一个有向图中是否存在回路，即是否含有环，可以使用方法。

三、阅读程序写结果(本题共20分，每小题5分)

1.单链表中，指针P指向某结点，执行以下操作后，请用一句话描述程序执行的结

果是什么？

q=p->next;

p->data=p->next->data;

p->next=p->next->next;

free(q);

2.阅读下面二分查找程序代码，填充空白位置，使算法完整。

intBinSearch(SeqListR,KeyTypek)

{intlow=l,high=n,mid;

while(low〈二high)

{mid=(low+high)/2;

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

if(R[mid].key>k)①;

else②;}

return0;

3.如下图所示给出了图G及对应的邻接表，根据给定的dfs算法，从顶点8出

发，写出其搜索序列。

Adjlistgl;

voiddfs(intv)

{structvexnode*p;

printf(zz%d，z,v);

visited[v]=l;

P=gl[v]->link;/*gl是该图的邻接表的表头指针数组*/

while(p!=NULL)

{if(visited[p->adjvex]==O)dfs(p->adjvex);

p=p->next;}

)

二一03->03

2二fI“，I44引El

3二HZQHIQ-dZI

4二7G「4~H81T

6二一HJHZQ

7二.卜|4[m

8乎EBHZH^ZmZEl

4.二叉树采用二叉链表存储结构，将第四题综合题3中的二叉树，运行下面的递归

算法，请写出最后的返回结果是什么？

intcount(btree*b)

{intnuml,num2;

if(b==NULL)return(0);

elseif(b->left==NULL&&b->right==NULL)return(1);

else{numl=count(b-〉left);

num2=count(b->right);

return(numl+num2);}

)

四、综合题(本题共30分，每小题5分)

1.有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为{4、7、

5、2、9},试画出对应的哈夫曼树(注意：构造哈夫曼树过程中请按左子树根结点的权

值小于等于右子树根结点的权值次序构造)，并求出每个字符的哈夫曼编码。

2.利用普里姆算法，从节点1出发构造出如下图所示的图G的一棵最小生成树。

3.一棵二叉树如下面的图所示，要求：

(1)写出对此二叉树进行中序遍历时得到的结点序列。

(2)画出由此二叉树转换得到的森林。

4.请画出，将元素3和元素6依次插入到下图所示的平衡二叉树中的结果，要求仍然

保持为一棵平衡二叉树。

5.一组元素为(46,25,78,62,12,37,70,29),要求:

(1)画出按元素排列顺序输入生成的一棵二叉排序树。

(2)画出在二叉排序树中，删除元素46后的结果

6.设哈希表长度为11,哈希函数h(key)=key/IE给定的关键字为1,13,12,34,

38,33,2,22。试画出用线性探查法解决冲突时所构造的哈希表。并计算在查找成

功时候的平均查找长度。

五、算法题(本题共10分)

假设线性表中包含n个数据元素，请写出顺序存储方式下对n个元素的冒泡排序

算法。具体存储结构如下:

#defineMaxsize20

TypedefintKeyType;

Typedefstruct{

KeyTypekey;〃关键字项

InfoTypeotherinfo;〃其它数据项

}RedType;//记录类型

Typedefstruct{

RedTyper[Maxsize+1];〃:r[0]闲置或者用做哨兵单元

Intlength;〃顺序表长度

}SqList;〃顺序表类型

参考答案

一、选择题（本题共20分，每题1分）

12345678910

CDACDCCCCD

11121314151617181920

BDCCBBCCCC

二、填空题（本题共20分，每空1分）

1.集合、线性结构、树形结构、网状结构

2.0（m*n）

3.n-i+1

4.①p->next②s->data③t

5.①②2*-1③2~+1

6.3层

7.①2②3③4

8.3

9.队尾、对头

10.拓扑排序

三、阅读程序写结果（本题共20分，每小题5分

1.删除了P结点

2.high=mid-l;low=mid+1;

3.搜索序列为：8,4,2,1,3,6,7,50

4.返回结果是2

四、综合题（本题共30分，每小题5分）

1.解：依题意，各字符对应的哈夫曼编码以及相应的哈夫曼树结果如下:

a：011b：10c：00d：010e：11

2.解：使