搜索
数据结构综合练习题要求：个人要独立认真思考，不懂问同学或指导教师一、单选题C．rear=(rear+1)modmD．rear=(rear+1)mod(m+1)7.字符串’ababaabab’的next函数为（）A.011232232B.012341234C.011122334D.0112342348.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（）A．9B．11C．15D．不确定9.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（）。A．BA+141B．BA+180C．BA+222D．BA+22510.n个顶点的带权无向连通图的最小生成树包含()个顶点A．n-1B．nC．n/2D．n+111．有关二叉树的下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为212．关键路径是AOE网中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径）13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（）。A．(n-1)/2B．n/2C．(n+1)/2D．n14．就平均性能而言，目前最好的内部排序方法是（）A．冒泡排序B．希尔排序C．堆排序D．快速排序15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（）A．head(tail(LS))B．tail(head(LS)C．head(tail(head(tail(LS))))D．head(tail(tail(head(LS))))1.计算机算法指的是（）。A．程序B．问题求解步骤的描述C．调度方法D．排序方法2.以下数据结构中，（）个是非线性数据结构。A．树B．字符串C．队D．栈3.对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（）。A．O(n)O(n)B．O(n)O(1)C．O(1)O(n)D．O(1)O(1)4.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）。A.p-next=s;s-next=p-nextB.s-next=p-next;p-next=sC.p-next=s;p-next=s-nextD.p-next=s-next;p-next=s5.n个顶点的有向图中,含有向边的数目最多为()A．n-1B．nC．n(n-1)/2D．n(n-1)6.循环队列存储在数组A[0..m]中，则入队时的操作为（）A．rear=rear+1B．rear=(rear+1)mod(m-1)C．head(tail(head(tail(LS))))D．head(tail(tail(head(LS))))17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：()A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B.在第i个结点后插入一个新结点（1≤i≤n）C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序18．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;19.设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，E.3，2，1，4，20.循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)21.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2，p3，…，pn，若p1=n，则pi为()A．iB．n=iC．n-i+1D．不确定22．串‘ababaaababaa’的next的函数值为（）。A．012345678999B．012121111212C．011234223456D．012301232234523．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定24．高度为k的二叉树最大的结点数为（）。A．2kB．2k-1C．2k-1D．2k-1-125．边远山区的N个小村庄，现要为他们建成能互相通信的网，并且总的花费最少，这可以归结为什么问题（）A最短路径B关键路径C拓扑排序D最小生成树26．当一个有n个顶点的无向图用邻接矩阵A表示时，顶点Vi的度是（）。A．nijiA1],[B．n1jj,iAC．niijA1],[D．nijiA1],[+n1ji,jA30．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A．(40,38,46,56,79,84)B.(40,38,46,79,56,84)C．(38,40,46,56,79,84)D.(40,38,46,84,56,79)31．在双向链表指针p的结点前插入一个指针q的结点操作是（）。A.p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;33.在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，主机将要打印的数据依次写入缓冲区，而打印机则依次驱除数据打印，该缓冲区该是一个什么结构（）A堆栈B图C树D队列35．串的长度是指（）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数36．具有10个叶子结点的二叉树中有（）个度为2的结点。A．8B．9C．10D．ll37.有关二叉树下列说法正确的是（）。A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为238．一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlog2n39．下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间。B．任何一个关键活动提前完成，那么整个工程将会提前完成。C．所有的关键活动提前完成，那么整个工程将会提前完成。D．某些关键活动提前完成，那么整个工程将会提前完成。40.已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head(tail((tail(tail(L））））)41．适用于折半查找的表的存储方式及元素排列要求为()A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序42.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A．(n-1)/2B.n/2C.(n+1)/2D.n43．下列四个序列中，哪一个是堆（）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1544．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。A．acbedB．decabC．deabcD．cedba二、填空题1.带头结点的单循环链表L中只有一个元素结点的条件是。2.串中所含字符个数称为该串的_______________。3.深度为h的完全二叉树至少有个结点，至多有个结点。4.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为。5．完全二叉树中，结点个数为n，则编号最大的非终端结点的编号为______。7.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。8．在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本无序，则最好选用。9.在n个结点的单链表中要删除已知结点*p，需找到它的，其时间复杂度为。10．模式串P=‘abaabcac’的next函数值序列为________。11．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为:。12．对有18个元素的有序表A[1，18]做折半查找，则查找A[3]的比较序列的下标依次为_____。三、判断题：对打“√”；错打“×”，并说明理由。1.数据元素是数据的最小单位。()2.顺序存储结构的主要缺点是不利于插入或删除操作。()3.线性表的长度是线性表所占用的存储空间的大小。()4.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）5.完全二叉树中，若一个结点没有左孩子，则它必是树叶。()6.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。()7.折半查找与二叉排序树的时间性能有时不相同。（）8.十字链表是无向图的一种存储结构，而邻接多重表是有向图的一种存储结构。（）9.在用堆排序算法排序时，如果要使排序后的记录序列按关键字非递减有序排列，则需要采用“大根堆”。（）10.强连通分量是无向图的极大强连通子图。（）11.散列表的装填因子α越小，发生冲突的可能性就越小。（）三．算法设计题1、假设以带头结点的单循环链表表示队列，其中结点结构为（data，next），并且只设一个指针rear指向队尾结点，但不设头指针，请写出相应的入队：EnQueue(LinkList&rear,ElemTypex)和出队DeQueue(LinkList&rear,ElemType&x)算法。2．是利用栈和队列实现对一个字符串的逆置。3．已知Q是一个非空队列，S是一个空栈。仅用如下给定的队列和栈的ADT函数和尽量少的工作变量，使用C或C++语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有：voidMakeEmpty(Stack&S)置空栈boolPush(Stack&S,DataTypee)新元素e进栈，入栈成功返回TRUE，否则返回FALSEDataTypePop(Stack&S)出栈，返回栈顶值,否则返回空值boolisSEmpty(StackS)判栈空否,若空返回TRUE，否则返回FALSE队列的ADT函数有：boolEnQueue(Queue&Q,DataTypee)元素e进队，入队成功返回TRUE，否则返回FALSEDataTypeDeQueue(Queue&Q)出队列，若队列非空返回队头值,否则返回空值boolisQEmpty(QueueQ).判队列空否。若空返回TRUE，否则返回FALSE4．下面的算法在中序线索二叉树中求结点p的中序后继，试补充完整（线索树的结点有五个域data,lchild,rchild,左、右标志域ltag、rtag，并规定标志0指向孩子