2009年全国自考数据结构模拟试卷(一)及答案

西华大学课程考试参考答案（A卷）课程代码： 8401801 试卷总分： 100 分一、单项选择题参考答案及评分标准：（本大题共20个小题，每小题2分，共40分）评分标准：选对一题得2分，不选或选错得0分。

1-5：CBACC 6-10：CCBDB 11-15：ABCCD 16-20：CADDC二、算法理解题参考答案及评分标准：（本大题共3个小题，第1、2小题各7分，第3小题6分，共20分）评分标准：请根据各解答步骤酌情给分。

1. 解：构造过程各图（略），最后结果为：2. 解：设权w=(5,29,7,8,14,23,3,11)，可构造一棵赫夫曼树如下图所示。

所得赫夫曼编码为：A: 0110B: 10C: 1110D: 1111E: 110F: 00G: 0111H: 0103. 解：（1）希尔排序第一趟（增量d=5）排序后 7、12、36、23、12、51、60、55、72、49第二趟（增量d=3）排序后 7、12、36、23、12、51、49、55、72、60第三趟（增量d=1）排序后 7、12、12、23、36、49、51、55、60、72（2）归并排序第一趟排序后 12、51、23、55、7、49、36、60、12、72第一趟排序后 12、23、51、55、7、36、49、60、12、72第三趟排序后 7、12、23、36、49、51、55、60、12、72第四趟排序后 7、12、12、23、36、49、51、55、60、72三、算法设计题参考答案及评分标准：（本大题共4个小题，每小题10分，共40分）评分标准：请根据编程情况酌情给分。

