自考数据结构02331历年试题及答案.doc

自考数据结构02331历年试题及答案资料仅供参考自考数据结构02331历年试题及答案( - 个人整理版)全国 1月自学考试数据结构试题一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列程序段的时间复杂度为( )9 s=0； for(i=1；in；i+) for(j=1；jnext=NULL；C.head!=NULL；D.head-next=head；3.栈是一种操作受限的线性结构，其操作的主要特征是( )32A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组An存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )A.(rear-front-1)nB.(rear-front)nC.(front-rear+1)nD.(rear-front+n)n5.判断两个串大小的基本准则是( )52A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小6.二维数组A45按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A00的存储地址为1000，则数组元素A32的存储地址为( )60A.1012B.1017C.1034D.1036a00a01a02a03a04a327.高度为5的完全二叉树中含有的结点数至少为( )72A.16B.17C.31D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( )A.5B.8C.11D.189.下列所示各图中是中序线索化二叉树的是( A )81A10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为( )108A.(v0，v1，v2，v5，v4，v3)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v5，v2，v3，v4)D.(v0，v1，v4，v5，v2，v3)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的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( )172A.B.C.D.14.已知一个散列表如图所示，其散列函数为H(key)=key11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( D )d 19715.数据库文件是由大量带有结构的( )206A.记录组成的集合B.字符组成的集合C.数据项组成的集合D.数据结构组成的集合二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.估算算法时间复杂度时考虑的问题规模一般是指算法求解问题的_输入量_。 817.在双向循环链表中插入一个新的结点时，应修改_4_个指针域的值。 2818.若进栈序列为a，b，c，且进栈和出栈能够穿插进行，则可能出现_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.索引顺序查找的索引表由各分块中的最大关键字及各分块的_起始位置_构成。17325.VSAM文件的实现依赖于操作系统中的_分页_存取方法的功能。 215三、解答题(本大题共4小题，每小题5分，共20分)26.假设有一个形如的88矩阵，矩阵元素都是整型量(次对角线以上的元素都是0)。若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题：(1)B数组的体积至少是多少?(2)若a18存储在B0中，a56存储在Bk中，则k值为多少?(1) （1+8）*8/2=36 存放次对角线以上的零为37(2) 1227.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。(1)写出排序过程中前两趟的划分结果；(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第一趟划分过程2315968712359687 1235768912356789ji(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)非稳定2315968712355768956789ji第一趟：（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，928.假设通信电文使用的字符集为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，2】P184根 【1，2】(1)画出将关键字6插入之后的B树；1,3695,8(2)画出在(1)所得树中插入关键字2之后的B树。1,2,3695,81,3695,81,2,3692,5,81692,5,831692358四、算法阅读题(本大题共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)2857(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 ; else return 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 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 ( ! visitedp - adjvex ) DFS( G, p - adjvex) ; p = p-next;void f32 ( ALGraph * G) int i; for (i = 0; i n; i +) visited i = FALSE ; for (i = 0; i n; i+) if ( ! visitedi ) DFS(G, i) ;(1)ABECD(2)图的深度优先搜寻ABCDE33.下列算法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) ) k=i;k 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,int i) Lnode *p,*q;int j;Elemtype x; P=L;j=0; While(p-next!=null&jnext;j+; If(! P-next|inext;x=q-data; P-next=q-next;free(q); Return(x);/*delete_L*/全国 10月自学考试数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.按值可否分解，数据类型一般可分为两类，它们是(c)A.静态类型和动态类型B.原子类型和表类型C.原子类型和结构类型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，且进栈和出栈能够穿插进行，则可能出现的含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.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.多关键字文件答案：D二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请在每个空格中填上正确答案。错填、不填均无分。1.数据的链式存储结构的特点是借助_指针_表示数据元素之间的逻辑关系。2.如果需要对线性表频繁进行_插入_或_删除_操作，则不宜采用顺序存储结构。3.如图所示，能够利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是_ top1top2(或top2=top1-1或top1=top2+1)。4.静态存储分配的顺序串在进行插入、置换和_联接_等操作时可能发生越界。5.广义表L=（a，（b，( )）的深度为_3_。6.任意一棵完全二叉树中，度为1的结点数最多为_1_。7.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中_边_的数目正相关。8.在5阶B树中，每个结点至多含4个关键字，除根结点之外，其它结点至少含_2_个关键字。9.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是_稳定_的。10.常见的索引顺序文件是_ ISAM _文件和_ VSAM _文件。三、解答题(本大题共4小题，每小题5分，共20分)1.答案：2.由字符集s，t，a，e，i及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为，请根据该哈夫曼树进行译码，写出原来的电文。答案：eatst(说明：每个字母1分)（5分）3.已知无向图G的邻接表如图所示，(1)画出该无向图；(2)画出该图的广度优先生成森林。4.对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。初始堆：第1趟：第2趟：答案：初始堆：（96，55，63，48，22，31，50，37，11）（2分）第1趟：（63，55，50，48，22，31，11，37，96）（2分）第2趟：（55，48，50，37，22，31，11，63，96）（1分）四、算法阅读题(本大题共4小题，每小题5分，共20分)1.阅读下列算法，并回答问题：(1)无向图G如图所示，写出算法f30(&G)的返回值；(2)简述算法f30的功能。#define MaxNum 20int visitedMaxNum；void DFS(Graph *g，int i)；/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visitedj为1*/int f30(Graph *g)int i，k；for (i=0； in； i+)*g-n为图g的顶点数目*visitedi=0；for (i=k=0； in; i+)if (visitedi=0)k+；DFS(g，i)；return k；(1)(2)答案：（1）3（3分）（2）返回无向图g中连通分量的个数。（2分）2.假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：typedef struct Node int id;/*学号*/int score；/*成绩*/struct Node *next； LNode， *LinkList；阅读算法f31，并回答问题：(2)简述算法f31的功能。void f31(LinkList A, LinkList B)LinkList p, q;p=A-next;q=B-next;while (p & q)if (p-idid)p=p-next;else if (p-id q-id)q=q-next;else if (p-score score score=q-score;else p-score=60;p=p-next;q=q-next;(1)(2)答案：3.阅读下列算法，并回答问题：(1)设串s=OneWorldOneDream，t=One，pos是一维整型数组，写出算法f32(s，t，pos)执行之后得到的返回值和pos中的值；(2)简述算法f32的功能。int strlen(char*s)； /*返回串s的长度*/int index(char*st，char*t)；*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1*/int f32(char*s, char*t, int pos) int i, j, k, ls, lt;ls=strlen(s);lt=strlen(t);if (ls=0|lt=0) return-1;k=0;i=0;do j=index(s+i, t);if (j=0) posk+=i+j;i+=j+it;while(i+it=0return k;(1)(2)答案：（1）2；pos0=0,pos1=8(说明：每个值1分)（3分）（2）返回串t在s中出现的次数，并将每次出现的位置依次存放在数组pos中。（2分）4.二叉排序树的存储结构定义为以下类型：typedef int KeyType;typedef struct node KeyType key;/*关键字项*/InfoType otherinfo;/*其它数据项*/struct node *lchild, *rchild;/*左、右孩子指针*/ BSTNode, *BSTree；阅读算法f33，并回答问题：(1)对如图所示的二叉排序树T，写出f33(T，8)返回的指针所指结点的关键字；(2)在哪些情况下算法f33返回空指针?(3)简述算法f33的功能。BSTNode *f33(BSTree T, KeyType x) BSTNode *p;if (T=NULL) return NULL;p=f33(T-lchild, x);if (p!=NULL) return p;if (T-key x) return T;return f33(T-rchild, x);(1)(2)(3)答案：（1）10（2分）（2）T是空树或T中所有结点的关键字均不大于给定值x时，返回空指针。（2分）（3）如果二叉排序树T中存在含有关键字大于给定值x的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。（1分）五、算法设计题（本题10分）1.假设线性表采用顺序存储结构，其类型定义如下：#define ListSize 100typedef struct int dataListSize;int length; SeqList, *Table;编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。答案：参考答案一：void f34(Table L)(或者参数说明为：SeqList *L,1分) int i,j,t;i=0;（初始化，1分）j=L-length-1;while(ij)(循环控制，1分) while(idatai%2)（1分）i+;while(idataj%2=0)（1分）j-;if(idatai;（交换，2分）L-datai=L-dataj;L-dataj=t;i+;(i和j,1分)j-;(其它，如“L-”表示，1分)参考答案二：void f34(SeqList*L)(或者参数说明为：Table L,1分) int i,j=0,t;(初始化，1分)for(i=0;ilength;i+)(循环控制，2分)if(L-datai%2)/*奇数*/（奇数处理框架，1分） if(i!=j)(避免同一元素交换，1分) t=L-datai;(交换，2分)L-datai=L-dataj;L-dataj=t;j+;（1分）（其它，如“L-”表示，1分）全国 1月自学考试数据结构试题一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）A问题规模 B语句条数C循环层数 D函数数量2具有线性结构的数据结构是（ C ）线性结构有：顺序表、栈和队列、串A树 B图C栈和队列 D广义表3将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ B ）AO(1) BO(m)CO(n)DO(m+n)插入到长度为m的单链表，需找到表尾，时间复杂度为o(m)，连接的时间复杂度为0(1),因此总的时间复杂度为0(m)4在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ C ）A2个 B3个 C4个D6个void DInsertBefore(DListNode *p,DataType x)/在带头结点的双链表中，将值为x的新结点插入结点*p之前，设pNULL DListNode *s=malloc(sizeof(ListNode);s-data=x;s-prior=p-prior; s-next=p;p-prior-next=s;p-prior=s; 5假设以数组A60存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ）A3 B37C50 D97对于循环向量中的循环队列，写出经过队头队尾指针表示的队列长度公式。（front指向实际队头，rear指向实际队尾的下一元素位置。）当rearfront时，队列长度L=rear-front；当rearfront时，L=m+(rear-front)。这两种情况可统一为L=(m+(rear-front)%m，这里m为向量的大小。本题中m=606若栈采用链式存储结构，则下列说法中正确的是（ B ） A需要判断栈满且需要判断栈空 B不需要判断栈满但需要判断栈空 C需要判断栈满但不需要判断栈空 D不需要判断栈满也不需要判断栈空因为链栈中的结点是动态分配的，能够不考虑上溢，因此无需定义stackFull运算。7若串str=”Software”，其子串的数目是（ D ）A8 B9C36 D378设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ C ）A1012 B1017C1032 D1039在n阶方阵A这个下三角矩阵中，第i（i从0开始）行（0in）有i+1个元素，元素总数为：n(n+1)/2，并将元素放在一个向量sa0. n(n+1)/2-1中。若ij，则aij在左下三角矩阵中，sak与aij的对应关系是k=i(i+1)/2+j。若ij，则aij在右上三角矩阵中，sak与aij的对应关系是k=j(j+1)/2+i。若all为第一个元素， a85与a00为第一个元素时的a(85-(11-00)= a74位置一样，k=7*8/2+4=32，则a85的地址=1000+32=1032；若a44为第一个元素， a85与a00为第一个元素时的a(85-(44-00)= a41位置一样，k=4*5/2+1=11，则a85的地址=1000+11=1011；9允许结点共享的广义表称为（ D ）A纯表 B线性表C递归表 D再入表10下列数据结构中，不属于二叉树的是（ A ）AB树 B树是一种平衡的多叉树BAVL树 AVL树是自平衡二叉查找树C二叉排序树 D哈夫曼树 哈夫曼树是最优二叉树11对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ）A1，5，2，6，3，4 B1，5，6，2，3，4C5，1，6，3，4，2 D5，1，2，6，4，312以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）Av1，v2，v3，v4，v5，v6，v7 Bv1，v2，v5，v4，v3，v7，v6Cv1，v2，v3，v4