数据结构常见题型整合

1、数据结构常见题型整合 1设栈的输入序列是 1 , 2, 3, 4,则()不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， 2、 在一个链队列中，若f，r分别为队首、队尾指针，则插入 s所指结点的操作为() (A) f-next=c ； f=s(B) r-next=s； r=s (C) s-next=r ； r=s (D) s-next=f； f=s 3、 顺序存储的栈和队列中已经各有N个结点，要删除一个结点分别需要移动数据()次 和( )次。 A. N/2 , NB. N , N/2C. 0 , ND. N , 0 4、设有三

2、个元素 X,Y,Z顺序进栈(进的过程中允许出栈)，下列得不到的出栈排列是 () A. XYZ B. YZXC. ZXYD. ZYX 5、 一个递归算法必须包括()。 A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分 6、 如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作(其中MAXQSIZE 表示队列的容量)()： A. if (Q.rear = Q.front) B. if (Q.rear = (Q.front + MAXQSIZE) C. if (Q.rear = (Q.front + 1) % MAXQSIZE) D. if (Q.front = (Q

3、.rear + 1) % MAXQSIZE) 7、假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中 的元素个数为（）。 A. （rear-front+m）%mB . rear-front+1 C. （front-rear+m）%mD . （rear-front）%m 8、若用一个大小为 6的数组来实现循环队列，且当前 rear和front的值分别为0和3,当 从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（） A. 1 和 5B. 2 和 4 C. 4 和 2 D. 5 和 1 9、利用栈进行十进制数1348转换成八进制数，则入

4、栈的数依次是（）。 A. 1 , 3,4,8 B. 8,4,3 , 1 C. 2,5,0,4D. 4,0 , 5,2 10、最大容量为n的循环队列, 队尾指针是rear，队头是front，则队空的条件是 A. (rear+1) MOD n=fro nt C. rear+1=front B. rear=fr ont D. (rear-l) MOD n=front C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 11、栈和队列的共同点是（） A.都是先进先出B. 都是先进后出 C.只允许在端点处插入和删除元素D.没有共同点 1、栈是操作受限（或限定仅在表尾进行插入和删除操作

5、）的线性表，其运算遵循 后进先出的原则。 3、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺 序，相应的S和X的操作串为_SX SSX SXX_。 4、表达式求值是栈应用的一个典型例子。 线性表 空。当 5、栈和队列在本质上都是同一种基本数据结构的特例，这种基本的数据结构就是 6、在作进栈运算时，应先判别栈是否.满，在作退栈运算时应先判别栈是否 栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为n 。 12、在二叉树的第I层（I 1）上最多含有结点数为（） A. 2 B. 2 1-1 -1 C. 2 1-1 D. 21 -1 13、深度为6的二叉

6、树最多有（）个结点 A . 64B.63C.32D.31 14、一棵树高为K的完全二叉树至少有（）个结点 A.2k - 1B.2k-1 - 1C.2 k-1D.2 k 15、有关二叉树下列说法正确的是（ A.二叉树的度为2 ） B. 一棵二叉树的度可以小于 2 A. 2n B. n I C. n + I D. n 17、线性表和树的结构区别在于（） A.前驱数量不同，后继数量相同B.前驱数量相同，后继数量不同 C. 前驱和后继的数量都相同D.前驱和后继的数量都不同 18、 已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为 ABC*+DE/-，则其前缀形式为 （） A. -A+B*C/

7、DE B. -A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE 19、设有一表示算术表达式的二叉树（见下图） 它所表示的算术表达式是（） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+( F-G) ) D. A*B+C/D*E+F-G 20、一棵具有n个结点的完全二叉树的树高度（深度）（符号x表示取不大于x的最大整 数）是（） A. log 2 n B. log 2 n 1 C. log 2( n 1) D. log 2 n 1 8、具有256个结点的完全二叉树的深度为9 21、利用二叉链表存储树，则

8、根结点的右指针是（ A.指向最左孩子 B.指向最右孩子 C .空 D .非空 22、已知一棵二叉树的前序遍历结果为ABCDEF中序遍历结果为 CBAEDF则后序遍历的结 果为（）。 A. CBEFDA B . FEDCBA C . CBEDFA D .不定 23、若前序遍历二叉树的结果为序列A、B C,则有棵不同的二叉树可以得到这 一结果。 A. 3B. 4 C. 5 D. 6 24、线索二叉树是一种（）结构。 A.逻辑 B .逻辑和存储C .物理 D .线性 二、填空题 7、对于任意一棵二叉树，如果其叶子结点数为 N0,度为1的结点数为N1,度为2的结点数 为 N2,贝y N0=_ N2 +

