全国2011年1月自学考试数据结构试题

课程代码：02331

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.下列选项中与数据存储结构无关的术语是（ D ）P3 A.顺序表 C.链队列

B.链表 D.栈

2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（ B ） A.n-1 C.2n-1

B.n D.2n

3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ D ） A.rear=(rear-1)%m; C.front=(front-1)%m;

B.front=(front+1)%m; D.rear=(rear+1)%m;

4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（ A ） A.堆栈 C.队列

B.多维数组 D.线性表

5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（ C ） A.求子串 C.串匹配

B.串联接 D.求串长

6.对于广义表A，若head(A)等于tail(A)，则表A为（ B ）P67 A.( ) C.(( ),( ))

B.(( )) D.(( ),( ),( ))

7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是

（ C ）

A.结点均无左孩子的二叉树 C.高度为n的二叉树

B.结点均无右孩子的二叉树 D.存在度为2的结点的二叉树

8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（ B ）P73 A.4 C.7

9.下列叙述中错误的是（ C ）

A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次P107 B.图的遍历可以采用深度优先遍历和广度优先遍历

第 1 页

B.5 D.8

C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程

10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={，，，，}，图G的拓扑序列是（ ） A.V1,V2,V3,V4 C.V1,V3,V4,V2

B.V1,V3,V2,V4 D.V1,V2,V4,V3

11.平均时间复杂度为O(n log n)的稳定排序算法是（ C ）P136 P164 8-2 A.快速排序 C.归并排序

B.堆排序 D.冒泡排序

12.已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（ D ）

A.(18,22,30,46,51,68,75,83) C.(46,30,22,18,51,75,68,83)

B.(30,18,22,46,51,75,83,68) D.(30,22,18,46,51,75,68,83)

13.某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是（ A ） A.43 C.198

B.79 D.200

14.在含有10个关键字的3阶B-树中进行查找，至多访问的结点个数为（ B ）即B-树的高度 A.2 C.4

B.3 D.5

15.ISAM文件系统中采用多级索引的目的是（ A ）P213 A.提高检索效率 C.减少数据的冗余

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

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

16.数据结构由数据的逻辑结构、存储结构和数据的_运算___________三部分组成。 17.在单链表中某结点后插入一个新结点，需要修改_______2________个结点指针域的值。

18.设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是_______3_________。

19.长度为零的串称为______空串__________。

20.广义表G=(a,b，(c，d，(e，f))，G)的长度为________4________。

21.一棵树T采用孩子兄弟链表存储，如果树T中某个结点为叶子结点，则该结点在二叉链表中所对应的结点一定是______左右指针域均为空__________。

第 2 页

B.提高存储效率 D.方便文件的修改

22.一个有n个顶点的无向连通图，最少有_____n-1___________条边。

23.当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是_______直接插入排序_________。

24.在一棵深度为h的具有n个结点的二叉排序树中，查找任一结点的最多比较次数是______h________。 25.不定长文件指的是文件的______记录含有的信息长度______大小不固定。 三、解答题（本大题共4小题，每小题5分，共20分）

26.已知一棵二叉排序树（结点值大小按字母顺序）的前序遍历序列为EBACDFHG， 请回答下列问题： (1) 画出此二叉排序树；

(2)

(3) 若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林。

27.已知有向图的邻接表如图所示，请回答下面问题： (1)给出该图的邻接矩阵；

(2)从结点A出发，写出该图的深度优先遍历序列。

第 3 页

28.已知待排记录的关键字序列为{25，96，11，63，57，78，44}，请回答下列问题： (1)画出堆排序的初始堆（大根堆）； (2)画出第二次重建堆之后的堆。

29.已知关键字序列为(56，23，41，79，38，62，18)，用散列函数H(key)=key将其散列到散列表HT[0..10]中，采用线性探测法处理冲突。请回答下列问题： (1)画出散列存储后的散列表：

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

四、算法阅读题（本大题共4小题，每小题5分，共20分） 30.阅读下列程序。

