当前位置：文档之家 › 自考数据结构真题09.1

自考数据结构真题09.1

  • 格式：doc
  • 大小：889.00 KB
  • 文档页数：6

全国2009年1月高等教育自学考试数据结构试题一、单项选择题(本大题共15小题，每小题2分，共30分)1.下列程序段的时间复杂度为( )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(n2)2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是( )A.head==NULL；B.head->next==NULL；C.head!=NULL；D.head->next==head；3.栈是一种操作受限的线性结构，其操作的主要特征是( )A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

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

错填、不填均无分。

16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_________。

17.在双向循环链表中插入一个新的结点时，应修改_________个指针域．．．的值。

18.若进栈序列为a ，b ，c ，且进栈和出栈可以穿插进行，则可能出现_________个不同的出栈序列。

19.链串的结点大小定义为结点的_________中存放的字符个数。

20.广义表(a ，(d ，(c)))的深度为_________。

21.在含有3个结点a ，b ，c 的二叉树中，前序序列为abc 且后序序列为cba 的二叉树有_________棵。

22.若用邻接矩阵表示有向图，则顶点i 的入度等于矩阵中_________。

23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为_________。

24.索引顺序查找的索引表由各分块中的最大关键字及各分块的_________构成。

25.VSAM 文件的实现依赖于操作系统中的_________存取方法的功能。

三、解答题(本大题共4小题，每小题5分，共20分)26.假设有一个形如的8×8矩阵，矩阵元素都是整型量(次对角线以上的元素都是0)。

若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题：(1)B数组的体积至少是多少?(2)若a18存储在B[0]中，a56存储在B[k]中，则k值为多少?(1)(2)27.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。

(1)写出排序过程中前两趟的划分结果；(2)快速排序是否是稳定的排序方法?(1)(2)28.假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。