9、 1 。 9、一个深度为4的二叉树，其结点至少有 4 个，至多有15 个: 10、深度为H的完全二叉树至少有 _ 2H-1_个结点；至多有 2H-1 _个结点；H和结点总数N 之间的关系是 H=? log 2N? +1。 11、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，N个结点的二叉树共有_2N_个指针域，其中 有_N-1_个指针域是 存放了地址，有 _N+1_个指针是空指针。 12、 设一棵赫夫曼树有 6个叶子结点，权值分别为3、4、7、14、15、20，则根结点的权值 是_63 13、对一棵完全二叉树，设一个结点的编号为 i，若它的

10、左孩子结点存在，则其编号为 2j_;若右孩子结点存在，则其编号为2i+1;而双亲结点的编号为 _ i/2 _ 。 14、 赫夫曼树是带权路径长度最小的 二叉树，又称最优二叉树 ，路径上权值较大的结点 离根较近。 15、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。 typedef struct node int data; struct node *lchild; _ struct node *rchild .; BiTNode, *BiTree; void createBitree(BiTree if(ch=#) T=NULL; else T=( BiTNode *)mal

11、loc(sizeof(BiTNode); T-data=ch; createBitree(T-lchild) ; createBitree(T-rchild); 16、二叉树由_根结点, 左子树_, _右子树三个基本单元组成。 17、 树的链表存储结构常用的有三种，其中，双亲 表示法一一以一组连续空间存储树的结 点，在每个结点中设一个指示器指示双亲结点的位置。孩子 表示法一一每个结点的孩子以 单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存 储结构存储。孩子兄弟表示法一一以二叉链表作为树的存储结构，链表中的结点的两个指 针分别指向该结点的第一个孩子结点和下一个兄

12、弟结点。/P135-136 18、 利用树的孩子兄弟表示法存储，可以将一棵树转换为二叉树一。 19、 在二叉树中，指针p所指结点为叶子结点的条件是_ p-lchild=NULL 31、一个含有n个顶点的非连通图，则(): A.它的边一定不大于 n-1B.它的边一定不大于n C.它的边一定小于n-1D.它的边一定大于0 32、要连通具有n个顶点的有向图，至少需要()条边。 A. n-1B . nC . n+lD. 2n 33、下列说法不正确的是()。 A.图的遍历是从给定的源点出发每一个顶点仅被访问一次 B. 遍历的基本算法有两种：深度遍历和广度遍历 C. 图的深度遍历不适用于有向图 D. 图的

13、深度遍历是一个递归过程 34、无向图 G=(V,E),其中： ，对该图进行深 V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 度优先遍历，得到的顶点序列正确的是()。 A. a,b,e,c,d,f B .a,c,f,e,b,d C a,e,b,c,f,d D . a,e,d,f,c,b 35、若一个连通图有 n个顶点，则它的生成树有()条边。 A. n B. n-1 C. n+1 D. n(n-1)/2 二、填空题 22、邻接多重表适于表示 _稀疏无向图，邻接表、逆邻接表和十字链表 适于表示稀疏有 向图。 23、设有向图的顶点

14、个数为n,则该图最多有n（n-1）条弧。 24、右图中顶点 D的出度是3 25、8层完全二叉树至少有128（第七层满，加第八层1个 ）_个结点，拥有 100个结点的 完全二叉树的最大层数为7 。 26、求图的最小生成树有两种算法：普里姆（Prim ）算法和克鲁斯卡尔 （Kruskal ）算法 其中，一克鲁斯卡尔算法适合于求边稀疏的稀疏图的最小生成树。普里姆算法适 用于求边稠密的网的最小生成树。 27、对于含n个顶点e条边的无向连通图，利用普里姆算法生成最小代价生成树其时间复杂 度为0(n2)利用克鲁斯卡尔算法生成最小代价生成树其时间复杂度为_ O(eloge) 28、 在无向图的 深度优先遍历

15、算法 中，DFS(从某个顶点出发深度优先遍历图的算法)被 调用了几次就说明该图有几个联通分量。 29、 一个有n个结点的图，最少有 1个连通分量，最多有 n个连通分量。 30、判断一个无向图是一棵树的条件是_有 n个顶点，n-1条边的无向连通图 31、有向图G的强连通分量是指 有向图的极大强连通子图 32、右图中的强连通分量的个数为3 个。 33、一个连通图的生成树 一个极小连通子图。 34、若用n表示图中顶点数目，则有 _ n(n-1)/2 _条边的无向图成为完全图。 35、已知一无向图 G=(V, E),其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b

16、,e) 现用某一种图遍历方法从顶点a开始遍历图，得到的序列为 abecd，则采用的是深度优先 _遍历方法。 36、为实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需队列 存放被访问的结点以实现遍历。 37、设无向图G有n个顶点，m条边。阅读下面用邻接表存储该图的算法。(设顶点值用1 n或0n-1编号)，并在画线处完成填空。 void CreatGraph (AdjList g) /建立有n个顶点和 m条边的无向图的邻接表存储结构 int n,m; sca nf(%d%d， for (i =1,i=n;i+)_/输入顶点信息，建立顶点向量 sca nf( gi.firstarc

17、 =n ull; for (k=1;kadjvex=j; p_n ext=gi.firstarc; gi.firstarc=p;/将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=i; p_n ext=gj.firstarc;gj.frstarc=p; 三、简答题 4、已知一个无向网的顶点集为a,b,c,d,e，其邻接矩阵如下所示 1 4 126 2 35 43 a b c d e (1) 画出该无向网图形； 写出相应的遍历序列。 (2) 根据邻接矩阵从顶点 a出发进行深度优先遍历和广度优先遍历, 答案: (1) 该无向网图形如下: 深度

18、优先序列为：a b c d e 广度优先序列为：a b d c e 36、适用于折半查找的表的存储方式及元素排列要求为 A.链接方式存储，元素无序 B.链接方式存储，元素有序 C.顺序方式存储，元素无序 D .顺序方式存储，元素有序 37、对有 A.1 , 18个元素的有序表 A作折半查找，则查找 A3 2, 3B.9, 5, 2, 3C.9, 5, 3 的比较序列的下标为（ D.9, 4, 2, 3 14个数据元素的有序表 R进行折半搜索，搜索到 过程中元素比较的顺序依次为（ 38对有 R3的关键字等于给定值，查找 A. R6, R2 ,R4, R3 C. R0, R1 ,R2, R3 B.

19、 R6, R4 ,R2, R3 D. R0, R13 ,R2, R3 39、对N个元素的表做顺序查找时，若查找每个元素的概率相同， A. （N+1） /2 B. N/2 C. N D. （1+N） 则平均查找长度为 *N /2 40、有一个长度为12的有序表，按二分查找法对该表进行查找, 下查找成功所需的平均比较次数为（ A . 35/12B.37/12C.39/12 在表内各元素等概率情况 ）。 D.43/12 41、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找, 前者比后者的查找速度（ 也可用顺序查找，但 A.必定快 B. 不一定 C.在大部分情况下要快 D. 取决于表递增还是

20、递减 42、设有序表的关键字序列为 当用二分查找法查找健值为 A.2 B. 3C. 4 1 , 4, 6, 10, 18, 35, 42, 53, 67, 71, 78, 84, 92, 99, 84的结点时，经()次比较后查找成功。 D.12 43、 在查找过程中，只完成查找操作，这种查找称为() A.静态查找B.动态查找C.内部查找D.外部查找 44、 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是() A. (100, 80, 90, 60, 120, 110, 130) B. ( 100, 120, 110, 130, 80, 60, 90) C. (100, 60

21、, 80, 90, 120, 110, 130) D. (100 , 80, 60 , 90, 120, 130, 110) 二、填空题 38、 对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找 失败，它们的平均查找长度是 _不同的，对于查找成功，他们的平均查找长度是 _相同的2 39、 执行顺序查找时，储存方式可以是顺序存储或链式存储，二分法查找时，要求线 性 表_顺序存储且有序_。 40、 在数据结构中一般采用 平均查找长度 衡量查找算法时间性能，而对于排序算法一班通过 统计记录的 比较次数和移动次数衡量排序算法的时间性能。 41、设查找表中有100个元素，如果

22、用二分法查找方法查找数据元素X则最多需要比较 7 次 就可以断定数据元素X是否在查找表中 42、 二叉查找树的查找效率与二叉树的树型有关，在呈单枝树时其查找效率最低。 43、 若表中元素个数为n,则顺序查找该表中的元素，若查找成功，则比较关键字的次数最 多为 丿一次，平均比较次数为(n +1)/2;若进行折半查找，则最大比较次数是 ?10g 2+1。 44、 给定一个主关键字，在长为 n的有序表中进行折半查找，则最多经过？ log 2n? +1次 比较即可确定该关键字是否在表中，至少经过1次比较即可确定该关键字在表中。 45、在顺序表(8,11,15,19,25,26,30,33,42,48,50 )中，用二分(折半)法查找关键码值 20,需做的关键码比较次数为_4_。 46、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次 为 _6,9,11,12。 47、己知有序表为(12,18,24,35,47,50,62,83,