08年10月自考《数据结构》真题及答案.docx

全国2008年10月自学考试数据结构试题
一、单项选择题(本大题共15小题,每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的 括号内.错选、多选或未选均无分.
1. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则 该结构是(c )A.栈B.队列
C.树D.图下面程序段的时间复杂度为(C )
for (i=0; i<m; i++)for (j=0; j<n; j++)
A[i] [j]=i*j；A. 0 (m2) B. 0 (n2)
C. 0 (m*n) D. 0 (m+n)在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是(A )
A. p->next==head B. p->next->next==headC. p->next==NULL D. p==head
2. 若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列 是(D )A. SXSSXXXX B. SXXSXSSX
C. SXSXXSSX D. SSSXXSXX两个字符串相等的条件是(D )
A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同
pivotpos二Partition (&L, low, high) ; //调用快速排序的划分算法if (pivotpos<k)
low二pivotpos+1;else if (pivotpos>k)
high二pivotposT;}while (pivotpos!=k);
return L. data [pivotpos];)
⑴20⑵利用快速排序的“划分”机制进行查找，以求取序列中排 行第k小的元素
五、算法设计题(本题io分)34.二叉排序树的类型定义如下：
typedef struct BSTNode {//二叉排序树的结点结构int data; 〃数据域
struct BSTNode *lchild, *rchild; 〃左、右孩子指针}BSTNode, *BSTree;
设计递归算法，统计一棵二叉排序树T中值小于a的结点个数.
void count (BSTree T , int a , int *suni) {1〃以sum所指单元统计二叉树排序树种元素值小于a的结点个数，其初值为0
if (T) {1
count (T->lchild , a , sum) :2if(T->data<a) {2
(*sum)++;2
count (T->rchild . a , sum):
)
}}
答案二：
int count (BSTree T , int a) {
//统计二叉树排序树中元素值小于a的结点个数
int sum;
if(!T) return 0;
else {sum二count(T->lchild, a);
if(T->data<a)return sum+l+count(T->rchild , a);
elsereturn sum;
3. 如果将矩阵AnXn的每一列看成一个子表，整 个矩阵看成是一个广义表L,即L=((all, a21, •••, anl), ( al2, a22,…,an2),…,(aln, 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)))
4. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为(D )
A. 0 B. 1C. 48 D. 49
5. 在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout，则所有顶点的入度之 和为(A )A. Dout B. Dout-1
C. Dout+1 D. n9 .如图所示的有向无环图可以得到的拓扑序列的个数是(C )
C. 5 D. 6/\10 .如图所示的带权无向图的最小生成树的权为(C )-<5)<
A. 0(log2n) B. 0(1)

