1、自考数据结构 02331 历年试题及答案(2009-2015 个人整理版)全国 2009 年 1 月自学考试数据结构试题一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列程序段的时间复杂度为( )9s=0；for(i=1；inext=NULL；C.head!=NULL； D.head-next=head；3.栈是一种操作受限的线性结构，其操作的主要特征是( )32A.先进先出 B.后进先出C.进优于出 D.出优于进4.假设以数组 An存放循环队列的元素，其头、尾指
2、针分别为 front 和 rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )A.(rear-front-1)n B.(rear-front)nC.(front-rear+1)n D.(rear-front+n)n5.判断两个串大小的基本准则是( )52A.两个串长度的大小 B.两个串中首字符的大小C.两个串中大写字母的多少 D.对应的第一个不等字符的大小6.二维数组 A45按行优先顺序存储，若每个元素占 2 个存储单元，且第一个元素 A00的存储地址为 1000，则数组元素 A32的存储地址为( )60A.1012 B.1017
3、C.1034 D.10367.高度为 5 的完全二叉树中含有的结点数至少为( )72A.16 B.17C.31 D.328.已知在一棵度为 3 的树中，度为 2 的结点数为 4，度为 3 的结点数为 3，则该树中的叶子结点数为( )A.5 B.8C.11 D.189.下列所示各图中是中序线索化二叉树的是( A )81A10.已知含 6 个顶点(v 0，v 1，v 2，v 3，v 4，v 5)的无向图的邻接矩阵如图所示，则从顶点 v0出发进行深度优先遍历可能得到的顶点访问序列为( )108A.(v0，v 1，v 2，v 5，v 4，v 3)B.(v0，v 1，v 2，v 3，v 4，v 5)C.
4、(v0，v 1，v 5，v 2，v 3，v 4)D.(v0，v 1，v 4，v 5，v 2，v 3)a00 a01 a02 a03 a04a3211.如图所示有向图的一个拓扑序列是( )A.ABCDEFB.FCBEADC.FEDCBAD.DAEBCF12.下列关键字序列中，构成大根堆的是( )A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，313.对长度为 15 的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( )172A. B.159 49C.
5、 D. 1514.已知一个散列表如图所示，其散列函数为 H(key)=key11，采用二次探查法处理冲突，则下一个插入的关键字 49 的地址为( D )d 19715.数据库文件是由大量带有结构的( )206A.记录组成的集合 B.字符组成的集合C.数据项组成的集合 D.数据结构组成的集合二、填空题(本大题共 10 小题，每小题 2 分，共 20 分)请在每小题的空格中填上正确答案。错填、不填均无分。16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_输入量_。 817.在双向循环链表中插入一个新的结点时，应修改_4_个指针域的值。 2818.若进栈序列为 a，b，c，且进栈和出栈
6、可以穿插进行，则可能出现_5_个不同的出栈序列。519.链串的结点大小定义为结点的_数据域_中存放的字符个数。 5420.广义表(a，(d，(c)的深度为_3 _。6721.在含有 3 个结点 a，b，c 的二叉树中，前序序列为 abc 且后序序列为 cba 的二叉树有_4_棵。422.若用邻接矩阵表示有向图，则顶点 i 的入度等于矩阵中_。第 i 列非零元素的个数 10723.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为 5 的一趟希尔排序的结果为_。15，12，11，10，8，16，18，1724.索引顺序查找的索引表由各分块中的最大关键字及各分块的_
7、起始位置_构成。17325.VSAM 文件的实现依赖于操作系统中的_分页_存取方法的功能。 215三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)26.假设有一个形如的 88 矩阵，矩阵元素都是整型量(次对角线以上的元素都是 0)。若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组 B 中，请回答下列问题：(1)B 数组的体积至少是多少?(2)若 a18存储在 B0中，a 56存储在 Bk中，则 k 值为多少?(1) （1+8）*8/2=36 存放次对角线以上的零为 37(2) 1227.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。(1)写出
8、排序过程中前两趟的划分结果；(2)快速排序是否是稳定的排序方法?(1)第一趟划分结果；(2，3，1)，5，(9，6，8，7)第二趟划分结果；(1，2，3)，5，(9，6，8，7)第三趟划分结果；(1，2，3)，5，(7，6，8，9)第四趟划分结果； 1，2，3，5，6，7，8，9第一趟划分过程(5，8，1，3，9，6，2，7)1(2，8，1，3，9，6，5，7)2(2，5，1，3，9，6，8，7)3(2，3，1，5，9，6，8，7)4(2，3，1，5，9，6，8，7)第二趟划分过程(2，3，1，5，9，6，8，7)1(1，2，3，5，7，6，8，9)(2)非稳定第一趟：（2，3，1）5 （9，
9、6，8，7）2 3 1 5 9 6 8 71 2 3 5 9 6 8 71 2 3 5 7 6 8 91 2 3 5 6 7 8 92 3 1 5 9 6 8 71 2 3 55 7 6 8 95 6 7 8 9ijij第二趟： 1，2，3，5 （9，6，8，7）第三趟：1，2，3，5， （7，6，8） ，9第四趟：1，2，3，5，6，7，8，928.假设通信电文使用的字符集为a，b，c，d，e，f，g，h，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这 8 个字符设计哈夫曼编码。要求：(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权
10、值)；(2)按左分支为 0 和右分支为 1 的规则，分别写出与每个字符对应的编码。(1)(2)29.已知 3 阶 B树如图所示，非根 【1，2】P184根 【1，2】(1)画出将关键字 6 插入之后的 B树；1,3 6 95,8(2)画出在(1)所得树中插入关键字 2 之后的 B树。四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分)30.假设以带头结点的单链表表示线性表，单链表的类型定义如下：typedef int DataType;typedef struct node DataType data;struct node * next; LinkNode, * LinkLis
11、t;阅读下列算法，并回答问题：(1)已知初始链表如图所示，画出执行 f30(head)之后的链表；1,3 6 95,81,2,3 6 95,81,2,3 6 92,5,81 6 92,5,831 6 92358题 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
12、;head - next = s; else s - next = r - next;r-next = s;r =s;(1)2 8 5 7(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 =
13、f31 ( T - lchild) + f31 ( T - rchild) ;if (T - lchild elsereturn d;(1)3(2)统计度为 2 的结点个数32.设有向图邻接表定义如下：typedef struct VertexNode adjlist MaxVertexNum ;int n，e； 图的当前顶点数和弧数ALGraph； 邻接表类型其中顶点表结点 VertexNode边表结点 EdgeNode 结构为：阅读下列算法，并回答问题：(1)已知某有向图存储在如图所示的邻接表 G 中，写出执行 f32(G)的输出；(2)简述算法 f32 的功能。int visited M
14、axNum ;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 ( ! visitedp - adjvex )DFS( G, p - adjvex) ;p = p-next;void f32 ( ALGraph * G) int i;for (i = 0; i n
15、; i +)visited i = FALSE ;for (i = 0; i n; i+)if ( ! visitedi ) DFS(G, i) ;(1)ABECD(2)图的深度优先搜寻33.下列算法 f33 的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。#define MAXLEN 100typedef int KeyType;typedef struct KeyType key;InfoTyp
16、e otherinfo; NodeType ;typedef NodeType SqList MAXLEN ;void f33 ( SqList R, int n) int i,j,k;NodeType t;ABCDEi =0;j =n-l;while (i Rk +l.key) t = Rk;Rk = Rk +1;Rk +1 = t;j-;for (k =j; k i; k - )if ( (2) ) Rk.key next;max=head-next;while(P)P=p-next;If(p-datamax-data) max=p;x=max-data;delete_L(Lnode *L
17、,int i)Lnode *p,*q;int j;Elemtype x;P=L;j=0;While(p-next!=nullj+;If(! P-next|inext;x=q-data;P-next=q-next;free(q);Return(x);/*delete_L*/全国 2009 年 10 月自学考试数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1. 按值可否分解，数据类型通常可分为两类，它们是(c)A. 静态类型和动态类型B. 原子类型和表类型C. 原子类型和
18、结构类型D. 数组类型和指针类型2. A. A f(n)是0(g(n)B. B g(n)是0(f(n)C. C h(n)是0(nlogn)D. D h(n)是0(n2)答案：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，且进
19、栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是()A. 3B. 5C. 6D. 7答案：B5. 假设以数组An存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为()A. rear=frontB. (front+1)n=rearC. rear+1=frontD. (rear+1)n=front答案：D6. 串的操作函数str定义为：A. 3B. 4C. 5D. 6答案：C7. 二维数组A106采用行优先的存储方法，若每个元素占4个存储单元，已知元素A34的存储地址为1000，则元素A43的存储地址为()A. 1020B. 1024C. 1036D. 1240答案：A8. 对广义表L= (a，()执行操作tail(L)的结果是()A. ()B. ()C. aD. (a)答案：B9. 已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为()A. FEDCBA
