1、数据结构导论真题 2013 年 10 月及答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(总题数：15，分数：30.00)1.下列几种算法时间复杂度中，最大的是_（分数：2.00）A.O(1)B.O(n)C.O(nlog2n)D.O(n2)2.数据结构中结点按逻辑关系依次排列形成一条“链”的结构是_（分数：2.00）A.集合B.图结构C.树形结构D.线性结构3.在表长为 100 的顺序表中做插入运算，平均移动元素的次数为_（分数：2.00）A.25B.33C.50D.1004.已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为_（分数：2.
2、00）A.O(1)B.O(1og2n)C.O(n)D.O(n2)5.下列表述正确的是_（分数：2.00）A.栈空时出栈产生“上溢”，栈满时进栈产生“下溢”B.栈空时出栈产生“下溢”，栈满时进栈产生“上溢”C.栈空时出栈和栈满时进栈均产生“上溢”D.栈空时出栈和栈满时进栈均产生“下溢”6.队列操作的原则是_（分数：2.00）A.先进先出B.后进先出C.先进后出D.只进不出7.一棵深度为 6 的满二叉树有_（分数：2.00）A.63 个结点B.64 个结点C.127 个结点D.128 个结点8.在一棵度为 3 的树中，度为 3 的结点有 4 个，度为 2 的结点有 2 个，度为 1 的结点有 3
3、个，则度为 0 的结点有_（分数：2.00）A.8 个B.10 个C.11 个D.12 个9.一棵二叉树 T，度为 2 的结点数为 20 个，则叶子结点数为_（分数：2.00）A.19 个B.20 个C.21 个D.22 个10.有 10 个叶结点的哈夫曼树中共有_（分数：2.00）A.10 个结点B.11 个结点C.19 个结点D.21 个结点11.求图中两个结点之间的最短路径采用的算法是_（分数：2.00）A.广度优先搜索(BFS)算法B.克鲁斯卡尔(Kruskal)算法C.普里姆(Prim)算法D.迪杰斯特拉(Dijkstra)算法12.顺序查找算法的平均查找长度为_（分数：2.00）A
4、.log2nB.(n-1)/2C.n/2D.(n+1)/213.二叉排序树中，根的_（分数：2.00）A.左子树是二叉排序树、右子树不一定是二叉排序树B.左子树是二叉排序树、右子树也是二叉排序树C.左子树不一定是二叉排序树、右子树是二叉排序树D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树14.冒泡排序的时间复杂度为_（分数：2.00）A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)15.关于稳定性的表述，正确的是_（分数：2.00）A.稳定性是排序方法本身的特性，与数据无关B.稳定性不是排序方法本身的特性，与数据有关C.稳定性是排序方法本身的特性，与数据有关D.稳
5、定性不是排序方法本身的特性，与数据无关二、第部分 非选择题(总题数：13，分数：26.00)16.数据中不可分割的最小标识单位是 1。 （分数：2.00）17.双向循环链表中，在 p 所指结点的后面插入一个新结点*t，需要修改 4 个指针，分别为：t-prior=p; 1; p-next-prior=t; p-next=t;。 （分数：2.00）18.在带有头结点的循环链表中，头指针为 head，判断指针 p 所指结点为首结点的条件是 1。 （分数：2.00）19.元素的进栈次序为 1，2，3，n，出栈的第一个元素是 n，则第 k 个出栈的元素是 1。 （分数：2.00）20.在栈结构中，允许
6、插入和删除的一端称为 1。 （分数：2.00）21.100 个结点的二叉树采用三叉链表存储时，空指针域 NULL 有 1 个。 （分数：2.00）22.某二叉树的先序遍历序列为 ABKLMNO，中序遍历序列为 BLKANMO，则该二叉树中结点 A 的右孩子为结点 1。 （分数：2.00）23.一个二叉树的最少结点个数为 1。 （分数：2.00）24.暂缺 （分数：2.00）25.设查找表有 n 个数据元素，则二分查找算法的平均查找长度为 1。 （分数：2.00）26.用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为 1。 （分数：2.00）27.若在线性表中采用二分查找法查找元素
7、，则该线性表必须按值有序，并且采用 1 存储结构。 （分数：2.00）28.堆分为最小堆和最大堆，若键值序列k 1 ，k 2 ，k n ，满足 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.设一个链栈的输入序列为 X，Y，Z，试写出出栈的所有可能的输出序列及其操作步骤。 （分数：6.00）_30.设二叉树的先序遍历序列为 DCBAHEIFG，中序遍历序列为 ABCHDIEFG，试画出该二叉树并写出后序遍历序列。 （分数：6.00）_31.已知连通带权图如下图所示，试利用普里姆(Prim)算法，从顶点 A 出发，构造它的最小生成树，并画出构造过程。 （分数：6.00）_32.
8、给定表(28，15，55，3，71，75，10，22，56)，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，并画出插入完成后的二叉排序树。 （分数：6.00）_33.应用直接选择排序算法，对初始关键字序列为 48，35，61，98，82，18，29，48 的记录进行从小到大排序，并写出排序过程和结果。 （分数：6.00）_四、算法设计题(总题数：2，分数：14.00)34.单链表的结点结构定义如下： typedef struct node int data; struct node * next; Node,*LinkList; 试编写在带头结点的单链表 head 中查找第 1
9、 个元素值小于 x 的结点的实现算法Node*GetLinklist(LinkList head, int x)，若找到，则返回指向该结点的指针，否则返回 NULL。 （分数：7.00）_35.假设树采用孩子兄弟链表表示法，其结构定义如下： typedef struct tnode DataType data; struct tnode *son,*brother; *Tree; 试编写算法 void leveltree(Tree root)实现树的按层次遍历。 （分数：7.00）_数据结构导论真题 2013 年 10 月答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(
10、总题数：15，分数：30.00)1.下列几种算法时间复杂度中，最大的是_（分数：2.00）A.O(1)B.O(n)C.O(nlog2n)D.O(n2) 解析：考点 算法时间复杂度 解析 按数量级递增排列，依次为 O(1)，O(n)，O(nlog 2 n)，O(n 2 )。2.数据结构中结点按逻辑关系依次排列形成一条“链”的结构是_（分数：2.00）A.集合B.图结构C.树形结构D.线性结构 解析：考点 线性表、图、树的基本概念 解析 集合并非完全按逻辑关系构成，且形成的不是链结构，图和树虽然按一定逻辑构成，但形成的不是链结构，只有线性结构符合。3.在表长为 100 的顺序表中做插入运算，平均移
11、动元素的次数为_（分数：2.00）A.25B.33C.50 D.100解析：考点 顺序表插入运算 解析 在等概率情况下插入，需要移动元素的平均次数为：n/2，n 代表总长度。4.已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为_（分数：2.00）A.O(1) B.O(1og2n)C.O(n)D.O(n2)解析：考点 链表的插入 解析 已知尾指针，可以立即定位到第一个结点，这样就可以直接将要插入的新节点在第一个结点后面插入，所以时间复杂度为 O(1)。5.下列表述正确的是_（分数：2.00）A.栈空时出栈产生“上溢”，栈满时进栈产生“下溢”B.栈空时出栈产生“下溢
12、”，栈满时进栈产生“上溢” C.栈空时出栈和栈满时进栈均产生“上溢”D.栈空时出栈和栈满时进栈均产生“下溢”解析：考点 栈的存储结构 解析 栈空时出栈产生“下溢”，栈满时进栈产生空间溢出，称为“上溢”。6.队列操作的原则是_（分数：2.00）A.先进先出 B.后进先出C.先进后出D.只进不出解析：考点 队列操作的基本原则 解析 队列的概念与现实生活中的排队相似，新来的成员加入队尾，排在前面的先离开，即先进先出。7.一棵深度为 6 的满二叉树有_（分数：2.00）A.63 个结点 B.64 个结点C.127 个结点D.128 个结点解析：考点 满二叉树的定义 解析 一颗深度为 k 且有 2k-1
13、 个结点的二叉树称为满二叉树。8.在一棵度为 3 的树中，度为 3 的结点有 4 个，度为 2 的结点有 2 个，度为 1 的结点有 3 个，则度为 0 的结点有_（分数：2.00）A.8 个B.10 个C.11 个 D.12 个解析：考点 树的特点 解析 树中度的总和为 19，即为树中边的总数，结点总数为边个总和+1，即 20，再减去 4 个度为 3 的，2 个度为 2 的，3 个度为 1 的结点，即度为 0 的结点个数为 11。9.一棵二叉树 T，度为 2 的结点数为 20 个，则叶子结点数为_（分数：2.00）A.19 个B.20 个C.21 个 D.22 个解析：考点 二叉树的性质 解
14、析 二叉树，若度为 0 的节点个数为 m，度为 2 的节点个数为 n，则 m=n+1。10.有 10 个叶结点的哈夫曼树中共有_（分数：2.00）A.10 个结点B.11 个结点C.19 个结点 D.21 个结点解析：考点 哈夫曼树的特点 解析 n 个叶子节点的哈夫曼树结点总数为 2n-1。11.求图中两个结点之间的最短路径采用的算法是_（分数：2.00）A.广度优先搜索(BFS)算法B.克鲁斯卡尔(Kruskal)算法C.普里姆(Prim)算法D.迪杰斯特拉(Dijkstra)算法 解析：考点 图的算法应用 解析 广度优先搜索算法是图的遍历算法的一种，普里姆算法和克鲁斯卡尔算法解决最小生成树
15、问题，迪杰斯特拉是解决最短路径的算法。12.顺序查找算法的平均查找长度为_（分数：2.00）A.log2nB.(n-1)/2C.n/2D.(n+1)/2 解析：考点 顺序查找算法长度 解析 ASL=(n+1)/2。13.二叉排序树中，根的_（分数：2.00）A.左子树是二叉排序树、右子树不一定是二叉排序树B.左子树是二叉排序树、右子树也是二叉排序树 C.左子树不一定是二叉排序树、右子树是二叉排序树D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树解析：考点 二叉排序树的定义 解析 二叉排序树的根的左右子树也分别为二叉排序树。14.冒泡排序的时间复杂度为_（分数：2.00）A.O(n)B.
16、O(nlog2n)C.O(n2) D.O(log2n)解析：考点 冒泡排序的时间复杂度 解析 冒泡排序是稳定的排序方法，其时间复杂度是 O(n 2 )。15.关于稳定性的表述，正确的是_（分数：2.00）A.稳定性是排序方法本身的特性，与数据无关 B.稳定性不是排序方法本身的特性，与数据有关C.稳定性是排序方法本身的特性，与数据有关D.稳定性不是排序方法本身的特性，与数据无关解析：考点 排序算法的稳定性 解析 一种排序方法如果是稳定的，则对所有的数据序列都是稳定的，稳定性是排序方法本身的特性，与数据无关。二、第部分 非选择题(总题数：13，分数：26.00)16.数据中不可分割的最小标识单位是
17、 1。 （分数：2.00）解析：数据元素 考点 数据元素的定义 解析 数据中不可分割的最小标识单位是数据元素。17.双向循环链表中，在 p 所指结点的后面插入一个新结点*t，需要修改 4 个指针，分别为：t-prior=p; 1; p-next-prior=t; p-next=t;。 （分数：2.00）解析：t-next=p-nextd 考点 双向循环链表的插入 解析 双向循环链表的插入顺序。18.在带有头结点的循环链表中，头指针为 head，判断指针 p 所指结点为首结点的条件是 1。 （分数：2.00）解析：if(p=head-next) 考点 单向循环链表的存储结构 解析 判断指针 p
18、所指结点为首节点的条件是 if(p=head-next)。19.元素的进栈次序为 1，2，3，n，出栈的第一个元素是 n，则第 k 个出栈的元素是 1。 （分数：2.00）解析：n-k+1 考点 出栈操作 解析 出栈第一个是 n，第二个是 n-1第 k 个是 n-k+1。n/k 为斜体。20.在栈结构中，允许插入和删除的一端称为 1。 （分数：2.00）解析：栈顶 考点 栈的概念 解析 允许插入和删除的一端是栈顶。21.100 个结点的二叉树采用三叉链表存储时，空指针域 NULL 有 1 个。 （分数：2.00）解析：102 考点 三叉链表的存储特点 解析 每个节点共有 3 个指针域，对于双亲
19、指针域，由于只有根节点没有双亲，所以在 100 节点中只有根节点的双亲指针域为空；对于左右孩子指针域，其必定指向一个子节点，而根节点不可能作为子节点，所以左右孩子指针域能指向的节点共有 99 个，则左右孩子指针域为空的个数为 2*100-99=101，故空指针域共有 101+1=102。22.某二叉树的先序遍历序列为 ABKLMNO，中序遍历序列为 BLKANMO，则该二叉树中结点 A 的右孩子为结点 1。 （分数：2.00）解析：M 考点 二叉树的排序遍历 解析 根据中序遍历知 NMO 是 A 的右子树组成，根据先序遍历，知 M 是 A 右孩子。23.一个二叉树的最少结点个数为 1。 （分数
20、：2.00）解析：0 考点 二叉树的定义 解析 二叉树是 n 个元素的有限集合，该集合或者为空，或者由一根及两棵互不相交的左右子树组成。24.暂缺 （分数：2.00）解析：暂缺25.设查找表有 n 个数据元素，则二分查找算法的平均查找长度为 1。 （分数：2.00）解析：log 2 (n+1)-1 考点 二分查找的平均查找长度 解析 可参见考点的定义。26.用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为 1。 （分数：2.00）解析：散列表 考点 散列表的定义 解析 散列表的定义。27.若在线性表中采用二分查找法查找元素，则该线性表必须按值有序，并且采用 1 存储结构。 （分数
21、：2.00）解析：顺序 考点 二分查找法的定义 解析 采用顺序存储，才可以使用二分法进行查找。28.堆分为最小堆和最大堆，若键值序列k 1 ，k 2 ，k n ，满足 （分数：2.00）解析：最大堆 考点 最大堆的定义 解析 最大堆的定义。三、应用题(总题数：5，分数：30.00)29.设一个链栈的输入序列为 X，Y，Z，试写出出栈的所有可能的输出序列及其操作步骤。 （分数：6.00）_正确答案：()解析：(1)X Y Z (2)X Z Y (3)Y Z X (4)Y X Z (5)Z Y X 考点 栈的应用 解析 (1)X 进 X 出，Y 进 Y 出，Z 进 Z 出；(3)X 进 X 出，Y
22、 进，Z 进 Z 出，Y 出；(3)X 进，Y 进 Y 出，Z进 Z 出，X 出；(4)X 进，Y 进 Y 出，X 出，Z 进 Z 出。30.设二叉树的先序遍历序列为 DCBAHEIFG，中序遍历序列为 ABCHDIEFG，试画出该二叉树并写出后序遍历序列。 （分数：6.00）_正确答案：()解析：31.已知连通带权图如下图所示，试利用普里姆(Prim)算法，从顶点 A 出发，构造它的最小生成树，并画出构造过程。 （分数：6.00）_正确答案：()解析：32.给定表(28，15，55，3，71，75，10，22，56)，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，并画出插入完
23、成后的二叉排序树。 （分数：6.00）_正确答案：()解析：33.应用直接选择排序算法，对初始关键字序列为 48，35，61，98，82，18，29，48 的记录进行从小到大排序，并写出排序过程和结果。 （分数：6.00）_正确答案：()解析：第 1 次选择排序：1848，35，61，98，82，29，48 第 2 次选择排序：18，2948，35，61，98，82，48 第 3 次选择排序：18，29，3548，61，98，82，48 第 4 次选择排序：18，29，35，4861，98，82，48 第 5 次选择排序：18，29，35，48，4861，98，82 第 6 次选择排序：18，
24、29，35，48，48，6198，82 第 7 次选择排序：18，29，35，48，48，61，8298 结果：18，29，35，48，48，61，82，98 考点 直接选择排序 解析 直接选择法每次挑出 t 原序列中的最小值放入排序序列。四、算法设计题(总题数：2，分数：14.00)34.单链表的结点结构定义如下： typedef struct node int data; struct node * next; Node,*LinkList; 试编写在带头结点的单链表 head 中查找第 1 个元素值小于 x 的结点的实现算法Node*GetLinklist(LinkList head,
25、int x)，若找到，则返回指向该结点的指针，否则返回 NULL。 （分数：7.00）_正确答案：()解析：Node *GetLinklist(LinkList head,int x) p=head-next; while(p!=NULL) if(p-datax) return p; p=p-next; return NULL; 考点 单链表的查找 解析 p 指针指向头结点的下一个结点，若 p 不为空，且 p 所指向的值小于 x，则返回，否则继续查找。35.假设树采用孩子兄弟链表表示法，其结构定义如下： typedef struct tnode DataType data; struct tn
26、ode *son,*brother; *Tree; 试编写算法 void leveltree(Tree root)实现树的按层次遍历。 （分数：7.00）_正确答案：()解析：void leveltree(Tree root) InitQueue Q; If(root) EnQueue(Q,root); while(!QueueEmpty(Q) p=DeQueue(Q); printf(p-data); If(p-son) EnQueue(Q,p-son); r=p-brother; while(r) EnQueue(Q,p-brother); r=r-brother; 考点 二叉树的遍历 解析 树的层次遍历，将结点入队列，若队列不空，则出队列，访问，并将 son 所指结点放入队列，若其 brother 所指结点存在，则依次放入队列中。循环判断队列是否为空，不空则重复上述过程。
