数据结构(第二版) 模拟试题自测卷AB卷带答案2

试卷三

一、单项选择题（在下列每小题四个备选答案中选出一个正确答案，并将其字母

标号填入题干的括号内。每小题2分，共30分）

I.数据结构可以形式化地定义为（S,△）,其中S指某种逻辑结构，△是指（）

A.S上的算法B.S的存储结构

C.在S上的一个基本运算集D.在S上的所有数据元素

2.下列说法正确的是（）

A.线性表的逻辑顺序与存储顺序总是一致的

B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续

C.线性表的线性存储结构优于链式存储结构

D.每种数据结构都具有插入、删除和查找三种基本运算

3.稀疏矩阵一般采用（）方法压缩存储。

A.三维数组B.单链表

C.三元组表D.散列表

4.在一个单链表中，若pt结点不是最后结点，在pt之后插入st结点，则实行（）。

A.st.next:=p；pt.next=s;

B.st.next:=pt.next;pt.next:二s；

C.st.next:=pt.next;p:=s;

D.pt.next:=s;st.next=p;

5•某个向量第一元素的存储地址为100,每个元素的长度为2,则第五个元素的地址是

（）。

A.110B.108C.100D.120

6.下面的二叉树中，（）不是完全二叉树。

A.B.C.D.

7.一组记录的排序码为（47、78、61、33、39>80）,则利用堆排序的方法建立的初始堆为

（）。

A.78、47、61>33、39、80B.80、78、61>33、39、47

C.80、78、61、47、39、33D.80、61、78、39、47、33

8.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指

针s所指的新结点作为非空双链表中q所指地点（中间结点）的直接后继结点插入到该双向

链表中，则下列算法段能正确完成上述要求的是（）

A.q->right=s;s->left=q;q->right->left=s;s->right=q->right;

B.s->left=q;q->right=s;q->right->left=s;s->right=q->right;

C.s->left=q;s->right=q->right;q->right->left=s;q->right=s;

D.以上都不对

9.由下列三棵树组成转的森林换成一棵二叉树为（）

©

A.@

/\

@©

©@

C.©D.@

/\

③®

/\\

©©©

©

10.for（i=0；i<m；i++）

for（j=0；j<t；j++）

c[i][j]=0；

for（i=0；i<m；i++）

for（j=0；j<t；j++）

for（k=0；k<n；k++）

c[i][j]=c[i][j]+a[i][k]*b[k][j];

上列程序的时间复杂度为（）

A.O（m+nXt）B.O（m+n+t）

C.O（mXnXt）D.O（mXt+n）

11.设循环队列的元素存放在一维数组Q[（）••30]中，队列非空时，front指示队头元素的前

一个位置，rear指示队尾元素。如果队列中元素的个数为11,front的值为25,则rear应

指向的元素是（）

A.Q[4]B.Q[5]

C.Q[14]D.Q[15]

12.定义二维数组A11-8,0-10],起始地址为LOC,每个元素占2L个存储单元，在以

行序为主序的存储方式下，某数据元素的地址为LOC+50L,则在以列序为主序的存储方

式下，该元素的存储地址为（）

A.LOC+28LB.LOC+36L

C.LOC+50LD.LOC+52L

13.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（）

A.插入和快速B.冒泡和快速

C.选择和插入D.选择和冒泡

14.设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段

p=h;

while（p->next->next!=h）

p=p->next;

p->next=h;

后（其中，p・>next为p指向结点的指针域），则（）

A.p->next指针指向链尾结点B.h指向链尾结点

C.删除链尾前面的结点D.删除链尾结点

15.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是（）

A.高度等于其结点数B.任一结点无左孩子

C.任一结点无右孩子D.空或只有一个结点

二'填空题（本大题共13小题，每小题2分，共26分）

请在每小题的空格中填上正确答案。错填、不填均无分。

16.数据的逻辑结构通常包括集合、线性结构、和图状结构。

17.给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过次

合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。

18.树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的关系。

19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结

点数为«

20.数据表示和是程序设计者所要考虑的两项基本任务。

21.在循环队列中，存储空间为0~n-L设队头指针front指向队头元素前一个空闲元素，队

尾指针指向队尾元素，那么其队空标志为rea『front,队满标志为。

22.深度为k的二叉树至多有个结点，最少有个结点。

23.在堆排序和快速排序中，若原始记录已基本有序，则较适合选用。

24.在一棵二叉排序树上按遍历得到的结点序列是一个有序序列。

25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是的。

26.三个结点可构成种不同形态的二叉树。

27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素和和的值，若比的

值大于ai+1的值，则交换a和ai+i»如此反复，直到某一趟中没有记录需要交换为止，

该排序方法被称为.

28.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为

2n个，其中个用于链接孩子结点。

三'应用题（本大题共5小题，每小题6分，共30分）

29.已知一棵二叉树的前序序列是ABCDEFG,中序序列是CBDAEGF。请构造出该二叉树,

