数据结构模拟卷(含答案)经典习题

1练习题一、单项选择题1.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上()A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合2.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为()A.n-i+1B.iC.i+1D.n-i3.若不带头结点的单链表的指针为head，则该链表为空的判定条件是()A.head==NULLB.head-next==NULLC.head!=NULLD.head-next==head4.引起循环队列队头位置发生变化的操作是()A.出队B.入队C.取队头元素D.取队尾元素5.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是()A.2，4，3，1，5，6B.3，2，4，1，6，5C.4，3，2，1，5，6D.2，3，5，1，6，426.字符串通常采用的两种存储方式是()A.散列存储和索引存储B.索引存储和链式存储C.顺序存储和链式存储D.散列存储和顺序存储7.数据结构是（）A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合8.算法分析的目的是（）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性9.在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（）A．插入B．删除C．排序D．定位10.下列图示的顺序存储结构表示的二叉树是()311.设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为(）A．15B．16C．17D．1812.二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（）A．1213B．1209C．1211D．120713.在按中序遍历二叉树的算法中，需要借助的辅助数据结构是（）A．队列B．栈C．线性表D．有序表414.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）A．不一定相同B．都相同C．都不相同D．互为逆序15.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法16.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（）A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目17.图的邻接矩阵表示法适用于表示（）A．无向图B．有向图C．稠密图D．稀疏图18.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）A．f,c,bB．f,d,bC．g,c,bD．g,d,b19.下面程序段的时间复杂度为()s=0；5for(i=1；in；i++)for(j=1；ji；j++)s+=i*j；A.O(1)B.O(logn)C.O(n)D.O(n2)20.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为()A.q-next=s-next；s-next=p；B.s-next=p；q-next=s-next；C.p-next=s-next；s-next=q；D.s-next=q；p-next=s-next；21.在计算机内实现递归算法时所需的辅助数据结构是()A.栈B.队列C.树D.图22.通常将链串的结点大小设置为大于1是为了()A.提高串匹配效率B.提高存储密度C.便于插入操作D.便于删除操作23.带行逻辑的三元组表是稀疏矩阵的一种()A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构24.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个6数为()A.n-1B.nC.n+lD.2n25.为便于判别有向图中是否存在回路，可借助于()A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法26.连通网的最小生成树是其所有生成树中()A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树27.按排序过程中依据的原则分类，快速排序属于()A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法28.在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为()A.4B.5C.6D.729.假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为()A.n-1B.n7C.n+lD.n+230.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）A．f,c,bB．f,d,bC．g,c,bD．g,d,b二、填空题1.数据的逻辑结构在计算机存储器内的表示，称为数据的____________。2.已知双向循环链表结点中，域prior指向前一结点，域next指向后一结点，则删除当前结点指针p的前驱结点(存在)应执行的语句是____________。3.栈下溢是指在____________时进行出栈操作，栈上溢是指在____________时进行入栈操作。4.已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=”ABCDEFGHIJK″,t=”ABCD″,执行运算substr(s,strlen(t),strlen(t))后的返回值为____________。5.已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点6.在有向图中，以顶点v为终点的弧的数目称为v的____________,以顶点v为源点的弧的数目称为v的_____________。87.假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。写出一般情况下队头元素位置的表达式。如果用变量front和quelen分别指示循环队列中队头元素的位置和元素的个数，则写出一般情况下队尾元素位置的表达式。8.已知二叉树如下，写出它的先序序列、中序序列和后序序列9.称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和_______的数量级相同。10.在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_________，删除*p结点的时间复杂度为_____________。11.假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为______。12.一棵含999个结点的完全二叉树的深度为_______,深度为10的满二叉树有________个结点。13.含n个顶点的无向连通图中至少含有______条边。BFGDCEA914..已知有向图G的定义如下：G=(V，E)V={a，b，c，d，e}E={a，b，a，c，b，c，b，d，c，d，e，c，e，d}(1)画出G的图形；(2)写出G的全部拓扑序列。15.线性表的链接存储比顺序存储的优点是：________________操作不需移动结点。16.孩子兄弟链表表示的树结构，其后根遍历结果同二叉树的___________.一致。17.哈夫曼树又称__________.其定义是______________________18队列是一种__________线性表，而栈是____________线性表。19.画出与如图所示森林对应的二叉树。20.下列线索化的树称为___________________，画出中序线素二叉树的线索表示。1021.填写语句完成对顺序表的初始化#defineLIST_INIT_SIZE100typedefstruct{ElemType*elem;//存储空间起始地址intlength;//线性表长度intlistSize;//分配容量}SqList;StatusinitList_Sq(SqList&l){l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!l.elem)exitERROR;__________________________;__________________________;returnOK;}22.一般而言，若二叉树的结点，其左子树的所有结点小于根结点，BACDEFGH11而右子树的所有结点大于根结点，则二叉树称为________________;如果结点的左子树深度和右子树深度之差的绝对值不超过1，则二叉树称为________________.三、解答题1.已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。（1）画出该二叉树；（2）画出与（1）求得的二叉树对应的森林。2.从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。（1）画出该二叉排序树；（2）画出从（1）所得树中删除关键字为37的结点之后的二叉排序树。3.已知用有序链表存储整数集合的元素。阅读算法f3，并回答下列问题：（1）写出执行f3（a,b）的返回值，其中a和b分别为指向存储集合{2，4，5，7，9，12}和{2，4，5，7，9,12}的链表的头指针；（2）简述算法f3的功能；（3）写出算法f3的时间复杂度。intf3(LinkListha,LinkListhb){12//LinkList是带有头结点的单链表//ha和hb分别为指向存储两个有序整数集合的链表的头指针LinkListpa,pb;pa=ha-next;pb=hb-next;while(pa&&pb&&pa-data==pb-data){pa=pa-next;pb=pb-next;}if(pa==NULL&&pb==NULL)return1;elsereturn0;}4.已知稀疏矩阵采用三元组表表示，其形式说明如下：#defineMaxSize100//稀疏矩阵的最大行数typedefstruct{inti,j,v;//行号、列号、元素值}TriTupleNode;typedefstruct{TriTupleNodedata[MaxSize];intm,n,t;//矩阵的行数、列数和非零元个数}RTriTupleTable;13下列算法f4的功能是，以行优先的顺序输入稀疏矩阵的非零元（行号、列号、元素值），建立稀疏矩阵的三元组表存储结构。请在空缺处填入合适内容，使其成为一个完整的算法。（注：矩阵的行、列下标均从1起计）voidf4(RTriTupleTable&R){inti,k;scanf(″%d%d%d″,&R-m,&R-n,&R-t);k=1;//k指示当前输入的非零元的行号for(i=0;①；i++){scanf(″%d%d%d″,②，③，_________④_____________;}}5.已知二叉树的存储结构为二叉链表，其类型定义如下：typedefstructNodeType{DataTypedata;structNodeType*lchild,*rchild;}BinTNode,*BinTree;阅读算法f5，并回答下列问题：(1)对于如图所示的二叉树，画出执行算法f5的结果；14（2）简述算法f5的功能。BinTreef5(BinTreebt1){BinTreebt2;if(bt1==NULL)bt2=NULL;else{bt2=(BinTNode*)malloc(sizeof(BinTNode));bt2-data