数据结构习题C++版

1、、选择题(D ) 1、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用 _ 存储方式节省时间：A、单链表 B 、双链表 C 、单循环链表 D 、顺序表。(A)2、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右 依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编 号为。A、98 B 、99 C 、50D、48(A)3、数组A1.5,1.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A5,5的地址是。A、1140 B 、1145 C 、1120 D 、1125(C ) 4、对二叉树从1开始编号，要求每个结点的编号大于其左

2、右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用实现编号。A、先序遍历B、中序遍历C、后序遍历 D、从根开始进行层次遍历(B ) 5、栈和队列都是。A、顺序存储的线性结构B、限制存取点的线性结构C、链式存储的线性结构D、限制存取点的非线性结构(C ) 6、若二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字 有序，则该二叉树是 。A、二叉排序树 B 、哈夫曼树 C 、堆 D 、AVI树(C)7、在顺序表(3,6,8,10,12,15,16,18,21,25,30 )中，用折半法查找关 键码值11,所需的关键码比较次数为 。A、2 B 、3 C 、4 D

3、、5(C ) 8、一组记录的关键字为(46,79,56,38,40,84),利用快速排序的方法，以第一记录为基准得到的一次划分结果为。A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38,46,56,79,84 D、40,38,46,84,56,79(D ) 9、对包含n个元素的哈希表进行查找，平均查找长度为 。A、O(log2n) B 、O(n) C 、0(nlog2n)D 、不直接依赖于n(C ) 10、一个有n个顶点的无向图最多有 边。11、有一个100*90的稀疏矩阵，非0元素有10个,设每个整型数占2字节, 则用三元组表示该矩阵时，所需的字节数是

4、A. 60 B. 66C.18000D. 3312、有关二叉树下列说法正确的是都为2A.二叉树的度为2.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度13、二叉树的第I层上最多含有结点数为(2 1-1 -12 1-1.21 -114、n个结点的完全有向图含有边的数目A . n*n B . n (n +1)Cn/2.n* (n I )15、一个有n个结点的图，最少有 个连通分量。个连通分量,最多有.n-116、一个有向无环图的拓扑排序序列()是唯一的。A. 一定A.从源点到汇点的最长路径从源点到汇点的最短路径.不一定17、关键路径是事件结点网络中最短回路

5、B,18、设一个栈的输入序列是A, 歹寸不可能是。A . A, B, C, D B . D, C,B,C,D,则借助一个栈所得到的输出序B,C . A, C, D, B D . D, A,19、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号最大的非叶结点的编号 为A、48B 、49 C 、50 D 、51、填空题1、已知L是带表头结点的非空单链表，且P结点既不是头结点，也不是尾结点,请填写删除P结点直接后继结点的主要语句序列(可利用辅助结点变量 Q)：Q=P->NEXT 、 P->NEXT=P->NEXT->NE

6、XT、free(Q) 。2、广义表心(),(a,(b,c) ) ,d)的表尾 Gettail(A) 为：(a,(b,c),d)。3、对任意一棵二叉树，若终端结点数为nO,则度为2的结点数为：_n0-1。4、 在顺序表(即顺序存储结构的线性表)中插入一个元素，需要平均移动n/25、已知一棵二叉树的前序序列为 ABDFC,中序序列为DFBAC,则后序序列为：FDBECA 。6通常是以算法执行所耗费的时间 和所占用的 空间来判断一个算法的优劣。7、已知一个3行、4列的二维数组A (各维下标均从1开始)，如果按“以列为主” 的顺序存储，则排在第8个位置的元素是： A23。三、 判断题：正确的在()中填

7、入，错误的填入“X” 0(x ) 1、线性表的逻辑顺序与物理顺序总是一致的。(X ) 2、线性表的顺序存储表示优于链式存储表示。(V ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续 可不连续。(X ) 4、二维数组是其数组元素为线性表的线性表。(V ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。(x ) 6、如果一个二叉树中没有度为1的结点，则必为满二叉树。(X ) 7、内部排序是指排序过程在内存中进行的排序。(V ) &在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。(X ) 9、拓扑排序是按AOE网中每个结点事件的最早发行时间对结点进行排

8、 序。(X ) 10、具有三个结点的二叉树有三种。四、分析题1、将关键码45, 24，53，12, 28, 90依次插入到一棵初始为空的二叉排序树 中，画出插完所有关键码后的二叉排序树。解:2、某二叉树的结点数据采用顺序存储表示如下：0123456789101112 1314 15 1617 18 19HIJACDBFGY（1）试画出此二叉树的图形表示。（2）写出结点D的双亲结点及左、右子女。解：(1)3、已知无向图如下图1所示， 给出图的邻接表。从 A开始，给出一棵广 度优先生成树。A图14、已知一棵树如图2所示，要求将该树转化为二叉树3题解答4题解答ABCDEFGIHJK5、已知一个序列a

9、bcdefghi,其字符对应的权分别为:字符abcdefghi权51020123048225画出对应的哈夫曼树生成过程，并给出每个字符的哈夫曼编码解：字符abcdefghi编码000011011110011000011110000010016、有如图4所示的带权图，使用普里姆算法来求最小生成树，将边的加入顺序填入下表中。序号123456789边d-e解答:序号12345678边d-ee-he-ch-ff-gh-ic-bb-a五、设计题1、 假设称正读和反读都相同的字符序列为“回文”，例如， abba'和abcba' 是回文，abcde'和 ababab'则不是回

10、文。试写一个算法判别读入的一个 以为结束符的字符序列是否是“回文”。2、 若矩阵Amxn中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Amxn,试编写求出矩阵中所有马鞍点的算法。解答：1、int Palindrome_Test()/判别输入的字符串是否回文序列，是则返回1,否则返回0 InitStack(S);InitQueue(Q);while(c=getchar()!='')Push(S,c);EnQueue(Q,c); /同/ 时使用栈和队列两种结构while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK;/Palindrome_Test2、void Get_Saddle(int Amn)/ 求矩阵 A 中的马鞍点for(i=0;i<m;i+)for(min=Ai0,j=0;j<n;j+)if(Aij<min) min=Aij; / 求一行中的最小值for(j=0;j&l