数据结构试题(含答案)3

《数据结构》试题(一)一、选择题(每小题1分，共20分)1．以下数据结构中，A是线性结构。A）队B）树C二叉树D）图2．5个顶点的无向图最多有B条边。A、5B、10C、20D、253．下面C是顺序存储结构的优点。A）存储密度大B）插入运算方便C查找方便D）适合各种逻辑结构的存储表示4．下面关于串的叙述中，B是不正确的。A）串是字符的有限序列B）空串是由空格构成的串C）模式匹配是串的一种重要运算D）串既可以采用顺序存储，也可以采用链式存储5．B的邻接矩阵是对称矩阵。A）有向图B）无向图C）AOV网D）AOE网6．用链式方式存储的队列，在进行删除运算时，D#A。A）仅修改头指针B）仅修改尾指针C）头、尾指针都要修改D）头、尾指针可能都要修改7．二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是C。先序序列：EFHIGJK中序序列：HFIEJKGA）EB）FC）GD）H8．下面B#A方法可以判断出一个有向图中是否有环。A）深度优先遍历B）拓朴排序C）求最短路径D）求关键路径9．若在线性表中采用折半查找法查找元素，该线性表应该C。A）元素按值有序B）采用顺序存储结构C）元素按值有序，且采用顺序存储结构D）元素按值有序，且采用链式存储结构10．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为A排序法。A）插入B）选择C）冒泡D）都不是11．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移A#C个元素。A、n-iB、n-i-1C、n-i+1D、i12．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是*#C。A、edcbaB、decbaC、dceabD、abcde13．从邻接矩阵010101010A可以看出，该图共有C#B顶点。A、9B、3C、6D、114．上题中，若是有向图，则有B条弧。A、5B、4C、3D、215．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是D。A、inB、2*i=nC、2*i+1nD、2*in16．向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动B个元素。A、64.5B、64C、63D、6517．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行D。A、q-next=p-next;p-next=q;B、p-next=q-next;q=p;C、p-next=p-next;q-next=q;D、p-next=q-next;q-nxet=p;18．对一个满二叉树，m个树叶，n个结点，深度为h，则有#D。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-119．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为A#D。A、front==rearB、front!=NULLC、rear!=NULLD、front==NULL20．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是A。A、选择排序B、冒泡排序C、插入排序D、希尔排序二、判断题：（每小题2分，共10分）（）1.栈和队列都是非线性数据结构。（）2.完全二叉树可以用顺序存储结构进行存储。（）3.数据元素是数据的最小单位。(基本单位)（）4.含尾指针的单链循环表可以被用于队列操作。（）5.数据结构包含数据的逻辑结构、数据的存储结构以及数据集合上定义的运算。三、填空题（每空2分，共10分）1、在线性表的单链表存储结构中，每个结点包含两个域，一个叫数据（值）域，另一个叫指针域。2、设字符串S1=‘ABCDEFG’，S2=‘PQRST’，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为BCDEFEF。3、队列的插入操作在队尾进行，栈的删除操作在栈顶进行。四、回答下列问题（每小题8分，共40分）1．分别给出对下图进行深度优先和广度优先遍历的结果。1．深度：125963784（不唯一）广度：123456789（不唯一）2．已知序列（12，4，17，10，7，30），用直接选择排序法对其进行递增排序，写出每一趟的排序结果。2．第1趟：4121710730第2趟：4717101230第3趟：4710171230第4趟：4710121730第5趟：47101217303．一批数据有如下的逻辑结构B=(K,R),其中K={kkkk1239,,,,},R={r},r={kkkkkkkkkkkkkkkk1213141718454689,,,,,,,,,,,,,,,},试用图示法表示其逻辑结构。4．已知一棵非空二叉树，其按中序和后序遍历的结果分别为：中序：CGBAHEDJFI后序：GBCHEJIFDA254136897254136897请画出这棵二叉树，并写出其前序遍历的结果。前序遍历结果:ACBGDEHFJI5．已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。c1:10c2:1111c3:01c4:1110c5:110c6:00五、编写算法（每小题10分，共20分）要求:1、说明算法中使用的主要数据结构、变量；2、用C可1．设有一个由正整数组成的无序无头结点的单链表，编写子程序(或函数)找到其最小值。2．冒泡排序。1．strucnode{intd;structnode*next;}intminn(node*p){intx=0;while(p){if(p-dx){x=p-d;}p=p-next;}RETURN(x);}2．intn;intp[n];voidsort(intp[],n){inti,j,t,k;for(i=0;in-1&&k;i++){k=1;for(j=0;j=n-i-1;j++;){if(p[j]p[j+1]){t=p[j];p[j]=p[j+1];p[j+1]=t;k=0;}}}}