数据结构卷一

黄河科技学院期末考试《数据结构》课程试题（A卷）一、单选题（每小题1分，共20分）1．串是任意有限个（B）。A.符号构成的序列B.字符构成的序列C.符号构成的集合D.字符构成的集合2．对于键值序列{20，73，71，23，74，16，05，68，76，103}用筛选法建堆，开始结点的键值是（B）。A.103B.74C.20D.233．若在线性表中采用二分法查找元素，该线性表应该（B）。A.元素按值有序B.元素按值有序，且采用顺序存储结构C.采用顺序存储结构D.元素按值有序，且采用链式存储结构4．一个具有n个顶点的有向图，若采用邻接矩阵表示，则该邻接矩阵中第i行非零元素的个数是Vi的（B）。A.入度B.出度C.度D.路径长度5．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行的操作是（B）。A.p-〉next=s;s-〉next=pB.s-〉next=p-〉next;p-〉next=sC.s-〉next=p;p-〉next=sD.s-〉next=p-〉next;p=s6．在双链表中删除指针P所指结点的后继结点，最多需修改的指针域的个数为（A）。A.4B.2C.1D.67．若一棵二叉树具有20个度为2的结点，则该二叉树的叶子结点个数是（C）。A.20B.10C.21D.不确定8．假设h（key），h1（key）是不同的散列函数，散列表冲突的条件是（A）。A.keyi≠keyj，h（keyi）=h（keyj）B.keyi≠keyj，h（keyi）=h1（keyj）C.h（keyi）=h（keyj）D.h1（keyi）=h（keyj）9．在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（C）。A.4B.5C.6D.710．串的长度是（C）。A.串中不同字母的个数B.串中不同字符的个数C.串中所含字符的个数D.串中所含字母的个数11．处理冲突的两类主要方法是（D）。A．线性探查法和基数转换法B.除余法和折叠法C.建溢出区法和不建溢出区法D.拉链法和开地址法12．链栈与顺序栈相比，有一个较明显的优点是（A）。A.通常不会出现栈满的情况B.通常不会出现栈空的情况C.插入操作更加方便D.删除操作更加方便13．具有20个顶点的有向完全图的边数是（C）。A.19B.190C.380即：n*(n-1)D.10014．平衡二叉排序树的平衡因子为（A）。A.0，-1，1绝对值=1B.0，1，2C.1，2，-1D．2，4，315．一个队列的入队序列是A，B，C，D，则队列的输出序列是（B）。A.D，C，B，AB.A，B，C，DC.A，D，C，BD.C，B，D，A16．循环单链表head的尾指针p满足（C）。A.p-next=NULLB.p==NULLC.p-next==headD.p==head17．如果以链表作为栈的存储结构，则入栈操作时（C）。A.必须判别栈是否满B.对栈不作任何判定C.必须判别栈是否空D.判别栈元素的类型18.计算机算法必须具备的三个特性（B）。A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性19．从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构20．下面的程序段的时间复杂度为（B）。for（i=1；i=n；i++）for（j=1；j=n；j++）y=y+1；A．O(2n)B．O(n2)C．O(n)D．O(log2n)二、判断题（每小题1分，共10分）1．线性表的链接存储结构优于顺序存储结构。（X）2.栈和队列都是线性表，只是操作受到了一些限制。(V)3.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。(V)4．哈夫曼树是带权外部路径长度最短的二叉树，路径上权值较大的结点离根较近。（V）5.连通图一定是无向完全图。（X）6．二叉树有五种基本形态。（V）7．冒泡排序算法是稳定的。（V）8．数据项是构成数据的基本单位。（X）9．构建散列表时，冲突是可以避免的。（X）10．利用有向无环图的邻接表构建拓扑排序时，需借助栈。（V）三、综合分析题（每小题10分，共60分）1．已知序列{10，18，4，3，6，12，20，9，15，1}，请采用冒泡排序法对该序列进行升序排序，画出具体过程。2．设有一组关键字序列：{29，12，23，22，13，20，18，30}，采用散列函数H（key）=keyMOD10，采用线性探查法解决碰撞，试在0～9的散列地址空间中对该关键字序列构造散列表，并求出在等概率的情况下，此散列表的成功的平均查找长度ASLsucc。3．已知无向图如图所示，（1）画出图的邻接表。（2）从A开始，给出一棵广度优先生成树。ABCDEF4．对于有向无环图：（1）叙述求拓扑排序的思想；aecgbdf1.叙述求拓扑排序的思想；(5分)在有向无环图中，选取一个入度为零的结点输出之，然后从图中删除该结点以及与其相邻接的弧，反复如此操作，直到所有结点都输出。（2）对于右图，写出它的四个不同的拓扑排序序列。2.abcedgf;abcgedfbacedgf;bacgedf5.已知一棵树如图所示,请将该树转化为二叉树。（孩子兄弟表示法）ABCDHGFEKJI6．已知一表为{13，25，12，6，33，15，35}，按表中顺序依次插入初始为空的二叉排序树，要求画出建立的二叉排序树。四、程序题（每小题10分，共10分）下面是对由n个记录组成的文件进行直接插入排序的算法,请补充完整.Typedefstructrecord{intkey;…};Voidstraitsort(R[n]){Structrecordrec;IntI,j;for(i=1;i=;i++){j=i-1;While(j=0){if(rec.keyR[j].key){;;};}}}}一、单选题（每小题1分，共20分）01-05．BBBBB06-10．ACACC11-15.DACAB16-20．CCBCB二、判断题（每小题1分，共10分）1-5.XVVVX6-10.VVXXV三、综合分析题（每小题10分，共60分）1．1)10，4，3，6，12，18，9，15，1，|202分2)4，3，6，10，12，9，15，1，|18，201分3)3，4，6，10，9，12，1，|15，18，201分4)3，4，6，9，10，1，|12，15，18，201分5)3，4，6，9，1，|10，12，15，18，201分6)3，4，6，1，|9，10，12，15，18，201分7)3，4，1，|6，9，10，12，15，18，201分8)3，1，|4，6，9，10，12，15，18，201分9)1，|3，4，6，9，10，12，15，18，201分2030122322131829ABCDEF2．h(29)=29MOD10=9h(12)=12MOD10=2h(23)=23MOD10=3h(22)=22MOD10=2h(13)=13MOD10=3h(20)=20MOD10=0h(18)=18MOD10=8h(30)=30MOD10=03分地址0123456789成功查找次数121133114分ASLsucc=(1+2+1+1+3+3+1+1)/8=13/83分3．已知无向图如图所示，（1）画出图的邻接表。234Λ135Λ12456Λ136Λ236Λ345Λ123456(5分)（2）从A开始，给出一棵广度优先生成树。(5分)ABCDEF4．对于有向无环图：（1）叙述求拓扑排序的思想；(5分)在有向无环图中，选取一个入度为零aecgbdf的结点输出之，然后从图中删除该结点以及与其相邻接的弧，反复如此操作，直到所有结点都输出。（2）对于右图，写出它的四个不同的拓扑排序序列。(5分,错一个扣2分)abcedgf;abcgedfbacedgf;bacgedfABCDHGFEKJI5.已知一棵树如图所示,请将该树转化为二叉树。1)连接兄弟(4分)2）擦除父母到子女的连线，只留下最左边父子的连线(3分)ABCDHGFEKJIABcccccDHGFEKJI3）旋转，即得结果(3分)6．1）Ф1分132）2分13253）2分1325124)1分13251265）1分1325126336)1分132512633157）1分13251263315358)1分四、程序题（每小题10分，共10分）下面是对由n个记录组成的文件进行直接插入排序的算法,请补充完整.Typedefstructrecord{intkey;…};Voidstraitsort(R[n]){Structrecordrec;IntI,j;for(i=1;i=n-1;i++)2分{rec=R[i]2分j=i-1;While(j=0){if(rec.keyR[j].key){R[j+1]=R[j];2分j--;2分}R[j+1]=rec;}}}}2分