《数据结构》模拟试卷三

数据结构模拟试卷(一)及参考答案一．单项选择题（本大题共15小题，每小题2分，共30分）1．如果只想得到1024个元素组成的序列中的前5个最小元素，那么用( A )方法最快。

A、起泡排序B、快速排序C、堆排序D、直接选择排序2．算法分析的目的是（B）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（C）A．插入B．删除C．定位D．排序4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（D）A．3，2，6，1，4，5 B．5，6，4，2，3，1C．1，2，5，3，4，6 D．3，4，2，1，6，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（A）A．15 B．16 C．17 D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（B）。

A. 108B. 112C. 116D. 1207．从一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（C）个结点。

A. nB. n/2C. (n+1)/2D. (n-1)/28．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（D）A．不一定相同 B．互为逆序C．都不相同D．都相同9．高度为5的二叉树至多有结点数为（A）A. 63B. 32C. 24D.6410．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（B）A．图中每个顶点的出度B．图中每个顶点的入度C．图中弧的条数D．图中连通分量的数目11．图的邻接矩阵表示法适用于表示（C）A．无向图B．有向图C．稠密图D．稀疏图12．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则执行（D）。

数据结构模拟试题（4）一、填空题:06分，每题02分1、模板类是一种数据抽象，它把________当作参数，可以实现类的复用。

2、假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为______个。

3、第i(i=1,2,...,n-1) 趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做__________排序。

二、单选题:10分，每题02分4、设循环队列的结构是const int MaxSize=100;typedef int DataT ype;struct Queue {DataT ype data[MaxSize];int front, rear;};若有一个Queue类型的队列Q，试问判断队列满的条件应为( )。

A: Q.front==Q.rear;B: Q.front-Q.rear==MaxSize;C: Q.front+Q.rear==MaxSize;D: Q.front==(Q.rear+1) % MaxSize;5、已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f))，则该二叉树的高度为( )。

假定树根结点的高度为0。

A: 3B: 4C: 5D: 66、对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值向上取整。

A: log2(n+1)B: log2nC: n/2D: (n+1)/27、设无向图的顶点个数为n，则该图最多有（）条边。

A: n-1B: n(n-1)/2C: n(n+1)/2D: n(n-1)8、在采用开散列法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的（）值相同A: 关键码B: 非关键码C: 散列函数D: 某个域三、判断题:10分，每题01分9、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。

数据结构模拟试题3 参考答案一、填空题1.设计良好的程序结构;函数名及变量名的命名规范化;使用合理的注释2.O（log10N）3.只存储非零元素（三元组表，十字链表）4.(rear+m-qulen+2) mod (m+1)5.(13,38,28,50,77,66,50,98)6.return s[i]-t[i]return strlen(s)-strlen(t)7.p=head->nextp=p->nextreturn length二、解答：1. Huffman算法:求Huffman树（带权路径长度最短的二叉树）Dijkstra算法:求图中从某个源点到其余各顶点的最短路径Prim算法:求最小生成树Kruskal算法:求最小生成树2. 选择排序不稳定举例:{256256*512128}i=1{128256*512256}i=2{128256*512256}i=3{128256*256512}256和256*在排序前后相对位置发生变化,所以说选择排序是不稳定的。

3.4.举例：5.Hash表如下查找成功情况下的平均查找长度为(3+4+4+4+1+2+2+1+1+2)/10=2.46.快速排序,堆排序,归并排序以归并排序说明:假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2或1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止.举例如下:三、解答：typedef struct BiTNode{TelemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){if(!T){p=f;return FALSE;}else if EQ(key,T->data.key){p=T;return TRUE;}else if LT(key,T-> data.key) SearchBST(T->lchild,key,T,p);else if SearchBST(T->rchild,key,T,p);}Staus InsertBST(BiTree &T,ElemType e){if(!SearchBST(T,e.key,NULL,p){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p) T=s;else if LT(e.key,p->data.key)p->lchild=s;else p->rchild=s;return TRUE;}else return FALSE;}从空树出发,经过一系列的查找插入操作之后,可生成一棵二叉树. main(){BiTree BiT=NULL;int elememt;scanf(“%d”,&element);while(element!=9999){InsertBST(BiT,element);scanf(“%d”,&element);}}typedef struct BiTNode{TelemType data;struct BiTNode *left, *right;int bal;}BiTNode,*BiTree;int computbal(BiTree bt){int hl, hr, max;if(bt==NULL) return(0);else {hl=computbal(bt->LChild);/* 求左子树的深度 */hr=computbal(bt->RChild);/* 求右子树的深度 */bt->bal=hl-hr;/*求出平衡因子*/max=hl>hr?hl:hr;/* 得到左、右子树深度较大者*/return(max+1);/* 返回树的深度 */}}void BFSTraverse(Graph G,Status (*visit)(int v)){for (v=0;v<G.vexnum;++v) visited[v]=FALSE;InitQueue(Q);for(v=0;v<G.vexnum;++v)if(!visited[v]){Visit(v);visited[v]=TRUE;EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!Visited[w]){Visit(w);visited[w]=TRUE;EnQueue(Q,w);}}}}。

