您好,欢迎访问三七文档
一、填空题(本题共10小题,每个空2分,共20分)1.根据数据元素之间的关系的不同特性,通常有下列4类基本逻辑结构:集合、线性结构、(树结构)和图结构。2.一个算法的优劣应该从以下几方面来评价:正确性、可读性、(健壮性)和高效性。3.顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的,链接存储结构中的数据元素之间的逻辑关系是由(指针)表示的。4.顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是(108)。5.循环队列的引入是为了克服(假溢出)。**6.广义表C=((((a),b)),(((),y))),则tail(head(tail(C)))=(())。**7.已知一棵完全二叉树共有768个结点,则该树中有(384)个叶子结点。**8.某二叉树的先序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,则其后序遍历序列是(CDBGFEA)。9.有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的(出度)。10.对n个待排序记录序列进行快速排序,其最坏时间复杂度为(O(n2))。二、选择题(本题共10小题,每个空2分,共24分)1.算法是指(A)A.对特定问题求解步骤的一种描述,是指令的有限序列B.计算机程序C.解决问题的计算方法D.数据处理2.若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱,则采用(A)存储方法最节省时间。A.顺序表B.单链表C.双链表D.单循环链表3.设计一个判别表达式中左右括号是否配对的算法,采用(B)数据结构最佳。A.队列B.栈C.链表D.树4.串是一种特殊的线性表,其特殊体现在(B)A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符**5.二维数组A[9][10]采用列优先存储方法,若每个元素各占6个存储单元,则存放A至少需要多少个字节?(C)A.90B.180C.540D.240**6.二叉树的先序序列和后序序列正好相反,则该棵二叉树一定是(C)的二叉树。A.空或只有一个结点B.任一结点无左孩子C.高度等于其结点数D.任一结点无右孩子座位号**7.若一棵二叉树有10个叶子结点,则该二叉树中度为2的结点个数是(D)A.11B.10C.不确定D.98.G是一个非连通图,共有28条边,则该图至少有多少个顶点?(D)A.6B.7C.8D.99.任何一个无向连通图的最小生成树有(A)A.一棵或多棵B.只有一棵C.一定有很多棵D.可能不存在10.二叉排序树中,最小值的结点的(B)A.右指针一定为空B.左指针一定为空C.左、右指针均一定为空D.左、右指针均不为为空11.堆排序中堆的形状是一棵(C)A.二叉排序树B.满二叉树C.完全二叉树D.普通二叉树12.在索引非顺序文件中,建立的索引表是(D)A.稀疏索引B.链接索引C.多级索引D.稠密索引三、名词解释(本题共3小题,每小题2分,共6分)算法——对特定问题求解步骤的一种描述,是指令的有限序列。数据结构——相互之间存在一种或多种特定关系的数据元素的集合。栈——限定仅在表尾进行插入或删除操作的线性表。四、应用题(本题共5小题,每小题7分,共35分)**1、简述以下算法的功能(**重要**)(栈的元素类型SElemType为int)。Statusalgo(StackS){inti,n=0,A[255];while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=1;i=n;i++)Push(S,A[i]);}若空栈,则StackEmpty(S)=true解:利用数组A把栈S中的元素逆序重排。2、有一份电文中共使用五个字符:a、b、c、d、e,它们的出现频率依次为(8、14、10、4、18),请构造相应的哈夫曼树(要求左子树根结点的权小于等于右子树根结点的权),求出每个字符的哈夫曼编码。解:哈夫曼树为:(2分)相应的哈夫曼编码为:a:011;b:10;c:00;d:010;e:11(每个1分)3、令s=’aaab’,t=’abcabaa’。试分别求出它们的next函数值和nextval函数值。解:串s的next函数值为:0123;(1.5分)nextval函数值为:0003;(1.5分)串t的next函数值为:0111232;(2分)nextval函数值为:0110132。(2分)4、设有三对角矩阵(ai,j)n╳n,将其三条对角线上的元素逐行的存于数组B(1:3n-2)中,使得B[k]=ai,j,求:(1)用i,j表示k的下标变换公式;(2)若n=103,每个元素占用L个单元,则用B[K]方式比常规存储节省多少单元。解:(1)k=2i+j-1(|i-j|=1;1k3n-2);(4分)(2)省了L*(103*103-(3*103-2))=997002L个单元。(3分)5、某AOE网如下图,问事件4的最早发生时间与最迟发生时间,活动E的最早开始时间与最迟开始时间和该AOE网代表的工程完成的最短时间(即关键路径的长度)。解:事件4的最早发生时间=15(1分)最迟发生时间=18(1分)活动E的最早开始时间=3(1分)最迟开始时间=3(1分)该AOE网代表的工程完成的最短时间=33(3分)五、程序填空:(共2小题,每小空2分,共10分)基于三元组顺序表的矩阵转置算法#defineMAXSIZE12500typedefstruct{inti,j;ElemTypee;}Triple;//三元组类型typedefunion{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;//稀疏矩阵类型StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(①T.tu){for(col=1;col=M.nu;++col)num[col]=0;for(t=1;t=M.tu;++t)②++num[M.data[t].j];③cpot[1]=1;for(col=2;col=M.nu;++col)④cpot[col]=cpot[col-1]+num[col-1];for(p=1;p=M.tu;++p){Col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;⑤++cpot[col];}}//ifreturnOK;}//FastTransposeSMatrix六、程序设计题(共5分)请写一个算法,统计二叉树中叶子结点的个数,设此二叉树以二叉链表做存储结构。解:voidCountLeaf(BiTreeT,int&count)(1分){if(T)(1分){if((!T-lchild)&&(!T-rchild))count++;//对叶子结点计数(1分)CountLeaf(T-lchild,count);(1分)CountLeaf(T-rchild,count);(1分)}//if}//CountLeafintLeafNodeCount(BiTreeT)P109{if(T==NULL)return0;//如果是空树,则叶子结点个数elseif(T-lchild==NULL&&T-rchild==NULL)return1;//判断该结点是否是叶子结点(左孩子右孩子都为空),若是则返回1elsereturnLeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);}
本文标题:数据结构样卷
链接地址:https://www.777doc.com/doc-2334122 .html