全国高等教育自学考试数据结构试题.docx

全国高等教育自学考试数据结构试题.docx

《全国高等教育自学考试数据结构试题.docx》由会员分享，可在线阅读，更多相关《全国高等教育自学考试数据结构试题.docx（115页珍藏版）》请在冰点文库上搜索。

全国高等教育自学考试数据结构试题

全国2005年1月高等教育自学考试

数据结构试题

课程代码：

02331

第一部分选择题（共30分）

一、单项选择题（本大题共15小题，每小题2分，共30分）

1.数据元素及其关系在计算机存储器内的表示，称为数据的（）

A.逻辑结构B.存储结构C.线性结构D.非线性结构

2.某带头结点的单链表的头指针为head，判定该链表为非空的条件是（）

A.head==NULLB.head->next==NULLC.head!

=NULLD.head->next!

=NULL

3.导致栈上溢的操作是（）

A.栈满时执行的出栈B.栈满时执行的入栈C.栈空时执行的出栈D.栈空时执行的入栈

4.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是（）

A.（rear-front）%m==1B.front==rearC.（rear-front）%m==m-1D.front==（rear+1）%m

5.假设S=″IAMASTUDENT″，则运算substr（S,4,8）的结果为（）

A.″MAS″B.″MASTUD″C.″ASTUDEN″D.″STUD″

6.在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为（）

A.模式串的最末字符B.主串的第一个字符C.模式串的第一个字符D.主串的最末字符

7.从广义表L=（（（d）,c,d））中分解得到（d）的操作为（）

A.head（head（head（L）））B.head（tail（head（L）））C.tail（head（head（L）））D.tail（tail（head（L）））

8.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在（）

A.BT[i/2]B.BT[2*i-1]C.BT[2*i]D.BT[2*i+1]

9.右图所示二叉树的中序序列是（）

A.DHEBAFIJCG

B.DHEBAFJICG

C.DBHEAFCJIG

D.DBHEAFJICG

10.连通图是指图中任意两个顶点之间（）

A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图

11.下图所示带权无向图的最小生成树的权为（）

A.14

B.15

C.17

D.18

12.对记录序列（314，298，508，123，486，145）依次按个位和十位进行两趟基数排序之后所得结果为（）

A.123，145，298，314，486，508B.508，314，123，145，486，298

C.486，314，123，145，508，298D.298，123，508，486，145，314

13.在待排关键字序列基本有序的前提下，效率最高的排序方法是（）

A.直接插入排序B.快速排序C.直接选择排序D.归并排序

14.在下列各棵二叉树中，二叉排序树是（）

15.采用ISAM或VSAM组织的文件是（）

A.索引非顺序文件B.顺序文件C.索引顺序文件D.散列文件

第二部分非选择题（共70分）

二、填空题（本大题共10小题，每小题2分，共20分）

请在每小题的空格中填上正确答案。

错填、不填均无分。

16.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为______。

17.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是______。

18.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为______。

19.已知广义表LS为空表，则其深度为______。

20.假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，且每个元素占2个存储单元，则A[4][3][2]的地址是______。

21.已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则它的后序序列为______。

22.在含n个顶点的连通图中，任意两个不同顶点之间的一条简单路径最多包含______条边。

23.对关键字序列（50，34，92，19，11，68，56，41，79）进行直接插入排序，当将第7个关键字56插入到当前的有序子表中时，为寻找插入位置需进行______次关键字之间的比较。

24.对有序表进行二分查找的过程可用判定树来描述，其判定树的形态只取决于______。

25.将有序表中n个元素依次插入到一棵空的二叉排序树中，则在等概率查找的情况下，该二叉排序树在查找成功时的平均查找长度是______。

三、解答题（本大题共4小题，每小题5分，共20分）

26.

（1）写出右侧图形表示的广义表L。

（2）画出其表头与表尾均为（a,（b,c））的广义表L1的图形表。

（1）

（2）

27.试推导一棵满k叉树上的叶子结点数a与非叶子结点数b之间满足以下关系：

a=（k-1）b+1