数据结构模拟试题三一．判断题（每小题1 分，共10分）1.逻辑结构不同的数据，要采用不同的存储方法来存储。

2.单链表中的结点只有后继，没有前驱。

3.栈和队列具有相同的逻辑特性。

4.二叉树中结点之间的相互关系不能用二元组来表示。

5.关键路径是由权值最大的边构成的。

6.在表示矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小无关。

7.在广义表中，每个原子必须是单个字符。

8.在平衡二叉排序树中，每个结点的平衡因子值是相等的。

9.只有在线性表的初始状态为逆序排列的情况下，起泡排序过程中，元素的移动次数才会达到最大值。

10.在B+树上可以进行顺序查找。

二．填空题（每空1分，共10分）1.若用不带表头结点的单链表来表示链接队列，则只有在________情况下，插入操作既要修改队尾指针的值，也要修改队头指针的值;只有在________情况下，删除操作仅需修改队首指针的值，不需修改队尾指针的值。

2.无向图中边的数目等于邻接矩阵中___________。

3.在各元素查找概率相等的情况下，在含有12个元素的二叉排序树上查找其中一个元素，元素间的平均比较次数至少是____次，至多是____次。

4.对12个元素进行快速排序，排序码的比较次数最多是___次。

5.对B+树来说，若某个非根分支结点中有6个关键字，则在它的某个孩子结点中至少有_____个关键字，至多有_____个关键字。

6.如果在根结点中要查到要找的关键字，则对于B-树来说，下一步应该_________，而对于B+树来说，下一步应该_________。

三．单选题（每题2分，共20分）1.线性结构采用链式存储，________。

A．对插入、删除结点的操作较为有利B．不利于进行顺序访问C．逻辑上相邻的结点在存储器中也相邻D．可以用一些不连续的存储区域来存放一个结点2. 某算法的时间复杂度为O（2n），表明该算法的________。

A．执行时间与2n成正比B．执行时间等于2nC．问题规模是2n D．问题规模与2n成正比3. 在长度为n的_________上，删除最后一个元素，其算法的时间复杂度是O(n)。

数据结构试题3参考答案一、单项选择题（本大题共15小题，每小题2分，共30分） 1．Ｄ ２．Ｂ３．Ｃ４．Ｂ５．Ｄ６．Ａ ７．Ｃ８，Ｄ９，Ａ10．Ｃ11．Ｄ 12．Ｃ13．Ｄ 14．Ｃ15．Ｂ二、填空题（本大题共10小题，每小题2分，共20分） 16．存储（或存储结构）17.p －＞next －＞next18．进栈和退栈．进栈和退栈19．12 12 2020．A[4][8] 21．384 22．abefcdg 23．快速排序、堆排序、希尔排序24．２．２ 25.多关键字多关键字三、解答题（本大题共4小题，每小题5分，共20分） 26．（1）对第一结点的操作和其他结点一样，无须特殊处理。

（（2）空表和非空表的处理相统一了。

）空表和非空表的处理相统一了。

27．28．该图的图形为：该图的图形为：深度优先遍历序列为：深度优先遍历序列为：abdce abdce广度优先遍历序列为：广度优先遍历序列为：abedc abedc2929．．（１）对关键字3535、、2020、、33和48进行查找的比较次数为３、２、１、１；１、１；（２）平均查找长度（２）平均查找长度59521123=++++=ASL四、算法阅读题（本大题共4小题，每小题5分，共20分） 30． ①S1=S1－>next ②s2=s2－>next ③s2(或s2!=NULL 或s2&&!s1) ④s1(或s1!=NULL 或s1&&!s2) ⑤return 0 31.（1）查询链表的尾结点）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a 2,a 3,…,a n ,a 1）32. ①(i＋1)%2(或1－i) ②Q－>rear[i] ③(Q－>rear[i]＋)%Maxsize 33.(1)Leafhead F H G D ∧（2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。

