《数据结构》考前练兵

Andy老师

《数据结构》考前练兵
1.[单选题] 在下列排序方法中，（ ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)。
更多学习资料www.openhelp100.com
    A.插入排序
    B.希尔排序
    C.快速排序
    D.堆排序
    答:——C——
2.[单选题] 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
    A.空或只有一个结点
    B.高度等于其结点数
    C.任一结点无左孩子
    D.任一结点无右孩子
    答:——B——
3.[单选题] 程序段：sum=0; for (i=1;i＜n*n;i++) sum++;的平均情况下时间代价的θ表达式是（      ）。
    A.θ(1)
    B.θ(n)
    C.θ(n2)
    D.θ(nlogn)
    答:——C——
4.[单选题] 数据结构通常是研究数据的（ ）及它们之间的联系。
    A.存储和逻辑结构
    B.存储和抽象
    C.理想和抽象
    D.理想与逻辑
    答:————
5.[单选题] 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为（ ）。
    A.98
    B.99
    C.50
    D.48
    答:————
6.[单选题] 在有n个叶结点的Huffman树中, 其结点总数为（ ）。
    A.2n-1
    B.2n+1
    C.2n
    D.不确定   
    答:————
7.[单选题] 快速排序在（ ）情况下最易发挥其长处。
    A.被排序数据中含有多个相同排序码
    B.双链被排序数据已基本有序
    C.被排序数据完全无序
    D.被排序数据中最大值和最小值相差悬殊
    答:————
8.[单选题] 设有100个元素，用折半查找法进行查找时，最大比较次数是（ ）。
    A.25
    B.50
    C.10
    D.7
    答:————
9.[单选题] 由两个栈共享一个向量空间的好处是（ ）。
    A.减少存取时间,降低下溢发生的机率
    B.节省存储空间,降低上溢发生的机率
    C.减少存取时间,降低上溢发生的机率
    D.节省存储空间,降低下溢发生的机率
    答:————
10.[单选题] 若需要利用形参直接访问实参，则应把形参变量说明为（ ）参数。
    A.指针
    B.引用
    C.传值
    D.常值
    答:————
11.[单选题] 图的深度优先遍历类似于二叉树的（ ）。
    A.先序遍历
    B.中序遍历
    C.后序遍历
    D.层次遍历
    答:————
12.[单选题] 线性链表不具有的特点是（ ）。
    A.随机访问
    B.不必事先估计所需存储空间大小
    C.插入与删除时不必移动元素
    D.所需空间与线性表长度成正比
    答:————
13.[单选题] 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ）。
    A.顺序表
    B.用头指针表示的循环单链表
    C.用尾指针表示的循环单链表
    D.单链表
    答:————
14.[单选题] 数据结构在计算机内存中的表示是指（ ）。
    A.数据的存储结构
    B.数据结构
    C.数据的逻辑结构
    D.数据元素之间的关系
    答:————
15.[单选题] 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。
    A.edcba
    B.decba
    C.dceab
    D.abcde
    答:————
16.[单选题] 若不带头结点的单循环链表的头指针为head，则该链表只有一个结点的判定条件是（ ）。
    A.head==NULL
    B.head-＞next==NULL
    C.head!=NULL
    D.head-＞next==head
    答:————
17.[单选题] 设listarray[size]为一个顺序存储的栈, 变量top指示栈中第一个空闲位置, 栈为空的条件是（ ）。
    A.top=-1
    B.top=0
    C.top=size
    D.top=size-1
    答:————
18.[单选题] 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。
    A.front == rear
    B.front != NULL
    C.rear != NULL
    D.front == NULL
    答:————
19.[单选题] 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。
    A.O(1)
    B.O(m)
    C.O(n)
    D.O(m+n)
    答:————
20.[单选题] 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
    A.逻辑
    B.存储
    C.逻辑和存储
    D.物理
    答:————
21.[单选题] 设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为（ ）。
    A.O(1)
    B.O(log2n)
    C.O(n)
    D.O(n2)
    答:————
22.[单选题] 在一棵树中，（ ）没有前驱结点。
    A.分支结点
    B.叶结点
    C.树根结点
    D.空结点
    答:————
23.[单选题] 一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为（ ）。
    A.1
    B.2
    C.3
    D.4
    答:————
24.[单选题] 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（ ）。
    A.4
    B.5
    C.8
    D.9
    答:————
25.[单选题] 由同一关键字集合构造的各棵二叉排序树（ ）。
    A.其形态不一定相同，但平均查找长度相同。
    B.其形态不一定相同，平均查找长度也不一定相同。
    C.其形态均相同，但平均查找长度不一定相同。
    D.其形态均相同，平均查找长度也都相同。
    答:————
26.[单选题] 具有n个顶点的无向连通图最少有（ ）条边。
    A.n
    B.n+1
    C.n-1
    D.2n
    答:————
27.[单选题] 若某文件经内部排序得到100个初始归并段，若使用K路归并三趟完成，则（ ）。
    A.K＞=2
    B.K＞=3
    C.K＞=4
    D.K＞=5
    答:————
28.[单选题] 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的（ ）方法是散列文件的关键。
    A.散列函数
    B.除余法中的质数
    C.冲突处理
    D.散列函数和冲突处理
    答:————
29.[单选题] 在需要经常查找结点的前驱与后继的场合中，使用（ ）比较合适。
    A.单链表
    B.双链表
    C.顺序表
    D.循环链表
    答:————
