数据结构综合题库.docx

《数据结构综合题库.docx》由会员分享，可在线阅读，更多相关《数据结构综合题库.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 判断题()1.数据的逻辑结构与数据元素本身的内容和形式无关。()2.线性表的逻辑顺序与物理顺序总是一致的。()3.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一 定是该子树的中序遍历结果序列的最后一个结点。()4.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索 树都是相同的。()5.最优二叉搜索树的任何子树都是最优二叉搜索树。()6.在二叉搜索树上插入新结点时，不必挪移其它结点，仅需改动某个结点的指针，使它 由空变为非空即可。()7.有n (nl)个顶点的有向强连通图至少有n条边。()8.连通分量是无向图中的极小连通子图。()9.二叉

2、树中任何一个结点的度都是2。()10.单链表从任何一个结点出发，都能访问到所有结点。()1L线性表的长度是线性表占用的存储空间的大小。()12.队列只能采用链式存储方式。()13.用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。()14.由二叉树的先序序列和中序序列能惟一确定一棵二叉树。()15.图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数。()16.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。()17.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三 个方面。()18.线性表中的每一个结点最多惟独一个前驱和一个后继。()

3、19.二叉排序树查找总比顺序查找速度快。()20.对具有n个顶点的连通图进行深度优先遍历，所得顶点序列是惟一的。()21 .线性表中各个数据元素的类型必须是相同的。()22.R树是一种特殊的二叉树。()23.栈可视为一种特殊的线性表。()24.快速排序总是比其它排序方法快。()25.使用双向链表存储数据，可以提高查找(定位运算)的速度。()26.最小生成树是边数至少的生成树。A1n中查找值为k的元素，若找到则输出其位置i (l二i二n),否则输出0作为标志；2)找 出数组A1n中元素的最大值和次最大值(本小题以数组元素的比较为标准操作)。20写出下面二叉树的中序遍历结果。21若栈为S,且已知p