《数据结构》模拟试题13一、填空题（每小题2分，共18分）1、数据的逻辑结构包括，和三种结构。

2、队列是操作受限的线性结构，只能在插入元素，而在删除元素。

3、串是一种特殊的线性表，其特殊性体现在。

4、有一个10阶对称矩阵A，采用压缩存储方式采用压缩存储方式，以行为主存储下三角形到一个一维数组中，A[0][0]的地址是100（每个元素占2个基本存储单元），则A[5][9]的地址是。

5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为。

6、对于一个有n个顶点和e条边的无向图，若采用邻接链表存储，则表头向量的大小为，邻接表中的结点总数为。

7、对线性表进行二分查找时，要求线性表必须是，且要求。

8、对于文件，按物理结构划分，可分为顺序文件、文件、文件和多关键字文件。

9、外部排序的最基本方法是，其主要时间花费在方面。

二、单项选择题（请将答案写在题目后的括号中。

每题2分，共18分）1、如下函数是求1!+2!+…+n!，其时间复杂度是（）。

Long int Sum (int n){ long int sum=0 , t=1 ; int p ;for (p=1; p<=n ;p++) { t=t*p ; sum+=t ; }return(sum) ;}（A）O(n) （B）O(n2) （C）O(㏒2n) （D）O(n㏒2n)2、设有一个栈顶指针为top的顺序栈S，则弹出S的栈定元素的操作是（）。

（A）p=S[top++]；（B）p=S[++top]；(C)p=S[top--]；（D）p=S[--top]；3、广义表((a),((b),c),(((d))))的表头是，表尾是。

（）（A）(a) ((b),c),(((d))) （B）(a) (((b),c),(((d))))（C）((a),((b),c)),(((d))) （D）(a) (((d)))4、一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，则其后序遍历序列是( )。

数据结构模拟题（一）一、单选题1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

试卷B一、选择题（本题共20分,每题2分）1．在数据结构中，从逻辑上可以把数据结构分成（ ） 。

A ．动态结构和静态结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧凑结构 D. 内部结构和外部结构 2. 下列程序段的时间复杂度是（ ）count=0;for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++;A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2) 3. 以下描述错误的是：（ ）A. 线性表是n 个数据元素的有限非空集合。

B. 栈和队列都是操作受限的线性表。

C. 串（或字符串）是由零个或多个字符组成的有限序列。

D. 非空栈中的栈顶指针top 始终指向栈顶元素的下一个位置。

4. 若采用少用一个队列空间的方法来区分队满队空两种状态，则判定一个顺序循环队列 Q （最大队列长度MAXSIZE ）为满队列的条件是( )。

A. Q.front=Q.rearB. Q.front!=Q.rearC. Q.front=(Q.rear+1) % MAXSIZED. Q.front!=(Q.rear+1) % MAXSIZE 5. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。

A. 3 B. 4 C. 5 D. 66. 设矩阵A （如下图所示）是一个对称矩阵，为了节省存储，将其下三角（包括对角线）部分按行序存放在一维数组 B[n(n+1)/2]中，对下三角部分中任一元素 ai,j(i ≥j)，在一维数组 B 的下标位置k 的值是（ ）。

A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j0,01,01,11,01,11,1...............n n n n a a a A a a a ----⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦7. 有一个有序表为｛5, 18，23, 33, 42, 54,56,78｝，当折半查找56时，经过（ ）次比较后查找成功。

《数据结构》模拟试卷及参考答案模拟试卷一一、单选题（每题2 分，共20分）1.以下数据结构中哪一个是线性结构？( )A. 有向图B. 队列C. 线索二叉树D. B树2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。

A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3.以下哪一个不是队列的基本运算？（）A. 在队列第i个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？A.14B.5C.6D.85.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。

以下6-8题基于图1。

6.该二叉树结点的前序遍历的序列为( )。

A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B7.该二叉树结点的中序遍历的序列为( )。

A. A、B、C、D、E、G、FB. E、A、G、C、F、B、DC. E、A、C、B、D、G、FE.B、D、C、A、F、G、E8.该二叉树的按层遍历的序列为( )。

