文档库 最新最全的文档下载
当前位置:文档库 › 自考-数据结构历年考题综合(答案)

自考-数据结构历年考题综合(答案)

自考-数据结构历年考题综合(答案)
自考-数据结构历年考题综合(答案)

2006.10

1.若结点的存储地址与其关键字之间存在某种映射关系,则称这种存储结构为( )

A.顺序存储结构

B.链式存储结构

C.索引存储结构

D.散列存储结构

2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素,元素的移动次数为( )

A.n-i+1

B.n-i

C.i

D.i-1

3.对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )

A.顺序表

B.用头指针表示的单循环链表

C.用尾指针表示的单循环链表

D.单链表

4.若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为( )

A.4

B.5

C.6

D.7

5.一棵有16结点的完全二叉树,对它按层编号,则对编号为7的结点X,它的双亲结点及右孩子结点的编号分别为()

A.2,14 B.2,15

C.3,14 D.3,15

6.设有一5阶上三角矩阵A[1..5,1..5],现将其上三角中的元素按列优先顺序存放在一堆数组B[1..15]中。已知B[1]的地址为100,每个元素占用2个存储单元,则A[3,4]的地址为()

A.116 B.118

C.120 D.122

7.一个带权的无向连通图的最小生成树()

A.有一棵或多棵B.只有一棵

C.一定有多棵D.可能不存在

8.下列有关图遍历的说法中不正确的是()

A.连通图的深度优先搜索是一个递归过程

B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征

C.非连通图不能用深度优先搜索法

D.图的遍历要求每一顶点仅被访问一次

9.某算法的空间花费s(n)=2n+n100+nlog2n+n101,则其空间复杂度为()。

A.O(nlog2n) B. O(n100) C. O(n101) D. O(2n)

10. 单链表中的存储密度一定()。

A.小于0.5 B. 等于1 C. 大于0.1 D. 小于1

11.在顺序栈中删除一个元素,至少要移动()元素。

A.0 B. 1 C. n/2 D. n

12.空串是()。

A.只包含空格符的串 B. 长度为0的串

C. 只包含一个空格符的串

D. 不含字母的串

13.采用三元组表存储稀疏矩阵,是为了()。

A.节省存取时间 B. 节省存储空间

C. 提高对矩阵元素的访问速度

D. 提高对矩阵运算的可靠性

14.高度为h的二叉树最多有()个节点。

A.2h-1 B. 2h C. 2h-1 D. 2h-1+1

15.N个顶点,e条边的无权有向图的邻接矩阵中非零元素有()个。

A.n B. n-e C. e D. e+n

16.直接选择排序在最好情况下的时间复杂度是()。

A.O(n) B. O(nlog2n) C. O(1) D. O(n2)

17.N个结点的m阶B树至少包含()个关键字。

A.(m-1)*n B. n C. (「m/2」-1)*(n-1)+1 D. n*「m/2」-1)

18.在散列文件中,同一个桶内的所有记录应当具有()。

A.相同的关键字 B. 相同的散列值

C. 相同的某个属性值

D. 相同的存取频率

19.在最坏的情况下,查找成功时二叉排序树的平均查找长度()

A.小于顺序表的平均查找长度B.大于顺序表的平均查找长度

C.与顺序表的平均查找长度相同D.无法与顺序表的平均查找长度比较

20.散列表中由于散列到同一个地址而引起的“堆积”现象,是由()

A.同义词之间发生冲突引起的

B.非同义词之间发生冲突引起的

C.同义词之间或非同义词之间发生冲突引起的

D.散列表“溢出”引起的

二、填空题(每空1.5分,计15分)

21.ALV树是一种平衡的二叉排序树,树中任一结点的( )

22.在VSAM文件的控制区间中,记录的存储方式为( )

23.单链表的存储密度()顺序表的存储密度。

24.设SQ是循环队列,存储在数组D[M]中,则SQ入队操作对其队尾指针rear的修改是()。

25.长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是()。

26.广义表(((a,b,c),d,e,f))的长度是()。

27.N(n>0)个节点的哈夫曼树恰含()个度为1的节点。

28.深度为n的二叉树最少有()个结点。

29.N(n>0)个顶点的连通有向图至少有()条边。

30.对N(n>0)个记录进行冒泡排序,最少要交换()记录。

三、简答题(每小题5分,计30分)

31.给出下面森林对应的二叉树及二叉树的后续序列。(图1)

32.一棵树有3度节点100个,2度节点200个,该树有叶子节点多少个,该树可以有多少个度为1的节点?

33.设有广义表A, A=(((a,b),x),((a),(b)),(c,(d,(y)))),写出由A得到y的对广义表A的操作序列。

34.画出用普里姆算法构造下面所示带权无向图的最小生成树的示意图。

35.写出下列用快排序对下列序列进行两次划分的过程及结果。

37 26 51 48 77 69 82 21 17 13 21 39 55 18

36.画出对下面的5阶B树插入关键字37后的结果。

四、理解设计题(每小题5分,计15分)

37.设某带头结头的单链表的结点结构说明如下:

typedef struct nodel { int data; struct nodel*next; }node;

试设计一个算法:void copy(node*head l,node*head 2),将以head 1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。(5分)

38. 阅读下列算法,并回答下列问题:

(1)该算法采用何种策略进行排序?

(2)算法中R[n+1]的作用是什么?

typedef struct { KeyType key; infoType otherinfo; } nodeType;

typedef nodeType SqList[MAXLEN];

