数据结构复习题

考试题型一、选择题(每小题2分，共30分)二、程序填空题(本大题共20空，每空1分，共20分)三、问答题(本大题共3小题，共35分)四、算法设计题(共15分)数据结构复习题一、选择题.下面程序段的时间复杂度是()。count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;A.O(log2n) B.O(n) C.O(nlog2n) D.0(n2).顺序存储结构中数据元素之间的逻辑关系是由()表示。A.线性结构 B.非线性结构 C.存储位置 D.指针.顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()。A.110 B.108 C.100 D.1201、与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。A.存储结构 B.存储实现C.逻辑结构 D.运算实现.试分析下面程序段的时间复杂度()。x=90;y=100;while(y>0)if(x>100){x=x-10;y-;}elsex++;A.0(1) B.0(n2) C.O(log3n)D.0().顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()。A.110 B.108 C.100 D.120.链接存储的存储结构所占存储空间()。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数.创建一个包括n个结点的有序单链表的时间复杂度是( )。A.0(1) B.0(n) C.0(n2) D.O(nlog2n).向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为()。A.8 B.63.5 C.63 D.7.在单锌表中，要将s所指结点插入到p所指结点之后，其语句应为（）。A.s->next=p+l;p->next=s; B.（*p）.next=s;（*s）.next=（+p）.next;C.s->next=p->next;p->next=s->next; D.s->next=p->next;p->next=s;.在一个以L为头指针的单循环链表中，p指针指向链尾的条件是（）。A.p->next==L B.p->next==NULLC.p->next->next==L D.p->data=-1.若已知一个栈的人栈序列是1,2,3, 其输出序列为pi,pz,P3,…，Pn，若Pi=n，则pi为（）。A.i B.n-i C.n-i+1 D.不确定。.已知循环队列存储在一维数组A[0..nT]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[（）]处,则初始时front和rear的值分别是（）。A.0,0 B.0,n-l C.n-1,0 D.n-l,n-l.已知字符串S为"abaabaabacacaabaabcc"，模式串t为"abaabc"，采用KMP算法进行匹配，第一次出现“失配"（s[i] 时，i=j=5,则下次开始匹配时，i和j的值分别是（）。A.i=l,j=0 B.i=5,j=0 C.i=5,j=2 D.i=6,j=2.已知一棵完全二叉树的第6层（设根为第1层）有8个叶子结点，则该完全二叉树的结点个数最多是（）。A.39 B.52 C.Ill D.119.若一组记录的排序码为{46,79,56,38,40,84},则利用堆排序的方法建立的初始堆为（）。A.79,46,56,38,40,84 B.84,79,56,38,40,46C.84,79,56,46,40,38 D.84,56,79,40,46,38.下列选项给出的是从根分别到大两个叶子结点路径上的权值序列，能属于同一棵哈夫曼树的是（）。A.24,10,5和24,10,7 B.24,10,5和24,12,7C.24J0,10和24,14/I D.24J0,5和24,14,6.在双向链表存储结构中，删除p所指的结点时须修改指针（）。p->next->prior=p->prior;p->prior->next=p->nex（;p->next=p->next->next;p->next->prior=p;p->prior->next=p;p->prior=p->prior->prior;p->prior=p->next->next;p->next=p->prior->prior;.若已知一个栈的入枝序列是1,2,3,…，n,其输出序列为pl,p2,p3,…，pn,若pl=n,贝ijpi为（）oA.i B.n-i C.n-i+1 D.不确定19.设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5和e6依次进入栈S,一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和el,则栈S的容最至少应该是（）。A.2 B.3 C.4 D.620.若••个枝以向量存储，初始栈顶指针top设为n+1,则元素x进栈的正确操作是（）<>A.top++;V[top]=x; B.V[top]=x;top++;C.top—;V[top]=x; D.V[top]=x;top-;21.最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是()。A.(rear+1)%n==front B.rear==frontC.rcar+l==front D.(rcar-l)%n==front.对右图图1所示的图进行拓扑排序，可以得到不同的拓扑序列个数是()。A.4 B.3 C.2 D.1 图1.对于有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是()。A.O(n) B.O(e) C.O(n+e) D.O(nxe).折半查找有序表{4,6,10,12,20,30,50,70,88,100}。若查找表中元素58,则它将依次与表中()比较大小，查找结果是失败。A.20,70,30,50 B.30,88,70,50 C.20,50 D.30,88,50.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[l..(n(n+l))/2]中，则在B中确定aij(i<j)的位置k的关系为()。A.i*(i-l)/2+jB.j*(j-l)/2+iC.i*(i+l)/2+jD.j*(j+l)/2+i.一个具有1025个结点的二叉树的高h为()。A.11 B.10 C.11至1025之间D.10至1024之间.深度为h的满m叉树的第k层有()个结点。(l=<k=<h)A.mk-1 B.mk-1 C.mh-1 D.mh-1.设哈夫曼树中有50个叶结点，则该哈夫曼树中有( )个结点。A.99 B.100C.101 D.102.下面()算法适合构造一个稀疏图G的最小生成树。A.Prim算法B.Kruskal算法C.Floyd算法D.Dijkstra算法.用邻接表表示图进行广度优先遍历时，通常借助()来实现算法。A.栈 B.队列 C.树 D.图.折半查找有序表(4,6,10,12,20,30,50,70,88,100)«若查找表中元素58,则它将依次与表中()比较大小，查找结果是失败。A.20,70,30,50 B.30,88,70,50C.20,50 D.30,88.50.下列关键字序列中，()是堆。A.16,72,31,23,94,53 B.94,23,31,72,16,S3C.16,53,23,94,31,72 D.16,23,53,31,94,72.下述几种排序方法中，()是稳定的排序方法。A.希尔排序B.快速排序 C.归并排序D.堆排序二、程序填空题.已知单链表的存储结构为typcdefstructLNode 〃定义单链表结点类型{ElemTypedata;〃数据域structLNodc*ncxt; 〃指向后继结点}LinkNode将以下程序补充完整，实现用尾插法建立单链表。voidCrcatcListR(LinkNodc*&L,ElcmTypca[],intn){LinkNode*s,*r; 〃i•为尾指针inti;L=(LinkNode*)malloc(sizeof(LinkNode));for(i=0;i<n;i++){s=(LinkNode*)malloc(sizeof(LinkNode));s->data=a[il;).设有一个不带表头结点的单链表L,设计两个递归算法，del(L,x)删除单链表L中第一个值为x的结点，delall(L,x)删除单链表L中所有值为x的结点。voiddel(LinkNode*&L,ElemTypex)(LinkNode*t;if(L==NULL);if(L->data==x)(t=;.free(t);J))voiddelall(LinkNode*&L,ElemTypex)(LinkNode*t;if(L==NULL)return;while()(t=L;L=L->next;).假设以I和()分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和0组成的序列。(1)下面所示的序列中哪些是合法的：A.IOIIOIOOB.1(X)10110C.III0I010D.111(X)100(2)通过对(1)的分析，设计一个算法判定所给的操作序列是否合法。若合法返回真;否则返回假。(假设被判定的操作序列已存入一维数组中)。booljudge(charstr[],,intn){inti=0;ElemTypex;LinkStNode*ls;boolflag=;InitStack(ls);while(i<n&&flag){ if(str[i]==,I')〃进栈elseif(str[i]=='')〃出栈{if(StackEmpty(ls))flag=false;〃栈空时else;)elseflag=;〃其他值无效i++;)if(!StackEmpty(ls))flag=;DestroyStack(ls);return;)三、问答题.已知模式串t="abcaabbabcab”写出用KMP法求得的每个字符对应的next和ncxtval函数值。.已知图2所示的无向网，请给出：(1)邻接表(2)最小生成树。图2.设散列表的地址范围为0~17,散列函数为：H(key)=key%16o用线性探测法处理冲突，输入关键字序列：(10,24,32,17,31,30,46,47,40,63,49),构造散列表，试回答下列问题：(1)画出散列表的示意图.(2)查找关键字60,需要依次与哪些关键字进行比较？(3)若查找关键字60,需要依次与哪些关键字进行比较？(4)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。.已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,给出该二叉树树形表示。.设一组关键字为(7,15,20,31,48,53,64,76,82,99),Hash函数H(key)=key%l1,Hash表表长m=ll,用线性探测法解决冲突，试构造Hash表，并计算查找成功和不成功情况下的平均查找长度。.已知一个图的顶点集V和边集E分别为：V={1,234,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)26(5,6)18,(6,7)25};说明：边集合中(1,2)3中1,2代表顶点，3为改边上的权值画出该图并用克鲁斯卡尔算法得到最小生成树，试写出最小生成树的边的生成顺序过程。.将整数序列(4,5,7,2,1,3,6)中的元素依次插入到一棵空的二叉排序树中，试构造相应的二叉排序树，要求用图形给出构造过程。四、算法设计题.当取di=n/2,&+1=[4/2]时,希尔排序算法如何实现？请完成函数voidShellSort(RecTypeR[],intn)o.假设图G采用邻接表存储，设廿一一个算法void