1. 参考答案示例：void DelInsert(LinkList &L）{∥本算法将带头结点的非空单链表L中数据域值最小的那个结点移到链表的最前面。

p=L->next；∥p是链表的工作指针pre=L；∥pre指向链表中数据域最小值结点的前驱。

q=p；∥q指向数据域最小值结点，初始假定是首元结点while （p->next!=NULL）{ if（p->next->data<q->data）{ pre=p；q=p->next；} ∥找到新的最小值结点 p=p->next；}if (q!=L->next){ pre->next=q->next；∥将最小值结点从链表上摘下q->next= L->next；∥将q结点插到链表最前面L->next=q；}}//DelInsert2. 参考答案示例：void Count(BiTree T,int &n0,int &n){//统计二叉树T上叶结点数n0和非叶结点数n。

全国2009年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.数据的不可分割的最小标识单位是（ A ）A.数据项B.数据记录C.数据元素(数据和运算基本单位)D.数据变量2. for（i=0；i<m；i++）for（j=0；j<t；j++）c［i］［j］=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为（ C ）A.O（m+n×t）B.O（m+n+t）C.O（m×n×t）D.O（m×t+n）3.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（ B ）A.单链表B.双链表C.单循环链表D.顺序表4.设单链表中指针p指向结点A，要删除A之后的结点（若存在），则修改指针的操作为（ A ）A.p—>next=p—>next—>next（下一个，下一个原则）B.p=p—>nextC.p=p—>next—>nextD.p—>next=p5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（ B ）A.hs—>next=s；B.s—>next=hs；hs=s；（下一个，赋值原则）C.s—>next=hs—>next；hs—>next=s；D.s—>next=hs；hs=hs—>next；6.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。

自考数据结构02331历年试题及答案(2009--2015个人整理版)全国2009年1月自学考试数据结构试题一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.下列程序段的时间复杂度为( )9 s=0；for(i=1；i<n ；i++) for(j=1；j<n ；j++) s+=i*j ； A.O(1) B.O(n)C.O(2n)D.O(n 2)2.假设某个带头结点的单链表的头指针为head ，则判定该表为空表的条件是( )22 A.head==NULL ； B.head->next==NULL ； C.head!=NULL ； D.head->next==head ；3.栈是一种操作受限的线性结构，其操作的主要特征是( )32 A.先进先出 B.后进先出 C.进优于出 D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front 和rear 。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( ) A.(rear-front-1)％n B.(rear-front)％n C.(front-rear+1)％n D.(rear-front+n)％n5.判断两个串大小的基本准则是( )52 A.两个串长度的大小 B.两个串中首字符的大小 C.两个串中大写字母的多少 D.对应的第一个不等字符的大小6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( )60 A.1012 B.1017 C.1034 D.10367.高度为5的完全二叉树中含有的结点数至少为( )72 A.16 B.17 C.31 D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( ) A.5 B.8 C.11 D.189.下列所示各图中是中序线索化二叉树的是( A)81A10.已知含6个顶点(v 0，v 1，v 2，v 3，v 4，v 5)的无向图的邻接矩阵如图所示，则从顶点v 0出发进行深度优先遍历可能得到的顶点访问序列为( )108 A.(v 0，v 1，v 2，v 5，v 4，v 3) B.(v 0，v 1，v 2，v 3，v 4，v 5) C.(v 0，v 1，v 5，v 2，v 3，v 4) D.(v 0，v 1，v 4，v 5，v 2，v 3)11.如图所示有向图的一个拓扑序列是( )a00a01 a02 a03 a04 a32A.ABCDEFB.FCBEADC.FEDCBAD.DAEBCF12.下列关键字序列中，构成大根堆的是( ) A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33 C.9，8，6，3，5，l ，2，7 D.9，8，6，7，5，1，2，313.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( )172A.1539B.1549 C.1551 D.1555 14.已知一个散列表如图所示，其散列函数为H(key)=key ％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( D )d 19715.数据库文件是由大量带有结构的( )206 A.记录组成的集合 B.字符组成的集合 C.数据项组成的集合 D.数据结构组成的集合二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。

数据结构模拟试卷及参考答案一、简答题（共10题，每题10分，共计100分）1. 什么是数据结构？请简要解释。

数据结构是计算机中用于组织和存储数据的方式，它包含了一系列的数据元素，以及这些数据元素之间的关系和操作。

通过使用不同的数据结构，可以更高效地存储、查找和操作数据。

2. 请解释什么是栈，并给出一个栈的应用场景。

栈是一种具有特定操作限制的数据结构，它遵循"先进后出"（LIFO）的原则。

栈的应用场景包括函数调用、表达式求值、撤销操作以及浏览器中的历史记录。

3. 什么是队列？请给出一个队列的实际应用例子。

队列是一种具有特定操作限制的数据结构，它遵循"先进先出"（FIFO）的原则。

一个实际应用例子是操作系统的进程调度，进程按照到达时间加入队列，并按照一定规则出队执行。

4. 请解释什么是链表，并给出一个链表的优点和缺点。

链表是一种动态数据结构，它由一系列节点构成，每个节点包含数据和指向下一个节点的指针。

链表的优点是可以动态地分配内存空间，且插入和删除节点的时间复杂度为O(1)。

缺点是访问链表某个具体节点的时间复杂度为O(n)，且需要额外的内存空间存储指针。

5. 请解释什么是树，并给出一个树的实际应用例子。

树是一种分层次的数据结构，它由一系列节点和节点之间的关系构成。

一个实际应用例子是文件系统的目录结构，文件和文件夹通过树的结构进行组织和存储。

6. 请解释什么是图，并给出一个图的实际应用例子。

图是一种由节点和节点之间的连接关系组成的数据结构。

一个实际应用例子是社交网络，人与人之间的关系可以用图来表示，每个人是一个节点，节点之间的连接表示关系。

7. 请解释什么是散列（哈希）表，以及它的优势和劣势。

散列表是一种根据关键字直接访问的数据结构，它通过将关键字映射到表中的位置来实现快速的查找操作。

散列表的优势是查找操作的平均时间复杂度为O(1)。

劣势是如果存在多个关键字映射到同一个位置，就会发生冲突，需要解决冲突问题。

更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/5346389）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........2009年10月全国自考数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.按值可否分解，数据类型通常可分为两类，它们是()A.静态类型和动态类型B.原子类型和表类型C.原子类型和结构类型D.数组类型和指针类型答案：C2.A. AB. BC. CD. D答案：C3.指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是()A.p->next=r；q->next=r->next；r->next=q；B.p->next=r；r->next=q；q->next=r->next；C.r->next=q；q->next=r->next；p->next=r；D.r->next=q；p->next=r；q->next=r->next；答案：A4.若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是()A. 3B. 5C. 6D.7答案：B5.假设以数组A［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为()A.rear==frontB.(front+1)％n==rearC.rear+1==frontD.(rear+1)％n==front答案：D6.串的操作函数str定义为：A. 3B. 4C. 5D. 6答案：C7.二维数组A［10］［6］采用行优先的存储方法，若每个元素占4个存储单元，已知元素A［3］［4］的存储地址为1000，则元素A［4］［3］的存储地址为()A.1020B.1024C.1036D.1240答案：A8.对广义表L= (a，())执行操作tail(L)的结果是()A.()B.(())C. aD.(a)答案：B9.已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为()A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEA答案：A10.已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7，3，5，1，2，则与F对应的二叉树的右子树中的结点个数为()A. 2B. 3C.8D.11答案：D11.若非连通无向图G含有21条边，则G的顶点个数至少为()A.7B.8C.21D.22答案：B12.如图所示的有向图的拓扑序列是()A.c，d，b，a，eB.c，a，d，b，eC.c，d，e，a，bD.c，a，b，d，e答案：B13.对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为()A.(5，1，4，3，6，2，8，7)B.(5，1，4，3，2，6，7，8)C.(5，1，4，3，2，6，8，7)D.(8，7，6，5，4，3，2，1)答案：C14.分块查找方法将表分为多块，并要求()A.块内有序B.块间有序C.各块等长D.链式存储答案：B15.便于进行布尔查询的文件组织方式是()A.顺序文件B.索引文件C.散列文件D.多关键字文件答案：二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请在每个空格中填上正确答案。

全国自考（数据结构）模拟试卷1(题后含答案及解析)题型有：1. 单项选择题 2. 填空题 3. 解答题 4. 算法阅读题 5. 算法设计题单项选择题1．索引顺序文件的记录，在逻辑上按关键字顺序排列，但物理上不一定按关键字顺序存储，故需要建立一张指示逻辑记录和物理记录之间一一对应关系的( )A．索引表B．链接表C．符号表D．交叉访问题正确答案：A2．在循环双链表的p所指结点之后插入s所指结点的操作是( )A．P—＞next=s；B．p—＞next=s；s—＞prior=p；p—＞next—＞prior=s；p—＞next—＞prior=s；s—＞prior=p；s—＞next=p—＞next；s —＞next=p—＞nextC．s—＞prior=p；D．s—＞prior=p；s—＞next=p—＞next；s—＞next=p—＞next；p—＞next=s；p—＞next—＞prior=s；p—＞next—＞prior=s；p—＞next=s；正确答案：D3．在下面的程序中，语句S的执行次数为( ) for(i=1;i＜=n-1;i++) {for(j=n;j＞=i;j--) {S; }A．&nbspB．&nbspC．&nbspD．&nbsp正确答案：B4．设矩阵A(aij,1≤i,j≤i0)的元素满足：aij≠0(i≥j,1≤i,j≤10) aij=O(i＜j,1≤i,j≤10) 现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占4个单元，则元素[9,5]的首地址为( )A．2160B．2164C．2336D．2340正确答案：A5．循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front 和rear，则当前队列中的元素个数是( )A．(rear-front+m)MODmB．rear-fomt+1C．rear-fribt-1D．rear-front正确答案：A6．如果要求一个线性表适应动态变化的要求，又必须能尽快地进行查找，则可以选择采用( )查找方法。

数据结构自考试题及答案一、单项选择题（每题1分，共10分）1. 在数据结构中，最基本的数据结构是（）。

A. 线性结构B. 非线性结构C. 顺序结构D. 链式结构答案：A2. 线性表的顺序存储结构和链式存储结构相比，其主要优点是（）。

A. 存储密度高B. 存储密度低C. 存储空间少D. 插入和删除操作快答案：A3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数为（）。

A. i-1B. n-iC. n-i+1D. n-1答案：C4. 栈的基本运算中，不包括（）。

A. 入栈B. 出栈C. 读栈顶元素D. 判断栈空答案：D5. 队列的特点是（）。

A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：A6. 树的深度为5，其中度为3的结点最多有（）个。

A. 3B. 7C. 9D. 15答案：D7. 在二叉树的前序遍历序列、中序遍历序列、后序遍历序列中，唯一与树的形态一一对应的序列是（）。

A. 前序遍历序列B. 中序遍历序列C. 后序遍历序列D. 无法确定答案：A8. 在图的遍历过程中，若某结点的入度为0，则该结点（）。

A. 一定为起点B. 一定为终点C. 可以为起点或终点D. 既不是起点也不是终点答案：C9. 哈夫曼编码是一种（）。

A. 定长编码B. 变长编码C. 唯一编码D. 非唯一编码答案：B10. 用邻接矩阵表示图时，若该图是无向图，则其邻接矩阵一定是（）。

A. 对称矩阵B. 非对称矩阵C. 稀疏矩阵D. 密集矩阵答案：A二、填空题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指算法执行过程中所需要的基本运算次数与输入数据量之间的关系。

算法的时间复杂度通常用大O符号表示，例如，O(n)表示时间复杂度与输入数据量成______关系。

答案：线性2. 线性表的两种存储结构分别是顺序存储结构和______存储结构。

答案：链式3. 在栈中，栈顶元素是最后被插入的元素，遵循______原则。

《数据结构》-1一、判断题 (每小题1分，共10分)1、线性表的逻辑顺序与物理顺序总是一致的。

( )2、线性表只能采用顺序存储结构或者链式存储结构。

( )3、线性表的顺序存储表示优于链式存储表示。

( )4、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。

( )5、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

( )6、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。

( )7、一般树和二叉树的结点数目都可以为0。

( )8、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。

( )9、每种数据结构都应具备三种基本运算：插入、删除和搜索。

( )10、若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。

( )二、单项选择题 (每小题2分，共20分)1、算法分析的目的是( )A.研究算法的输入与输出之间的关系B.找出数据结构的合理性C.分析算法的效率以求改进算法D.分析算法的可读性与可移植性2、已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作( )A. s->link = p； p->link = s；B. s->link = p->link； p->link = s；C. s->link = p->link； p = s；D. p->link = s； s->link = p；3、图的深度优先搜索类似于树的（）次序遍历。

A.先根B.中根C.后根D.层次4、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列（）A. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，15、若深度为5的完全二叉树的第5层有3个叶结点，则该二叉树一共有( )个结点。

A.15B.16C.17D.186、下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关（）A. 直接插入排序B. 起泡排序C. 快速排序D. 直接选择排序7、对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，38 ,50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是( )A.插入排序法B.选择排序法C.冒泡排序法D.堆积排序法8、对于循环队列，存储空间大小为n，头指针为F，尾指针为R。

自考02331数据结构真题及答案(2009-2018)自考02331数据结构真题及答案(2009-2018)数据结构是计算机科学与技术领域中的一门基础课程，通过研究数据的组织、存储和管理方式，以及不同数据结构之间的相互关系和运算方法，提高算法效率和问题解决能力。

在自考02331数据结构课程中，真题及其答案对于学生来说是很重要的复习资料。

本文将提供自考02331数据结构真题及答案的综合整理，希望对广大自考学子的备考有所帮助。

一、2009年自考02331数据结构真题及答案1. (1) 数据除了数值外还可以是什么类型的？答：数据除了数值类型外还可以是字符型、字符串型、布尔型等。

(2) 数据的逻辑结构和物理结构分别指什么？答：数据的逻辑结构指数据之间的关系及其运算规律，如线性结构、树形结构、图形结构等；数据的物理结构指数据在计算机内存中的存储方式，如顺序存储、链式存储等。

2. 用C语言编写一个递归函数，计算n的阶乘。

答：以下是一个计算n的阶乘的递归函数的C语言代码：```cint factorial(int n) {if(n == 0 || n == 1) {return 1;}return n * factorial(n-1);}```二、2018年自考02331数据结构真题及答案1. 请给出二叉树的定义，并用C语言实现二叉树的结点结构。

答：二叉树是一种特殊的树结构，每个结点最多有两个子结点。

以下是用C语言实现二叉树结点结构的代码：```ctypedef struct BinaryNode {int data; // 结点存储的数据struct BinaryNode* left; // 左子结点指针struct BinaryNode* right; // 右子结点指针} BinaryNode;```2. 请解释线性表的顺序存储和链式存储，并分别给出其对应的存储结构。

答：线性表是一种数据元素之间存在一对一关系的数据结构。

2009年4月自考计算机系统结构试卷答案课程代码：02325一、单项选择题(本大题共10小题，每小题1分，共10分)1、D2、D3、C4、B5、D6、C7、A8、C9、B 10、B二、填空题(本大题共20空，每空1分，共20分)11.通用片用户片 12. 资源重复资源共享13.标志符数据数据描述符 14.系统软件中断级屏蔽15.顺序顺序 16.程序主存17.静态动态 18.相关专用通路降低速度19. log2（N/2） 20.粗 21.知识库机、推理机三、简答题(本大题共5小题，每小题6分，共30分)22.答案：(1)系统结构设计考虑是否要设置乘法指令；（2分）(2)计算机组成设计考虑是否要配置高速的乘法器；（2分）(3)计算机实现考虑的是组成高速乘法器或加法—移位器的器件集成度、类型、数量以及微组装技术。

（2分）23.设计RISC的一般原则：(1)确定指令系统时，只选择使用频度很高的那些指令，再增加少量能有效支持操作系统、高级语言实现及其它功能的指令，大大减少指令条数，使之一般不超过100条；(2)减少指令系统所用寻址方式种类，一般不超过两种；(3)让所有的指令都在一个机器周期内完成；(4)扩大通用寄存器数，一般不少于32个，尽量减少访存，只有存取指令访存；(5)为提高指令执行速度，大多数指令都用硬联控制实现，少数指令才用微程序实现；(6)通过精简指令和优化设计编译程序，简单有效地支持高级语言的实现。

（以上每点1分）24.(1)回写法:CPU只写入Cache,不写入主存,仅当Cache块替换时,才先写回主存后再替换。

(2分)这种方法要求对每个Cache块增加一个修改位的资源开销；（1分）(2)写直达法：CPU每次写Cache的同时，也通过直接通路写入主存。

（2分）这种方法要增加写主存的时间开销。

（1分）25.答案：全局性相关是指转移指令与其后续指令之间的相关。

处理方法有：(1)猜测法，猜选其中一个分支继续流入，待条件码形成后再决定是继续执行，还是作废，按另一条重新流入；(2)提前形成转移所需的条件，包括指令内或程序段内条件码的提前生成；(3)加快短循环程序的处理，判断如属于短循环，将循环体各指令一次取入指令缓冲器中，停止预取指令；猜选分支恒选循环分支。

2009年全国⾃考数据结构模拟试卷（⼗）及答案2009年全国⾃考数据结构模拟试卷(⼗)⼀、单项选择题(本⼤题共15⼩题,每⼩题2分,共30分)在每⼩题列出的四个备选项⽬中只有⼀个是符号题⽬要求的,请将其代码填写的括号内.错选、多选或未选均⽆分。

1. 索引顺序⽂件的记录，在逻辑上按关键字顺序排列，但物理上不⼀定按关键字顺序存储，故需要建⽴⼀张指⽰逻辑记录和物理记录之间⼀⼀对应关系的()A. 索引表B. 链接表C. 符号表D. 交叉访问题答案：A2. 若已知⼀个栈的输⼊序列为1，2，3…，n，其输出序列为P1，P2，…，Pn。

若P1＝n，则P1为()A. iB. n＝iC. n-i+1D. 不确定答案：C3. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，⼀个元素出栈后即进⼊队列Q，若6个元素出列的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量⾄少应该是()A. 6B. 4C. 3D. 2答案：C4. 静态查找表与动态查找表⼆者的根本差别在于()A. 它们的逻辑结构不⼀样B. 施加在其上的操作不同C. 所包含的数据元素的类型不⼀样D. 存储实现不⼀样答案：B5. ⼀个栈的⼊栈序列是a,b,c,d,e，则栈的不可能的输出序列是()A. e d c b aB. d e c b aC. d c e a bD. a b c d e答案：C6. ⾮空的单循环链表L的尾结点P↑，满⾜()A. P↑.next＝NULL；B. P＝NULL；C. P↑.next＝L；D. P＝L答案：C7. 通常要求同⼀逻辑结构中的所有数据元素具有相同的特性，这意味着()A. 数据元素具有同⼀特点B. 不仅数据元素所包含的数据项的个数要相同，⽽且对应数据项的类型要⼀致C. 每个数据元素都⼀样D. 数据元素所包含的数据项的个数要相等答案：B8. 线索⼆叉树是⼀种()结构。

A. 物理B. 逻辑C. 存储D. 线性答案：A9. 排序的重要⽬的是为了以后对已排序的数据元素进⾏()A. 打印输出B. 分类C. 查找D. 合并答案：C10. 实现任意⼆叉树的后序遍历的⾮递归算法⽽不使⽤栈结构，最佳⽅案是⼆叉树采⽤()存储结构。

全国2009年10月高等教育自学考试数据库系统原理试题课程代码：04735一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.数据库系统的核心组成部分是（ D ）A.DBB.DDC.DBAD.DBMS2.数据库的最小存取单位是（ B ）A.字符B.数据项C.记录D.文件3.数据库应用程序的编写是基于三级模式结构中的（ A ）A.外模式B.逻辑模式C.内模式D.概念模式4.完成关系模式设计是在数据库设计的（ C ）A.需求分析阶段B.概念设计阶段C.逻辑设计阶段D.物理设计阶段5.下列关于外键的说法正确的是（C ）A.外键必须和相应的主键同名B.外键值不允许为空C.外键和相应的主键可以不同名，只要定义在相同域上即可D.外键的取值只允许等于所参照关系中某个主键值6.关系模式设计理论主要解决的问题是（ B ）A.提高查询速度B.消除操作异常和数据冗余C.减少数据操作的复杂性D.保证数据的安全性和完整性7.设有关系R （A ，B ，C ）和S （A ，D ）则与R S 等价的关系代数表达式是（D ） A.R S B.S)(R D C,B,R.A,⨯∏C.A .S ,A .R =σ )S R (⨯）D.S))(R (S.A R.A D C,B,R.A,⨯∏=σ8.设有关系模式R （A ，B ，C ），其关系r 如下表所示：下面叙述正确的是（ D ）A.函数依赖A→B在上述关系中成立B.函数依赖BC→A在上述关系中成立C.函数依赖B→A在上述关系中成立D.函数依赖A→BC在上述关系中成立9.设有关系R和S如下表所示，则R S的值是（ A ）A. B.C. D.10.SQL语言是（ C ）A.高级言语B.汇编语言C.结构化查询语言D.宿主语言11.在SQL中，与“NOT IN”等价的操作符是（ A ）A.< >ALLB.< >SOMEC.= SOMED.= ALL12.关于事务的故障与恢复，下列说法正确的是（ D ）A.事务日志用来记录事务执行的频度B.任何故障的恢复都由系统自动完成C.系统故障的恢复只需进行REDO操作D.对日志文件设置检查点是为了提高故障恢复的效率13.下列不属于．．．并发操作带来的问题是（ D ）A.丢失更新B.读脏数据C.不可重复读D.死锁1.4.在子类之间的语义约束中，表示超类中的对象必须在子类中出现的是（ B ）A.OverlappingpleteC.DisjointD.Imcomplete15.在对象联系图中，双向箭头（←→）表示（ D ）A.属性值是单值B.属性值是多值C.对象类型之间的联系D.两个属性之间值的联系二、填空题（本大题共10小题，每小题1分，共10分）请在每小题的空格上填上正确答案。

自考数据结构02331历年试题及答案(2009--2015个人整理版)全国2009年1月自学考试数据结构试题一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.下列程序段的时间复杂度为( )9s=0；for(i=1；i<n；i++)for(j=1；j<n；j++)s+=i*j；A.O(1)B.O(n)C.O(2n)D.O(n2)2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是( )22A.head==NULL；B.head->next==NULL；C.head!=NULL；D.head->next==head；3.栈是一种操作受限的线性结构，其操作的主要特征是( )32A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )A.(rear-front-1)％nB.(rear-front)％nC.(front-rear+1)％nD.(rear-front+n)％n5.判断两个串大小的基本准则是( )52A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( )60A.1012B.1017C.1034D.10367.高度为5的完全二叉树中含有的结点数至少为( )72A.16B.17C.31D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( )C.11D.189.下列所示各图中是中序线索化二叉树的是( A )81A10.已知含6个顶点(v 0，v 1，v 2，v 3，v 4，v 5)的无向图的邻接矩阵如图所示，则从顶点v 0出发进行深度优先遍历可能得到的顶点访问序列为( )108 A.(v 0，v 1，v 2，v 5，v 4，v 3) B.(v 0，v 1，v 2，v 3，v 4，v 5) C.(v 0，v 1，v 5，v 2，v 3，v 4) D.(v 0，v 1，v 4，v 5，v 2，v 3)11.如图所示有向图的一个拓扑序列是( ) A.ABCDEF B.FCBEADC.FEDCBAD.DAEBCF12.下列关键字序列中，构成大根堆的是( ) A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33 C.9，8，6，3，5，l ，2，7 D.9，8，6，7，5，1，2，313.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( )172 A.1539 B.1549 C.1551 D.1555 14.已知一个散列表如图所示，其散列函数为H(key)=key ％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( D )d 19715.数据库文件是由大量带有结构的( )206 A.记录组成的集合 B.字符组成的集合 C.数据项组成的集合 D.数据结构组成的集合二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。

全国2009年1月高等教育自学考试数据结构试题 课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.下列程序段的时间复杂度为( )9 s=0；for(i=1；i<n ；i++) for(j=1；j<n ；j++) s+=i*j ； A.O(1) B.O(n)C.O(2n)D.O(n 2)2.假设某个带头结点的单链表的头指针为head ，则判定该表为空表的条件是( )22 A.head==NULL ； B.head->next==NULL ； C.head!=NULL ； D.head->next==head ；3.栈是一种操作受限的线性结构，其操作的主要特征是( )32 A.先进先出 B.后进先出 C.进优于出 D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front 和rear 。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( ) A.(rear-front-1)％n B.(rear-front)％n C.(front-rear+1)％n D.(rear-front+n)％n5.判断两个串大小的基本准则是( )52 A.两个串长度的大小 B.两个串中首字符的大小 C.两个串中大写字母的多少 D.对应的第一个不等字符的大小6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( )60 A.1012 B.1017 C.1034 D.10367.高度为5的完全二叉树中含有的结点数至少为( )72 A.16 B.17 C.31 D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( ) A.5 B.8 C.11 D.189.下列所示各图中是中序线索化二叉树的是( )81A10.已知含6个顶点(v 0，v 1，v 2，v 3，v 4，v 5)的无向图的邻接矩阵如图所示，则从顶点v 0出发进行深度优先遍历可能得到的顶点访问序列为( )108 A.(v 0，v 1，v 2，v 5，v 4，v 3)a00 a01 a02 a03 a04 a32B.(v 0，v 1，v 2，v 3，v 4，v 5)C.(v 0，v 1，v 5，v 2，v 3，v 4)D.(v 0，v 1，v 4，v 5，v 2，v 3)11.如图所示有向图的一个拓扑序列是( )A.ABCDEFB.FCBEADC.FEDCBAD.DAEBCF12.下列关键字序列中，构成大根堆的是( ) A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33 C.9，8，6，3，5，l ，2，7 D.9，8，6，7，5，1，2，313.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( )172A.1539B.1549 C.1551 D.1555 14.已知一个散列表如图所示，其散列函数为H(key)=key ％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )d 19715.数据库文件是由大量带有结构的( )206 A.记录组成的集合 B.字符组成的集合 C.数据项组成的集合 D.数据结构组成的集合二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。

