数据结构选择题答案及相关知识点.doc

1、在一棵具有5层的满二叉树中结点总数为（ A ）。A) 31 B）32C）33 D）16(2n) - 1,N = 2k-1(N总结点数，k层数)2、串的逻辑结构与（ A ）的逻辑结构不相同。A）线性表 B）栈C）队列 D）集合串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。P713、下列序列中，执行第一趟快速排序后得到的序列是（A）。A）d,a,e,d,bfh,g B) c,e,a,dfh,g,bC) g,a,e,c,bfd,h D) a,b,c,d,fe,g,h左大右小4、n个顶点的强连通图至少有（ C ）条边。A）n B）n+1 C）n-1 D）n(n-1)单节点除外，so,-15、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（ A ）。A）p-next=p-next-next B）p=p-nextC）p=p-nexe-next D）p-next=p无限删除6、对下图V4的度为（ C ）。A）1 B）2 C）3 D）4 v1 v2 v3 v47、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。A）4 B）5C）6 D）7图1-7设度为0的结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，度为3的个数n3树中结点总数n0+ n1 + n2 + n3，所有边的数量为0 * n0 + 1 * n1 + 2 * n2 + 3 * n3树中结点比边多1个，合并这两个式子就可以得到：n0 = 1 + n2 + 2 * n38、在数据结构中，从逻辑上可以把数据结构分为（ C ）。 A）动态结构和静态结构 B）紧凑结构和非紧凑结构 C）线性结构和非线性结构 D）内部结构和外部结构 数据的逻辑结构分两大类： 线性结构 和 非线性结构 数据的存储方法有四种： 顺序存储方法 、 链接存储方法 、 索引存储方法和散列存储方法(hash存储)9、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。A）loc(A1)+i*c B）loc(A1)+(i-1)*cC）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c10、（ C ）在进行插入操作时，常产生假溢出现象。A）顺序栈 B）循环队列C）顺序队列 D）链队列循环队列产生是为了解决顺序队列的假溢出11、下列各种数据结构中属于线性结构的有（ A ）。A）栈 B) 二叉树C) 广义表 D) 图数据元素之间的关系称为结构：1.集合；2.线性结构；3.树形结构；4.图/网状结构12、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ B ）。A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法13、广义表head(a,b),(c,d)的运算结果为（ D ）。A）(a,b) B）(c,d)C）空表 D）（a,b）,(c,d)）14、 n个顶点的图的最小生成树必定（ D ），是不正确的描述。A）不唯一 B）权的总和唯一C）不含回路 D）有n条边15、采用链结构存储线性表时，其地址（ B ）。A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的16、队列的操作的原则是（ A ）。A）先进先出 B) 后进先出C) 只能进行插入 D) 只能进行删除U字走法，不是Y17、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n),Tn表示式中记号O表示（ A ）。A）一个数量级别 B）一个平均值C）一个最大值 D）一个均方值18、线性表的链接实现有利于（ A ）运算。A）插入 B）读元素C）查找 D）定位20、下面程序段的时间复杂度是( A )。 s =0; for( i =0; in; i+) for(j=0;jLchild=Null B) D-ltag=1C) D-Rchild=Null D) D-ltag=0L Tag0 lchild域指示节点的左孩子;1 lchild域指示节点的前驱R tag0 rchild域指示节点的左孩子;1 rchild域指示节点的前驱没有前趋结点并没有左子树就没有左孩子，通常没有头结点的情况下，中序遍历的第一个结点就满足条件。29、栈进行插入和删除操作的特点是（ A ）。A）LIFO B）FIFOC）FCFS D）HPFLIFO = “last in first out”30、与无向图相关的术语有（ C ）。A）强连通图 B）入度C）路径 D）弧32、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。A）上三角矩阵 B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵34、栈进行插入和删除操作的特点是（ A ）。A）LIFO B）FIFOC）FCFS D）HPF39、在循环队列中，若front与rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是( C )。 A）front=rear+1 B）rear=front+1 C）front=rear D）front=0 此时我们约定：少用一个元素，“队列头指针在队列尾指针的下一位置”作为队列呈“满”状态的标志。43、在有n个叶结点的哈夫曼树中其结点总数为：（ D ）。（A）不确定 （B）2 n （C）2 n + 1 （D）2 n 1无论哈夫曼树是几叉，其特点是一致的（假设为m叉），即树中只存在度为0的结点（即叶结点）和度为m的结点。不妨设度为0的结点个数为x，度为m的结点个数为y，则存在一个等式x+y=my+1，即x=(m-1)y+1，x+y是树的总结点个数。就这道题来说，假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。44、（ C ）在进行插入操作时，常产生假溢出现象。A）顺序栈 B）循环队列C）顺序队列 D）链队列1-10这个要记一下,重复就重复48、某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为：( C )A）3 B）2 C）4 D）5后序最后一个为根节点49、在数据结构中假定在一棵二叉树中，度为2的结点数为15个，度为1的结点数为32个，则叶子结点数为（ B ）个。A）15 B）16 C）17 D）47每个分枝下面都有一个结点，所以总结点数N=2*15+1*32+0*叶子数+1(根节点）=63二叉树中除了双分支结点，单分支结点就是叶子结点。所以叶子数=63-15-32=16.50、树最适合用来表示( C )。 A）有序数据元素 B）无序数据元素 C）元素之间具有分支层次关系的数据 D）元素之间无联系的数据51、在顺序存储结构的线性表中第i个元素(1=inext =NULL C）head-next =head D）head!=NULL61、二维数组A33按行优先顺序存储，若数组元素A11的存储地址为1087，A22的存储地址为1095，则数组元素A00的存储地址为（A）。 A）1079 B）1080 C）1078 D）1060（1095-1087）/4 =2； A00 = A11-8 = 107962、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）A）队列 B）栈C）线性表 D）有序表63、对线性表进行折半查找时，要求线性表必须（ B ）。 A）以顺序方式存储 B）以顺序方式存储，且结点按关键字有序排列 C）以链式方式存储 D）以链式方式存储，且结点按关键字有序排列64、节点的带权路径是指从根节点到该节点的路径长度乘以该节点的权值，树的带权路径长度是指树中所有叶子节点的带权路径长度之和，已知叶子节点a,b,c的权分别是2,5,7左边给出的树的带权路径长度为（ A ）A）21 B）14C）22 D）28(2+5)*2+7=21 cabA65、对一棵有n个节点的二叉树按上述方法对节点进行编号，如果编号为i(inext = NULL B）p = NULL C）p-next =head D）p = head68、设无向图的邻接链表如图所示，则该图的边的数目是（B）A）4 B）5 C）10 D）20V2V1V4V369、下面的算法中（ A ）是用来构造最小生成树的算法。A）普里姆（Prim）算法B）迪杰斯特拉（Dijkstra）算法C）弗洛伊德（Floyd）算法 D）拓扑排序B: 是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。C: 是一种用于寻找给定的加权图中多源点之间最短路径的算法。D: 对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边+-(u,v)E(G)，则u在线性序列中出现在v之前。70、设有一个栈，元素依次进栈的顺序为A、B、C、D、E。下列( C )是不可能的出栈序列。 A）A,B,C,D,E B）B,C,D,E,A C）E,A,B,C,D D）E,D,C,B,A71、若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（A） A）f,c,b B）f,d,b C）g,c,b D）g,d,b72、排序算法中，不稳定的排序是（D）A）直接插入排序 B）冒泡排序C）堆排序 D）归并排序若待排序列中两数据元素具有相同值,在排序前后它们位置发生颠倒,则称该排序算法是不稳定的。73、堆排序是一种（ B ）排序。 A）插入 B）选择 C）交换 D）归并