自考数据结构02331历年试题及答案全国20XX1月自学考试数据结构试题一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列程序段的时间复杂度为9 s=0； fori=1；i forj=1；j s+=i*j；A.OB.OC.OD.O2.假设某个带头结点的单链表的头指针为head,则判定该表为空表的条件是22A.head=NULL；B.head-next=NULL；C.head!=NULL；D.head-next=head；3.栈是一种操作受限的线性结构,其操作的主要特征是32A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组An存放循环队列的元素,其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素,头指针指向队列中队头元素的前一个位置,则当前存于队列中的元素个数为A.nB.nC.nD.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.下列所示各图中是中序线索化二叉树的是81A10.已知含6个顶点的无向图的邻接矩阵如图所示,则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为108A.B.C.D.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=key11,采用二次探查法处理冲突,则下一个插入的关键字49的地址为d 19715.数据库文件是由大量带有结构的206A.记录组成的集合B.字符组成的集合C.数据项组成的集合D.数据结构组成的集合二、填空题请在每小题的空格中填上正确答案。错填、不填均无分。16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_输入量_。 817.在双向循环链表中插入一个新的结点时,应修改_4_个指针域的值。 2818.若进栈序列为a,b,c,且进栈和出栈可以穿插进行,则可能出现_5_个不同的出栈序列。519.链串的结点大小定义为结点的_数据域_中存放的字符个数。 5420.广义表a,d,的深度为_3_。6721.在含有3个结点a,b,c的二叉树中,前序序列为abc且后序序列为cba的二叉树有_4_棵。422.若用邻接矩阵表示有向图,则顶点i的入度等于矩阵中_。第i列非零元素的个数10723.对关键字序列进行增量为5的一趟希尔排序的结果为_。 15,12,11,10,8,16,18,1724.索引顺序查找的索引表由各分块中的最大关键字及各分块的_起始位置_构成。17325.VSAM文件的实现依赖于操作系统中的_分页_存取方法的功能。 215三、解答题26.假设有一个形如的88矩阵,矩阵元素都是整型量。若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中,请回答下列问题：B数组的体积至少是多少?若a18存储在B0中,a56存储在Bk中,则k值为多少? 1+8*8/2=36 存放次对角线以上的零为37 1227.对关键字序列按从小到大进行快速排序。写出排序过程中前两趟的划分结果；快速排序是否是稳定的排序方法?第一趟划分结果；,5,第二趟划分结果；,5,第三趟划分结果；,5,第四趟划分结果；1,2,3,5,6,7,8,9第一趟划分过程23159687123596871235768912356789ji1234第二趟划分过程1 非稳定2315968712355768956789ji第一趟：2,3,15 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个字符设计哈夫曼编码。要求：画出你所构造的哈夫曼树； 按左分支为0和右分支为1的规则,分别写出与每个字符对应的编码。29.已知3阶B树如图所示,非根 1,2P184根 1,2画出将关键字6插入之后的B树；1,3695,8画出在所得树中插入关键字2之后的B树。1,2,3695,81,3695,81,2,3692,5,81692,5,831692358四、算法阅读题30.假设以带头结点的单链表表示线性表,单链表的类型定义如下：typedef int DataType;typedef struct node DataType data; struct node * next; LinkNode, * LinkList;阅读下列算法,并回答问题：已知初始链表如图所示,画出执行f30之后的链表；题30图简述算法f30的功能。void f30 LinkList p,r, s; if next r = head - next; p = r-next;r - next = NULL; while s =p; p = p-next; if data% 2 = = 0 s - next = head - next; head - next = s; else s - next = r - next; r-next = s; r =s; 285731.假设以二叉链表表示二叉树,其类型定义如下：typedef struct node DataType data; struct node * lchild, * rchild; /左右孩子指针 * BinTree ;阅读下列算法,并回答问题：已知以T为根指针的二叉树如图所示, 写出执行f31之后的返回值；简述算法f31的功能。int f31 int d; if return 0; d = f31 lchild + f31 rchild ; if lchild & T - rchild return d + 1 ; else return d;3统计度为2的结点个数32.设有向图邻接表定义如下：typedef struct VertexNode adjlist MaxVertexNum ; int n,e； 图的当前顶点数和弧数ALGraph； 邻接表类型其中顶点表结点VertexNode边表结点EdgeNode结构为：阅读下列算法,并回答问题：已知某有向图存储在如图所示的邻接 表G中,写出执行f32的输出；简述算法f32的功能。int visited MaxNum ;void DFS EdgeNode * p; visited i = T