2009年4月全国自考（互联网数据库）真题试卷(题后含答案及解析) 题型有：1. 单项选择题 2. 填空题 3. 简答题 4. 设计题 5. 综合题单项选择题1．一个事务中所有对数据库的操作要么都做，要么都不做，这是事务的【】A．原子性B．一致性C．隔离性D．持久性正确答案：A2．OODBS的含义是【】A．对象关系数据库系统B．数据库管理系统C．面向对象数据库系统D．对象关系数据库正确答案：C3．对数据库模式进行规范化处理，是在数据库设计的【】A．需求分析阶段B．概念设计阶段C．逻辑设计阶段D．物理设计阶段正确答案：C4．实现关系代数投影运算的SQL子句是【】A．SELECTB．ORDER BYC．FROMD．WHERE正确答案：A5．在SQL．中，SELECT语句的”SELECT DISTINCT”表示查询结果中【】A．属性名都不相同B．去掉了重复的列C．属性值都不相同D．行都不相同正确答案：D6．数据的存储结构与数据的逻辑结构之间的独立性称为数据的【】A．结构独立性B．物理独立性C．逻辑独立性D．分布独立性正确答案：B7．在关系R中，代数表达式σ3 (2)商店(商店编号，店名，店址，店经理)主键：商店编号职工(职工编号，职工名，性别，工资，商店编号，工作开始时间) 主键：职工编号外键：商店编号会员(会员编号，会员名，地址)主键：会员编号SM(会员编号，商店编号，会员加入时间) 主键：会员编号，商店编号外键：会员编号；商店编号(3)以上关系模式中，所有属性对候选键都不存在传递依赖，因此都是BCNF。

