全国2023年1月数据结构导论试题课程**：02142
一、单项选择题(本大题共15小题，每小题2分，共30分)
1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )a.集合 b.线性结构 c.树形结构 d.图状结构。
2.下面算法程序段的时间复杂度为( )
for ( int i=0; ifor ( int j=0; ja［i］［j］=i*j;
a. o(m2b. o(n2) c. o(mnd. o(m+n)
3.线性结构是( )a.具有n（n≥0）个表元素的有穷序列 b.具有n（n≥0）个字符的有穷序列。
c.具有n（n≥0）个结点的有穷序列 d.具有n（n≥0）个数据项的有穷序列
4.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是( )
a. o(1) b. o() c. o(log2n) d. o(n)
5.关于串的叙述，正确的是( )a.串是含有一个或多个字符的有穷序列 b.空串是只含有空格字符的串。
c.空串是含有零个字符或含有空格字符的串 d.串是含有零个或多个字符的有穷序列。
6.栈的输入序列依次为1，2，3，4，则不可能的出栈序列是( )a.1243 b. 1432 c. 2134 d.4312
7.队列是( )a. 先进先出的线性表 b. 先进后出的线性表 c. 后进先出的线性表 d.随意进出的线性表。
8.10阶上三角矩阵压缩存储时需存储的元素个数为a.11 b.56 c.100 d.101
9.深度为k（k≥1）的二叉树，结点数最多有( )a.2k 个 b.(2k -1)个 c.2k-1个 d.(2k+1)个。
10.具有12个结点的二叉树的二叉链表存储结构中，空链域null的个数为( )a. 11 b.13 c. 23 d. 25
11.具有n个顶点的无向图的边数最多为( )d.2n(n+1)
12.三个顶点v1,v2,v3的图的邻接矩阵为，该图中顶点v3的入度为( )a. 0 b. 1 c. 2 d. 3
13.顺序存储的**中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为( )a.
20000 b.30000 c.40000 d.
60000
14.外存储器的主要特点是( )
a.容量小和存取速度低 b.容量大和存取速度低 c.容量大和存取速度高 d.容量小和存取速度高。
15.在待排数据基本有序的前提下，效率最高的排序算法是()a.直接插入排序 b.直接选择排序c.快速排序d.归并排序。
二、填空题(本大题共13小题，每小题2分，共26分)
16.数据的不可分割的最小标识单位是___它通常不具有完整确定的实际意义，或不被当作一个整体对待。
17.运算分为加工型运算和引用型运算，读取操作是___运算。
18.带有头结点的单向循环链表l（l为头指针）中，指针p所指结点为尾结点的条件是 __
19.在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句 __
20.元素s1，s2，s3，s4，s5，s6依次进入顺序栈s，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为 __
21. 稀疏矩阵一般采用的压缩存储方法是___
22. 在一棵树中，__结点没有双亲。
23.一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为1，若编号为i的结点有父结点，那么其父结点的编号为 __
24.二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是___
25.边稀疏的无向图采用 __存储较省空间。
26.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为 __
27.二分查找算法的时间复杂度是 __
28.要将序列建成堆，则只需把18与 __相互交换。
三、应用题(本大题共5小题，每小题6分，共30分)
29.将题29图所示的一棵二叉树转换成对应的森林。
题29图题31图题32图。
30.给定权值｛3，9，13，5，7｝，构造相应的哈夫曼（huffman）树，并计算其带权路径长度。
31.写出题31图的邻接矩阵和每个顶点的入度与出度。
32. 二叉排序树的各结点的值依次为20~28，请在题32图中标出各结点的值。
33.用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。
四、算法设计题(本大题共2小题，每小题7分，共14分)
34.设线性表a =（a1， a2， …am），b=（b1, b2, …bn），试写一个按下列规则合并a，b为线性表c的算法，使得。
c=（a1, b1, …am ,bm ,bm+1, …bn） 当m≤n时；
或者 c=（a1, b1, …an ,bn ,an+1, …am） 当m>n时。
线性表a，b和c均以带头结点的单链表作为存储结构，且c表利用a表和b表中的结点空间构成。（注意：单链表的长度值m和n均未显式存储。）
35. 二叉树的二叉链表类型定义如下：
typedef struct btnode {
datatype data;
struct btnode *lchild,*rchild;
bitreptr;
写出后根遍历根指针为t的二叉树的递归算法( void postorder (bitreptr *t) )
全国数据结构导论试题
全国2011年10月数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.设栈s和队列q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈s，元素退栈后即进入队列q，若6个元素的出队序列是e2，e4，e3，e6，e5，e1，则栈s的容量至少为 a...
全国数据结构导论试题
全国2013年1月高等教育自学考试。数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.数据的基本单位是。a.数据元素 b.数据项。c.字段 d.域。2.算法的空间复杂度是指。a.算法中输入数据所占用的存储空间的大小。b.算法本身所占用的存储空间的大小。c....
数据结构导论试题
一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 二00一年下半年全国高等教育自学考试。数据结构导论试卷。一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 2.在一个具有n个结点的单链表达中查找值为m的某结点，若查找成功，则...