​数据结构自考2010年1月真题

数据结构自考2010年1月真题及答案解析

本试卷为单选题型，填空题，算法阅读，算法设计等题型。

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

1.若一个算法的时间复杂度用T(n)表示，其中n的含义是( )

A.问题规模
B.语句条数
C.循环层数
D.函数数量

2.具有线性结构的数据结构是( )

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

3.将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为( )

A.O(1)
B.O(m)
C.O(n)
D.O(m+n)

4.在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是( )

A.2个
B.3个
C.4个
D.6个

5.假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为( )

A.3
B.37
C.50
D.97

6.若栈采用链式存储结构，则下列说法中正确的是( )

A.需要判断栈满且需要判断栈空
B.不需要判断栈满但需要判断栈空
C.需要判断栈满但不需要判断栈空
D.不需要判断栈满也不需要判断栈空

7.若串str=”Software”，其子串的数目是( )

A.8
B.9
C.36
D.37

8.设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，为第一个元素，其存储地址为1000，每个元素占一个地址单元，则的地址为( )

A.1012
B.1017
C.1032
D.1039

9.允许结点共享的广义表称为( )

A.纯表
B.线性表
C.递归表
D.再入表

10.下列数据结构中，不属于二叉树的是( )

A.B树
B.AVL树
C.二叉排序树
D.哈夫曼树

11.对下面有向图给出了四种可能的拓扑序列，其中错误的是( )

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为起始结点对下图进行深度优先遍历，正确的遍历序列是( )

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.快速排序
B.归并排序
C.冒泡排序
D.直接插入排序

14.一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是( )

A.2
B.3
C.4
D.8

15.采用ISAM组织文件的方式属于( )

A.链组织
B.顺序组织
C.散列组织
D.索引组织

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

11.数据元素及其关系在计算机存储器内的表示称为_________。

12.长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是_________。

13.下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________。typedef struct{DataType data[100];int top;}SeqStack;DataType f18(SeqStack*S){ if(StackEmpty(S))Error(”Stack is empty”);return S->data[S->top];}

14.在串匹配中，一般将主串称为目标串，将子串称为_________。

15.已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))= _________。

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

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

18.对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_________。

19.高度为3的3阶B-树最少的关键字总数是_________。

110.VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是_________。

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

21.假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作：(1)遍历右子树;(2)访问根节点;(3)遍历左子树。已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。

22.已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。请回答下列问题：(1)请画出对应的图G。(2)画出图G的邻接表存储结构。

23.已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。

24.已知一棵二叉排序树如图所示。 请回答下列问题：(1)画出插入元素23后的树结构;(2)请画出在原图中删除元素57后的树结构。

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

1.已知下列程序，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)请简述算法的功能。

2.已知字符串处理函数f31程序如下。int f31(char*strl，char*str2){ while(*strl==*str2&&(*strl!=’’)){strl++;str2++;}return(*strl-*str2 ? 1∶0);}请回答下列问题：(1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是f31(”abcde”，”abcde”)，则函数的返回值是什么?(2)简述该函数的功能。

3.数组A[]中存储有n个整数，请阅读下列程序。void f32(intA[]，int n) {inti，j，k，x;k=n-l;   while(k>0){i=k; k=0;for(j=O;j<i;j++)  if(A[j]>A[j+1]){   x=A[j];  A[j]=A[j+l];  A[j+1]=x; k=j;    }  //end of if }//end of whilereturn;}请回答下列问题：(1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么?(2)说明该算法的功能。

4.下面程序实现二分查找算法。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小题，共10分)

11.已知二叉树采用二叉链表存储，其结点结构定义如下：typedef struct Node{ElmType data;struct Node *lchild，*rchild;}*BiTree;请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数。