数据结构与算法试题

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

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

3、 C ）。A 80 B 100 C 240 D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。A 栈 B 队列 C 循环队列 D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。10、在循环队列中用数组A0.m-1 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % mC ( front - rear + m) % m D ( rear - front + m) % m11、一个数组元素ai与

4、（ A ）的表示等价。A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。A 指针 B 引用 C 值 D 变量13、下面程序段的时间复杂度为（ C ） 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，则应执行下列哪

5、一个操作（ B ）A s-link=p-link; p-link=s; B q-link=s; s-link=pC p-link=s-link;s-link=p; D p-link=s; s-link=q;20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（ A ）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、针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ）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是否达到链表表尾的语句是( D )。A current-link

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

8、的条件为( D ).A f+1= =r B r+1= =f C f= =0 D f= =r27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ B ）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 ）操作。A x=top-data;

9、 top=top-link; B top=top-link; x=top-data; C 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，试问判断队列满的条件应是下列哪一个语句（ D ）A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; C Q.fron

10、t + Q.rear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize;31、设有一个递归算法如下：int fact (int n ) if (n=0) return 1;else return n*fact(n-1);下面正确的叙述是（ B ）A 计算fact(n) 需要执行n次递归 B fact(7)=5040 C 此递归算法最多只能计算到fact(8) D 以上结论都不对32、设有一个递归算法如下int x (int n) if (n递归表纯表线性表 B 递归表线性表再入表纯表 C 递归表再入表纯表线性表 D递归表再入表线性表纯表37、某二叉树的前

11、序和后序序列正好相反，则该二叉树一定是（B）的二叉树。A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子38、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则( A )A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1 39、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ）A 24 B 73 C 48 D 5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（A）。A da1+(I-1)*m B d

12、a1+I*m C da1-I*m D da1+(I+1)*m41、34 具有35个结点的完全二叉树的深度为( A )A 5 B 6 C 7 D 842、对线性表进行折半搜索时，要求线性表必须（ C ）A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储 C 以数组方式存储且结点按关键码有序排列 D以链接方式存储43、顺序搜索算法适合于存储结构为（ B ）的线性表。A 散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ）A O（n2） B O（n log2n） C O（log2n） D O（n）45、对于

13、一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( A )A n B n+1 C n-1 D n+e46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ）。A 求关键路径的方法 B 求最短路径的Dijkstra方法 C 深度优先遍历算法 D 广度优先遍历算法47、在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为( A )A 1 B 2 C 9 D 1048、对包含n 个元素的散列表进行搜索，平均搜索长度为（ C ）A O（log2n） B O（n）C 不直接依赖于n D 上述都不对二、 填空题（）1、数据的逻辑结构被分为集合结构、线性结构、树

14、形结构、图形结构 四种2、数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构 四种3、一种抽象数据类型包括（数据 ）和（操作 ）两个部分。4、 设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配） 5、 栈、队列逻辑上都是（线性存储）结构。6、 线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。9、设目标串T=”abccdcdc

15、cbaa”,模式P=”cdcc”则第（6）次匹配成功。10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组Amn,若采用按行优先存放的方式，则任一数组元素Aij相对于A00的地址为（ n*i+j）。11、向一个顺序栈插入一个元素时，首先使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写 ）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。12、在一个循环队列Q中，判断队空的条件为（Q.front= =Q.rear）, 判断队满的条件为（ (Q.rear+1)%MaxSize= =

16、q.front ）13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（ n-1 ）。14、一棵高度为5的满二叉树中的结点数为（ 63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a0中，其余类推，则ai元素的左子女结点为（ 2*i+1），右子女结点为（ 2*i+2 ），双亲结点（i=1）为（(i-1)/2 ）.16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。17、已知具有n个元素的一维数组采用顺序存储结构，每个元

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

18、树的第7有10个叶子结点，则整个二叉树的结点数最多是（235）23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（），判定树中前层的结点数为（），最后一层的结点数为（）。25、在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。在一个具有n个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n个顶点的有向完全图中，包含有（ n(n-1) ）条边。26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和（n-1）。27、设线性表中元素的类型是实型，其首

19、地址为1024，则线性表中第6个元素的存储位置是( 1044)。28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序）。29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n）31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。32、处理冲突的三种方法，分别为(线性探测)、（ 随机探测 ）、（ 链地址法）。33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间

20、复杂度为（ （n2） ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（elog2e） ）34、快速排序在平均情况下的时间复杂度为（nlog2n），在最坏情况下的时间复杂度为（n2）；快速排序在平均情况下的空间复杂度为（log2n），在最坏情况下的空间复杂度为（n）。35、假定一组记录的排序码为（，），对其进行归并排序的过程中，第二趟排序后的结果是（）36、假定一组记录的排序码为（，），对其进行快速排序的第一次划分的结果是（）。37、一个结点的子树的（ 个数 ）称为该结点的度。度为（ 零 ）的结点称为叶结点或终端结点。度不为（ 零 ）的结点称为分支结点或非终端结点。树中各结点度的（ 最大

21、值 ）称为树的度。38、设Ki=Kj (1=i=n, 1=j=n,ji)且在排序前的序列中Ri领先于Rj (i1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。6、 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:(1)

22、各层的结点个数是多少?(2) 编号为i的结点的父结点(若存在)的编号是多少?(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?(5) 若结点个数为 n, 则高度h是n 的什么函数关系?答案：（1）各层的结点个数是ki (i=0,1,2,.,h)（2）编号为i的结点的父结点(若存在)的编号是 (i+k-2)/k（3）编号为i的结点的第m个孩子结点(若存在)的编号是(i-1)*k+m+1（4）当(i-1)%k0时有右兄弟， 右兄弟的编号为 i+1（5）若结点个数为 n ，则高度h和n 的关系为：h=logk(n*(

23、k-1)+1)-1 (n=0时h=-1)7、 写出下列中缀表达式的后缀形式：(1) A* - B + C(2) (A + B) * D + E / (F + A * D) + C(3) A & B| ! (E F)注：按C+的优先级)(4) !(A & !( (B D) ) )|(C !| (4)ABC|!&!CE1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个

24、分支结点。16、 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树, 其最大高度是多少? 最小高度是多少?答案：设高度为h(空树的高度为-1)的AVL树的最少结点为Nh，则Nh = Fh+3 -1。Fh 是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3/2*log2(n+1),最小高度为log2(n+1) -1。17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和

25、搜索不成功的平均搜索长度。509154677017275170503094553897512612765908答案：折半搜索时的判定树为： ASLSUCC=1/14（1+2*2+3*4+4*7）=45/14ASLUNSUCC=1/15（3*1+4*14）=59/1518、试对下图所示的AOE网络(1) 这个工程最早可能在什么时间结束。(2) 求每个事件的最早开始时间Vei和最迟开始时间Vli。(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。答案：按拓朴有序的顺序计算各个顶点的最早可

26、能开始时间Ve和最迟允许开始时间Vl，然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l,根据l-e是否等于0来确定关键活动，从而确定关键路径。Ve01915293843Vl01915373843e00151919152938L170152719273738l-e1700801280此工程最早完成时间为43，关键路径为19、已知有五个待排序的记录，其关键字分别为：256，301，751，129，937,863，742，694，076，438请用快速排序的方法将它们从小到大排列。答案：第一次排序：（076，129），256，（751，937，863，742，694，301，439）第二次

27、排序：076，129，256，（438，301，694，742），751，（863，937）第三次排序：076，129，256，301，438，（694，742），751，（863，937）第四次排序：076，129，256，301，438，694，742，751，（863，937）第五次排序：076，129，256，301，438，694，742，751，863，937 20、设有150个记录要存储到散列表中, 并利用线性探查法解决冲突, 要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ (设a是散列表的装载因子，则有ASLsucc = ( 1+1/ (1-a) )/2)。

28、答案：已知要存储的记录数为n=150,查找成功的平均查找长度为ASLsucc 2，则有：ASLsucc =1/2（1+1/（1-a）2 解得 a2/3 ，又有：a=n/m=150/m两式联立得：150/m2/3,解得：m225.所以散列表需要设计225个单位。五、算法分析题1、给出下列递归过程的执行结果 void unknown ( int w ) if ( w ) unknown ( w-1 ); for ( int i = 1; i = w; i+ ) cout w ; cout endl; 调用语句为 unknown (4)。 答案：(1)1 2 23 3 3 4 4 4 4 2、给出递

29、归过程的执行结果 void unknown ( int n ) cout n % 10 ; if ( int ( n / 10 ) ) unknown ( int ( n / 10 ) ); 调用语句为unknown ( 582 )。答案： 2853、给出递归过程的执行结果int unknown ( int m ) int value; if ( ! m ) value = 3; else value = unknown ( m-1 ) + 5; return value;执行语句为 cout unknown (3)。答案： 18 4、 设有一个二维数组Amn，假设A00存放位置在644（10

30、），A22存放位置在676（10），每个元素占一个空间，问A33（10）存放在什么位置？脚注（10）表示用10进制表示。答案：设数组元素Aij存放在起始地址为Loc(i,j)的存储单元中。 因为：Loc(2,2)= Loc(0,0)+2*n+2=644+2*n+2=676 所以：n=(676-2-644)/2=15 所以：Loc(3,3)= Loc(0,0)+3*15+3=644+45+3=6925、设单链表结构为 struct ListNode int data ; ListNode * link ; ;下面的程序是以单链表为存储结构, 实现二路归并排序的算法, 要求链表不另外占用存储空间,

31、 排序过程中不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。在初始状态下, 所有待排序记录链接在一个以r为头指针的单链表中。例如, 在算法实现时，利用了一个队列做为辅助存储, 存储各有序链表构成的归并段的链头指针。初始时, 各初始归并段为只有一个结点的有序链表。队列的数据类型为Queue, 其可直接使用的相关操作有n 置空队列操作：makeEmpty ( ); n 将指针x加入到队列的队尾操作：EnQueue ( ListNode * x ); n 退出队头元素, 其值由函数返回的操作：ListNode *DlQueue ( );n 判队列空否的函数, 空则返

32、回1, 不空则返回0：int IsEmpty( )。 解决方法提示： 程序首先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头 指针存放在一个指针队列中。 当队列不空时, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头指针存放到队列中。 如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序子链表即为所求。在算法实现时有 6 处语句缺失，请阅读程序后补上。(1) 两路归并算法void merge ( ListNode * ha, ListNode * hb, ListNode *& hc ) ListNode *pa, *pb, *pc ; i

33、f ( hadata = hbdata ) hc = ha; pa = halink; pb = hb; else hc = hb; pb = hblink; pa = ha ; pc = hc; while ( pa & pb ) if ( padata = pbdata) pclink = pa; pc = pa; pa = palink; else pclink = pb; pc = pb; pb = pblink; if ( pa ) pclink = pa; else pclink = pb; ;(2) 归并排序主程序void mergesort ( ListNode * r ) ListNode * s, t; Queue Q ; if ( ! r ) return;s = r;