A．E、G、F、A、C、D、B B. E、A、C、B、D、G、FC. E、A、G、C、F、B、DD. E、G、A、C、D、F、B9.下面关于图的存储的叙述中正确的是( )。

A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )A. a，g，h，m，n，p，q，x，zB. a，g，m，h，q，n，p，x，zC. g，m，q，a，n，p，x，h，zD. h，g，m，p，a，n，q，x，z二、填空题（每空1分，共26分）1.数据的物理结构被分为_________、________、__________和___________四种。

数据结构模拟题3（无答案）模拟试题3一．选择题1.当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（）A.n-1B.log2nC. 2log2nD.n22.以下时间复杂性不是O(n2)的排序方法是( )A.直接插入排序B.二路归并排序C.冒泡排序D.直接选择排序3.．对采用二分查找法进行查找运算的查找表，要求按（）方式进行存储。

A.顺序存储 B 链式存储C.顺序存储且结点按关键字有序D.链式存储且结点按关键字有序4.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。

A.2B. 3C. 4D. 125.静态查找表与动态查找表两者的根本差别在于( )…………………………………………….A.逻辑结构不同B.存储实现不同C.施加的操作不同D.数据元素的类型不同6．用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为A.O（n2）B. O(nlog2n)C. O（n）D.O(log2n)7.设有6个结点的无向图，该图至少应有（）条边能确保是一个连通图。

A. 5B. 6C. 7 D 88.在无向图中，所有顶点的度数之和是所有边数的（）倍。

A.0．5B.1C.2D.49.深度为6的二叉树最多有( )个结点.A.64B.63C.32D.3110．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为 ( )A.42B.40C.21D.2011.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（）A.acbedB.deabcC.decabD.cedba12.设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同13．如果以链表作为栈的存储结构，做退栈操作时( )A.必须判别栈是否满B.必须判别栈是否空C.判别栈元素的类型D.对栈不做任何操作14．链栈与顺序栈相比，有一个比较明显的优点即（）A.插入操作更方便B. 通常不会出现栈满的情况C.不会出现栈空的情况D. 删除操作更方便15.线性结构中的一个结点代表一个（）A. 数据元素B. 数据项C. 数据D. 数据结构二．填空题1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。

数据结构试卷（一）一、选择题（ 20 分）1．构成数据的基本单位是（）。

(A) 数据项(B) 数据种类(C) 数据元素(D) 数据变量2．设数据结构 A=(D， R)，此中 D={1 ， 2， 3， 4} ， R={r} ，r={<1 ， 2>， <2， 3>， <3， 4>， <4， 1>} ，则数据结构 A 是（）。

(A) 线性结构(B) 树型结构(C) 图型结构(D) 会合3．数组的逻辑结构不一样于以下（）的逻辑结构。

(A) 线性表(B) 栈(C) 行列(D) 树4．二叉树中第 i(i ≥ 1) 层上的结点数最多有（）个。

(A) 2i (B) 2 i (C) 2 i-1 (D) 2i-15．设指针变量 p 指向单链表结点A，则删除结点 A 的后继结点 B 需要的操作为（）。

