数据结构真题

12007年山东省专升本考试数据结构真题一、判断题（10分。本大题共10小题，每小题1分，在小题左面用√表示是，×表示否）1.线性表的顺序存储结构是一种随机存储结构。（）2.一个栈的入栈序列是a,b,c,d,e，则dceab是一个不可能的输出序列。（）3.广义表(a,(a,b),d,e,((i,j),k))的深度是2。（）4.树是一种重要的线性数据结构。（）5.按照二叉树的定义，具有三个结点的二叉树有5种。（）6.已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是求矩阵第i列非零元的个数。（）7.将递归算法转换为对应的非递归算法时，通常需要使用队列。（）8.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同。（）9.散列法存储的基本思想是由关键字的值决定数据的存储地址。（）10.（101，88，46，70，34，39，45，58，66，10）是堆。（）二、填空题（15分。本大题共5小题，5个空，每个空3分，将正确答案填在空格处）。1.将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7,5]的地址为___________。2.若某二叉树有20个叶结点，有30个只有一个孩子的结点，则该二叉树的总结点数为___________。3.如果以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。4.在顺序存储的二叉树中，编号为i和编号为j的结点处在同一层的条件是___________。5.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值为82的结点时，___________次比较后查找成功。三、（10分）已知关键字序列为{46，57，84，32，73，36，15，48，90，20}，要求：（1）构造一棵二叉排序树；（2）在等概率情况下，该二叉排序树查找成功的平均查找长度。2四、（8分）假设在长度大于1的循环链表中，既无头结点，也无头指针，p为指向该链表中某个结点的指针。设计一个算法，删除p指向结点的前趋结点。五.（7分）设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号和花括号，嵌套的顺序任意，如{[()]()}是正确的。请编写一个算法，实现判别给定表达式中所含括号是否正确配对。32008年山东省专升本考试数据结构真题一、单项选择题（10分、每题1分）1、在一个单链表，已知p所指向的是q所指向结点的前驱结点，若在q和p之间插入s所指向的结点，则执行（）A、s-next=q-next;q-next=sB、q-next=s-next;s-next=qC、p-next=s;s-next=qD、q-next=s;s-next=p2、串是（）A、一些符号构成的序列B、一些字母构成的序列C、一个以上的字符构成的序列D、任意有限个字符构成的序列3、数组A[10][10]的下标下界为1，每个元素占2个字节，存储在起始地址为100的连续内存单元，则元素A[3][8]的地址为（）A、138B、154C、111D、1454、已知广义表L=((x,y,z),a,(u,t,w)),则从L中取出原子项y的操作是（）A、head(tail(head(L)))B、head(head(tail(tail(tail(L)))))C、head(tail(tail(tail(tail(L)))))D、head(tail(tail(head(tail(L)))))5、已知完全二叉树有80个结点，则整个二叉树有____个度为2的结点。（）A、39B、41C、40D、386、赫夫曼树中度为1的结点个数为（）A、0B、1C、2D、不确定7、具有n个顶点的有向完全图，边的总数为（）A、nB、n(n-1)C、n-1D、n(n-1)/28、二分查找法适用于存储结构为____的，且按关键字排好序的线性表。（）A、顺序存储B、链接存储C、顺序存储或链接存储D、索引存储9、下列排序算法中，第一趟排序结束后，其最大或最小元素一定在其最终位置上的算法是（）A、归并排序B、直接插入排序C、快速排序D、起泡排序10、一个有向无环图的拓扑序列个数是（）A、1个B、1个或多个C、0个D、多个二、正误判断题（10分，正确打√，错误打×，每小题1分）1、链表中结点数据域占的存储空间越多，存储密度越小。（）2、带头结点和不带头结点的单链表在查找、删除、求长度等操作上无区别。（）3、如果两个串串长相等且对应字符也相同，则这两个串相等。（）4、压缩存储的三角矩阵和对称矩阵的存储空间不相同。（）5、满二叉树是完全二叉树。（）6、对于给定的树，与其对应的二叉树是唯一的。（）7、线索二叉树的指针域中，指向前驱或后继的个数少于指向孩子的个数。（）8、给定图的邻接矩阵存储不一定唯一。（）9、若一个有向图的邻接矩阵主对角线以下的元素均为0，则该图拓扑有序序列存在。（）10、对n个记录进行直接插入排序，其平均时间复杂度为O(nlog2n）。（）三、填空题（10分，1题每空2分，其他题每空1分）1、下列函数的功能是实现带头结点的单链表逆置。voidturn(slink*L){slink*p,*q;p=_____________________________;L-next=NULL;4while(___________________________){q=p;p=___________________________;q-next=L-next;L-next=q;}}2、“算法”（Algorithm）就是对求解问题步骤的一种描述，也称为算法设计。它具有以下五个特征有穷性，_____________,_______________，输入和输出。3、评价算法好坏的五个方面_______________,_______________,正确性，可读性，健壮性。四、操作计算题（10分，每题5分）1、有一组关键字序列（24，19，56，13，97，59，41，85，1，87），写出用堆排序法进行升序排序的初始堆序列及第一趟排序后的堆序列。2、给定如下图所示的带权无向图G1。（1）画出该图的邻接矩阵（2）给出采用普里姆算法从顶点3出发构造最小生成树的的过程。五、算法设计题（10分）给定二叉树，采用链式结构存储，编写算法voidcount(BitTreebt),实现功能：统计二叉树中度为1的结点数目。123465910511877652009年山东省专升本考试数据结构真题一、填空题（10分，每空0.5分）1、根据数据元素之间关系的不同，数据的逻辑结构划分为______、______、______、______。2、栈是一种特殊的线性表，它允许在表的一端进行____________操作，栈中元素的进出原则为__________________。3、深度为k的二叉树其结点数最多有______个结点。4、通常象交通、道路问题的数学模型是一种称为____________的数据结构。5、算法的五个重要的特征是______、______、______、______、______。6、两个字符串相等的充分必要条件是____________________________________。7、在一棵二叉树中，度为零的结点个数为0n，度为2的结点个数为2n，则有0n=______。8、树的度是指__________________________________________的最大值。9、在一个有向图中，某个结点的度是指该结点的______和______之和。10、在线性表的二分查找法中要求线性表的存储结构必须是采用____________，且表中的元素必须是____________。二、选择题（10分，每题1分）1.一个具有10个顶点的无向完全图应有______条边。()A.9B.45C.55D.902.长度为n（1…n）的顺序循环队列中，front和rear分别指示队首和对尾，判断队列为满队列的条件是()A.rear=frontB.(rear+1)%n=frontC.rear=0D.front=03.由______组成的集合是一个数据对象。()A.不同类型的数据项B.不同类型的数据元素C.相同类型的数据项D.相同类型的数据元素4.______是表示线性数据结构的。()A.循环链表B.邻接多重表C.孩子链表D.单链表5.设一个栈的入栈元素序列为a，b，c，d，e，则不可得到出栈的元素序列有()。A.edcbaB.decbaC.dceabD.abcde66.______又是一棵满二叉树。()A.二叉排序树B.深度为5有31个结点的二叉树C.有15个结点的完全二叉树D.哈夫曼（Huffman）树7.折半查找有序表（2，5，8，20，25，36，40，60），若查找元素60，需依次与表中元素______进行比较。()A.20，36，40，60B.25，40C.25，40，60D.20，36，408.查找哈希（Hash）表，解决冲突的方法有()。A.链地址法B.线性探测再散列法C.直接地址法D.除留余数法9.一个排序算法时间复杂度的大小______有关。()A.不与所需移动记录的数目B.与该算法的稳定性C.与所需比较关键字的次数D.与所需辅助存储空间的大小10.数据的基本单位是。()A.结点B.数据元素C.数据类型D.数据项三、求解下列问题（10分，每题5分）1.将下面的一个普通书转换成一棵二叉树，并写出它先序、中序、后序三种遍历的遍历序列。转换后的二叉树：ABGHCDEFIKJLM先序遍历序列：中序遍历序列：7后序遍历序列：2.用克鲁斯卡尔算法将下面的图构造成最小生成树，画出生成过程。0152345636625514四、程序填空（10分，每空1分）1.将下面折半查找算法补充完整算法说明：已知r[1…n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下：#defineMAXSIZE100typedefstruct{keytypekey;}Nodetype;typedefNodetypeSqlist[MAXSIZE];算法（C函数）：8intbinsearch(Sqlistr,datatypek,intn){intlow=1,high=n,mid;while(_______________){_______________;if(r[mid].key==k)_______________;elseif(r[mid].keyk)_______________else_______________}return(0);}2.将下面单链表的插入算法补充完整。算法说明：在带有头结点的单链线性表中第i个位置之前插入元素x:typedef_______________{DataTypedata;structnode*next;}LNode,*LinkList;intlistinsert(LinkListhead,inti,DataTypex){LinkListp=head.sintj=0;while(p!=NULL&&ji-1){_______________;j++;}9if(p==NULL)return(0);s=_______________malloc(sizeof(LNode));s-data=x;_______________;_______________;return(1);}五、算法设计（10分）已知S为顺序栈。写出S的存储结构类型描述。编写算法实现将元素x入栈操作Push(S,x)，入栈成功返回1，否则返回0和删除栈顶元素的出栈操作Pop(S)出栈成功返回1，否则返回0。102010年山东省专升本考试数据结构真题一、判断题（每小题1分，共5分）1.算法的执行时间和所需的存储空间都是问题规模的函数，进行算法分析就是要找出这种函数关系。（）