void f30(int A[]， int n) {

int i,j,m;

for (i=1；i

for (j=0；j

m=A[i*n+j]； A[i*n+j]=A[j*n+i]； A[j*n+i]=m； }

}

回答下列问题：

第 4 页

? 1 2 3???(1)已知矩阵B=? 4 5 6?，将其按行优先存于一维数组A中，给出执行函数调

?? 7 8 9??用f30(A，3)后矩阵B的值； (2)简述函数f30的功能。

31.假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { char data;

struct node*Ichild, *rchild; ∥左右孩子指针 } *BinTree； 阅读下列程序。 void f31(BinTree T) {

InitStack(S); ∥ 初始化一个堆栈S while (T || !StackEmpty(S) {

while (T) {

Push(S,T); T=T->lchild; }

if (!StackEmpty(S)) {

T=Pop(S); printf(“%c”,T->data); T=T->rchild; } } }

回答下列问题：

(1)已知以T为根指针的二叉树如图所示， 请写出执行f31(T)的输出结果：

第 5 页

(2)简述算法f31的功能。

32.阅读下列程序。

void f32(int A[],int n) {

int i,j,m=l,t；

for (i=0; i

for (j=0； j

for (j=1; j

if (A[j-1]>A[j]) { t=A[j-l]; A[j-1]=A[j]； A[j]=t； m=1； }

} } 回答问题：

已知整型数组A[ ]={34,26,15,89,42}，写出执行函数调用f32(A,5)后的输出结果。

33.已知顺序表的表结构定义如下： #define MAXLEN 100 typedef int KeyType;

第 6 页

typedef struct { KeyType key; InfoType otherinfo; } NodeType；

typedef NodeType SqList[MAXLEN]; 阅读下列程序。

Int f33(SqList R，NodeType X, int p, int q) { int m;

if (p>q) return -1; m=(p+q)／2；

if (R[m].key==X.key) return m; if (R[m].key>X.key) return f33(R,X,p,m-l); else return f33(R,X,m+l,q); }

请回答下列问题：

(1)若有序的顺序表R的关键字序列为(2,5，13,26,55,80,105)，分别写出X.key=18和X.key=26时，执行函数调用f33(R,X,0,6)的函数返回值。 (2)简述算法f33的功能。

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

34.假设用带头结点的单循环链表表示线性表，单链表的类型定义如下： typedef struct node { int data; struct node*next; }LinkNode，*LinkList;

编写程序，求头指针为head的单循环链表中data域值为正整数的结点个数占结点总数的比例，若为空表输出0，并给出所写算法的时间复杂度。函数原型为：

float f34(LinkList head):

第 7 页

全国2010年10月自学考试数据结构试题

课程代码：02331

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.数据的四种存储结构是( A )

A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构

2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是( C ) A.无头结点的单向链表 O(N) C.带头结点的双循环链表O(1)

B.带头结点的单向链表 O(N) D.带头结点的单循环链表O(N)

3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( B ) A.head=NULL

B.head->next=NULL

第 8 页

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

4.若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是( D ) A.n-i C.n-i+2

5.串匹配算法的本质是( C ) A.串复制 C.子串定位

B.串比较 D.子串链接 B.n-i+l D.无法确定

6.设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为( C ) A.13 B.18 C.33 D.40

7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树

D.树中非叶结点均只有右子树 8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( A ) A.n

B. C. +1 (完全二叉树)

D.n/2

9.在图G中求两个结点之间的最短路径可以采用的算法是( A ) A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.普里姆(Prim)算法

D.广度优先遍历(BFS)算法

（BC为求最小生成树）

10.下图G=(V,E)是一个带权连通图，G的最小生成树的权为( D ) A.15 B.16 C.17 D.18

11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( B ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7

第 9 页

B ) 12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( B ) A.不稳定的 C.基于交换的

B.稳定的 D.基于选择的

13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为( C ) A.1 B.2 C.3 D.4

14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( D

15.若需高效地查询多关键字文件，可以采用的文件组织方式为( D ) A.顺序文件 B.索引文件 C.散列文件

D.倒排文件

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

请每小题的空格中填上正确答案。错填、不填均无分。 16.下面程序段的时间复杂度为___________。

sum=1；

for（i=0；sum

sum+=1；

17.已知链表结点定义如下：

typedef struct node{

char data［16］； struct node *next; } LinkStrNode；

如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是___________。

第 10 页

)

18.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为___________。 19.3个结点可以组成___________种不同树型的二叉树。

20.用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。

21.若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为___________。 22.影响排序效率的两个因素是关键字的___________次数和记录的移动次数。 23.对任一m阶的B树，每个结点中最多包含___________个关键字。

24.若两个关键字通过散列函数映射到同一个散列地址，这种现象称为___________。 25.如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为___________。

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

26.要在［0..n-l］的向量空间中建立两个栈stackl和stack2，请回答： (1)应该如何设计这两个栈才能充分利用整个向量空间？

(2)若stackl的栈顶指针为topl,stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则： 栈stackl空的条件是：___________； 栈stack2空的条件是：___________；

栈stackl和栈stack2满的条件是：___________。

27.已知广义表如下： A=(B,y) B=(x，L) L=(a，b) 要求：

第 11 页

(1)写出下列操作的结果 tail(A)=_______________. head(B)=______________。 (2)请画出广义表A对应的图形表示。

28.已知二叉树如下：

请画出该二叉树对应的森林。29.请回答下列问题：

(1)英文缩写DAG的中文含义是什么？

(2)请给出下面DAG图的全部拓扑排序。第 12 页

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

30.已知线性表(a1,a2,a3...，an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为(x,x,-x,-x,x,x,-x)，变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容，使其成为完整的算法。 f30(int a［］，int n) { int k，m,temp；

m= (1) ；

while (a［m］<0 &&m

m= (2) ； k=m; while (k

{ while(a［k］>=0&&k

k= (3) ； if(k

{ temp=a［k］； a［k］=a［m］； a［m］= (4) ； m= (5) ； } } }

(1) (2) (3) (4) (5)

31.阅读下列程序，并回答问题： #include

substr(char*t,char*s,int pos,int len) { while（len>0&&*s）

{ *t=*(s+pos-l);

第 13 页

t++;s++;len--; } *t='\\0'; }

char *f31(char*s) { char t[100]; if (strlen(s)=1) return s; substr(t,s,1,1); substr(s,s,2,strlen(s)-1); f31(s); return strcat(s,t); } main( )

{ char str[100]= ''String''; printf(''%s\\n'',f31(str)); }

(1)请写出执行该程序后的输出结果； (2)简述函数f31的功能。

32.下面程序实现插入排序算法。 typedef struct{

int key; Info otherinfo; }SeqList;

void InsertSort(SeqList R［］,int n) {/* 待排序列保存在R［1..n］中*/

SeqList x； int i，j，k，lo,hi,mi; for (i=2；i<=n；i++) {

(1) ； lo=1；

第 14 页

hi=i-l;

while (lo<=hi) {

mi=(lo+hi)/2;

if ( (2) ) break; if (R［mi］.key>x.key) hi=mi-l; else lo=mi+l; }

if (mi=lo) k=i - mi; else k=i - mi-1; for (j=0；j

(3) ； R［i-j］=x； } }

在空白处填写适当的内容，使该程序功能完整。(1)

(2) (3)

33.设有单链表类型定义如下： typedef struct node {

int data;

struct node *next; } *LinkList;

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

void f33(LinkList head, int A, int B) {

LinkList p=NULL; While (head !=NULL) {

if (head->data>A&&head->data

p=head;

第 15 页

head=head->next; }

if (p !=NULL)

printf(\

}

(1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果；

(2)简述算法f33的功能。

五、算法设计题（本题10分） 34.已知二叉树的定义如下： typedef struct node{

int data;

struct node *lchild, *rchild; }*Bitptr；

编写递归算法求二叉树的高度。函数原型为：int f34（Bitptr t）；

全国2010年1月自学考试数据结构试题

课程代码：02331

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ） A．问题规模 B．语句条数 C．循环层数 D．函数数量 2．具有线性结构的数据结构是（ C ）

第 16 页

A．树 B．图 C．栈和队列 D．广义表

3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ B ） A．O(1) B．O(m) C．O(n) D．O(m+n)

4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ C ） A．2个 B．3个 ． C．4个 D．6个

5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ） A．3 B．37 C．50 D．97

6．若栈采用链式存储结构，则下列说法中正确的是（ B ） A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空 D．不需要判断栈满也不需要判断栈空

7．若串str=”Software”，其子串的数目是（ D ） A．8 B．9 C．36 D．37

8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ C ） A．1012 B．1017 C．1032 D．1039 9．允许结点共享的广义表称为（ D ） A．纯表 B．线性表 C．递归表 D．再入表 10．下列数据结构中，不属于二叉树的是（ A ） A．B树 B．AVL树 C．二叉排序树 D．哈夫曼树 11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） ．．

A．1，5，2，6，3，4 B．1，5，6，2，3，4 C．5，1，6，3，4，2 D．5，1，2，6，4，3

12．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）

第 17 页

A．v1，v2，v3，v4，v5，v6，v7 B．v1，v2，v5，v4，v3，v7，v6 C．v1，v2，v3，v4，v7，v5，v6 D．v1，v2，v5，v6，v7，v3，v4 13．下列排序算法中不稳定的是（ A ） A．快速排序 B．归并排序 C．冒泡排序 D．直接插入排序

14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，

查找成功需要的比较次数是（ B ） A．2 B．3 C．4 D．8 15．采用ISAM组织文件的方式属于（ D ） A．链组织 B．顺序组织 C．散列组织 D．索引组织 二、填空题(本大题共10小题，每小题2分，共20分)

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

16．数据元素及其关系在计算机存储器内的表示称为__数据的存储结构_______。

17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是___O（n）______。 18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是__取栈顶元素_______。 typedef struct{

DataType data[100]； int top； }SeqStack；

DataType f18(SeqStack*S) { if(StackEmpty(S))

Error(”Stack is empty”)； return S->data[S->top]； }

19．在串匹配中，一般将主串称为目标串，将子串称为____模式串_____。

20．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))= ____（c）_____。

21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为

___219______。

22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是____35_____。

第 18 页

23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是__{42,13,94,55,05,46,17}_______。 24．高度为3的3阶B-树最少的关键字总数是____7_____。

+

25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是____B树_____。 三、解答题(本大题共4小题，每小题5分，共20分) 26．假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作： (1)遍历右子树； (2)访问根节点； (3)遍历左子树。

已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。 （GCFABD）

27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。

请回答下列问题：

(1)请画出对应的图G。

(2)画出图G的邻接表存储结构。 (参考书P104)

28．已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请

给出初始建堆后的序列。

（12,15,14,18,16,36,18,60,25,85） 29．已知一棵二叉排序树如图所示。 请回答下列问题：

(1)画出插入元素23后的树结构；

(2)请画出在原图中删除元素57后的树结构。

（在二叉排序树中对于插入元素，直接插入即可，删除元素时是删除其中序遍历的后继）

第 19 页

四、算法阅读题(本大题共4小题，每小题5分，共20分) 30．已知下列程序，Ls指向带头结点的单链表。 Typedefstruct node { DataType data; struct node * next; } * LinkList;

void f30( LinkList Ls ) { LinkList p, q; q = Ls->next;

if ( q && q->next ) { Ls->next = q->next; p=q

while ( p->next ) p = p->next; p->next = q; q->next = NULL; } }

请回答下列问题：

(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。

(2)请简述算法的功能。

23451

将单链表中第一个结点连接到原链表中最后一个结点

31．已知字符串处理函数f31程序如下。 int f31(char*strl，char*str2)

{ while(*strl==*str2&&(*strl!=’＼0’)){

strl++； str2++； }

return(*strl-*str2 ? l∶0)； }

请回答下列问题：

(1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是

f31(”abcde”，”abcde”)，则函数的返回值是什么? (2)简述该函数的功能。

（1）1,0

（2）比较两个字符串，相等返回0，不相等返回1.

32．数组A[]中存储有n个整数，请阅读下列程序。 void f32(intA[]，int n) { inti，j，k，x；

k=n-l； while(k>0){

第 20 页

i=k； k=0；

for(j=O；jA[j+1]){ x=A[j]；

A[j]=A[j+l]； A[j+1]=x； k=j；

}／／end of if }／／end of while return；

}

请回答下列问题：

(1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么? (2)说明该算法的功能。

（1）A【】={2,4,6,7,8,10} （2）将数组中的数据按从小到大排列

33．下面程序实现二分查找算法。 Typedef struct{

KeyType key；

InfoType otherinfo； }SeqList[N+1]；

int BinSearch(SeqList R, int n，KeyType K) { int low=1，high=n； while( (1) ){

mid=(1ow+high)／2； if( (2) )

return mid； if(R[mid]．key>K)

high=mid-1； else

(3) ；

}

return O； } ／／BinSearch

请在空白处填写适当内容，使该程序功能完整。 (1)low<=high

(2)R[mid].key==k (3)low=mid+1

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

34．已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{

ElmType data；

struct Node *lchild，*rchild； }*BiTree；

第 21 页

请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数。

求解步骤：

判断树是否为空，如果为空返回0

如果只有一个根节点，返回1，否则结点数为左子树+右子数+1 int SumNOde(BiTree) {if(T==NULL)return 0;

if(lchild==NULL&&rchild==NULL) return 1; else

return SumNOde(T->lchild)+ SumNOde (T->rchild)+1; }

全国2009年10月自学考试数据结构试题

课程代码：02331

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．按值可否分解，数据类型通常可分为两类，它们是（ C ） A．静态类型和动态类型 C．原子类型和结构类型

B．原子类型和表类型 D．数组类型和指针类型

2．对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陈述中不成立的是．（ C ） A．f(n)是0(g(n)) C．h(n)是0(nlogn)

B．g(n)是0(f(n)) D．h(n)是0(n2)

3．指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（ A ） A．p->next=r； q->next=r->next； r->next=q； B．p->next=r； r->next=q； q->next=r->next； C．r->next=q； q->next=r->next； p->next=r； D．r->next=q； p->next=r； q->next=r->next；

4．若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（ B ） A．3 C．6

B．5 D．7

5．假设以数组A［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为（ D ） A．rear= =front

B．(front+1)％n= =rear

第 22 页

C．rear+1= =front

6．串的操作函数str定义为：

int str(char*s) { char *p=s；

while (*p！=′\\0′)p++； return p-s； }

则str(″abcde″)的返回值是（ C ） A．3 C．5

D．(rear+1)％n= =front

B．4 D．6

7．二维数组A［10］［6］采用行优先的存储方法，若每个元素占4个存储单元，已知元素A［3］［4］的存储地址为1000，则元素A［4］［3］的存储地址为（ A ） A．1020 C．1036

B．1024 D．1240

8．对广义表L= (a，())执行操作tail(L)的结果是（ B ） A．() C．a

B．(()) D．(a)

9．已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（ A ） A．FEDCBA C．FDECBA

B．ABCDEF D．FBDCEA

10．已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7，3，5，l，2，则

与F对应的二叉树的右子树中的结点个数为（ D ） A．2 C．8

B．3 D．11

11．若非连通无向图G含有21条边，则G的顶点个数至少为（ B ） ．A．7 C．21

B．8 D．22

12．如图所示的有向图的拓扑序列是（ B ） A．c，d，b，a，e B．c，a，d，b，e C．c，d，e，a，b D．c，a，b，d，e

13．对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为（ C ） A．(5，1，4，3，6，2，8，7)

B．(5，1，4，3，2，6，7，8)

第 23 页

C．(5，1，4，3，2，6，8，7) D．(8，7，6，5，4，3，2，1)

14．分块查找方法将表分为多块，并要求（ B ） A．块内有序 C．各块等长

B．块间有序 D．链式存储

15．便于进行布尔查询的文件组织方式是（ D ） A．顺序文件 C．散列文件

B．索引文件 D．多关键字文件

二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）

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

16．数据的链式存储结构的特点是借助___指针_____表示数据元素之间的逻辑关系。

17．如果需要对线性表频繁进行___插入_____或____删除____操作，则不宜采用顺序存储结构。 18．如图所示，可以利用一个向量空间同时实现两个类型相

件是top1=0，栈2为空的条件是top2=n-1，则“栈满”__top2+1=top1______。

19．静态存储分配的顺序串在进行插入、置换和___链接_____等操作时可能发生越界。 20．广义表L=（a，（b，( )））的深度为____3____。

21．任意一棵完全二叉树中，度为1的结点数最多为____1____。

22．求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中____边____的数目正相关。

23．在5阶B-树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含___2_____个关键字。 24．若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是____稳定____的。 25．常用的索引顺序文件是____ISAM____文件和___VSAM_____文件。 三、解答题(本大题共4小题，每小题5分，共20分)

26．如图所示，在n×n矩阵A中，所有下标值满足关系式i+j＜n+l的元素aij的值均为0，现将A中其它元素按行

优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a1，n存储在sa［0］。 (1)设n=10，元素a4，9存储在sa［p］，写出下标p的值；

(2)设元素ai，j存储在sa［k］中，写出由i,j和n计算k的一般公式。 8

aij=i(i-1)/2+i-n+j-1

同的栈。其中栈1为空的条的

判

定

条

件

是

27．由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为

第 24 页

111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

eatst

28．已知无向图G的邻接表如图所示，

(1)画出该无向图；

(2)画出该图的广度优先生成森林。

29．对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之

后的序列状态。

初始堆：(96,55,63,48,22,31,50,37,11) 第1趟：(63,55,50,48,,22,31,11,37,96) 第2趟：(55,48,50,37,22.31,11,63,96)

四、算法阅读题(本大题共4小题，每小题5分，共20分) 30．阅读下列算法，并回答问题：

(1)无向图G如图所示，写出算法 f30(&G)的返回值；

第 25 页

(2)简述算法f30的功能。 #define MaxNum 20 int visited[MaxNum]； void DFS(Graph *g，int i)；

/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visited[j]为1*/ int f30(Graph *g) { int i，k；

for (i=0； in； i++)／*g->n为图g的顶点数目*／

visited[i]=0；

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

if (visited[i]= =0) { k++； DFS(g，i)； } return k； }

(1)3

(2)返回图中连通分量的个数

31．假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：

typedef struct Node {

int id; /*学号*/ int score； /*成绩*/ struct Node *next； } LNode， *LinkList； 阅读算法f31，并回答问题： (1)设结点结构为

f31(A，B)后A所指的链表；

，成绩链表A和B如图所示，画出执行算法

第 26 页

(2)简述算法f31的功能。

void f31(LinkList A, LinkList B) { LinkList p, q; p=A->next; q=B->next; while (p && q) { if (p->idid)

p=p->next; else if (p->id>q->id)

q=q->next; else

{ if (p->score<60)

if (q->score<60)

p->score=q->score; else p->score=60; p=p->next; q=q->next; } } }

链A链B中相同学号的成绩均小于60的把B的成绩赋给A，B中大于A的将A中的成绩改为60

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

(1)设串s=“OneWorldOneDream”，t=＂One＂，pos是一维整型数组，写出算法 f32(s，t，pos)执行之后得到的返回值和pos中的值； (2)简述算法f32的功能。

int strlen(char*s)； /*返回串s的长度*/ int index(char*st，char*t)；

／*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1*/ int f32(char*s, char*t, int pos［］) { int i, j, k, ls, lt; ls=strlen(s); 1t=strlen(t);

if (ls= =0||1t= =0) return-1; k=0;

第 27 页

i=0; do {

j=index(s+i, t); if (j>=0)

{ pos［k++］=i+j;

i+=j+1t; }

}while(i+1t<=1s && j >=0); return k; } （1）8

（2）返回子串在主串中出现的次数，并将每一次出现的位置依次保存在pos数组当中。

33．二叉排序树的存储结构定义为以下类型：

typedef int KeyType; typedef struct node {

KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struct node *1child, *rchild; /*左、右孩子指针*/ } BSTNode, *BSTree； 阅读算法f33，并回答问题：

(1)对如图所示的二叉排序树T，写出f33(T，8) 返回的指针所指结点的关键字； (2)在哪些情况下算法f33返回空指针? (3)简述算法f33的功能。

BSTNode *f33(BSTree T, KeyType x) { BSTNode *p;

if (T= =NULL) return NULL; p=f33(T->1child, x); if (p!=NULL)return p; if (T->key>x)return T; return f33(T-> rchild, x); }

（1）10

（2）a空树b当树中所有值都小于X的时候

（3）在二叉排序树中找第一次出现比X大的结点，若没有找到返回空指针。

第 28 页

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

34．假设线性表采用顺序存储结构，其类型定义如下：

#define ListSize 100 typedef struct {

int data［ListSize］; int length; } SeqList, *Table;

编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。

voil f34(Table L) {int i=0,j=0,t;

for(i=0;Llength;i++) {if(L->data[i]%2==1) {if(i!=j) {t=L->data[i] L->data[i]=L-data[j] L->data[j]=t } j++; } } }

2009年1月自学考试数据结构试题

课程代码：02331

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.下列程序段的时间复杂度为( D ) s=0；

for(i=1；i

第 29 页

2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是( B ) A.head==NULL；

B.head->next==NULL；

C.head!=NULL； D.head->next==head；

3.栈是一种操作受限的线性结构，其操作的主要特征是( B ) A.先进先出 B.后进先出 C.进优于出 D.出优于进

4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( D ) A.(rear-front-1)％n C.(front-rear+1)％n

B.(rear-front)％n D.(rear-front+n)％n

5.判断两个串大小的基本准则是( D ) A.两个串长度的大小 B.两个串中首字符的大小 C.两个串中大写字母的多少

D.对应的第一个不等字符的大小

6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( C ) A.1012 B.1017 C.1034 D.1036

7.高度为5的完全二叉树中含有的结点数至少为( A ) A.16 C.31

B.17 D.32

8.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( C ) A.5 B.8 C.11 D.18

9.下列所示各图中是中序线索化二叉树的是( A )

第 30 页

10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为( A ) A.(v0，v1，v2，v5，v4，v3) B.(v0，v1，v2，v3，v4，v5) C.(v0，v1，v5，v2，v3，v4) D.(v0，v1，v4，v5，v2，v3)

11.如图所示有向图的一个拓扑序列是( B ) A.ABCDEF B.FCBEAD C.FEDCBA D.DAEBCF

12.下列关键字序列中，构成大根堆的是( D ) A.5，8，1，3，9，6，2，7 C.9，8，6，3，5，l，2，7

B.9，8，1，7，5，6，2，33 D.9，8，6，7，5，1，2，3

13.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( B )

39A.15 51C.15

49B.15 55D.15

14.已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( D )

15.数据库文件是由大量带有结构的( A ) A.记录组成的集合

B.字符组成的集合

C.数据项组成的集合 D.数据结构组成的集合

二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。

16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的__规模函数_______。 17.在双向循环链表中插入一个新的结点时，应修改__4_______个指针域的值。

第 31 页

18.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现_____5____个不同的出栈序列。 19.链串的结点大小定义为结点的___数据域______中存放的字符个数。 20.广义表(a，(d，(c)))的深度为____3_____。

21.在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有____4_____棵。 22.若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中__第i列的非零个数_______。

23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为

_15,12,11,10,8,16,18,17,13,19________。

24.索引顺序查找的索引表由各分块中的最大关键字及各分块的____起始地址_____构成。 25.VSAM文件的实现依赖于操作系统中的___虚拟______存取方法的功能。 三、解答题(本大题共4小题，每小题5分，共20分) 26.假设有一个形如

的8×8矩阵，矩阵元素都是整型量(次对角线以上的元素都是0)。

若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题： (1)B数组的体积至少是多少?

(2)若a18存储在B[0]中，a56存储在B[k]中，则k值为多少? (1)36 (2)12

27.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。 (1)写出排序过程中前两趟的划分结果； (2)快速排序是否是稳定的排序方法? (1)2,3,1,5,9,6,8,7

1,3,2,5,7,6,8,9,

(2)不稳定

28.假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求：

(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；

第 32 页

(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。 (1)

(2)f：000 c：10000 e：101 h：001 g：10001 d：11 b：01 a：1001 29.已知3阶B—树如图所示， (1)画出将关键字6插入之后的B—树；

(2)画出在(1)所得树中插入关键字2之后的B—树。 (1) (2)

做这个题的口诀是：中间往上走，两边要岔开。

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

30.假设以带头结点的单链表表示线性表，单链表的类型定义如下：

typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList; 阅读下列算法，并回答问题：

(1)已知初始链表如图所示，画出执行f30(head)之后的链表；

题30图

(2)简述算法f30的功能。 void f30( LinkList head) { LinkList p,r, s; if (head - > next) { r = head - > next; p = r->next;

r - > next = NULL;

第 33 页

while (p) { s =p; p = p->next;

if ( s - > data% 2 = = 0) { s - > next = head - > next; head - > next = s; } else {

s - > next = r - > next; r->next = s; r =s; } } } } (1)8,2,5,7

(2)将链表中的值偶数置前奇数置后。

31.假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { DataType data;

struct node * lchild, * rchild; //左右孩子指针 } * BinTree ;

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

(1)已知以T为根指针的二叉树如图所示， 写出执行f31(T)之后的返回值； (2)简述算法f31的功能。 int f31 ( BinTree T) { int d;

if ( ! T) return 0;

d = f31 ( T - > lchild) + f31 ( T - > rchild) ;

第 34 页

if (T - > lchild && T - > rchild) return d + 1 ; else

return d; (1)3

(2)求二叉树度为2 的结点个数 32.设有向图邻接表定义如下： typedef struct {

VertexNode adjlist[ MaxVertexNum ] ; int n，e； ／／图的当前顶点数和弧数 }ALGraph； ／／邻接表类型 其中顶点表结点VertexNode 边表结点EdgeNode结构为： 阅读下列算法，并回答问题：

(1)已知某有向图存储在如图所示的邻接 表G中，写出执行f32(＆G)的输出； (2)简述算法f32的功能。 int visited[ MaxNum ]; void DFS(ALGraph * G, int i) { EdgeNode * p; visited [ i ] = TRUE ;

if (G - > adjlist[ i]. firstedge = = NULL) printf( \； else {

p = G - > adjlist[ i]. firstedge; while (p ! = NULL) { if ( ! visited[p -> adjvex] ) DFS( G, p - > adjvex) ; p = p->next;

第 35 页

} } }

void f32 ( ALGraph * G) { int i;

for (i = 0; i < G->n; i ++) visited [ i ] = FALSE ; for (i = 0; i < G->n; i++) if ( ! visited[i] ) DFS(G, i) ; }P108 (1)BD

(2)输出无邻接点的顶点

33.下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。

#define MAXLEN 100 typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; } NodeType ;

typedef NodeType SqList[ MAXLEN ]; void f33 ( SqList R, int n) { int i,j,k; NodeType t; i =0; j =n-l; while (i < j) {

第 36 页

for ( (1) ) if (R[k].key > R[k +l].key) { t = R[k]; R[k] = R[k +1]; R[k +1] = t; } j--;

for (k =j; k > i; k -- ) if ( (2) ) { t = R[k]; R[k] = R[k-1]; R[k-1] = t; }

(3) ; } }

(1)k=0;k

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

34.假设以带头结点的单链表表示线性表，单链表的类型定义如下： typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList;

编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为： void f34(LinkList head) ;

第 37 页

全国2008年10月自学考试数据结构试题

课程代码：02331

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

在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ C ） A. 栈 C. 树

B. 队列 D. 图

2.下面程序段的时间复杂度为（ C ） for (i=0; i

B. O (n2)

C. O (m*n) D. O (m+n)

3.在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（ A ） A. p->next==head B. p->next->next==head C. p->next==NULL

D. p==head

4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ D ） A. SXSSXXXX B. SXXSXSSX C. SXSXXSSX

D. SSSXXSXX

5.两个字符串相等的条件是（ D ） A. 串的长度相等 B. 含有相同的字符集

C. 都是非空串 D. 串的长度相等且对应的字符相同

6.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（ A ） A. head (tail (head (L)))

B. head (head(head(L)))

C. tail (head (tail (L))) D. head (head (tail (L)))

第 38 页

7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ D ） A. 0 B. 1 C. 48

D. 49

8.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ A ） A. Dout B. Dout-1 C. Dout+1

D. n

9.如图所示的有向无环图可以得到的拓扑序列的个数是（ C ） A. 3 B. 4 C. 5 D. 6

10.如图所示的带权无向图的最小生成树的权为（ C ） A. 51 C. 54

11.对长度为n的关键字序列进行堆排序的空间复杂度为（ B ） A. O（log2n） C. O（n）

B. O（1）

B. 52 D. 56

D. O（n*log2n）

12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为

（35，51，24，13，68，56，42，77，93） （35，24，13，51，56，42，68，77，93） 所采用的排序方法是（ B ） A. 插入排序 B. 冒泡排序 C. 快速排序 D. 归并排序

第 39 页

13.已知散列表的存储空间为T[0..18]，散列函数H（key）=key,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（ D ） A. T[2] B. T[4] C. T[8] D. T[10]

14.适宜进行批量处理的文件类型是（ A ） A. 顺序文件 B. 索引顺序文件 C. 散列文件 D. 多关键字文件 15.VSAM文件的索引结构为（ A ） A. B+树 B. 二叉排序树 C. B-树 D. 最优二叉树

二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。

16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n3，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的 4 倍。 17.将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是 O(m+n) 。

18.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是 （rear-front+m）%m 。

19.字符串“sgabacbadfgbacst” 中存在有 3 个与字符串“ba”相同的子串。

20.假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为 Loc a[00]+4*(5j+i) 。 21.假设用表示树的边（其中x是y的双亲），已知一棵树的边集为 {,,,,,}，该树的度是 3 。 22.n个顶点且含有环路的无向连通图中，至少含有 n 条边。

23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 选择排

序 。

24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 存储 结构也无特殊要求。 25.顺序文件中记录存放的物理顺序和 逻辑 顺序一致。 三、解答题(本大题共4小题，每小题5分，共20分)

第 40 页

26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。

前序序列：GHIJ 后序序列：HJIG

27.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node { int adjvex;

struct node *next; }EdgeNode; typedef struct { VertexType vertex; EdgeNode *firstedge; }VertexNode;

typedef VertexNode AdjList[MaxVertexNum]; typedef struct { AdjList adjlist; int n, e; }ALGraph;

为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。

第 41 页

28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成，形如E32。运用基数排序 对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。 E13，A37，F43，B32，B47，E12，F37，B12 第一趟：书第二趟： 第三趟：

29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；

（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。 （1）P172 （2）3次

四、算法阅读题（本大题共4小题，每小题5分，共20分） 30.已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：

（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态； （2）简述算法f30的功能。 void f30 (SeqList *L) { int i,j;

for (i=j=0;ilength; i++) if(L->data[i]>=0){

if(i!=j)L->data[j]=L->data[i]; j++； }

第 42 页 题27图

P161

L->length=j; }

(1)L=（21,19,0,34,30） (2)删除顺序表中负值元素

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

（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态； （2）简述算法f31的功能。

（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作） void f31 (Queue*Q, Queue*Q1, Queue*Q2) { int e; lnitQueue (Q1); lnitQueue (Q2);

while (!QueueEmpty (Q)) { e=DeQueue (Q); if (e>=0) EnQueue (Q1,e); else EnQueue (Q2,e) } }

（1） Q==NULL

Q1=（1,0,2,9） Q2=（-5，-4.-6）

（2）将队列Q中元素依次退队，并将正值及0元素入队列到Q1中，负值元素入队到队列Q2中。 32.阅读下列算法，并回答问题：

（1）假设串由合法的英文字母和空格组成，并以’\\0’作结束符。设串s=”??|?am?a???student”(?表示空格符)，写出f32（s）的返回值； （2）简述算法f32的功能。 int f32 (char*s){ int i, n, inword;

第 43 页

n=inword=0; for (i=0;s[i]!=’\\0’;i++) if (s[i]!=’?’&& inword==0){ inword=1; n++; }

else if (s[i]==’?’&& inword==1) inword=0; return n; } （1）4

（2）对字符串的单词个数进行累加计数。

33.阅读下列对正整数关键字序列L操作的算法，并回答问题： （1）设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值； （2）简述函数f33的功能。

int Partition (SeqList*L, int low, int high);

∥对L[low..high]做划分，返回基准记录的位置，并使左部的关键字 ∥都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字 int f33 (SeqList L, int k){ int low, high, pivotpos; low=1; high=L.length; if (khigh) return-1; do {

pivotpos=Partition (&L, low, high);∥调用快速排序的划分算法 if (pivotpos

第 44 页

else if (pivotpos>k) high=pivotpos-1; }while (pivotpos!=k); return L.data [pivotpos]; } （1）20

（2） 利用快速排序的划分机制进行查找，以求取序列中排序第K个的元素。 五、算法设计题（本题10分） 34.二叉排序树的类型定义如下：

typedef struct BSTNode {∥ 二叉排序树的结点结构 int data; ∥数据域

struct BSTNode *lchild, *rchild; ∥左、右孩子指针 }BSTNode,*BSTree;

设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。

Void count(BSTNode,int a int *sum) {if(T)

{count(T->lchild,a,sum); If(T->data

{(*sum)++;count(T->rchild,a,sum)} } }

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

数据结构试题

课程代码：02331

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.逻辑上通常可以将数据结构分为（ C ） A.动态结构和静态结构 C.线性结构和非线性结构

B.顺序结构和链式结构 D.初等结构和组合结构

第 45 页

2.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ A ）

A.访问第i个元素的前驱（1

3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ D ） A.head= =NULL C.head!=NULL

B.head–>next= =NULL D.head–>next= =head

4.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ） A.5，4，3，2，1，6 C.3，2，5，4，1，6

B.2，3，5，6，1，4 D.1，4，6，5，2，3

5.与线性表相比，串的插入和删除操作的特点是（ A ） A.通常以串整体作为操作对象 C.算法的时间复杂度较高

B.需要更多的辅助空间 D.涉及移动的元素更多

6.假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ B ） ?0?8?0?7A.?00???50??0?8?0?0C.?70???50?060??000?

000??400??060??003?

000??400???0?8?0?7B.??50??00??0?8?0?7D.??50??00?060??003?

400??000??060??000?

403??000??7.以下有关广义表的表述中，正确的是（ A ） A.由0个或多个原子或子表构成的有限序列 B.至少有一个元素是子表 C.不能递归定义 D.不能为空表

8.树的先根序列等同于与该树对应的二叉树的（ A ） A.先序序列 C.后序序列

B.中序序列 D.层序序列

9.假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（ B ） ．A.n

B.e

第 46 页

C.2e D.n·e

10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（ C ） A.1 C.3

B.2 D.4

11.下列排序方法中，稳定的排序方法为（ D ） A.希尔排序 C.快速排序

B.堆排序 D.直接插入排序

12.对下列关键字序列进行快速排序时，所需进行比较次数最少的是（ C ） A.（1，2，3，4，5，6，7，8） C.（4，3，8，6，1，7，5，2）

B.（8，7，6，5，4，3，2，1） D.（2，1，5，4，3，6，7，8）

13.含n个关键字的二叉排序树的平均查找长度主要取决于（ B ） A.关键字的个数 C.关键字的取值范围

B.树的形态

D.关键字的数据类型

14.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（ D ） A.分块查找 C.二分查找

B.顺序查找 D.散列查找

15.可有效提高次关键字查找效率的文件是（ B ） A.顺序文件 C.散列文件

B.倒排文件 D.VSAM文件

二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16.数据的存储结构是其逻辑结构__映像_____。

17.输入线性表的n个元素建立带头结点的单链表，其时间复杂度为____O（n）_______。

18.假设循环队列的元素存储空间大小为m，队头指针f指向队头元素，队尾指针r指向队尾元素的下一个位置，则在少用一个元素空间的前提下，表示“队满”的条件是____（rear+1）%m=f_______。 19.给定串的联接操作函数：

char *strcat(char *to, char *from);

//将串from联接到串to的末尾，并返回联接后的串

若字符串s1=〞point〞,s2=〞of〞,则strcat(s1,strcat)(s2,s1))的操作结果是_____pointofpoint______。

20.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储 地址为100,则元素A[4][5]的存储地址为___190_______。

21.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为____499_______。

第 47 页

22.已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为_____55______。

23.在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n2)的排序算法有____快速排序_______。

24.假设散列表的表长为11,散列函数为H(key)=key%7,若用线性探测处理冲突,则探查地址序列hi的计算公式为 （H（key）+i-1）___________(i?1,2,?,10)。

25.VSAM文件由__索引集_________，顺序集___________和数据集三部分组成。 三、解答题（本大题共4小题，每小题5分，共20分） 26.已知广义表的图形表示如图所示,

(1) 写出该广义表L;

(2) 分别写出该广义表的深度和长度。 (1) 3,4

(2) L=((e)，(),(a,(b,c,d)), (b,c,d))

27.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF，

(1) 画出该二叉树的二叉链表存储表示; (2) 写出该二叉树的后序序列。 (1)

(2)DHEBIFCA

28.已知有向图的邻接表如图所示,

(1) 写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列; (2) 画出该有向图的逆邻接表。 ．(1)ABDCE (2)

29.依次读入给定的整数序列{7，16，4，8，20，9，6，18，5}，完成下列操作： 1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;

第 48 页

2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个

元素。 (1) (2) 7,8,9

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

30.假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题: (1) 设线性表为( a1, a2, a3, a4, a5, a6, a7 ), 写出执行算法f30后的线性表； (2) 简述算法f30的功能。 void f30(LinkList L) {

//L为带头结点单链表的头指针 LinkList p,q; P =L;

while (p &&p–>next){ q = p–>next; p–>next =q–>next; p =q–>next; free(q); } } (1)a7

(2)将线性表中前n-1个元素依次删除，保留最后的一个结点，使得头结点指向最后一个结点

31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换，阅读算法并回答问题： (1) 画出n为十进制的1348时算法执行过程中栈的动态变化情况; (2) 说明算法中while循环完成的操作。 void f31(int n) //n为非负的十进制整数 { int e; SeqStack S; InitStack(& S); do{

Push(& S,n%8); n =n/8; }while (n);

第 49 页

while ( ! StackEmpty(& S)){ e =Pop(& S); printf (〞%ld〞,e); } } (1) (2)

32.已知以二叉链表作二叉树的存储结构，阅读算法f32，并回答问题： (1) 设二叉树T如图所示,写出执行f32(T)的返回值; (2) 简述算法f32的功能。 int f32(BinTree T) { int m, n; if(! T) return 0; else{

m= f32(T–>lchild); n = f 32(T–>rchild); if(m>n)return m +1; else return n+1; } }

(1)4

(2)求二叉树的高度

33.设有向图邻接表定义如下； typedef struct{

VertexNode adjlist[Max VertexNum];

int n,e; //图的当前顶点数和弧数 } ALGraph;

//邻接表类型

vertex firstedge 第 50 页

其中顶点表结点VertexNode结构为：