(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈 S 和行列 Q的初始状态为空，元素E1、E2、E3、E4、 E5 和 E6 挨次经过栈 S，一个元素出栈后即进入行列 Q，若 6 个元素出列的次序为E2、 E4、 E3、 E6、 E5 和 E1，则栈 S 的容量起码应当是（）。

(A) 6 (B) 4 (C) 3 (D) 27．将 10 阶对称矩阵压缩储存到一维数组 A 中，则数组 A 的长度最少为（）。

(A) 100 (B) 40 (C) 55 (D) 808．设结点 A 有 3 个兄弟结点且结点 B 为结点 A 的双亲结点，则结点 B 的度数数为（）。

(A) 3 (B) 4 (C) 5 (D) 19．依据二叉树的定义可知二叉树共有（）种不一样的形态。

(A) 4 (B) 5 (C) 6 (D) 710. 设有以下四种排序方法，则（）的空间复杂度最大。

《数据结构》模拟试题03一、单项选择题（每题 2 分，共30分）1．算法指的是（ ）A ．计算机程序B ．解决问题的计算方法C ．排序算法D ．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ ） A ．必须是不连续的 B ．连续与否均可 C ．必须是连续的D ．和头结点的存储地址相连续3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（ ） A ．O （1） B ．O （n ） C ．O （m ） D ．O （m+n ） 4．由两个栈共享一个向量空间的好处是：（ ） A ．减少存取时间，降低下溢发生的机率 B ．节省存储空间，降低上溢发生的机率 C ．减少存取时间，降低上溢发生的机率 D ．节省存储空间，降低下溢发生的机率5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为（ ）A ．front=front+1B ．front=(front+1)%(m-1)C ．front=(front-1)%mD ．front=(front+1)%m 6．如下陈述中正确的是（ ）A ．串是一种特殊的线性表B ．串的长度必须大于零C ．串中元素只能是字母D ．空串就是空白串7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）A ．O （n3） B ．O （n ） C ．O （n2） D ．O （n3）8．一个非空广义表的表头（ ）A ．不可能是子表B ．只能是子表C ．只能是原子D ．可以是子表或原子 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表对应的稀疏矩阵是（ ）5A.08067000000050400000--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥B.08067000504000000300--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥C.08060000020050400000--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥D.08060000700050400300--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A．4 B．5 C．6 D．711．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )A．e B．2e C．n2－e D．n2－2e12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）A．选择排序B．希尔排序C．归并排序D．快速排序14．适于对动态查找表进行高效率查找的组织结构是（）A．有序表B．分块有序表C．三叉排序树D．线性链表15．不定长文件是指（）A．文件的长度不固定B．记录的长度不固定C．字段的长度不固定D．关键字项的长度不固定二、填空题（每题2分，共20分）1．数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关，是独立于计算机的。

数据结构期末模拟试题03（有答案）吉首大学试题库课程测试试题（卷）----------------------以下为教师填写--------------------I、命题院（部）：数学与计算机科学学院II、课程名称：数据结构III、测试学期：20 －20 学年度第学期IV、测试对象：学院专业级班V、问卷页数（A4）：页VI、答卷页数（A4）：页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、单选题（每小题2分，共8分）1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )。

A nB n/2C (n+1)/2D (n-1)/22、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。

A s→link=p→link; p→link=s;B p→link=s; s→link=q;C p→link=s→link; s→link=p;D q →link=s; s→link =p; 3、栈的插入和删除操作在（）进行。

A 栈顶B 栈底C 任意位置D 指定位置4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A 24B 71C 48D 53 二、填空题（每空1分，共32分）1、数据的逻辑结构被分为__________、___________ 、________和________四种。

2、一种抽象数据类型包括______________和_____________两个部分。

3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。

第3章栈和队列一、填空题1. 线性表、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队头删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。

不允许插入和删除运算的一端称为栈底。

3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 在一个循环队列中，队首指针指向队首元素的前一个位置。

5. 在具有n个单元的循环队列中，队满时共有n-1个元素。

6. 向栈中压入元素的操作是先移动栈顶指针，后存储元素。

7. 从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。

8. 带表头结点的空循环双向链表的长度等于0 。

二、判断正误（×）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（×）2. 在表结构中最常用的是线性表，栈和队列不太常用。

（√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

（×）5. 栈和链表是两种不同的数据结构。

（×）6. 栈和队列是一种非线性数据结构。

（√）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（√）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（×）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

（×）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

三、单项选择题（ B ）1. 栈中元素的进出原则是Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出（C）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定（B）3. 判定一个栈ST（最多元素为m0）为空的条件是Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0（A）4. 判定一个队列QU（最多元素为m0）为满队列的条件是Ａ．QU->rear －QU->front = = m0 Ｂ．QU->rear －QU->front －1= = m0Ｃ．QU->front = = QU->rear Ｄ．QU->front = = QU->rear+1（ D ）5．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n6. 设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。

数据结构与算法-模拟试题3一、单项选择题（每个题只有一个答案是正确的，请将正确的答案填写到括号内。

本题共15个小题，每小题3分，共45分）1. 下面的说法正确的是（）。

A.数据结构可以分成逻辑结构和线性结构B.数据的逻辑结构是指数据及其逻辑结构在计算机中的表示C.从逻辑结构角度数据结构可以分为集合、线性结构、树结构和图结构四类D.数据的存储结构是从具体问题抽象出来的数学模型2. 线性表采用链式存储时，存储空间（）。

A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续3.顺序循环队列容量为20，队头表示第一个元素的位置，队尾表示最后一个元素的下一个位置，当队头为12，队尾为5的时候，队列中共有（）个元素。

A.15B.14C.12D.134. 设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。

A. 顺序表B. 链表C. 队列D. 栈5. 下列有关串的操作中，（）不是串的常用操作。