28.假设用迪杰斯特拉（Dijkstra）算法求下列图中从顶点a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。

29.已知关键字序列在R[1..8]中的初始状态为

R

48

70

33

65

24

56

12

92

1

2

3

4

5

6

7

8

写出在将它调整为大根堆的过程中每一次筛选后R的状态。

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30.如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag,每当尾指针和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满”。

请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法。

intEnQueue（CirQueue*Q,DataTypex）{

if（

（1））return0;

Q->data[Q->rear]=x;

Q->rear=（Q->rear+1）%MAXQSIZE

（2）

return1;

}

intDeQueue（CirQueue*Q,DataType*x）{

if（（3））return0;

*x=Q->data[Q->front];

Q->front=（4）;

（5）;

return1;

}

（1）

（2）

（3）

（4）

（5）

31.已知具有n个结点的完全二叉树采用顺序存储结构存储在向量BT[1..n]中，结点的数据元素为字符类型，请阅读下列算法，并回答问题：

（1）假设向量BT中的内容为：

BT

A

B

C

D

E

F

1

2

3

4

5

6

写出执行f31（BT,6）后的输出结果；

（2）说明该算法的功能。

voidf31（charBT[],intn）

{inti=1;

while（i>0）

if（i<=n）{

printf（″%c″,BT[i]）;

i=i*2;

}else{

do{i=i/2;}while（i%2）;

if（i>0）i++;

}

}

（1）

（2）

32.设数组f的初始元素序列为：

f[1..9]=（1,3,2,3,3,2,1,2,1）

阅读下列算法，并回答问题。

其中算法f32中调用的函数swap（a,b）用以完成交换a和b的值。

（1）写出执行f32（f,9,3,1）之后f[1..9]中的元素序列，并写出在执行过程中调用swap函数的次数。

（2）简述算法f32的功能。

voidf32（intf[],intn,intx,inty）{

inti=1,j=1,k=n;

while（j<=k）

if（f[j]==y）j++;

elseif（f[j]==x）

{swap（f[i],f[j]）;i++;j++;}

else{swap（f[k],f[j];k--;}

}

（1）

（2）

33.下列算法利用二分查找方法在有序表r中插入元素x，并保持表r的有序性，其中参数*n为表r的长度。

请在空缺处填入合适的内容，使其成为一个完整的算法。

voidBinInsert（SeqListr,int*n,DataTypex）

{intlow=1,high=*n,mid,i;

while（low<=high）

{mid=

（1）;

if（x.key

else

（2）;

}

for（i=*n;（3）;i--）

r[i+1]=r[i];

（4）;

*n++;

}

（1）

（2）

（3）

（4）

五、算法设计题（本题共10分）

34.假设一元多项式以循环链表表示，链表的结点结构为：

typedefstructPNode{

floatcoef;//系数

intexp;//指数

structPNode*next;

}*LinkList;

现需要将一个用循环链表h表示的代数多项式拆分成两个多项式循环链表h1和h2，其中h1仅含多项式的奇次项，h2仅含多项式的偶次项。

要求利用原链表中的结点构成链表h1和h2。

例如多项式7x8+5x3-4x的循环链表为

经拆分之后的情况应是：

请编写完成上述拆分的算法，并进行算法分析。

全国2005年10月高等教育自学考试

数据结构试题

课程代码：

02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

1.若将数据结构形式定义为二元组（K，R），其中K是数据元素的有限集合，则R是K上

（）

A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合

2.在长度为n的顺序表中删除第i个元素（1≤i≤n）时，元素移动的次数为（）

A.n-i+1B.IC.i+1D.n-i

3.若不带头结点的单链表的头指针为head，则该链表为空的判定条件是（）

A.head==NULLB.head->next==NULLC.head!

=NULLD.head->next==head

4.引起循环队列队头位置发生变化的操作是（）

A.出队B.入队C.取队头元素D.取队尾元素

5.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（）

A.2，4，3，1，5，6.3，2，4，1，6，5C.4，3，2，1，5，6D.2，3，5，1，6，4

6.字符串通常采用的两种存储方式是（）