一、单项选择题：1、为解决主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A. 栈 C. 树 D. 图2、设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S Q，则栈S的容量至少是A. 1B. 2 D. 43、给定二叉树如下图所示。

设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是A. LRNB. NRLC. RLN4A. C. D.5、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该二叉树的结点个数最多是A. 39B. 52 D. 1196、将森林转换为对应的而二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是Ⅰ. 父子关系Ⅱ. 兄弟关系Ⅲ. u的父结点和v的父结点是兄弟关系A. 只有Ⅱ C. Ⅰ和Ⅲ D. Ⅰ、Ⅱ和Ⅲ7、下列关于无向连通图特性的叙述中，正确的是Ⅰ. 所有顶点的度之和为偶数Ⅱ. 边数大于顶点个数减1Ⅲ. 至少有一个顶点的度为1B. 只有ⅡC. Ⅰ和ⅡD. Ⅰ和Ⅲ8、下列叙述中，不符合m阶B树定义要求的是A. 根结点最多有m棵子树B. 所有叶结点都在同一层上C. 各结点内关键字均升序或降序排列9、已知关键字序列5、8、12、19、28、20、15、22是小根堆，插入关键字3，调整后得到的小根堆是B. 3、5、12、19、20、15、22、8、28C. 3、8、12、5、20、15、22、28、19D. 3、12、5、8、28、20、15、22、1910、若数据元素序列11、12、13、7、8、9、23、4、5是采用下列排序算法之一得到的第二趟排序后的结果，则该排序算法只能是A. 起泡排序C. 选择排序D. 二路归并排序二、综合应用题一、带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。