2010年10月自考数据结构试题及答案.pdf

《2010年10月自考数据结构试题及答案.pdf》由会员分享，可在线阅读，更多相关《2010年10月自考数据结构试题及答案.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！1/7 2010 年 10 月全国自考数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分）1数据的四种存储结构是(A)A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下

2、列选项中，应选择的存储结构是(C)A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D.带头结点的单循环链表 3若带头结点的单链表的头指针为head，则判断链表是否为空的条件是(B)A.head=NULL B.head-next=NULL C.head!=NULL D.head-next!=head 4若元素的入栈顺序为1，2，3.，n，如果第2个出栈的元素是n，则输出的第i(1=i=n)个元素是(D)A.n-i B.n-i+l C.n-i+2 D.无法确定 5串匹配算法的本质是(C)A.串复制 B.串比较 C.子串定位 D.子串链接 6设有一个10阶的对称矩阵A，采用

3、行优先压缩存储方式，a11为第一个元素，其存储地址为 1，每个元素占一个字节空间，则a85的地址为(C)A.13 B.18 C.33 D.40 7若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是(B)A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8若根结点的层数为1，则具有n个结点的二叉树的最大高度是(A)A.n B.2log n C.2log n+1 D.n/2 9在图G中求两个结点之间的最短路径可以采用的算法是(A)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档

4、！2/7 A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.普里姆(Prim)算法 D.广度优先遍历(BFS)算法 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 12如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是(B)A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的 13设有一组关键字(1

5、9,14,23,1，6，20,4，27,5，11,10,9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为(C)A.1 B.2 C.3 D.4 14已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是(D)15若需高效地查询多关键字文件，可以采用的文件组织方式为(D)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！3/7 A.顺序文件 B.索引文件 C.散列文件 D.倒排文件 二、填空题（本大题共10小题，每小题2分，共20分）16下面程序段的时间复杂度为（O(n)）。sum=1；fo

6、r(i=0;sumn;i+)sum+=1；17已知链表结点定义如下：typedef struct node char data16;struct node*next;LinkStrNode;如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是（0.8）。18使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为（99）。193个结点可以组成（5）种不同树型的二叉树。20用5个权值3,2，4，5，1构造的哈夫曼(Huffman)树的带权路

7、径长度是（33）。21 若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为（2m）。22影响排序效率的两个因素是关键字的（比较）次数和记录的移动次数。23对任m阶的B树，每个结点中最多包含（m-1）个关键字。24若两个关键字通过散列函数映射到同一个散列地址，这种现象称为（冲突）。25如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为（稠密索引）。三、解答题（本大题共4小题，每小题5分，共20分）26要在0.n-l的向量空间中建立两个栈stackl和stack2，请回答：(1)应该如何设计这两个栈才能充分利用整个向量空间？(2)若stackl的栈顶指针为top

8、l,stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则：栈stackl空的条件是：（）;栈stack2空的条件是：（）;栈stackl和栈stack2满的条件是：（）。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！4/7 答：(1)采用双向栈的形式，stack1的栈底设置在下标为0的元素上，stack2的栈底设置在下标为 n-1的元素上。(2)top1=-1，top2=n，top1-1=top2 27已知广义表如下：A=(B,y),B=(x,L),L=(a,b),要求：(1)写出下列操作的结果：tail(A)=（(y)）。head

9、(B)=（x）。(2)请画出广义表A对应的图形表示。答：AByxLab 28已知二叉树如下：请画出该二叉树对应的森林。答：abcdefghjk 29请回答下列问题：(1)英文缩写DAG的中文含义是什么？(2)请给出下面DAG图的全部拓扑排序。答：(1)有向无环图(2)abdcefg，abdcfeg，adbcefg，adbcfeg 四、算法阅读题（本大题共4小题，每小题5分，共20分）30已知线性表(a1,a2,a3.，an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为欢迎您阅读并下载本文档，本文档来源于互联

10、网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！5/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(am0&mn)m=(2);k=m;while(k=0&kn)k=(3);if(kn)temp=ak;ak=am;am=(4);m=(5);答：(1)0 (2)m+1 (3)k+1 (4)temp (5)m+1 31阅读下列程序，并回答问题：#include substr(char*t,char*s,int po

11、s,int len)while(len0&*s)*t=*(s+pos-l);t+;s+;len-;*t=0;char*f31(char*s)char t100;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 str100=String;printf(%sn,f31(str);(1)请写出执行该程序后的输出结果；(2)简述函数f31的功能。答：(1)gnirtS(2)将字符串s中的字符倒置。32下面程序实现插入排序算法。欢迎您阅读并下载本文

12、档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！6/7 typedef struct int key;Info otherinfo;SeqList;void InsertSort(SeqList R,int n)/*待排序列保存在R1.n中*/SeqList x;int i,j,k,lo,hi,mi;for(i=2;i=n;i+)(1);lo=1;hi=i-l;while(lox.key)hi=mi-l;else lo=mi+l;if(mi=lo)k=i-mi;else k=i-mi-1;for(j=0;jdataA&head-datanext;if(p!=NULL)

13、printf(%dn,p-data);欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！7/7 (1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果；(2)简述算法f33的功能。答：(1)7 (2)输出链表h中（若存在）最后一个大于A到小于B的值。五、算法设计题（本题10分）34.已知二叉树的定义如下：typedef struct node int data;struct node*lchild,*rchild;*Bitptr;编写递归算法求二叉树的高度。函数原型为：int f34（Bitptr t）；答：int f34(Bitptr t)if(!t)return 0;lh=f34(t-lchild);rh=f34(t-rchild);return lhrh?lh+1:rh+1;