A.散列存储和索引存储B.索引存储和链式存储

C.顺序存储和链式存储D.散列存储和顺序存储

7.设主串长为n，模式串长为m（m≤n），则在匹配失败情况下，朴素匹配算法进行的无效位移次数为（）

A.mB.n-mC.n-m+1D.n

8.二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为（）

A.429B.432C.435D.438

9.对广义表L=（（a,b）,（c,d）,（e,f））执行操作tail（tail（L））的结果是（）

A.（e,f）B.（（e,f））C.（f）D.（）

10.下列图示的顺序存储结构表示的二叉树是（）

11.n个顶点的强连通图中至少含有（）

A.n-1条有向边B.n条有向边C.n（n-1）/2条有向边D.n（n-1）条有向边

12.对关键字序列（56，23，78，92，88，67，19，34）进行增量为3的一趟希尔排序的结果为（）

A.（19，23，56，34，78，67，88，92）B.（23，56，78，66，88，92，19，34）

C.（19，23，34，56，67，78，88，92）D.（19，23，67，56，34，78，92，88）

13.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为

（）

A.4B.5C.8D.9

14.由同一关键字集合构造的各棵二叉排序树（）

A.其形态不一定相同，但平均查找长度相同

B.其形态不一定相同，平均查找长度也不一定相同

C.其形态均相同，但平均查找长度不一定相同

D.其形态均相同，平均查找长度也都相同

15.ISAM文件和VSAM文件的区别之一是（）

A.前者是索引顺序文件，后者是索引非顺序文件

B.前者只能进行顺序存取，后者只能进行随机存取

C.前者建立静态索引结构，后者建立动态索引结构

D.前者的存储介质是磁盘，后者的存储介质不是磁盘

二、填空题（本大题共10小题，每空2分，共20分）

16.数据的逻辑结构在计算机存储器内的表示，称为数据的____________。

17.删除双向循环链表中*p的前驱结点（存在）应执行的语句是____________。

18.栈下溢是指在____________时进行出栈操作。

19.已知substr（s,i,len）函数的功能是返回串s中第i个字符开始长度为len的子串，strlen（s）函数的功能是返回串s的长度。

若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr（s,strlen（t）,strlen（t））后的返回值为____________。

20.去除广义表LS=（a1,a2,a3,……，an）中第1个元素，由其余元素构成的广义表称为LS的____________。

21.已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。

22.在有向图中，以顶点v为终点的边的数目称为v的____________。

23.当关键字的取值范围是实数集合时，无法进行箱排序和____________排序。

24.产生冲突现象的两个关键字称为该散列函数的____________。

25.假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中____________。

三、解答题（本大题共4小题，每小题5分，共20分）

26.假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。

（1）写出队满的条件表达式；

（2）写出队空的条件表达式；

（3）设m=40,rear=13,quelen=19,求队头元素的位置；

（4）写出一般情况下队头元素位置的表达式。

（1）

（2）

（3）

（4）

27.已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。

28.画出下图所示有向图的所有强连通分量。

29.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。

（1）假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；

（2）对所举序列进行快速排序，写出排序过程。

（1）

（2）

四、算法阅读题（本大题共4小题，每小题5分，共20分）

30.阅读下列算法，并回答问题：

（1）设顺序表L=（3,7,11,14,20,51），写出执行f30（&L,15）之后的L；

（2）设顺序表L=（4,7,10,14,20,51），写出执行f30（&L,10）之后的L；

（3）简述算法的功能。

voidf30（SeqList*L,DataTypex）

{

inti=0,j;

while（ilength&&x>L->data［i］）i++;

if（ilength&&x==L->data［i］）{

for（j=i+1;jlength;j++）

L->data［j-1］=L->data［j］;

L->length--;

}else{

for（j=L->length;j>i;j--）

L->data［j］=L->data［j-1］;

L->data［i］=x;

L->length++;

}

}

（1）

（2）

（3）

31.已知图的邻接表表示的形式说明如下：

#defineMaxNum50//图的最大顶点数

typedefstructnode{

intadjvex;//邻接点域

structnode*next;//链指针域

}EdgeNode;//边表结点结构描述