4、op(S) = A,试说明下列等式是否成立：Pop (push(S, A) = push (S,pop(S)； 22对于下图，从顶点1出发，分别按深度优先搜索和广度优先搜索方法遍历，写出相应的顶点 序列。23.已知下图所示双向循环链表L=(a, b, c, d) o请写出将该表转换为L=(b, a, c, d)的简24.对于给定字符串，1234+ - X/15678,试写出删除串中的+ - X/的算法。25算法与程序有何不同？，为何要引出算法概念？，如何评价算法的时间、空间复杂性及好坏？。26已知线性表(a , a , a )中的元素值按递增有序罗列，选用向量结构存放。试编写算 12n法删除线

5、性表中值介于C与d (c = d)之间的元素。27.说明栈和队列与线性表的异同点。28、给定一组元素值17、28、54、30、27、94、15、21、83、40,用这一组元素值构造一棵哈 夫曼树。29如果队列中不设表头结点，如图所示，并令front = rear = null表示队列空，试写出实现队 列的三个基本操作（入队、出队、判空）。front30、设一个有叙文件的关键字为2, 5, 8, 11, 13, 17, 25, 36, 47, 55, 60, 63, 65, 67, 76, 84,当用折半查找算法查找关键字55时，试决定关键字的比较次数。31、抽象数据类型（ADT）与面向对象方法

6、有何关系？使用ADT的优点有哪些？32、给出一组关键字12, 2, 16, 30, 8, 4, 10, 20, 6, 18。写出按下上升排序时，用汽泡 排序方法排序的每一趟排序结束状态。33、试写出一个将已知字符串所有字符倒过来重新罗列的算法。例如ABCDEF改为FEDCBA。34、试描述数据结构的概念与程序设计语言中数据类型概念的区别。35、试设计算法，求循环链表中结点的个数，并删除表中的第一个结点a。二、单选题1向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要挪移（）个元素。A. 8B. 63.5C. 63D. 72设有一个二维数组假设A0 0存放位置在644, A2

7、 2存放位置在676,每个元素占一个空间，则A在（）位置，。）表明常10进数表示。（10）A. 692B. 626C. 709 D. 724（10）（10）（10）（10）3 N个顶点的连通图至少有（）条边。D. 0A. N-lB. NC. N+14下面程序的时间复杂度为()。for(int i=0; ilink=p-link; p-link =s;B. q-link=s; s-link =p;C. p-link=s-link; s-link =q;D. p-link=s; s-link =q;6 栈的插入和删除操作在（）进行。A.栈顶B.栈底C.任意位置D.指定位置7若让元素1, 2, 3挨

8、次进栈，则出栈次序不可能浮现哪种情况（）。A. 3, 2, 1B.8广义表A (a),则表尾为(A. aB.()2, 1, 3)OC. 3, 1, 2C.空表D.D. 1, 3, 2(a)）OD.按层次遍历9采用邻接表存储的图的深度优先遍历算法类似于二叉树的（A.中序遍历B.前序遍历C.后序遍历 10每次从无序表中挑选出一个最小或者最大元素，把它交换到有序表的一端，此种排序方法叫 做（）序。A.插入B.选择 C.交换D.外排序11 . 一个顺序表有255个对象，采用顺序搜索查找，平均数据比较次数为（）。A. 128B. 127C. 126D. 25512 .含5个结点（元素值均不相同）的二叉树

9、搜索树有（）种。A. 54B. 42C. 36I）. 6513 .数据结构中，与所使用的计算机无关的是数据的结构。（A）存储；（B）物理； （C）逻辑； （D）物理和存储；14 .在链表中进行操作比在顺序表中进行操作效率高。（A）顺序查找； （B）折半查找；（C）分块查找；（D）插入；15 .树结构最适合于用来表示。（A）元素间具有分支和层次关系的数据；（B）无序数据；（C）有序数据；（D）元素间没有关联的数据；16 .借助于栈，输入A、B、C、D四个元素，则不可能浮现的输出序列为 o(A) ABCD； (B) CABD； (C) DCBA； (D) BACD；17 .从理论上讲，将数据以结构

10、存放，则查找一个数据所用时间不依赖于数据个数N。A二叉查找树；(B)链表； (C)二叉树；(D)散列表；18 .头指针为L的单循环链表，指针p所指结点为尾结点的条件为。(A) pf next = NULL； (B) pf next = L； (C) p = L； (D) p = NULL；19直接选择排序的时间复杂度为 (n为元素的个数)。A 0(n) ；(B) O(log n) ；(C) 0(n log n) ；(D) 0(n2)o2220散列存储中，碰撞(或者称冲突)指的是 o(A)两个元素具有相同序号； (B)不同的关键字对应于相同的存储地址；(C)两个记录的关键字相同；(D)数据元素过

11、多；三、填空题1 .算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应具有输入、输 出、有穷性和可执行性等特性。2 .当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的 。3 .在一棵度为3的树中，度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是4 .当用长度为n的数组顺序存储一个栈时，若用top=n表示栈空，则表示栈满的条件为5 .对序列(49, 38, 65, 97, 76, 27, 13, 50)采用快速排序法进行排序，以序列的第一个元素为基准 元素得到的划分结果是 o6 .对于一棵具有n个结点的树，该树中所有结点的度数之和为 o7 .

12、请指出在顺序表5、11、23、35、51、64、72、85、88、90、98中，用折半查找关键码30 需做 次关键码比较。8 .若线性表采用顺序存储结构，每一个元素占用4个存储单元，第一个元素的存储地址为100, 则第12个元素的存储地址是 o9 .在一个长度为n的顺序表中，向第i个元素(1W iW n+1)之前插入一个新元素时，需要 向后挪移 个元素。10 .设有两个串p和q,求q在p中首次浮现的位置的运算称作。11 .判定一个循环队列QU(最多元素为m)为满队列的条件是 o12 .在一个无向图的邻接表中，若表结点的个数是明则图中边的条数是 条。13 .对于一个具有n个顶点的图，若采用邻接矩

13、阵表示，则矩阵大小为。14 .有N个顶点的无向连通图至少有 条边。15 .在下图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们挨次是 和HD41H 11 K I -II 1AlP “ b16 .设根结点的层数为0,定义树的高度为树中层数最大的结点的层数。则高度为k的二叉树具有 的结点数目，至少为，最多为 o17 .单链表中指针p所指结点惟独一个后继结点的条件是 o18 .深度为k的满二叉树有个结点。19 .设s = I AM A STUDENT ，t =GOOD WORKER ，CONCAT(Substr(s, 6, 2), t)2

14、0 .文件在外存储器组织结构的三种形式分别为、和 o21 .对广义表LS=(a, (b, c),( ), d),(e)进行HEAD和TAIL运算的结果分别是、O22二维数组AL.20, L. 10按行优先顺序存储，每一个元素占4个单元，月51, 1的地址是1000, 则A18, 9的存储地址是 o23 .深度为k的彻底二叉树至少有个结点，至多有仝结点。24 ISAM文件由、柱面索引、磁道索引和主文件组成。25在单链表中，将指针p所指结点插到指针s所指结点后面的两步主要操作语句为，O26 .设二维数组AL.20, 1.10按行优先存储，每一个元素占4个单元，Al, 1的地址是100, 则A5,

15、5的地址是.27 .散列既是一种方式，又是一种查找方法。28抽象数据类型定叉甬部份组成。四、程序阅读填空1 .在顺序表中第i个位置插入新元素Xtemplate int SeqList:Insert (Type & x, int i) if (ilast+l | | last=MaxSize-l) return 0; 插入不成功 else last+;for( ；ji；j)datai = x;return 1;插入成功)2 .直接选择排序的算法template void SelectSort(datalist & list) for(int i=0; ilist.CurrentSize-1; i

16、+); template viod SelectExchange(datalist & list, const int i) int k = i;for(int j=i + l;j list.CurrentSize;j+)if(list. Vectorj. getKey()list. Vectork. getKey()； 当前具有最小关键码的对象if (k! = i) Swap (list. Vector i, list. Vector k); 交换)3、删去链表中除表头结点外的所有其他结点template void List : : MakeEmpty ( ) ListNode *q;whi

17、le (firstf link!二NULL) /将表头结点后第一个结点从链中摘下 delete q;/释放它)last二first;修改表尾指针) 4、基于有序顺序表的折半搜索递归算法(Element为有序顺序表) template int orderedList :BinarySearch(const Type & x, const int low, const int high)const (int mid =-1;if ( low = high ) if ( Elementmid. getKey( ) x )mid = BinarySearch ( x, low, mid -1 );)r

