数据结构试题样题及答案

数据结构试题样题及答案一、单项选择题（每小题2分，共30分）1.数据结构中，与所使用的计算机无关的是数据的（）结构。A.逻辑B.物理C.存储D.逻辑与物理2.下述各类表中可以随机访问的是（）。A.单向链表B.双向链表C.单向循环链表D.顺序表3.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（）。A.21B.20C.19D.254.元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（）。A.642B.624C.426D.2645.一个队列的入队序列是5，6，7，8，则队列的输出序列是（）。A.5678B.8765C.7865D.可能有多种情况6.串函数StrCmp（“d”，“D”）的值为（）。A．0B．1C．-1D．37．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。A．p=qnextB．pnext=qC．pnext=qnextD．qnext=NULL8.设一棵哈夫曼树共有n个非叶结点，则该树一共有（）个结点。A.2*n-1B.2*n+1C.2*nD.2*(n-1)9.对如图1所示二叉树进行中序遍历，结果是（）。A.dfebagcB.defbagcC.defbacgD.dbaefcgabccdgfe图110.任何一个无向连通图的最小生成树（）。A.至少有一棵B.只有一棵C.一定有多棵D.可能不存在11．设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（）。A．33B．32C．85D．41.一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A．31，29，37，85，47，70B．29，31，37，47，70，851C．31，29，37，70，47，85D．31，29，37，47，70，8513.对n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就结束排序过程。对某n个元素的排序共进行了3n-6次元素间的比较就完成了排序，则（）。原序列是升序排列原序列是降序排列对序列只进行了2趟冒泡对序列只进行了3趟冒泡14．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行（）。A.x=top->data;top=top->next;B.top=top->next;x=top;C.x=top;top=top->next;D.x=top->data;15．串函数StrCat（a,b）的功能是进行串（）。A．比较B．复制C．赋值D．连接二、填空题（每小题2分，共24分）1．在一个单向链表中p所指结点之后插入一个s所指的新结点，应执行s->next=p->next；和______操作。2．根据数据元素间关系的不同特性，通常可分为________、、、四类基本结构。3．在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为________。(结点的指针域为next)4.________遍历二叉排序树可得到一个有序序列。5.一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_______个叶结点。6.如图1所示的二叉树，其中序遍历序列为_________。abcdefhgi图1对稀疏矩阵进行压缩存储，矩阵中每个非零元素所对应的三元组包括该元素的________、________和________三项信息。8.有一个有序表{2,3,9,13,33,42,45,63,74,77,82,95,110},用折半查找法查找值为82的结点，经________次比较后查找成功。9.图的深度优先搜索和广度优先搜索序列不是唯一的。此断言是______的。(回答正确2或不正确)10．哈希法既是一种存储方法，又是一种。11．44.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_________次。12．栈和队列的操作特点分别是________和________。三、综合题（每小题10分，共30分）1．已知序列{11，19，5，4，7，13，2，10}，1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程）。2．设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1,2,,12.（1）说出有哪几个元素需要经过3次元素间的比较才能成功查到2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）3）设查找元素5，需要进行多少次元素间的比较才能确定不能查到.3．(1)设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据，构造一棵二叉排序树.（2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.四、程序填空题（每空2分，共16分）1．以下冒泡法程序对存放在a[1]，a[2]，，a[n]中的序列进行冒泡排序，完成程序中的空格部分，其中n是元素个数，程序按升序排列。Voidbsort(NODEa[],int){NODEtemp;inti,j,flag;for(j=1;（1）;j++);{flag=0;for(i=1;（2）;i++)if(a[i].key>a[i+1].key){flag=1;temp=a[i];（3）;（4）;}if(flag==0)break;}}程序中flag的功能是（5）7．以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域为data，其数据类型为字符型，BT指向根结点）。3VoidPostorder(structBTreeNode*BT){if(BT!=NULL){（1）;（2）;（3）;}}试题答案；一、单项选择题（每小题2分，共30分）1．A2．D3．B4．B5．A6．C7．C8．B9．A10．A11．A12．D13．D14．A15．D二、填空题（每小题2分，共24分）1.p->next=s;集合、线性、树形、图状f=f->next;中序5.ndgbaechhif行号、列号、元素值8.4次正确10．查找方法11．3次12．先进后出先进先出三、综合题（每小题10分，共30分）1．(1)初始11，19，5，4，7，13，2，10第一趟[11，19][4，5][7，13][2，10]第二趟[4，5，11，19][2，7，10，，13]第三趟[2，4，5，7，10，11，13，19](2)111119219547135471321010411242411197135197131510102．(1)13,36,63,135(2)639147112581012(3)3次3．(1)5214461837165(2)中序遍历中序2，3，4，5，6，7，14，16，18四、程序填空题（每空2分，共16分）1．1）j<=n-12）i<=n-j3）a[i]=a[i+1]4）a[i+1]=temp5）当某趟冒泡中没有出现交换则已排好序，结束循环2．（1）Postorder(BTleft)（2）Postorder(BTright)（3）printf(“%c”,BTdata)6