数据结构复习资料

1、数据结构试题一、 单选题1、 在数据结构的讨论中把数据结构从逻辑上分为 （） a 内部结构与外部结构 b 静态结构与动态结构 c 线性结构与非线性结构 d 紧凑结构与非紧凑结构。2、采用线性链表表示一个向量时，要求占用的存储空间地址（） a 必须是连续的 b 部分地址必须是连续的 c 一定是不连续的 d 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ ）。 a n b n/2 c (n-1)/2 d (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ ）。a slink = plink; plink = s;

2、b plink = s; slink = q;c plink = slink; slink = p; d qlink = s; slink = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ ）方法最好。 a 起泡排序 b 堆排序 c 锦标赛排序 d 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。 a 求子串 b 模式匹配 c 串替换 d 串连接7、在数组a中，每一个数组元素aij占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ ）。a 80 b 100 c 240

3、 d 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。a 栈 b 队列 c 循环队列 d 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ ）。10、在循环队列中用数组a0.m-1 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ ）。 a ( front - rear + 1) % m b ( rear - front + 1) % mc ( front - rear + m) % m d ( rear - front + m) % m11、一个数组元素ai与（ ）的表示等价。a *（a+i） b a+i c *

4、a+i d &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ ）参数。a 指针 b 引用 c 值 d 变量13、下面程序段的时间复杂度为（ ） for (int i=0;im;i+) for (int j=0;jlink=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;19、 设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（ ）20、 a s-link=p-link; p-li

5、nk=s; b q-link=s; s-link=p21、 c p-link=s-link;s-link=p; d p-link=s; s-link=q;20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（ ）a p-link=p-link-link; b p=p-link; p-link=p-link-link;c p-link=p-link; d p=p-link-link;21、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ ）

6、a s=rear; rear=rear-link; delete s; b rear=rear-link; delete rear; c rear=rear-link-link; delete rear; d s=rear-link-link; rear-link-link=s-link; delete s;s为第一个结点硫22、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( )。a current-link =null b first-link=currentc fir

7、st=current d current-link=first？23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( )。a c,b,a b b,a,c c c,a,b d a,c,b24、栈的数组表示中，top为栈顶指针，栈空的条件是( )。a top=0 b top=maxsize c top=maxsize d top=-125、栈和队列的共同特点是( )。a 都是先进后出 b 都是先进先出c 只允许在端点处插入和删除 d 没有共同点26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( ).a f+1= =r b r+1= =f c f= =0 d

8、f= =r27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ ）a n-2 b n-1 c n d n+128、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。a top+; b top-; c top=0; d top;29、设链式栈中结点的结构为（data, link）,且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（ ）操作。a x=top-data; top=top-link; b top=top-link; x=top-data; c

9、 x=top; top=top-link; d x=top-data;30、设循环队列的结构是： const int maxsize=100; typedef int data type; typedef struct data type datamaxsize; int front, rear; queue;若有一个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)

10、% maxsize;31、设有一个递归算法如下：int fact (int n ) if (n=0) return 1;else return n*fact(n-1);下面正确的叙述是（ ）a 计算fact(n) 需要执行n次递归 b fact(7)=5040 c 此递归算法最多只能计算到fact(8) d 以上结论都不对32、设有一个递归算法如下int x (int n) if (n递归表纯表线性表 b 递归表线性表再入表纯表 c 递归表再入表纯表线性表 d递归表再入表线性表纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。a 空或只有一个结点 b 高度等于其结点数

11、c 任一结点无左孩子 d 任一结点无右孩子38、对于任何一棵二叉树t，如果其终端结点数为n0，度为2的结点为n2.,则( )a n0= n2+1 b n2= n0+1 c n0= 2n2+1 d n2=2n0+1 39、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）a 24 b 73 c 48 d 5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第i 个结点的地址为（）。a da1+(i-1)*m b da1+i*m c da1-i*m d da1+(i+1)*m41、34 具有35个结点的完全二叉树的深度为

12、( )a 5 b 6 c 7 d 842、对线性表进行折半搜索时，要求线性表必须（ ）a 以链接方式存储且结点按关键码有序排列 b 以数组方式存储 c 以数组方式存储且结点按关键码有序排列 d以链接方式存储43、顺序搜索算法适合于存储结构为（ ）的线性表。a 散列存储 b 顺序存储或链接存储 c 压缩存储 d 索引存储44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ ）a o（n2） b o（n log2n） c o（log2n） d o（n）45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( )a n b n+1 c n-1 d n+e46、判断一个

13、有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。a 求关键路径的方法 b 求最短路径的dijkstra方法 c 深度优先遍历算法 d 广度优先遍历算法47、在10阶b-树中根结点所包含的关键码个数最多为（ ），最少为( )a 1 b 2 c 9 d 1048、对包含n 个元素的散列表进行搜索，平均搜索长度为（ ）a o（log2n） b o（n）c 不直接依赖于n d 上述都不对二、 填空题（）1、数据的逻辑结构被分为 四种2、数据的存储结构被分为 四种3、一种抽象数据类型包括（ ）和（ ）两个部分。4、 设有两个串p和q，求p在q中首次出现的位置的运算称为（） 5、 栈、队

14、列逻辑上都是（）结构。6、 线性结构反映结点间的逻辑关系是（）的，图中的数据元素之间的关系是（）的，树形结构中数据元素间的关系是（）的。）8、串是由（）字符组成的序列。（）称为空串，（）称为空格串。9、设目标串t=”abccdcdccbaa”,模式p=”cdcc”则第（）次匹配成功。10、一维数组的逻辑结构是（），存储结构是（）。对于二维数组，有（）和（）两种不同的存储方式，对于一个二维数组amn,若采用按行优先存放的方式，则任一数组元素aij相对于a00的地址为（ ）。11、向一个顺序栈插入一个元素时，首先使（ ）后移一个位置，然后把待插入元素（ ）到这个位置上。从一个顺序栈删除元素时，需要

15、前移一位（）。12、在一个循环队列q中，判断队空的条件为（）, 判断队满的条件为（ ）13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（ ）。14、一棵高度为5的满二叉树中的结点数为（ ）个，一棵高度为3满四叉树中的结点数为（ ）个。15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a0中，其余类推，则ai元素的左子女结点为（ ），右子女结点为（ ），双亲结点（）为（ ）.16、在一个最大堆中，堆顶结点的值是所有结点中的（），在一个最小堆中，堆顶结点的值是所有结点中的（）。17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k

16、个存储单元，第一个元素的地址为loc(a1)，那么，loc(ai)= 。18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（ ）个字符编码。19、设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（）个。20、由一棵二叉树的前序序列和（）可唯一确定这棵二叉树。 21、以折半搜索方法搜索一个线性表时，此线性表必须是（）存储的（）表。22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（）23、对于折半

17、搜索所对应的判定树，它既是一棵（），又是一棵（）。24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（），判定树中前层的结点数为（），最后一层的结点数为（）。25、在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。在一个具有n个顶点的无向完全图中，包含有（ ）条边，在一个具有n个顶点的有向完全图中，包含有（ ）条边。26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（）和（）。27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是( )。28、在插入和选择排序中，若初始数据基本正序，则选择（），若初始数据基本反序，则

18、最好选择（）。29、算法是对特定问题的求解步驟的一种描述，它是（）的有限序列，每一条（指令）表示一个或多个操作。30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（）31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。32、处理冲突的三种方法，分别为(线性探测)、（ 随机探测 ）、（ 链地址法）。33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（ ）34、快速排序在平均情况下的时间复杂度为（），在最坏情况下的时间复杂度为（）；快速排序在平均情

19、况下的空间复杂度为（），在最坏情况下的空间复杂度为（）。35、假定一组记录的排序码为（，），对其进行归并排序的过程中，第二趟排序后的结果是（）36、假定一组记录的排序码为（，），对其进行快速排序的第一次划分的结果是（）。37、一个结点的子树的（ ）称为该结点的度。度为（ ）的结点称为叶结点或终端结点。度不为（ ）的结点称为分支结点或非终端结点。树中各结点度的（ 最 ）称为树的度。38、设ki=kj (1=i=n, 1=j=n,ji)且在排序前的序列中ri领先于rj (i1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个

20、分支结点？答案：6、 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:(1) 各层的结点个数是多少?(2) 编号为i的结点的父结点(若存在)的编号是多少?(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?(5) 若结点个数为 n, 则高度h是n 的什么函数关系?答案：7、 写出下列中缀表达式的后缀形式：(1) a* - b + c(2) (a + b) * d + e / (f

21、+ a * d) + c(3) a & b| ! (e f)注：按c+的优先级)(4) !(a & !( (b d) ) )|(c 1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？16、 对于一个高度为h的avl树，其最少结点数是多少？反之，对于一个有n个结点的avl树, 其最大高度是多少? 最小高度是多少?17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的

22、判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。答案：折半搜索时的判定树为： 18、试对下图所示的aoe网络(1) 这个工程最早可能在什么时间结束。(2) 求每个事件的最早开始时间vei和最迟开始时间vli。(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。19、已知有五个待排序的记录，其关键字分别为：256，301，751，129，937,863，742，694，076，438请用快速排序的方法将它们从小到大排列。答案： 20、设有150个记录要存储到散列表中,

23、并利用线性探查法解决冲突, 要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ (设a是散列表的装载因子，则有aslsucc = ( 1+1/ (1-a) )/2)。五、算法分析题1、给出下列递归过程的执行结果 void unknown ( int w ) if ( w ) unknown ( w-1 ); for ( int i = 1; i = w; i+ ) cout w ; cout endl; 调用语句为 unknown (4)。 2、给出递归过程的执行结果 void unknown ( int n ) cout n % 10 ; if ( int ( n / 10

24、) ) unknown ( int ( n / 10 ) ); 调用语句为unknown ( 582 )。3、给出递归过程的执行结果int unknown ( int m ) int value; if ( ! m ) value = 3; else value = unknown ( m-1 ) + 5; return value;执行语句为 cout unknown (3)。 4、 设有一个二维数组amn，假设a00存放位置在644（10），a22存放位置在676（10），每个元素占一个空间，问a33（10）存放在什么位置？脚注（10）表示用10进制表示。5、设单链表结构为 struct

25、listnode int data ; listnode * link ; ;下面的程序是以单链表为存储结构, 实现二路归并排序的算法, 要求链表不另外占用存储空间, 排序过程中不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。在初始状态下, 所有待排序记录链接在一个以r为头指针的单链表中。例如, 在算法实现时，利用了一个队列做为辅助存储, 存储各有序链表构成的归并段的链头指针。初始时, 各初始归并段为只有一个结点的有序链表。队列的数据类型为queue, 其可直接使用的相关操作有n 置空队列操作：makeempty ( ); n 将指针x加入到队列的队尾操作：e

26、nqueue ( listnode * x ); n 退出队头元素, 其值由函数返回的操作：listnode *dlqueue ( );n 判队列空否的函数, 空则返回1, 不空则返回0：int isempty( )。 解决方法提示： 程序首先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头 指针存放在一个指针队列中。 当队列不空时, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头指针存放到队列中。 如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序子链表即为所求。在算法实现时有 6 处语句缺失，请阅读程序后补上。(1) 两路归并算法voi

27、d merge ( listnode * ha, listnode * hb, listnode *& hc ) listnode *pa, *pb, *pc ; if ( hadata = hbdata ) hc = ha; pa = halink; pb = hb; else hc = hb; pb = hblink; pa = ha ; pc = hc; while ( pa & pb ) if ( ) pclink = pa; pc = pa; ; else pclink = pb; pc = pb; ; if ( pa ) pclink = pa; else pclink = pb;

28、 ;(2) 归并排序主程序void mergesort ( listnode * r ) listnode * s, t; queue q ; if ( ! r ) return;s = r; ; while ( s ) t = slink; while ( t != 0 & sdata next; if (q) error(“*p not in head”); 7、 已知一完全二叉树从根结点开始，自顶向下，同一层自左向右连续编号，根结点的编号为0，阅读以下程序请回答该程序所实现的功能： template void linkedtosequent(bintreenode *t,type a ,

29、int i) if (t!=null) a=t-getdata(); linkedtosequent(t-getleftchild(),a,2*i+1); linkedtosequent(t-getrightchild(),a,2*i+2); 主程序调用方式：linkedtosequent(t.root,a,0);答案：8、设散列表为ht13, 散列函数为 h (key) = key %13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1) 采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成

30、功的平均搜索长度和搜索不成功的平均搜索长度。(2) 采用双散列法寻找下一个空位, 再散列函数为 rh (key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 hi = (hi-1 + rh (key) % 13, h1 = h (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。答案： 9、阅读下面程序，指出其算法的功能并求出其时间复杂度。（1） int prime(int n)int i=2,x=(int)sqrt(n);while(ix) return 1;else return 0; (2)int sum1(int n) int p=1,s=0; f

31、or(int i=1;irlink,q=dl-llink; while(p!=q&p-llink=q)& ) if (p-data=q-data) else sym=0; return sym;11、阅读下面程序，指出其算法的功能 #include “stack.h” int basetrans(int n,int b) int i,result=0;stacks; while(n!=0)i=n%b;n=n/b;s.push(i); while(!s.isempty()i=s.gettop();s.pop(); result=result*10+i; return result; 答案：12、阅读下面程序，指出其算法的功能template void binarytree:binsearchtree(bintreenode*t,int &bs) if(t!=null)if(t-letfchild=null|t-datat-leftchild-data)& (t-rightchild=null|t-datarightchild-data) bs=1;binsearchtree(t-leftchild,bs);if(bs) binsearchtree(t-rightchild,bs);else bs=0; 答