要求：(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。

(1)(2)29.已知3阶B—树如图所示，(1)画出将关键字6插入之后的B—树；(2)画出在(1)所得树中插入关键字2之后的B—树。

(1)(2)四、算法阅读题(本大题共4小题，每小题5分，共20分)30.假设以带头结点的单链表表示线性表，单链表的类型定义如下：typedef int DataType;typedef struct node {DataType data;struct node * next;} LinkNode, * LinkList;阅读下列算法，并回答问题：(1)已知初始链表如图所示，画出执行f30(head)之后的链表；题30图(2)简述算法f30的功能。

void f30( LinkList head){ LinkList p,r, s;if (head - > next) {r = head - > next;p = r->next;r - > next = NULL;while (p) {s =p;p = p->next;if ( s - > data% 2 = = 0) {s - > next = head - > next;head - > next = s;} else {s - > next = r - > next;r->next = s;r =s;}}}}(1)(2)31.假设以二叉链表表示二叉树，其类型定义如下：typedef struct node {DataType data;struct node * lchild, * rchild; //左右孩子指针} * BinTree ;阅读下列算法，并回答问题：(1)已知以T为根指针的二叉树如图所示，写出执行f31(T)之后的返回值；(2)简述算法f31的功能。

int f31 ( BinTree T){ int d;if ( ! T) return 0;d = f31 ( T - > lchild) + f31 ( T - > rchild) ;if (T - > lchild && T - > rchild)return d + 1 ;elsereturn d;(1)(2)32.设有向图邻接表定义如下：typedef struct {VertexNode adjlist[ MaxVertexNum ] ;int n，e；／／图的当前顶点数和弧数}ALGraph；／／邻接表类型其中顶点表结点VertexNode边表结点EdgeNode结构为：阅读下列算法，并回答问题：(1)已知某有向图存储在如图所示的邻接表G中，写出执行f32(＆G)的输出；(2)简述算法f32的功能。

int visited[ MaxNum ];void DFS(ALGraph * G, int i) {EdgeNode * p;visited [ i ] = TRUE ;if (G - > adjlist[ i]. firstedge = = NULL)printf( "% c ", G - > adjlist[ i]. vertex)；else {p = G - > adjlist[ i]. firstedge;while (p ! = NULL) {if ( ! visited[p -> adjvex] )DFS( G, p - > adjvex) ;p = p->next;}}}void f32 ( ALGraph * G) {int i;for (i = 0; i < G->n; i ++)visited [ i ] = FALSE ;for (i = 0; i < G->n; i++)if ( ! visited[i] ) DFS(G, i) ;}(1)(2)33.下列算法f33的功能是对记录序列进行双向冒泡排序。

算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。

请在空缺处填入合适的内容，使其成为完整的算法。

#define MAXLEN 100typedef int KeyType;typedef struct {KeyType key;InfoType otherinfo;} NodeType ;typedef NodeType SqList[ MAXLEN ];void f33 ( SqList R, int n){ int i,j,k;NodeType t;i =0;j =n-l;while (i < j) {for ( (1) )if (R[k].key > R[k +l].key) {t = R[k];R[k] = R[k +1];R[k +1] = t;}j--;for (k =j; k > i; k -- )if ( (2) ) {t = R[k];R[k] = R[k-1];R[k-1] = t;}(3) ;}}(1)(2)(3)五、算法设计题(本大题10分)34.假设以带头结点的单链表表示线性表，单链表的类型定义如下：typedef int DataType;typedef struct node {DataType data;struct node * next;} LinkNode, * LinkList;编写算法，删除线性表中最大元素(假设最大值唯一存在)。

合集下载

数据结构910真题试卷

数据结构910真题试卷

数据结构910真题试卷数据结构是计算机科学中的一门重要课程，它涉及到存储、组织和管理数据的方法和技术。

在计算机科学领域中，数据结构是构建算法和程序的基础。

本文将通过分析数据结构910真题试卷的题目，探讨其中涉及的知识点和解题思路。

第一道题目是关于二叉树的遍历。

二叉树是一种常用的数据结构，在实际应用中具有广泛的用途。

题目要求对给定的二叉树进行前序遍历，即先访问根节点，然后按照左子树-右子树的顺序遍历。

解决这个问题可以使用递归的方法，先访问根节点，然后递归遍历左子树和右子树。

第二道题目是关于图的最短路径算法。

图是由节点和边组成的数据结构，它可以用来表示各种实际问题，如网络连接、交通路线等。

题目要求使用Dijkstra算法求解给定图中两个节点之间的最短路径。

Dijkstra算法是一种贪心算法，通过不断更新节点的最短距离来求解最短路径。

首先初始化起始节点的最短距离为0，然后遍历所有节点，更新到达每个节点的最短路径。

最后得到目标节点的最短路径。

第三道题目是关于哈希表的应用。

哈希表是一种常用的数据结构，它可以通过哈希函数将键值映射到存储位置，从而实现高效的查找和插入操作。

题目要求实现一个简单的哈希表，包括插入、删除和查找操作。

解决这个问题可以使用数组和链表结合的方式，通过哈希函数计算键值的存储位置，然后在对应位置的链表中进行插入、删除和查找操作。

第四道题目是关于堆的应用。

堆是一种完全二叉树，它满足堆性质，即父节点的值总是大于或小于其子节点的值。

题目要求使用堆实现一个动态数组，包括插入和删除操作。

解决这个问题可以使用数组来表示堆，通过维护堆性质来实现插入和删除操作。

插入操作将新元素插入到堆的末尾，并通过上浮操作恢复堆性质；删除操作将堆顶元素删除，并通过下沉操作恢复堆性质。

通过分析这些题目，我们可以看到数据结构是计算机科学中的重要组成部分，它涉及到各种常用的数据结构和算法。

掌握数据结构的基本原理和应用方法对于解决实际问题和提高程序效率非常重要。

2009年9月答案解析

2009年9月答案解析

2009年9月二级VF笔试真卷参考答案一、选择题（1）C）【解析】根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。

循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。

（2）B）【解析】栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据；队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。

（3）D）【解析】所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。

循环队列的主要操作是：入队运算和退队运算。

每进行一次入队运算，队尾指针就进一。

每进行一次退队运算，排头指针就进一。

当rear或front等于队列的长度加1时，就把rear 或front值置为1。

所以在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针。

（4）A）【解析】算法的空间复杂度是指执行这个算法所需要的内存空间。

这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。

（5）B）【解析】耦合性与内聚性是模块独立性的两个定性标准。

一般一个较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。

（6）A）【解析】结构化设计方法的主要原则可以概括为自顶向下、逐步求精、模块化限制使用goto语句。

（7）C）【解析】N-S图把整个程序写在一个大框图内，这个大框图是由若干个小的基本框图构成的流程图。

E-R图即实体-联系图（Entity Relationship Diagram），提供了表示实体型、属性和联系的方法，用来描述现实世界的概念模型。

PAD是问题分析图，用二维树形结构的图表示程序的控制流，将这种图转换为程序代码比较容易。

全国2009年1月自考数据结构导论考试试题,答案,笔记分析

全国2009年1月自考数据结构导论考试试题,答案,笔记分析

全国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--2018年(缺少2017年))

自考数据结构02331历年试题及答案(2009--2018年(缺少2017年))

自考数据结构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分)请在每小题的空格中填上正确答案。