18、eturn mid;5、在顺序表中第i个位置插入新元素x o int insert(sqlist *L, datatype x, inti) intj;if (L-n=maxsize) coutw”表满，不能插入！(上溢)n; return -1 ； if()coutw”非法插入位置！ n”; return 0;for(j=L-n;j=i;j-)L-dataj=L-dataj-1;节点后移；/插入xL-n+;修改表长Return 1;插入成功)6、直接选择排序的算法void SelectSort( list R, intn ) intij, k;for (i=1; i=n-1 ;i+) /n-

19、1 趟排序for(j=i+1；jv=n,j+)/在当前无序区中找键值最小的记录Rkif(Rj.key(54 .上图所示为一有向图，请给出该图的下述要求：(1)给出每一个顶点的入度和出度；(2)以结点3为起始结点，分别画出该图的一个深度优先生成树和一个宽度优先生成树;(3)给出该图的邻接矩阵；(4)给出该图的邻接表；5 .对于如上图所示的有向图，试写出:(1)从顶点出发进行深度优先搜索所得到的深度优先生成树;(2)从顶点出发进行广度优先搜索所得到的广度优先生成树;6 .已知二叉树的先序、中序和后序序列分别如下，但其中有一些已含糊不清，试构造出该二叉 树。先序序列 _BC_EF_中序序列 BDE_

20、 AG_H后序序列 _DC_GH_A7 .分析下列两个程序段的运行时间(时间复杂度)。void mystery (intn) inti J, k;for (i =1; i n; i+)for (j = i+1;j v= n;j+)for (k= 1; k=j; k+);)void odd (intn) intij, x = 0, y = 0;for (i =1; i = n; i+)if odd(i) for(j = i;j = n;j+)x+;for(j = 1;j = i;j+) y+;)9.有一组数据：25, 50, 70, 21, 4, 18, 100, 43, 7, 12。现采用汽泡

21、排序算法进行排序，写 出每趟排序的结果，并标明第一趟数据的挪移情况。10 .数据结构与软件的关系是什么？。解决实际问题时，选取或者设计数据结构的原则是什么？。11 .说明下列概念是否正确：线性表在物理存储空间中也一定是连续的；链表的物理存储 结构具有同链表一样的顺序；链表的删除算法很简单，因为当删去链表中某个结点后，计算 机会自动地将后继的各个单元向前挪移。使用双向链表存储数据，可以提高查找(定位)的速 度。12 .写一个算法，借助栈将一个单链表倒置(提示：可以使用栈的基本运算)。也即，将下面的单链表:13描述以下概念的区别：头指针、头结点、首元结点。头指针变量和头结点的作用？。并比较顺 序存

22、储结构和链式存储结构的优缺点。14哪些链表可以仅由一个尾指针来惟一确定。即从尾指针出发能访问到链表上任何一个结点。15设n为正整数，试确定下列三段程序中带下划线语句的频度。(a) int i =1, k = 0； while (i = n - 1) k = k +10*i: i = i+1; (b) int i =1, j = 0； while (i+j) i)i+:else i+;(c) int i =1, k = 0； while ( - i = n - 1) k = k+10*i: i+；)16已知s=(xyz)+*， t=(x+z)*y，试利用联接、求子串和置换等串的基本运算，将s 转化为t。17有如下12个整数：23,37, 7, 79, 29, 43, 73, 19, 31, 61, 23, 47,按气泡排序方法将这组整数排序，分别写出每遍处理后的数列。18逻辑结构与存储结构是什么关系？，有何区别？。19设计求解下列问题的C+语言算法，并分析其最坏情况时间复杂度及其数量级：1)在数组