A. 0(log2n) B. 0(1)
题10图
C. 0(n) D. 0(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.归并排序
13. 已知散列表的存储空间为T[0.. 18],散列函数H（key）=key%17,并用二次探测法处理 冲突.散列表中已插入下列关键字:T[5]=39,T[6]=57和T[7]=7,则下一个关键字23插入 的位置是（D ）A. T[2] B. T[4]
C. T[8] D. T[10]适宜进行批量处理的文件类型是（A ）
A.顺序文件B.索引顺序文件C.散列文件D.多关键字文件
14. VSAM文件的索引结构为（A ）A. | B+树B.二叉排序树
C. B-树D.最优二叉树二、填空题（本大题共10小题,每小题2分，共20分） 请在每小题的空格中填上正确答案.错填、不填均无分.
15. 如果某算法对于规模为n的问题的时间耗费为T（n）=3n3,在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原 问题规模的4倍.
16. 将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是0（m+n）
17. 已知循环队列的存储空间大小为m,队头指针front指向队头元素，队尾指针rear指 向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是
(rear-front+m) %m 字符串"sgabacbadfgbacst”中存在有3个与字符串“ba”相同的
子串.
18. 假设以列优先顺序存储二维数组A[5] [8],其中元素A[0] [0]的存储地址为LOC(aOO), 且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为LOC(aOO)+4(5j+i).
19. 假设用〈x, y>表示树的边(其中x是y的双亲),己知一棵树的边集为{<b, d>, <a, b>, <c, g>, <c, f>, <c, h>, <a, c>},该树的度是3.
20. n个顶点且含有环路的无向连通图中，至少含有n条边.
21. 在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最 少的是 选择.
22. 和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对存 储结构也无特殊要求.(P170) 顺序文件中记录存放的物理顺序和逻辑顺序一致.
三、解答题(本大题共4小题,每小题5分，共20分)由森林转换得到的对应二叉树如图所示,写出原森林中第三棵树的前序序列和后序 序列.
前序序列:ghIj 后序序列:HJIG图的邻接表的类型定义如下所示：(pl06)
ttdefine MaxVertexNum50
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;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义
的存储表示实例如下图所示，请写出重新定义的类型说明.
Typedef
struct ArcNode(
VNode
* adjvex ; 〃该弧所指向的顶点的位置；
struct
ArcNode * nextarc ; 〃指向吓一条弧的指
针;
}ArcNode;Typedef struct VNode(
VertexType data ; //顶点信息
struct VNode * nextVertex ; 〃指向下一个顶点的 指针
ArcNode * firstarc ; 〃指向第一条依附该顶点的 弧}VNode , * AdjList ;
typedef struct(AdjList adjList ;
Int n , e ;}ALGraph ;
23. 某类物品的编号由一个大写英文字母及2位数字(0.. 9)组成，形如E32.运用基数排序(先对个位数进行排序，在对十位数进行排序)(P161)
对下列物品编号序列进行按字典序的排序，写出每一趟(分配和收集)后的结果.
E13, A37, F43, B32, B47, E12, F37, B12第一趟:B32, E12, B12, E13, F43, A37, B47, F37,
第二趟：E12,B12,E13,B32,A37,F37, F43, B47第三趟:A37, B12, B32, B47, E12, E13, F37, F43
24. (1)画出对表长为13的有序顺序表进行二分查找的判定树；
(2)已知关键字序列为(12, 14, 16, 21, 24, 28, 35, 43, 52, 67, 71, 84, 99),写出在该序列中 二分查找37时所需进行的比较次数.
⑴(P172)⑵3
四、算法阅读题(本大题共4小题,每小题5分，共20分)已知线性表的存储结构为顺序表，阅读下列算法,并回答问题：
(1) 设线性表 L= (21, -7, -8, 19, 0,-11, 34, 30,-10)，写出执行 f30 (&L)后的 L 状态；
L=(21 , 19 , 0 , 34 , 30)简述算法f30的功能.
void f30 (SeqList *L) {int i, j;
for (i=j=0;i<L->length; i++)if (L->data[i]>=0) {
if(i!=j) L->data[j]=L->data[i];j++；
}L->length=j;
}⑵删除顺序表中的负值元素
25. 阅读下列算法,并回答问题：
(1) Q、Q1和Q2都是队列结构，设队列Q=(l,0, -5, 2, -4, -6, 9),其中1为队头元素，写出 执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；简述算法f31的功能.
(注:lnitQueue> EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和
判队空的操作）void f31 (Queue*Q, Queue*Ql, Queue*Q2) {
int e;InitQueue (QI);
InitQueue (Q2);while (IQueueEmpty (Q)) {
e二DeQueue (Q);if (e>=0) EnQueue (QI,e);
else EnQueue (Q2,e)}
}
(1) Q=();Ql=(l, 0, 2, 9)
Q2= (-5, -4, -6)⑵将队列Q的元素依次退队，并将正值及0元素入队到Q1, 负值元素入队到Q2
26. 阅读下列算法,并回答问题：
(1) 假设串由合法的英文字母和空格组成，并以'\0'作结束符.设串s=" uu|uamuauuustudent”(口表示空格符)，写出f32(s)的返回值；
(2) 简述算法f32的功能.
int f32 (charts) {int i, n, inword;
n=inword=0;
for (i=0;s[i]!='\0' ;i++)if (s[i]! = ' lj' && inword—0) {
inword=l:
n++;}
else if (s[i]=二，&& inword~l)inword=0;
return n;}
⑴4⑵对字符串内的单词个数进行累加计数
27. 阅读下列对正整数关键字序列L操作的算法,并回答问题：
(1) 设 L= (28, 19, 27, 49, 56, 12, 10, 25, 20, 50),写出 f33 (L, 4)的返回值；简述函数f33的功能.
int Partition (SeqList*L, int low, int high);〃对L[low.. high]做划分，返回基准记录的位置，并使左部的关键字
〃都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字 int f33 (SeqList L, int k) {int low, high, pivotpos:
1ow=1;high=L. length;
if (k<low || k>high) return-1;do (