30.[单选题] 在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于（ ）。
    A.2h-1
    B.2h+1
    C.2h-1
    D.2h
    答:————
31.[判断题] 若将一株树转换成二元树，则该二元树的根结点一定没有右子树。
    A.对
    B.错
    答:————
32.[判断题] 一般树和二叉树的结点数目都可以为0。
    A.对
    B.错
    答:————
33.[判断题] 在链式存储的栈的头部必须要设头结点。
    A.对
    B.错
    答:————
34.[判断题] 线性表的逻辑顺序与物理顺序总是一致的。
    A.对
    B.错
    答:————
35.[判断题] 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。
    A.对
    B.错
    答:————
36.[判断题] 在二叉树中插入结点，则该项二叉树便不再是二叉树。
    A.对
    B.错
    答:————
37.[判断题] 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得到的序列也一定相同。
    A.对
    B.错
    答:————
38.[判断题] 堆栈在数据中的存储原则是先进先出。
    A.对
    B.错
    答:————
39.[判断题] 用树的前序遍历序列和中序遍历序列可以导出树的后序遍历序列。
    A.对
    B.错
    答:————
40.[判断题] 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。
    A.对
    B.错
    答:————
41.[判断题] 线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。
    A.对
    B.错
    答:————
42.[判断题] 树的父链表示就是用数组表示树的存储结构。
    A.对
    B.错
    答:————
43.[判断题] AOE网中，只有一个入度为0的顶点（起始点），只有一个出度为0的顶点（结束点）。
    A.对
    B.错
    答:————
44.[判断题] 栈和队列逻辑上都是线性表。
    A.对
    B.错
    答:————
45.[判断题] 在AOE网中，关键路径是唯一的。
    A.对
    B.错
    答:————
46.[填空题] 折半搜索只适合用于 ##。
    答:————
47.[填空题] 栈结构允许进行删除操作的一端为 ##。
    答:————
48.[填空题] 若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为 ##。
    答:————
49.[填空题] 一棵具有５层满二叉树中节点总数为 ##。
    答:————
50.[填空题] 图的逆邻接表存储结构只适用于 ##图。
    答:————
51.[填空题] 设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为 ##。
    答:————
52.[填空题] 从树中一个结点到另一个结点之间的分支构成这两个结点之间的 ##。
    答:————
53.[填空题] 在无向图中，若从顶点A到顶点B存在 ##，则称A与B之间是连通的。
    答:————
54.[填空题] 关键码分别为10，20，30，40的四个结点，能构造出 ##种不同的二叉搜索树。
    答:————
55.[填空题] 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的外部路径权重为 ##。
    答:————
56.[填空题] 冒泡排序在最好情况下的元素交换次数为 ##。
    答:————
57.[填空题] 若频繁地对线性表进行插入与删除操作，该线性表应采用 ##存储结构。
    答:————
58.[填空题] ##链表从任何一个结点出发，都能访问到所有结点。
    答:————
59.[填空题] 某带头结点的单链表的头指针head，判定该单链表非空的条件 ##。
    答:————
60.[填空题] 数据结构算法中，通常用时间复杂度和 ##两种方法衡量其效率。
    答:————
61.[问答题] 应用题已知一棵非空二叉树,其按中序和后序遍历的结果分别为: 中序:CGBAHEDJFI 后序:GBCHEJIFDA 请画出这棵二叉树,并写出其前序遍历的结果。
    答:————
62.[问答题] 应用题设有一个关键码的输入序列{ 55, 88, 100, 120, 90, 150, 40, 20,95},从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。若发生不平衡,指明需做的平衡旋转的类型及平衡旋转的结果。
    答:————
63.[问答题] 设计在顺序有序表中实现二分查找的算法。
    答:————
64.[问答题] 设计判断二叉树是否为二叉排序树的算法。
    答:————
65.[问答题] 算法与程序有何区别和联系？
    答:————
66.[问答题] 在链式存储结构上设计直接插入排序算法。
    答:————
67.[问答题] 设计在链式结构上实现简单选择排序算法。
    答:————
68.[问答题] 设计求结点在二叉排序树中层次的算法。
    答:————
69.[问答题] 树的存储方法主要有哪些？简要说明各种存储方法的结构。
    答:————
70.[问答题] 设计在顺序存储结构上实现求子串算法。
    答:————
71.[问答题] 设计计算二叉树中所有结点值之和的算法。
    答:————
72.[问答题] 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。
    答:————
73.[问答题] 设计一个在链式存储结构上统计二叉树中结点个数的算法。
    答:————
74.[问答题] 设计将所有奇数移到所有偶数之前的算法。
    答:————
75.[问答题] 设计判断单链表中元素是否是递增的算法。
    答:————
76.[问答题] 设计在链式存储结构上合并排序的算法。
    答:————
77.[问答题] 已知序列（12，4，17，10，7，30），用直接选择排序法对其进行递增排序，写出每一趟的排序结果。
    答:————
78.[问答题] 单链表结点的类型定义如下：
typedef struct LNode {
??????? int data;
??????? struct LNode *next;
} LNode, *Linklist;
写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。（注：不破坏A和B的原有结构）
    答:————
79.[问答题] 编写实现“直接插入排序”的子函数，入口参数是整型数组L[ ]和数组长度n。
    答:————

更多学习资料www.openhelp100.com