专升本十套-数据结构(试题及答案).doc

数据结构试卷（一）一、单选题（每题 2分,共20分）1. 栈与队列得共同特点就是( )。A、只允许在端点处插入与删除元素、都就是先进后出 C、都就是先进先出D、没有共同点 2. 用链接方式存储得队列,在进行插入运算时（ ）、 A、 仅修改头指针 B、 头、尾指针都要修改 C、 仅修改尾指针 、头、尾指针可能都要修改3. 以下数据结构中哪一个就是非线性结构？( ) 、队列 、 栈 C、线性表 、二叉树4. 设有一个二维数组Amn，假设0存放位置在644（10）,A2存放位置在76（0）,每个元素占一个空间，问A33(10)存放在什么位置？脚注(0）表示用10进制表示。 A.68 B8 C.62 D695. 树最适合用来表示（ )。 、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系得数据 D、元素之间无联系得数据6. 二叉树得第k层得结点数最多为( )、 。 B、2K+1 C、2K-1 D、 2k-7. 若有8个元素得有序表存放在一维数组A19中，第一个元素放A中,现进行二分查找，则查找3得比较序列得下标依次为( ) A、1,2,3、 9，5，2， C、 9，,3D、 9,4，2，38. 对个记录得文件进行快速排序，所需要得辅助存储空间大致为 A、 (1） 、O（） C、 O（1og2n) D、 O(n)9. 对于线性表(7,34,5，25,64，6，20,10）进行散列存储时，若选用H（K）=K %9作为散列函数,则散列地址为1得元素有（ ）个， A。1 B2 C3 D410. 设有6个结点得无向图,该图至少应有（ )条边才能确保就是一个连通图。 A、5 B、6 C、7 、8二、填空题（每空1分,共26分）1. 通常从四个方面评价算法得质量：_、_、_与_.2. 一个算法得时间复杂度为（n2ogn+14n）n,其数量级表示为_.3. 假定一棵树得广义表表示为A(C，（E,F，G），H(I，J），则树中所含得结点数为_个，树得深度为_，树得度为_。4. 后缀算式9 2 3 + 12 得值为_.中缀算式（+4X)2Y/3对应得后缀算式为_。5. 若用链表存储一棵二叉树时,每个结点除数据域外，还有指向左孩子与右孩子得两个指针。在这种存储结构中,n个结点得二叉树共有_个指针域，其中有_个指针域就是存放了地址，有_个指针就是空指针。6. 对于一个具有n个顶点与e条边得有向图与无向图,在其对应得邻接表中，所含边结点分别有_个与_个。7. AOV网就是一种_得图。8. 在一个具有n个顶点得无向完全图中，包含有_条边，在一个具有n个顶点得有向完全图中，包含有_条边。9. 假定一个线性表为（12，23，,，3，0)，若按Ke 4条件进行划分，使得同一余数得元素成为一个子表，则得到得四个子表分别为_、_、_与_。10. 向一棵B_树插入元素得过程中,若最终引起树根结点得分裂，则新树比原树得高度_。11. 在堆排序得过程中,对任一分支结点进行筛运算得时间复杂度为_,整个堆排序过程得时间复杂度为_。12. 在快速排序、堆排序、归并排序中，_排序就是稳定得.三、计算题（每题 分,共4分)1. 在如下数组A中链接存储了一个线性表，表头指针为 0、ext，试写出该线性表. 0 1 2 3 4 5 6 7data6nex3572412. 请画出下图得邻接矩阵与邻接表。3. 已知一个图得顶点集V与边集E分别为：V=1，2，3,，5，6,； E=(1，)3，（1，3）5，(1，4），（，）0,（,3）6，（，4）1,（，5)1,（3,6)，（,）4，（4，）20，（5,6）18,（6,7）25； 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到得各条边。4. 画出向小根堆中加入数据4， 2, 8， 3时，每加入一个数据后堆得变化。四、阅读算法（每题7分,共1分)1. nLs me（LinkLit L) /就是不带头结点得单链表得头指针 if(L&next） qL;L=next;p=L； S1: whle（p-et） =next; S： pet=q；qexUL; eturn L； 请回答下列问题： (1)说明语句1得功能; （2）说明语句组S2得功能; （）设链表表示得线性表为(1，a2， ,a)，写出算法执行后得返回值所表示得线性表.2. vo A（BTNde) if AC（Blet); ABC（BTrght); outBdta ； 该算法得功能就是:五、算法填空（共8分）二叉搜索树得查找-递归算法:ol Fin（reode BT，Elemye& itm) i (BS=NLL） rtr fals; 查找失败 ee if(itBSTdaa) ite=BS-ta;/查找成功 eturn ._； ele f(itmBSta） rrn Fin（_，im）； ese reur in（_,iem）； /i六、编写算法（共8分）统计出单链表H中结点得值等于给定值X得结点数。 n CntX(LNde H,lemTpe x)数据结构试卷(二)一、选择题（24分）.下面关于线性表得叙述错误得就是( )。（)线性表采用顺序存储必须占用一片连续得存储空间(B） 线性表采用链式存储不必占用一片连续得存储空间（) 线性表采用链式存储便于插入与删除操作得实现（） 线性表采用顺序存储便于插入与删除操作得实现2。设哈夫曼树中得叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。（）2m(B） m(C） m+（D) m3.设顺序循环队列Q0:1得头指针与尾指针分别为F与R,头指针总就是指向队头元素得前一位置,尾指针R总就是指向队尾元素得当前位置，则该循环队列中得元素个数为（ ）。（） R（B）FR（C） (F+M)（D) （F-R+)%.设某棵二叉树得中序遍历序列为ACD,前序遍历序列为CBD,则后序遍历该二叉树得到序列为( ）。(） AD(B) CD(） CAB(D） CBDA。设某完全无向图中有个顶点，则该完全无向图中有（ )条边。（A) n（n）2（B） n（n-）（C) n2 (D) n216设某棵二叉树中有200个结点，则该二叉树得最小高度为（ ）.（A) 9（） 10(C)() 127.设某有向图中有个顶点，则该有向图对应得邻接表中有( )个表头结点.（A） n-（B） (C) n+1() n18。设一组初始记录关键字序列(,6，3，8),以第一个记录关键字5为基准进行一趟快速排序得结果为（ )。(） ，3，5，8，6(B)3，2，5,8，6(C）3，,6,8(D） ,3,6,5,8二、填空题（24分）1. 为了能有效地应用HA查找技术,必须解决得两个问题就是_与_。2. 下面程序段得功能实现数据x进栈，要求在下划线处填上正确得语句.typee struc int s10； nt top; sqtack；id psh(sqstck sck，int x)if （stak、to=m） pritf(“ovrfow”）;ee_；_；3. 中序遍历二叉排序树所得到得序列就是_序列（填有序或无序)。4. 快速排序得最坏时间复杂度为_,平均时间复杂度为_.5. 设某棵二叉树中度数为得结点数为N0，度数为1得结点数为N，则该二叉树中度数为2得结点数为_；若采用二叉链表作为该二叉树得存储结构,则该二叉树中共有_个空指针域。6. 设某无向图中顶点数与边数分别为n与e，所有顶点得度数之与为d，则e=_.7. 设一组初始记录关键字序列为（55，63，44,38，5,80,31,6），则利用筛选法建立得初始堆为_。8。已知一有向图得邻接表存储结构如下：从顶点1出发，DFS遍历得输出序列就是 ,BS遍历得输出序列就是 三、应用题(3分）1 设一组初始记录关键字序列为（4,0，48，0，2，78），则分别给出第4趟简单选择排序与第4趟直接插入排序后得结果。2 设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A得后面插入结点B得操作序列（设双向链表中结点得两个指针域分别为llink与lik）。3 设一组有序得记录关键字序列为(3，1，24,35，47，50，62，,90)，查找方法用二分查找,要求计算出查找关键字62时得比较次数并计算出查找成功时得平均查找长度.4 设一棵树T中边得集合为（，B），(A,C),（A,），(B，E)，(C，F)，(C，G），要求用孩子兄弟表示法(二叉链表）表示出该树得存储结构并将该树转化成对应得二叉树。5 设有无向图,要求给出用普里姆算法构造最小生成树所走过得边得集合.6 设有一组初始记录关键字为(45，48,4，22,8),要求构造一棵二叉排序树并给出构造过程。四、算法设计题(16分） 1 设有一组初始记录关键字序列（K1,K2，K），要求设计一个算法能够在O（n)得时间复杂度内将线性表划分成两部分,其中左半部分得每个关键字均小于K,右半部分得每个关键字均大于等于i。2 设有两个集合A与集合B,要求设计生成集合AB得算法，其中集合A、B与用链式存储结构表示。数据结构试卷(三）一、选择题(每题1分,共分）1。设某数据结构得二元组形式表示为A=（D，R），D0,02，03，04，05，6,0，0，09,=r,r=，01，03,01，4，02，05，0,07,3，08，0，09，则数据结构A就是（ )。（A） 线性结构（B) 树型结构(C）物理结构（D） 图型结构2下面程序得时间复杂为（ ）for(i=1,s； i=n； i+)t=；for(j；jdata=qa;next-net;ee（q）；(B） q=pnxt；-dat=p-ta；nextqext；free（)；(C） pnext；pnext=-next；fr(q）;(D） qnext;p-data=at;fe();。设有n个待排序得记录关键字，则在堆排序中需要（ ）个辅助记录单元。(A)(B) n（C) lo2n（D) 5。设一组初始关键字记录关键字为（0，5,14,18,21，40,0）,则以2为基准记录得一趟快速排序结束后得结果为(）。(） 10,5,14,8,20,3，40，(B)0，1，,8，20，40,36,21(C）10，15,4，20,1,40，36,2l（D） 1,10，14，18,2，36，40，21。设二叉排序树中有n个结点，则在二叉排序树得平均平均查找长度为( ).(A） O(1）(B) O（2n)（C)（D） O（n)设无向图中有n个顶点e条边，则其对应得邻接表中得表头结点与表结点得个数分别为（ ）。(A）n,e（B) ，n（C) 2n,e（D)n,2e8、设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。（A) n(-1）（B) +（C) n（D） n(n1)9。设有50个待排序得记录关键字，如果需要用最快得方法选出其中最小得0个记录关键字,则用下列( )方法可以达到此目得。（A) 快速排序(B) 堆排序(C) 归并排序（D） 插入排序10、下列四种排序中( ）得空间复杂度最大.（A） 插入排序（） 冒泡排序（）堆排序（） 归并排序二、填空殖(每空1分 共2分）1. 数据得物理结构主要包括_与_两种情况.2. 设一棵完全二叉树中有50个结点,则该二叉树得深度为_;若用二叉链表作为该完全二叉树得存储结构，则共有_个空指针域。3. 设输入序列为、2、3,则经过栈得作用后可以得到_种不同得输出序列。4. 设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之与等于顶点i得_,第i列上所有元素之与等于顶点i得_。5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有_个度数为1得结点。6. 设有向图G中有个顶点条有向边,所有得顶点入度数之与为d,则e与d得关系为_.7. _遍历二叉排序树中得结点可以得到一个递增得关键字序列（填先序、中序或后序）。8. 设查找表中有10个元素,如果用二分法查找方法查找数据元素X,则最多需要比较_次就可以断定数据元素X就是否在查找表中.9. 不论就是顺序存储结构得栈还就是链式存储结构得栈，其入栈与出栈操作得时间复杂度均为_。10. 设有n个结点得完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点得双亲结点编号为_，右孩子结点得编号为_。11. 设一组初始记录关键字为(72，73，1，4，6,5），则以记录关键字7为基准得一趟快速排序结果为_。12. 设有向图中有向边得集合E=1，2，,3，1,4,4，2,3，则该图得一种拓扑序列为_.13. 下列算法实现在顺序散列表中查找值为得关键字，请在下划线处填上正确得语句。rucrecordint key; othrs;；thashsqearch(strct recor hashtable ,in )int ,j； ji=k %；whil （hastaj、ky！=k&hahtabe、lg!=)=(_）%; if（i=j) retu(1）；if（_ ） rturn(j); ese rturn(1）；14. 下列算法实现在二叉排序树上查找关键值k,请在下划线处填上正确得语句。typeefstctoeint k;rucnode *lchld；tr ode rchild;bt;bite stsearc(btre*， int k) （t= ） retun（0）；ele whl (t！0）if （ke=k）_； ele if(tkyk）=lcil； s_;三、计算题（每题0分,共30分）1、已知二叉树得前序遍历序列就是AFBGCHI，中序遍历序列就是FBCHKJD，画出此二叉树,并画出它得后序线索二叉树。2。已知待散列得线性表为（36，15，0，63,2),散列用得一维地址空间为0、6,假定选用得散列函数就是H（K)= K md7，若发生冲突采用线性探查法处理，试:(1）计算出每一个元素得散列地址并在下图中填写出散列表： 0 2 4 6(2）求出在查找每一个元素概率相等情况下得平均查找长度。3。已知序列(10，18，4,3，6,12，1,9,18，8）请用快速排序写出每一趟排序得结果。四、算法设计题(每题15分，共30分)1 设计在单链表中删除值相同得多余结点得算法。2 设计一个求结点x在二叉树中得双亲结点算法。数据结构试卷（四）一、选择题(每题分共2分)1.设一维数组中有n个数组元素,则读取第i个数组元素得平均时间复杂度为（ )。(A） O（）(B） O(nog）（） O(）()（n2)2。设一棵二叉树得深度为k，则该二叉树中最多有（ )个结点。（) 2k-1(B) 2(C) 2k1(） k13.设某无向图中有n个顶点e条边，则该无向图中所有顶点得入度之与为（ )。（A） n（B） e（C） 2(D) 24。在二叉排序树中插入一个结点得时间复杂度为（ ）。（A)O(1）(） O（）(C） O（log2)(D） (2)5。设某有向图得邻接表中有个表头结点与m个表结点,则该图中有（ ）条有向边.(A） n（B） n1（C) m（） m16.设一组初始记录关键字序列为（45，25,67，94，627)，则用基数排序需要进行（)趟得分配与回收才能使得初始关键字序列变成有序序列。(A) (B）4（C) （) 7.设用链表作为栈得存储结构则退栈操作( ）.（A)必须判别栈就是否为满（) 必须判别栈就是否为空（） 判别栈元素得类型（D) 对栈不作任何判别8。下列四种排序中（ )得空间复杂度最大。（A）快速排序() 冒泡排序（C) 希尔排序（D)堆9.设某二叉树中度数为得结点数为N0，度数为得结点数为Nl,度数为2得结点数为N，则下列等式成立得就是（ ）。（) 0=N1+1(B） N=NlN2(）N0=2+1（D) N0=2N、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素得最多比较次数不超过（ ）。(A）lo2n+() log2n1（C）o2（) lo(+1）二、填空题（每空分共 20分)1 设有n个无序得记录关键字,则直接插入排序得时间复杂度为_,快速排序得平均时间复杂度为_。2 设指针变量p指向双向循环链表中得结点X,则删除结点X需要执行得语句序列为_(设结点中得两个指针域分别为llnk与rlik)。3 根据初始关键字序列(9，2，1，38,10）建立得二叉排序树得高度为_。4 深度为k得完全二叉树中最少有_个结点.5 设初始记录关键字序列为（K1,K2，,Kn),则用筛选法思想建堆必须从第_个元素开始进行筛选.6 设哈夫曼树中共有99个结点，则该树中有_个叶子结点；若采用二叉链表作为存储结构,则该树中有_个空指针域。7 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_个队列元素；当前实际存储_个队列元素(设头指针指向当前队头元素得前一个位置，尾指针指向当前队尾元素得位置）。8 设顺序线性表中有n个数据元素,则第个位置上插入一个数据元素需要移动表中_个数据元素；删除第i个位置上得数据元素需要移动表中_个元素。9 设一组初始记录关键字序列为(20,18,22，,3，1）,则以0为中轴得一趟快速排序结果为_。10 设一组初始记录关键字序列为（20,18,22，16,0，9)，则根据这些初始关键字序列建成得初始堆为_.11 设某无向图G中有n个顶点，用邻接矩阵A作为该图得存储结构，则顶点i与顶点j互为邻接点得条件就是_。12 设无向图对应得邻接矩阵为A，则A中第上非元素得个数_第列上非元素得个数(填等于，大于或小于）。13 设前序遍历某二叉树得序列为ABCD,中序遍历该二叉树得序列为C，则后序遍历该二叉树得序列为_。14 设散列函数H(k)= mod p,解决冲突得方法为链地址法。要求在下列算法划线处填上正确得语句完成在散列表hashtalb中查找关键字值等于得结点,成功时返回指向关键字得指针,不成功时返回标志0。yestuct nodn key;strct nodnet;lklst； oid cratelkhash（llit hashtable ）nt ，k; lkls ;for(i=0;i；i+）_；for(i=；inext=head（D） ad！04.时间复杂度不受数据初始状态影响而恒为O（nlo2n)得就是（ )。（A） 堆排序（B） 冒泡排序(） 希尔排序（D） 快速排序5设二叉树得先序遍历序列与后序遍历序列正好相反,则该二叉树满足得条件就是( )。（A） 空或只有一个结点（B）高度等于其结点数（) 任一结点无左孩子（D) 任一结点无右孩子6。一趟排序结束后不一定能够选出一个元素放在其最终位置上得就是（ ）。(A)堆排序（B) 冒泡排序（C) 快速排序(D) 希尔排序设某棵三叉树中有40个结点,则该三叉树得最小高度