2024年数据结构真题

山東省专升本考试数据构造真題一、判断題（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）在等概率状况下，该二叉排序树查找成功的平均查找長度。四、（8分）假设在長度不小于1的循环链表中，既無頭結點，也無頭指针，p為指向该链表中某個結點的指针。设计一种算法，删除p指向結點的前趋結點。五.（7分）设算术体現式由字符串b表达，其中可以包括三种括号：圆括号、方括号和花括号，嵌套的次序任意，如{[()]()}是對的的。請编写一种算法，实現鉴别給定体現式中所含括号与否對的配對。山東省专升本考试数据构造真題一、單项选择題（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;while(___________________________){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的結點数目。山東省专升本考试数据构造真題一、填空題（10分，每空0.5分）1、根据数据元素之间关系的不一样，数据的逻辑构造划分為______、______、______、______。2、栈是一种特殊的线性表，它容許在表的一端進行____________操作，栈中元素的進出原则為__________________。深度為k的二叉树其結點数最多有______個結點。4、一般象交通、道路問題的数學模型是一种称為____________的数据构造。5、算法的五個重要的特性是______、______、______、______、______。6、两個字符串相等的充足必要条件是____________________________________。7、在一棵二叉树中，度為零的結點個数為，度為2的結點個数為，则有=______。8、树的度是指__________________________________________的最大值。9、在一种有向图中，某個結點的度是指该結點的______和______之和。10、在线性表的二分查找法中规定线性表的存储构造必须是采用____________，且表中的元素必须是____________。二、选择題（10分，每題1分）一种具有10個顶點的無向完全图应有______条边。()A.9 B.45 C.55 D.90長度為n（1…n）的次序循环队列中，front和rear分别指示队首和對尾，判断队列為满队列的条件是()A.rear=front B.(rear+1)%n=frontC.rear=0 D.front=0由______构成的集合是一种数据對象。()A.不一样类型的数据项 B.不一样类型的数据元素C.相似类型的数据项 D.相似类型的数据元素______是表达线性数据构造的。()A.循环链表 B.邻接多重表C.孩子链表 D.單链表设一种栈的入栈元素序列為a，b，c，d，e，则不可得到出栈的元素序列有()。A.edcba B.decba C.dceab D.abcde______又是一棵满二叉树。()A.二叉排序树 B.深度為5有31個結點的二叉树C.有15個結點的完全二叉树 D.哈夫曼（Huffman）树折半查找有序表（2，5，8，20，25，36，40，60），若查找元素60，需依次与表中元素______進行比较。()A.20，36，40，60 B.25，40C.25，40，60 D.20，36，40查找哈希（Hash）表，处理冲突的措施有()。A.链地址法 B.线性探测再散列法C.直接地址法 D.除留余数法一种排序算法時间复杂度的大小______有关。()A.不与所需移動记录的数目B.与该算法的稳定性C.与所需比较关键字的次数D.与所需辅助存储空间的大小数据的基本單位是。()A.結點 B.数据元素 C.数据类型 D.数据项三、求解下列問題（10分，每題5分）1.将下面的一种一般書转换成一棵二叉树，并写出它先序、中序、後序三种遍历的遍历序列。转换後的二叉树：先序遍历序列：中序遍历序列：後序遍历序列：2.用克鲁斯卡尔算法将下面的图构导致最小生成树，画出生成過程。四、程序填空（10分，每空1分）1.将下面折半查找算法补充完整算法阐明：已知r[1…n]是n個记录的递增有序表，用折半查找法查找关键字為k的记录，若查找失败返回零；否则返回该记录的序号值。查找表次序存储构造定义如下：#define MAXSIZE 100typedef struct{ keytype key;}Nodetype;typedef Nodetype Sqlist[MAXSIZE];算法（C函数）：int binsearch(Sqlistr,datatypek,intn){ intlow=1,high=n,mid; while(_______________) { _______________; if(r[mid].key==k) _______________; elseif(r[mid].key>k) _______________ else _______________ } return(0);}2.将下面單链表的插入算法补充完整。算法阐明：在带有頭結點的單链线性表中第i個位置之前插入元素x:typedef_______________{ DataTypedata; structnode*next;}LNode,*LinkList;intlistinsert(LinkListhead,inti,DataTypex){ LinkListp=head.s intj=0; while(p!=NULL&&j<i-1) { _______________; j++; } if(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。山東省专升本考试数据构造真題一、判断題（每題1分，共5分）1.算法的执行時间和所需的存储空间都是問題规模的函数，進行算法分析就是要找出這种函数关系。（）2.完全二叉树只能采用次序存储措施，不能采用链表存储措施。（）3.在次序循环队列的第i個元素之後插入一种元素是次序循环队列的基本运算。（）4.若一种叶子是某二叉树的中序遍历的最终一种結點，则它必是该二叉树的前序遍历的最终一种結點。（）5.直接插入排序的关键码比较次数与初始排列有关。（）二、單项选择題（每題2分，共10分）1.如下数据构造中哪一种是线性构造（）A.栈B.线索二叉树C.AOV网D.二叉排序树2.若有a，b，c三個字符的字符序列执行入栈操作，则其所有也許的输出排列共有（）A.4种B.5种C.6种D.其他3.一棵树的广义表表达為a(b,c(e,f(g)),d)，當用左孩子—右兄弟链表表达時，右指针域非空的节點個数為（）A.1B.2C.3D.44.下面有关图的存储的论述中對的的是（）A.用邻接矩阵法存储图，占用的存储空间大小与图中結點個数和边数均有关B.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与結點個数無关C.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与結點個数無关D.用邻接表法存储图，占用的存储空间大小与图中边数和結點個数均有关5.對長度為12的有序表采用次序存储构造，折半查找技术，在等概率状况下，查找成功的平均查找長度是（）A.37/12B.62/13C.49/12D.其他三、应用題（每題5分，共20分）1、已知一棵三叉树的存储构造如下表所示，其中root=0，n=7。画出该二叉树。2、用克鲁斯卡尔算法求下图的最小生成树。3、下图是一棵二叉排序树，规定當二叉排序树被删除的結點既有左子树，又有右子树時，以其中序前驱替代。画出删除55後的二叉排序树。4、已知散列表地址空间為HT[0..8]，散列函数為H(key)=key%7，采用线性探测法处理冲突，将数据序列{107,27,28,42,3,25,99,38}依次存入散列表中。试画出對应的散列表；并计算等概率下搜索成功的平均搜索長度。散列表及其查找各关键字要比较的次数如下所示：012345678关键字比较次数搜索成功的平均搜索長度為：ASL=四、算法设计題（每題5分，共15分）1.已知次序栈s，简述f1函数功能，當输入80時，输出成果是多少？f1(){initstack(s);scanf(“%d”,&n);while(n){push(s,n%8);n=n/8)}while(!Emptystcak(s)){pop(s,x);printf(“%d”,x);}}2.写出二叉树前序遍历非递归算法的设计思想，然後写出算法。3.写出直接插入排序算法。山東省专升本考试数据构造真題一、选择題（本大題共10小題，每題1分，共10分）1.数据构造，与所使用的计算机無关的是数据的哪种构造（）A.存储B.物理C.逻辑D.物理和存储2.线性表是（）A.一种有限序列，可认為空B.一种有限序列，不能為空C.一种無限序列，可认為空D.一种無限序列，不能為空3.下列哪個选项的邻接矩阵必然是對称矩阵（）A.有向图B.無向图C.AOV网D.AOE网4.串是一种特殊的线性表，其特殊性体目前（）A.可以次序存储B.数据元素是一种字符C.可以链式存储D.数据元素可以是多种字符5.不含任何結點的空树是（）A.是一棵树B.是一棵二叉树C.是一棵树也是一棵二叉树D.既不是树也不是二叉树6.已知一维数组A采用次序存储构造，每個元素占用4個存储單元，第9個元素的地址為144，则第一种元素的地址是（）A.108B.180C.176D.1127.链表合用于哪种查找措施（）A.次序B.二分法C.次序，也能二分法D.随机8.用邻接表表达图，進行广度优先遍历時，一般是采用哪种构造来实現算法的。（）A.栈B.队列C.树D.图9.任何一种無向连通图的最小生成树是（）A.只有一棵B.一棵或多棵C.一定有多棵D.也許不存在10.若某完全二叉树的結點個数為100，则第60個結點的度為（）A.0B.1C.2D.不确定二、填空題（本大題共5小題，每題2分，共10分）1、一棵深度為6的满二叉树有個分支點和個叶子。2、一种字符串相等的充要条件是和。3、從邻接矩阵A=可以看出，该图共有個顶點。假如是有向图，该图共有条弧。4、栈的特點是，队列的特點是。5、三元组表中的每個节點對应与稀疏矩阵的一种非零元素，它包具有三個数据项，分别表达该元素的、和值。三、简答題（本大題共2小題，每題5分，共10分）1、已知二叉树（如图）請給出它的3种遍历序列先序：中序：後序2、简述数据构造的概念？在讨论数据构造時，一般會從哪三個方面進行？四、操作題（本大題共2小題，每題10分，共20分）1、已知一组关键字為{19,14,23