数据构造模拟卷(含答案)经典习题培训讲学.docx
数据构造模拟卷(含答案)经典习题培训讲学当前位置：文档视界数据构造模拟卷(含答案)经典习题培训讲学数据构造模拟卷(含答案)经典习题培训讲学练习题一、单项选择题1.若将数据构造形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上()A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合2.在长度为n的顺序表中删除第i个元素(1in)时，元素移动的次数为()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，46.字符串通常采用的两种存储方式是()A.散列存储和索引存储B.索引存储和链式存储C.顺序存储和链式存储D.散列存储和顺序存储7.数据构造是A一种数据类型B数据的存储构造C一组性质一样的数据元素的集合D互相之间存在一种或多种特定关系的数据元素的集合8.算法分析的目的是A辨别数据构造的合理性B评价算法的效率C研究算法中输入与输出的关系D鉴别算法的可读性9.在线性表的下列运算中，不改变数据元素之间构造关系的运算是A插入B删除C排序D定位10.下列图示的顺序存储构造表示的二叉树是()11.设串sl=DataStructureswithJava,s2=it，则子串定位函数index(s1,s2)的值为(A15B16C17D1812.二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087，A47的存储地址为1153，则数组元素A67的存储地址为A1213B1209C1211D120713.在按中序遍历二叉树的算法中，需要借助的辅助数据构造是A队列B栈C线性表D有序表14.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系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的经过中，先后进行比拟的关键字依次为Af,c,bBf,d,bCg,c,bDg,d,b19.下面程序段的时间复杂度为()s=0；for(i=1；inext=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个结点的二叉树时，值为空的指针域的个数为()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.nC.n+lD.n+230.若有序表的关键字序列为b,c,d,e,f,g,q,r,s,t，则在二分查找关键字b的经过中，先后进行比拟的关键字依次为Af,c,bBf,d,bCg,c,bDg,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的_。7.假设以数组seqnm存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。写出一般情况下队头元素位置的表达式。假如用变量front和quelen分别指示循环队列中队头元素的位置和元素的个数，则写出一般情况下队尾元素位置的表达式。8.已知二叉树如下，写出它的先序序列、中序序列和后序序列9.称算法的时间复杂度为O(f(n)，其含义是指算法的执行时间和_的数量级一样。10.在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_，删除*p结点的时间复杂度为_。11.假设为循环队列分配的向量空间为Q20，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为_。12.一棵含999个结点的完全二叉树的深度为_,深度为10的满二叉树有_个结点。13.含n个顶点的无向连通图中至少含有_条边。14.已知有向图G的定义如下：G=(V，E)V=a，b，c，d，eE=，(1)画出G的图形；(2)写出G的全部拓扑序列。15.线性表的链接存储比顺序存储的优点是：_操作不需移动结点。16.孩子兄弟链表表示的树构造，其后根遍历结果同二叉树的_.一致。17.哈夫曼树又称_.其定义是_18队列是一种_线性表，而栈是_线性表。19.画出与如下图森林对应的二叉树。20.下列线索化的树称为_，画出中序线素二叉树的线索表示。21.填写语句完成对顺序表的初始化#defineLIST_INIT_SIZE100typedefstructElemType*elem;/存储空间起始地址intlength;/线性表长度intlistSize;/分配容量SqList;StatusinitList_Sq(SqList&l)l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!l.elem)exitERROR;_;_;returnOK;
