《全国2010年1月高等教育自学考试数据结构试题及参考答案》由会员分享，可在线阅读，更多相关《全国2010年1月高等教育自学考试数据结构试题及参考答案（7页珍藏版）》请在金锄头文库上搜索。
1、本资料由广州自考网收集整理，更多自考资料请登录 www.gzzk.cc 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。 - 本套试题共分 7 页，当前页是第 1 页 - 全国 2010 年 1 月高等教育自学考试数据结构试题及参考答案课程代码： 02331 一、单项选择题 ( 本大题共 15 小题，每小题 2 分，共 30 分 ) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1若一个算法的时间复杂度用 T(n) 表示，其中 n 的含义是（ A ）A问题规模 B语句条数C循环层数 D函数数量2具有线性结构的数据结构是（
2、 C ）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假设以数组 A60 存放循环队列的元素，其头指针是 front=47 ，当前队列有 50 个元素，则队列的尾指针值为（ B ）A 3 B 37 C 50 D 97 6若栈采用链式存储结构，则下列说法中正确的是（ B ）A 需要判断栈满且需要判断栈空B 不需要判断栈满但需要判断栈空C 需要判断栈满
3、但不需要判断栈空D 不需要判断栈满也不需要判断栈空7若串 str= ” Software ”，其子串的数目是（ D ）A 8 B 9 C 36 D 37 8设有一个 10 阶的下三角矩阵 A，采用行优先压缩存储方式， all 为第一个元素，其存储地址为 1000，每个元素占一个地址单元，则 a85 的地址为 （ C ）A 1012 B 1017 本资料由广州自考网收集整理，更多自考资料请登录 www.gzzk.cc 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。 - 本套试题共分 7 页，当前页是第 2 页 - C 1032 D 1039 9允许结点共享的广义表称为（ D ）A
4、纯表 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 ）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
5、， 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索引组织本资料由广州自考网收集整理，更多自考资料请登录 www.gzzk.cc 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。 - 本套试题共
6、分 7 页，当前页是第 3 页 - 二、填空题 ( 本大题共 10 小题，每小题 2 分，共 20 分 ) 请在每小题的空格中填上正确答案。错填、不填均无分。16数据元素及其关系在计算机存储器内的表示称为 _存储结构 _。17长度为 n 的线性表采用单链表结构存储时，在等概率情况下查找第 i 个元素的时间复杂度是 _O（ n ） _。18下面是在顺序栈上实现的一个栈基本操作，该操作的功能是 _。typedef struct DataType data100 ；int top ；SeqStack ；DataType f18(SeqStack*S) if(StackEmpty(S) Error(
7、” Stack is empty ” ) ；return S-dataS-top ； 19在串匹配中，一般将主串称为目标串，将子串称为 _模式串 _。20已知广义表 C=(a(b ， c) ， d) ，则： tail(head(tail(C)= _ _()_ _。21用 6 个权值分别为 6、 13、 18、 30、 7 和 16 的结点构造一棵哈夫曼 (Huffman) 树， 该树 的带权路径长度为_221_。22已知有向图如下所示，其中顶点 A 到顶点 C的最短路径长度是 _35_。23对序列 55 ， 46， 13， 05， 94， 17， 42 进行基数排序，第一趟排序后的结果是 _1
8、0,42,12,94,55,01,46,17 。24高度为 3 的 3 阶 B-树最少的关键字总数是 _13_。25 VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是 _B+_。三、解答题 (本大题共 4 小题，每小题 5 分，共 20 分 ) 26假设二叉树的 RNL遍历算法定义如下：若二叉树非空，则依次执行如下操作：(1) 遍历右子树；(2) 访问根节点；本资料由广州自考网收集整理，更多自考资料请登录 www.gzzk.cc 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。 - 本套试题共分 7 页，当前页是第 4 页 - (3) 遍历左子树。已知一棵二叉树
9、如图所示，请给出其 RNL遍历的结果序列。 GCFABDC27已知一个无向图 G=(V， E)，其中 V=A， B， C， D， E， F ，邻接矩阵表示如下所示。请回答下列问题：(1) 请画出对应的图 G。(2) 画出图 G的邻接表存储结构。28已知一组待排记录的关键字序列为 (16， 12， 18， 60， 15， 36， 14， 18， 25， 85) ，用堆排序方法建小根堆，请给出初始建堆后的序列。29已知一棵二叉排序树如图所示。请回答下列问题：(1) 画出插入元素 23 后的树结构；(2) 请画出在原图中删除元素 57 后的树结构。四、算法阅读题 (本大题共 4 小题，每小题 5 分
10、，共 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 本资料由广州自考网收集整理，更多自考资料请登录 www.gzzk.cc 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。 - 本套试题共分 7 页，当前页是第 5 页 - while ( p-next
11、) p = p-next; p-next = q; q-next = NULL; 请回答下列问题：(1) 当 Ls 指向的链表如下图所示，请画出执行本函数之后的链表的结果。(2) 请简述算法的功能。31已知字符串处理函数 f31 程序如下。int f31(char*strl ， char*str2) while(*strl=* str2&(*strl!= 0 )strl+ ；str2+ ； return(*strl-*str2 ? l 0) ； 请回答下列问题：(1) 若 调 用 语 句 是 f31( ” abcde” ， ” abcdf ) ， 则 函 数 的 返 回 值 是 什 么 ? 若
12、 调 用 语 句 是f31( ” abcde”，” abcde” ) ，则函数的返回值是什么 ? (2) 简述该函数的功能。32数组 A 中存储有 n 个整数，请阅读下列程序。void f32(intA ， int n) inti ， j ， k， x；k=n-l ；while(k0) i=k ； k=0 ；for(j=O ； jAj+1) x=Aj ；Aj=Aj+l ；Aj+1=x ；k=j ；本资料由广州自考网收集整理，更多自考资料请登录 www.gzzk.cc 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。 - 本套试题共分 7 页，当前页是第 6 页 - end of
13、if end of while return ； 请回答下列问题：(1) 当 A=10 ， 8， 2， 4， 6， 7 时，执行 f32(A ， 6) 后，数组 A中存储的结果是什么 ? (2) 说明该算法的功能。33下面程序实现二分查找算法。Typedef struct KeyType key ；InfoType otherinfo ；SeqListN+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(Rmid keyK) high=mid-1 ；else (3) ； return O ； BinSearch 请在空白处填写适当内容，使该程序功能完整。(1) (2) (3) 五、算法设计题 (本题 10 分 ) 34已知二叉树采用二叉链表存储，其结点结构定义如下：typedef struct Node ElmType data ；本资料由广州自考网收集整理
