下载文档原格式
2014年10月全国自考数据结构考前密卷02331(含答案)一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。
第1题用数组A［0..N-1］存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为()A. (rear-front+m) mod mB. (rear-front+1) mod mC. (rear-front-1+m) mod mD. (rear-front)mod m【正确答案】 A【你的答案】本题分数2分第2题考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是()A. 直接插入排序和快速排序B. 快速排序和归并排序C. 直接选择排序和归并排序D. 直接插入排序和归并排序【正确答案】 C【你的答案】本题分数2分第3题下面关于线性表的叙述错误的是()A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链接存储，不必占用一片连续的存储单元D. 线性表采用链接存储，不便于插入和删除操作【正确答案】 A【你的答案】本题分数2分第4题对于一棵具有三个结点的二叉树，共有()种不同的树的形态。
A. 4B. 5C. 6【正确答案】 B【你的答案】本题分数2分第5题对文件进行直接存取的是根据()A. 逻辑记录号去存取某个记录B. 逻辑记录的关键字去存取某个记录C. 逻辑记录的结构去存取某个记录D. 逻辑记录的具体内容去存取某个记录【正确答案】 A【你的答案】本题分数2分第6题快速排序在最坏情况下的时间复杂度是()【正确答案】 B【你的答案】本题分数2分第7题在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的()A. 先序遍历B. 中序遍历C. 后序遍历D. 按层次遍历【正确答案】 A【你的答案】本题分数2分第8题已知一个向量的第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是()A. 120B. 112C. 110【正确答案】 C【你的答案】本题分数2分第9题对含有()个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
2016年4月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)注意事项：1．本试卷分为两部分，第一部分为选择题，第二部分为非选择题。
2．应考者必须按试题顺序在答题卡(纸)指定位置上作答，答在试卷上无效。
3．涂写部分、画图部分必须使用2B铅笔书写部分必须使用黑色字迹签字笔。
第一部分选择题一、单项选择题（本大题共15小题，每小题2分，共30分）1．下列选项中，属于非线性数据结构的是（）A．队列B．栈C．二叉排序树D．线性表2．瑞士计算机科学家沃思教授曾指出：算法+数据结构=程序．这里的数据结构指的是（）A．数据的逻辑结构和存储结构B．数据的线性结构和非线性结构C．数据的紧凑结构和非紧凑结构D．数据的顺序结构和链式结构3．线性表顺序存储时，逻辑上相邻的两个数据元素，其存储地址（）A．一定相邻B．一定不相邻C．不一定相邻D．可能不相邻4．数据元素1，2，3，4，5依次入栈，则不可能得到的出栈序列是（）A．4，5，3，2，1 B．1，2，3，4，5C．4，3，5，1，2 D．5，4，3，2，15．设顺序表首元素A[0]的存储地址是4000，每个数据元素占5个存储单元，则元素A[20]的起始存储地址是（）A．4005 B．4020 C．4100 D．41056．广义表 A=(a，(b，c，(e，f)))，函数 head(head(tail(A)))的运算结果是（）A．a B．b C．c D．e7．设高度为h的二叉树中，只有度为0和2的结点，则此类二叉树包含的结点数至少是（）A．2h B．2h-1 C．2h+1 D．h+18．—棵非空二叉树T的前序遍历和后序遍历序列正好相反，则T一定满足（）A．所有结点均无左孩子B．所有结点均无右孩子C．只有一个叶子结点D．是一棵满二叉树9．设图的邻接矩阵A如下所示。
各顶点的度依次是（）A．1，2，1，2 B．2，2，1，1 C．3，4，2，3 D．4，4，2，21O．无向图G如题10图所示，从顶点a开始进行深度优先遍历，下列遍历序列中，正确的是（）A．a，b，e，c，d，f B．a，c，f，e，d，bC．a，c，b，e，f，d D．a，e，d，f，c，b11．设带权连通图G中含有n（n>1）个顶点，下列关于G的最小生成树T的叙述中，正确的是（）A．T中可能含有回路B．T中含有图G的所有边C．T是唯一的，且含有n-1条边D．T可能不唯一，但权一定相等12．若要求对序列进行稳定的排序，则在下列选项中应选择（）A．希尔排序B．快速排序C．直接插入排序D．直接选择排序13．下列排序算法中，空间复杂度最差的是（）A．归并排序B．希尔排序C．冒泡排序D．堆排序14．下列排序算法中，初始数据有序时，花费的时间反而更多的算法是（）A．插入排序B．冒泡排序C．快速排序D．希尔排序15．对线性表L进行二分查找时，要求L必须满足（）A．以顺序方式存储B．以顺序方式存储，且数据元素有序C．以链接方式存储D．以链接方式存储，且数据元素有序第二部分非选择题二、填空题（本大题共10小题，每小题2分，共20分）16．下面程序段的时间复杂度是_________。
1 / 72010年10月全国自考数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分） 1．数据的四种存储结构是(A )A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构2．若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是(C ) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表D.带头结点的单循环链表3．若带头结点的单链表的头指针为head ，则判断链表是否为空的条件是(B ) A.head=NULL B.head->next=NULL C.head!=NULLD.head->next!=head4．若元素的入栈顺序为1，2，3....，n ，如果第2个出栈的元素是n ，则输出的第i(1<=i<=n)个元素是(D )A.n-iB.n-i+lC.n-i+2D.无法确定5．串匹配算法的本质是(C )A.串复制B.串比较C.子串定位D.子串链接6．设有一个10阶的对称矩阵A ，采用行优先压缩存储方式，a 11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a 85的地址为(C ) A.13 B.18 C.33D.407．若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是(B ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树D.树中非叶结点均只有右子树8．若根结点的层数为1，则具有n 个结点的二叉树的最大高度是(A )A.nB.2log n ⎢⎥⎣⎦C.2log n ⎢⎥⎣⎦+1D.n/2 9．在图G 中求两个结点之间的最短路径可以采用的算法是(A )2 / 7A.迪杰斯特拉（Dijkstra ）算法B.克鲁斯卡尔（Kruskal ）算法C.普里姆(Prim)算法D.广度优先遍历(BFS)算法10．下图G=(V,E)是一个带权连通图，G 的最小生成树的权为(D ) A.15 B.16 C.17 D.1811．在下图中，从顶点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 712．如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是(B ) A.不稳定的 B.稳定的 C.基于交换的D.基于选择的13．设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为(C ) A.1 B.2 C.3D.414．已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是(D)15．若需高效地查询多关键字文件，可以采用的文件组织方式为(D)A.顺序文件B.索引文件C.散列文件D.倒排文件二、填空题（本大题共10小题，每小题2分，共20分）16．下面程序段的时间复杂度为（O(n)）。
2017年10月高等教育自学考试全国统一命题考试数据结构试卷（课程代码02331）注意事项：1.本试卷分为两部分，第一部分为选择题，第二部分为非选择题。
2.应考者必须按试卷顺序在答题卡（纸）制定位置上作答，答在试卷上无效。
3.涂写部分、画图部分必须使用2B铅笔，书写部分必须使用黑色字迹签字笔。
第一部分选择题（共30分）一、单项选择题：本大题共15小题，每小题2分，共30分。
在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。
1．下列选项中，与数据存储结构直接相关的是A.线性表 B．双向链表 C．二叉树 D.有向图2．将12个数据元素保存在顺序表中，若第一个元素的存储地址是100，第二个元素的存储地址是105，则该顺序表最后一个元素的存储地址是A．111 B．144 C. 155 D．1563．设栈的初始状态为空，元素1，2，3，4，5，6依次入栈，栈的容量是3，能够得到的出栈序列是A．1,2,6,4,3,5 B．2,4,3,6,5,1C．3,1,2,5,4,6 D．3,2,6,5,1,44．设指针变量head指向非空单循环链表的头结点，指针变量p指向终端结点，next是结点的指针域，则下列逻辑表达式中，值为真的是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL5．己知广义表LS=(((a,b)),((c,(d))),(e,(f))),(g,h))，LS的深度是A．2 B．3 C．4 D．56．已知一棵高度为4的完全二叉树T共有5个叶结点，则T中结点个数最少是A．9 B．10 C．11 D. 127．在一棵非空二叉树的中序遍历序列中，所有列在根结点前面的是A．左子树中的部分结点 B．左子树中的全部结点C．右子树中的部分结点 D．右子树中的全部结点8．用邻接矩阵表示有n个顶点和e条边的无向图，采用压缩方式存储，矩阵中零元素的个数是A．n(n+l)/2-e B．n(n+l)/2-2e C．n×n-e D．n×n-2e9．无向图G中所有顶点的度数之和是20，则G中的边数是A．10 B．20 C．30 D．4010.设有向图G含有n个顶点、e条边，使用邻接表存储。
绝密★启用前2018年4月高等教育自学考试全国统一命题考试数据结构试题答案(课程代码02331)一、单项选择题：本大题共15小题，每小题2分，共30分。
1．A 2．B 3．C 4．D 5．D6．C 7．D 8．B 9．D 10．C11．A 12．D 13.B 14．A 15．B二、填空题：本大题共10小题，每小题2分，共20分。
16.非线性结构17.头结点18. 320 19．(( ))20.2h-1 21.生成树22. 16 23.长度24. 32，36，l8，13，36，45，76，97，49，53 25．基数排序三、解答题：本大题共4小题，每小题5分，共20分。
26.答案：(1)判断栈满int stackfull( SeqStack *s){ return s->topl+1 == s->top2;}(2)进栈void push(SeqStack*s, int si, DataTypex){ if ( stackfull( s））printf( "satck overflow");else{ if (si==0)s->data[ ++s->topl] = x;else s->data[ --s->top2] = x;}}27.答案：①C ②H ③D ④E ⑤H ⑥D ⑦B ⑧E ⑨G ⑩A28.答案：(1)是有向无环图。
(2)该图的拓扑排序序列有：(1,2,5,4,7,3,6)和(1,2,5,4,3,7,6)29.答案：(1)散列表是(2) ASL查找成功=12/8 =1.5四、算法阅读题：本大题共4小题，每小题5分，共20分。
30.答案：(1) Q->rear==Q->front(2) (Q->rear+l)%QueueSize(3) (Q->front+l)%QueueSize31.答案（1）*a（2）k ++(3) k32.答案：输出结果：7，3，9，6，1，5，2，8，433.答案：输出结果：62，32，21，23，25，5，10，1，20，9五、算法设计题：本题10分。
最新全国自考数据结构（02331）试题及答案全国2012年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。
选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。
如需改动，用橡皮擦干净后，再选涂其他答案标号。
不能答在试题卷上。
一、单项选择题(本大题共l5小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。
错涂、多涂或未涂均无分。
1．一个算法的时间耗费的数量级称为该算法的A．效率B．难度C．可实现性D．时间复杂度2．顺序表便于A．插入结点B．删除结点C．按值查找结点D．按序号查找结点3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear 指向队尾元素的下一个位置，则当前队列中的元素个数为A．(rear-front+m)％m B．rear-front+1C．(front-rear+m)％m D．(rear-front)％m5．下列关于顺序栈的叙述中，正确的是A．入栈操作需要判断栈满，出栈操作需要判断栈空B．入栈操作不需要判断栈满，出栈操作需要判断栈空C．入栈操作需要判断栈满，出栈操作不需要判断栈空D．入栈操作不需要判断栈满，出栈操作不需要判断栈空6．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1，每个元素占一个存储单元，则a7,5的地址为A．25 B．26C．33 D．347．树的后序遍历等价于该树对应二叉树的A．层次遍历B．前序遍历C．中序遍历D．后序遍历8．使用二叉线索树的目的是便于A．二叉树中结点的插入与删除B．在二叉树中查找双亲C．确定二叉树的高度D．查找一个结点的前趋和后继9．设无向图的顶点个数为n，则该图边的数目最多为A．n-l B．n(n-1)／2C．n(n+1)／2 D．n210．可进行拓扑排序的图只能是A．有向图B．无向图C．有向无环图D．无向连通图11．下列排序方法中稳定的是A．直接插入排序B．直接选择排序C．堆排序D．快速排序12．下列序列不为．．堆的是A．75,45,65,30,15,25 B．75,65,45,30,25,15C．75,65,30,l5,25,45 D．75,45,65,25,30,1513．对线性表进行二分查找时，要求线性表必须是A．顺序存储B．链式存储C．顺序存储且按关键字有序D．链式存储且按关键字有序14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同．．的序列是A．(4,1,2,3,5) B．(4,2,3,l,5)C．(4,5,2,1,3) D．(4,2,1,5,3)15．下列关于m阶B树的叙述中，错误．．的是A．每个结点至多有m个关键字B．每个结点至多有m棵子树C．插入关键字时，通过结点分裂使树高增加D．删除关键字时通过结点合并使树高降低非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
全国2020年10月高等教育自学考试数据结构试题课程代码:023311.请考生按规定用笔将所有试题的答案涂、写在答题纸上。
2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
选择题部分注意事项:每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。
如需改动,用橡皮擦干净后，再选涂其他答案标号。
不能答在试题卷上。
一、单项选择题:本大题共15小题，每小题2分，共30分。
在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。
1.数据结构研究的基本内容是A.数据的逻辑结构、存储结构和对数据元素施加的操作B.数据的类型、数据的定义、算法描述和各种操作实现C.数据的线性结构、树型结构、图型结构及相关的算法D.数据元素之间的逻辑关系、物理存储和相关程序实现2.数据结构中，评价算法好坏的重要指标之一是A.程序的执行时间B.源程序的代码长度C.程序采用的语言D.算法的时间复杂度3.等概率情况下，在长度为n的顺序表中插入1个元素需要移动元素的平均次数是A.1B. n/2C. nD. n+14.已知head为指向带头结点的单链表的头指针，指针变量p指向一个新结点，next是结点的指针域，若要将p所指结点插入到单链表的表头，则正确的语句序列是A. head->next= p; p->next= head;B. p->next = head->next; head = p;C. head=p; p->next = head->head;D. p->next = head->next; head->next-p;5.后缀表达式求值的过程中要用到的数据结构是A.一个保存各种操作符的栈B.一个保存操作数及运算结果的栈C.两个分别保存操作符和操作数的栈D.两个分别保存操作数和运算结果的栈8.用n(n≥2)个带权值的结点作为叶结点构造一棵哈夫曼树，下列选项中正确的是A.哈夫曼树是叶结点权值之和最小的二叉树B.哈夫曼树是带权路径长度WPL最小的二叉树C.n个带有权值的结点可以构造出唯---棵哈夫曼树D.哈夫曼树是有n个叶结点的二叉树中高度最低的二叉树9.将一棵树T转换为等价的二叉树T1，与T的后序遍历序列相同的是T1的A.前序遍历序列B. 中序遍历序列C. 后序遍历序列D. 按层遍历序列10.要在带权图(权值>0)中求从某一顶点到其余各顶点的最短路径，应采用的算法是A.哈夫曼算法B.普里姆算法:C.克鲁斯卡尔算法D.迪杰斯特拉算法11.设图G存在拓扑序列，则下列结论中正确的是A.图G是一个有向图B.图G的拓扑序列唯一C.图G是一个无向图D.图G是一个有向无环图12.内排序过程中，待排序数据保存在A. CPU中B.内存储器中C.外存储器中D.计算机中13.下列排序方法中，关键字总的比较次数与记录的初始排列次序无关的是A.冒泡排序.B.希尔排序C.直接插入排序D. 直接选择排序非选择题部分注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。
烟台南山学院2015—2016学年春季学期期末考试
《数据结构试卷》A
(课程代码：02331 专业：计算机及应用学习层次：专科年级：2015级)
本试题需在【计算机】作答。
(试题总分100分)
一、算法阅读题（共4题，每小题5分，满分20分)
1. 分析下面程序的时间复杂度，并指出语句频度最高的是哪一条
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
c[i][j]=0;
for(k=1;k<=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
2. 下面是一个在带头结点的单链表head中删除所有数据域值为x的结点的算法，但不完善，请在相应的地方填上适当的语句，使之成为完整的算法
void DeleX(LinkList head, DataType x){
LinkNode *p,*q,*s;
p=head;
q=p->next;
while(q!=null)
if(q->data==x){
s=q;
q=q->next;
free(s);
（1）
}
else{
p=q;
（2）
}
}
3. 分析下面语句，写出输出结果及K的值（栈结点数据域为字符型char）
SeqStack s; char x,y;
x='c';
y='k';
push(s,x);
push(s,'a');
push(s,y);
x=pop(s);
push(s,'t');
push(s,x);
x=pop(s);
push(s,'s');
while(!StackEmpty(s)){
y=pop(s);
putchar(y);
}
putchar(x);
...
4. 分析下面程序，写出算法功能
typedef struct node{
DataType data;
struct node *lchild,*rchild;
}BinTNode;
typedef BinTNode *BinTree;
void Preorder(BinTree bt){
if(bt!=NULL){
printf("%c",bt->data);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}
二、解答题（共7题，每小题5分，满分35分）
1．假设输入栈的元素为a、b、c，在栈S的输出半端得到一个输出序列为a、b、c，试写出在输入端所有可能的输入序列
2．已知有一个10阶对称矩阵A，采用压缩存储方式存储（以行序为主，每个元素占一个单元），其起始地址为1100，写出A[4][5]的地址
3.求广义表((a,b),(c,(d,())))的表头和表尾
4.对于下图所示的有向图，请给出图的邻接矩阵
5.下出下图的两个拓扑排序序列
6.对于给定的一组关键字（26，18，60，14，7，45，13，32），进行直接选择排序，写出其排序的每一趟结果
7.判断下列序列是否为堆（小根堆或大根椎），如果不是，则将其调整为堆
（17，18，60，40，7，32，73，65）
三、画图分析题（共7题，每小题5分，满分35分)
1.已知一棵二叉树的中序序列为cbafehgd，后序遍历序列为cbfhgeda，画出此二叉树
2.对下图的树，画出其孩子兄弟链表存储结构
3.用分别以8，11，13，5，17，25，21作为权值的叶结点，构造一棵哈夫曼树，并求该二叉树的带权路径长度WPL
4.试给出二、4题所示图的强连通分量
5.画出对长度为13的有序表进行二分查找的判定树
6.对上题求出其等概率情况下查找成功的平均查找长度
7.画出在线性表（5，10，15，20，25，30，35，40）中用二分查找方法查找关键字10的查找过程
四、算法设计（共1题，每题10分，满分10分)
用C语言写出二分查找的递归算法。