A.连接（concat）B.求子串（substring）C.插入（insert）D.求长度(length)6. 广义表GL=(a, (a))的表头是（）。

A. aB. (a)C. ()D. ((a))7.二叉树高度为k，第1层到第k-1层每层都是满的，第k层结点数不满，但该层结点从左到右满放，则该二叉树为（）。

A. 斜树B. 有序树C. 满二叉树D. 完全二叉树8.将一棵树转换为二叉树后，该转换后的二叉树的特点是（）。

A. 没有右子树B. 没有左子树C. 左右子树都有D. 每层上只有一个结点9. 关于有向图的的说法错误的是（）。

A. 有向图中顶点v的入度(indegree)是以顶点v为终点（弧头）的弧的数目B. 有向图中顶点v的出度(outdegree)是以顶点v为始点（弧尾）的弧的数目C. 有向图中各顶点的入度之和等于各顶点的出度之和D. 有向图中各顶点入度之和等于弧数e的2倍10. 在无向图的邻接表存储结构中插入一个顶点和一条边，不需要进行的操作是（）。

模拟试题三模拟试题三一、选择题（30分）1.下面程序的时间复杂度为( )。

for(i=O;i<m;i++)for(j=0;j<t;j++)c[i][j]=O;for(i=O;i<m;i++)for(j=O;j<t;j++)for(k=O;k< SPAN>c[i][j]=c[i][j]+a[i][k]b[k][j];A) O (mnt) B)0(m+n+t) C) O(m+nt) D)O(mt+n)2.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动( )个元素。

A) n-i B) n-i+l C) n-i-l D)i3.串的逻辑结构与( )的逻辑结构不同。

A)线性表 B)栈 C)队列 D)树4.二叉树第i(i≥1)层最多有( )个结点。

A) 2i B) 2i C) 2i-l D) 2i-15.设单链表中指针p指向结点A，若要删除A之后的结点（若存在），则修改指针的操作为( )。

A) p->next=p->next->next B) p=p->nextC) p=p->next->next D)p->next=p6.设一数列的输入顺序为l，2，3，4，5，6，通过栈操作不可能排成的输出序列为( )。

A)3,2,5,6,4,l B)l,5,4,6,2,3C)2,4,3,5,l,6 D)4,5,3,6,2,l7。

设字符串Sl=‘ABCDEFG’，S2=‘PQRST’，则运算S=Concat(Sub(S1，2，Length(S2))Sub(S1，Length(S2)，2))后结果为( )。

A)‘BCQR' B)‘BCDEF'C)‘BCDEFG' D)‘BCDEFEF'8.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，all为第1个元素，其存储地址为1，每个元素占用1个地址空间，则a85的地址为( )A) 13 B) 33 C) 18 D) 409.如果结点A有3个兄弟，且B为A的双亲，则B的度为( )。

数据结构模拟卷3一、单项选择题，在每小题的四个备选答案中，选出一个正确的答案，并将其代码填入答题纸上对应题号后的括号内。

不准不填，否则无分。

（共15 小题，每小题2分，共30 分）1、线性表是具有n个C的有限序列。

A、表元素B、字符C、数据元素D、信息项2、若长度为n的线性表采用顺序存储结存，在其第i个位置插入一个新元素的算法时复杂度为C。

(1≤i≤n+1)A、O(0)B、O(1)C、O(n)D、O(n*n)3、设单链表中结点的结构为（data，Link）。

已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插人结点*s，则应执行下列哪一个操作B。

A、s->link=p->link; p->link=s;B、q->link=s; s->link=p;C、p->link=s->link; s->link=p;D、p->link=s; s->link=q;4、设单链表中结点的结构为（data，Link）。

已知指针p所指结点不是尾结点的，若在*p之后插入结点*s，则应执行下列哪一个操作 B ？A、s->link=p; p->link=s;B、s->link=p->link; p->link=s;C、s->link=p->link; p=s;D、p->link=s; s->link=p;5、将一个递归算法改为对应的非递归算法时，通常需要使用A。

A、栈B、队列C、循环队列D、优先队列6、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为C。

A、n-2B、n-1C、nD、n+17、广义表A(a),则表尾为C。

A、aB、(( ) )C、空表D、（a）8、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2,则AA、 n0=n2+1B、 n2=n0+1C、n0=2n2+1D、 n2=2n0+19、栈的插入和删除操作在A进行。