并给出该二叉树的后序序列。

30.有一字符串序列为5*-x-y/x+2,利用栈的运算将其输出结果变为5x-*yx+/-2,试写出该

操作的入栈和出栈过程（采用push（a）表示a入栈，pop（a）表示a出栈）。

31.已知某二叉树的顺序存储结构如图所示，试画出该二叉树，并画出其二叉链表表示。

ABCDEFG

32.已知一组键值序列为（38,64,73,52,40,37,56,43）,试采用快速排序法对该组序列

作升序排序，并给出每一趟的排序结果。

33.请按照数列｛28,45,33,12,37,20,18,55｝的先后插入次序，生成一棵二叉排序树。

四'算法设计题（本大题共3小题，共14分）

34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。（4分）

35.某带头结点的单链表的结点结构说明如下：（6分）

typedefstructnodel

intdata;

structnodel*next

}node；

试设H^一个算法intcopy（node*headl,node*head2）,将以headl为头指针的单链表复制到一

个不带头结点且以head2为头指针的单链表中。

36.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。（4

分）

参考答案

一、选择题（本题共30分，每题2分）

1、C2、B3、C4、B5、B6、C7、B8、C9、A

10、C11、B12、D13、C14、D15、A

二'填空题（本题共26分,每小题2分）

16、树状结构17、n-1

18、逻辑19、n/2

20、数据处理21、front==(rear+1)%n

22、2k-l,k23、堆排序

24、中序25、有序

26、527、冒泡排序

28、n-l

三、应用题（本题共30分，每小题6分）

29、

后序序列：CDBGFEA（3分）

(3分)

30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);

pop(y);push(/);push(x);pop(x);push(+)；pop(+)；pop(/);pop(-);push(2);pop(2);

32、

第1趟:[37]38[735240645643]

第2趟：3738[4352406456]73

第3趟：3738[40]43[526456]73

第4趟：3738404352[6456]73

第5趟：3738404352[56]6473

第6趟：3738404352566473

31、

四、算法设计题(本题共14分)

34、(4分)

typedefstructnode.pointer;

structnode

(

datatypedata;

pointernext;

)；

typedefpointerIklist;

voidinsert_lklist(lklisthead,datatypex,inti)

(

pointer*p,*s;

p=head;

j=0;

while((p->next!=NULL)&&(j<i-1))

{p=p->next;j++;}

if(j!=i-l)

{printff不存在第i个位置)

break();

else{s=malloc(size);s->data=x;

s->next=p->next;

p->next=s;}

)

35、(6分)

intcopy(node*headl,node*head2)

(

Node*p,*s;

P=headl->next;

If(p!=NULL)

{

*r=malloc(size);

r->data=p->data;

head2=r;

p=p->next;

)

else

{head2=NULL;

Return(O);

)

While(p!=NULL)

{*s=malloc(size);

s->data=p->data;

r->next=s;

r=s;

p=p->next;

1

r->next=NULL;

retum(l);

)

36>(4分)

typedefcharDataType;

typedefstructnode

(

DataTypedata;

structnode*lchild,*rchild;

}BinTNode;

typedefBinTNodeinTree;

intnodes(BinTreeT)

intnuml,num2;

if(T==NULL)retum(O);

elseif(T->lchild==NULL&&T->rchild==NULL)return(l);

else

{

num1=nodes(T->lchild);

num2=nodes(T->rchild);

retum(num1+num2+1);

试卷A

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

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

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

C.线性结构和非线性结构1）.内部结构和外部结构

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（最多元素为mO）为满队列的条件是（）。

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

C.QU->front==（QU->rear+1）%mOD.QU->front!=（QU->rear+1）%mO

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

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

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

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

首地址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

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

是（）。

A.acbedB.decabC.deabcD.cedba

12.如下图所示的4棵二叉树中，（）不是完全二叉树。

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

A.3B.4

C.5D.6

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

数至少为（）。

A.2hB.2h-1

C.2h+lD.h+1

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

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

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

A.nB.n+1

C.n-1D.n/2

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

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+l)/2D.(n-l)/2

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

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

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

二、填空题(本题共20分，每空1分)

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

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

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

for0=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开始)，则编号最小的叶子结点的编号是

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

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

这棵树的深度是。

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(H%d",v);

visited[v]=l;

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

while(p!=NULL)

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

p=p->next;}

[ZEHZE1

03-EE1

EQ-*HZl

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

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

intcount(btree*b)

{intnuml,num2;

if(b二二NULL)return(O);

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

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

num2=count(b->right);

return(nuinl+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/11。给定的关键字为1,13,12,34,38,

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

平均查找长度。

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

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

具体存储结构如下：

#defineMaxsize20

TypedefintKeyType;

Typedefstruct{

KeyTypekey;〃关键字项

InfoTypeotherinfo;〃其它数据项

}RedType;〃记录类型

Typedefstruct{

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

Intlength;〃顺序表长度

}SqList;〃顺序表类型