typedefstruct{

charvertex;//顶点域

EdgeNode*firstedge;//边表头指针

}VertexNode;//顶点表结点结构描述

typedefstruct{

VertexNodeadjlist［MaxNum］;//邻接表

intn,e;//图中当前的顶点数和边数

}ALGraph;//邻接表结构描述

下列算法输出图G的深度优先生成树（或森林）的边。

阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。

typedefenum{FALSE,TRUE}Boolean;

Booleanvisited［MaxNum］;

voidDFSForest（ALGraph*G）{

inti;

for（i=0;in;i++）visited［i］=

（1）;

for（i=0;in;i++）if（!

visited［i］）DFSTree（G,i）;

}

voidDFSTree（ALGraph*G,inti）{

EdgeNode*p;

visited［i］=TRUE;

p=G->adjlist［i］.firstedge;

while（p!

=NULL）{

if（!

visited［p->adjvex］）{

printf（″<%c,%c>″,G->adjlist［i］.vertex,

G->adjlist［p->adjvex］.vertex）;

（2）;

}

（3）;

}

}

（1）

（2）（3）

32.阅读下列算法，并回答问题：

（1）假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32（L，8）后的L；

（2）写出上述函数调用过程中进行元素交换操作的总次数。

voidf32（intR［］,intn）{

inti,t;

for（i=0;i

while（R［i］!

=i）{

t=R［R［i］］;

R［R［i］］=R［i］;

R［i］=t;

}

}

（1）

（2）

key

next

33.已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。

设散列表的长度为m，散列函数为Hash（key）=key%m。

链表的结点结构为：

。

请在空缺处填入适当内容，使其成为一个完整算法。

voidf33（LinkListL,LinkListH［］,intm）

{//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在

inti,j;

LinkListp,q;

for（i=0;i

H［i］=

（1）;

p=L->next;

while（p）

{

q=p->next;

j=p->key%m;

（2）;

H［j］=p;

（3）;

}

free（L）;

}

（1）

（2）（3）

五、算法设计题（本大题10分）

34.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示：

typedefcharDataType;

typedefstructnode{

DataTypedata;

structnode*lchild,*rchild;//左右孩子指针

structnode*parent;//指向双亲的指针

}BinTNode;

typedefBinTNode*BinTree;

若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。

（1）就后继的不同情况，简要叙述实现求后继操作的方法；

（2）编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。

全国2006年1月高等教育自学考试

数据结构试题

课程代码：

02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

1．根据数据元素的关键字直接计算出该元素存储地址的存储方法是（　　　）

A．顺序存储方法B．链式存储方法C．索引存储方法D．散列存储方法

2．下述程序段中语句①的频度是（　　　）

s=0;

for（i=1;i

for（j=0;j<=i;j++）

①s+=j;

A．

B．

C．

D．

3．求单链表中当前结点的后继和前驱的时间复杂度分别是（　　　）

A．O（n）和O

（1）B．O

（1）和O

（1）C．O

（1）和O（n）D．O（n）和O（n）

4．非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（　　　）

A．rear->next==headB．rear->next->next==head

C．head->next==rearD．head->next->next==rear

5．若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（　　　）

A．栈B．线性表C．队列D．二叉排序树

6．已知主串s=″ADBADABBAAB″，模式串t=″ADAB″，则应用朴素的串匹配算法进行模式匹配过程中，无效位移的次数是（　　　）

A．2B．3C．4D．5

7．串s=″DataStructure″中长度为3的子串的数目是（　　　）

A．9B．11C．12D．14

8．假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（　　　）

A．R[3][3][3]B．R[3][3][4]C．R[4][3][5]D．R[4][3][4]

9．除第一层外，满二叉树中每一层结点个数是上一层结点个数的（　　　）

A．1/2倍B．1倍C．2倍D．3倍

10．对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（　　　）

A．O（n）B．O（e）C．O（n+e）D．O（n2）

11．如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（　　　）

A．深度优先搜索算法B．广度优先搜索算法

C．求最小生成树的