历年数据结构
本试卷为历年数据结构，题目包括：单项选择题。
本卷包括如下题型：
数据结构
一、单项选择题 （共50题，每题2分，共计100分）
（ D ）
1、在带权图的最短路径问题中,路径长度是指。
（ B ）
2、若要求尽可能快地对序列进行稳定的排序,则应选( B )。
（ A ）
3、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( A )。
（ A ）
4、数据的四种存储结构是()。
（ A ）
5、(4分)在一个单链表中,已知q指向p所指向结点的前趋结点,若在q. p所指结点之间插入一个s所指向的新结点,则执行的操作是(A)。
（ D ）
6、(4分) 指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点,要将两个链表链接成-一个新的单循环链表,应执行的操作为(D)。
（ D ）
7、(10分)已知关键字序列为(66,82, 25, 51, 98, 108}, 利用快速排序方法,以第- 一个元素为基准得到的一 趟排序结果为(D)。
（ C ）
8、输入序列为ABC,可以变为CBA时,经过的栈操作为()。
（ C ）
9、假定在一棵二叉树中,度为 2 的结点的数目为 6,则该二叉树中叶子结点的数目是( )。
（ D ）
10、若线性表最常用的操作是存取第i个元素及其前驱的值,则采用()存储方式节省时间。
（ A ）
11、以下错误的是()。
（ B ）
12、对顺序表上的插入、删除算法的时间复杂性分析来说,常以()为标准操作。
（ C ）
13、给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，冒泡排序(大数下沉)的第一趟排序结果应为
（ B ）
14、若一组记录的排序码值序列为{50，80，30，40，70，60}利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为
（ D ）
15、数据结构这门学科的研究内容下面选项最准确的是
（ C ）
16、折半搜索与二叉排序树的时间性能（ ）。
（ D ）
17、广度优先遍历类似于二叉树的（ ）。
（ C ）
18、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。
（ D ）
19、循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
（ B ）
20、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。
（ A ）
21、数组A中，每个元素A的长度为3个字节，行下标i从1到5，列下标j从1到6，从首地址开始连续存放在存储器内，存放该数组至少需要的单元数是（ ）。
（ C ）
22、单链表的存储密度为（ ）。
（ D ）
23、既希望查找速度快又便于线性表动态变化的查找方法有（）
（ C ）
24、下列关于线性链表的叙述中,正确的是()。
（ A ）
25、设顺序表的长度为 n。下列排序方法中,最坏情况下比较次数小于 n(n-1)/2 的是()。
（ C ）
26、设某强连通图中有n个顶点，则该强连通图中至少有（ ）。条边。
（ A ）
27、下列程序段的时间复杂度为（ ）。 for(i=0； i
（ C ）
28、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）。(1<=i<=n+1)。
（ A ）
29、算法的时间复杂度是由（ ）决定的。
（ A ）
30、线性链表是通过何种方式表示元素之间的关系（ ）。
（ C ）
31、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是
（ A ）
32、判断带头结点的单链表为空表的条件是( ),假设头指针为head。 (3.0分)
（ A ）
33、抽象数据类型的三个组成部分分别为( )。
（ C ）
34、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为( )。
（ A ）
35、一个顺序栈S,空栈时top的初始值为0,其栈顶指针为top,则将元素e入栈的操作是( )。
（ C ）
36、五节车厢以编号1,2,3,4,5顺序进入铁路调度站(栈),可以得到( )的编组。
（ D ）
37、正常情况下,删除非空的顺序存储结构的堆栈的栈顶元素,栈顶指针top的变化是( )。
（ A ）
38、将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子编号为( )。
（ C ）
39、用链接方式存储的带头结点的队列,在进行插入运算时
（ D ）
40、以下数据结构中哪一个是非线性结构?
（ A ）
41、设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为( )。
（ A ）
42、执行一趟快速排序能够得到的序列是( )。
（ A ）
43、有n个数据的二叉排序树最大可能深度是( )
（ C ）
44、一个具有1025个结点的二叉树的高度是为( )
（ A ）
45、栈通常采用的两种存储结构是（ ）
（ A ）
46、用单链表表示的链式队列的队首在链表的（ ）位置
（ C ）
47、一棵树的广义表表示为 a(b(c)，d(e(g(h))，f，k))，则该树的叶子结点个数为（ ）。
（ B ）
48、以下说法错误的是（ ）
（ C ）
49、有一份电文中共使用 5 个字符：a、b、c、d、e，它们的出现频率依次为 4、7、5、2、9，对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造）中字符 a 的赫夫曼编码长度为 （ ）
（ B ）
50、表示一个有 100 个顶点，1000 条边的非带权有向图的邻接矩阵有（ ） 个非零矩阵元素。
相关标签：
- 数据结构