void sort(SqList R,int n) { //n小于MAXLEN-1

int k;i;

for(k=n-1;k>=1;k--)

if(R[k].key>R[k+1].key) {

R[n+1]=R[k];

for(i=k+1;R[i].key

R[i-1]=R[n+1];

}}

39.下面函数BinInsert的功能是对线性表R的前n个元素实现二分法插入排序。请在空缺处填入适当的语句,使其能够正确工作。

TYPEDEF STRUCT NODE { INT KEY; /* OTHER INFO */ } NODE;

TYPEDEF NODE SEQLIST[100];

VOID BININSERT(SEQLIST R,INT N)

{ INT LOW,UP,MID,I,J;

NODE T;

FOR(I=0;I

{ _____(1)________________;

LOW=0; __________(2)_____________;

WHILE(LOW

{ MID=(LOW+UP)/2;

IF(R[MID].KEY==T.KEY) {_________(3)__________; BREAK;}

IF(T.KEY

}

FOR(J=I;J>LOW;J--) R[J]=R[J-1];

_________(6)_____________;

}

}

五、算法实现题(共10分)

40.假设二叉树T采用如下定义的存储结构:

typedef struct node { DataType data; struct node *lchild,*rchild,*parent; }PBinTree;

其中,结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针,而parent域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法,将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。

2006

一.单项选择题

1.D

2.B

3.C

4.B

5.D

6.C

7.B

8.D

9.D 10.D

11.A 12.B 13.B 14.A 15.C 16.A 17.C 18.B 19.C 20.B

二.填空题

21.左右子树树高之差的绝对值不大于1 23.小于 24.sq->rear=(sq->rear+1) % m 25.O(n) 26.1 27.0

28. n 29. n 30. 0

三.简答题

31.

G F E D C B J I K H A

32、n0=n2+2n3+1

=200+2*100+1

=401

33、Tail(Head(Tail(Head(Tail(Tail(A)))))=(y)

34、

35、18 26 21 13 17 21 【37】82 69 77 48 39 55 51

36、

四.阅读理解题

37、一边遍历,一边申请新结点,链接到head2序列中。

38、直接插入排序。

哨兵。避免边界检测,提高程序运行效率。

39、t=R[i]; up=i-1;

low=mid+1; up=mid-1; low=mid+1;

R[low]=t;

2002

1.某算法的空间花费s(n)=2n+n100+nlog2n+n101,则其空间复杂度为()。

A.O(nlog2n) B. O(n100) C. O(n101) D. O(2n)

2.单链表中的存储密度一定()。

A.小于0.5 B. 等于1 C. 大于0.1 D. 小于1

3.在顺序栈中删除一个元素,至少要移动()元素。

A.0 B. 1 C. n/2 D. n

4.空串是()。

A.只包含空格符的串 B. 长度为0的串

C. 只包含一个空格符的串

D. 不含字母的串

5.采用三元组表存储稀疏矩阵,是为了()。

A.节省存取时间 B. 节省存储空间

C. 提高对矩阵元素的访问速度

D. 提高对矩阵运算的可靠性

6.高度为h的二叉树最多有()个节点。

A.2h-1 B. 2h C. 2h-1 D. 2h-1+1

7.N个顶点,e条边的无权有向图的邻接矩阵中非零元素有()个。

A.n B. n-e C. e D. e+n

8.直接选择排序在最好情况下的时间复杂度是()。

A.O(n) B. O(nlog2n) C. O(1) D. O(n2)

9.N个结点的m阶B树至少包含()个关键字。

A.(m-1)*n B. n C. (「m/2」-1)*(n-1)+1 D. n*「m/2」-1)

10.在散列文件中,同一个桶内的所有记录应当具有()。

A.相同的关键字 B. 相同的散列值

C. 相同的某个属性值

D. 相同的存取频率

11.某算法的时间花费T(n)=0.05n2+100n+10,则该算法的时间复杂度为()。

12.单链表的存储密度()顺序表的存储密度。

13.设SQ是循环队列,存储在数组D[M]中,则SQ入队操作对其队尾指针rear的修改是()。14.长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是()。

15.广义表(((a,b,c),d,e,f))的长度是()。

16.N(n>0)个节点的哈夫曼树恰含()个度为1的节点。

17.深度为n的二叉树最少有()个结点。

18.N(n>0)个顶点的连通有向图至少有()条边。

19.对N(n>0)个记录进行冒泡排序,最少要交换()记录。

20.倒排文件的每个倒排表项包含()和记录地址。

21.给出下面森林对应的二叉树及二叉树的后续序列。(图1)

22.一棵树有3度节点100个,2度节点200个,该树有叶子节点多少个,该树可以有多少个度为1的节点?23.设有广义表A, A=(((a,b),x),((a),(b)),(c,(d,(y)))),写出由A得到y的对广义表A的操作序列。

24.设有程序:

int f(int a[],int n,int key)

{ int i;

for (i=0;i

if(a[i]==key) return i;

return -1;

}

若key在a[j](j=0,1,2,…n-1)中的概率为2-(j+1),key不在a中的概率为2-n,那么查找Key时平均比较Key的次数是多少,该算法的时间复杂度是多少?

25.画出用普里姆算法构造下面所示带权无向图的最小生成树的示意图。

四、理解题(每题6分,计12分)

26.指出下面函数GV的功能及其返回值的含义。其中,Tab是存储稀疏矩阵A的非零元素的长度为LEN的三元组表。

#INCLUDE

TYPEDEF STRUCT {INT ROW,COL,V AL;} TRITUPLENODE;

INT GV(INT I,INT J,INT LEN,TRITUPLENODE TAB[])

{ INT K;

FOR(K=0; K

IF(TAB[K].ROW==I && TAB[K].COL==J) RETURN TAB[K].VAL;

RETURN 0;

}

27.设P1和P2是两个单链表,他们的元素都递增有序,指出下面函数F的功能。

TYPEDEF INT DA TATYPE;

TYPEDEF STRUCT NODE {DATA TYPE DA TA; STRUCT NODE * NEXT;} LISTNODE;

TYPEDEF LISTNODE * LINKLIST;

LINKLIST F(LINKLIST P1, LINKLIST P2)

{ LINKLIST H=NULL, P;

WHILE(P1&&P2)

{ IF(P1->DA TADATA) { P=P1; P1=P1->NEXT; }

ELSE { P=P2; P2=P2->NEXT;}

P->NEXT=H; H=P;

}

WHILE(P1) { P=P1; P1=P1->NEXT; P->NEXT=H; H=P;}

WHILE(P2) { P=P2; P2=P2->NEXT; P->NEXT=H; H=P;}

RETURN H;

}

五、填充题(每题18分)

28.下面函数BinInsert的功能是对线性表R的前n个元素实现二分法插入排序。请在空缺处填入适当的语句,使其能够正确工作。

TYPEDEF STRUCT NODE { INT KEY; /* OTHER INFO */ } NODE;

TYPEDEF NODE SEQLIST[100];

VOID BININSERT(SEQLIST R,INT N)

{ INT LOW,UP,MID,I,J;

NODE T;

FOR(I=0;I

{ _____(1)________________;

LOW=0; __________(2)_____________;

WHILE(LOW

{ MID=(LOW+UP)/2;

IF(R[MID].KEY==T.KEY) {_________(3)__________; BREAK;}

IF(T.KEY

}

FOR(J=I;J>LOW;J--) R[J]=R[J-1];

_________(6)_____________;

}

}

2002D

一、单项选择题

1.D

2.D

3.A

4.B

5.B

6.A

7.C

8.D

9.C 10.B

二、填空题(每小题2分,共30分)

11. O(n2)12.小于 13.rear=(rear+1) % m 14. O(n)15. 1 16. 017. n18. n 19. 0 20. 次关键字

三、简答题

21、(见下图)后序序列GFEDCBJIKHA

22、叶结点有401个,度为1的结点可以有任意多个。

24、平均比较次数=1*2-(0+1)+2*2-(1+1)+……+n*2-((n-1)+1)+n*2-n

=2-2-(n-1)-n*2-n

时间复杂度为:O(1)

25、见图。

四、理解题

26、在三元组表Tab中,查找稀疏矩阵中元素A[I,J]的值,并把此值作为函数的返回值。

27、把两个递增有序的单链表合并为一个递减有序的单链表。

五、填充题

t=R[i]; up=i-1 low=mid+1

up=mid-1 low=mid+1 R[low]=t

2002-10

一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个选项中只有一个选项是符合题目要求的,

请将正确选项前的字母填在题后的括号内。

1.若结点的存储地址与其关键字之间存在某种映射关系,则称这种存储结构为( )

A.顺序存储结构

B.链式存储结构

C.索引存储结构

D.散列存储结构

2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素,元素的移动次数为( )

A.n-i+1

B.n-i

C.i

D.i-1

3.对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )

A.顺序表

B.用头指针表示的单循环链表

C.用尾指针表示的单循环链表

D.单链表

4.若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为( )

A.4

B.5

C.6

D.7

5.为查找某一特定单词在文本中出现的位置,可应用的串运算是( )

A.插入

B.删除

C.串联接

D.子串定位

6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串,函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″,则调用函数Scopy(P,Sub(S,1,7))后得到( )

A.P=″SCIENCE″

B.P=″STUDY″

C.S=″SCIENCE″

D.S=″STUDY″

7.三维数组A[4][5][6]按行优先存储方法存储在内存中,若每个元素占2个存储单元,且数组中第一个元素的存储地址为120,则元素A[3][4][5]的存储地址为( )

A.356

B.358

C.360

D.362

8.如右图所示广义表是一种( )

A.线性表

B.纯表

C.结点共享表

D.递归表

9.下列陈述中正确的是( )

A.二叉树是度为2的有序树

B.二叉树中结点只有一个孩子时无左右之分

C.二叉树中必有度为2的结点

D.二叉树中最多只有两棵子树,并且有左右之分

10.n个顶点的有向完全图中含有向边的数目最多为( )

A.n-1

B.n

C.n(n-1)/2

D.n(n-1)

11.已知一个有向图如右所示,则从顶点a出发进行深度优先偏历,不可能得到的DFS

序列为( )

A.a d b e f c

B.a d c e f b

C.a d c b f e

D.a d e f c b

12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( )

A.快速排序

B.堆排序

C.归并排序

D.基数排序

13.不可能生成右图所示二叉排序树的关键字序列是( )

A.4 5 3 1 2

B.4 2 5 3 1

C.4 5 2 1 3

D.4 2 3 1 5

14.ALV树是一种平衡的二叉排序树,树中任一结点的( )

A.左、右子树的高度均相同

B.左、右子树高度差的绝对值不超过1

C.左子树的高度均大于右子树的高度

D.左子树的高度均小于右子树的高度

15.在VSAM文件的控制区间中,记录的存储方式为( )

A.无序顺序

B.有序顺序

C.无序链接

D.有序链接

二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分)

16.若一个算法中的语句频度之和为T(n)=3720n+4nlogn,则算法的时间复杂度为________。

17.在如图所示的链表中,若在指针p所指的结点之后插入数据域值相继为a和b的两个结点,则可用下列两个语句实现该操作,它们依次是________和________。

18.假设以S和X分别表示进栈和退栈操作,则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后,得到的输出序列为________。

19.串S=″I am a worker″的长度是________。

20.假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中,则C数组的大小应为________。

21.在n个结点的线索二叉链表中,有________个线索指针。

22.若采用邻接矩阵结构存储具有n个顶点的图,则对该图进行广度优先遍历的算法时间复杂度为________。

23.对关键字序列(52,80,63,44,48,91)进行一趟快速排序之后得到的结果为________。

24.由10000个结点构成的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度的最大值可能达到________。

25.若要找出所有工资低于1500元,职称是副教授,及所有工资低于2000元,职称是教授的记录,则查询条件是________。

三、解答题(本大题共4小题,每小题5分,共20分)

26.已知一个6行5列的稀疏矩阵中非零元的值分别为:-90,41,-76,28,-54,65和-8,它们在矩阵中的列号依次为:1,4,5,1,2,4和5。当以带行表的三元组表作存储结构时,其行表RowTab中的值依次为0,0,2,2,3和5。请写出该稀疏矩阵(注:矩阵元素的行列下标均从1开始)。

27.已知树T的先序遍历序列为ABCDEFGHIJKL,后序遍历序列为CBEFDJIKLHGA。请画出树T。

28.对关键字序列(72,87,61,23,94,16,05,58)进行堆排序,使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。

初始堆:________ 第1趟:________

第2趟:________ 第3趟:________

29.在关键字序列(07,12,15,18,27,32,41,92)中用二分查找法查找和给定值92相等的关键字,请写出查找过程

中依次和给定值“92”比较的关键字。

四、算法阅读题(本大题共4小题,每小题5分,共20分)

30.以下函数中,h是带头结点的双向循环链表的头指针。

(1)说明程序的功能;(2)当链表中结点数分别为1和6(不包括头结点)时,请写出程序中while循环体的执行次数。

int f(DListNode *h) {

DListNode *p,*q; int j=1;

p=h->next; q=h->prior;

while(p!=q && p->prior!=q)

if(p->data==q->data)

{

p=p->next;

q=q->prior;

}

else j=0;

return j;

}

31.设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。请写出调用algo(&s)后栈S的状态。

void algo(Stack *S)

{int i=0;

Queue Q; Stack T;

InitQueue(&Q);InitStack(&T);

while (!StackEmpty(S))

{

if((i=!i)!=0)Push(&T,Pop(&S));

else EnQueue(&Q,Pop(&S));

}

while(!QueueEmpty(Q))

Push(&S,DeQueue(&Q));

while(!StackEmpty(T))

Push(&S,Pop(&T));}

32.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下:

#define MaxNum 50//图的最大顶点数

#define INFINITY INT_MAX //INT_MAX为最大整数,表示∞

typedef struct{

char vexs[MaxNum];//字符类型的顶点表

int edges[MaxNum][MaxMum];//权值为整型的邻接矩阵

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

}MGraph;//邻接矩阵结构描述

typedef struct node {

int adjvex;//邻接点域

int weight;//边的权值

struct node *next;//链指针域

} EdgeNode;//边表结点结构描述typedef struct {

char vertex;//顶点域

EdgeNode * firstedge;//边表头指针} VertexNode ;//顶点表结点结构描述typedef struct {

VertexNode adjlist[MaxNum];//邻接表int n,e;//图中当前的顶点数和边数

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

下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2,请填入合适的内容,使其成为一个完整的算法。

void convertM(MGraph *G1,ALGraph *G2)

{ int i,j;

EdgeNode * p;

G2->n=G1->n;

G2->e=G1->e;

for(i=0;in;i++)

{

G2->adjlist[i].vertex=G1->vexs[i];

G2->adjlist[i].firstedge= (1) ;

}

for (i=0;in;i++)

for (j=0;jn;j++)

if(G1->edges[i][j]

{ p=(EdgeNode *) malloc(sizeof(EdgeNode));

p->weight= (2) ;

p->adjvex=j;

p->next=G2->adjlist[i].firstedge;

(3) ;

}}

33.阅读下列算法,并回答下列问题:(1)该算法采用何种策略进行排序?

(2)算法中R[n+1]的作用是什么? Typedef struct {

KeyType key;

infoType otherinfo;

} nodeType;

typedef nodeType SqList[MAXLEN]; void sort(SqList R,int n)

{

//n小于MAXLEN-1

int k;i;

for(k=n-1;k>=1;k--)

if(R[k].key>R[k+1].key)

{

R[n+1]=R[k];

for(i=k+1;R[i].key

R[i-1]=R[i];

R[i-1]=R[n+1];

}

}

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

34.假设二叉树T采用如下定义的存储结构:

typedef struct node {

DataType data;

struct node *lchild,*rchild,*parent;

}PBinTree;

其中,结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针,而parent域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法,将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。

一.单项选择题

1.D

2.A

3.A

4.B

5.D

6.A

7.A

8.C

9.D 10.D

11.A 12.B 13.A 14.B 15.D

二.填空题

16. O(nlogn) 17.b->next=p->next; p->next=s;

18.bceda 19.14

20.46 21.n+1

22.O(n2) 23. 48,44,82,63,80,91

24. (10000+1)/2

25. 职称=“副教授”and工资<1500 or职称=“教授”and and工资<2000

三.简答题

26.

27.由于树的后序序列就是等价二叉树的中序遍历序列,因此先得到等价二叉树,然后转化为相应的树。

28.初始堆:05,23,16,58,94,72,61,87第一趟:16,23,61,58,94,72,87,05

第二趟:23,58,61,87,94,72,16,05 第三趟:58,72,61,87,94,23,16,05

29.18 32 41 92

四.算法阅读题

30.(1). 检查循环链表中头结点两端对应位置处的结点值是否对称相等。

(2). 当结点个数为1时,循环次数为0次。

当结点个数为0时,循环次数为3次。

31. 7 5 3 1 2 4 6 (7为栈顶)

32.(1)NULL

(2)G1->edges[i][j]

(3)G2->adjlist[i].firstedge=p 33.(1)从右侧进行的直接插入排序

(2)R[n+1]的作用为哨兵

五.算法设计题

34.BintreeNode *pre; pre=NULL;

void xiugai(BinTree *T)

{ if(T)

{ xiugai ((*T) ->lchild);

(*T)->parent=pre;

pre=(*T);

xiugai ((*T) ->rchild);

}}

2003.10

1.下列说法正确的是()

A.数据是数据元素的基本单位

B.数据元素是数据项中不可分割的最小标识单位

C.数据可由若干个数据元素构成

D.数据项可由若干个数据元素构成

2.数据结构的基本任务是()

A.逻辑结构和存储结构的设计B.数据结构的运算实现

C.数据结构的评价与选择D.数据结构的设计与实现

3.在一个具有n个结点的有序单链表中插入一个新结点,并使插入后仍然有序,则该操作的时间复杂性量级为()A.O(1)B.O(n)

C.O(nlog2n)D.O(n2)

4.顺序存储的线性表(a1,a2,…,a n),在任一结点前插入一个新结点时所需移动结点的平均次数为()

A.n B.n/2

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

5.下列树U′,经剪枝运算DELETE(U′,x,2)后为()

6.一棵有16结点的完全二叉树,对它按层编号,则对编号为7的结点X,它的双亲结点及右孩子结点的编号分别为()

A.2,14 B.2,15

C.3,14 D.3,15

7.设有一5阶上三角矩阵A[1..5,1..5],现将其上三角中的元素按列优先顺序存放在一堆数组B[1..15]中。已知B [1]的地址为100,每个元素占用2个存储单元,则A[3,4]的地址为()

A.116 B.118

C.120 D.122

8.一个带权的无向连通图的最小生成树()

A.有一棵或多棵B.只有一棵

C.一定有多棵D.可能不存在

9.下列有关图遍历的说法中不正确的是()

A.连通图的深度优先搜索是一个递归过程

B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征

C.非连通图不能用深度优先搜索法

D.图的遍历要求每一顶点仅被访问一次

10.在最坏的情况下,查找成功时二叉排序树的平均查找长度()

A.小于顺序表的平均查找长度B.大于顺序表的平均查找长度

C.与顺序表的平均查找长度相同D.无法与顺序表的平均查找长度比较

11.闭散列表中由于散列到同一个地址而引起的“堆积”现象,是由()

A.同义词之间发生冲突引起的

B .非同义词之间发生冲突引起的

C .同义词之间或非同义词之间发生冲突引起的

D .散列表“溢出”引起的

12.从外存设备的观点看,存取操作的基本单位是( ) A .逻辑记录 B .数据元素 C .文件 D .物理记录

13.对文件进行检索操作时,每次都要从第一个记录开始的文件是( ) A .顺序文件 B .索引文件 C .顺序索引文件 D .散列文件

14.一组记录的键值为(46,74,18,53,14,20,40,38,86,65),利用堆排序的方法建立的初始堆为( ) A .(14,18,38,46,65,40,20,53,86,74) B .(14,38,18,46,65,20,40, 53,86,74) C .(14,18,20,38,40,46,53,65,74,86) D .(14,86,20,38,40,46,53,65,74,18)

15.对序列(22,86,19,49,12,30,65,35,18)进行一趟排序后得到的结果如下:(18,12,19,22,49,30,65,35,86),则可以认为使用的排序方法是( ) A .选择排序 B .冒泡排序 C .快速排序 D .插入排序

二、填空题(本大题共13小题,每空2分,共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.表示逻辑关系的存储结构可以有四种方式,即顺序存储方式、链式存储方式、_______________和散列存储方式。 17.设某非空双链表,其结点形式为 若要删除指针q 所指向的结点,则需执行下述语句段:q->prior->next =q->next; _______________。

18.如图所示,设输入元素的顺序是A ,B ,C ,D ,通过栈的变换,在输出端可得到各种排列。若输出序列的第一个元素为D ,则输出序列为_______________。

19.队列中允许进行删除的一端为________________。

20.设一棵二叉树中度为2的结点数为10,则该树的叶子数为________________。 21.如图所示的二叉树,若按后根遍历,则其输出序列为________________。

22.一个具有n 个顶点的有向完全图的弧数为________________。

23.查找表的数据结构有别于线性表、树型结构等,其逻辑结构为________________。 24.长度为L 的顺序表,采用设置岗哨方式顺序查找,若查找不成功,其查找长度为________________。

25.在开散列表上查找某元素时,通常分两步进行,首先必须计算该键值的散列地址,然后在地址指针所指________________中查找该结点。

26.文件的检索有顺序存取、________________和按关键字存取三种方式。

27.在待排序的n 个记录中任取一个记录,以该记录的键值作为标准,将所有记录分为两组,使得第一组中各记录的

键值均小于或等于该键值,第二组中的各记录的键值均大于该键值;然后将该记录排在两组中间。再对所分成的两组分别使用上述方法,直到所有记录都排在适当位置为止。这种排序方法称为________________。

28.在对一组记录关键字(54,38,96,23,15,72,60,45,83)进行冒泡排序时,整个冒泡排序过程中需进行________________趟才能完成。

三、应用题(本大题共5小题,共30分)

29.设有一顺序队列sq ,容量为5,初始状态时sq.front=sq.rear=0,画出做完下列操作后队列及其头尾指针的状态变化情况,若不能入队,请简述其理由后停止。(6分) (1) d,e,b 入队 (2) d,e 出队 (3) i,j 入队 (4) b 出队 (5) n,o,p 入队

30.已知无向图G 的邻接矩阵如下,假设对其每行元素访问时必须从右到左,请写出从V 0开始的深度优先搜索的序列。(4分)

4

v 3

v 2

v 1

v 0

v 432100111010110110111110100110V V V V V ???

????

?

???????

?

31.画出下列二叉树的二叉链表表示图。(6分)

32.用二分查找法对一个长度为10的有序表进行查找,填写查找每一元素需要的比较次数。(8分)

元素下标

比较次数 33.已知序列(10,18,4,3,6,12,1,9

,15,8),请给出采用二路归并排序法对该序列进行升序排序时的每一趟

结果。(6分)

四、设计题(本大题共2小题,共14分) 34.设某带头结头的单链表的结点结构说明如下: typedef struct nodel { int data; struct nodel*next;

}node;

试设计一个算法:void copy(node*head l, node*head 2),将以head 1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。(6分)

35.修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾,第二次把最小记录放到表头,如此反复进行。试编写修改后的算法:void dbubble(int a[],int n)。(8分)

一、单项选择题

1.C

2.B

3.B

4.D

5.C

6.D

7.A

8.A

9.C 10.C 11.B 12.D 13.A 14.B 15.C 二、填空题

16.索引存储方式 17. q->next->prior=q->prior; 18. D C B A 19. 队首

20. 11 21. D B F H G E C A 22. N (N-1) 24. L+1 25、链表中 26. 随机存取 27、快排序 28、7 三、应用题:

29、图形略,提示对于使用顺序表的队列,一般使用循环结构,否则随着出队入队次数的增多,一定会出现队尾益出顺序表的情况。

30、V 0 V 2 V 4 V 3 V 1

32、比较次数顺序为: 3、2、3、4、1、3、4、2、3、4

33、第一趟:(10 8) (3 4) (6 12) (1 9) (8 15) 第二趟:(3 4 8 10) (1 6 9 12) (8 15) 在本趟末尾并入剩余的一组,结果为:

(3 4 8 10) (1 6 8 9 12 15) 第三趟:(1 3 4 6 8 9 10 12 15 四、设计题:

34、void copy(node * head1, *head2) { node *p, *q, *r; p=head1->next;

if(p==NULL) { printf(“Error”); return;} while(p)

{ q=(node *)malloc(sizeof(node)); q->data=p->data; q->next=NULL; if(head2==NULL) { head2=q; r2=q;} else

{ r2->next=q; r2=q;}} }

2004.10

1.在数据结构中,数据的逻辑结构可以分成( ) A .内部结构和外部结构

B .线性结构和非线性结构

C .紧凑结构和非紧揍结构

D .动态结构和静态结构 2.在以单链表为存储结构的线性表中,数据元素之间的逻辑关系用( )

A .数据元素的相邻地址表示

B .数据元素在表中的序号表示

C .指向后继元素的指针表示

D .数据元素的值表示

3.设p 指向单链表中的一个结点,s 指向待插入的结点,则下述程序段的功能是( ) s -> next = p -> next; p -> next = s;

t = p -> data; p -> data = s -> data; s ->data = t; A .结点*p 与结点*s 的数据域互换 B .在p 所指结点的元素之前插入元素 C .在p 所指结点的元素之后插入元素 D .在结点*p 之前插入结点*s 4.栈和队列都是( ) A .限制存取位置的线性结构 B .顺序存储的线性结构 C .链式存储的线性结构

D .限制存取位置的非线性结构

5.若数组s[0..n-1]为两个栈s1和s2的共用存储空间,且仅当s[0..n-1]全满时,各栈才不能进行进栈操作,则为这两个栈分配空间的最佳方案是:s1和s2的栈顶指针的初值分别为( ) A .1和n+1 B .1和n/2 C .-1和n

D .-1和n+1

6.执行下列程序段后,串X 的值为( )

S=〞abcdefgh 〞; T=〞xyzw 〞;

substr (X,S,2,strlen(T));

substr (Y,S, stelen(T),2);

strcat (X,Y);

A.〞cdefgh〞B.〞cdxyzw〞

C.〞cdefxy〞D.〞cdefef〞

7.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()

A.数组的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列

C.数组的元素之间存在次序关系D.数组是多维结构,内存是一维结构

8.从广义表LS=((p, q), r, s)中分解出原子q的运算是()

A.tail (head (LS)) B.head (tail (head (LS)))

C.head (tail (LS)) D.tail (tail (head (LS)))

9.在具有n个叶子结点的严格二叉树中,结点总数为()

A.2n+1 B.2n

C.2n-1 D.2n-2

10.若是有向图的一条边,则称()

A.v i邻接于v j B.v j邻接于v i

C.v i和v j相互邻接D.v i与v j不相邻接

11.在一个带权连通图G中,权值最小的边一定包含在G的()

A.最小生成树中B.深度优先生成树中

C.广度优先生成树中D.深度优先生成森林中

12.当在二叉排序树中插入一个新结点时,若树中不存在与待插入结点的关键字相同的结点,且新结点的关键字小于根结点的关键字,则新结点将成为()

A.左子树的叶子结点B.左子树的分支结点

C.右子树的叶子结点D.右子树的分支结点

13.希尔排序的增量序列必须是()

A.递增的B.随机的

C.递减的D.非递减的

14.如果在排序过程中,每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置,则该排序方法称为()

A.插入排序B.归并排序

C.冒泡排序D.堆排序

15.设置溢出区的文件是()

A.索引非顺序文件B.ISAM文件

C.VSAM文件D.顺序文件

二、填空题(本大题共10小题,每小题2分,共20分)

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

16.下列程序段的时间复杂度为________________。

product = 1;

for (i = n;i>0; i--)

for (j = i+1; j

product *=j;

17.已知指针p指向单链表中某个结点,则语句p -> next =p -> next -> next的作用是________________。

18.假设元素只能按a,b,c,d的顺序依次进栈,且得到的出栈序列中的第一个元素为c,则可能得到的出栈序列为________________,不可能得到的出栈序列为________________。

19.若链串结点中的指针占4个字节,每个字符占1个字节,则结点大小为2的链串的存储密度为________________。

20.右图表示的广义表为________________。

21.若一棵满三叉树中含有121个结点,则该

树的深度为________________。

22.若以邻接矩阵表示有向图,则邻接矩阵上

第i行中非零元素的个数即为顶点v i的________________。

23.若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素,并且要求排序过程中所进行的关键字比较次数尽可能少,则应该选用________________排序方法。

24.在含20个关键字的3阶B树(2-3树)上查找一个关键字,至多需要访问___________次外存。

25.文件上的两类主要操作为________________和________________。

三、解答题(本大题共4小题,每小题5分,共20分)

26.设栈S1的入栈序列为1 2 3 4(每个数字为13个元素),则不可能得

到出栈序列3142。但可通过增设栈S2来实现。例如,按下图中的箭头

指示,依次经过栈S1和S2,便可得到序列3 1 4 2。

如果用H1和H2分别表示栈S1和S2的进栈操作,用P1和P2分别表

示两个栈的出栈操作,则得到3 1 4 2的一个操作步骤为

H1,H1,H1,P1,H2,P2,P1,H2,P1,H2,P2,H1,P1,H2,P2,P2

请仿照上例写出利用两个栈从1 2 3 4得到4 1 3 2的操作步骤。

27.已知树如右图所示,

(1)写出该树的后序序列;

(2)画出由该树转换得到的二叉树。

28.为关键字(17,33,31,40,48)构造一个长度为7的散列表,设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是

hi = (h(key) + i(key%5+1))%7 0≤i≤6

(1)画出构造所得的散列表;

(2)求出在等概率情况下查找成功时的平均查找长度。

29.已知R[1..8]中的元素依次为(12,5,9,20,6,31,24,27),写出按算法MergeSortDC对R进行自顶向下的二路归并排序过程中,前5次调用函数Merge(R, low, mid, high)时参数low, mid 和high的值。

void MergeSortDC (int R[], int low, int mid, int high )

{

int mid;

if (low

{

mid = (low +high)/2;

MergeSortDC (R, low, mid);

MergeSortDC (R, mid+1, high);

Merge (R, low, mid, high);

}

} // MergeSortDC

(1)第一次调用时的参数值;

(2)第二次调用时的参数值;

(3)第三次调用时的参数值;

(4)第四次调用时的参数值;

(5)第五次调用时的参数值;

四、算法阅读题(本大题共4小题,每小题5分,共20分)

30.下列函数的功能是,对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操作:将所有在Lb表中存在而La表中不存在的结点插入到La中,其中La和Lb分别为两个链表的头指针。

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

void union (LinkList La, LinkList Lb) {

//本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中

LinkList pre = La, q;

LinkList pa = La -> next;

LinkList pb = Lb -> next;

free (Lb);

while (pa && pd)

{

if (pa -> data data)

{ pre = pa; pa = pa ->

next;}

else if (pa -> data > pb

->data)

{

(1) ;

pre = pb;

pb = pb -> next;

(2) ;

}

else

{

q = pb; pb = pb -> next;

free (q);

}

}

if (pb)

(3) ;

}

31.已知串的存储结构为动态存储分配的顺序串。阅读下列算法,并回答问题:

(1)写出执行函数调用strc (s, r)的返回结果,其中s=〃aba〃, r=〃abababa〃;

(2)简述函数strc的功能。

int strc (HString * sub, HString * str)

{

int i=0, j, k, count =0;

while (i < str -> length – sub -> length +1)

{

j=i; k=0;

while (k length && str -> ch[j] = =sub -> ch[k] )

{

j++; k++;

}

if (k = = sub -> length)

{count ++; i=j-sub -> length +1;}

else i++;

}

return count;

}

32.下列函数MDFSForest的功能是,对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历,输出所得深度优先生成森林中各条边。请在空缺处填入合适内容,使其成为一个完整的算法。

#define MaxMun 20 //图的最大顶点数typedef struct {

char vexs [MaxNum]; //字符类型的顶点表

int edges [MaxNum][MaxNum]; //邻接矩阵

int n, e; //图的顶点数和边数

}MGraph; //图的邻接矩阵结构描述

typedef enum {FALSE, TRUE} Boolean; Boolean visited [MaxNum];

void MDFSTree (MGraph *G, int i);

void MDFSForest (MGraph *G)

{

int i, k;

for (i=0; i n; i++)

visited [i] = (1) ; for (k = 0; k n; k++)

if (!visited [k]) MDFSTree (G,k); }

void MDFSTree (MGraph *G, int i)

{

int j;

visited [i]=TRUE;

for (j=0; j n; j++)

{

if ( (2) )

{

printf (〃<%c, %c>〃G -> vexs [i], G -> vexs [j]);

(3) ;

}

}

33.已知整形数组L[1..8]中的元素依次为(9,8,5,7,6,3,2,1),阅读下列函数,并写出执行函数调用sort(L, 8)时,对L进行的头两趟(pass分别为0和1)处理结果。

V oid sort (int R[],int n)

{

int pass = 0, k, exchange, x;

do {

k=pass%2+1;

exchange = 0;

while (k

{

if (R[k]>R[k+1])

{

x = R[k]; R[k] = R[k+1]; R[k+1] = x;

exchange =1;

}

K+=2

}

pass ++;

}while (exchange = = 1|| pass <=1);

}

第一趟(pass = 0):

第二趟(pass = 1):

五、算法设计题(本大题共10分)

34.已知二叉排序树中结点的关键字为整数,设计递归算法按递增有序性输出树中所有大于或等于给定值x的结点,并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构,其结点结构为:

1.B

2.C

3.B

4.A

5.C

6.D

7.D

8.B

9.C 10.B11.A 12.B 13.C 14.A 15.B

二、填空题

16.O(n2) 17. 删除p所指示的结点后面的结点

18. 可能:c b a d或c d b a、c b d a不可能:c a b d、c d a b、c a d b

19. 33.3% 20. 递归表21. 5 22. 出度23. 堆排序 24、425、检索和更新

三、解答题:

26. H1 H1 H1 H1 P1 H2 P2

P1 H2 P1 H2 P1 H2 P2

P2 H1 P2

P1 H2 P2

27、EBJKFGHICDA, 见下图。

次比较,找48需4次比较。

29、(1) R,1,4,8 (2) R,1,2,4 (3) R,5,6,8

(4) R,1,1,2 (5) R,3,3,4

四、算法阅读题:

30、pre->next=pb; pre->next=pa; pre->next=pb;

30、函数的返回结果为:3 返回sub子串在字符串str中出现的次数;

32、 false;

G->edges[i][j]!=0 && !visited[j]

MDFSTree(G,j);

33、这是一个奇偶排序的算法。

第一趟:8 9 5 7 3 6 1 2第二趟:8 5 9 3 7 1 6 2

五、算法题目:

假设BinNode是如图所示的结点类型,BinTree是指向树根的指针类型;

int tongji(Bintree T, DataType x)

{ int count1,count2,count;

if (T)

{

count1=tongji(T->lchild,x);

if(T->data>=x) { printf(T->data); count=1;}

count2=tongji(T->rchild,x);

} return count+count1+count2;

else return 0;

}

也可以写成下面的形式:首先定义全局变量count,并赋初值0。

int count=0;

void tongji(Bintree T, DataType x)

{ if (T)

{

tongji(T->lchild,x);

if(T->data>=x) { printf(T->data); count++;}

tongji(T->rchild,x);

}

}

2004.1B

数据结构-数据结构历年考题及答案2

中国矿业大学2011-2012学年 《数据结构》试卷(A卷)(考试时间:100分钟) 一. 填空(每空2分,共40分) 1. 数据结构式具有相同性质的数据元素的(1)。 2. 通常程序在调用另一个程序时,都需要使用一个(2)来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A,每个元素用相邻的6个字节存储,存储器按字节编址,已知A的起始存储地址(基址)为1000,在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__(3)_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点,左孩子是第 (6) 个节点。如果该二叉树有10层,则共有 (7) 个节点。 5. 请描述在循环队列Q中,队头和队尾指针分别由front和rear表示,该队列有10个存储空间,判断队空和队满的条件分别分:_____(8)________,_______(9)_________。 6. 字符串t=”child”,s=”cake”,请写出下列函数的结果:StrLength(t) =(10)__;Concat(SubString(s,3,1),SubString(t,2,2))=____(11)___。 7. 一棵二叉树为 则后序序列为(12),中序序列为(13),先序序列为__(14)____。 8. 请用数据序列{53,17,12,66,58,70,87,25,56,60 }构造一棵二叉排序树_(15)_。 9.。一个栈输入的序列式1,2,3,则可能的且以2为开头的输出序列是 (16) ,不可能的序列是____(17)____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据:2,3,4,8,9,11,13查找11,若采用折半查找法,则在(19)次比较后,才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中,平均情况下(20)_____最快。 二简答题: 1给定{15,3,14,2,6,9,16,17},试为这8个数设计哈夫曼编码,并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。(要求使用图画出每一步过程)。 C G E D F B H A

自考数据结构试题真题

全国2011年1月高等教育自学考试 数据结构试题 课程代码:02331 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是() A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是() A.n-1 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为m,队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置,则向队列中插入新元素时,修改指针的操作是() A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时,处理参数及返回地址,应采用的数据结构是() A.堆栈 B.多维数组 C.队列 D.线性表 5.设有两个串p和q,其中q是p的子串,则求q在p中首次出现位置的算法称为() A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表A,若head(A)等于tail(A),则表A为() A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反,则该二叉树一定是 ()A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树

C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3,度为2的结点个数是4,则该二叉树叶子结点的个数是() A.4 B.5 C.7 D.8 9.下列叙述中错误的是() A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10.已知有向图G=(V,E),其中V={V1,V2,V3,V4},E={},图G的拓扑序列是() A.V1,V2,V3,V4 B.V1,V3,V2,V4 C.V1,V3,V4,V2 D.V1,V2,V4,V3 11.平均时间复杂度为O(n log n)的稳定排序算法是() A.快速排序 B.堆排序 C.归并排序 D.冒泡排序 12.已知关键字序列为(51,22,83,46,75,18,68,30),对其进行快速排序,第一趟划分完成后的关键字序列是() A.(18,22,30,46,51,68,75,83) B.(30,18,22,46,51,75,83,68) C.(46,30,22,18,51,75,68,83) D.(30,22,18,46,51,75,68,83) 13.某索引顺序表共有元素395个,平均分成5块。若先对索引表采用顺序查找,再对块中元素进行顺序查找,则在等概率情况下,分块查找成功的平均查找长度是()A.43 B.79 C.198 D.200 14.在含有10个关键字的3阶B-树中进行查找,至多访问的结点个数为() A.2 B.3 C.4 D.5 15.ISAM文件系统中采用多级索引的目的是() A.提高检索效率 B.提高存储效率

计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6

计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6 (总分:60.00,做题时间:90分钟) 一、单项选择题(总题数:14,分数:28.00) 1.为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009年 全国试题1(2)分】 A.栈 B.队列√ C.树 D.图 2.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,j,g=g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是( )。【2009年全国试题2(2)分】 A.1 B.2 C.3 √ D.4 按元素出队顺序计算栈的容量。b进栈时栈中有a,b出栈,cd进栈,栈中有acd,dc出栈,ef进栈,栈 中有aef,fea出栈,栈空,g进栈后出栈。所以栈S的容量至少是3。 3.若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈操作,则不可能得到的出栈序列是( )。【2010年全国试题1(2)分】 A.d,c,e,b,f,a B.c,b,d,a,e,f C.b,c,a,e,f,d D.a,f,e,d,c,b √ 4.某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素a,b,c,d,e依次入此队列后再进行出队操作,则不可能得到的出队序列是( )。【2010年全国试题2(2)分】 A.b,a,c,d, e B.d,b,a,c,e C.d,b,c,a,e √ D.e,c,b,a,d a先入队,b和c可在a的任一端入队,选项A、B、D都符合要求,只有选项C不可能出现。双端队列出队结果的分析可参见四、36。 5.元素a,b,c,d,e依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d开头的序列个数是( )。【2011年全国试题2(2)分】 A.3 B.4 √ C.5 D.6 元素d进栈时,元素a,b,c已在栈中,d出栈后,P可以在a,b,c任一元素的前面进栈并出栈,也可以在元素a后出栈,c,b,a必须依次出栈,所以元素d开头的序列个数是4。 6.已知循环队列存储在一维数组A[0.n-1]中,且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空,且要求第1个进入队列的元素存储在A[0]处,则初始时front和rear的值分别是( )。[2011年全国试题3(2)分】 A.0,0 B.0,n—1 √ C.n一1,0

计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编6

计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编 6 (总分:88.00,做题时间:90分钟) 一、单项选择题(总题数:33,分数:66.00) 1.一棵完全二叉树又是一棵( )。【华中科技大学2006一、7(2分)】 A.平衡二叉树 B.堆√ C.二叉排序树 D.哈夫曼(Huffman)树 完全二叉树的叶子至多在下面两层上,且一个结点若无左子树,绝不能有右子树。平衡二叉树任何结点的左右子树的高度差的绝对值不超过1,但其结点的值符合二叉排序树的定义。平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。堆是一个序列,有大堆和小堆,编号为i的结点,其父结点、左右子女结点之间位置的关系,符合完全二叉树父结点、左右子女结点之间的关系,从这点上说,可以把堆看成完全二叉树。哈夫曼树是二叉树,但树形不一定满足完全二叉树的定义。 2.一棵左子树为空的二叉树在先序线索化后,其中空的链域的个数是( )。【合肥工业大学1999一、5(2分)】 A.不确定 B.0 C.1 D.2 √ 左子树为空的二叉树的根结点的左线索为空(无前驱),先序序列的最后结点的右线索为空(无后继),共2个空链域。 3.一棵左右子树均不空的二叉树在先序线索化后,其中空的链域的个数是( )。【合肥工业大学2000一、5(2分)】 A.0 B.1 √ C.2 D.不确定 4.若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则X的前驱为( )。【南京理工大学1996 一、6(2分)】 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点√ D.X的左子树中最右叶结点 5.引入二叉线索树的目的是( )。【南京理工大学1998一、5(2分)】 A.加快查找结点的前驱或后继的速度√ B.为了能在二叉树中方便地进行插入与删除 C.为了能方便地找到双亲 D.使二叉树的遍历结果唯一 6.线素二叉树是一种( )结构。【西安电子科技大学1996一、9(2分)】 A.逻辑 B.逻辑和存储 C.物理√ D.线性 7.甩个结点的线索二叉树上含有的线索数为( )。【中山大学1998二、8(2分)】

自考02331数据结构重点总结(最终修订)

自考02331数据结构重点总结(最终修订) 第一章概论 1.瑞士计算机科学家沃思提出:算法+数据结构=程序。算法是对数据运算的描述,而数据结构包括逻辑结构和存储结构。由此可见,程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构。 2.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成,数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。 3.数据结构指的是数据元素之间的相互关系,即数据的组织形式。 数据结构一般包括以下三方面内容:数据的逻辑结构、数据的存储结构、数据的运算 ①数据的逻辑结构是从逻辑关系上描述数据,与数据元素的存储结构无关,是独立于计算机的。 数据的逻辑结构分类:线性结构和非线性结构。 线性表是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。 ②数据元素及其关系在计算机内的存储方式,称为数据的存储结构(物理结构)。 数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。 ③数据的运算。最常用的检索、插入、删除、更新、排序等。 4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储 (1)顺序存储:通常借助程序设计语言的数组描述。 (2)链接存储:通常借助于程序语言的指针来描述。 (3)索引存储:索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。 (4)散列存储:该方法的基本思想是:根据元素的关键字直接计算出该元素的存储地址。 5.算法必须满足5个准则:输入,0个或多个数据作为输入;输出,产生一个或多个输出;有穷性,算法执行有限步后结束;确定性,每一条指令的含义都明确;可行性,算法是可行的。 算法与程序的区别:程序必须依赖于计算机程序语言,而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类:类Pascal和类C。 6.评价算法的优劣:算法的"正确性"是首先要考虑的。此外,主要考虑如下三点: ①执行算法所耗费的时间,即时间复杂性; ②执行算法所耗费的存储空间,主要是辅助空间,即空间复杂性; ③算法应易于理解、易于编程,易于调试等,即可读性和可操作性。

数据结构历年真题收集第1章 绪论(含答案)

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的()。【北京邮电大学2000 二、3 (20/8分)】 A.效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于()【中科院计算所 1998 二、1 (2分)】 A.问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是(1),它必须具备(2)这三个特性。 (1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1(2分)【武汉交通科技大学 1996 一、1( 4分)】4.一个算法应该是()。【中山大学 1998 二、1(2分)】 A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和C. 5. 下面关于算法说法错误的是()【南京理工大学 2000 一、1(1.5分)】 A.算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是()【南京理工大学 2000 一、2 (1.5分)】 (1)算法原地工作的含义是指不需要任何额外的辅助空间 (2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界 (4)同一个算法,实现语言的级别越高,执行效率就越低 A.(1) B.(1),(2) C.(1),(4) D.(3) 7.从逻辑上可以把数据结构分为()两大类。【武汉交通科技大学 1996 一、4(2分)】A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 8.以下与数据的存储结构无关的术语是()。【北方交通大学 2000 二、1(2分)】A.循环队列 B. 链表 C. 哈希表 D. 栈 9.以下数据结构中,哪一个是线性结构()?【北方交通大学 2001 一、1(2分)】A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10.以下那一个术语与数据的存储结构无关?()【北方交通大学 2001 一、2(2分)】A.栈 B. 哈希表 C. 线索树 D. 双向链表 11.在下面的程序段中,对x的赋值语句的频度为()【北京工商大学 2001 一、10(3分)】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A. O(2n) B.O(n) C.O(n2) D.O(log2n) 12.程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1]

自考数据结构公式汇总

自考数据结构公式汇总 1.O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、 O(n3)、O(n k)、O(2n)。 2.在顺序表中第i个位置插入一个结点的移动次数为n-i+1,插入平均移动n/2次,删 除顺序表第i个结点移动次数为n-i,平均移动(n-1)/2次。 3.定义变量p=(LinkList)malloc(sizeof(ListNode))或 p=(LinkNode*)malloc(sizeof(ListNode)) 4.单循环链表判断空:head= =head->next 5.共享向量空间判断满top1=top2-1 6.入队EnQueue,出队DeQueue,front=rear空队列,循环队列克服假上溢 7.循环队列判断队满(rear+1)%m=front,循环队列指针移动方向顺时针。判队列长度 (rear-front+m)%m 8.链队列判空:Q->front=Q->rear=NULL 9.求串长strlen,串复制strcpy(to,from),联接strcat(to,from),串比较strcmp(s1 大就大于s1小就小于,小写字母>大写字母),字符定位strchr 10.串的子串定位(模式匹配)下标从0开始,最坏情况下时间复杂度比较次数 O((n-m+1)m) 11.二维数组下标为0公式:行优先LOC(a00)+[i*n+j]*d,列优先LOC(a00)+[j*m+i]*d 12.三维数组下标为0公式:三维数组A mnp按行优先LOC(a ijk)=LOC(a000)+[i*n*p+j*p+k]*d 13.对称矩阵一共有n(n+1)/2个元素,存储位置 k=I*(I+1)/2+J(I=max(i,j),J=min(i,j))下标0开始 14.上三角矩阵:k=i*(2n-i+1)+j-i,下三角矩阵:k=i*(i+1)/2+j。上三角i>j下三角 i(k-1)/2,则元素a ij=0 16.三元组表组成:i(行)j(列)v(值),转置时间复杂度O(m*n),带行表的三元组表是一 种顺序存储结构。

自考数据结构 试题及答案解析

2015年lO月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共8页。满分l00分。考试时间l50分钟。 考生答题注意事项: 1.本卷所有试题必须在答题卡上作答。答在试卷上无效,试卷空白处和背面均可作草稿纸. 2.第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3.第二部分为非选择题。必须注明大、小题号,使用0.5毫米黑色字迹签字笔作答。 4.合理安排答题空间.超出答题区域无效。 第一部分选择题 一、单项选择题(本大题共l5小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题卡” 的相应代码涂黑。未涂、错涂或多涂均无分。

1.下列选项中,不属于线性结构的是 A.网 B.栈 C.队列 D.线性表 2.长度为n的顺序表,删除位置i上的元素(0≤i≤n一1),需要移动的元素个数为 A.n—i B.n—i—l C.i D.i+1 3.栈采用不同的存储方式时,下列关于出栈过程的叙述中,正确的是 A.顺序栈需要判定栈空,链栈也需要判定 B.顺序栈需要判定栈空,而链栈不需要判定 C.顺序栈不需要判定栈空,而链栈需要判定 D.顺序栈不需要判定栈空,链栈也不需要判定 4.若一个栈以数组V[0..n-1]存储,初始栈顶指针top为n,则x入栈的正确操作是 A.top=top+1;V[top]=x B.V[top]=x;top=top+1 C.top=top一1;V[mp]=x D.V[top]=x;top=top—l 5.在二维数组a[9][10]中:每个数组元素占用3个存储空间,从首地址SA开始按行优先

计算机专业基础综合数据结构(概论)历年真题试卷汇编3

计算机专业基础综合数据结构(概论)历年真题试卷汇编3 (总分:70.00,做题时间:90分钟) 一、单项选择题(总题数:15,分数:30.00) 1.设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。【2011年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1年全国试题1(2分)】 x=2; while(x *x; (分数:2.00) A.O(log 2 n) √ B.O(n) C.O(nlog 2 n) D.O(n 2 ) 解析: 2.求整数n(n≥0)阶乘的算法如下,其时间复杂度是( )。【2012年全国试题1(2分)】int fact(int n){if(n<=i) return i;return n*fact(n一1); (分数:2.00) A.O(log 2 n) B.O(n) √ C.O(nlog 2 n) D.O(n 2 ) 解析: 3.已知两个长度分别为m和n的升序链表,若将它们合并为一个长度为m+n的降序链表,则最坏情况下的时间复杂度是( )。【2013年全国试题1(2)分】 (分数:2.00) A.O(n) B.O(m×n) C.O(min(m,n)) D.O(max(m,n)) √ 解析: 4.下列程序段的时间复杂度是( )。【2014年全国试题1(2分)】count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++; (分数:2.00) A.O(log 2 n) B.O(n) C.O(nlog 2 n) √ D.O(n 2 ) 解析: 5.在数据结构中,数据的最小单位是( )。【北京理工大学2006九、1(1分)】 (分数:2.00) A.数据元素 B.字节 C.数据项√ D.结点 解析: 6.在数据结构中,数据的基本单位是( )。【北京理工大学2004五、1(1分)】 (分数:2.00) A.数据项 B.数据类型 C.数据元素√

全国2014年4月自考数据结构真题

绝密★考试结束前 全国2014年4月高等教育自学考试 数据结构试题 课程代码:02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项: 1.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸” 的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关 ..的概念是 A.栈 B.链表 C.顺序表 D.二叉链表 2.顺序表中有10个数据元素,若第一个元素的存储地址是1000,则最后一个元素地址是1036,第5个元素的地址是 A.1010 B.1016 C.1018 D.1019 3.设栈的初始状态为空,元素1、2、3、4、5、6依次入栈,得到的出栈序列是(2,4,3,6,5,1),则栈的容量至少是 A.2 B.3 C.4 D..6 4.下列关于队列的叙述中,错误 ..的是 A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 1

D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 B.节省存储空间 C.便于输入输出 D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14 B.64 C.127 D.128 7.下列选项为完全二叉树的是 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e B. e C. 2e D. n+e 9.无向图中所有顶点的度数之和与所有边数之比是 A.1/2 B.1 C.2 D.4 10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 11.对序列(15,9,7,8,20,-1,4)进行排序,若一趟排序后的结果为(-1,15,9,7,8,20,4),则采用的排序方法是 A.归并排序 B.快速排序 C.直接选择排序 D.冒泡排序 12.比较次数与待排序列初始状态无关的排序方法是 A.快速排序 B.冒泡排序 C.直接插入排序 D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找 B.二分查找 C.顺序查找 D.折半查找 14.下列关于m阶B树的叙述中,错误 ..的是 2

计算机考研数据结构统考历年真题

目前刚整理了2009-2015的试题过几天2016的也会上传上去 希望对你有帮助。。。。。。。 2009 1.为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图 2.设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量至少是 A.1 B.2 C.3 D.4 3.给定二叉树图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是 A.LRN B.NRL C.RLN D.RNL 4.下列二叉排序树中,满足平衡二叉树定义的是 5.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是 A.39 B.52 C.111 D.119 6.将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的

父结点,则在原来的森林中,u和v可能具有的关系是I.父子关系 II.兄弟关系 III.u的父结点与v的父结点是兄弟关系 A.只有II B.I和II C.I和III D.I、II和III 7.下列关于无向连通图特性的叙述中,正确的是 I.所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1 A.只有I B.只有II C.I和II D.I和III 8.下列叙述中,不符合m阶B树定义要求的是 A.根节点最多有m棵子树 B.所有叶结点都在同一层上 C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接 9.已知关键序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后得到的小根堆是 A.3,5,12,8,28,20,15,22,19 B.3,5,12,19,20,15,22,8,28 C.3,8,12,5,20,15,22,28,19 D.3,12,5,8,28,20,15,22,19 10.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是 A.起泡排序 B.插入排序 C.选择排序 D.二路归并排序 41.(10分)带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:

计算机专业基础综合数据结构(图)历年真题试卷汇编3

计算机专业基础综合数据结构(图)历年真题试卷汇编3 (总分:58.00,做题时间:90分钟) 一、综合题(总题数:23,分数:58.00) 1.给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列;(2)给出从顶v1,1开始,对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分)】 __________________________________________________________________________________________ 正确答案:(正确答案:(1)v 1 v 2 v 4 v 3 v 5 v 6 (2) v 1 v 2 v 3 v 4 v 5 v 6) 给出图G 4.00) (1).画出G的邻接表表示图; __________________________________________________________________________________________ 正确答案:( (2).根据你画出的邻接表,以顶点①为根,画出G的深度优先生成树和广度优先生成树。【南开大学1997五(14分)】【烟台大学2007四、3(15分)】 __________________________________________________________________________________________ 正确答案:( 2.已知一个有向图如图所示,则从顶点a出发进行深度优先遍历,写出所有可能得到的DFS 京交通大学2006四、4(5分)】 __________________________________________________________________________________________ 正确答案:(正确答案:共8个:adbcfe,adbfce,adcbfe,adcebf adcefb,adebcj,adebfc,adefbc) 2000计算机应用六(10分)】(分数:4.00) (1).如果每个指针需要4字节,每个顶点的标号占2字节,每条边的权值占2字节。下图采用哪种表示法所需的空间较多?为什么? __________________________________________________________________________________________ 正确答案:(正确答案:邻接矩阵:(6*6个元素)*2字节/元素=72字节邻接表:表头向量6*(4+2)+边结点9*(2+2+4)*2=180字节邻接多重表:表头向量6*(4+2)+边结点9*(2+2+2+4+4)=162字节邻接表占用空间较多,因为边较多,边结点又是边数的2倍,一般来说,邻接矩阵所占空间与边个数无关(不考虑压缩存储),适合存储稠密图,而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数,但结点中增加了一个顶点下标域和一个指针域。) (2).写出下图从顶点1开始的:DFS树。 __________________________________________________________________________________________ 正确答案:(正确答案:因未确定存储结构,从顶点1开始的DFS 3.如下所示的连通图,请画出:(1)以顶点①为根的深度优先生成树;(5分)(2)如果有关节顶点,请找出 所有的关节顶点。(5分)【清华大学l 998七(10分)】 __________________________________________________________________________________________ 正确答案:(正确答案:(1)未确定存储结构,其DFS树不唯一,其中之一(按邻接点逆序排列) 关节顶点有3,1,8,7,2。)

全国自学考试数据结构导论试题及答案(4套)

全国2011年1月自学考试数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在顺序表中查找第i个元素,时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n) 2.树形结构中,度为0的结点称为( ) A.树根 B.叶子 C.路径 D.二叉树 3.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={,,,},则图G的拓扑序列是 ( ) A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7 4.有关图中路径的定义,表述正确的是( ) A.路径是顶点和相邻顶点偶对构成的边所形成的序列 B.路径是不同顶点所形成的序列 C.路径是不同边所形成的序列 D.路径是不同顶点和不同边所形成的集合 5.串的长度是指( ) A.串中所含不同字母的个数 B.串中所含字符的个数 C.串中所含不同字符的个数 D.串中所含非空格字符的个数 6.组成数据的基本单位是( ) A.数据项 B.数据类型 C.数据元素 D.数据变量 7.程序段 i=n;x=0; do{x=x+5*i;i--;}while (i>0); 的时间复杂度为( ) A.O(1) B.O(n) C.O(n2) D.O(n3) 8.与串的逻辑结构不同的 ...数据结构是( ) A.线性表 B.栈 C.队列 D.树

全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构考点归纳与典型题(含历年真题)详解-第一章

第1章绪论 1.1考点归纳 【考纲指定考点】 本章初步了解数据结构的基本概念。分析算法的时间复杂度和空间复杂度是本章的重点。 一、数据结构的基本概念 1.基础概念和术语 (1)数据(Data):数据是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。 (2)数据元素(Data Element):数据元素是数据的基本单位,在程序中通常作为一个整体来进行考虑和处理。 (3)数据项(Data Item):数据项是数据的不可分割的最小单位,数据项是对客观事物的某一方面的数据描述。一个数据元素可由若干个数据项(Data Item)组成。 (4)数据对象(Data Object):数据对象是性质相同的数据元素的集合,是数据的一个子集。如字符集合C={‘A’,‘B’,‘C’,…}。 (5)数据结构(Data Structure):数据结构是指相互之间存在一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。 2.数据结构的形式定义

数据结构的形式定义是一个二元组: Data Structure=(D,S) 其中D是数据元素的有限集,S是D上关系的有限集。 数据元素之间的关系可以是元素之间本身代表的某种自然关系,也可以是为了处理问题方便而人为定义的关系,这种自然或人为定义的关系称为数据元素之间的逻辑关系,相应的结构称为逻辑结构。 3.数据结构的组成 数据结构的三个组成部分: (1)逻辑结构 数据元素之间的逻辑关系的描述。数据元素之间的逻辑结构有四种基本类型: ①集合:结构中的数据除了“同属于一个集合”外,没有其它关系。 ②线性结构:结构中的数据元素之间存在一对一的关系。 ③树形结构:结构中的数据元素之间存在一对多的关系。 ④图形结构或网状结构:结构中的数据元素之间存在多对多的关系。 (2)存储结构 数据结构在计算机中的实际表达方式,它包括对数据元素的表示和对关系的表示。存储结构主要有:顺序存储、链式存储、索引存储和散列存储。 ①顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构。数据元素存放的地址是连续的。其优点是可以实现随机存取,存储空间小;缺点是只能使用相邻的一整块存储单元,容易产生碎片。 ②链式存储结构:在每一个数据元素中增加一个存放另一个元素地址的指针,用该指针

数据结构历年试题及答案

一、单项选择题 1.算法指的是( D ) D .解决问题的有限运算序列 2.线性表采用链式存储时,结点的存储地址( B )B .连续与否均可 3.将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为( C ) A .O (1) B .O (n ) C .O (m ) D .O (m+n ) 4.由两个栈共享一个向量空间的好处是:( B ) B .节省存储空间,降低上溢发生的机率 5.设数组data[m]作为循环队列SQ 的存储空间,front 为队头指针,rear 为队尾指针,则执 行出队操作后其头指针front 值为( D ) D .front=(front+1)%m 6.如下陈述中正确的是( A ) A .串是一种特殊的线性表 7.若目标串的长度为n ,模式串的长度为[n/3],则执行模式匹配算法时,在最坏情况下的 时间复杂度是( C ) C .O (n 2) 8.一个非空广义表的表头( D ) D .可以是子表或原子 9 对应的稀疏矩阵是( A ) ????????????? ???--0000040 5000000076080.A 10.在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个 数为( C ) C .6 11.在含n 个顶点和e 条边的无向图的邻接矩阵中,零元素的个数为( D ) D .n 2-2e 12.假设一个有n 个顶点和e 条弧的有向图用邻接表表示,则删除与某个顶点v i 相关的所有 弧的时间复杂度是( C ) C .O(n+e) 13.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时, 序列的变化情况如下: 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84 则所采用的排序方法是( D ) D .快速排序 14.适于对动态查找表进行高效率查找的组织结构是( C ) C .三叉排序树 15.不定长文件是指(B ) B .记录的长度不固定 二、填空题 16.数据的逻辑结构是从逻辑关系上描述数据,它与数据的 存储(存储结构) 无关,是独立于计算机的。 17.在一个带头结点的单循环链表中,p 指向尾结点的直接前驱,则指向头结点的指针head 可用p 表示为head= p->next->next 。 18.栈顶的位置是随着 进栈和退栈 操作而变化的。 19.在串S=“structure ”中,以t 为首字符的子串有 12 个。

自考《数据结构》真题和答案

2016年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共7页,满分100分,考试时间150分钟。 考生答题注意事项: 1 ?本卷所有试题必须在答题卡上作答。答在试卷上无效,试卷空白处和背面均可作草稿纸 2. 第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑' 3. 第二部分为非选择题。毖须注明大、小题号,使用0. 5毫米黑色字迹签字笔作答。 4 ?合理安排答题空间,超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共15小题,每小题2分,共30分> 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1. 下列选项中,不属于线性结构特征的是 A.数据元素之间存在线性关系 B .结构中只有一个幵始结点 C.结构中只有一个终端结点 D .每个结点都仅有一个直接前趋

2. 设17个元素的顺序表中,若将第个元素e 移动到第个位置,

不改变除e外其他元素之间的相对次序,则需移动的表中元素个数是 A. AM B, i-i C.上汁】D讨3 .若用一个大小为7的数组作为循环队列的存储结构,且当前rew和盘Ont的值分别 为2和4,在此之前的操作是从队列中删除了一个元素及加入两个元素,请问这3 个操作之前rear和矗Ont的值分别是 A. 0 和I B . 0 和3 C . 3 和6 D . 4 和5 4 .已知广义表LS=(((a)) , ((b , (c)) , (d , (e , f))) , 0) , LS 的长度是 A. 2 B . 3 C . 4 D. 5 5.—棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点 于中包含的结点数是 A. k B. 2k-1 C k2 D .2k-1 6.如果某二叉树的前序遍历序列为abced,中序遍历序列为cebda,则该二叉树的后序遍历序列是 A. cedba B decba C ecdba D . ecbad 7.—个森林有m棵树,顶点总数为n,则森林中含有的总边数是 A. m B. n-l C n-m n+m 8.设图的邻接矩阵A如下所示。各顶点的度依次是

第一部分“数据结构”历年真题

第一部分“数据结构”历年真题 一、选择题 1、(05-9-2)下列数据结构中,能用二分法进行查找的是() A)顺序存储的有序线性表B)线性链表 C)二叉链表D)有序线性链表 2、(05-9-3)下列关于栈的描述正确的是() A)在栈中只能插入元素而不能删除元素B)在栈中只能删除元素而不能插入元素 C)栈是特殊的线性表,只能在一端插入或删除元素 D)栈是特殊的线性表,只能在一端插入元素,而在另一端删除元素 3、(05-9-4)下列叙述正确的是() A)一个逻辑数据结构只能有一种存储结构 B)数据的逻辑结构属于线性结构,存储结构属于非线性结构 C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率 D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率 4、(08-9-3)在长度为n的有序线性表中进行二分查找,最坏情况下需要比较的次数是() A)O(N) B)O(n2) C)O(log2n)D)O(n log2n) 5、(06-4-4)按照“后进先出”的原则组织数据的数据结构是 A)队列B)栈C)双向链表D)二叉树 6、(06-4-5)下列叙述中正确的是() A)线性链表是线性表的链式存储结构B)栈与队列是非线性结构 C)双向链表是非线性结构D)只有根结点的二叉树是线性结构 7、(06-4-6)对如下二叉树 进行后序遍历的结果为() A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA 8、(06-4-7)在深度为7的满二叉树中,叶子结点的个数为()

A )32 B )31 C )64 D )63 9、(06-9-7)下列叙述中正确的是( ) A )一个算法的空间复杂度大,则其时间复杂度也必定大 B )一个算法的空间复杂度大,则其时间复杂度必定小 C )一个算法的时间复杂度大,则其空间复杂度必定小 D )上述三种说法都不对 10、(06-9-8)在长度为64的有序线型表中进行顺序查找,最坏情况下需要比较的次数为( ) A )63 B )64 C )6 D )7 11、(06-9-10) 进行中序遍历的结果是( ) A )ACBDFEG B )ACBDFGE C ) ABDCGEF D )FCADBEG 12、(07-4-1)下列叙述中正确的是( ) A )算法的效率只与问题的规模有关,而与数据的存储结构无关 B )算法的时间复杂度是指执行算法所需要的计算工作量 C )数据的逻辑结构与存储结构是一一对应的 D )算法的时间复杂度与空间复杂度一定相关 13、(07-4-5)下列对队列的叙述正确的是( ) A )队列属于非线性表 B )队列按“先进后出”原则组织数据 C )队列在队尾删除数据 D )队列按“先进先出”原则组织数据 14、(07-4-6)对下列二叉树

相关文档
相关文档 最新文档